37c46b5c8c303329390860cd0a27ba77cade30c3
[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->resourceRootEntry, &findNode);
397     if (matchingNode) {
398         matchingEnd = matchingNode->base + matchingNode->length - 1;
399         findEnd = findNode.base + findNode.length - 1;
400         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {        
401             opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
402             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
403                                                                                   opInfo->serviceSrcInstNode);            
404             retVal = RM_SERVICE_APPROVED;
405         }
406         else {
407             retVal = RM_SERVICE_DENIED_PARTIAL_STATUS;
408         }
409     }
410     else {
411         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
412     }
414     return(retVal);  
417 /* FUNCTION PURPOSE: Preallocates an allocator resource
418  ***********************************************************************
419  * DESCRIPTION: Called when an allocate request is made but the base 
420  *              is unspecified.  The preallocation algorithm looks at 
421  *              available resources as well as policy permissions to 
422  *              determine a resource range that satisfies the request.
423  *              If a valid range is found it will be returned for the 
424  *              treeAllocate algorithm to handle.
425  */
426 static int32_t allocatorPreAllocate(Rm_Handle rmHandle,
427                                     Rm_AllocatorNode *allocator,
428                                     int32_t resourcePolicy,
429                                     Rm_AllocatorOpInfo *opInfo)
430 {   
431     Rm_Inst           *rmInst = (Rm_Inst *)rmHandle;
432     Rm_ResourceNode    findNode;
433     Rm_ResourceNode   *matchingNode = NULL;
434     Rm_ResourceNode   *nextNode;
435     uint32_t           matchingEnd;
436     uint32_t           findEnd;
437     uint32_t           rangeIndex;
438     int                resourceFound = RM_FALSE;
439     Rm_PolicyCheckType policyCheckType;
440     Rm_PolicyCheckCfg  policyCheckCfg;
441     int                nodePassesPolicy;
442     int32_t            retVal = RM_OK;
444     if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) {
445         policyCheckType = Rm_policyCheck_INIT;
446     }
447     else if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE) {
448         policyCheckType = Rm_policyCheck_USE;
449     }
450     else {
451         retVal = RM_ERROR_INVALID_SERVICE_TYPE;
452         return (retVal);
453     }
455     if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
456         /* Set base to first node's base since CD will not have all resources like Server */
457         matchingNode = RB_MIN(_Rm_AllocatorResourceTree, allocator->resourceRootEntry);
458         opInfo->resourceInfo->base = matchingNode->base;
459     }
460     else {
461         opInfo->resourceInfo->base = rmPolicyGetResourceBase(opInfo->policy, opInfo->serviceSrcInstNode, 
462                                                              resourcePolicy, policyCheckType, 
463                                                              &retVal);
464     }
465     
466     if (retVal != RM_OK) {
467         return (retVal);
468     }
470     if (opInfo->resourceInfo->alignment == RM_RESOURCE_ALIGNMENT_UNSPECIFIED) {  
471         /* Get alignment from policy */
472         opInfo->resourceInfo->alignment = rmPolicyGetResourceAlignment(opInfo->policy, resourcePolicy);
473     } 
475     if (opInfo->resourceInfo->alignment == 0) {
476         opInfo->resourceInfo->alignment = 1;
477     } 
479     memset((void *)&findNode, 0, sizeof(findNode));
480     findNode.base = opInfo->resourceInfo->base;
481     findNode.length = opInfo->resourceInfo->length;
483     /* Configure policy checking structure */
484     memset((void *)&policyCheckCfg, 0, sizeof(policyCheckCfg));
485     policyCheckCfg.policyDtb = opInfo->policy;
486     policyCheckCfg.resourceOffset = resourcePolicy;
487     
488     do {
489         matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, &findNode);
490         
491         if (matchingNode) {
492             matchingEnd = matchingNode->base + matchingNode->length - 1;
493             findEnd = findNode.base + findNode.length - 1;
494             nodePassesPolicy = RM_BOOL_UNDEF;
495             if ((matchingNode->allocationCount == 0) &&
496                 (findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
497                 /* Attempt to preallocate from node only if not owned by anyone and sits
498                  * within a matching node. */
499                 policyCheckCfg.type = policyCheckType;
500                 policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
501                 policyCheckCfg.resourceBase = findNode.base;
502                 policyCheckCfg.resourceLength = findNode.length;
503                 nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);    
504                 
505                 if (nodePassesPolicy && (matchingNode->allocationCount > 0)) {
506                     policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
507                     
508                     if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode, rmPolicyGetLinuxInstNode(rmHandle))) {
509                         /* Check if instance requesting resource has privileges to share
510                          * a resource already reserved by Linux */
511                         policyCheckCfg.type = Rm_policyCheck_SHARED_LINUX;
512                         nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
513                     }
515                     if (nodePassesPolicy) {
516                         /* Check exclusive privileges of instance requesting resource.  Requesting
517                          * instance with exclusive privileges can't reserve resource if already owned*/
518                         policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
519                         nodePassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
520                     }
521                 }
522                 
523                 if (nodePassesPolicy && (matchingNode->allocationCount == 1)) {
524                     /* Check exclusive privileges of instance that currently owns resource */
525                     policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
526                     policyCheckCfg.validInstNode = matchingNode->ownerList->instNameNode;
527                     nodePassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
528                 }
530                 if (retVal != RM_OK) {
531                     break;
532                 }
534                 if (nodePassesPolicy) {
535                     /* Initialize indexer to be first resource value that alignment satisfies */
536                     rangeIndex = findNode.base;
537                     if (rangeIndex % opInfo->resourceInfo->alignment) {
538                         rangeIndex += (opInfo->resourceInfo->alignment -
539                                       (rangeIndex % opInfo->resourceInfo->alignment));
540                     }
541                     
542                     if ((rangeIndex + opInfo->resourceInfo->length - 1) <= matchingEnd) {
543                         /* Block of unallocated resources within matchingNode that satisfies
544                          * allocate requirements */
545                         opInfo->resourceInfo->base = rangeIndex;
546                         resourceFound = RM_TRUE;
547                         retVal = RM_SERVICE_PROCESSING;
548                     }     
549                 }
550             }
551             
552             if (!resourceFound) {
553                 /* Check next resource node for available resources */
554                 if (findNode.base < matchingNode->base) {
555                     findNode.base = matchingNode->base;
556                 }
557                 else {
558                     if (!nodePassesPolicy) {
559                         findNode.base += findNode.length;
560                     }
561                     else {
562                         /* Matching node allocated, move to next node */
563                         if ((nextNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode))) {
564                             findNode.base = nextNode->base;
565                         }
566                         else {
567                             retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
568                         }
569                     }
570                 }
571             }
572         }
573         else {
574             retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
575         }
576     } while ((!resourceFound) && 
577              (retVal != RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET));
579     return(retVal); 
582 /* FUNCTION PURPOSE: Allocates an allocator resource
583  ***********************************************************************
584  * DESCRIPTION: Will attempt to allocate the resource with specified
585  *              base and length from the resource's allocator.  The
586  *              allocation algorithm will verify the allocation against
587  *              the policy permissions for the instance requesting the
588  *              allocation.  If the policy allows the allocation the 
589  *              algorithm will allocate the resource then combine any
590  *              resource nodes that may have become equivalent (in terms
591  *              of ownership) after the allocation.
592  */
593 static int32_t allocatorAllocate(Rm_Handle rmHandle,
594                                  Rm_AllocatorNode *allocator,
595                                  int32_t resourcePolicy,
596                                  Rm_AllocatorOpInfo *opInfo)
598     Rm_ResourceNode     findNode;
599     Rm_ResourceNode    *matchingNode = NULL;
600     Rm_ResourceNode    *leftNode = NULL;
601     Rm_ResourceNode    *rightNode = NULL;
602     Rm_PolicyCheckType  policyCheckType;
603     Rm_PolicyCheckCfg   policyCheckCfg;
604     int                 allocPassesPolicy;
605     int                 combineLeft = RM_FALSE;
606     int                 combineRight = RM_FALSE;
607     uint32_t            findEnd;
608     uint32_t            matchingEnd;
609     int32_t             retVal;
611     if (opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) {
612         policyCheckType = Rm_policyCheck_INIT;
613     }
614     else if (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE) {
615         policyCheckType = Rm_policyCheck_USE;
616     }
617     else {
618         retVal = RM_ERROR_INVALID_SERVICE_TYPE;
619         return (retVal);
620     }   
622     memset((void *)&findNode, 0, sizeof(findNode));
623     findNode.base = opInfo->resourceInfo->base;
624     findNode.length = opInfo->resourceInfo->length;
625     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, &findNode);
627     /* Prepare privilege checks */
628     memset((void *)&policyCheckCfg, 0, sizeof(policyCheckCfg)); 
630     if (matchingNode) {
631         findEnd = findNode.base + findNode.length - 1;
632         matchingEnd = matchingNode->base + matchingNode->length - 1;
633         
634         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
635             if (opInfo->serviceSrcInstNode == rmPolicyGetLinuxInstNode(rmHandle)) {
636                 /* Bypass policy checks since Linux Kernel has full privileges */
637                 allocPassesPolicy = RM_TRUE;
638             }
639             else {
640                 policyCheckCfg.policyDtb = opInfo->policy;
641                 policyCheckCfg.resourceOffset = resourcePolicy;    
642                 policyCheckCfg.type = policyCheckType;
643                 policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
644                 policyCheckCfg.resourceBase = findNode.base;
645                 policyCheckCfg.resourceLength = findNode.length;
646                 allocPassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
647                 if (!allocPassesPolicy) {
648                     if (policyCheckType == Rm_policyCheck_INIT) {
649                         retVal = RM_SERVICE_DENIED_INIT_PERM_NOT_GIVEN;
650                     }
651                     else {
652                         retVal = RM_SERVICE_DENIED_USE_PERM_NOT_GIVEN;
653                     }
654                 }
656                 if (!allocatorResNodeIsOwnedBy(rmHandle, matchingNode, opInfo->serviceSrcInstNode)) {
657                     if (allocPassesPolicy && (matchingNode->allocationCount > 0)) {
658                         if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode, rmPolicyGetLinuxInstNode(rmHandle))) {
659                             /* Check if instance requesting resource has privileges to share
660                              * a resource already reserved by Linux */
661                             policyCheckCfg.type = Rm_policyCheck_SHARED_LINUX;
662                             policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
663                             allocPassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
664                             if (!allocPassesPolicy) {
665                                 retVal = RM_SERVICE_DENIED_RES_NOT_SHARED_LINUX;
666                             }
667                         }
668                         if (allocPassesPolicy) {
669                             /* Check exclusive privileges of instance requesting resource.  Requesting
670                              * instance with exclusive privileges can't reserve resource if already owned*/
671                             policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
672                             policyCheckCfg.validInstNode = opInfo->serviceSrcInstNode;
673                             allocPassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
674                             if (!allocPassesPolicy) {
675                                 retVal = RM_SERVICE_DENIED_EXCLUSIVE_RES_ALLOCD;
676                             }
677                         }
678                     }
679                     if (allocPassesPolicy && (matchingNode->allocationCount == 1)) {
680                         /* Check exclusive privileges of instance that currently owns resource */
681                         policyCheckCfg.type = Rm_policyCheck_EXCLUSIVE;
682                         policyCheckCfg.validInstNode = matchingNode->ownerList->instNameNode;
683                         allocPassesPolicy = !rmPolicyCheckPrivilege(&policyCheckCfg, &retVal);
684                         if (!allocPassesPolicy) {
685                             retVal = RM_SERVICE_DENIED_ALLOCD_TO_EXCLUSIVE_INST;
686                         }                
687                     }  
688                 }
689             }
690             
691             if (allocPassesPolicy) {
692                 /* Handle any possible node combinations if requesting instance is
693                  * not already in resource's owner list.  Automatic approval if requesting
694                  * instance is already in owner list. */
695                 if ((findNode.base == matchingNode->base) && (findEnd == matchingEnd)) {
696                     /* findNode range matches matchingNode range
697                      *
698                      *   |<--left node-->||<--matched  node-->||<--right node-->| => existing node
699                      *                    |<--alloc request-->|  => requested resources
700                      */                     
701                     leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
702                     rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
703                     RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
704                     allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
706                     if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
707                         allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
708                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
709                         combineLeft = RM_TRUE;
710                     }
711                     if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
712                         allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
713                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
714                         combineRight = RM_TRUE;
715                     }
717                     if (combineLeft && combineRight) {
718                         /* Combine all three nodes into matchingNode */
719                         matchingNode->base = leftNode->base;
720                         matchingNode->length = leftNode->length + matchingNode->length + rightNode->length;
722                         allocatorResNodeOwnerClear(rmHandle, leftNode);
723                         rmResourceNodeFree(leftNode);
724                         allocatorResNodeOwnerClear(rmHandle, rightNode);
725                         rmResourceNodeFree(rightNode);                        
726                     }
727                     else if (combineLeft) {
728                         /* Combine left and matching nodes.  Reinsert right. */
729                         matchingNode->base = leftNode->base;
730                         matchingNode->length += leftNode->length;
732                         allocatorResNodeOwnerClear(rmHandle, leftNode);
733                         rmResourceNodeFree(leftNode);
734                         if (rightNode) {
735                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);  
736                         }
737                     }
738                     else if (combineRight) {
739                         /* Combine right and matching nodes.  Reinsert left. */
740                         matchingNode->length += rightNode->length;
742                         allocatorResNodeOwnerClear(rmHandle, rightNode);
743                         rmResourceNodeFree(rightNode);
744                         if (leftNode) {
745                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
746                         }
747                     }
748                     else {
749                         /* No combine. */
750                         if (leftNode) {
751                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
752                         }
753                         if (rightNode) {
754                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
755                         }
756                     }
758                     /* Always reinsert matchingNode */                
759                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
760                     
761                     /* Matching node contains new reference count after alloc.  Return new owner count
762                      * and originating instance allocation reference count. */
763                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
764                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
765                                                                                           opInfo->serviceSrcInstNode);
766                 }   
767                 else if ((findNode.base > matchingNode->base) && (findEnd < matchingEnd)) {
768                     /* findNode range is subset of matchingNode range and neither boundary is
769                      * equivalent.
770                      *
771                      * |<----------matched node---------->|
772                      *        |<---alloc request--->|
773                      */ 
774                     RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
775                     leftNode = rmResourceNodeNew(matchingNode->base, findNode.base - matchingNode->base);
776                     allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
777                     rightNode = rmResourceNodeNew(findNode.base + findNode.length, matchingEnd - findEnd);
778                     allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
780                     matchingNode->base = findNode.base;                                    
781                     matchingNode->length = findNode.length;
782                     allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
784                     /* Insert all the nodes */
785                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
786                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
787                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
788                     
789                     /* Matching node contains new reference count after alloc.  Return new owner count
790                      * and originating instance allocation reference count. */
791                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
792                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode, 
793                                                                                           opInfo->serviceSrcInstNode);
794                 }  
795                 else {    
796                     if (findNode.base == matchingNode->base) {
797                         /* findNode base and matchingNode base are equivalent.  May be combine
798                          * possibilities to the left
799                          *
800                          * |<---left node (alloc'd)--->||<----------matched node---------->|
801                          *                              |<---findNode (alloc req)--->|
802                          */                         
803                         leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
804                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
805                         /* Add allocating instance to owner list for compare with leftNode */
806                         allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
807                         
808                         if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
809                             allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
810                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
811                             /* Combine leftNode and findNode */
812                             leftNode->length += findNode.length;
813                         }
814                         else {
815                             leftNode = rmResourceNodeNew(findNode.base, findNode.length);
816                             allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
817                         }
819                         /* Account for leftNode in matchingNode */
820                         matchingNode->base = findNode.base + findNode.length;
821                         matchingNode->length = matchingEnd - findEnd;  
823                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
824                         /* Left node contains new reference count after alloc.  Return new owner count
825                          * and originating instance allocation reference count. */
826                         opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
827                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, leftNode, 
828                                                                                               opInfo->serviceSrcInstNode);
829                     }
830                     else if (findEnd == matchingEnd) {
831                         /* findNode end and matchingNode end are equivalent.  May be combine
832                          * possibilities to the right
833                          *
834                          * |<----------matched node---------->||<---right node (alloc'd)--->|
835                          *       |<---findNode (alloc req)--->|
836                          */                        
837                         rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
838                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
839                         /* Add allocating instance to owner list for compare with rightNode */
840                         allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
841                         
842                         if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
843                             allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
844                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
845                             /* Combine rightNode and findNode */
846                             rightNode->base = findNode.base;
847                             rightNode->length += findNode.length;
848                         }
849                         else {
850                             rightNode = rmResourceNodeNew(findNode.base, findNode.length);
851                             allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
852                         }
854                         /* Account for rightNode in matchingNode */
855                         matchingNode->length -= findNode.length;  
857                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
858                         /* Right node contains new reference count after alloc.  Return new owner count
859                          * and originating instance allocation reference count. */
860                         opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
861                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, rightNode, 
862                                                                                               opInfo->serviceSrcInstNode);
863                     }
864                     /* Remove allocating instance from leftover matchingNode */
865                     allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
866                     RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
867                 }
868                 retVal = RM_SERVICE_APPROVED;
869             }
870         }
871         else {
872             retVal = RM_SERVICE_DENIED_PARTIAL_ALLOCATION;
873         }
874     }
875     else {
876         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
877     }
879     return(retVal);        
882 /* FUNCTION PURPOSE: Frees an allocator resource
883  ***********************************************************************
884  * DESCRIPTION: Will attempt to free the resource with specified
885  *              base and length from the resource's allocator.  The
886  *              free algorithm will verify the free request parameters
887  *              match an allocated range for the resource and that the
888  *              range is owned by the instance requesting the free. If
889  *              the free is validated the algorithm will free the 
890  *              resource then combine any resource nodes that may have
891  *              become equivalent (in terms of ownership) after the
892  *              allocation.
893  */
894 static int32_t allocatorFree(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
895                              Rm_AllocatorOpInfo *opInfo)
897     Rm_ResourceNode  findNode;
898     Rm_ResourceNode *matchingNode = NULL;
899     Rm_ResourceNode *leftNode = NULL;
900     Rm_ResourceNode *rightNode = NULL;
901     int              combineLeft = RM_FALSE;
902     int              combineRight = RM_FALSE;
903     uint32_t         findEnd;
904     uint32_t         matchingEnd;
905     int32_t          retVal;
907     memset((void *)&findNode, 0, sizeof(findNode));
908     findNode.base = opInfo->resourceInfo->base;
909     findNode.length = opInfo->resourceInfo->length;
910     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, &findNode);
912     if (matchingNode) {
913         findEnd = findNode.base + findNode.length - 1;
914         matchingEnd = matchingNode->base + matchingNode->length - 1;
915         
916         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {  
917             if (matchingNode->allocationCount) {
918                 if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode, opInfo->serviceSrcInstNode)) {
919                     if ((findNode.base == matchingNode->base) && (findEnd == matchingEnd))
920                     {
921                         /* Case 1: Free range equals allocated matched node exactly. Attempt to combine 
922                          *         freed node with nodes to left and right.
923                          *
924                          * |<--left node-->||<---matched node--->||<--right node-->|
925                          *                  |<---free request--->|
926                          */ 
927                         leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
928                         rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
929                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
930                         allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
932                         if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
933                             allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
934                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
935                             combineLeft = RM_TRUE;
936                         }
937                         if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
938                             allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
939                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
940                             combineRight = RM_TRUE;
941                         }
943                         if (combineLeft && combineRight) {
944                             /* Combine all three nodes into matchingNode */
945                             matchingNode->base = leftNode->base;
946                             matchingNode->length = leftNode->length + matchingNode->length + rightNode->length;
948                             allocatorResNodeOwnerClear(rmHandle, leftNode);
949                             rmResourceNodeFree(leftNode);
950                             allocatorResNodeOwnerClear(rmHandle, rightNode);
951                             rmResourceNodeFree(rightNode);                        
952                         }
953                         else if (combineLeft) {
954                             /* Combine left and matching nodes.  Reinsert right. */
955                             matchingNode->base = leftNode->base;
956                             matchingNode->length += leftNode->length;
958                             allocatorResNodeOwnerClear(rmHandle, leftNode);
959                             rmResourceNodeFree(leftNode);
960                             if (rightNode) {
961                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode); 
962                             }
963                         }
964                         else if (combineRight) {
965                             /* Combine right and matching nodes.  Reinsert left. */
966                             matchingNode->length += rightNode->length;
968                             allocatorResNodeOwnerClear(rmHandle, rightNode);
969                             rmResourceNodeFree(rightNode);
970                             if (leftNode) {
971                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
972                             }
973                         }
974                         else {
975                             /* No combine. */
976                             if (leftNode) {
977                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
978                             }
979                             if (rightNode) {
980                                 RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
981                             }
982                         }
984                         /* Always reinsert matchingNode */
985                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
986                         
987                         /* Matching node is what remains after free.  Return remaining owner count
988                          * and originating instance allocation reference count. */
989                         opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
990                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
991                                                                                               opInfo->serviceSrcInstNode);
992                     }
993                     else if ((findNode.base > matchingNode->base) && (findEnd < matchingEnd)) {
994                         /* Case 2: Free range is less than range in matched node. Split
995                          *         matched node into three nodes.
996                          *
997                          * |<----------matched node---------->|
998                          *        |<---free request--->|
999                          *
1000                          * Remove instance from owner list then add it back in for side nodes for
1001                          * proper accounting of allocations in validInstance list
1002                          */ 
1003                         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1004                         allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1005                         
1006                         leftNode = rmResourceNodeNew(matchingNode->base, findNode.base - matchingNode->base);
1007                         allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
1008                         allocatorResNodeOwnerAdd(rmHandle, leftNode, opInfo->serviceSrcInstNode);
1009                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
1010                         
1011                         rightNode = rmResourceNodeNew(findNode.base + findNode.length, matchingEnd - findEnd);
1012                         allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
1013                         allocatorResNodeOwnerAdd(rmHandle, rightNode, opInfo->serviceSrcInstNode);
1014                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
1016                         matchingNode->base = findNode.base;                                    
1017                         matchingNode->length = findNode.length;
1018                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1019                         
1020                         /* Matching node is what remains after free.  Return remaining owner count
1021                          * and originating instance allocation reference count. */
1022                         opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1023                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
1024                                                                                               opInfo->serviceSrcInstNode);
1025                     }
1026                     else {                        
1027                         if (findNode.base == matchingNode->base) {
1028                             /* Case 3: Free range is on left boundary of matched node. Try to 
1029                              *         combine free range with left node.
1030                              *
1031                              * |<---left node (free)--->||<----------matched node---------->|
1032                              *                           |<---findNode (free req)--->|
1033                              */ 
1035                             leftNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1036                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1037                             /* Remove freeing instance from owner list for compare with leftNode */
1038                             allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1039                             
1040                             if (leftNode && allocatorResNodeOwnerCompare(rmHandle, leftNode, matchingNode) &&
1041                                 allocatorResNodeBoundaryCompare(leftNode, matchingNode)) {
1042                                 RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
1043                                 /* Combine leftNode and findNode */
1044                                 leftNode->length += findNode.length;
1045                             }
1046                             else {
1047                                 leftNode = rmResourceNodeNew(findNode.base, findNode.length);
1048                                 allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
1049                             }
1051                             /* Remove leftNode range from matchingNode */
1052                             matchingNode->base = findNode.base + findNode.length;
1053                             matchingNode->length = matchingEnd - findEnd;  
1054                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, leftNode);
1055                             
1056                             /* Left node is what remains after free.  Return remaining owner count
1057                              * and originating instance allocation reference count. */
1058                             opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
1059                             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, leftNode,
1060                                                                                                   opInfo->serviceSrcInstNode);
1061                         }
1062                         else if (findEnd == matchingEnd) {
1063                             /* Case 4: Free range is on right boundary of matched node. Try to 
1064                              *         combine free range with right node.
1065                              *
1066                              * |<----------matched node---------->||<---right node (free)--->|
1067                              *        |<---findNode (free req)--->|
1068                              */ 
1069                             
1070                             rightNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1071                             RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode); 
1072                             /* Remove freeing instance from owner list for compare with rightNode */
1073                             allocatorResNodeOwnerDelete(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1074                             
1075                             if (rightNode && allocatorResNodeOwnerCompare(rmHandle, rightNode, matchingNode) &&
1076                                 allocatorResNodeBoundaryCompare(rightNode, matchingNode)) {
1077                                 RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
1078                                 /* Combine rightNode and findNode */
1079                                 rightNode->base = findNode.base;
1080                                 rightNode->length += findNode.length;
1081                             }
1082                             else {
1083                                 rightNode = rmResourceNodeNew(findNode.base, findNode.length);
1084                                 allocatorResNodeOwnerCopy(rmHandle, rightNode, matchingNode);
1085                             }
1087                             /* Remove rightNode range from matchingNode */
1088                             matchingNode->length -= findNode.length;  
1089                             RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, rightNode);
1090                             
1091                             /* Right node is what remains after free.  Return remaining owner count
1092                              * and originating instance allocation reference count. */
1093                             opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
1094                             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, rightNode,
1095                                                                                                   opInfo->serviceSrcInstNode);
1096                         }
1098                         /* Add freeing instance back into matchingNode allocations */
1099                         allocatorResNodeOwnerAdd(rmHandle, matchingNode, opInfo->serviceSrcInstNode);
1100                         RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1101                     }
1102                     retVal = RM_SERVICE_APPROVED;
1103                 }
1104                 else {
1105                     /* Return owner count and instance alloc count.  In case it's a reference count
1106                      * check in application */
1107                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1108                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
1109                                                                                           opInfo->serviceSrcInstNode);
1110                     retVal = RM_SERVICE_DENIED_RES_NOT_ALLOCD_TO_INST;
1111                 }
1112             }
1113             else {
1114                 /* Return owner count and instance alloc count.  In case it's a reference count
1115                  * check in application */
1116                 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1117                 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle, matchingNode,
1118                                                                                       opInfo->serviceSrcInstNode);
1119                 retVal = RM_SERVICE_DENIED_RES_ALREADY_FREE;
1120             }
1121         }
1122         else {
1123             retVal = RM_SERVICE_DENIED_PARTIAL_FREE;
1124         }
1125     }
1126     else {
1127         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
1128     }
1129     return(retVal);  
1132 /* FUNCTION PURPOSE: Reserves a Linux resource
1133  ***********************************************************************
1134  * DESCRIPTION: Reserves resources for Linux using the base and length
1135  *              values retrieved from the Linux DTB via the
1136  *              "linux-dtb-alias" properties within the GRL.
1137  */
1138 static int32_t allocatorReserveLinuxResource(Rm_Handle rmHandle, Rm_LinuxAlias *linuxAlias, 
1139                                              Rm_LinuxValueRange *linuxValues, Rm_AllocatorOpInfo *opInfo)
1141     int32_t   retVal = RM_OK;
1142     int       baseFound = RM_FALSE;
1143     int       lengthFound = RM_FALSE;
1144     uint32_t  valueIndex = 0;
1146     while ((linuxValues) && (!baseFound || !lengthFound)) {
1147         if (linuxAlias->baseOffset == valueIndex) {
1148             opInfo->resourceInfo->base = linuxValues->value;
1149             baseFound = RM_TRUE;
1151             if (linuxAlias->lengthOffset == RM_DTB_UTIL_LINUX_ALIAS_OFFSET_NOT_SET) {
1152                 opInfo->resourceInfo->length = 1;
1153                 lengthFound = RM_TRUE;
1154             }
1155         }
1156         else if (linuxAlias->lengthOffset == valueIndex) {
1157             opInfo->resourceInfo->length = linuxValues->value;
1158             lengthFound = RM_TRUE;
1159         }
1161         linuxValues = (Rm_LinuxValueRange *)linuxValues->nextValue;
1162         valueIndex++;
1163     }
1165     if (!baseFound || !lengthFound) {
1166         retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1167     }
1168     else {
1169         /* Allocate resource to Linux */
1170         retVal = rmAllocatorOperation(rmHandle, opInfo);
1171         if (retVal == RM_SERVICE_APPROVED) {
1172             retVal = RM_OK;
1173         }
1174     }
1175     return (retVal);
1178 /* FUNCTION PURPOSE: Finds and reserves Linux resources
1179  ***********************************************************************
1180  * DESCRIPTION: Parses the Linux DTB for resources consumed by the
1181  *              Linux kernel.  If the resource is found via the
1182  *              "linux-dtb-alias" property defined in the GRL it is 
1183  *              reserved.
1184  */
1185 static int32_t allocatorFindLinuxResource(Rm_Handle rmHandle, const char *resourceName, void *linuxDtb, 
1186                                           Rm_LinuxAlias *linuxAlias)
1188     Rm_Inst            *rmInst = (Rm_Inst *)rmHandle;
1189     Rm_AllocatorOpInfo  opInfo;
1190     Rm_ResourceInfo     resourceInfo;
1191     uint32_t            pathOffset;
1192     uint32_t            pathSize;
1193     char               *tempAliasPath;
1194     char               *spacePtr;
1195     int32_t             propOffset;
1196     int32_t             nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1197     int32_t             prevDepth = RM_DTB_UTIL_STARTING_DEPTH;
1198     int32_t             depth = RM_DTB_UTIL_STARTING_DEPTH;
1199     int32_t             propertyLen;
1200     const char         *propertyName;
1201     const void         *propertyData; 
1202     Rm_LinuxValueRange *linuxValueRange;
1203     int32_t             retVal = RM_OK; 
1205     memset((void *)&opInfo, 0, sizeof(opInfo));
1206     memset((void *)&resourceInfo, 0, sizeof(resourceInfo));
1208     rm_strncpy(resourceInfo.name, resourceName, RM_NAME_MAX_CHARS);
1209     opInfo.policy = rmInst->u.server.globalPolicy;
1210     opInfo.serviceSrcInstNode = rmPolicyGetLinuxInstNode(rmHandle);
1211     opInfo.operation = Rm_allocatorOp_ALLOCATE_INIT;
1212     opInfo.resourceInfo = &resourceInfo;    
1214     while(linuxAlias) {
1215         /* Reset parsing variables */
1216         pathOffset = 0;
1217         pathSize = strlen(linuxAlias->path) + 1;
1218         tempAliasPath = Rm_osalMalloc(pathSize);
1219         rm_strncpy(tempAliasPath, linuxAlias->path, pathSize);
1220         nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1221         prevDepth = RM_DTB_UTIL_STARTING_DEPTH;   
1222         resourceInfo.base = 0;
1223         resourceInfo.length = 0;
1225         spacePtr = strpbrk(tempAliasPath, " ");
1226         if (spacePtr) {
1227             *spacePtr = '\0';
1228         }       
1229         
1230         while(pathOffset < pathSize) {
1231             /* Move through DTB nodes until next alias path node found */
1232             if (strcmp(tempAliasPath + pathOffset, fdt_get_name(linuxDtb, nodeOffset, NULL))) {
1233                 nodeOffset = fdt_next_node(linuxDtb, nodeOffset, &depth);
1235                 if ((depth < prevDepth) || (nodeOffset == -FDT_ERR_NOTFOUND)) {
1236                     /* Returning from subnode that matched part of alias path without finding
1237                      * resource values */
1238                     retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1239                     break;
1240                 }
1241             }
1242             else {
1243                 /* Found next alias path node.  Move to next node name in path string. */
1244                 pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1245                 spacePtr = strpbrk(tempAliasPath + pathOffset, " ");
1246                 if (spacePtr) {
1247                     *spacePtr = '\0';
1248                 }       
1249                 
1250                 prevDepth = fdt_node_depth(linuxDtb, nodeOffset);
1251                 propOffset = fdt_first_property_offset(linuxDtb, nodeOffset);
1252                 while ((propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1253                        (pathOffset < pathSize)) {
1254                     propertyData = fdt_getprop_by_offset(linuxDtb, propOffset, 
1255                                                          &propertyName, &propertyLen);
1257                     if (strcmp(tempAliasPath + pathOffset, propertyName) == 0) {
1258                         /* Found resource at end of alias path */
1259                         pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1260                         linuxValueRange = rmDtbUtilLinuxExtractValues(propertyData, propertyLen);
1261                         retVal = allocatorReserveLinuxResource(rmHandle, linuxAlias, 
1262                                                                linuxValueRange, &opInfo);
1263                         rmDtbUtilLinuxFreeValues(linuxValueRange);
1264                     }
1265                     propOffset = fdt_next_property_offset(linuxDtb, propOffset);
1266                 } 
1268                 if (propOffset < -FDT_ERR_NOTFOUND) {
1269                     retVal = propOffset;
1270                     break;
1271                 }
1272             }
1273         }
1274         
1275         Rm_osalFree(tempAliasPath, pathSize);
1276         if (retVal < RM_OK) {
1277             break;
1278         }
1279         linuxAlias = linuxAlias->nextLinuxAlias;
1280     }
1281     return (retVal);
1284 /* FUNCTION PURPOSE: Creates and initializes a resource allocator
1285  ***********************************************************************
1286  * DESCRIPTION: Creates a resource allocator for the provided
1287  *              resource name and resource properties retrieved
1288  *              from the GRL.  Resources will be reserved for 
1289  *              the Linux kernel if the Linux DTB is provided
1290  *              and there are "linux-dtb-alias" properties
1291  *              specified in the GRL.
1292  */
1293 static int32_t allocatorExtractGrlResProps(Rm_Handle rmHandle,
1294                                            const char *resourceName,
1295                                            Rm_ResourceProperties *resProps,
1296                                            void *linuxDtb)
1298     Rm_Inst             *rmInst = (Rm_Inst *)rmHandle;
1299     Rm_ResourceRange    *range = NULL;
1300     Rm_ResourceRange    *rangeBasePtr = NULL;
1301     Rm_NsAssignment     *nsAssignments = NULL;
1302     Rm_NsAssignment     *nsAssignmentBasePtr = NULL;
1303     Rm_LinuxAlias       *linuxAlias = NULL;
1304     Rm_NameServerObjCfg  nameServerObjCfg;
1305     int32_t              retVal = RM_OK;
1306     
1307     if ((strlen(resourceName) + 1) > RM_NAME_MAX_CHARS) {
1308         retVal = RM_ERROR_RESOURCE_NAME_TOO_LONG;
1309         return(retVal);
1310     }
1312     if (resProps->rangeData && (resProps->rangeLen > 0)) {
1313         range = rangeBasePtr = rmDtbUtilResExtractRange(resProps->rangeData,
1314                                                         resProps->rangeLen);
1316         if ((retVal = rmAllocatorCreate(rmHandle, resourceName, range)) >= RM_OK) {
1317             if (resProps->linuxAliasData && resProps->linuxAliasLen) {
1318                 if (linuxDtb) {
1319                     linuxAlias = rmDtbUtilResExtractLinuxAlias(resProps->linuxAliasData,
1320                                                                resProps->linuxAliasLen, &retVal);
1321                     if (linuxAlias) {
1322                         retVal = allocatorFindLinuxResource(rmHandle, resourceName, linuxDtb, linuxAlias);            
1323                     }
1324                 }
1325             }
1326         }
1327     }
1328     
1329     if (retVal >= RM_OK) {
1330         if (resProps->nsAssignData && resProps->nsAssignLen) {
1331             nsAssignments = rmDtbUtilResExtractNsAssignment(resProps->nsAssignData, 
1332                                                             resProps->nsAssignLen, &retVal);
1333             if (nsAssignments) {
1334                 nsAssignmentBasePtr = nsAssignments;
1335                 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1336                     rmNameServerTreeInv(rmInst->u.server.nameServer);
1337                 }                  
1338                 while (nsAssignments) {
1339                     memset((void *)&nameServerObjCfg, 0, sizeof(nameServerObjCfg));
1340                     nameServerObjCfg.nameServerTree = rmInst->u.server.nameServer;
1341                     nameServerObjCfg.nodeCfg.objName = nsAssignments->nsName;
1342                     nameServerObjCfg.nodeCfg.resourceName = (char *)resourceName;
1343                     nameServerObjCfg.nodeCfg.resourceBase= nsAssignments->resourceBase;
1344                     nameServerObjCfg.nodeCfg.resourceLength = nsAssignments->resourceLength;                
1345                     rmNameServerAddObject(&nameServerObjCfg);
1346                     nsAssignments = nsAssignments->nextNsAssignment;
1347                 }
1348                 if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1349                     rmNameServerTreeWb(rmInst->u.server.nameServer);
1350                 }                
1351                 rmDtbUtilResFreeNsAssignmentList(nsAssignmentBasePtr);
1352             }
1353         }
1354     }
1355     else if (retVal != RM_ERROR_COULD_NOT_CREATE_NEW_ALLOCATOR) {
1356         rmAllocatorDelete(rmHandle, resourceName);
1357     }
1359     rmDtbUtilResFreeRange(rangeBasePtr);
1360     if (linuxAlias) {
1361         rmDtbUtilResFreeLinuxAlias(linuxAlias);
1362     }
1363     return(retVal);
1366 /**********************************************************************
1367  ********************** Internal Functions ****************************
1368  **********************************************************************/
1370 /* FUNCTION PURPOSE: Creates a new allocator
1371  ***********************************************************************
1372  * DESCRIPTION: Creates a new allocator and its resource tree
1373  *              using the provided resource name and value range.  The
1374  *              name and value originate from the GRL.
1375  */
1376 int32_t rmAllocatorCreate(Rm_Handle rmHandle, const char *resourceName,
1377                           Rm_ResourceRange *range)
1379     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1380     Rm_AllocatorTree *allocTree   = rmAllocatorGetTree(rmHandle);
1381     Rm_AllocatorNode *newAllocNode = NULL;
1382     Rm_ResourceTree  *resTree = NULL;
1383     Rm_ResourceNode  *resNode = NULL;
1385     newAllocNode = rmAllocatorNodeNew(resourceName);
1386     if (newAllocNode) {
1387         resTree = Rm_osalMalloc(sizeof(*resTree));
1388         RB_INIT(resTree);
1390         while (range != NULL) {
1391             resNode = rmResourceNodeNew(range->base, range->length);
1392             RB_INSERT(_Rm_AllocatorResourceTree, resTree, resNode);
1393             range = range->nextRange;
1394         }
1395         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1396             rmResourceTreeWb(resTree);
1397         }
1399         newAllocNode->resourceRootEntry = resTree;
1400         RM_SS_OBJ_WB(rmInst, newAllocNode, Rm_AllocatorNode);
1402         RB_INSERT(_Rm_AllocatorTree, allocTree, newAllocNode);
1403         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1404             rmAllocatorTreeWb(allocTree);
1405         }
1406     }
1407     else {
1408         return(RM_ERROR_COULD_NOT_CREATE_NEW_ALLOCATOR);
1409     }
1411     return(RM_OK);
1414 /* FUNCTION PURPOSE: Returns a pointer to the allocator tree
1415  ***********************************************************************
1416  * DESCRIPTION: Returns a pointer to the instance's allocator tree
1417  *              based on the instance type
1418  */
1419 Rm_AllocatorTree *rmAllocatorGetTree(Rm_Handle rmHandle)
1421     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1422     Rm_AllocatorTree *tree = NULL;
1424     if ((rmInst->instType == Rm_instType_SERVER) ||
1425         (rmInst->instType == Rm_instType_SHARED_SERVER)) {
1426         tree = rmInst->u.server.allocatorTree;
1427     }
1428     else if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
1429         tree = rmInst->u.cd.allocatorTree;
1430     }
1431     return(tree);
1434 /* FUNCTION PURPOSE: Finds an allocator
1435  ***********************************************************************
1436  * DESCRIPTION: Returns a pointer to an allocator that matches the 
1437  *              provided resource name.
1438  */
1439 Rm_AllocatorNode *rmAllocatorFind(Rm_Handle rmHandle, const char *resourceName)
1441     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1442     Rm_AllocatorTree *tree = rmAllocatorGetTree(rmHandle);
1443     Rm_AllocatorNode  findNode;
1445     if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1446         rmAllocatorTreeInv(tree);
1447     }
1449     memset((void *)&findNode, 0, sizeof(Rm_AllocatorNode));
1450     rm_strncpy(findNode.resourceName, resourceName, RM_NAME_MAX_CHARS);
1452     return(RB_FIND(_Rm_AllocatorTree, tree, &findNode));
1455 /* FUNCTION PURPOSE: Checks if a resource node is localized
1456  ***********************************************************************
1457  * DESCRIPTION: Checks if a resource node is localized.  A localized
1458  *              node is one that is free and has no neighboring nodes
1459  *              or neighboring nodes that do not have resource values
1460  *              contiguous with the node being checked.  The function
1461  *              will return RM_TRUE if the node is localized.  
1462  *              Otherwise, the function returns RM_FALSE
1463  */
1464 int rmAllocatorGetNodeLocalization(Rm_Handle rmHandle, char *resourceName,
1465                                    int32_t *resBase, uint32_t *resLen)
1467     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1468     void             *policy = NULL;
1469     int32_t           resOffsetInPolicy;
1470     uint32_t          allocSize;
1471     Rm_AllocatorNode *allocator = NULL;
1472     Rm_ResourceNode   findNode;
1473     Rm_ResourceNode  *matchingNode = NULL;
1474     Rm_ResourceNode  *neighborNode = NULL;
1475     int               nodeIsLocalized = RM_FALSE;
1477     policy = rmPolicyGetPolicy((Rm_Handle)rmInst);
1478     resOffsetInPolicy = rmPolicyGetResourceOffset(policy,resourceName);
1479     allocSize = rmPolicyGetResourceCdAllocSize(policy, resOffsetInPolicy);
1480     allocator = rmAllocatorFind(rmHandle, resourceName);
1482     /* Nothing to free back to server if policy never specified blocks could be allocated
1483      * to CD */
1484     if (allocSize) {
1485         memset((void *)&findNode, 0, sizeof(findNode));
1486         findNode.base = *resBase;
1487         findNode.length = *resLen;
1488         matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, &findNode);
1490         if (matchingNode) {
1491             /* Node can be freed back to Server from CD if:
1492              * - allocationCount == 0
1493              * - node's resource range is multiple of policy allocation size
1494              * - node's resource range boundaries are not contiguous with surrounding nodes */
1495             if (matchingNode->allocationCount) {
1496                 goto exitLocalization;
1497             }
1498                 
1499             if (matchingNode->length % allocSize) {
1500                 goto exitLocalization;        
1501             }
1503             /* Check left neighbor */
1504             neighborNode = RB_PREV(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1505             if (neighborNode && allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1506                 goto exitLocalization; 
1507             }
1509             /* Check right neighbor */
1510             neighborNode = RB_NEXT(_Rm_AllocatorResourceTree, allocator->resourceRootEntry, matchingNode);
1511             if (neighborNode && allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1512                 goto exitLocalization; 
1513             }
1515             /* All localization checks passed.  Return the base and length of localized node. */
1516             nodeIsLocalized = RM_TRUE;
1517             *resBase = matchingNode->base;
1518             *resLen = matchingNode->length;
1519         }
1520         else {
1521             nodeIsLocalized = RM_FALSE;
1522         }
1523     }
1525 exitLocalization:
1526     return (nodeIsLocalized);
1529 /* FUNCTION PURPOSE: Issues an allocator operation
1530  ***********************************************************************
1531  * DESCRIPTION: Issues an allocator preallocate, allocate, or free
1532  *              for an RM resource.
1533  */
1534 int32_t rmAllocatorOperation(Rm_Handle rmHandle, Rm_AllocatorOpInfo *opInfo)
1536     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1537     Rm_AllocatorNode *allocator = NULL;
1538     int32_t           resourceOffsetInPolicy;
1539     int32_t           retVal;
1540     
1541     resourceOffsetInPolicy = rmPolicyGetResourceOffset(opInfo->policy, opInfo->resourceInfo->name);
1542     allocator = rmAllocatorFind(rmHandle, opInfo->resourceInfo->name);
1543     
1544     if ((resourceOffsetInPolicy > 0) && allocator) {
1545         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1546             rmResourceTreeInv(allocator->resourceRootEntry);
1547         }
1549         if (opInfo->operation == Rm_allocatorOp_GET_STATUS) {
1550             retVal = allocatorStatus(rmHandle, allocator, opInfo);
1551         }
1552         else if ((opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) ||
1553                  (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE)) {
1554             retVal = allocatorPreAllocate(rmHandle, allocator, resourceOffsetInPolicy, opInfo);
1555         }               
1556         else if ((opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) ||
1557                  (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE)) {
1558             retVal = allocatorAllocate(rmHandle, allocator, resourceOffsetInPolicy, opInfo);
1559         }
1560         else if (opInfo->operation == Rm_allocatorOp_FREE) {
1561             retVal = allocatorFree(rmHandle, allocator, opInfo);
1562         } 
1564         if ((rmInst->instType == Rm_instType_SHARED_SERVER) &&
1565             (opInfo->operation != Rm_allocatorOp_GET_STATUS) &&
1566             (retVal == RM_SERVICE_APPROVED)) {
1567             rmResourceTreeWb(allocator->resourceRootEntry);
1568         }        
1569     }
1570     else {
1571         /* Resource could not be found in policy and/or allocator */
1572         retVal = RM_SERVICE_DENIED_RES_DOES_NOT_EXIST;
1573     }
1574     return(retVal);
1577 /* FUNCTION PURPOSE: Creates the allocator tree root
1578  ***********************************************************************
1579  * DESCRIPTION: Initializes a RM instance's allocator tree root entry
1580  */
1581 int32_t rmAllocatorInitTree(Rm_Handle rmHandle)
1583     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1584     Rm_AllocatorTree *root = NULL;
1585     int32_t           retVal = RM_OK;
1587     root = Rm_osalMalloc(sizeof(Rm_AllocatorTree));
1588     if (root) {
1589         RB_INIT(root);
1590         RM_SS_OBJ_WB(rmInst, root, Rm_AllocatorTree);
1592         if ((rmInst->instType == Rm_instType_SERVER) ||
1593             (rmInst->instType == Rm_instType_SHARED_SERVER)) {
1594             rmInst->u.server.allocatorTree = root;
1595         }
1596         else if (rmInst->instType == Rm_instType_CLIENT_DELEGATE) {
1597             rmInst->u.cd.allocatorTree = root;
1598         }
1599     } else {
1600         retVal = RM_ERROR_COULD_NOT_INIT_ALLOC_TREE;
1601     }
1602     return(retVal);
1605 /* FUNCTION PURPOSE: Populates server allocator tree
1606  ***********************************************************************
1607  * DESCRIPTION: Creates and initializes a server instance's
1608  *              resource allocator tree using the GRL and, if
1609  *              provided, Linux DTB.
1610  */
1611 int32_t rmAllocatorPopulateTree(Rm_Handle rmHandle, void *globalResourceDtb,
1612                                 void *linuxDtb)
1614     int32_t                nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1615     int32_t                nodeDepth = RM_DTB_UTIL_STARTING_DEPTH;
1616     Rm_ResourceProperties  resProperties;
1617     int32_t                propOffset;
1618     int32_t                propertyLen;
1619     const char            *propertyName;
1620     const void            *propertyData;
1621     Rm_ResourcePropType    propertyType;
1622     int32_t                retVal = RM_OK;
1624     /* Parse the Global Resource List, creating an allocator for each
1625      * specified resource node */
1626     while ((nodeOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1627            (nodeDepth >= RM_DTB_UTIL_STARTING_DEPTH)) {
1628         memset((void *)&resProperties, 0, sizeof(resProperties));
1629         /* Get properties of resource node */
1630         propOffset = fdt_first_property_offset(globalResourceDtb, nodeOffset);
1631         while (propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) {
1632             propertyData = fdt_getprop_by_offset(globalResourceDtb, propOffset,
1633                                                  &propertyName, &propertyLen);
1634             propertyType = rmDtbUtilResGetPropertyType(propertyName);
1635             if (propertyType == Rm_resourcePropType_RESOURCE_RANGE) {
1636                 resProperties.rangeData = propertyData;
1637                 resProperties.rangeLen = propertyLen;
1638             }
1639             else if (propertyType == Rm_resourcePropType_NSASSIGNMENT) {
1640                 resProperties.nsAssignData = propertyData;
1641                 resProperties.nsAssignLen = propertyLen;
1642             }
1643             else if (propertyType == Rm_resourcePropType_RESOURCE_LINUX_ALIAS) {
1644                 resProperties.linuxAliasData = propertyData;
1645                 resProperties.linuxAliasLen = propertyLen;
1646             }
1647             else {
1648                 retVal = RM_ERROR_GRL_UNKNOWN_RESOURCE_PROPERTY;
1649                 goto exitAllocInit;
1650             }
1652             propOffset = fdt_next_property_offset(globalResourceDtb,
1653                                                   propOffset);
1654             if (propOffset == -FDT_ERR_NOTFOUND) {
1655                 /* No more resource properties but at least one found.  Extract
1656                  * the property values */
1657                 retVal = allocatorExtractGrlResProps(rmHandle,
1658                             fdt_get_name(globalResourceDtb, nodeOffset, NULL),
1659                             &resProperties, linuxDtb);
1660                 if (retVal < RM_OK) {
1661                     goto exitAllocInit;
1662                 }
1663             }
1664             else if (propOffset < -FDT_ERR_NOTFOUND) {
1665                 /* Error returned by LIBFDT */
1666                 retVal = propOffset;
1667                 goto exitAllocInit;
1668             }
1669         }
1670         if (propOffset < -FDT_ERR_NOTFOUND) {
1671             /* Error returned by LIBFDT */
1672             retVal = propOffset;
1673             goto exitAllocInit;
1674         }
1676         nodeOffset = fdt_next_node(globalResourceDtb, nodeOffset, &nodeDepth);
1677         if (nodeOffset < -FDT_ERR_NOTFOUND) {
1678             /* Error returned by LIBFDT */
1679             retVal = nodeOffset;
1680             goto exitAllocInit;
1681         }
1682     }
1684 exitAllocInit:
1685     return(retVal);
1688 /* FUNCTION PURPOSE: Deletes a node from a resource tree
1689  ***********************************************************************
1690  * DESCRIPTION: Deletes a node from an allocator's resource tree based on the
1691  *              given base and length.
1692  */
1693 void rmAllocatorDeleteResNode(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
1694                               int32_t resBase, uint32_t resLen)
1696     Rm_Inst         *rmInst = (Rm_Inst *)rmHandle;
1697     Rm_ResourceNode  find;
1698     Rm_ResourceNode *match;
1700     memset((void *)&find, 0, sizeof(find));
1701     find.base = resBase;
1702     find.length = resLen;
1703     match = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRootEntry,
1704                     &find);
1705     
1706     if (match) {
1707         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRootEntry,
1708                   match);
1709         rmResourceNodeFree(match);
1710         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1711             rmResourceTreeWb(allocator->resourceRootEntry);
1712         }
1713     }
1716 /* FUNCTION PURPOSE: Deletes an allocator's resource tree
1717  ***********************************************************************
1718  * DESCRIPTION: Deletes an allocator's resource tree based on the given
1719  *              resource name.
1720  */
1721 int32_t rmAllocatorDelete(Rm_Handle rmHandle, const char *resourceName)
1723     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1724     Rm_AllocatorTree *allocTree = rmAllocatorGetTree(rmHandle);
1725     Rm_AllocatorNode  find;
1726     Rm_AllocatorNode *match;
1727     Rm_ResourceTree  *resTree;
1728     Rm_ResourceNode  *resNode = NULL;
1729     Rm_ResourceNode  *nextResNode = NULL;
1730     int32_t           retVal = RM_OK;
1732     if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1733         rmAllocatorTreeInv(allocTree);
1734     }
1736     memset((void *)&find, 0, sizeof(find));
1737     rm_strncpy(find.resourceName, resourceName, RM_NAME_MAX_CHARS);
1738     match = RB_FIND(_Rm_AllocatorTree, allocTree, &find);
1740     if (match) {
1741         resTree = match->resourceRootEntry;
1743         /* Destroy resource tree */
1744         if (resTree) {
1745             for (resNode = RB_MIN(_Rm_AllocatorResourceTree, resTree);
1746                  resNode != NULL;
1747                  resNode = nextResNode) {
1748                 nextResNode = RB_NEXT(_Rm_AllocatorResourceTree, resTree,
1749                                       resNode);
1750                 RB_REMOVE(_Rm_AllocatorResourceTree, resTree, nextResNode);
1751                 rmResourceNodeFree(resNode);
1752             }
1753             Rm_osalFree((void *)resTree, sizeof(*resTree));
1754             match->resourceRootEntry = NULL;
1755             RM_SS_OBJ_WB(rmInst, match, Rm_AllocatorNode);
1756         }
1758         RB_REMOVE(_Rm_AllocatorTree, allocTree, match);
1759         rmAllocatorNodeFree(match);
1760         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1761             rmAllocatorTreeWb(allocTree);
1762         }
1763     }
1764     else {
1765         retVal = RM_ERROR_RES_ALLOCATOR_DOES_NOT_EXIST;
1766     }
1767     return (retVal);
1770 /* FUNCTION PURPOSE: Deletes allocator tree
1771  ***********************************************************************
1772  * DESCRIPTION: Removes all resource nodes for each allocator node and then
1773  *              deletes the allocator tree root.
1774  */
1775 void rmAllocatorDeleteTree(Rm_Handle rmHandle)
1777     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1778     Rm_AllocatorTree *allocTree = rmAllocatorGetTree(rmHandle);
1779     Rm_AllocatorNode *allocNode;
1780     Rm_AllocatorNode *nextAllocNode;
1781     Rm_ResourceTree  *resTree;
1782     Rm_ResourceNode  *resNode;
1783     Rm_ResourceNode  *nextResNode;
1785     if (allocTree) {
1786         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1787             rmAllocatorTreeInv(allocTree);
1788         }
1790         for (allocNode = RB_MIN(_Rm_AllocatorTree, allocTree);
1791              allocNode != NULL;
1792              allocNode = nextAllocNode) {
1793             nextAllocNode = RB_NEXT(_Rm_AllocatorTree, allocTree, allocNode);
1795             resTree = allocNode->resourceRootEntry;
1797             if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1798                 rmResourceTreeInv(resTree);
1799             }
1800             /* Delete each node in the resource tree */
1801             for (resNode = RB_MIN(_Rm_AllocatorResourceTree, resTree);
1802                  resNode != NULL;
1803                  resNode = nextResNode) {
1804                 nextResNode = RB_NEXT(_Rm_AllocatorResourceTree, resTree,
1805                                       resNode);
1806                 RB_REMOVE(_Rm_AllocatorResourceTree, resTree, resNode);
1807                 if (resNode->allocationCount) {
1808                     /* Delete all the owners in the resource's owner list */
1809                     allocatorResNodeOwnerClear(rmHandle, resNode);
1810                 }
1811                 rmResourceNodeFree(resNode);
1812             }
1813             Rm_osalFree((void *)resTree, sizeof(*resTree));
1815             RB_REMOVE(_Rm_AllocatorTree, allocTree, allocNode);
1816             rmAllocatorNodeFree(allocNode);
1817         }
1818         Rm_osalFree((void *)allocTree, sizeof(*allocTree));
1819         RM_SS_OBJ_WB(rmInst, rmInst, Rm_Inst);
1820     }