1 /**
2 * @file rm_allocator.c
3 *
4 * @brief
5 * This is the Resource Manager allocator source.
6 *
7 * \par
8 * ============================================================================
9 * @n (C) Copyright 2012-2015, Texas Instruments, Inc.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 *
15 * Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 *
18 * Redistributions in binary form must reproduce the above copyright
19 * notice, this list of conditions and the following disclaimer in the
20 * documentation and/or other materials provided with the
21 * distribution.
22 *
23 * Neither the name of Texas Instruments Incorporated nor the names of
24 * its contributors may be used to endorse or promote products derived
25 * from this software without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
28 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
29 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
30 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
31 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
32 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
33 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
34 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
35 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
36 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
37 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 *
39 * \par
40 */
42 /* RM external includes */
43 #include <ti/drv/rm/rm.h>
45 /* RM internal includes */
46 #include <ti/drv/rm/include/rm_internal.h>
47 #include <ti/drv/rm/include/rm_loc.h>
48 #include <ti/drv/rm/include/rm_allocatorloc.h>
49 #include <ti/drv/rm/include/rm_dtb_utilloc.h>
50 #include <ti/drv/rm/include/rm_policyloc.h>
51 #include <ti/drv/rm/include/rm_treeloc.h>
53 /* RM LIBFDT includes */
54 #include <ti/drv/rm/util/libfdt/libfdt.h>
56 /* Tree algorithm includes */
57 #include <ti/drv/rm/util/tree.h>
59 /* RM OSAL layer */
60 #include <rm_osal.h>
62 /**********************************************************************
63 ************************ Local Functions *****************************
64 **********************************************************************/
66 /* FUNCTION PURPOSE: Checks a resource node's ownership
67 ***********************************************************************
68 * DESCRIPTION: Returns the owner reference count if the provided
69 * instance node is in the list of resource node owners.
70 * Otherwise, returns 0.
71 */
72 static int allocatorResNodeIsOwnedBy(Rm_Handle rmHandle, Rm_ResourceNode *node,
73 Rm_PolicyValidInstNode *serviceInstNode)
74 {
75 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
76 Rm_Owner *owner = node->ownerList;
78 while (owner) {
79 RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
80 if (owner->instNameNode == serviceInstNode) {
81 return(owner->refCnt);
82 }
83 owner = owner->nextOwner;
84 }
85 return(0);
86 }
88 /* FUNCTION PURPOSE: Increments an owner's refCnt
89 ***********************************************************************
90 * DESCRIPTION: Increments a resource owner's reference count
91 */
92 static void allocatorResNodeOwnerRefCntInc(Rm_Handle rmHandle,
93 Rm_ResourceNode *node,
94 Rm_PolicyValidInstNode *serviceInstNode)
95 {
96 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
97 Rm_Owner *owner = node->ownerList;
99 while (owner) {
100 RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
101 if (owner->instNameNode == serviceInstNode) {
102 owner->refCnt++;
103 RM_SS_OBJ_WB(rmInst, owner, Rm_Owner);
104 break;
105 }
106 owner = owner->nextOwner;
107 }
108 }
110 /* FUNCTION PURPOSE: Decrements an owner's refCnt
111 ***********************************************************************
112 * DESCRIPTION: Decrements a resource owner's reference count
113 */
114 static void allocatorResNodeOwnerRefCntDec(Rm_Handle rmHandle,
115 Rm_ResourceNode *node,
116 Rm_PolicyValidInstNode *serviceInstNode)
117 {
118 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
119 Rm_Owner *owner = node->ownerList;
121 while (owner) {
122 RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
123 if (owner->instNameNode == serviceInstNode) {
124 owner->refCnt--;
125 RM_SS_OBJ_WB(rmInst, owner, Rm_Owner);
126 break;
127 }
128 owner = owner->nextOwner;
129 }
130 }
132 /* FUNCTION PURPOSE: Returns an owner's refCnt
133 ***********************************************************************
134 * DESCRIPTION: Returns a resource owner's reference count
135 */
136 static uint16_t allocatorResNodeOwnerGetRefCnt(Rm_Handle rmHandle,
137 Rm_ResourceNode *node,
138 Rm_PolicyValidInstNode *serviceInstNode)
139 {
140 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
141 Rm_Owner *owner = node->ownerList;
143 while (owner) {
144 RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
145 if (owner->instNameNode == serviceInstNode) {
146 return (owner->refCnt);
147 }
148 owner = owner->nextOwner;
149 }
151 return(0);
152 }
154 /* FUNCTION PURPOSE: Adds an owner to an allocator resource
155 ***********************************************************************
156 * DESCRIPTION: Adds a RM instance node to a resource node's
157 * list of owners. If the owner is already present that
158 * owner's reference count is incremented
159 */
160 static void allocatorResNodeOwnerAdd(Rm_Handle rmHandle, Rm_ResourceNode *node,
161 Rm_PolicyValidInstNode *serviceInstNode)
162 {
163 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
164 Rm_Owner *ownerList = node->ownerList;
165 Rm_Owner *newOwner = NULL;
167 if (allocatorResNodeIsOwnedBy(rmHandle, node, serviceInstNode)) {
168 allocatorResNodeOwnerRefCntInc(rmHandle, node, serviceInstNode);
169 } else {
170 newOwner = Rm_osalMalloc(sizeof(*newOwner));
172 if (newOwner) {
173 newOwner->instNameNode = serviceInstNode;
174 newOwner->refCnt = 0;
175 newOwner->nextOwner = NULL;
177 /* Add owner entry to end of list */
178 if (ownerList) {
179 RM_SS_OBJ_INV(rmInst, ownerList, Rm_Owner);
180 while (ownerList->nextOwner) {
181 ownerList = ownerList->nextOwner;
182 RM_SS_OBJ_INV(rmInst, ownerList, Rm_Owner);
183 }
184 ownerList->nextOwner = newOwner;
185 RM_SS_OBJ_WB(rmInst, ownerList, Rm_Owner);
186 } else {
187 node->ownerList = newOwner;
188 }
190 node->allocationCount++;
191 newOwner->refCnt++;
192 newOwner->instNameNode->allocRefCount++;
193 RM_SS_OBJ_WB(rmInst, newOwner, Rm_Owner);
194 RM_SS_OBJ_WB(rmInst, newOwner->instNameNode,
195 Rm_PolicyValidInstNode);
196 }
197 }
198 }
200 /* FUNCTION PURPOSE: Compares two resource node's boundaries
201 ***********************************************************************
202 * DESCRIPTION: Returns TRUE if the resource nodes are neighbors from
203 * a base+length perspective. Otherwise, returns FALSE.
204 */
205 static int allocatorResNodeBoundaryCompare(Rm_ResourceNode *node1,
206 Rm_ResourceNode *node2)
207 {
208 uint32_t node1End;
209 uint32_t node2End;
211 if (node1 && node2) {
212 node1End = node1->base + node1->length - 1;
213 node2End = node2->base + node2->length - 1;
215 if (node1->base < node2->base) {
216 if (node1End == (node2->base - 1)) {
217 return(RM_TRUE);
218 }
219 } else if (node2->base < node1->base) {
220 if (node2End == (node1->base - 1)) {
221 return(RM_TRUE);
222 }
223 }
224 /* else: fall through to return false, not neighbors */
225 }
226 return(RM_FALSE);
227 }
229 /* FUNCTION PURPOSE: Compares two resource node's owners
230 ***********************************************************************
231 * DESCRIPTION: Returns TRUE if the owners of two resource nodes
232 * are equivalent. Otherwise, returns FALSE.
233 */
234 static int allocatorResNodeOwnerCompare(Rm_Handle rmHandle,
235 Rm_ResourceNode *node1,
236 Rm_ResourceNode *node2)
237 {
238 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
239 Rm_Owner *node1Owners = node1->ownerList;
240 Rm_Owner *node2Owners = node2->ownerList;
241 int matchedInst;
243 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
244 while(node2Owners) {
245 Rm_osalBeginMemAccess((void *)node2Owners, sizeof(*node2Owners));
246 node2Owners = node2Owners->nextOwner;
247 }
248 node2Owners = node2->ownerList;
249 }
251 if (node1->allocationCount == node2->allocationCount) {
252 while (node1Owners) {
253 RM_SS_OBJ_INV(rmInst, node1Owners, Rm_Owner);
254 matchedInst = RM_FALSE;
255 while (node2Owners) {
256 if ((node1Owners->instNameNode == node2Owners->instNameNode) &&
257 (node1Owners->refCnt == node2Owners->refCnt)) {
258 matchedInst = RM_TRUE;
259 break;
260 }
261 node2Owners = node2Owners->nextOwner;
262 }
264 if (matchedInst) {
265 node2Owners = node2->ownerList;
266 node1Owners = node1Owners->nextOwner;
267 } else {
268 return(RM_FALSE);
269 }
270 }
271 } else {
272 return(RM_FALSE);
273 }
275 return(RM_TRUE);
276 }
278 /* FUNCTION PURPOSE: Deletes an owner from an allocator resource
279 ***********************************************************************
280 * DESCRIPTION: Removes a RM owner entry from a resource node's
281 * list of owners. If the refCnt for the specified
282 * owner is greater than 1 only the refCnt is
283 * decremented
284 */
285 static void allocatorResNodeOwnerDelete(Rm_Handle rmHandle,
286 Rm_ResourceNode *node,
287 void *serviceInstNode)
288 {
289 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
290 Rm_Owner *owner = node->ownerList;
291 Rm_Owner *prevOwner = NULL;
293 if (allocatorResNodeIsOwnedBy(rmHandle, node, serviceInstNode) > 1) {
294 allocatorResNodeOwnerRefCntDec(rmHandle, node, serviceInstNode);
295 } else {
296 while (owner) {
297 RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
298 if (owner->instNameNode == serviceInstNode) {
299 break;
300 }
301 prevOwner = owner;
302 owner = owner->nextOwner;
303 }
305 if (owner) {
306 if (prevOwner == NULL) {
307 node->ownerList = owner->nextOwner;
308 } else {
309 prevOwner->nextOwner = owner->nextOwner;
310 RM_SS_OBJ_WB(rmInst, prevOwner, Rm_Owner);
311 }
313 node->allocationCount--;
314 owner->instNameNode->allocRefCount--;
315 RM_SS_OBJ_WB(rmInst, owner->instNameNode, Rm_PolicyValidInstNode);
316 Rm_osalFree((void *)owner, sizeof(*owner));
317 }
318 }
319 }
321 /* FUNCTION PURPOSE: Copies the owners of a resource node
322 ***********************************************************************
323 * DESCRIPTION: Creates a list of resource owners for the destination
324 * resource node that is equivalent to the source resource
325 * node's owners
326 *
327 * dstNode must be a newly created node without any owners.
328 */
329 static void allocatorResNodeOwnerCopy(Rm_Handle rmHandle,
330 Rm_ResourceNode *dstNode,
331 Rm_ResourceNode *srcNode)
332 {
333 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
334 Rm_Owner *srcOwnerList = srcNode->ownerList;
335 Rm_Owner *dstNewOwner;
336 Rm_Owner *dstPrevOwner;
338 if (dstNode->ownerList != NULL) {
339 return;
340 }
341 dstNode->allocationCount = srcNode->allocationCount;
343 while (srcOwnerList) {
344 RM_SS_OBJ_INV(rmInst, srcOwnerList, Rm_Owner);
345 dstNewOwner = Rm_osalMalloc(sizeof(*dstNewOwner));
346 dstNewOwner->instNameNode = srcOwnerList->instNameNode;
347 dstNewOwner->refCnt = srcOwnerList->refCnt;
348 dstNewOwner->nextOwner = NULL;
349 RM_SS_OBJ_WB(rmInst, dstNewOwner, Rm_Owner);
351 if (dstNode->ownerList == NULL) {
352 dstNode->ownerList = dstNewOwner;
353 } else {
354 dstPrevOwner->nextOwner = dstNewOwner;
355 RM_SS_OBJ_WB(rmInst, dstPrevOwner, Rm_Owner);
356 }
357 dstPrevOwner = dstNewOwner;
358 srcOwnerList = srcOwnerList->nextOwner;
359 }
360 }
362 /* FUNCTION PURPOSE: Clears a resource node's owners
363 ***********************************************************************
364 * DESCRIPTION: Deletes all owners from the owners list of a
365 * resource node.
366 */
367 static void allocatorResNodeOwnerClear(Rm_Handle rmHandle,
368 Rm_ResourceNode *node)
369 {
370 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
371 Rm_Owner *owner = node->ownerList;
372 Rm_Owner *nextOwner;
374 while (owner) {
375 RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
376 nextOwner = owner->nextOwner;
377 node->allocationCount--;
378 owner->instNameNode->allocRefCount--;
379 RM_SS_OBJ_WB(rmInst, owner->instNameNode, Rm_PolicyValidInstNode);
380 Rm_osalFree((void *)owner, sizeof(*owner));
381 owner = nextOwner;
382 }
383 }
385 /* FUNCTION PURPOSE: Get the status for an allocator resource
386 ***********************************************************************
387 * DESCRIPTION: Called when a resource status request is made. The
388 * resource's allocator is searched for the resource base
389 * and length specified in the transaction. The
390 * resource's owner reference count is returned if the
391 * resource range is found.
392 */
393 static int32_t allocatorStatus(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
394 Rm_AllocatorOpInfo *opInfo)
395 {
396 Rm_ResourceNode findNode;
397 Rm_ResourceNode *matchingNode = NULL;
398 uint32_t matchingEnd;
399 uint32_t findEnd;
400 int32_t retVal;
402 memset((void *)&findNode, 0, sizeof(findNode));
403 findNode.base = opInfo->resourceInfo->base;
404 findNode.length = opInfo->resourceInfo->length;
405 matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
406 &findNode);
408 if (matchingNode) {
409 matchingEnd = matchingNode->base + matchingNode->length - 1;
410 findEnd = findNode.base + findNode.length - 1;
411 if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
412 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
413 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
414 matchingNode,
415 opInfo->serviceInstNode);
416 retVal = RM_SERVICE_APPROVED;
417 } else {
418 retVal = RM_SERVICE_DENIED_PARTIAL_STATUS;
419 }
420 } else {
421 retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
422 }
424 return(retVal);
425 }
427 /* FUNCTION PURPOSE: Preallocates an allocator resource
428 ***********************************************************************
429 * DESCRIPTION: Called when an allocate request is made but the base
430 * is unspecified. The preallocation algorithm looks at
431 * available resources as well as policy permissions to
432 * determine a resource range that satisfies the request.
433 * If a valid range is found it will be returned for the
434 * treeAllocate algorithm to handle.
435 */
436 static int32_t allocatorPreAllocate(Rm_Handle rmHandle,
437 Rm_AllocatorNode *allocator,
438 Rm_AllocatorOpInfo *opInfo)
439 {
440 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
441 Rm_ResourceNode findNode;
442 Rm_ResourceNode *matchingNode = NULL;
443 Rm_ResourceNode *nextNode;
444 uint32_t matchingEnd;
445 uint32_t findEnd;
446 uint32_t rangeIndex;
447 int resourceFound = RM_FALSE;
448 Rm_PolicyCheckType policyCheckType;
449 Rm_PolicyCheckCfg policyCheckCfg;
450 int nodePassesPolicy;
451 int32_t retVal = RM_OK;
453 if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) {
454 policyCheckType = Rm_policyCheck_INIT;
455 } else if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE) {
456 policyCheckType = Rm_policyCheck_USE;
457 } else {
458 retVal = RM_ERROR_INVALID_SERVICE_TYPE;
459 return(retVal);
460 }
462 if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
463 /* Set base to first node's base since CD will not have all resources
464 * like Server */
465 matchingNode = RB_MIN(_Rm_AllocatorResourceTree, allocator->resourceRoot);
466 opInfo->resourceInfo->base = matchingNode->base;
467 } else {
468 int32_t tmpBase;
470 retVal = rmPolicyGetResourceBase(allocator->policyRoot,
471 opInfo->serviceInstNode,
472 policyCheckType, &tmpBase);
473 if (retVal == RM_OK) {
474 opInfo->resourceInfo->base = tmpBase;
475 } else {
476 return(retVal);
477 }
478 }
480 if (opInfo->resourceInfo->alignment == RM_RESOURCE_ALIGNMENT_UNSPECIFIED) {
481 /* Get alignment from policy */
482 opInfo->resourceInfo->alignment = rmPolicyGetAllocAlign(allocator->policyRoot);
483 }
485 if (opInfo->resourceInfo->alignment == 0) {
486 opInfo->resourceInfo->alignment = 1;
487 }
489 memset((void *)&findNode, 0, sizeof(findNode));
490 findNode.base = opInfo->resourceInfo->base;
491 findNode.length = opInfo->resourceInfo->length;
493 /* Configure policy checking structure */
494 memset((void *)&policyCheckCfg, 0, sizeof(policyCheckCfg));
495 policyCheckCfg.polTree = allocator->policyRoot;
497 do {
498 matchingNode = RB_FIND(_Rm_AllocatorResourceTree,
499 allocator->resourceRoot, &findNode);
501 if (matchingNode) {
502 matchingEnd = matchingNode->base + matchingNode->length - 1;
503 findEnd = findNode.base + findNode.length - 1;
504 nodePassesPolicy = RM_BOOL_UNDEF;
505 if ((matchingNode->allocationCount == 0) &&
506 (findNode.base >= matchingNode->base) &&
507 (findEnd <= matchingEnd)) {
508 /* Attempt to preallocate from node only if not owned by anyone
509 * and sits within a matching node. */
510 policyCheckCfg.type = policyCheckType;
511 policyCheckCfg.negCheck = RM_FALSE;
512 policyCheckCfg.validInstNode = opInfo->serviceInstNode;
513 policyCheckCfg.resourceBase = findNode.base;
514 policyCheckCfg.resourceLength = findNode.length;
515 nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg);
517 if (nodePassesPolicy) {
518 /* Is range excluded from UNSPECIFIED allocations? */
519 policyCheckCfg.type = Rm_policyCheck_UNSPEC_EXCLUSION;
520 policyCheckCfg.negCheck = RM_TRUE;
521 nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg);
522 }
524 if (nodePassesPolicy) {
525 /* Initialize indexer to be first resource value that
526 * alignment satisfies */
527 rangeIndex = findNode.base;
528 if (rangeIndex % opInfo->resourceInfo->alignment) {
529 rangeIndex += (opInfo->resourceInfo->alignment -
530 (rangeIndex %
531 opInfo->resourceInfo->alignment));
532 }
534 if ((rangeIndex + opInfo->resourceInfo->length - 1) <=
535 matchingEnd) {
536 /* Block of unallocated resources within matchingNode
537 * that satisfies allocate requirements */
538 opInfo->resourceInfo->base = rangeIndex;
539 resourceFound = RM_TRUE;
540 retVal = RM_SERVICE_PROCESSING;
541 }
542 }
543 }
545 if (!resourceFound) {
546 /* Check next resource node for available resources */
547 if (findNode.base < matchingNode->base) {
548 findNode.base = matchingNode->base;
549 } else {
550 if (!nodePassesPolicy) {
551 findNode.base += findNode.length;
552 } else {
553 /* Matching node allocated, move to next node */
554 if ((nextNode = RB_NEXT(_Rm_AllocatorResourceTree,
555 allocator->resourceRoot,
556 matchingNode))) {
557 findNode.base = nextNode->base;
558 } else {
559 retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
560 }
561 }
562 }
563 }
564 } else {
565 retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
566 }
567 } while ((!resourceFound) &&
568 (retVal != RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET));
570 return(retVal);
571 }
573 /* FUNCTION PURPOSE: Allocates an allocator resource
574 ***********************************************************************
575 * DESCRIPTION: Will attempt to allocate the resource with specified
576 * base and length from the resource's allocator. The
577 * allocation algorithm will verify the allocation against
578 * the policy permissions for the instance requesting the
579 * allocation. If the policy allows the allocation the
580 * algorithm will allocate the resource then combine any
581 * resource nodes that may have become equivalent (in terms
582 * of ownership) after the allocation.
583 */
584 static int32_t allocatorAllocate(Rm_Handle rmHandle,
585 Rm_AllocatorNode *allocator,
586 Rm_AllocatorOpInfo *opInfo)
587 {
588 Rm_ResourceNode findNode;
589 Rm_ResourceNode *matchingNode = NULL;
590 Rm_ResourceNode *leftNode = NULL;
591 Rm_ResourceNode *rightNode = NULL;
592 Rm_PolicyCheckType policyCheckType;
593 Rm_PolicyCheckCfg checkCfg;
594 int32_t allocPassesPolicy;
595 int combineLeft = RM_FALSE;
596 int combineRight = RM_FALSE;
597 uint32_t findEnd;
598 uint32_t matchingEnd;
599 int32_t retVal;
601 if (opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) {
602 policyCheckType = Rm_policyCheck_INIT;
603 } else if (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE) {
604 policyCheckType = Rm_policyCheck_USE;
605 } else {
606 retVal = RM_ERROR_INVALID_SERVICE_TYPE;
607 return (retVal);
608 }
610 memset((void *)&findNode, 0, sizeof(findNode));
611 findNode.base = opInfo->resourceInfo->base;
612 findNode.length = opInfo->resourceInfo->length;
613 matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
614 &findNode);
616 /* Prepare privilege checks */
617 memset((void *)&checkCfg, 0, sizeof(checkCfg));
619 if (matchingNode) {
620 findEnd = findNode.base + findNode.length - 1;
621 matchingEnd = matchingNode->base + matchingNode->length - 1;
623 if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
624 if (opInfo->serviceInstNode == rmPolicyGetLinuxInstNode(rmHandle)) {
625 /* Bypass policy checks since Linux Kernel has full
626 * privileges */
627 allocPassesPolicy = RM_TRUE;
628 } else {
629 checkCfg.type = policyCheckType;
630 checkCfg.negCheck = RM_FALSE;
631 checkCfg.polTree = allocator->policyRoot;
632 checkCfg.validInstNode = opInfo->serviceInstNode;
633 checkCfg.resourceBase = findNode.base;
634 checkCfg.resourceLength = findNode.length;
635 allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
636 if (!allocPassesPolicy) {
637 if (policyCheckType == Rm_policyCheck_INIT) {
638 retVal = RM_SERVICE_DENIED_INIT_PERM_NOT_GIVEN;
639 } else {
640 retVal = RM_SERVICE_DENIED_USE_PERM_NOT_GIVEN;
641 }
642 }
644 if (!allocatorResNodeIsOwnedBy(rmHandle, matchingNode,
645 opInfo->serviceInstNode)) {
646 if (allocPassesPolicy &&
647 (matchingNode->allocationCount > 0)) {
648 if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode,
649 rmPolicyGetLinuxInstNode(rmHandle))) {
650 /* Check if instance requesting resource has
651 * privileges to share a resource already reserved
652 * by Linux */
653 checkCfg.type = Rm_policyCheck_SHARED_LINUX;
654 checkCfg.negCheck = RM_FALSE;
655 checkCfg.validInstNode = opInfo->serviceInstNode;
656 allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
657 if (!allocPassesPolicy) {
658 retVal = RM_SERVICE_DENIED_RES_NOT_SHARED_LINUX;
659 }
660 }
661 if (allocPassesPolicy) {
662 /* Check exclusive privileges of instance
663 * requesting resource. Requesting instance with
664 * exclusive privileges can't reserve resource if
665 * already owned*/
666 checkCfg.type = Rm_policyCheck_EXCLUSIVE;
667 checkCfg.negCheck = RM_TRUE;
668 checkCfg.validInstNode = opInfo->serviceInstNode;
669 allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
670 if (!allocPassesPolicy) {
671 retVal = RM_SERVICE_DENIED_EXCLUSIVE_RES_ALLOCD;
672 }
673 }
674 }
675 if (allocPassesPolicy &&
676 (matchingNode->allocationCount == 1)) {
677 /* Check exclusive privileges of instance that
678 * currently owns resource */
679 checkCfg.type = Rm_policyCheck_EXCLUSIVE;
680 checkCfg.negCheck = RM_TRUE;
681 checkCfg.validInstNode = matchingNode->ownerList->instNameNode;
682 allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
683 if (!allocPassesPolicy) {
684 retVal = RM_SERVICE_DENIED_ALLOCD_TO_EXCLUSIVE_INST;
685 }
686 }
687 }
688 }
690 if (allocPassesPolicy) {
691 /* Handle any possible node combinations if requesting instance
692 * is not already in resource's owner list. Automatic approval
693 * if requesting instance is already in owner list. */
694 if ((findNode.base == matchingNode->base) &&
695 (findEnd == matchingEnd)) {
696 /* findNode range matches matchingNode range
697 *
698 * |<--left node-->||<--matched node-->||<--right node-->|
699 * |<--alloc request-->|
700 */
701 leftNode = RB_PREV(_Rm_AllocatorResourceTree,
702 allocator->resourceRoot, matchingNode);
703 rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
704 allocator->resourceRoot, matchingNode);
705 RB_REMOVE(_Rm_AllocatorResourceTree,
706 allocator->resourceRoot, matchingNode);
707 allocatorResNodeOwnerAdd(rmHandle, matchingNode,
708 opInfo->serviceInstNode);
710 if (leftNode &&
711 allocatorResNodeOwnerCompare(rmHandle,
712 leftNode,
713 matchingNode) &&
714 allocatorResNodeBoundaryCompare(leftNode,
715 matchingNode)) {
716 RB_REMOVE(_Rm_AllocatorResourceTree,
717 allocator->resourceRoot, leftNode);
718 combineLeft = RM_TRUE;
719 }
720 if (rightNode &&
721 allocatorResNodeOwnerCompare(rmHandle,
722 rightNode,
723 matchingNode) &&
724 allocatorResNodeBoundaryCompare(rightNode,
725 matchingNode)) {
726 RB_REMOVE(_Rm_AllocatorResourceTree,
727 allocator->resourceRoot, rightNode);
728 combineRight = RM_TRUE;
729 }
731 if (combineLeft && combineRight) {
732 /* Combine all three nodes into matchingNode */
733 matchingNode->base = leftNode->base;
734 matchingNode->length = leftNode->length +
735 matchingNode->length +
736 rightNode->length;
738 allocatorResNodeOwnerClear(rmHandle, leftNode);
739 rmResourceNodeFree(leftNode);
740 allocatorResNodeOwnerClear(rmHandle, rightNode);
741 rmResourceNodeFree(rightNode);
742 } else if (combineLeft) {
743 /* Combine left and matching nodes. Reinsert right. */
744 matchingNode->base = leftNode->base;
745 matchingNode->length += leftNode->length;
747 allocatorResNodeOwnerClear(rmHandle, leftNode);
748 rmResourceNodeFree(leftNode);
749 if (rightNode) {
750 RB_INSERT(_Rm_AllocatorResourceTree,
751 allocator->resourceRoot, rightNode);
752 }
753 } else if (combineRight) {
754 /* Combine right and matching nodes. Reinsert left. */
755 matchingNode->length += rightNode->length;
757 allocatorResNodeOwnerClear(rmHandle, rightNode);
758 rmResourceNodeFree(rightNode);
759 if (leftNode) {
760 RB_INSERT(_Rm_AllocatorResourceTree,
761 allocator->resourceRoot, leftNode);
762 }
763 } else {
764 /* No combine. */
765 if (leftNode) {
766 RB_INSERT(_Rm_AllocatorResourceTree,
767 allocator->resourceRoot, leftNode);
768 }
769 if (rightNode) {
770 RB_INSERT(_Rm_AllocatorResourceTree,
771 allocator->resourceRoot, rightNode);
772 }
773 }
775 /* Always reinsert matchingNode */
776 RB_INSERT(_Rm_AllocatorResourceTree,
777 allocator->resourceRoot, matchingNode);
779 /* Matching node contains new reference count after alloc.
780 * Return new owner count and originating instance
781 * allocation reference count. */
782 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
783 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
784 matchingNode,
785 opInfo->serviceInstNode);
786 } else if ((findNode.base > matchingNode->base) &&
787 (findEnd < matchingEnd)) {
788 /* findNode range is subset of matchingNode range and
789 * neither boundary is equivalent.
790 *
791 * |<----------matched node---------->|
792 * |<---alloc request--->|
793 */
794 RB_REMOVE(_Rm_AllocatorResourceTree,
795 allocator->resourceRoot, matchingNode);
796 leftNode = rmResourceNodeNew(matchingNode->base,
797 findNode.base -
798 matchingNode->base);
799 allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
800 rightNode = rmResourceNodeNew(findNode.base +
801 findNode.length,
802 matchingEnd - findEnd);
803 allocatorResNodeOwnerCopy(rmHandle, rightNode,
804 matchingNode);
806 matchingNode->base = findNode.base;
807 matchingNode->length = findNode.length;
808 allocatorResNodeOwnerAdd(rmHandle, matchingNode,
809 opInfo->serviceInstNode);
811 /* Insert all the nodes */
812 RB_INSERT(_Rm_AllocatorResourceTree,
813 allocator->resourceRoot, matchingNode);
814 RB_INSERT(_Rm_AllocatorResourceTree,
815 allocator->resourceRoot, leftNode);
816 RB_INSERT(_Rm_AllocatorResourceTree,
817 allocator->resourceRoot, rightNode);
819 /* Matching node contains new reference count after alloc.
820 * Return new owner count and originating instance
821 * allocation reference count. */
822 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
823 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
824 matchingNode,
825 opInfo->serviceInstNode);
826 } else {
827 if (findNode.base == matchingNode->base) {
828 /* findNode base and matchingNode base are equivalent.
829 * May be combine possibilities to the left
830 *
831 * |<-left node (alloc'd)->||<-----matched node------->|
832 * |<-findNode (alloc req)->|
833 */
834 leftNode = RB_PREV(_Rm_AllocatorResourceTree,
835 allocator->resourceRoot,
836 matchingNode);
837 RB_REMOVE(_Rm_AllocatorResourceTree,
838 allocator->resourceRoot, matchingNode);
839 /* Add allocating instance to owner list for compare
840 * with leftNode */
841 allocatorResNodeOwnerAdd(rmHandle, matchingNode,
842 opInfo->serviceInstNode);
844 if (leftNode &&
845 allocatorResNodeOwnerCompare(rmHandle,
846 leftNode,
847 matchingNode) &&
848 allocatorResNodeBoundaryCompare(leftNode,
849 matchingNode)) {
850 RB_REMOVE(_Rm_AllocatorResourceTree,
851 allocator->resourceRoot, leftNode);
852 /* Combine leftNode and findNode */
853 leftNode->length += findNode.length;
854 } else {
855 leftNode = rmResourceNodeNew(findNode.base,
856 findNode.length);
857 allocatorResNodeOwnerCopy(rmHandle, leftNode,
858 matchingNode);
859 }
861 /* Account for leftNode in matchingNode */
862 matchingNode->base = findNode.base + findNode.length;
863 matchingNode->length = matchingEnd - findEnd;
865 RB_INSERT(_Rm_AllocatorResourceTree,
866 allocator->resourceRoot, leftNode);
867 /* Left node contains new reference count after alloc.
868 * Return new owner count and originating instance
869 * allocation reference count. */
870 opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
871 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
872 leftNode,
873 opInfo->serviceInstNode);
874 } else /* (findEnd == matchingEnd) */ {
875 /* findNode end and matchingNode end are equivalent.
876 * May be combine possibilities to the right
877 *
878 * |<------matched node----->||<-right node (alloc'd)->|
879 * |<-findNode (alloc req)->|
880 */
881 rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
882 allocator->resourceRoot,
883 matchingNode);
884 RB_REMOVE(_Rm_AllocatorResourceTree,
885 allocator->resourceRoot, matchingNode);
886 /* Add allocating instance to owner list for compare
887 * with rightNode */
888 allocatorResNodeOwnerAdd(rmHandle, matchingNode,
889 opInfo->serviceInstNode);
891 if (rightNode &&
892 allocatorResNodeOwnerCompare(rmHandle,
893 rightNode,
894 matchingNode) &&
895 allocatorResNodeBoundaryCompare(rightNode,
896 matchingNode)) {
897 RB_REMOVE(_Rm_AllocatorResourceTree,
898 allocator->resourceRoot, rightNode);
899 /* Combine rightNode and findNode */
900 rightNode->base = findNode.base;
901 rightNode->length += findNode.length;
902 } else {
903 rightNode = rmResourceNodeNew(findNode.base,
904 findNode.length);
905 allocatorResNodeOwnerCopy(rmHandle, rightNode,
906 matchingNode);
907 }
909 /* Account for rightNode in matchingNode */
910 matchingNode->length -= findNode.length;
912 RB_INSERT(_Rm_AllocatorResourceTree,
913 allocator->resourceRoot, rightNode);
914 /* Right node contains new reference count after alloc.
915 * Return new owner count and originating instance
916 * allocation reference count. */
917 opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
918 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
919 rightNode,
920 opInfo->serviceInstNode);
921 }
922 /* Remove allocating instance from leftover matchingNode */
923 allocatorResNodeOwnerDelete(rmHandle, matchingNode,
924 opInfo->serviceInstNode);
925 RB_INSERT(_Rm_AllocatorResourceTree,
926 allocator->resourceRoot, matchingNode);
927 }
928 retVal = RM_SERVICE_APPROVED;
929 }
930 } else {
931 retVal = RM_SERVICE_DENIED_PARTIAL_ALLOCATION;
932 }
933 } else {
934 retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
935 }
937 return(retVal);
938 }
940 /* FUNCTION PURPOSE: Frees an allocator resource
941 ***********************************************************************
942 * DESCRIPTION: Will attempt to free the resource with specified
943 * base and length from the resource's allocator. The
944 * free algorithm will verify the free request parameters
945 * match an allocated range for the resource and that the
946 * range is owned by the instance requesting the free. If
947 * the free is validated the algorithm will free the
948 * resource then combine any resource nodes that may have
949 * become equivalent (in terms of ownership) after the
950 * allocation.
951 */
952 static int32_t allocatorFree(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
953 Rm_AllocatorOpInfo *opInfo)
954 {
955 Rm_ResourceNode findNode;
956 Rm_ResourceNode *matchingNode = NULL;
957 Rm_ResourceNode *leftNode = NULL;
958 Rm_ResourceNode *rightNode = NULL;
959 int combineLeft = RM_FALSE;
960 int combineRight = RM_FALSE;
961 uint32_t findEnd;
962 uint32_t matchingEnd;
963 int32_t retVal;
965 memset((void *)&findNode, 0, sizeof(findNode));
966 findNode.base = opInfo->resourceInfo->base;
967 findNode.length = opInfo->resourceInfo->length;
968 matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
969 &findNode);
971 if (matchingNode) {
972 findEnd = findNode.base + findNode.length - 1;
973 matchingEnd = matchingNode->base + matchingNode->length - 1;
975 if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
976 if (matchingNode->allocationCount) {
977 if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode,
978 opInfo->serviceInstNode)) {
979 if ((findNode.base == matchingNode->base) &&
980 (findEnd == matchingEnd)) {
981 /* Case 1: Free range equals allocated matched node
982 * exactly. Attempt to combine freed node with
983 * nodes to left and right.
984 *
985 * |<-left node->||<---matched node--->||<-right node->|
986 * |<---free request--->|
987 */
988 leftNode = RB_PREV(_Rm_AllocatorResourceTree,
989 allocator->resourceRoot,
990 matchingNode);
991 rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
992 allocator->resourceRoot,
993 matchingNode);
994 RB_REMOVE(_Rm_AllocatorResourceTree,
995 allocator->resourceRoot, matchingNode);
996 allocatorResNodeOwnerDelete(rmHandle, matchingNode,
997 opInfo->serviceInstNode);
999 if (leftNode &&
1000 allocatorResNodeOwnerCompare(rmHandle,
1001 leftNode,
1002 matchingNode) &&
1003 allocatorResNodeBoundaryCompare(leftNode,
1004 matchingNode)) {
1005 RB_REMOVE(_Rm_AllocatorResourceTree,
1006 allocator->resourceRoot, leftNode);
1007 combineLeft = RM_TRUE;
1008 }
1009 if (rightNode &&
1010 allocatorResNodeOwnerCompare(rmHandle,
1011 rightNode,
1012 matchingNode) &&
1013 allocatorResNodeBoundaryCompare(rightNode,
1014 matchingNode)) {
1015 RB_REMOVE(_Rm_AllocatorResourceTree,
1016 allocator->resourceRoot, rightNode);
1017 combineRight = RM_TRUE;
1018 }
1020 if (combineLeft && combineRight) {
1021 /* Combine all three nodes into matchingNode */
1022 matchingNode->base = leftNode->base;
1023 matchingNode->length = leftNode->length +
1024 matchingNode->length +
1025 rightNode->length;
1027 allocatorResNodeOwnerClear(rmHandle, leftNode);
1028 rmResourceNodeFree(leftNode);
1029 allocatorResNodeOwnerClear(rmHandle, rightNode);
1030 rmResourceNodeFree(rightNode);
1031 } else if (combineLeft) {
1032 /* Combine left and matching nodes.
1033 * Reinsert right. */
1034 matchingNode->base = leftNode->base;
1035 matchingNode->length += leftNode->length;
1037 allocatorResNodeOwnerClear(rmHandle, leftNode);
1038 rmResourceNodeFree(leftNode);
1039 if (rightNode) {
1040 RB_INSERT(_Rm_AllocatorResourceTree,
1041 allocator->resourceRoot, rightNode);
1042 }
1043 } else if (combineRight) {
1044 /* Combine right and matching nodes.
1045 * Reinsert left. */
1046 matchingNode->length += rightNode->length;
1048 allocatorResNodeOwnerClear(rmHandle, rightNode);
1049 rmResourceNodeFree(rightNode);
1050 if (leftNode) {
1051 RB_INSERT(_Rm_AllocatorResourceTree,
1052 allocator->resourceRoot, leftNode);
1053 }
1054 } else {
1055 /* No combine. */
1056 if (leftNode) {
1057 RB_INSERT(_Rm_AllocatorResourceTree,
1058 allocator->resourceRoot, leftNode);
1059 }
1060 if (rightNode) {
1061 RB_INSERT(_Rm_AllocatorResourceTree,
1062 allocator->resourceRoot, rightNode);
1063 }
1064 }
1066 /* Always reinsert matchingNode */
1067 RB_INSERT(_Rm_AllocatorResourceTree,
1068 allocator->resourceRoot, matchingNode);
1070 /* Matching node is what remains after free. Return
1071 * remaining owner count and originating instance
1072 * allocation reference count. */
1073 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1074 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1075 matchingNode,
1076 opInfo->serviceInstNode);
1077 } else if ((findNode.base > matchingNode->base) &&
1078 (findEnd < matchingEnd)) {
1079 /* Case 2: Free range is less than range in matched
1080 * node. Split matched node into three nodes.
1081 *
1082 * |<----------matched node---------->|
1083 * |<---free request--->|
1084 *
1085 * Remove instance from owner list then add it back in
1086 * for side nodes for proper accounting of allocations
1087 * in validInstance list
1088 */
1089 RB_REMOVE(_Rm_AllocatorResourceTree,
1090 allocator->resourceRoot, matchingNode);
1091 allocatorResNodeOwnerDelete(rmHandle, matchingNode,
1092 opInfo->serviceInstNode);
1094 leftNode = rmResourceNodeNew(matchingNode->base,
1095 findNode.base -
1096 matchingNode->base);
1097 allocatorResNodeOwnerCopy(rmHandle, leftNode,
1098 matchingNode);
1099 allocatorResNodeOwnerAdd(rmHandle, leftNode,
1100 opInfo->serviceInstNode);
1101 RB_INSERT(_Rm_AllocatorResourceTree,
1102 allocator->resourceRoot, leftNode);
1104 rightNode = rmResourceNodeNew(findNode.base +
1105 findNode.length,
1106 matchingEnd - findEnd);
1107 allocatorResNodeOwnerCopy(rmHandle, rightNode,
1108 matchingNode);
1109 allocatorResNodeOwnerAdd(rmHandle, rightNode,
1110 opInfo->serviceInstNode);
1111 RB_INSERT(_Rm_AllocatorResourceTree,
1112 allocator->resourceRoot, rightNode);
1114 matchingNode->base = findNode.base;
1115 matchingNode->length = findNode.length;
1116 RB_INSERT(_Rm_AllocatorResourceTree,
1117 allocator->resourceRoot, matchingNode);
1119 /* Matching node is what remains after free. Return
1120 * remaining owner count and originating instance
1121 * allocation reference count. */
1122 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1123 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1124 matchingNode,
1125 opInfo->serviceInstNode);
1126 } else {
1127 if (findNode.base == matchingNode->base) {
1128 /* Case 3: Free range is on left boundary of
1129 * matched node. Try to combine free range
1130 * with left node.
1131 *
1132 * |<-left node (free)->||<-----matched node------>|
1133 * |<-findNode (free req)->|
1134 */
1136 leftNode = RB_PREV(_Rm_AllocatorResourceTree,
1137 allocator->resourceRoot,
1138 matchingNode);
1139 RB_REMOVE(_Rm_AllocatorResourceTree,
1140 allocator->resourceRoot, matchingNode);
1141 /* Remove freeing instance from owner list for
1142 * compare with leftNode */
1143 allocatorResNodeOwnerDelete(rmHandle, matchingNode,
1144 opInfo->serviceInstNode);
1146 if (leftNode &&
1147 allocatorResNodeOwnerCompare(rmHandle,
1148 leftNode,
1149 matchingNode) &&
1150 allocatorResNodeBoundaryCompare(leftNode,
1151 matchingNode)) {
1152 RB_REMOVE(_Rm_AllocatorResourceTree,
1153 allocator->resourceRoot, leftNode);
1154 /* Combine leftNode and findNode */
1155 leftNode->length += findNode.length;
1156 } else {
1157 leftNode = rmResourceNodeNew(findNode.base,
1158 findNode.length);
1159 allocatorResNodeOwnerCopy(rmHandle, leftNode,
1160 matchingNode);
1161 }
1163 /* Remove leftNode range from matchingNode */
1164 matchingNode->base = findNode.base +
1165 findNode.length;
1166 matchingNode->length = matchingEnd - findEnd;
1167 RB_INSERT(_Rm_AllocatorResourceTree,
1168 allocator->resourceRoot, leftNode);
1170 /* Left node is what remains after free. Return
1171 * remaining owner count and originating instance
1172 * allocation reference count. */
1173 opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
1174 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1175 leftNode,
1176 opInfo->serviceInstNode);
1177 } else /* (findEnd == matchingEnd) */ {
1178 /* Case 4: Free range is on right boundary of
1179 * matched node. Try to combine free range
1180 * with right node.
1181 *
1182 * |<-----matched node----->||<-right node (free)->|
1183 * |<-findNode (free req)->|
1184 */
1186 rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
1187 allocator->resourceRoot,
1188 matchingNode);
1189 RB_REMOVE(_Rm_AllocatorResourceTree,
1190 allocator->resourceRoot, matchingNode);
1191 /* Remove freeing instance from owner list for
1192 * compare with rightNode */
1193 allocatorResNodeOwnerDelete(rmHandle, matchingNode,
1194 opInfo->serviceInstNode);
1196 if (rightNode &&
1197 allocatorResNodeOwnerCompare(rmHandle,
1198 rightNode,
1199 matchingNode) &&
1200 allocatorResNodeBoundaryCompare(rightNode,
1201 matchingNode)) {
1202 RB_REMOVE(_Rm_AllocatorResourceTree,
1203 allocator->resourceRoot, rightNode);
1204 /* Combine rightNode and findNode */
1205 rightNode->base = findNode.base;
1206 rightNode->length += findNode.length;
1207 } else {
1208 rightNode = rmResourceNodeNew(findNode.base,
1209 findNode.length);
1210 allocatorResNodeOwnerCopy(rmHandle, rightNode,
1211 matchingNode);
1212 }
1214 /* Remove rightNode range from matchingNode */
1215 matchingNode->length -= findNode.length;
1216 RB_INSERT(_Rm_AllocatorResourceTree,
1217 allocator->resourceRoot, rightNode);
1219 /* Right node is what remains after free. Return
1220 * remaining owner count and originating instance
1221 * allocation reference count. */
1222 opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
1223 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1224 rightNode,
1225 opInfo->serviceInstNode);
1226 }
1228 /* Add freeing instance back into matchingNode
1229 * allocations */
1230 allocatorResNodeOwnerAdd(rmHandle, matchingNode,
1231 opInfo->serviceInstNode);
1232 RB_INSERT(_Rm_AllocatorResourceTree,
1233 allocator->resourceRoot, matchingNode);
1234 }
1235 retVal = RM_SERVICE_APPROVED;
1236 } else {
1237 /* Return owner count and instance alloc count. In case
1238 * it's a reference count check in application */
1239 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1240 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1241 matchingNode,
1242 opInfo->serviceInstNode);
1243 retVal = RM_SERVICE_DENIED_RES_NOT_ALLOCD_TO_INST;
1244 }
1245 } else {
1246 /* Return owner count and instance alloc count. In case it's
1247 * a reference count check in application */
1248 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1249 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1250 matchingNode,
1251 opInfo->serviceInstNode);
1252 retVal = RM_SERVICE_DENIED_RES_ALREADY_FREE;
1253 }
1254 } else {
1255 retVal = RM_SERVICE_DENIED_PARTIAL_FREE;
1256 }
1257 } else {
1258 retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
1259 }
1260 return(retVal);
1261 }
1263 /* FUNCTION PURPOSE: Reserves a Linux resource
1264 ***********************************************************************
1265 * DESCRIPTION: Reserves resources for Linux using the base and length
1266 * values retrieved from the Linux DTB via the
1267 * "linux-dtb-alias" properties within the GRL.
1268 */
1269 static int32_t allocatorReserveLinuxResource(Rm_Handle rmHandle,
1270 Rm_LinuxAlias *linuxAlias,
1271 Rm_LinuxValueRange *linuxValues,
1272 Rm_AllocatorOpInfo *opInfo)
1273 {
1274 int32_t retVal = RM_OK;
1275 int baseFound = RM_FALSE;
1276 int lengthFound = RM_FALSE;
1277 uint32_t valueIndex = 0;
1279 while ((linuxValues) && (!baseFound || !lengthFound)) {
1280 if (linuxAlias->baseOffset == valueIndex) {
1281 opInfo->resourceInfo->base = linuxValues->value;
1282 baseFound = RM_TRUE;
1284 if (linuxAlias->lengthOffset ==
1285 RM_DTB_UTIL_LINUX_ALIAS_OFFSET_NOT_SET) {
1286 opInfo->resourceInfo->length = 1;
1287 lengthFound = RM_TRUE;
1288 }
1289 } else if (linuxAlias->lengthOffset == valueIndex) {
1290 opInfo->resourceInfo->length = linuxValues->value;
1291 lengthFound = RM_TRUE;
1292 }
1293 /* else: value was not a base or length so skip to next alias value */
1295 linuxValues = (Rm_LinuxValueRange *)linuxValues->nextValue;
1296 valueIndex++;
1297 }
1299 if (!baseFound || !lengthFound) {
1300 retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1301 } else {
1302 /* Allocate resource to Linux */
1303 retVal = rmAllocatorOperation(rmHandle, opInfo);
1304 if (retVal == RM_SERVICE_APPROVED) {
1305 retVal = RM_OK;
1306 }
1307 }
1308 return(retVal);
1309 }
1311 /* FUNCTION PURPOSE: Finds and reserves Linux resources
1312 ***********************************************************************
1313 * DESCRIPTION: Parses the Linux DTB for resources consumed by the
1314 * Linux kernel. If the resource is found via the
1315 * "linux-dtb-alias" property defined in the GRL it is
1316 * reserved.
1317 */
1318 static int32_t allocatorFindLinuxResource(Rm_Handle rmHandle,
1319 const char *resourceName,
1320 void *linuxDtb,
1321 Rm_LinuxAlias *linuxAlias)
1322 {
1323 Rm_AllocatorOpInfo opInfo;
1324 Rm_ResourceInfo resourceInfo;
1325 uint32_t pathOffset;
1326 uint32_t pathSize;
1327 char *tempAliasPath;
1328 char *spacePtr;
1329 int32_t propOffset;
1330 int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1331 int32_t prevDepth = RM_DTB_UTIL_STARTING_DEPTH;
1332 int32_t depth = RM_DTB_UTIL_STARTING_DEPTH;
1333 int32_t propertyLen;
1334 const char *propertyName;
1335 const void *propertyData;
1336 Rm_LinuxValueRange *linValRange;
1337 int32_t retVal = RM_OK;
1339 memset((void *)&opInfo, 0, sizeof(opInfo));
1340 memset((void *)&resourceInfo, 0, sizeof(resourceInfo));
1342 rm_strncpy(resourceInfo.name, resourceName, RM_NAME_MAX_CHARS);
1343 opInfo.serviceInstNode = rmPolicyGetLinuxInstNode(rmHandle);
1344 opInfo.operation = Rm_allocatorOp_ALLOCATE_INIT;
1345 opInfo.resourceInfo = &resourceInfo;
1347 if (!opInfo.serviceInstNode) {
1348 retVal = RM_SERVICE_DENIED_INST_NAME_NOT_VALID;
1349 goto errorExit;
1350 }
1352 while(linuxAlias) {
1353 /* Reset parsing variables */
1354 pathOffset = 0;
1355 pathSize = strlen(linuxAlias->path) + 1;
1356 tempAliasPath = Rm_osalMalloc(pathSize);
1357 rm_strncpy(tempAliasPath, linuxAlias->path, pathSize);
1358 nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1359 prevDepth = RM_DTB_UTIL_STARTING_DEPTH;
1360 resourceInfo.base = 0;
1361 resourceInfo.length = 0;
1363 spacePtr = strpbrk(tempAliasPath, " ");
1364 if (spacePtr) {
1365 *spacePtr = '\0';
1366 }
1368 while(pathOffset < pathSize) {
1369 /* Move through DTB nodes until next alias path node found */
1370 if (strcmp(tempAliasPath + pathOffset,
1371 fdt_get_name(linuxDtb, nodeOffset, NULL))) {
1372 nodeOffset = fdt_next_node(linuxDtb, nodeOffset, &depth);
1374 if ((depth < prevDepth) || (nodeOffset == -FDT_ERR_NOTFOUND)) {
1375 /* Returning from subnode that matched part of alias path
1376 * without finding resource values */
1377 retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1378 break;
1379 }
1380 } else {
1381 /* Found next alias path node. Move to next node name in path
1382 * string. */
1383 pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1384 spacePtr = strpbrk(tempAliasPath + pathOffset, " ");
1385 if (spacePtr) {
1386 *spacePtr = '\0';
1387 }
1389 prevDepth = fdt_node_depth(linuxDtb, nodeOffset);
1390 propOffset = fdt_first_property_offset(linuxDtb, nodeOffset);
1391 while ((propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1392 (pathOffset < pathSize)) {
1393 propertyData = fdt_getprop_by_offset(linuxDtb, propOffset,
1394 &propertyName,
1395 &propertyLen);
1397 if (strcmp(tempAliasPath + pathOffset, propertyName) == 0) {
1398 /* Found resource at end of alias path */
1399 pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1400 linValRange = rmDtbUtilLinuxExtractValues(propertyData,
1401 propertyLen);
1402 retVal = allocatorReserveLinuxResource(rmHandle,
1403 linuxAlias,
1404 linValRange,
1405 &opInfo);
1406 rmDtbUtilLinuxFreeValues(linValRange);
1407 }
1408 propOffset = fdt_next_property_offset(linuxDtb, propOffset);
1409 }
1411 if (propOffset < -FDT_ERR_NOTFOUND) {
1412 retVal = propOffset;
1413 break;
1414 }
1415 }
1416 }
1418 Rm_osalFree(tempAliasPath, pathSize);
1419 if (retVal < RM_OK) {
1420 break;
1421 }
1422 linuxAlias = linuxAlias->nextLinuxAlias;
1423 }
1424 errorExit:
1425 return(retVal);
1426 }
1428 /* FUNCTION PURPOSE: Populates an allocator's resource tree
1429 ***********************************************************************
1430 * DESCRIPTION: Uses resource range information pulled from GRL to
1431 * populate an allocator's resource tree
1432 */
1433 static int32_t allocatorPopulateResTree(Rm_ResourceTree *resTree,
1434 Rm_ResourceRange *range)
1435 {
1436 Rm_ResourceNode *resNode = NULL;
1437 int32_t retVal = RM_OK;
1439 while (range != NULL) {
1440 if ((resNode = rmResourceNodeNew(range->base, range->length))) {
1441 RB_INSERT(_Rm_AllocatorResourceTree, resTree,
1442 resNode);
1443 } else {
1444 retVal = RM_ERROR_MALLOC_FAILED_RES_NODE;
1445 break;
1446 }
1447 range = range->nextRange;
1448 }
1450 return(retVal);
1451 }
1453 /* FUNCTION PURPOSE: Initializes a new allocator
1454 ***********************************************************************
1455 * DESCRIPTION: allocates and initializes a new allocator for the
1456 * provided resource name. The resource and policy tree
1457 * root nodes are allocated and initialized as part of
1458 * the allocator node initialization.
1459 */
1460 static Rm_AllocatorNode *allocatorInitNode(Rm_Inst *rmInst,
1461 const char *resourceName,
1462 int32_t *retVal)
1463 {
1464 Rm_AllocatorTree *allocTree = rmInst->allocatorTree;
1465 Rm_AllocatorNode *newAllocNode = NULL;
1466 Rm_ResourceTree *resTree = NULL;
1467 Rm_PolicyTree *polTree = NULL;
1469 *retVal = RM_OK;
1471 if ((strlen(resourceName) + 1) > RM_NAME_MAX_CHARS) {
1472 *retVal = RM_ERROR_RESOURCE_NAME_TOO_LONG;
1473 goto errorExit;
1474 }
1476 newAllocNode = rmAllocatorNodeNew(resourceName);
1477 if (newAllocNode) {
1478 if (RB_INSERT(_Rm_AllocatorTree, allocTree, newAllocNode)) {
1479 /* Collision */
1480 *retVal = RM_ERROR_RES_SPECIFIED_MORE_THAN_ONCE;
1481 goto errorExit;
1482 }
1484 if ((resTree = Rm_osalMalloc(sizeof(*resTree)))) {
1485 RB_INIT(resTree);
1486 newAllocNode->resourceRoot = resTree;
1487 } else {
1488 *retVal = RM_ERROR_MALLOC_FAILED_RES_TREE;
1489 goto errorExit;
1490 }
1492 if ((polTree = Rm_osalMalloc(sizeof(*polTree)))) {
1493 RB_INIT(polTree);
1494 newAllocNode->policyRoot = polTree;
1495 } else {
1496 *retVal = RM_ERROR_MALLOC_FAILED_POL_TREE;
1497 goto errorExit;
1498 }
1499 } else {
1500 *retVal = RM_ERROR_COULD_NOT_CREATE_NEW_ALLOCATOR;
1501 goto errorExit;
1502 }
1504 errorExit:
1505 if ((*retVal != RM_OK) && newAllocNode) {
1506 rmAllocatorNodeFree(newAllocNode);
1507 }
1508 return(newAllocNode);
1509 }
1511 /* FUNCTION PURPOSE: Creates and initializes an allocator node
1512 ***********************************************************************
1513 * DESCRIPTION: Creates an allocator for the provided resource name.
1514 * The resource properties retrieved from the GRL are used
1515 * to create a resource tree. Resources will be reserved
1516 * for the Linux kernel if the Linux DTB is provided and
1517 * there are "linux-dtb-alias" properties specified in
1518 * the GRL. A policy tree will be created using the
1519 * resource's entry in the policy.
1520 */
1521 static int32_t allocatorCreateNode(Rm_Inst *rmInst, void *policyDtb,
1522 void *linuxDtb, const char *resourceName,
1523 Rm_ResourceProperties *resProps)
1524 {
1525 Rm_AllocatorNode *allocNode = NULL;
1526 Rm_ResourceRange *range = NULL;
1527 Rm_LinuxAlias *linuxAlias = NULL;
1528 int32_t retVal = RM_OK;
1530 allocNode = allocatorInitNode(rmInst, resourceName, &retVal);
1531 if (allocNode) {
1532 range = rmDtbUtilResExtractRange(resProps->rangeData,
1533 resProps->rangeLen);
1534 retVal = allocatorPopulateResTree(allocNode->resourceRoot, range);
1535 if (retVal != RM_OK) {
1536 goto errorExit;
1537 }
1538 /* Create the companion policy tree for the resource */
1539 retVal = rmPolicyPopulateTree((Rm_Handle)rmInst, allocNode->policyRoot,
1540 policyDtb, resourceName);
1541 if (retVal != RM_OK) {
1542 goto errorExit;
1543 }
1545 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1546 /* Writeback resource tree for Linux resource reservation which
1547 * uses path through rmAllocatorOperation function. This function
1548 * performs an invalidate of resource tree */
1549 rmResourceTreeWb(allocNode->resourceRoot);
1550 }
1552 if (resProps->linuxAliasData && linuxDtb) {
1553 linuxAlias = rmDtbUtilResExtractLinuxAlias(resProps->linuxAliasData,
1554 resProps->linuxAliasLen,
1555 &retVal);
1556 /* linuxAlias will be NULL if retVal contains error code */
1557 if (linuxAlias) {
1558 retVal = allocatorFindLinuxResource(rmInst, resourceName,
1559 linuxDtb, linuxAlias);
1560 }
1562 if (retVal != RM_OK) {
1563 goto errorExit;
1564 }
1565 }
1567 errorExit:
1568 if (range) {
1569 rmDtbUtilResFreeRange(range);
1570 }
1571 if (linuxAlias) {
1572 rmDtbUtilResFreeLinuxAlias(linuxAlias);
1573 }
1574 }
1575 return(retVal);
1576 }
1578 /* FUNCTION PURPOSE: Creates NameServer assignment entries
1579 ***********************************************************************
1580 * DESCRIPTION: Creates a NameServer entry for each NameServer assignment
1581 * found in a GRL's resource node
1582 */
1583 static int32_t allocatorNsAdd(Rm_Inst *rmInst, const char *resourceName,
1584 Rm_ResourceProperties *resProps)
1585 {
1586 Rm_NsAssignment *nsAssigns = NULL;
1587 Rm_NsAssignment *nsAssignsBase = NULL;
1588 Rm_NameServerObjCfg nsCfg;
1589 int32_t retVal = RM_OK;
1591 if (resProps->nsAssignData) {
1592 nsAssigns = rmDtbUtilResExtractNsAssignment(resProps->nsAssignData,
1593 resProps->nsAssignLen,
1594 &retVal);
1595 /* nsAssignments will be NULL if retVal contains error code */
1596 if (nsAssigns) {
1597 nsAssignsBase = nsAssigns;
1598 while (nsAssigns) {
1599 memset((void *)&nsCfg, 0, sizeof(nsCfg));
1600 nsCfg.nameServerTree = rmInst->u.server.nameServer;
1601 nsCfg.nodeCfg.objName = nsAssigns->nsName;
1602 nsCfg.nodeCfg.resourceName = (char *)resourceName;
1603 nsCfg.nodeCfg.resourceBase= nsAssigns->resourceBase;
1604 nsCfg.nodeCfg.resourceLength = nsAssigns->resourceLength;
1605 rmNameServerAddObject(&nsCfg);
1606 nsAssigns = nsAssigns->nextNsAssignment;
1607 }
1608 rmDtbUtilResFreeNsAssignmentList(nsAssignsBase);
1609 }
1610 }
1612 return(retVal);
1613 }
1616 /* FUNCTION PURPOSE: Populate the allocator tree based on the GRL
1617 ***********************************************************************
1618 * DESCRIPTION: Populates the allocator tree using the GRL and policy DTBs.
1619 * Optionally, the Linux DTB will be scanned for resources used
1620 * by the Kernel if the Linux DTB is non-NULL.
1621 */
1622 static int32_t allocatorPopulateGrlBased(Rm_Inst *rmInst, void *grlDtb,
1623 void *policyDtb, void *linuxDtb)
1624 {
1625 int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1626 int32_t nodeDepth = RM_DTB_UTIL_STARTING_DEPTH;
1627 Rm_ResourceProperties resProps;
1628 int32_t propOffset;
1629 int32_t propertyLen;
1630 const char *propertyName;
1631 const void *propertyData;
1632 Rm_ResourcePropType propertyType;
1633 int32_t retVal = RM_OK;
1635 /* Create allocator tree node with resource and policy trees for
1636 * each resource found in the GRL. */
1637 while ((nodeOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1638 (nodeDepth >= RM_DTB_UTIL_STARTING_DEPTH)) {
1640 memset((void *)&resProps, 0, sizeof(resProps));
1641 /* Get properties of resource node */
1642 propOffset = fdt_first_property_offset(grlDtb, nodeOffset);
1644 while (propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) {
1645 propertyData = fdt_getprop_by_offset(grlDtb, propOffset,
1646 &propertyName, &propertyLen);
1647 propertyType = rmDtbUtilResGetPropertyType(propertyName);
1648 switch(propertyType) {
1649 case Rm_resourcePropType_RESOURCE_RANGE:
1650 resProps.rangeData = propertyData;
1651 resProps.rangeLen = propertyLen;
1652 break;
1653 case Rm_resourcePropType_NSASSIGNMENT:
1654 resProps.nsAssignData = propertyData;
1655 resProps.nsAssignLen = propertyLen;
1656 break;
1657 case Rm_resourcePropType_RESOURCE_LINUX_ALIAS:
1658 resProps.linuxAliasData = propertyData;
1659 resProps.linuxAliasLen = propertyLen;
1660 break;
1661 default:
1662 retVal = RM_ERROR_GRL_UNKNOWN_RESOURCE_PROPERTY;
1663 goto errorExit;
1664 }
1666 propOffset = fdt_next_property_offset(grlDtb, propOffset);
1667 if (propOffset == -FDT_ERR_NOTFOUND) {
1668 const char *resName = fdt_get_name(grlDtb, nodeOffset,
1669 NULL);
1671 if ((!resProps.rangeData) && (!resProps.nsAssignData)) {
1672 retVal = RM_ERROR_GRL_INVALID_NODE_DEF;
1673 goto errorExit;
1674 }
1676 if (resProps.rangeData) {
1677 /* At least range property found. Create allocator node
1678 * using extracted values for resource tree and
1679 * resource's policy entry for policy tree */
1680 retVal = allocatorCreateNode(rmInst, policyDtb, linuxDtb,
1681 resName, &resProps);
1682 if (retVal != RM_OK) {
1683 goto errorExit;
1684 }
1685 }
1687 if (resProps.nsAssignData) {
1688 retVal = allocatorNsAdd(rmInst, resName, &resProps);
1689 if (retVal != RM_OK) {
1690 goto errorExit;
1691 }
1692 }
1693 } else if (propOffset < -FDT_ERR_NOTFOUND) {
1694 /* Error returned by LIBFDT */
1695 retVal = propOffset;
1696 goto errorExit;
1697 }
1698 /* else: fall through to get next property */
1699 }
1700 if (propOffset < -FDT_ERR_NOTFOUND) {
1701 /* Error returned by LIBFDT */
1702 retVal = propOffset;
1703 goto errorExit;
1704 }
1706 nodeOffset = fdt_next_node(grlDtb, nodeOffset, &nodeDepth);
1707 if (nodeOffset < -FDT_ERR_NOTFOUND) {
1708 /* Error returned by LIBFDT */
1709 retVal = nodeOffset;
1710 goto errorExit;
1711 }
1712 }
1714 errorExit:
1715 return(retVal);
1716 }
1718 /* FUNCTION PURPOSE: Populate the allocator tree based on the Policy DTB
1719 ***********************************************************************
1720 * DESCRIPTION: Populates the allocator tree using the policy DTB. The
1721 * resource trees in each allocator will be created on the fly
1722 * as a CD requests resources from the server. Client instances
1723 * will never create resource trees since they'll only use the
1724 * allocator's policy trees for the static initialization phase.
1725 */
1726 static int32_t allocatorPopulatePolicyBased(Rm_Inst *rmInst, void *policyDtb)
1727 {
1728 int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1729 int32_t nodeDepth = RM_DTB_UTIL_STARTING_DEPTH;
1730 int32_t propOffset;
1731 const char *resName;
1732 const char *propName;
1733 Rm_PolicyPropType propType;
1734 Rm_AllocatorNode *newAllocNode = NULL;
1735 int32_t retVal = RM_OK;
1737 /* Search for resource node definitions in the policy */
1738 while ((nodeOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1739 (nodeDepth >= RM_DTB_UTIL_STARTING_DEPTH)) {
1741 propOffset = fdt_first_property_offset(policyDtb, nodeOffset);
1742 while (propOffset > RM_DTB_UTIL_STARTING_NODE_OFFSET) {
1743 fdt_getprop_by_offset(policyDtb, propOffset, &propName, NULL);
1744 propType = rmDtbUtilPolicyGetPropertyType(propName);
1745 if (propType == Rm_policyPropType_ASSIGNMENTS) {
1746 /* Found a resource node's assignment property. Create an
1747 * allocator node for the resource and populate it with a
1748 * policy tree */
1749 resName = fdt_get_name(policyDtb, nodeOffset, NULL);
1751 newAllocNode = allocatorInitNode(rmInst, resName, &retVal);
1752 if (newAllocNode) {
1753 retVal = rmPolicyPopulateTree((Rm_Handle)rmInst,
1754 newAllocNode->policyRoot,
1755 policyDtb, resName);
1756 if (retVal != RM_OK) {
1757 goto errorExit;
1758 }
1759 } else {
1760 goto errorExit;
1761 }
1763 /* Move on to next resource node */
1764 break;
1765 } else if (propType == Rm_policyPropType_UNKNOWN) {
1766 retVal = RM_ERROR_UNKNOWN_POLICY_RESOURCE_PROPERTY;
1767 goto errorExit;
1768 }
1769 /* else: fall through to get next property since read property
1770 * wasn't an assignment */
1772 propOffset = fdt_next_property_offset(policyDtb, propOffset);
1773 }
1774 if (propOffset < -FDT_ERR_NOTFOUND) {
1775 /* Error returned by LIBFDT */
1776 retVal = propOffset;
1777 goto errorExit;
1778 }
1780 nodeOffset = fdt_next_node(policyDtb, nodeOffset, &nodeDepth);
1781 if (nodeOffset < -FDT_ERR_NOTFOUND) {
1782 /* Error returned by LIBFDT */
1783 retVal = nodeOffset;
1784 goto errorExit;
1785 }
1786 }
1788 errorExit:
1789 return(retVal);
1790 }
1792 /* FUNCTION PURPOSE: Initializes the allocator tree root
1793 ***********************************************************************
1794 * DESCRIPTION: Initializes the allocator tree root structure
1795 */
1796 static int32_t allocatorTreeRootInit(Rm_Inst *rmInst)
1797 {
1798 Rm_AllocatorTree *root = NULL;
1799 int32_t retVal = RM_OK;
1801 root = Rm_osalMalloc(sizeof(*root));
1802 if (root) {
1803 RB_INIT(root);
1804 rmInst->allocatorTree = root;
1805 } else {
1806 retVal = RM_ERROR_COULD_NOT_INIT_ALLOC_TREE;
1807 }
1808 return(retVal);
1809 }
1811 /**********************************************************************
1812 ********************** Internal Functions ****************************
1813 **********************************************************************/
1815 /* FUNCTION PURPOSE: Finds an allocator
1816 ***********************************************************************
1817 * DESCRIPTION: Returns a pointer to an allocator that matches the
1818 * provided resource name.
1819 */
1820 Rm_AllocatorNode *rmAllocatorFind(Rm_Handle rmHandle, const char *resourceName)
1821 {
1822 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
1823 Rm_AllocatorTree *tree = rmInst->allocatorTree;
1824 Rm_AllocatorNode findNode;
1826 memset((void *)&findNode, 0, sizeof(findNode));
1827 rm_strncpy(findNode.resourceName, resourceName, RM_NAME_MAX_CHARS);
1829 return(RB_FIND(_Rm_AllocatorTree, tree, &findNode));
1830 }
1832 /* FUNCTION PURPOSE: Checks if a resource node is localized
1833 ***********************************************************************
1834 * DESCRIPTION: Checks if a resource node is localized. A localized
1835 * node is one that is free and has no neighboring nodes
1836 * or neighboring nodes that do not have resource values
1837 * contiguous with the node being checked. The function
1838 * will return RM_TRUE if the node is localized.
1839 * Otherwise, the function returns RM_FALSE
1840 */
1841 int rmAllocatorGetNodeLocalization(Rm_Handle rmHandle, char *resourceName,
1842 int32_t *resBase, uint32_t *resLen)
1843 {
1844 uint32_t allocSize;
1845 Rm_AllocatorNode *allocator = NULL;
1846 Rm_ResourceNode findNode;
1847 Rm_ResourceNode *matchingNode = NULL;
1848 Rm_ResourceNode *neighborNode = NULL;
1849 int nodeIsLocalized = RM_FALSE;
1851 allocator = rmAllocatorFind(rmHandle, resourceName);
1852 allocSize = rmPolicyGetCdAllocSize(allocator->policyRoot);
1854 /* Nothing to free back to server if policy never specified blocks could
1855 * be allocated to CD */
1856 if (allocSize) {
1857 memset((void *)&findNode, 0, sizeof(findNode));
1858 findNode.base = *resBase;
1859 findNode.length = *resLen;
1860 matchingNode = RB_FIND(_Rm_AllocatorResourceTree,
1861 allocator->resourceRoot, &findNode);
1863 if (matchingNode) {
1864 /* Node can be freed back to Server from CD if:
1865 * - allocationCount == 0
1866 * - node's resource range is multiple of policy allocation size
1867 * - node's resource range boundaries are not contiguous with
1868 * surrounding nodes */
1869 if (matchingNode->allocationCount) {
1870 goto exitLocalization;
1871 }
1873 if (matchingNode->length % allocSize) {
1874 goto exitLocalization;
1875 }
1877 /* Check left neighbor */
1878 neighborNode = RB_PREV(_Rm_AllocatorResourceTree,
1879 allocator->resourceRoot, matchingNode);
1880 if (neighborNode &&
1881 allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1882 goto exitLocalization;
1883 }
1885 /* Check right neighbor */
1886 neighborNode = RB_NEXT(_Rm_AllocatorResourceTree,
1887 allocator->resourceRoot, matchingNode);
1888 if (neighborNode &&
1889 allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1890 goto exitLocalization;
1891 }
1893 /* All localization checks passed. Return the base and length of
1894 * localized node. */
1895 nodeIsLocalized = RM_TRUE;
1896 *resBase = matchingNode->base;
1897 *resLen = matchingNode->length;
1898 } else {
1899 nodeIsLocalized = RM_FALSE;
1900 }
1901 }
1903 exitLocalization:
1904 return(nodeIsLocalized);
1905 }
1907 /* FUNCTION PURPOSE: Issues an allocator operation
1908 ***********************************************************************
1909 * DESCRIPTION: Issues an allocator preallocate, allocate, or free
1910 * for an RM resource.
1911 */
1912 int32_t rmAllocatorOperation(Rm_Handle rmHandle, Rm_AllocatorOpInfo *opInfo)
1913 {
1914 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
1915 Rm_AllocatorNode *allocator = NULL;
1916 int32_t retVal;
1918 if ((allocator = rmAllocatorFind(rmHandle, opInfo->resourceInfo->name))) {
1919 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1920 rmResourceTreeInv(allocator->resourceRoot);
1921 }
1923 if (opInfo->operation == Rm_allocatorOp_GET_STATUS) {
1924 retVal = allocatorStatus(rmHandle, allocator, opInfo);
1925 } else if ((opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) ||
1926 (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE)) {
1927 retVal = allocatorPreAllocate(rmHandle, allocator, opInfo);
1928 } else if ((opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) ||
1929 (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE)) {
1930 retVal = allocatorAllocate(rmHandle, allocator, opInfo);
1931 } else if (opInfo->operation == Rm_allocatorOp_FREE) {
1932 retVal = allocatorFree(rmHandle, allocator, opInfo);
1933 } else {
1934 retVal = RM_ERROR_INVALID_SERVICE_TYPE;
1935 }
1937 if ((rmInst->instType == Rm_instType_SHARED_SERVER) &&
1938 (opInfo->operation != Rm_allocatorOp_GET_STATUS) &&
1939 (retVal == RM_SERVICE_APPROVED)) {
1940 rmResourceTreeWb(allocator->resourceRoot);
1941 }
1942 } else {
1943 /* Resource could not be found in policy and/or allocator */
1944 retVal = RM_SERVICE_DENIED_RES_DOES_NOT_EXIST;
1945 }
1946 return(retVal);
1947 }
1949 /* FUNCTION PURPOSE: Initializes the allocator tree
1950 ***********************************************************************
1951 * DESCRIPTION: Initializes a RM instance's allocator tree using the
1952 * supplied GRL and policy
1953 */
1954 int32_t rmAllocatorTreeInit(Rm_Handle rmHandle, void *grlDtb,
1955 void *policyDtb, void *linuxDtb)
1956 {
1957 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
1958 int32_t retVal = RM_OK;
1960 if ((retVal = allocatorTreeRootInit(rmInst)) != RM_OK) {
1961 goto errorExit;
1962 }
1964 if (grlDtb && policyDtb &&
1965 ((rmInst->instType == Rm_instType_SERVER) ||
1966 (rmInst->instType == Rm_instType_SHARED_SERVER))) {
1967 /* Create an allocator for each resource node in GRL. Companion
1968 * policy info will be pulled and placed into policy tree */
1969 retVal = allocatorPopulateGrlBased(rmInst, grlDtb, policyDtb, linuxDtb);
1970 } else if (policyDtb &&
1971 ((rmInst->instType == Rm_instType_CLIENT_DELEGATE) ||
1972 (rmInst->instType == Rm_instType_CLIENT))) {
1973 /* Create an allocator for each resource node in the policy.
1974 * Resource tree portion of the allocator will be NULL. Resource
1975 * trees will be added at run time for Client Delegate instances.
1976 * Client instances with static policy just need allocators with
1977 * policy information for each resource. */
1978 retVal = allocatorPopulatePolicyBased(rmInst, policyDtb);
1979 } else if ((rmInst->instType != Rm_instType_CLIENT) &&
1980 (rmInst->instType != Rm_instType_SHARED_CLIENT)) {
1981 retVal = RM_ERROR_INVALID_ALLOCATOR_INIT;
1982 } else {
1983 retVal = RM_ERROR_INVALID_INST_TYPE;
1984 }
1986 errorExit:
1987 return(retVal);
1988 }
1990 /* FUNCTION PURPOSE: Adds a node to a resource tree
1991 ***********************************************************************
1992 * DESCRIPTION: Adds a node to an allocator's resource tree based on the
1993 * given base and length.
1994 */
1995 int32_t rmAllocatorAddResNode(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
1996 int32_t resBase, uint32_t resLen)
1997 {
1998 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
1999 Rm_ResourceNode *resNode = NULL;
2000 int32_t retVal = RM_OK;
2002 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2003 rmResourceTreeInv(allocator->resourceRoot);
2004 }
2006 if ((resNode = rmResourceNodeNew(resBase, resLen))) {
2007 if (RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot,
2008 resNode)) {
2009 retVal = RM_ERROR_RES_SPECIFIED_MORE_THAN_ONCE;
2010 }
2011 } else {
2012 retVal = RM_ERROR_MALLOC_FAILED_RES_NODE;
2013 }
2015 return(retVal);
2016 }
2018 /* FUNCTION PURPOSE: Deletes a node from a resource tree
2019 ***********************************************************************
2020 * DESCRIPTION: Deletes a node from an allocator's resource tree based on the
2021 * given base and length.
2022 */
2023 void rmAllocatorDeleteResNode(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
2024 int32_t resBase, uint32_t resLen)
2025 {
2026 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
2027 Rm_ResourceNode find;
2028 Rm_ResourceNode *match;
2030 memset((void *)&find, 0, sizeof(find));
2031 find.base = resBase;
2032 find.length = resLen;
2033 match = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
2034 &find);
2036 if (match) {
2037 RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot,
2038 match);
2039 rmResourceNodeFree(match);
2040 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2041 rmResourceTreeWb(allocator->resourceRoot);
2042 }
2043 }
2044 }
2046 /* FUNCTION PURPOSE: Deletes allocator tree
2047 ***********************************************************************
2048 * DESCRIPTION: Removes all resource nodes for each allocator node and then
2049 * deletes the allocator tree root.
2050 */
2051 void rmAllocatorTreeDelete(Rm_Handle rmHandle)
2052 {
2053 Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
2054 Rm_AllocatorTree *allocTree = rmInst->allocatorTree;
2055 Rm_AllocatorNode *allocNode;
2056 Rm_AllocatorNode *nextAllocNode;
2057 Rm_ResourceTree *resTree;
2058 Rm_ResourceNode *resNode;
2059 Rm_ResourceNode *nextResNode;
2060 Rm_PolicyTree *polTree;
2061 Rm_PolicyNode *polNode;
2062 Rm_PolicyNode *nextPolNode;
2064 if (allocTree) {
2065 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2066 rmAllocatorTreeInv(allocTree);
2067 }
2069 for (allocNode = RB_MIN(_Rm_AllocatorTree, allocTree);
2070 allocNode != NULL;
2071 allocNode = nextAllocNode) {
2072 nextAllocNode = RB_NEXT(_Rm_AllocatorTree, allocTree, allocNode);
2074 resTree = allocNode->resourceRoot;
2075 polTree = allocNode->policyRoot;
2077 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2078 rmResourceTreeInv(resTree);
2079 rmPolicyTreeInv(polTree);
2080 }
2082 /* Delete each node in the resource tree */
2083 for (resNode = RB_MIN(_Rm_AllocatorResourceTree, resTree);
2084 resNode != NULL;
2085 resNode = nextResNode) {
2086 nextResNode = RB_NEXT(_Rm_AllocatorResourceTree, resTree,
2087 resNode);
2088 RB_REMOVE(_Rm_AllocatorResourceTree, resTree, resNode);
2089 if (resNode->allocationCount) {
2090 /* Delete all the owners in the resource's owner list */
2091 allocatorResNodeOwnerClear(rmHandle, resNode);
2092 }
2093 rmResourceNodeFree(resNode);
2094 }
2095 Rm_osalFree((void *)resTree, sizeof(*resTree));
2097 /* Delete each node in the policy tree */
2098 for (polNode = RB_MIN(_Rm_AllocatorPolicyTree, polTree);
2099 polNode != NULL;
2100 polNode = nextPolNode) {
2101 nextPolNode = RB_NEXT(_Rm_AllocatorPolicyTree, polTree,
2102 polNode);
2103 RB_REMOVE(_Rm_AllocatorPolicyTree, polTree, polNode);
2104 rmPolicyNodeFree(polNode);
2105 }
2106 Rm_osalFree((void *)polTree, sizeof(*polTree));
2108 RB_REMOVE(_Rm_AllocatorTree, allocTree, allocNode);
2109 rmAllocatorNodeFree(allocNode);
2110 }
2111 Rm_osalFree((void *)allocTree, sizeof(*allocTree));
2112 RM_SS_OBJ_WB(rmInst, rmInst, Rm_Inst);
2113 }
2114 }