Added policy tree elements
[keystone-rtos/rm-lld.git] / src / rm_allocator.c
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.  Otherwise,
70  *              returns 0.
71  */
72 static int allocatorResNodeIsOwnedBy(Rm_Handle rmHandle, Rm_ResourceNode *node, Rm_PolicyValidInstNode *serviceInstNode)
73 {
74     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;
75     Rm_Owner *owner = node->ownerList;
77     while (owner) {
78         RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
79         if (owner->instNameNode == serviceInstNode) {
80             return(owner->refCnt);           
81         }
82         owner = owner->nextOwner;
83     }
84     return(0);
85 }
87 /* FUNCTION PURPOSE: Increments an owner's refCnt
88  ***********************************************************************
89  * DESCRIPTION: Increments a resource owner's reference count
90  */
91 static void allocatorResNodeOwnerRefCntInc(Rm_Handle rmHandle, Rm_ResourceNode *node, Rm_PolicyValidInstNode *serviceInstNode)
92 {
93     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;
94     Rm_Owner *owner = node->ownerList;
96     while (owner) {
97         RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
98         if (owner->instNameNode == serviceInstNode) {
99             owner->refCnt++;
100             RM_SS_OBJ_WB(rmInst, owner, Rm_Owner);
101             break;
102         }
103         owner = owner->nextOwner;
104     }
107 /* FUNCTION PURPOSE: Decrements an owner's refCnt
108  ***********************************************************************
109  * DESCRIPTION: Decrements a resource owner's reference count
110  */
111 static void allocatorResNodeOwnerRefCntDec(Rm_Handle rmHandle, Rm_ResourceNode *node, Rm_PolicyValidInstNode *serviceInstNode)
113     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;
114     Rm_Owner *owner = node->ownerList;
116     while (owner) {
117         RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
118         if (owner->instNameNode == serviceInstNode) {
119             owner->refCnt--;
120             RM_SS_OBJ_WB(rmInst, owner, Rm_Owner);
121             break;
122         }
123         owner = owner->nextOwner;
124     }
127 /* FUNCTION PURPOSE: Returns an owner's refCnt
128  ***********************************************************************
129  * DESCRIPTION: Returns a resource owner's reference count
130  */
131 static uint16_t allocatorResNodeOwnerGetRefCnt(Rm_Handle rmHandle, Rm_ResourceNode *node, Rm_PolicyValidInstNode *serviceInstNode)
133     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;
134     Rm_Owner *owner = node->ownerList;
136     while (owner) {
137         RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
138         if (owner->instNameNode == serviceInstNode) {
139             return (owner->refCnt);
140         }
141         owner = owner->nextOwner;
142     }
144     return(0);
147 /* FUNCTION PURPOSE: Adds an owner to an allocator resource
148  ***********************************************************************
149  * DESCRIPTION: Adds a RM instance node to a resource node's
150  *              list of owners.  If the owner is already present that
151  *              owner's reference count is incremented
152  */
153 static void allocatorResNodeOwnerAdd(Rm_Handle rmHandle, Rm_ResourceNode *node, Rm_PolicyValidInstNode *serviceInstNode)
155     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;    
156     Rm_Owner *ownerList = node->ownerList;
157     Rm_Owner *newOwner = NULL;
159     if (allocatorResNodeIsOwnedBy(rmHandle, node, serviceInstNode)) {
160         allocatorResNodeOwnerRefCntInc(rmHandle, node, serviceInstNode);
161     }
162     else {
163         newOwner = Rm_osalMalloc(sizeof(*newOwner));
165         if (newOwner) {
166             newOwner->instNameNode = serviceInstNode;
167             newOwner->refCnt = 0;
168             newOwner->nextOwner = NULL;  
170             /* Add owner entry to end of list */
171             if (ownerList) {
172                 RM_SS_OBJ_INV(rmInst, ownerList, Rm_Owner);
173                 while (ownerList->nextOwner) {
174                     ownerList = ownerList->nextOwner;
175                     RM_SS_OBJ_INV(rmInst, ownerList, Rm_Owner);
176                 }
177                 ownerList->nextOwner = newOwner;
178                 RM_SS_OBJ_WB(rmInst, ownerList, Rm_Owner);
179             }
180             else {
181                 node->ownerList = newOwner;
182             }
184             node->allocationCount++;
185             newOwner->refCnt++;
186             newOwner->instNameNode->allocRefCount++;
187             RM_SS_OBJ_WB(rmInst, newOwner, Rm_Owner);
188             RM_SS_OBJ_WB(rmInst, newOwner->instNameNode, Rm_PolicyValidInstNode);
189         }
190     }
193 /* FUNCTION PURPOSE: Compares two resource node's boundaries
194  ***********************************************************************
195  * DESCRIPTION: Returns TRUE if the resource nodes are neighbors from
196  *              a base+length perspective.  Otherwise, returns FALSE.
197  */
198 static int allocatorResNodeBoundaryCompare(Rm_ResourceNode *node1, Rm_ResourceNode *node2)
200     uint32_t node1End;
201     uint32_t node2End;
203     if (node1 && node2) {
204         node1End = node1->base + node1->length - 1;
205         node2End = node2->base + node2->length - 1;
206         
207         if (node1->base < node2->base) {
208             if (node1End == (node2->base - 1)) {
209                 return(RM_TRUE);
210             }
211         }
212         else if (node2->base < node1->base) {
213             if (node2End == (node1->base - 1)) {
214                 return(RM_TRUE);
215             }     
216         }
217     }
218     return(RM_FALSE);
221 /* FUNCTION PURPOSE: Compares two resource node's owners
222  ***********************************************************************
223  * DESCRIPTION: Returns TRUE if the owners of two resource nodes 
224  *              are equivalent.  Otherwise, returns FALSE.
225  */
226 static int allocatorResNodeOwnerCompare(Rm_Handle rmHandle, Rm_ResourceNode *node1, Rm_ResourceNode *node2)
228     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;    
229     Rm_Owner *node1Owners = node1->ownerList;
230     Rm_Owner *node2Owners = node2->ownerList;
231     int       matchedInst;
233     if (rmInst->instType == Rm_instType_SHARED_SERVER) {
234         while(node2Owners) {
235             Rm_osalBeginMemAccess((void *)node2Owners, sizeof(*node2Owners));
236             node2Owners = node2Owners->nextOwner;
237         }
238         node2Owners = node2->ownerList;
239     }
241     if (node1->allocationCount == node2->allocationCount) {
242         while (node1Owners) {
243             RM_SS_OBJ_INV(rmInst, node1Owners, Rm_Owner);
244             matchedInst = RM_FALSE;
245             while (node2Owners) {
246                 if ((node1Owners->instNameNode == node2Owners->instNameNode) &&
247                     (node1Owners->refCnt == node2Owners->refCnt)) {
248                     matchedInst = RM_TRUE;
249                     break;
250                 }
251                 node2Owners = node2Owners->nextOwner;
252             }
254             if (matchedInst) {
255                 node2Owners = node2->ownerList;
256                 node1Owners = node1Owners->nextOwner;
257             }
258             else {
259                 return(RM_FALSE);
260             }                
261         }
262     }
263     else {
264         return(RM_FALSE);
265     }  
266     
267     return(RM_TRUE);
270 /* FUNCTION PURPOSE: Deletes an owner from an allocator resource
271  ***********************************************************************
272  * DESCRIPTION: Removes a RM owner entry from a resource node's
273  *              list of owners.  If the refCnt for the specified
274  *              owner is greater than 1 only the refCnt is
275  *              decremented
276  */
277 static void allocatorResNodeOwnerDelete(Rm_Handle rmHandle, Rm_ResourceNode *node, void *serviceInstNode)
279     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;    
280     Rm_Owner *owner = node->ownerList;
281     Rm_Owner *prevOwner = NULL;
283     if (allocatorResNodeIsOwnedBy(rmHandle, node, serviceInstNode) > 1) {
284         allocatorResNodeOwnerRefCntDec(rmHandle, node, serviceInstNode);
285     }
286     else {
287         while (owner) {
288             RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
289             if (owner->instNameNode == serviceInstNode) {
290                 break;             
291             }
292             prevOwner = owner;
293             owner = owner->nextOwner;
294         }
296         if (owner) {
297             if (prevOwner == NULL) {
298                 node->ownerList = owner->nextOwner;
299             }
300             else {
301                 prevOwner->nextOwner = owner->nextOwner;
302                 RM_SS_OBJ_WB(rmInst, prevOwner, Rm_Owner);
303             }
304             
305             node->allocationCount--;
306             owner->instNameNode->allocRefCount--;
307             RM_SS_OBJ_WB(rmInst, owner->instNameNode, Rm_PolicyValidInstNode);
308             Rm_osalFree((void *)owner, sizeof(*owner));
309         }
310     }
313 /* FUNCTION PURPOSE: Copies the owners of a resource node
314  ***********************************************************************
315  * DESCRIPTION: Creates a list of resource owners for the destination
316  *              resource node that is equivalent to the source resource
317  *              node's owners
318  *
319  *              dstNode must be a newly created node without any owners.
320  */
321 static void allocatorResNodeOwnerCopy(Rm_Handle rmHandle, Rm_ResourceNode *dstNode, Rm_ResourceNode *srcNode)
323     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;
324     Rm_Owner *srcOwnerList = srcNode->ownerList;
325     Rm_Owner *dstNewOwner;
326     Rm_Owner *dstPrevOwner;
328     if (dstNode->ownerList != NULL) {
329         return;
330     }
331     dstNode->allocationCount = srcNode->allocationCount;
333     while (srcOwnerList) {
334         RM_SS_OBJ_INV(rmInst, srcOwnerList, Rm_Owner);
335         dstNewOwner = Rm_osalMalloc(sizeof(*dstNewOwner));
336         dstNewOwner->instNameNode = srcOwnerList->instNameNode;
337         dstNewOwner->refCnt = srcOwnerList->refCnt;
338         dstNewOwner->nextOwner = NULL;
339         RM_SS_OBJ_WB(rmInst, dstNewOwner, Rm_Owner);
341         if (dstNode->ownerList == NULL) {
342             dstNode->ownerList = dstNewOwner;
343         }
344         else {
345             dstPrevOwner->nextOwner = dstNewOwner;
346             RM_SS_OBJ_WB(rmInst, dstPrevOwner, Rm_Owner);
347         }
348         dstPrevOwner = dstNewOwner;
349         srcOwnerList = srcOwnerList->nextOwner;
350     }
353 /* FUNCTION PURPOSE: Clears a resource node's owners
354  ***********************************************************************
355  * DESCRIPTION: Deletes all owners from the owners list of a 
356  *              resource node.
357  */
358 static void allocatorResNodeOwnerClear(Rm_Handle rmHandle, Rm_ResourceNode *node)
360     Rm_Inst  *rmInst = (Rm_Inst *)rmHandle;    
361     Rm_Owner *owner = node->ownerList;
362     Rm_Owner *nextOwner;
364     while (owner) {
365         RM_SS_OBJ_INV(rmInst, owner, Rm_Owner);
366         nextOwner = owner->nextOwner;
367         node->allocationCount--;
368         owner->instNameNode->allocRefCount--;
369         RM_SS_OBJ_WB(rmInst, owner->instNameNode, Rm_PolicyValidInstNode);
370         Rm_osalFree((void *)owner, sizeof(*owner));
371         owner = nextOwner;
372     }
375 /* FUNCTION PURPOSE: Get the status for an allocator resource
376  ***********************************************************************
377  * DESCRIPTION: Called when a resource status request is made.  The
378  *              resource's allocator is searched for the resource base
379  *              and length specified in the transaction.  The 
380  *              resource's owner reference count is returned if the 
381  *              resource range is found.
382  */
383 static int32_t allocatorStatus(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
384                                Rm_AllocatorOpInfo *opInfo)
386     Rm_ResourceNode  findNode;
387     Rm_ResourceNode *matchingNode = NULL; 
388     uint32_t         matchingEnd;
389     uint32_t         findEnd;    
390     int32_t          retVal;
392     memset((void *)&findNode, 0, sizeof(findNode));
393     findNode.base = opInfo->resourceInfo->base;
394     findNode.length = opInfo->resourceInfo->length;
395     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
396                            &findNode);
398     if (matchingNode) {
399         matchingEnd = matchingNode->base + matchingNode->length - 1;
400         findEnd = findNode.base + findNode.length - 1;
401         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
402             opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
403             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
404                                                                                   opInfo->serviceSrcInstNode);            
405             retVal = RM_SERVICE_APPROVED;
406         }
407         else {
408             retVal = RM_SERVICE_DENIED_PARTIAL_STATUS;
409         }
410     }
411     else {
412         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
413     }
415     return(retVal);  
418 /* FUNCTION PURPOSE: Preallocates an allocator resource
419  ***********************************************************************
420  * DESCRIPTION: Called when an allocate request is made but the base 
421  *              is unspecified.  The preallocation algorithm looks at 
422  *              available resources as well as policy permissions to 
423  *              determine a resource range that satisfies the request.
424  *              If a valid range is found it will be returned for the 
425  *              treeAllocate algorithm to handle.
426  */
427 static int32_t allocatorPreAllocate(Rm_Handle rmHandle,
428                                     Rm_AllocatorNode *allocator,
429                                     int32_t resourcePolicy,
430                                     Rm_AllocatorOpInfo *opInfo)
431 {   
432     Rm_Inst           *rmInst = (Rm_Inst *)rmHandle;
433     Rm_ResourceNode    findNode;
434     Rm_ResourceNode   *matchingNode = NULL;
435     Rm_ResourceNode   *nextNode;
436     uint32_t           matchingEnd;
437     uint32_t           findEnd;
438     uint32_t           rangeIndex;
439     int                resourceFound = RM_FALSE;
440     Rm_PolicyCheckType policyCheckType;
441     Rm_PolicyCheckCfg  policyCheckCfg;
442     int                nodePassesPolicy;
443     int32_t            retVal = RM_OK;
445     if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) {
446         policyCheckType = Rm_policyCheck_INIT;
447     }
448     else if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE) {
449         policyCheckType = Rm_policyCheck_USE;
450     }
451     else {
452         retVal = RM_ERROR_INVALID_SERVICE_TYPE;
453         return (retVal);
454     }
456     if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
457         /* Set base to first node's base since CD will not have all resources like Server */
458         matchingNode = RB_MIN(_Rm_AllocatorResourceTree, allocator->resourceRoot);
459         opInfo->resourceInfo->base = matchingNode->base;
460     }
461     else {
462         opInfo->resourceInfo->base = rmPolicyGetResourceBase(opInfo->policy, opInfo->serviceSrcInstNode, 
463                                                              resourcePolicy, policyCheckType, 
464                                                              &retVal);
465     }
466     
467     if (retVal != RM_OK) {
468         return (retVal);
469     }
471     if (opInfo->resourceInfo->alignment == RM_RESOURCE_ALIGNMENT_UNSPECIFIED) {  
472         /* Get alignment from policy */
473         opInfo->resourceInfo->alignment = rmPolicyGetResourceAlignment(opInfo->policy, resourcePolicy);
474     } 
476     if (opInfo->resourceInfo->alignment == 0) {
477         opInfo->resourceInfo->alignment = 1;
478     } 
480     memset((void *)&findNode, 0, sizeof(findNode));
481     findNode.base = opInfo->resourceInfo->base;
482     findNode.length = opInfo->resourceInfo->length;
484     /* Configure policy checking structure */
485     memset((void *)&policyCheckCfg, 0, sizeof(policyCheckCfg));
486     policyCheckCfg.policyDtb = opInfo->policy;
487     policyCheckCfg.resourceOffset = resourcePolicy;
488     
489     do {
490         matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot, &findNode);
491         
492         if (matchingNode) {
493             matchingEnd = matchingNode->base + matchingNode->length - 1;
494             findEnd = findNode.base + findNode.length - 1;
495             nodePassesPolicy = RM_BOOL_UNDEF;
496             if ((matchingNode->allocationCount == 0) &&
497                 (findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
498                 /* Attempt to preallocate from node only if not owned by anyone and sits
499                  * within a matching node. */
500                 policyCheckCfg.type = policyCheckType;
501                 policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
502                 policyCheckCfg.resourceBase = findNode.base;
503                 policyCheckCfg.resourceLength = findNode.length;
504                 nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);    
505                 
506                 if (nodePassesPolicy && (matchingNode->allocationCount > 0)) {
507                     policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
508                     
509                     if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode, rmPolicyGetLinuxInstNode(rmHandle))) {
510                         /* Check if instance requesting resource has privileges to share
511                          * a resource already reserved by Linux */
512                         policyCheckCfg.type = Rm_policyCheck_SHARED_LINUX;
513                         nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
514                     }
516                     if (nodePassesPolicy) {
517                         /* Check exclusive privileges of instance requesting resource.  Requesting
518                          * instance with exclusive privileges can't reserve resource if already owned*/
519                         policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
520                         nodePassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
521                     }
522                 }
523                 
524                 if (nodePassesPolicy && (matchingNode->allocationCount == 1)) {
525                     /* Check exclusive privileges of instance that currently owns resource */
526                     policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
527                     policyCheckCfg.validInstNode = matchingNode->ownerList->instNameNode;
528                     nodePassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
529                 }
531                 if (retVal != RM_OK) {
532                     break;
533                 }
535                 if (nodePassesPolicy) {
536                     /* Initialize indexer to be first resource value that
537                      * alignment satisfies */
538                     rangeIndex = findNode.base;
539                     if (rangeIndex % opInfo->resourceInfo->alignment) {
540                         rangeIndex += (opInfo->resourceInfo->alignment -
541                                       (rangeIndex %
542                                        opInfo->resourceInfo->alignment));
543                     }
545                     if ((rangeIndex + opInfo->resourceInfo->length - 1) <=
546                         matchingEnd) {
547                         /* Block of unallocated resources within matchingNode
548                          * that satisfies allocate requirements */
549                         opInfo->resourceInfo->base = rangeIndex;
550                         resourceFound = RM_TRUE;
551                         retVal = RM_SERVICE_PROCESSING;
552                     }
553                 }
554             }
556             if (!resourceFound) {
557                 /* Check next resource node for available resources */
558                 if (findNode.base < matchingNode->base) {
559                     findNode.base = matchingNode->base;
560                 }
561                 else {
562                     if (!nodePassesPolicy) {
563                         findNode.base += findNode.length;
564                     }
565                     else {
566                         /* Matching node allocated, move to next node */
567                         if ((nextNode = RB_NEXT(_Rm_AllocatorResourceTree,
568                                                 allocator->resourceRoot,
569                                                 matchingNode))) {
570                             findNode.base = nextNode->base;
571                         }
572                         else {
573                             retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
574                         }
575                     }
576                 }
577             }
578         }
579         else {
580             retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
581         }
582     } while ((!resourceFound) && 
583              (retVal != RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET));
585     return(retVal); 
588 /* FUNCTION PURPOSE: Allocates an allocator resource
589  ***********************************************************************
590  * DESCRIPTION: Will attempt to allocate the resource with specified
591  *              base and length from the resource's allocator.  The
592  *              allocation algorithm will verify the allocation against
593  *              the policy permissions for the instance requesting the
594  *              allocation.  If the policy allows the allocation the 
595  *              algorithm will allocate the resource then combine any
596  *              resource nodes that may have become equivalent (in terms
597  *              of ownership) after the allocation.
598  */
599 static int32_t allocatorAllocate(Rm_Handle rmHandle,
600                                  Rm_AllocatorNode *allocator,
601                                  int32_t resourcePolicy,
602                                  Rm_AllocatorOpInfo *opInfo)
604     Rm_ResourceNode     findNode;
605     Rm_ResourceNode    *matchingNode = NULL;
606     Rm_ResourceNode    *leftNode = NULL;
607     Rm_ResourceNode    *rightNode = NULL;
608     Rm_PolicyCheckType  policyCheckType;
609     Rm_PolicyCheckCfg   policyCheckCfg;
610     int                 allocPassesPolicy;
611     int                 combineLeft = RM_FALSE;
612     int                 combineRight = RM_FALSE;
613     uint32_t            findEnd;
614     uint32_t            matchingEnd;
615     int32_t             retVal;
617     if (opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) {
618         policyCheckType = Rm_policyCheck_INIT;
619     }
620     else if (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE) {
621         policyCheckType = Rm_policyCheck_USE;
622     }
623     else {
624         retVal = RM_ERROR_INVALID_SERVICE_TYPE;
625         return (retVal);
626     }   
628     memset((void *)&findNode, 0, sizeof(findNode));
629     findNode.base = opInfo->resourceInfo->base;
630     findNode.length = opInfo->resourceInfo->length;
631     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot, &findNode);
633     /* Prepare privilege checks */
634     memset((void *)&policyCheckCfg, 0, sizeof(policyCheckCfg)); 
636     if (matchingNode) {
637         findEnd = findNode.base + findNode.length - 1;
638         matchingEnd = matchingNode->base + matchingNode->length - 1;
639         
640         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
641             if (opInfo->serviceSrcInstNode == rmPolicyGetLinuxInstNode(rmHandle)) {
642                 /* Bypass policy checks since Linux Kernel has full privileges */
643                 allocPassesPolicy = RM_TRUE;
644             }
645             else {
646                 policyCheckCfg.policyDtb = opInfo->policy;
647                 policyCheckCfg.resourceOffset = resourcePolicy;    
648                 policyCheckCfg.type = policyCheckType;
649                 policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
650                 policyCheckCfg.resourceBase = findNode.base;
651                 policyCheckCfg.resourceLength = findNode.length;
652                 allocPassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
653                 if (!allocPassesPolicy) {
654                     if (policyCheckType == Rm_policyCheck_INIT) {
655                         retVal = RM_SERVICE_DENIED_INIT_PERM_NOT_GIVEN;
656                     }
657                     else {
658                         retVal = RM_SERVICE_DENIED_USE_PERM_NOT_GIVEN;
659                     }
660                 }
662                 if (!allocatorResNodeIsOwnedBy(rmHandle, matchingNode, opInfo->serviceSrcInstNode)) {
663                     if (allocPassesPolicy && (matchingNode->allocationCount > 0)) {
664                         if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode, rmPolicyGetLinuxInstNode(rmHandle))) {
665                             /* Check if instance requesting resource has privileges to share
666                              * a resource already reserved by Linux */
667                             policyCheckCfg.type = Rm_policyCheck_SHARED_LINUX;
668                             policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
669                             allocPassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
670                             if (!allocPassesPolicy) {
671                                 retVal = RM_SERVICE_DENIED_RES_NOT_SHARED_LINUX;
672                             }
673                         }
674                         if (allocPassesPolicy) {
675                             /* Check exclusive privileges of instance requesting resource.  Requesting
676                              * instance with exclusive privileges can't reserve resource if already owned*/
677                             policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
678                             policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
679                             allocPassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
680                             if (!allocPassesPolicy) {
681                                 retVal = RM_SERVICE_DENIED_EXCLUSIVE_RES_ALLOCD;
682                             }
683                         }
684                     }
685                     if (allocPassesPolicy && (matchingNode->allocationCount == 1)) {
686                         /* Check exclusive privileges of instance that currently owns resource */
687                         policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
688                         policyCheckCfg.validInstNode = matchingNode->ownerList->instNameNode;
689                         allocPassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
690                         if (!allocPassesPolicy) {
691                             retVal = RM_SERVICE_DENIED_ALLOCD_TO_EXCLUSIVE_INST;
692                         }                
693                     }  
694                 }
695             }
696             
697             if (allocPassesPolicy) {
698                 /* Handle any possible node combinations if requesting instance is
699                  * not already in resource's owner list.  Automatic approval if requesting
700                  * instance is already in owner list. */
701                 if ((findNode.base == matchingNode->base) && (findEnd == matchingEnd)) {
702                     /* findNode range matches matchingNode range
703                      *
704                      *   |<--left node-->||<--matched  node-->||<--right node-->| => existing node
705                      *                    |<--alloc request-->|  => requested resources
706                      */                     
707                     leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
708                     rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
709                     RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
710                     allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
712                     if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
713                         allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
714                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
715                         combineLeft = RM_TRUE;
716                     }
717                     if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
718                         allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
719                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
720                         combineRight = RM_TRUE;
721                     }
723                     if (combineLeft && combineRight) {
724                         /* Combine all three nodes into matchingNode */
725                         matchingNode->base = leftNode->base;
726                         matchingNode->length = leftNode->length + matchingNode->length + rightNode->length;
728                         allocatorResNodeOwnerClear(rmHandle, leftNode);
729                         rmResourceNodeFree(leftNode);
730                         allocatorResNodeOwnerClear(rmHandle, rightNode);
731                         rmResourceNodeFree(rightNode);                        
732                     }
733                     else if (combineLeft) {
734                         /* Combine left and matching nodes.  Reinsert right. */
735                         matchingNode->base = leftNode->base;
736                         matchingNode->length += leftNode->length;
738                         allocatorResNodeOwnerClear(rmHandle, leftNode);
739                         rmResourceNodeFree(leftNode);
740                         if (rightNode) {
741                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);  
742                         }
743                     }
744                     else if (combineRight) {
745                         /* Combine right and matching nodes.  Reinsert left. */
746                         matchingNode->length += rightNode->length;
748                         allocatorResNodeOwnerClear(rmHandle, rightNode);
749                         rmResourceNodeFree(rightNode);
750                         if (leftNode) {
751                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
752                         }
753                     }
754                     else {
755                         /* No combine. */
756                         if (leftNode) {
757                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
758                         }
759                         if (rightNode) {
760                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
761                         }
762                     }
764                     /* Always reinsert matchingNode */                
765                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
766                     
767                     /* Matching node contains new reference count after alloc.  Return new owner count
768                      * and originating instance allocation reference count. */
769                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
770                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
771                                                                                           opInfo->serviceSrcInstNode);
772                 }   
773                 else if ((findNode.base > matchingNode->base) && (findEnd < matchingEnd)) {
774                     /* findNode range is subset of matchingNode range and neither boundary is
775                      * equivalent.
776                      *
777                      * |<----------matched node---------->|
778                      *        |<---alloc request--->|
779                      */ 
780                     RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
781                     leftNode = rmResourceNodeNew(matchingNode->base, findNode.base - matchingNode->base);
782                     allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
783                     rightNode = rmResourceNodeNew(findNode.base + findNode.length, matchingEnd - findEnd);
784                     allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
786                     matchingNode->base = findNode.base;                                    
787                     matchingNode->length = findNode.length;
788                     allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
790                     /* Insert all the nodes */
791                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
792                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
793                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
794                     
795                     /* Matching node contains new reference count after alloc.  Return new owner count
796                      * and originating instance allocation reference count. */
797                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
798                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode, 
799                                                                                           opInfo->serviceSrcInstNode);
800                 }  
801                 else {    
802                     if (findNode.base == matchingNode->base) {
803                         /* findNode base and matchingNode base are equivalent.  May be combine
804                          * possibilities to the left
805                          *
806                          * |<---left node (alloc'd)--->||<----------matched node---------->|
807                          *                              |<---findNode (alloc req)--->|
808                          */                         
809                         leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
810                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
811                         /* Add allocating instance to owner list for compare with leftNode */
812                         allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
813                         
814                         if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
815                             allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
816                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
817                             /* Combine leftNode and findNode */
818                             leftNode->length += findNode.length;
819                         }
820                         else {
821                             leftNode = rmResourceNodeNew(findNode.base, findNode.length);
822                             allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
823                         }
825                         /* Account for leftNode in matchingNode */
826                         matchingNode->base = findNode.base + findNode.length;
827                         matchingNode->length = matchingEnd - findEnd;  
829                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
830                         /* Left node contains new reference count after alloc.  Return new owner count
831                          * and originating instance allocation reference count. */
832                         opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
833                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, leftNode, 
834                                                                                               opInfo->serviceSrcInstNode);
835                     }
836                     else if (findEnd == matchingEnd) {
837                         /* findNode end and matchingNode end are equivalent.  May be combine
838                          * possibilities to the right
839                          *
840                          * |<----------matched node---------->||<---right node (alloc'd)--->|
841                          *       |<---findNode (alloc req)--->|
842                          */                        
843                         rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
844                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
845                         /* Add allocating instance to owner list for compare with rightNode */
846                         allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
847                         
848                         if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
849                             allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
850                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
851                             /* Combine rightNode and findNode */
852                             rightNode->base = findNode.base;
853                             rightNode->length += findNode.length;
854                         }
855                         else {
856                             rightNode = rmResourceNodeNew(findNode.base, findNode.length);
857                             allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
858                         }
860                         /* Account for rightNode in matchingNode */
861                         matchingNode->length -= findNode.length;  
863                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
864                         /* Right node contains new reference count after alloc.  Return new owner count
865                          * and originating instance allocation reference count. */
866                         opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
867                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, rightNode, 
868                                                                                               opInfo->serviceSrcInstNode);
869                     }
870                     /* Remove allocating instance from leftover matchingNode */
871                     allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
872                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
873                 }
874                 retVal = RM_SERVICE_APPROVED;
875             }
876         }
877         else {
878             retVal = RM_SERVICE_DENIED_PARTIAL_ALLOCATION;
879         }
880     }
881     else {
882         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
883     }
885     return(retVal);        
888 /* FUNCTION PURPOSE: Frees an allocator resource
889  ***********************************************************************
890  * DESCRIPTION: Will attempt to free the resource with specified
891  *              base and length from the resource's allocator.  The
892  *              free algorithm will verify the free request parameters
893  *              match an allocated range for the resource and that the
894  *              range is owned by the instance requesting the free. If
895  *              the free is validated the algorithm will free the 
896  *              resource then combine any resource nodes that may have
897  *              become equivalent (in terms of ownership) after the
898  *              allocation.
899  */
900 static int32_t allocatorFree(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
901                              Rm_AllocatorOpInfo *opInfo)
903     Rm_ResourceNode  findNode;
904     Rm_ResourceNode *matchingNode = NULL;
905     Rm_ResourceNode *leftNode = NULL;
906     Rm_ResourceNode *rightNode = NULL;
907     int              combineLeft = RM_FALSE;
908     int              combineRight = RM_FALSE;
909     uint32_t         findEnd;
910     uint32_t         matchingEnd;
911     int32_t          retVal;
913     memset((void *)&findNode, 0, sizeof(findNode));
914     findNode.base = opInfo->resourceInfo->base;
915     findNode.length = opInfo->resourceInfo->length;
916     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot, &findNode);
918     if (matchingNode) {
919         findEnd = findNode.base + findNode.length - 1;
920         matchingEnd = matchingNode->base + matchingNode->length - 1;
921         
922         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {  
923             if (matchingNode->allocationCount) {
924                 if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode, opInfo->serviceSrcInstNode)) {
925                     if ((findNode.base == matchingNode->base) && (findEnd == matchingEnd))
926                     {
927                         /* Case 1: Free range equals allocated matched node exactly. Attempt to combine 
928                          *         freed node with nodes to left and right.
929                          *
930                          * |<--left node-->||<---matched node--->||<--right node-->|
931                          *                  |<---free request--->|
932                          */ 
933                         leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
934                         rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
935                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
936                         allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
938                         if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
939                             allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
940                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
941                             combineLeft = RM_TRUE;
942                         }
943                         if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
944                             allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
945                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
946                             combineRight = RM_TRUE;
947                         }
949                         if (combineLeft && combineRight) {
950                             /* Combine all three nodes into matchingNode */
951                             matchingNode->base = leftNode->base;
952                             matchingNode->length = leftNode->length + matchingNode->length + rightNode->length;
954                             allocatorResNodeOwnerClear(rmHandle, leftNode);
955                             rmResourceNodeFree(leftNode);
956                             allocatorResNodeOwnerClear(rmHandle, rightNode);
957                             rmResourceNodeFree(rightNode);                        
958                         }
959                         else if (combineLeft) {
960                             /* Combine left and matching nodes.  Reinsert right. */
961                             matchingNode->base = leftNode->base;
962                             matchingNode->length += leftNode->length;
964                             allocatorResNodeOwnerClear(rmHandle, leftNode);
965                             rmResourceNodeFree(leftNode);
966                             if (rightNode) {
967                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode); 
968                             }
969                         }
970                         else if (combineRight) {
971                             /* Combine right and matching nodes.  Reinsert left. */
972                             matchingNode->length += rightNode->length;
974                             allocatorResNodeOwnerClear(rmHandle, rightNode);
975                             rmResourceNodeFree(rightNode);
976                             if (leftNode) {
977                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
978                             }
979                         }
980                         else {
981                             /* No combine. */
982                             if (leftNode) {
983                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
984                             }
985                             if (rightNode) {
986                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
987                             }
988                         }
990                         /* Always reinsert matchingNode */
991                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
992                         
993                         /* Matching node is what remains after free.  Return remaining owner count
994                          * and originating instance allocation reference count. */
995                         opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
996                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
997                                                                                               opInfo->serviceSrcInstNode);
998                     }
999                     else if ((findNode.base > matchingNode->base) && (findEnd < matchingEnd)) {
1000                         /* Case 2: Free range is less than range in matched node. Split
1001                          *         matched node into three nodes.
1002                          *
1003                          * |<----------matched node---------->|
1004                          *        |<---free request--->|
1005                          *
1006                          * Remove instance from owner list then add it back in for side nodes for
1007                          * proper accounting of allocations in validInstance list
1008                          */ 
1009                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1010                         allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1011                         
1012                         leftNode = rmResourceNodeNew(matchingNode->base, findNode.base - matchingNode->base);
1013                         allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
1014                         allocatorResNodeOwnerAdd(rmHandle, leftNode, opInfo->serviceSrcInstNode);
1015                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
1016                         
1017                         rightNode = rmResourceNodeNew(findNode.base + findNode.length, matchingEnd - findEnd);
1018                         allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
1019                         allocatorResNodeOwnerAdd(rmHandle, rightNode, opInfo->serviceSrcInstNode);
1020                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
1022                         matchingNode->base = findNode.base;                                    
1023                         matchingNode->length = findNode.length;
1024                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1025                         
1026                         /* Matching node is what remains after free.  Return remaining owner count
1027                          * and originating instance allocation reference count. */
1028                         opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1029                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
1030                                                                                               opInfo->serviceSrcInstNode);
1031                     }
1032                     else {                        
1033                         if (findNode.base == matchingNode->base) {
1034                             /* Case 3: Free range is on left boundary of matched node. Try to 
1035                              *         combine free range with left node.
1036                              *
1037                              * |<---left node (free)--->||<----------matched node---------->|
1038                              *                           |<---findNode (free req)--->|
1039                              */ 
1041                             leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1042                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1043                             /* Remove freeing instance from owner list for compare with leftNode */
1044                             allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1045                             
1046                             if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
1047                                 allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
1048                                 RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
1049                                 /* Combine leftNode and findNode */
1050                                 leftNode->length += findNode.length;
1051                             }
1052                             else {
1053                                 leftNode = rmResourceNodeNew(findNode.base, findNode.length);
1054                                 allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
1055                             }
1057                             /* Remove leftNode range from matchingNode */
1058                             matchingNode->base = findNode.base + findNode.length;
1059                             matchingNode->length = matchingEnd - findEnd;  
1060                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, leftNode);
1061                             
1062                             /* Left node is what remains after free.  Return remaining owner count
1063                              * and originating instance allocation reference count. */
1064                             opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
1065                             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, leftNode,
1066                                                                                                   opInfo->serviceSrcInstNode);
1067                         }
1068                         else if (findEnd == matchingEnd) {
1069                             /* Case 4: Free range is on right boundary of matched node. Try to 
1070                              *         combine free range with right node.
1071                              *
1072                              * |<----------matched node---------->||<---right node (free)--->|
1073                              *        |<---findNode (free req)--->|
1074                              */ 
1075                             
1076                             rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1077                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode); 
1078                             /* Remove freeing instance from owner list for compare with rightNode */
1079                             allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1080                             
1081                             if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
1082                                 allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
1083                                 RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
1084                                 /* Combine rightNode and findNode */
1085                                 rightNode->base = findNode.base;
1086                                 rightNode->length += findNode.length;
1087                             }
1088                             else {
1089                                 rightNode = rmResourceNodeNew(findNode.base, findNode.length);
1090                                 allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
1091                             }
1093                             /* Remove rightNode range from matchingNode */
1094                             matchingNode->length -= findNode.length;  
1095                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, rightNode);
1096                             
1097                             /* Right node is what remains after free.  Return remaining owner count
1098                              * and originating instance allocation reference count. */
1099                             opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
1100                             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, rightNode,
1101                                                                                                   opInfo->serviceSrcInstNode);
1102                         }
1104                         /* Add freeing instance back into matchingNode allocations */
1105                         allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1106                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1107                     }
1108                     retVal = RM_SERVICE_APPROVED;
1109                 }
1110                 else {
1111                     /* Return owner count and instance alloc count.  In case it's a reference count
1112                      * check in application */
1113                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1114                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
1115                                                                                           opInfo->serviceSrcInstNode);
1116                     retVal = RM_SERVICE_DENIED_RES_NOT_ALLOCD_TO_INST;
1117                 }
1118             }
1119             else {
1120                 /* Return owner count and instance alloc count.  In case it's a reference count
1121                  * check in application */
1122                 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1123                 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
1124                                                                                       opInfo->serviceSrcInstNode);
1125                 retVal = RM_SERVICE_DENIED_RES_ALREADY_FREE;
1126             }
1127         }
1128         else {
1129             retVal = RM_SERVICE_DENIED_PARTIAL_FREE;
1130         }
1131     }
1132     else {
1133         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
1134     }
1135     return(retVal);  
1138 /* FUNCTION PURPOSE: Reserves a Linux resource
1139  ***********************************************************************
1140  * DESCRIPTION: Reserves resources for Linux using the base and length
1141  *              values retrieved from the Linux DTB via the
1142  *              "linux-dtb-alias" properties within the GRL.
1143  */
1144 static int32_t allocatorReserveLinuxResource(Rm_Handle rmHandle, Rm_LinuxAlias *linuxAlias, 
1145                                              Rm_LinuxValueRange *linuxValues, Rm_AllocatorOpInfo *opInfo)
1147     int32_t   retVal = RM_OK;
1148     int       baseFound = RM_FALSE;
1149     int       lengthFound = RM_FALSE;
1150     uint32_t  valueIndex = 0;
1152     while ((linuxValues) && (!baseFound || !lengthFound)) {
1153         if (linuxAlias->baseOffset == valueIndex) {
1154             opInfo->resourceInfo->base = linuxValues->value;
1155             baseFound = RM_TRUE;
1157             if (linuxAlias->lengthOffset == RM_DTB_UTIL_LINUX_ALIAS_OFFSET_NOT_SET) {
1158                 opInfo->resourceInfo->length = 1;
1159                 lengthFound = RM_TRUE;
1160             }
1161         }
1162         else if (linuxAlias->lengthOffset == valueIndex) {
1163             opInfo->resourceInfo->length = linuxValues->value;
1164             lengthFound = RM_TRUE;
1165         }
1167         linuxValues = (Rm_LinuxValueRange *)linuxValues->nextValue;
1168         valueIndex++;
1169     }
1171     if (!baseFound || !lengthFound) {
1172         retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1173     }
1174     else {
1175         /* Allocate resource to Linux */
1176         retVal = rmAllocatorOperation(rmHandle, opInfo);
1177         if (retVal == RM_SERVICE_APPROVED) {
1178             retVal = RM_OK;
1179         }
1180     }
1181     return (retVal);
1184 /* FUNCTION PURPOSE: Finds and reserves Linux resources
1185  ***********************************************************************
1186  * DESCRIPTION: Parses the Linux DTB for resources consumed by the
1187  *              Linux kernel.  If the resource is found via the
1188  *              "linux-dtb-alias" property defined in the GRL it is 
1189  *              reserved.
1190  */
1191 static int32_t allocatorFindLinuxResource(Rm_Handle rmHandle, const char *resourceName, void *linuxDtb, 
1192                                           Rm_LinuxAlias *linuxAlias)
1194     Rm_Inst            *rmInst = (Rm_Inst *)rmHandle;
1195     Rm_AllocatorOpInfo  opInfo;
1196     Rm_ResourceInfo     resourceInfo;
1197     uint32_t            pathOffset;
1198     uint32_t            pathSize;
1199     char               *tempAliasPath;
1200     char               *spacePtr;
1201     int32_t             propOffset;
1202     int32_t             nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1203     int32_t             prevDepth = RM_DTB_UTIL_STARTING_DEPTH;
1204     int32_t             depth = RM_DTB_UTIL_STARTING_DEPTH;
1205     int32_t             propertyLen;
1206     const char         *propertyName;
1207     const void         *propertyData; 
1208     Rm_LinuxValueRange *linuxValueRange;
1209     int32_t             retVal = RM_OK; 
1211     memset((void *)&opInfo, 0, sizeof(opInfo));
1212     memset((void *)&resourceInfo, 0, sizeof(resourceInfo));
1214     rm_strncpy(resourceInfo.name, resourceName, RM_NAME_MAX_CHARS);
1215     opInfo.policy = rmInst->u.server.globalPolicy;
1216     opInfo.serviceSrcInstNode = rmPolicyGetLinuxInstNode(rmHandle);
1217     opInfo.operation = Rm_allocatorOp_ALLOCATE_INIT;
1218     opInfo.resourceInfo = &resourceInfo;    
1220     while(linuxAlias) {
1221         /* Reset parsing variables */
1222         pathOffset = 0;
1223         pathSize = strlen(linuxAlias->path) + 1;
1224         tempAliasPath = Rm_osalMalloc(pathSize);
1225         rm_strncpy(tempAliasPath, linuxAlias->path, pathSize);
1226         nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1227         prevDepth = RM_DTB_UTIL_STARTING_DEPTH;   
1228         resourceInfo.base = 0;
1229         resourceInfo.length = 0;
1231         spacePtr = strpbrk(tempAliasPath, " ");
1232         if (spacePtr) {
1233             *spacePtr = '\0';
1234         }       
1235         
1236         while(pathOffset < pathSize) {
1237             /* Move through DTB nodes until next alias path node found */
1238             if (strcmp(tempAliasPath + pathOffset, fdt_get_name(linuxDtb, nodeOffset, NULL))) {
1239                 nodeOffset = fdt_next_node(linuxDtb, nodeOffset, &depth);
1241                 if ((depth < prevDepth) || (nodeOffset == -FDT_ERR_NOTFOUND)) {
1242                     /* Returning from subnode that matched part of alias path without finding
1243                      * resource values */
1244                     retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1245                     break;
1246                 }
1247             }
1248             else {
1249                 /* Found next alias path node.  Move to next node name in path string. */
1250                 pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1251                 spacePtr = strpbrk(tempAliasPath + pathOffset, " ");
1252                 if (spacePtr) {
1253                     *spacePtr = '\0';
1254                 }       
1255                 
1256                 prevDepth = fdt_node_depth(linuxDtb, nodeOffset);
1257                 propOffset = fdt_first_property_offset(linuxDtb, nodeOffset);
1258                 while ((propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1259                        (pathOffset < pathSize)) {
1260                     propertyData = fdt_getprop_by_offset(linuxDtb, propOffset, 
1261                                                          &propertyName, &propertyLen);
1263                     if (strcmp(tempAliasPath + pathOffset, propertyName) == 0) {
1264                         /* Found resource at end of alias path */
1265                         pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1266                         linuxValueRange = rmDtbUtilLinuxExtractValues(propertyData, propertyLen);
1267                         retVal = allocatorReserveLinuxResource(rmHandle, linuxAlias, 
1268                                                                linuxValueRange, &opInfo);
1269                         rmDtbUtilLinuxFreeValues(linuxValueRange);
1270                     }
1271                     propOffset = fdt_next_property_offset(linuxDtb, propOffset);
1272                 } 
1274                 if (propOffset < -FDT_ERR_NOTFOUND) {
1275                     retVal = propOffset;
1276                     break;
1277                 }
1278             }
1279         }
1280         
1281         Rm_osalFree(tempAliasPath, pathSize);
1282         if (retVal < RM_OK) {
1283             break;
1284         }
1285         linuxAlias = linuxAlias->nextLinuxAlias;
1286     }
1287     return (retVal);
1290 /* FUNCTION PURPOSE: Creates and initializes a resource allocator
1291  ***********************************************************************
1292  * DESCRIPTION: Creates a resource allocator for the provided
1293  *              resource name and resource properties retrieved
1294  *              from the GRL.  Resources will be reserved for 
1295  *              the Linux kernel if the Linux DTB is provided
1296  *              and there are "linux-dtb-alias" properties
1297  *              specified in the GRL.
1298  */
1299 static int32_t allocatorExtractGrlResProps(Rm_Handle rmHandle,
1300                                            const char *resourceName,
1301                                            Rm_ResourceProperties *resProps,
1302                                            void *linuxDtb)
1304     Rm_Inst             *rmInst = (Rm_Inst *)rmHandle;
1305     Rm_ResourceRange    *range = NULL;
1306     Rm_ResourceRange    *rangeBasePtr = NULL;
1307     Rm_NsAssignment     *nsAssignments = NULL;
1308     Rm_NsAssignment     *nsAssignmentBasePtr = NULL;
1309     Rm_LinuxAlias       *linuxAlias = NULL;
1310     Rm_NameServerObjCfg  nameServerObjCfg;
1311     int32_t              retVal = RM_OK;
1312     
1313     if ((strlen(resourceName) + 1) > RM_NAME_MAX_CHARS) {
1314         retVal = RM_ERROR_RESOURCE_NAME_TOO_LONG;
1315         return(retVal);
1316     }
1318     if (resProps->rangeData && (resProps->rangeLen > 0)) {
1319         range = rangeBasePtr = rmDtbUtilResExtractRange(resProps->rangeData,
1320                                                         resProps->rangeLen);
1322         if ((retVal = rmAllocatorCreate(rmHandle, resourceName, range)) >= RM_OK) {
1323             if (resProps->linuxAliasData && resProps->linuxAliasLen) {
1324                 if (linuxDtb) {
1325                     linuxAlias = rmDtbUtilResExtractLinuxAlias(resProps->linuxAliasData,
1326                                                                resProps->linuxAliasLen, &retVal);
1327                     if (linuxAlias) {
1328                         retVal = allocatorFindLinuxResource(rmHandle, resourceName, linuxDtb, linuxAlias);            
1329                     }
1330                 }
1331             }
1332         }
1333     }
1334     
1335     if (retVal >= RM_OK) {
1336         if (resProps->nsAssignData && resProps->nsAssignLen) {
1337             nsAssignments = rmDtbUtilResExtractNsAssignment(resProps->nsAssignData, 
1338                                                             resProps->nsAssignLen, &retVal);
1339             if (nsAssignments) {
1340                 nsAssignmentBasePtr = nsAssignments;
1341                 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1342                     rmNameServerTreeInv(rmInst->u.server.nameServer);
1343                 }                  
1344                 while (nsAssignments) {
1345                     memset((void *)&nameServerObjCfg, 0, sizeof(nameServerObjCfg));
1346                     nameServerObjCfg.nameServerTree = rmInst->u.server.nameServer;
1347                     nameServerObjCfg.nodeCfg.objName = nsAssignments->nsName;
1348                     nameServerObjCfg.nodeCfg.resourceName = (char *)resourceName;
1349                     nameServerObjCfg.nodeCfg.resourceBase= nsAssignments->resourceBase;
1350                     nameServerObjCfg.nodeCfg.resourceLength = nsAssignments->resourceLength;                
1351                     rmNameServerAddObject(&nameServerObjCfg);
1352                     nsAssignments = nsAssignments->nextNsAssignment;
1353                 }
1354                 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1355                     rmNameServerTreeWb(rmInst->u.server.nameServer);
1356                 }                
1357                 rmDtbUtilResFreeNsAssignmentList(nsAssignmentBasePtr);
1358             }
1359         }
1360     }
1361     else if (retVal != RM_ERROR_COULD_NOT_CREATE_NEW_ALLOCATOR) {
1362         rmAllocatorDelete(rmHandle, resourceName);
1363     }
1365     rmDtbUtilResFreeRange(rangeBasePtr);
1366     if (linuxAlias) {
1367         rmDtbUtilResFreeLinuxAlias(linuxAlias);
1368     }
1369     return(retVal);
1372 /**********************************************************************
1373  ********************** Internal Functions ****************************
1374  **********************************************************************/
1376 /* FUNCTION PURPOSE: Creates a new allocator
1377  ***********************************************************************
1378  * DESCRIPTION: Creates a new allocator and its resource tree
1379  *              using the provided resource name and value range.  The
1380  *              name and value originate from the GRL.
1381  */
1382 int32_t rmAllocatorCreate(Rm_Handle rmHandle, const char *resourceName,
1383                           Rm_ResourceRange *range)
1385     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1386     Rm_AllocatorTree *allocTree   = rmAllocatorGetTree(rmHandle);
1387     Rm_AllocatorNode *newAllocNode = NULL;
1388     Rm_ResourceTree  *resTree = NULL;
1389     Rm_ResourceNode  *resNode = NULL;
1391     newAllocNode = rmAllocatorNodeNew(resourceName);
1392     if (newAllocNode) {
1393         resTree = Rm_osalMalloc(sizeof(*resTree));
1394         RB_INIT(resTree);
1396         while (range != NULL) {
1397             resNode = rmResourceNodeNew(range->base, range->length);
1398             RB_INSERT(_Rm_AllocatorResourceTree, resTree, resNode);
1399             range = range->nextRange;
1400         }
1401         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1402             rmResourceTreeWb(resTree);
1403         }
1405         newAllocNode->resourceRoot = resTree;
1406         RM_SS_OBJ_WB(rmInst, newAllocNode, Rm_AllocatorNode);
1408         RB_INSERT(_Rm_AllocatorTree, allocTree, newAllocNode);
1409         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1410             rmAllocatorTreeWb(allocTree);
1411         }
1412     }
1413     else {
1414         return(RM_ERROR_COULD_NOT_CREATE_NEW_ALLOCATOR);
1415     }
1417     return(RM_OK);
1420 /* FUNCTION PURPOSE: Returns a pointer to the allocator tree
1421  ***********************************************************************
1422  * DESCRIPTION: Returns a pointer to the instance's allocator tree
1423  *              based on the instance type
1424  */
1425 Rm_AllocatorTree *rmAllocatorGetTree(Rm_Handle rmHandle)
1427     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1428     Rm_AllocatorTree *tree = NULL;
1430     if ((rmInst->instType == Rm_instType_SERVER) ||
1431         (rmInst->instType == Rm_instType_SHARED_SERVER)) {
1432         tree = rmInst->u.server.allocatorTree;
1433     }
1434     else if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
1435         tree = rmInst->u.cd.allocatorTree;
1436     }
1437     return(tree);
1440 /* FUNCTION PURPOSE: Finds an allocator
1441  ***********************************************************************
1442  * DESCRIPTION: Returns a pointer to an allocator that matches the 
1443  *              provided resource name.
1444  */
1445 Rm_AllocatorNode *rmAllocatorFind(Rm_Handle rmHandle, const char *resourceName)
1447     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1448     Rm_AllocatorTree *tree = rmAllocatorGetTree(rmHandle);
1449     Rm_AllocatorNode  findNode;
1451     if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1452         rmAllocatorTreeInv(tree);
1453     }
1455     memset((void *)&findNode, 0, sizeof(Rm_AllocatorNode));
1456     rm_strncpy(findNode.resourceName, resourceName, RM_NAME_MAX_CHARS);
1458     return(RB_FIND(_Rm_AllocatorTree, tree, &findNode));
1461 /* FUNCTION PURPOSE: Checks if a resource node is localized
1462  ***********************************************************************
1463  * DESCRIPTION: Checks if a resource node is localized.  A localized
1464  *              node is one that is free and has no neighboring nodes
1465  *              or neighboring nodes that do not have resource values
1466  *              contiguous with the node being checked.  The function
1467  *              will return RM_TRUE if the node is localized.  
1468  *              Otherwise, the function returns RM_FALSE
1469  */
1470 int rmAllocatorGetNodeLocalization(Rm_Handle rmHandle, char *resourceName,
1471                                    int32_t *resBase, uint32_t *resLen)
1473     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1474     void             *policy = NULL;
1475     int32_t           resOffsetInPolicy;
1476     uint32_t          allocSize;
1477     Rm_AllocatorNode *allocator = NULL;
1478     Rm_ResourceNode   findNode;
1479     Rm_ResourceNode  *matchingNode = NULL;
1480     Rm_ResourceNode  *neighborNode = NULL;
1481     int               nodeIsLocalized = RM_FALSE;
1483     policy = rmPolicyGetPolicy((Rm_Handle)rmInst);
1484     resOffsetInPolicy = rmPolicyGetResourceOffset(policy,resourceName);
1485     allocSize = rmPolicyGetResourceCdAllocSize(policy, resOffsetInPolicy);
1486     allocator = rmAllocatorFind(rmHandle, resourceName);
1488     /* Nothing to free back to server if policy never specified blocks could be allocated
1489      * to CD */
1490     if (allocSize) {
1491         memset((void *)&findNode, 0, sizeof(findNode));
1492         findNode.base = *resBase;
1493         findNode.length = *resLen;
1494         matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot, &findNode);
1496         if (matchingNode) {
1497             /* Node can be freed back to Server from CD if:
1498              * - allocationCount == 0
1499              * - node's resource range is multiple of policy allocation size
1500              * - node's resource range boundaries are not contiguous with surrounding nodes */
1501             if (matchingNode->allocationCount) {
1502                 goto exitLocalization;
1503             }
1504                 
1505             if (matchingNode->length % allocSize) {
1506                 goto exitLocalization;        
1507             }
1509             /* Check left neighbor */
1510             neighborNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1511             if (neighborNode && allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1512                 goto exitLocalization; 
1513             }
1515             /* Check right neighbor */
1516             neighborNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRoot, matchingNode);
1517             if (neighborNode && allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1518                 goto exitLocalization; 
1519             }
1521             /* All localization checks passed.  Return the base and length of localized node. */
1522             nodeIsLocalized = RM_TRUE;
1523             *resBase = matchingNode->base;
1524             *resLen = matchingNode->length;
1525         }
1526         else {
1527             nodeIsLocalized = RM_FALSE;
1528         }
1529     }
1531 exitLocalization:
1532     return (nodeIsLocalized);
1535 /* FUNCTION PURPOSE: Issues an allocator operation
1536  ***********************************************************************
1537  * DESCRIPTION: Issues an allocator preallocate, allocate, or free
1538  *              for an RM resource.
1539  */
1540 int32_t rmAllocatorOperation(Rm_Handle rmHandle, Rm_AllocatorOpInfo *opInfo)
1542     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1543     Rm_AllocatorNode *allocator = NULL;
1544     int32_t           resourceOffsetInPolicy;
1545     int32_t           retVal;
1546     
1547     resourceOffsetInPolicy = rmPolicyGetResourceOffset(opInfo->policy, opInfo->resourceInfo->name);
1548     allocator = rmAllocatorFind(rmHandle, opInfo->resourceInfo->name);
1549     
1550     if ((resourceOffsetInPolicy > 0) && allocator) {
1551         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1552             rmResourceTreeInv(allocator->resourceRoot);
1553         }
1555         if (opInfo->operation == Rm_allocatorOp_GET_STATUS) {
1556             retVal = allocatorStatus(rmHandle, allocator, opInfo);
1557         }
1558         else if ((opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) ||
1559                  (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE)) {
1560             retVal = allocatorPreAllocate(rmHandle, allocator, resourceOffsetInPolicy, opInfo);
1561         }               
1562         else if ((opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) ||
1563                  (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE)) {
1564             retVal = allocatorAllocate(rmHandle, allocator, resourceOffsetInPolicy, opInfo);
1565         }
1566         else if (opInfo->operation == Rm_allocatorOp_FREE) {
1567             retVal = allocatorFree(rmHandle, allocator, opInfo);
1568         } 
1570         if ((rmInst->instType == Rm_instType_SHARED_SERVER) &&
1571             (opInfo->operation != Rm_allocatorOp_GET_STATUS) &&
1572             (retVal == RM_SERVICE_APPROVED)) {
1573             rmResourceTreeWb(allocator->resourceRoot);
1574         }        
1575     }
1576     else {
1577         /* Resource could not be found in policy and/or allocator */
1578         retVal = RM_SERVICE_DENIED_RES_DOES_NOT_EXIST;
1579     }
1580     return(retVal);
1583 /* FUNCTION PURPOSE: Creates the allocator tree root
1584  ***********************************************************************
1585  * DESCRIPTION: Initializes a RM instance's allocator tree root entry
1586  */
1587 int32_t rmAllocatorInitTree(Rm_Handle rmHandle)
1589     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1590     Rm_AllocatorTree *root = NULL;
1591     int32_t           retVal = RM_OK;
1593     root = Rm_osalMalloc(sizeof(Rm_AllocatorTree));
1594     if (root) {
1595         RB_INIT(root);
1596         RM_SS_OBJ_WB(rmInst, root, Rm_AllocatorTree);
1598         if ((rmInst->instType == Rm_instType_SERVER) ||
1599             (rmInst->instType == Rm_instType_SHARED_SERVER)) {
1600             rmInst->u.server.allocatorTree = root;
1601         }
1602         else if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
1603             rmInst->u.cd.allocatorTree = root;
1604         }
1605     } else {
1606         retVal = RM_ERROR_COULD_NOT_INIT_ALLOC_TREE;
1607     }
1608     return(retVal);
1611 /* FUNCTION PURPOSE: Populates server allocator tree
1612  ***********************************************************************
1613  * DESCRIPTION: Creates and initializes a server instance's
1614  *              resource allocator tree using the GRL and, if
1615  *              provided, Linux DTB.
1616  */
1617 int32_t rmAllocatorPopulateTree(Rm_Handle rmHandle, void *globalResourceDtb,
1618                                 void *linuxDtb)
1620     int32_t                nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1621     int32_t                nodeDepth = RM_DTB_UTIL_STARTING_DEPTH;
1622     Rm_ResourceProperties  resProperties;
1623     int32_t                propOffset;
1624     int32_t                propertyLen;
1625     const char            *propertyName;
1626     const void            *propertyData;
1627     Rm_ResourcePropType    propertyType;
1628     int32_t                retVal = RM_OK;
1630     /* Parse the Global Resource List, creating an allocator for each
1631      * specified resource node */
1632     while ((nodeOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1633            (nodeDepth >= RM_DTB_UTIL_STARTING_DEPTH)) {
1634         memset((void *)&resProperties, 0, sizeof(resProperties));
1635         /* Get properties of resource node */
1636         propOffset = fdt_first_property_offset(globalResourceDtb, nodeOffset);
1637         while (propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) {
1638             propertyData = fdt_getprop_by_offset(globalResourceDtb, propOffset,
1639                                                  &propertyName, &propertyLen);
1640             propertyType = rmDtbUtilResGetPropertyType(propertyName);
1641             if (propertyType == Rm_resourcePropType_RESOURCE_RANGE) {
1642                 resProperties.rangeData = propertyData;
1643                 resProperties.rangeLen = propertyLen;
1644             }
1645             else if (propertyType == Rm_resourcePropType_NSASSIGNMENT) {
1646                 resProperties.nsAssignData = propertyData;
1647                 resProperties.nsAssignLen = propertyLen;
1648             }
1649             else if (propertyType == Rm_resourcePropType_RESOURCE_LINUX_ALIAS) {
1650                 resProperties.linuxAliasData = propertyData;
1651                 resProperties.linuxAliasLen = propertyLen;
1652             }
1653             else {
1654                 retVal = RM_ERROR_GRL_UNKNOWN_RESOURCE_PROPERTY;
1655                 goto exitAllocInit;
1656             }
1658             propOffset = fdt_next_property_offset(globalResourceDtb,
1659                                                   propOffset);
1660             if (propOffset == -FDT_ERR_NOTFOUND) {
1661                 /* No more resource properties but at least one found.  Extract
1662                  * the property values */
1663                 retVal = allocatorExtractGrlResProps(rmHandle,
1664                             fdt_get_name(globalResourceDtb, nodeOffset, NULL),
1665                             &resProperties, linuxDtb);
1666                 if (retVal < RM_OK) {
1667                     goto exitAllocInit;
1668                 }
1669             }
1670             else if (propOffset < -FDT_ERR_NOTFOUND) {
1671                 /* Error returned by LIBFDT */
1672                 retVal = propOffset;
1673                 goto exitAllocInit;
1674             }
1675         }
1676         if (propOffset < -FDT_ERR_NOTFOUND) {
1677             /* Error returned by LIBFDT */
1678             retVal = propOffset;
1679             goto exitAllocInit;
1680         }
1682         nodeOffset = fdt_next_node(globalResourceDtb, nodeOffset, &nodeDepth);
1683         if (nodeOffset < -FDT_ERR_NOTFOUND) {
1684             /* Error returned by LIBFDT */
1685             retVal = nodeOffset;
1686             goto exitAllocInit;
1687         }
1688     }
1690 exitAllocInit:
1691     return(retVal);
1694 /* FUNCTION PURPOSE: Deletes a node from a resource tree
1695  ***********************************************************************
1696  * DESCRIPTION: Deletes a node from an allocator's resource tree based on the
1697  *              given base and length.
1698  */
1699 void rmAllocatorDeleteResNode(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
1700                               int32_t resBase, uint32_t resLen)
1702     Rm_Inst         *rmInst = (Rm_Inst *)rmHandle;
1703     Rm_ResourceNode  find;
1704     Rm_ResourceNode *match;
1706     memset((void *)&find, 0, sizeof(find));
1707     find.base = resBase;
1708     find.length = resLen;
1709     match = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
1710                     &find);
1711     
1712     if (match) {
1713         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot,
1714                   match);
1715         rmResourceNodeFree(match);
1716         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1717             rmResourceTreeWb(allocator->resourceRoot);
1718         }
1719     }
1722 /* FUNCTION PURPOSE: Deletes an allocator's resource tree
1723  ***********************************************************************
1724  * DESCRIPTION: Deletes an allocator's resource tree based on the given
1725  *              resource name.
1726  */
1727 int32_t rmAllocatorDelete(Rm_Handle rmHandle, const char *resourceName)
1729     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1730     Rm_AllocatorTree *allocTree = rmAllocatorGetTree(rmHandle);
1731     Rm_AllocatorNode  find;
1732     Rm_AllocatorNode *match;
1733     Rm_ResourceTree  *resTree;
1734     Rm_ResourceNode  *resNode = NULL;
1735     Rm_ResourceNode  *nextResNode = NULL;
1736     int32_t           retVal = RM_OK;
1738     if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1739         rmAllocatorTreeInv(allocTree);
1740     }
1742     memset((void *)&find, 0, sizeof(find));
1743     rm_strncpy(find.resourceName, resourceName, RM_NAME_MAX_CHARS);
1744     match = RB_FIND(_Rm_AllocatorTree, allocTree, &find);
1746     if (match) {
1747         resTree = match->resourceRoot;
1749         /* Destroy resource tree */
1750         if (resTree) {
1751             for (resNode = RB_MIN(_Rm_AllocatorResourceTree, resTree);
1752                  resNode != NULL;
1753                  resNode = nextResNode) {
1754                 nextResNode = RB_NEXT(_Rm_AllocatorResourceTree, resTree,
1755                                       resNode);
1756                 RB_REMOVE(_Rm_AllocatorResourceTree, resTree, nextResNode);
1757                 rmResourceNodeFree(resNode);
1758             }
1759             Rm_osalFree((void *)resTree, sizeof(*resTree));
1760             match->resourceRoot = NULL;
1761             RM_SS_OBJ_WB(rmInst, match, Rm_AllocatorNode);
1762         }
1764         RB_REMOVE(_Rm_AllocatorTree, allocTree, match);
1765         rmAllocatorNodeFree(match);
1766         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1767             rmAllocatorTreeWb(allocTree);
1768         }
1769     }
1770     else {
1771         retVal = RM_ERROR_RES_ALLOCATOR_DOES_NOT_EXIST;
1772     }
1773     return (retVal);
1776 /* FUNCTION PURPOSE: Deletes allocator tree
1777  ***********************************************************************
1778  * DESCRIPTION: Removes all resource nodes for each allocator node and then
1779  *              deletes the allocator tree root.
1780  */
1781 void rmAllocatorDeleteTree(Rm_Handle rmHandle)
1783     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1784     Rm_AllocatorTree *allocTree = rmAllocatorGetTree(rmHandle);
1785     Rm_AllocatorNode *allocNode;
1786     Rm_AllocatorNode *nextAllocNode;
1787     Rm_ResourceTree  *resTree;
1788     Rm_ResourceNode  *resNode;
1789     Rm_ResourceNode  *nextResNode;
1791     if (allocTree) {
1792         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1793             rmAllocatorTreeInv(allocTree);
1794         }
1796         for (allocNode = RB_MIN(_Rm_AllocatorTree, allocTree);
1797              allocNode != NULL;
1798              allocNode = nextAllocNode) {
1799             nextAllocNode = RB_NEXT(_Rm_AllocatorTree, allocTree, allocNode);
1801             resTree = allocNode->resourceRoot;
1803             if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1804                 rmResourceTreeInv(resTree);
1805             }
1806             /* Delete each node in the resource tree */
1807             for (resNode = RB_MIN(_Rm_AllocatorResourceTree, resTree);
1808                  resNode != NULL;
1809                  resNode = nextResNode) {
1810                 nextResNode = RB_NEXT(_Rm_AllocatorResourceTree, resTree,
1811                                       resNode);
1812                 RB_REMOVE(_Rm_AllocatorResourceTree, resTree, resNode);
1813                 if (resNode->allocationCount) {
1814                     /* Delete all the owners in the resource's owner list */
1815                     allocatorResNodeOwnerClear(rmHandle, resNode);
1816                 }
1817                 rmResourceNodeFree(resNode);
1818             }
1819             Rm_osalFree((void *)resTree, sizeof(*resTree));
1821             RB_REMOVE(_Rm_AllocatorTree, allocTree, allocNode);
1822             rmAllocatorNodeFree(allocNode);
1823         }
1824         Rm_osalFree((void *)allocTree, sizeof(*allocTree));
1825         RM_SS_OBJ_WB(rmInst, rmInst, Rm_Inst);
1826     }