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