Added policy permission to exclude resource ranges from UNSPECIFIED base allocation...
[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         int32_t tmpBase;
470         retVal = rmPolicyGetResourceBase(allocator->policyRoot,
471                                          opInfo->serviceInstNode,
472                                          policyCheckType, &tmpBase);
473         if (retVal == RM_OK) {
474             opInfo->resourceInfo->base = tmpBase;
475         } else {
476             return(retVal);
477         }
478     }
480     if (opInfo->resourceInfo->alignment == RM_RESOURCE_ALIGNMENT_UNSPECIFIED) {
481         /* Get alignment from policy */
482         opInfo->resourceInfo->alignment = rmPolicyGetAllocAlign(allocator->policyRoot);
483     }
485     if (opInfo->resourceInfo->alignment == 0) {
486         opInfo->resourceInfo->alignment = 1;
487     }
489     memset((void *)&findNode, 0, sizeof(findNode));
490     findNode.base = opInfo->resourceInfo->base;
491     findNode.length = opInfo->resourceInfo->length;
493     /* Configure policy checking structure */
494     memset((void *)&policyCheckCfg, 0, sizeof(policyCheckCfg));
495     policyCheckCfg.polTree = allocator->policyRoot;
497     do {
498         matchingNode = RB_FIND(_Rm_AllocatorResourceTree,
499                                allocator->resourceRoot, &findNode);
501         if (matchingNode) {
502             matchingEnd = matchingNode->base + matchingNode->length - 1;
503             findEnd = findNode.base + findNode.length - 1;
504             nodePassesPolicy = RM_BOOL_UNDEF;
505             if ((matchingNode->allocationCount == 0) &&
506                 (findNode.base >= matchingNode->base) &&
507                 (findEnd <= matchingEnd)) {
508                 /* Attempt to preallocate from node only if not owned by anyone
509                  * and sits within a matching node. */
510                 policyCheckCfg.type           = policyCheckType;
511                 policyCheckCfg.neg            = RM_FALSE;
512                 policyCheckCfg.validInstNode  = opInfo->serviceInstNode;
513                 policyCheckCfg.resourceBase   = findNode.base;
514                 policyCheckCfg.resourceLength = findNode.length;
515                 nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg);
517                 if (nodePassesPolicy) {
518                     /* Is range excluded from UNSPECIFIED allocations? */
519                     policyCheckCfg.type = Rm_policyCheck_UNSPEC_EXCLUSION;
520                     policyCheckCfg.neg  = RM_TRUE;
521                     nodePassesPolicy = rmPolicyCheckPrivilege(&policyCheckCfg);
522                 }
524                 if (nodePassesPolicy) {
525                     /* Initialize indexer to be first resource value that
526                      * alignment satisfies */
527                     rangeIndex = findNode.base;
528                     if (rangeIndex % opInfo->resourceInfo->alignment) {
529                         rangeIndex += (opInfo->resourceInfo->alignment -
530                                       (rangeIndex %
531                                        opInfo->resourceInfo->alignment));
532                     }
534                     if ((rangeIndex + opInfo->resourceInfo->length - 1) <=
535                         matchingEnd) {
536                         /* Block of unallocated resources within matchingNode
537                          * that satisfies allocate requirements */
538                         opInfo->resourceInfo->base = rangeIndex;
539                         resourceFound = RM_TRUE;
540                         retVal = RM_SERVICE_PROCESSING;
541                     }
542                 }
543             }
545             if (!resourceFound) {
546                 /* Check next resource node for available resources */
547                 if (findNode.base < matchingNode->base) {
548                     findNode.base = matchingNode->base;
549                 } else {
550                     if (!nodePassesPolicy) {
551                         findNode.base += findNode.length;
552                     } else {
553                         /* Matching node allocated, move to next node */
554                         if ((nextNode = RB_NEXT(_Rm_AllocatorResourceTree,
555                                                 allocator->resourceRoot,
556                                                 matchingNode))) {
557                             findNode.base = nextNode->base;
558                         } else {
559                             retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
560                         }
561                     }
562                 }
563             }
564         } else {
565             retVal = RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET;
566         }
567     } while ((!resourceFound) && 
568              (retVal != RM_SERVICE_DENIED_RES_ALLOC_REQS_NOT_MET));
570     return(retVal);
573 /* FUNCTION PURPOSE: Allocates an allocator resource
574  ***********************************************************************
575  * DESCRIPTION: Will attempt to allocate the resource with specified
576  *              base and length from the resource's allocator.  The
577  *              allocation algorithm will verify the allocation against
578  *              the policy permissions for the instance requesting the
579  *              allocation.  If the policy allows the allocation the 
580  *              algorithm will allocate the resource then combine any
581  *              resource nodes that may have become equivalent (in terms
582  *              of ownership) after the allocation.
583  */
584 static int32_t allocatorAllocate(Rm_Handle rmHandle,
585                                  Rm_AllocatorNode *allocator,
586                                  Rm_AllocatorOpInfo *opInfo)
588     Rm_ResourceNode     findNode;
589     Rm_ResourceNode    *matchingNode = NULL;
590     Rm_ResourceNode    *leftNode = NULL;
591     Rm_ResourceNode    *rightNode = NULL;
592     Rm_PolicyCheckType  policyCheckType;
593     Rm_PolicyCheckCfg   checkCfg;
594     int32_t             allocPassesPolicy;
595     int                 combineLeft = RM_FALSE;
596     int                 combineRight = RM_FALSE;
597     uint32_t            findEnd;
598     uint32_t            matchingEnd;
599     int32_t             retVal;
601     if (opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) {
602         policyCheckType = Rm_policyCheck_INIT;
603     } else if (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE) {
604         policyCheckType = Rm_policyCheck_USE;
605     } else {
606         retVal = RM_ERROR_INVALID_SERVICE_TYPE;
607         return (retVal);
608     }
610     memset((void *)&findNode, 0, sizeof(findNode));
611     findNode.base = opInfo->resourceInfo->base;
612     findNode.length = opInfo->resourceInfo->length;
613     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
614                            &findNode);
616     /* Prepare privilege checks */
617     memset((void *)&checkCfg, 0, sizeof(checkCfg));
619     if (matchingNode) {
620         findEnd = findNode.base + findNode.length - 1;
621         matchingEnd = matchingNode->base + matchingNode->length - 1;
623         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
624             if (opInfo->serviceInstNode == rmPolicyGetLinuxInstNode(rmHandle)) {
625                 /* Bypass policy checks since Linux Kernel has full
626                  * privileges */
627                 allocPassesPolicy = RM_TRUE;
628             } else {
629                 checkCfg.type           = policyCheckType;
630                 checkCfg.neg            = RM_FALSE;
631                 checkCfg.polTree        = allocator->policyRoot;
632                 checkCfg.validInstNode  = opInfo->serviceInstNode;
633                 checkCfg.resourceBase   = findNode.base;
634                 checkCfg.resourceLength = findNode.length;
635                 allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
636                 if (!allocPassesPolicy) {
637                     if (policyCheckType == Rm_policyCheck_INIT) {
638                         retVal = RM_SERVICE_DENIED_INIT_PERM_NOT_GIVEN;
639                     } else {
640                         retVal = RM_SERVICE_DENIED_USE_PERM_NOT_GIVEN;
641                     }
642                 }
644                 if (!allocatorResNodeIsOwnedBy(rmHandle, matchingNode,
645                                                opInfo->serviceInstNode)) {
646                     if (allocPassesPolicy &&
647                         (matchingNode->allocationCount > 0)) {
648                         if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode,
649                                           rmPolicyGetLinuxInstNode(rmHandle))) {
650                             /* Check if instance requesting resource has
651                              * privileges to share a resource already reserved
652                              * by Linux */
653                             checkCfg.type = Rm_policyCheck_SHARED_LINUX;
654                             checkCfg.neg = RM_FALSE;
655                             checkCfg.validInstNode = opInfo->serviceInstNode;
656                             allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
657                             if (!allocPassesPolicy) {
658                                 retVal = RM_SERVICE_DENIED_RES_NOT_SHARED_LINUX;
659                             }
660                         }
661                         if (allocPassesPolicy) {
662                             /* Check exclusive privileges of instance
663                              * requesting resource.  Requesting instance with
664                              * exclusive privileges can't reserve resource if
665                              * already owned*/
666                             checkCfg.type = Rm_policyCheck_EXCLUSIVE;
667                             checkCfg.neg = RM_TRUE;
668                             checkCfg.validInstNode = opInfo->serviceInstNode;
669                             allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
670                             if (!allocPassesPolicy) {
671                                 retVal = RM_SERVICE_DENIED_EXCLUSIVE_RES_ALLOCD;
672                             }
673                         }
674                     }
675                     if (allocPassesPolicy &&
676                         (matchingNode->allocationCount == 1)) {
677                         /* Check exclusive privileges of instance that
678                          * currently owns resource */
679                         checkCfg.type = Rm_policyCheck_EXCLUSIVE;
680                         checkCfg.neg = RM_TRUE;
681                         checkCfg.validInstNode = matchingNode->ownerList->instNameNode;
682                         allocPassesPolicy = rmPolicyCheckPrivilege(&checkCfg);
683                         if (!allocPassesPolicy) {
684                             retVal = RM_SERVICE_DENIED_ALLOCD_TO_EXCLUSIVE_INST;
685                         }
686                     }
687                 }
688             }
690             if (allocPassesPolicy) {
691                 /* Handle any possible node combinations if requesting instance
692                  * is not already in resource's owner list.  Automatic approval
693                  * if requesting instance is already in owner list. */
694                 if ((findNode.base == matchingNode->base) &&
695                     (findEnd == matchingEnd)) {
696                     /* findNode range matches matchingNode range
697                      *
698                      * |<--left node-->||<--matched  node-->||<--right node-->|
699                      *                  |<--alloc request-->|
700                      */
701                     leftNode = RB_PREV(_Rm_AllocatorResourceTree,
702                                        allocator->resourceRoot, matchingNode);
703                     rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
704                                         allocator->resourceRoot, matchingNode);
705                     RB_REMOVE(_Rm_AllocatorResourceTree,
706                               allocator->resourceRoot, matchingNode);
707                     allocatorResNodeOwnerAdd(rmHandle, matchingNode,
708                                              opInfo->serviceInstNode);
710                     if (leftNode &&
711                         allocatorResNodeOwnerCompare(rmHandle,
712                                                      leftNode,
713                                                      matchingNode) &&
714                         allocatorResNodeBoundaryCompare(leftNode,
715                                                         matchingNode)) {
716                         RB_REMOVE(_Rm_AllocatorResourceTree,
717                                   allocator->resourceRoot, leftNode);
718                         combineLeft = RM_TRUE;
719                     }
720                     if (rightNode &&
721                         allocatorResNodeOwnerCompare(rmHandle,
722                                                      rightNode,
723                                                      matchingNode) &&
724                         allocatorResNodeBoundaryCompare(rightNode,
725                                                         matchingNode)) {
726                         RB_REMOVE(_Rm_AllocatorResourceTree,
727                                   allocator->resourceRoot, rightNode);
728                         combineRight = RM_TRUE;
729                     }
731                     if (combineLeft && combineRight) {
732                         /* Combine all three nodes into matchingNode */
733                         matchingNode->base = leftNode->base;
734                         matchingNode->length = leftNode->length +
735                                                matchingNode->length +
736                                                rightNode->length;
738                         allocatorResNodeOwnerClear(rmHandle, leftNode);
739                         rmResourceNodeFree(leftNode);
740                         allocatorResNodeOwnerClear(rmHandle, rightNode);
741                         rmResourceNodeFree(rightNode);
742                     } else if (combineLeft) {
743                         /* Combine left and matching nodes.  Reinsert right. */
744                         matchingNode->base = leftNode->base;
745                         matchingNode->length += leftNode->length;
747                         allocatorResNodeOwnerClear(rmHandle, leftNode);
748                         rmResourceNodeFree(leftNode);
749                         if (rightNode) {
750                             RB_INSERT(_Rm_AllocatorResourceTree,
751                                       allocator->resourceRoot, rightNode);  
752                         }
753                     } else if (combineRight) {
754                         /* Combine right and matching nodes.  Reinsert left. */
755                         matchingNode->length += rightNode->length;
757                         allocatorResNodeOwnerClear(rmHandle, rightNode);
758                         rmResourceNodeFree(rightNode);
759                         if (leftNode) {
760                             RB_INSERT(_Rm_AllocatorResourceTree,
761                                       allocator->resourceRoot, leftNode);
762                         }
763                     } else {
764                         /* No combine. */
765                         if (leftNode) {
766                             RB_INSERT(_Rm_AllocatorResourceTree,
767                                       allocator->resourceRoot, leftNode);
768                         }
769                         if (rightNode) {
770                             RB_INSERT(_Rm_AllocatorResourceTree,
771                                       allocator->resourceRoot, rightNode);
772                         }
773                     }
775                     /* Always reinsert matchingNode */
776                     RB_INSERT(_Rm_AllocatorResourceTree,
777                               allocator->resourceRoot, matchingNode);
779                     /* Matching node contains new reference count after alloc.
780                      * Return new owner count and originating instance
781                      * allocation reference count. */
782                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
783                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
784                                                       matchingNode,
785                                                       opInfo->serviceInstNode);
786                 } else if ((findNode.base > matchingNode->base) &&
787                            (findEnd < matchingEnd)) {
788                     /* findNode range is subset of matchingNode range and
789                      * neither boundary is equivalent.
790                      *
791                      * |<----------matched node---------->|
792                      *        |<---alloc request--->|
793                      */
794                     RB_REMOVE(_Rm_AllocatorResourceTree,
795                               allocator->resourceRoot, matchingNode);
796                     leftNode = rmResourceNodeNew(matchingNode->base,
797                                                  findNode.base -
798                                                  matchingNode->base);
799                     allocatorResNodeOwnerCopy(rmHandle, leftNode, matchingNode);
800                     rightNode = rmResourceNodeNew(findNode.base +
801                                                   findNode.length,
802                                                   matchingEnd - findEnd);
803                     allocatorResNodeOwnerCopy(rmHandle, rightNode,
804                                               matchingNode);
806                     matchingNode->base = findNode.base;
807                     matchingNode->length = findNode.length;
808                     allocatorResNodeOwnerAdd(rmHandle, matchingNode,
809                                              opInfo->serviceInstNode);
811                     /* Insert all the nodes */
812                     RB_INSERT(_Rm_AllocatorResourceTree,
813                               allocator->resourceRoot, matchingNode);
814                     RB_INSERT(_Rm_AllocatorResourceTree,
815                               allocator->resourceRoot, leftNode);
816                     RB_INSERT(_Rm_AllocatorResourceTree,
817                               allocator->resourceRoot, rightNode);
819                     /* Matching node contains new reference count after alloc.
820                      * Return new owner count and originating instance
821                      * allocation reference count. */
822                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
823                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
824                                                      matchingNode,
825                                                      opInfo->serviceInstNode);
826                 } else {
827                     if (findNode.base == matchingNode->base) {
828                         /* findNode base and matchingNode base are equivalent.
829                          * May be combine possibilities to the left
830                          *
831                          * |<-left node (alloc'd)->||<-----matched node------->|
832                          *                          |<-findNode (alloc req)->|
833                          */
834                         leftNode = RB_PREV(_Rm_AllocatorResourceTree,
835                                            allocator->resourceRoot,
836                                            matchingNode);
837                         RB_REMOVE(_Rm_AllocatorResourceTree,
838                                   allocator->resourceRoot, matchingNode);
839                         /* Add allocating instance to owner list for compare
840                          * with leftNode */
841                         allocatorResNodeOwnerAdd(rmHandle, matchingNode,
842                                                  opInfo->serviceInstNode);
844                         if (leftNode &&
845                             allocatorResNodeOwnerCompare(rmHandle,
846                                                          leftNode,
847                                                          matchingNode) &&
848                             allocatorResNodeBoundaryCompare(leftNode,
849                                                             matchingNode)) {
850                             RB_REMOVE(_Rm_AllocatorResourceTree,
851                                       allocator->resourceRoot, leftNode);
852                             /* Combine leftNode and findNode */
853                             leftNode->length += findNode.length;
854                         } else {
855                             leftNode = rmResourceNodeNew(findNode.base,
856                                                          findNode.length);
857                             allocatorResNodeOwnerCopy(rmHandle, leftNode,
858                                                       matchingNode);
859                         }
861                         /* Account for leftNode in matchingNode */
862                         matchingNode->base = findNode.base + findNode.length;
863                         matchingNode->length = matchingEnd - findEnd;
865                         RB_INSERT(_Rm_AllocatorResourceTree,
866                                   allocator->resourceRoot, leftNode);
867                         /* Left node contains new reference count after alloc.
868                          * Return new owner count and originating instance
869                          * allocation reference count. */
870                         opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
871                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
872                                                     leftNode,
873                                                     opInfo->serviceInstNode);
874                     } else /* (findEnd == matchingEnd) */ {
875                         /* findNode end and matchingNode end are equivalent.
876                          * May be combine possibilities to the right
877                          *
878                          * |<------matched node----->||<-right node (alloc'd)->|
879                          *  |<-findNode (alloc req)->|
880                          */
881                         rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
882                                             allocator->resourceRoot,
883                                             matchingNode);
884                         RB_REMOVE(_Rm_AllocatorResourceTree,
885                                   allocator->resourceRoot, matchingNode);
886                         /* Add allocating instance to owner list for compare
887                          * with rightNode */
888                         allocatorResNodeOwnerAdd(rmHandle, matchingNode,
889                                                  opInfo->serviceInstNode);
891                         if (rightNode &&
892                             allocatorResNodeOwnerCompare(rmHandle,
893                                                          rightNode,
894                                                          matchingNode) &&
895                             allocatorResNodeBoundaryCompare(rightNode,
896                                                             matchingNode)) {
897                             RB_REMOVE(_Rm_AllocatorResourceTree,
898                                       allocator->resourceRoot, rightNode);
899                             /* Combine rightNode and findNode */
900                             rightNode->base = findNode.base;
901                             rightNode->length += findNode.length;
902                         } else {
903                             rightNode = rmResourceNodeNew(findNode.base,
904                                                           findNode.length);
905                             allocatorResNodeOwnerCopy(rmHandle, rightNode,
906                                                       matchingNode);
907                         }
909                         /* Account for rightNode in matchingNode */
910                         matchingNode->length -= findNode.length;
912                         RB_INSERT(_Rm_AllocatorResourceTree,
913                                   allocator->resourceRoot, rightNode);
914                         /* Right node contains new reference count after alloc.
915                          * Return new owner count and originating instance
916                          * allocation reference count. */
917                         opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
918                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
919                                                     rightNode,
920                                                     opInfo->serviceInstNode);
921                     }
922                     /* Remove allocating instance from leftover matchingNode */
923                     allocatorResNodeOwnerDelete(rmHandle, matchingNode,
924                                                 opInfo->serviceInstNode);
925                     RB_INSERT(_Rm_AllocatorResourceTree,
926                               allocator->resourceRoot, matchingNode);
927                 }
928                 retVal = RM_SERVICE_APPROVED;
929             }
930         } else {
931             retVal = RM_SERVICE_DENIED_PARTIAL_ALLOCATION;
932         }
933     } else {
934         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
935     }
937     return(retVal);
940 /* FUNCTION PURPOSE: Frees an allocator resource
941  ***********************************************************************
942  * DESCRIPTION: Will attempt to free the resource with specified
943  *              base and length from the resource's allocator.  The
944  *              free algorithm will verify the free request parameters
945  *              match an allocated range for the resource and that the
946  *              range is owned by the instance requesting the free. If
947  *              the free is validated the algorithm will free the 
948  *              resource then combine any resource nodes that may have
949  *              become equivalent (in terms of ownership) after the
950  *              allocation.
951  */
952 static int32_t allocatorFree(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
953                              Rm_AllocatorOpInfo *opInfo)
955     Rm_ResourceNode  findNode;
956     Rm_ResourceNode *matchingNode = NULL;
957     Rm_ResourceNode *leftNode = NULL;
958     Rm_ResourceNode *rightNode = NULL;
959     int              combineLeft = RM_FALSE;
960     int              combineRight = RM_FALSE;
961     uint32_t         findEnd;
962     uint32_t         matchingEnd;
963     int32_t          retVal;
965     memset((void *)&findNode, 0, sizeof(findNode));
966     findNode.base = opInfo->resourceInfo->base;
967     findNode.length = opInfo->resourceInfo->length;
968     matchingNode = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
969                            &findNode);
971     if (matchingNode) {
972         findEnd = findNode.base + findNode.length - 1;
973         matchingEnd = matchingNode->base + matchingNode->length - 1;
974         
975         if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd)) {
976             if (matchingNode->allocationCount) {
977                 if (allocatorResNodeIsOwnedBy(rmHandle, matchingNode,
978                     opInfo->serviceInstNode)) {
979                     if ((findNode.base == matchingNode->base) &&
980                         (findEnd == matchingEnd)) {
981                         /* Case 1: Free range equals allocated matched node
982                          *         exactly. Attempt to combine freed node with
983                          *         nodes to left and right.
984                          *
985                          * |<-left node->||<---matched node--->||<-right node->|
986                          *                |<---free request--->|
987                          */
988                         leftNode = RB_PREV(_Rm_AllocatorResourceTree,
989                                            allocator->resourceRoot,
990                                            matchingNode);
991                         rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
992                                             allocator->resourceRoot,
993                                             matchingNode);
994                         RB_REMOVE(_Rm_AllocatorResourceTree,
995                                   allocator->resourceRoot, matchingNode);
996                         allocatorResNodeOwnerDelete(rmHandle, matchingNode,
997                                                     opInfo->serviceInstNode);
999                         if (leftNode &&
1000                             allocatorResNodeOwnerCompare(rmHandle,
1001                                                          leftNode,
1002                                                          matchingNode) &&
1003                             allocatorResNodeBoundaryCompare(leftNode,
1004                                                             matchingNode)) {
1005                             RB_REMOVE(_Rm_AllocatorResourceTree,
1006                                       allocator->resourceRoot, leftNode);
1007                             combineLeft = RM_TRUE;
1008                         }
1009                         if (rightNode &&
1010                             allocatorResNodeOwnerCompare(rmHandle,
1011                                                          rightNode,
1012                                                          matchingNode) &&
1013                             allocatorResNodeBoundaryCompare(rightNode,
1014                                                             matchingNode)) {
1015                             RB_REMOVE(_Rm_AllocatorResourceTree,
1016                                       allocator->resourceRoot, rightNode);
1017                             combineRight = RM_TRUE;
1018                         }
1020                         if (combineLeft && combineRight) {
1021                             /* Combine all three nodes into matchingNode */
1022                             matchingNode->base = leftNode->base;
1023                             matchingNode->length = leftNode->length +
1024                                                    matchingNode->length +
1025                                                    rightNode->length;
1027                             allocatorResNodeOwnerClear(rmHandle, leftNode);
1028                             rmResourceNodeFree(leftNode);
1029                             allocatorResNodeOwnerClear(rmHandle, rightNode);
1030                             rmResourceNodeFree(rightNode);
1031                         } else if (combineLeft) {
1032                             /* Combine left and matching nodes.
1033                              * Reinsert right. */
1034                             matchingNode->base = leftNode->base;
1035                             matchingNode->length += leftNode->length;
1037                             allocatorResNodeOwnerClear(rmHandle, leftNode);
1038                             rmResourceNodeFree(leftNode);
1039                             if (rightNode) {
1040                                 RB_INSERT(_Rm_AllocatorResourceTree,
1041                                           allocator->resourceRoot, rightNode);
1042                             }
1043                         } else if (combineRight) {
1044                             /* Combine right and matching nodes.
1045                              * Reinsert left. */
1046                             matchingNode->length += rightNode->length;
1048                             allocatorResNodeOwnerClear(rmHandle, rightNode);
1049                             rmResourceNodeFree(rightNode);
1050                             if (leftNode) {
1051                                 RB_INSERT(_Rm_AllocatorResourceTree,
1052                                           allocator->resourceRoot, leftNode);
1053                             }
1054                         } else {
1055                             /* No combine. */
1056                             if (leftNode) {
1057                                 RB_INSERT(_Rm_AllocatorResourceTree,
1058                                           allocator->resourceRoot, leftNode);
1059                             }
1060                             if (rightNode) {
1061                                 RB_INSERT(_Rm_AllocatorResourceTree,
1062                                           allocator->resourceRoot, rightNode);
1063                             }
1064                         }
1066                         /* Always reinsert matchingNode */
1067                         RB_INSERT(_Rm_AllocatorResourceTree,
1068                                   allocator->resourceRoot, matchingNode);
1069                         
1070                         /* Matching node is what remains after free.  Return
1071                          * remaining owner count and originating instance
1072                          * allocation reference count. */
1073                         opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1074                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1075                                                     matchingNode,
1076                                                     opInfo->serviceInstNode);
1077                     } else if ((findNode.base > matchingNode->base) &&
1078                                (findEnd < matchingEnd)) {
1079                         /* Case 2: Free range is less than range in matched
1080                          *         node. Split matched node into three nodes.
1081                          *
1082                          * |<----------matched node---------->|
1083                          *        |<---free request--->|
1084                          *
1085                          * Remove instance from owner list then add it back in
1086                          * for side nodes for proper accounting of allocations
1087                          * in validInstance list
1088                          */
1089                         RB_REMOVE(_Rm_AllocatorResourceTree,
1090                                   allocator->resourceRoot, matchingNode);
1091                         allocatorResNodeOwnerDelete(rmHandle, matchingNode,
1092                                                     opInfo->serviceInstNode);
1094                         leftNode = rmResourceNodeNew(matchingNode->base,
1095                                                      findNode.base -
1096                                                      matchingNode->base);
1097                         allocatorResNodeOwnerCopy(rmHandle, leftNode,
1098                                                   matchingNode);
1099                         allocatorResNodeOwnerAdd(rmHandle, leftNode,
1100                                                  opInfo->serviceInstNode);
1101                         RB_INSERT(_Rm_AllocatorResourceTree,
1102                                   allocator->resourceRoot, leftNode);
1104                         rightNode = rmResourceNodeNew(findNode.base +
1105                                                       findNode.length,
1106                                                       matchingEnd - findEnd);
1107                         allocatorResNodeOwnerCopy(rmHandle, rightNode,
1108                                                   matchingNode);
1109                         allocatorResNodeOwnerAdd(rmHandle, rightNode,
1110                                                  opInfo->serviceInstNode);
1111                         RB_INSERT(_Rm_AllocatorResourceTree,
1112                                   allocator->resourceRoot, rightNode);
1114                         matchingNode->base = findNode.base;
1115                         matchingNode->length = findNode.length;
1116                         RB_INSERT(_Rm_AllocatorResourceTree,
1117                                   allocator->resourceRoot, matchingNode);
1119                         /* Matching node is what remains after free.  Return
1120                          * remaining owner count and originating instance
1121                          * allocation reference count. */
1122                         opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1123                         opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1124                                                     matchingNode,
1125                                                     opInfo->serviceInstNode);
1126                     } else {
1127                         if (findNode.base == matchingNode->base) {
1128                             /* Case 3: Free range is on left boundary of
1129                              *         matched node. Try to combine free range
1130                              *         with left node.
1131                              *
1132                              * |<-left node (free)->||<-----matched node------>|
1133                              *                       |<-findNode (free req)->|
1134                              */
1136                             leftNode = RB_PREV(_Rm_AllocatorResourceTree,
1137                                                allocator->resourceRoot,
1138                                                matchingNode);
1139                             RB_REMOVE(_Rm_AllocatorResourceTree,
1140                                       allocator->resourceRoot, matchingNode);
1141                             /* Remove freeing instance from owner list for
1142                              * compare with leftNode */
1143                             allocatorResNodeOwnerDelete(rmHandle, matchingNode,
1144                                                        opInfo->serviceInstNode);
1146                             if (leftNode &&
1147                                 allocatorResNodeOwnerCompare(rmHandle,
1148                                                              leftNode,
1149                                                              matchingNode) &&
1150                                 allocatorResNodeBoundaryCompare(leftNode,
1151                                                                 matchingNode)) {
1152                                 RB_REMOVE(_Rm_AllocatorResourceTree,
1153                                           allocator->resourceRoot, leftNode);
1154                                 /* Combine leftNode and findNode */
1155                                 leftNode->length += findNode.length;
1156                             } else {
1157                                 leftNode = rmResourceNodeNew(findNode.base,
1158                                                              findNode.length);
1159                                 allocatorResNodeOwnerCopy(rmHandle, leftNode,
1160                                                           matchingNode);
1161                             }
1163                             /* Remove leftNode range from matchingNode */
1164                             matchingNode->base = findNode.base +
1165                                                  findNode.length;
1166                             matchingNode->length = matchingEnd - findEnd;
1167                             RB_INSERT(_Rm_AllocatorResourceTree,
1168                                       allocator->resourceRoot, leftNode);
1170                             /* Left node is what remains after free.  Return
1171                              * remaining owner count and originating instance
1172                              * allocation reference count. */
1173                             opInfo->resourceInfo->ownerCount = leftNode->allocationCount;
1174                             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1175                                                     leftNode,
1176                                                     opInfo->serviceInstNode);
1177                         } else /* (findEnd == matchingEnd) */ {
1178                             /* Case 4: Free range is on right boundary of
1179                              *         matched node. Try to combine free range
1180                              *         with right node.
1181                              *
1182                              * |<-----matched node----->||<-right node (free)->|
1183                              *  |<-findNode (free req)->|
1184                              */
1186                             rightNode = RB_NEXT(_Rm_AllocatorResourceTree,
1187                                                 allocator->resourceRoot,
1188                                                 matchingNode);
1189                             RB_REMOVE(_Rm_AllocatorResourceTree,
1190                                       allocator->resourceRoot, matchingNode);
1191                             /* Remove freeing instance from owner list for
1192                              * compare with rightNode */
1193                             allocatorResNodeOwnerDelete(rmHandle, matchingNode,
1194                                                        opInfo->serviceInstNode);
1195                             
1196                             if (rightNode &&
1197                                 allocatorResNodeOwnerCompare(rmHandle,
1198                                                              rightNode,
1199                                                              matchingNode) &&
1200                                 allocatorResNodeBoundaryCompare(rightNode,
1201                                                                 matchingNode)) {
1202                                 RB_REMOVE(_Rm_AllocatorResourceTree,
1203                                           allocator->resourceRoot, rightNode);
1204                                 /* Combine rightNode and findNode */
1205                                 rightNode->base = findNode.base;
1206                                 rightNode->length += findNode.length;
1207                             } else {
1208                                 rightNode = rmResourceNodeNew(findNode.base,
1209                                                               findNode.length);
1210                                 allocatorResNodeOwnerCopy(rmHandle, rightNode,
1211                                                           matchingNode);
1212                             }
1214                             /* Remove rightNode range from matchingNode */
1215                             matchingNode->length -= findNode.length;
1216                             RB_INSERT(_Rm_AllocatorResourceTree,
1217                                       allocator->resourceRoot, rightNode);
1219                             /* Right node is what remains after free.  Return
1220                              * remaining owner count and originating instance
1221                              * allocation reference count. */
1222                             opInfo->resourceInfo->ownerCount = rightNode->allocationCount;
1223                             opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1224                                                     rightNode,
1225                                                     opInfo->serviceInstNode);
1226                         }
1228                         /* Add freeing instance back into matchingNode
1229                          * allocations */
1230                         allocatorResNodeOwnerAdd(rmHandle, matchingNode,
1231                                                  opInfo->serviceInstNode);
1232                         RB_INSERT(_Rm_AllocatorResourceTree,
1233                                   allocator->resourceRoot, matchingNode);
1234                     }
1235                     retVal = RM_SERVICE_APPROVED;
1236                 } else {
1237                     /* Return owner count and instance alloc count.  In case
1238                      * it's a reference count check in application */
1239                     opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1240                     opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1241                                                     matchingNode,
1242                                                     opInfo->serviceInstNode);
1243                     retVal = RM_SERVICE_DENIED_RES_NOT_ALLOCD_TO_INST;
1244                 }
1245             } else {
1246                 /* Return owner count and instance alloc count.  In case it's
1247                  * a reference count check in application */
1248                 opInfo->resourceInfo->ownerCount = matchingNode->allocationCount;
1249                 opInfo->resourceInfo->instAllocCount = allocatorResNodeOwnerGetRefCnt(rmHandle,
1250                                                     matchingNode,
1251                                                     opInfo->serviceInstNode);
1252                 retVal = RM_SERVICE_DENIED_RES_ALREADY_FREE;
1253             }
1254         } else {
1255             retVal = RM_SERVICE_DENIED_PARTIAL_FREE;
1256         }
1257     } else {
1258         retVal = RM_SERVICE_DENIED_RES_RANGE_DOES_NOT_EXIST;
1259     }
1260     return(retVal);
1263 /* FUNCTION PURPOSE: Reserves a Linux resource
1264  ***********************************************************************
1265  * DESCRIPTION: Reserves resources for Linux using the base and length
1266  *              values retrieved from the Linux DTB via the
1267  *              "linux-dtb-alias" properties within the GRL.
1268  */
1269 static int32_t allocatorReserveLinuxResource(Rm_Handle rmHandle,
1270                                              Rm_LinuxAlias *linuxAlias,
1271                                              Rm_LinuxValueRange *linuxValues,
1272                                              Rm_AllocatorOpInfo *opInfo)
1274     int32_t  retVal = RM_OK;
1275     int      baseFound = RM_FALSE;
1276     int      lengthFound = RM_FALSE;
1277     uint32_t valueIndex = 0;
1279     while ((linuxValues) && (!baseFound || !lengthFound)) {
1280         if (linuxAlias->baseOffset == valueIndex) {
1281             opInfo->resourceInfo->base = linuxValues->value;
1282             baseFound = RM_TRUE;
1284             if (linuxAlias->lengthOffset ==
1285                 RM_DTB_UTIL_LINUX_ALIAS_OFFSET_NOT_SET) {
1286                 opInfo->resourceInfo->length = 1;
1287                 lengthFound = RM_TRUE;
1288             }
1289         } else if (linuxAlias->lengthOffset == valueIndex) {
1290             opInfo->resourceInfo->length = linuxValues->value;
1291             lengthFound = RM_TRUE;
1292         }
1293         /* else: value was not a base or length so skip to next alias value */
1295         linuxValues = (Rm_LinuxValueRange *)linuxValues->nextValue;
1296         valueIndex++;
1297     }
1299     if (!baseFound || !lengthFound) {
1300         retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1301     } else {
1302         /* Allocate resource to Linux */
1303         retVal = rmAllocatorOperation(rmHandle, opInfo);
1304         if (retVal == RM_SERVICE_APPROVED) {
1305             retVal = RM_OK;
1306         }
1307     }
1308     return(retVal);
1311 /* FUNCTION PURPOSE: Finds and reserves Linux resources
1312  ***********************************************************************
1313  * DESCRIPTION: Parses the Linux DTB for resources consumed by the
1314  *              Linux kernel.  If the resource is found via the
1315  *              "linux-dtb-alias" property defined in the GRL it is 
1316  *              reserved.
1317  */
1318 static int32_t allocatorFindLinuxResource(Rm_Handle rmHandle,
1319                                           const char *resourceName,
1320                                           void *linuxDtb,
1321                                           Rm_LinuxAlias *linuxAlias)
1323     Rm_AllocatorOpInfo  opInfo;
1324     Rm_ResourceInfo     resourceInfo;
1325     uint32_t            pathOffset;
1326     uint32_t            pathSize;
1327     char               *tempAliasPath;
1328     char               *spacePtr;
1329     int32_t             propOffset;
1330     int32_t             nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1331     int32_t             prevDepth = RM_DTB_UTIL_STARTING_DEPTH;
1332     int32_t             depth = RM_DTB_UTIL_STARTING_DEPTH;
1333     int32_t             propertyLen;
1334     const char         *propertyName;
1335     const void         *propertyData;
1336     Rm_LinuxValueRange *linValRange;
1337     int32_t             retVal = RM_OK;
1339     memset((void *)&opInfo, 0, sizeof(opInfo));
1340     memset((void *)&resourceInfo, 0, sizeof(resourceInfo));
1342     rm_strncpy(resourceInfo.name, resourceName, RM_NAME_MAX_CHARS);
1343     opInfo.serviceInstNode = rmPolicyGetLinuxInstNode(rmHandle);
1344     opInfo.operation       = Rm_allocatorOp_ALLOCATE_INIT;
1345     opInfo.resourceInfo    = &resourceInfo;
1347     if (!opInfo.serviceInstNode) {
1348         retVal = RM_SERVICE_DENIED_INST_NAME_NOT_VALID;
1349         goto errorExit;
1350     }
1352     while(linuxAlias) {
1353         /* Reset parsing variables */
1354         pathOffset = 0;
1355         pathSize = strlen(linuxAlias->path) + 1;
1356         tempAliasPath = Rm_osalMalloc(pathSize);
1357         rm_strncpy(tempAliasPath, linuxAlias->path, pathSize);
1358         nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1359         prevDepth = RM_DTB_UTIL_STARTING_DEPTH;
1360         resourceInfo.base = 0;
1361         resourceInfo.length = 0;
1363         spacePtr = strpbrk(tempAliasPath, " ");
1364         if (spacePtr) {
1365             *spacePtr = '\0';
1366         }
1368         while(pathOffset < pathSize) {
1369             /* Move through DTB nodes until next alias path node found */
1370             if (strcmp(tempAliasPath + pathOffset,
1371                        fdt_get_name(linuxDtb, nodeOffset, NULL))) {
1372                 nodeOffset = fdt_next_node(linuxDtb, nodeOffset, &depth);
1374                 if ((depth < prevDepth) || (nodeOffset == -FDT_ERR_NOTFOUND)) {
1375                     /* Returning from subnode that matched part of alias path
1376                      * without finding resource values */
1377                     retVal = RM_ERROR_DATA_NOT_FOUND_AT_LINUX_ALIAS;
1378                     break;
1379                 }
1380             } else {
1381                 /* Found next alias path node.  Move to next node name in path
1382                  * string. */
1383                 pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1384                 spacePtr = strpbrk(tempAliasPath + pathOffset, " ");
1385                 if (spacePtr) {
1386                     *spacePtr = '\0';
1387                 }
1389                 prevDepth = fdt_node_depth(linuxDtb, nodeOffset);
1390                 propOffset = fdt_first_property_offset(linuxDtb, nodeOffset);
1391                 while ((propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1392                        (pathOffset < pathSize)) {
1393                     propertyData = fdt_getprop_by_offset(linuxDtb, propOffset,
1394                                                          &propertyName,
1395                                                          &propertyLen);
1397                     if (strcmp(tempAliasPath + pathOffset, propertyName) == 0) {
1398                         /* Found resource at end of alias path */
1399                         pathOffset += (strlen(tempAliasPath + pathOffset) + 1);
1400                         linValRange = rmDtbUtilLinuxExtractValues(propertyData,
1401                                                                   propertyLen);
1402                         retVal = allocatorReserveLinuxResource(rmHandle,
1403                                                                linuxAlias,
1404                                                                linValRange,
1405                                                                &opInfo);
1406                         rmDtbUtilLinuxFreeValues(linValRange);
1407                     }
1408                     propOffset = fdt_next_property_offset(linuxDtb, propOffset);
1409                 }
1411                 if (propOffset < -FDT_ERR_NOTFOUND) {
1412                     retVal = propOffset;
1413                     break;
1414                 }
1415             }
1416         }
1418         Rm_osalFree(tempAliasPath, pathSize);
1419         if (retVal < RM_OK) {
1420             break;
1421         }
1422         linuxAlias = linuxAlias->nextLinuxAlias;
1423     }
1424 errorExit:
1425     return(retVal);
1428 /* FUNCTION PURPOSE: Populates an allocator's resource tree
1429  ***********************************************************************
1430  * DESCRIPTION: Uses resource range information pulled from GRL to
1431  *              populate an allocator's resource tree
1432  */
1433 static int32_t allocatorPopulateResTree(Rm_ResourceTree *resTree,
1434                                         Rm_ResourceRange *range)
1436     Rm_ResourceNode *resNode = NULL;
1437     int32_t retVal = RM_OK;
1439     while (range != NULL) {
1440         if ((resNode = rmResourceNodeNew(range->base, range->length))) {
1441             RB_INSERT(_Rm_AllocatorResourceTree, resTree,
1442                       resNode);
1443         } else {
1444             retVal = RM_ERROR_MALLOC_FAILED_RES_NODE;
1445             break;
1446         }
1447         range = range->nextRange;
1448     }
1450     return(retVal);
1453 /* FUNCTION PURPOSE: Initializes a new allocator
1454  ***********************************************************************
1455  * DESCRIPTION: allocates and initializes a new allocator for the
1456  *              provided resource name.  The resource and policy tree
1457  *              root nodes are allocated and initialized as part of
1458  *              the allocator node initialization.
1459  */
1460 static Rm_AllocatorNode *allocatorInitNode(Rm_Inst *rmInst,
1461                                            const char *resourceName,
1462                                            int32_t *retVal)
1464     Rm_AllocatorTree *allocTree  = rmInst->allocatorTree;
1465     Rm_AllocatorNode *newAllocNode = NULL;
1466     Rm_ResourceTree  *resTree = NULL;
1467     Rm_PolicyTree    *polTree = NULL;
1469     *retVal = RM_OK;
1471     if ((strlen(resourceName) + 1) > RM_NAME_MAX_CHARS) {
1472         *retVal = RM_ERROR_RESOURCE_NAME_TOO_LONG;
1473         goto errorExit;
1474     }
1476     newAllocNode = rmAllocatorNodeNew(resourceName);
1477     if (newAllocNode) {
1478         if (RB_INSERT(_Rm_AllocatorTree, allocTree, newAllocNode)) {
1479             /* Collision */
1480             *retVal = RM_ERROR_RES_SPECIFIED_MORE_THAN_ONCE;
1481             goto errorExit;
1482         }
1484         if ((resTree = Rm_osalMalloc(sizeof(*resTree)))) {
1485             RB_INIT(resTree);
1486             newAllocNode->resourceRoot = resTree;
1487         } else {
1488             *retVal = RM_ERROR_MALLOC_FAILED_RES_TREE;
1489             goto errorExit;
1490         }
1492         if ((polTree = Rm_osalMalloc(sizeof(*polTree)))) {
1493             RB_INIT(polTree);
1494             newAllocNode->policyRoot = polTree;
1495         } else {
1496             *retVal = RM_ERROR_MALLOC_FAILED_POL_TREE;
1497             goto errorExit;
1498         }
1499     } else {
1500         *retVal = RM_ERROR_COULD_NOT_CREATE_NEW_ALLOCATOR;
1501         goto errorExit;
1502     }
1504 errorExit:
1505     if ((*retVal != RM_OK) && newAllocNode) {
1506         rmAllocatorNodeFree(newAllocNode);
1507     }
1508     return(newAllocNode);
1511 /* FUNCTION PURPOSE: Creates and initializes an allocator node
1512  ***********************************************************************
1513  * DESCRIPTION: Creates an allocator for the provided resource name.
1514  *              The resource properties retrieved from the GRL are used
1515  *              to create a resource tree.  Resources will be reserved
1516  *              for the Linux kernel if the Linux DTB is provided and
1517  *              there are "linux-dtb-alias" properties specified in
1518  *              the GRL.  A policy tree will be created using the
1519  *              resource's entry in the policy.
1520  */
1521 static int32_t allocatorCreateNode(Rm_Inst *rmInst, void *policyDtb,
1522                                    void *linuxDtb, const char *resourceName,
1523                                    Rm_ResourceProperties *resProps)
1525     Rm_AllocatorNode *allocNode = NULL;
1526     Rm_ResourceRange *range = NULL;
1527     Rm_LinuxAlias    *linuxAlias = NULL;
1528     int32_t           retVal = RM_OK;
1530     allocNode = allocatorInitNode(rmInst, resourceName, &retVal);
1531     if (allocNode) {
1532         range = rmDtbUtilResExtractRange(resProps->rangeData,
1533                                          resProps->rangeLen);
1534         retVal = allocatorPopulateResTree(allocNode->resourceRoot, range);
1535         if (retVal != RM_OK) {
1536             goto errorExit;
1537         }
1538         /* Create the companion policy tree for the resource */
1539         retVal = rmPolicyPopulateTree((Rm_Handle)rmInst, allocNode->policyRoot,
1540                                       policyDtb, resourceName);
1541         if (retVal != RM_OK) {
1542             goto errorExit;
1543         }
1545         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1546             /* Writeback resource tree for Linux resource reservation which
1547              * uses path through rmAllocatorOperation function.  This function
1548              * performs an invalidate of resource tree */
1549             rmResourceTreeWb(allocNode->resourceRoot);
1550         }
1552         if (resProps->linuxAliasData && linuxDtb) {
1553             linuxAlias = rmDtbUtilResExtractLinuxAlias(resProps->linuxAliasData,
1554                                                        resProps->linuxAliasLen,
1555                                                        &retVal);
1556             /* linuxAlias will be NULL if retVal contains error code */
1557             if (linuxAlias) {
1558                 retVal = allocatorFindLinuxResource(rmInst, resourceName,
1559                                                     linuxDtb, linuxAlias);
1560             }
1562             if (retVal != RM_OK) {
1563                 goto errorExit;
1564             }
1565         }
1567 errorExit:
1568         if (range) {
1569             rmDtbUtilResFreeRange(range);
1570         }
1571         if (linuxAlias) {
1572             rmDtbUtilResFreeLinuxAlias(linuxAlias);
1573         }
1574     }
1575     return(retVal);
1578 /* FUNCTION PURPOSE: Creates NameServer assignment entries
1579  ***********************************************************************
1580  * DESCRIPTION: Creates a NameServer entry for each NameServer assignment
1581  *              found in a GRL's resource node
1582  */
1583 static int32_t allocatorNsAdd(Rm_Inst *rmInst, const char *resourceName,
1584                               Rm_ResourceProperties *resProps)
1586     Rm_NsAssignment     *nsAssigns = NULL;
1587     Rm_NsAssignment     *nsAssignsBase = NULL;
1588     Rm_NameServerObjCfg  nsCfg;
1589     int32_t              retVal = RM_OK;
1591     if (resProps->nsAssignData) {
1592         nsAssigns = rmDtbUtilResExtractNsAssignment(resProps->nsAssignData,
1593                                                     resProps->nsAssignLen,
1594                                                     &retVal);
1595         /* nsAssignments will be NULL if retVal contains error code */
1596         if (nsAssigns) {
1597             nsAssignsBase = nsAssigns;
1598             while (nsAssigns) {
1599                 memset((void *)&nsCfg, 0, sizeof(nsCfg));
1600                 nsCfg.nameServerTree = rmInst->u.server.nameServer;
1601                 nsCfg.nodeCfg.objName = nsAssigns->nsName;
1602                 nsCfg.nodeCfg.resourceName = (char *)resourceName;
1603                 nsCfg.nodeCfg.resourceBase= nsAssigns->resourceBase;
1604                 nsCfg.nodeCfg.resourceLength = nsAssigns->resourceLength;
1605                 rmNameServerAddObject(&nsCfg);
1606                 nsAssigns = nsAssigns->nextNsAssignment;
1607             }
1608             rmDtbUtilResFreeNsAssignmentList(nsAssignsBase);
1609         }
1610     }
1612     return(retVal);
1616 /* FUNCTION PURPOSE: Populate the allocator tree based on the GRL
1617  ***********************************************************************
1618  * DESCRIPTION: Populates the allocator tree using the GRL and policy DTBs.
1619  *              Optionally, the Linux DTB will be scanned for resources used
1620  *              by the Kernel if the Linux DTB is non-NULL.
1621  */
1622 static int32_t allocatorPopulateGrlBased(Rm_Inst *rmInst, void *grlDtb,
1623                                          void *policyDtb, void *linuxDtb)
1625     int32_t                nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1626     int32_t                nodeDepth = RM_DTB_UTIL_STARTING_DEPTH;
1627     Rm_ResourceProperties  resProps;
1628     int32_t                propOffset;
1629     int32_t                propertyLen;
1630     const char            *propertyName;
1631     const void            *propertyData;
1632     Rm_ResourcePropType    propertyType;
1633     int32_t                retVal = RM_OK;
1635     /* Create allocator tree node with resource and policy trees for
1636      * each resource found in the GRL. */
1637     while ((nodeOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1638            (nodeDepth >= RM_DTB_UTIL_STARTING_DEPTH)) {
1640         memset((void *)&resProps, 0, sizeof(resProps));
1641         /* Get properties of resource node */
1642         propOffset = fdt_first_property_offset(grlDtb, nodeOffset);
1644         while (propOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) {
1645             propertyData = fdt_getprop_by_offset(grlDtb, propOffset,
1646                                                  &propertyName, &propertyLen);
1647             propertyType = rmDtbUtilResGetPropertyType(propertyName);
1648             switch(propertyType) {
1649                 case Rm_resourcePropType_RESOURCE_RANGE:
1650                     resProps.rangeData = propertyData;
1651                     resProps.rangeLen = propertyLen;
1652                     break;
1653                 case Rm_resourcePropType_NSASSIGNMENT:
1654                     resProps.nsAssignData = propertyData;
1655                     resProps.nsAssignLen = propertyLen;
1656                     break;
1657                 case Rm_resourcePropType_RESOURCE_LINUX_ALIAS:
1658                     resProps.linuxAliasData = propertyData;
1659                     resProps.linuxAliasLen = propertyLen;
1660                     break;
1661                 default:
1662                     retVal = RM_ERROR_GRL_UNKNOWN_RESOURCE_PROPERTY;
1663                     goto errorExit;
1664             }
1666             propOffset = fdt_next_property_offset(grlDtb, propOffset);
1667             if (propOffset == -FDT_ERR_NOTFOUND) {
1668                 const char *resName = fdt_get_name(grlDtb, nodeOffset,
1669                                                    NULL);
1671                 if ((!resProps.rangeData) && (!resProps.nsAssignData)) {
1672                     retVal = RM_ERROR_GRL_INVALID_NODE_DEF;
1673                     goto errorExit;
1674                 }
1676                 if (resProps.rangeData) {
1677                     /* At least range property found.  Create allocator node
1678                      * using extracted values for resource tree and
1679                      * resource's policy entry for policy tree */
1680                     retVal = allocatorCreateNode(rmInst, policyDtb, linuxDtb,
1681                                                  resName, &resProps);
1682                     if (retVal != RM_OK) {
1683                         goto errorExit;
1684                     }
1685                 }
1687                 if (resProps.nsAssignData) {
1688                     retVal = allocatorNsAdd(rmInst, resName, &resProps);
1689                     if (retVal != RM_OK) {
1690                         goto errorExit;
1691                     }
1692                 }
1693             } else if (propOffset < -FDT_ERR_NOTFOUND) {
1694                 /* Error returned by LIBFDT */
1695                 retVal = propOffset;
1696                 goto errorExit;
1697             }
1698             /* else: fall through to get next property */
1699         }
1700         if (propOffset < -FDT_ERR_NOTFOUND) {
1701             /* Error returned by LIBFDT */
1702             retVal = propOffset;
1703             goto errorExit;
1704         }
1706         nodeOffset = fdt_next_node(grlDtb, nodeOffset, &nodeDepth);
1707         if (nodeOffset < -FDT_ERR_NOTFOUND) {
1708             /* Error returned by LIBFDT */
1709             retVal = nodeOffset;
1710             goto errorExit;
1711         }
1712     }
1714 errorExit:
1715     return(retVal);
1718 /* FUNCTION PURPOSE: Populate the allocator tree based on the Policy DTB
1719  ***********************************************************************
1720  * DESCRIPTION: Populates the allocator tree using the policy DTB.  The
1721  *              resource trees in each allocator will be created on the fly
1722  *              as a CD requests resources from the server.  Client instances
1723  *              will never create resource trees since they'll only use the
1724  *              allocator's policy trees for the static initialization phase.
1725  */
1726 static int32_t allocatorPopulatePolicyBased(Rm_Inst *rmInst, void *policyDtb)
1728     int32_t            nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;
1729     int32_t            nodeDepth = RM_DTB_UTIL_STARTING_DEPTH;
1730     int32_t            propOffset;
1731     const char        *resName;
1732     const char        *propName;
1733     Rm_PolicyPropType  propType;
1734     Rm_AllocatorNode  *newAllocNode = NULL;
1735     int32_t            retVal = RM_OK;
1737     /* Search for resource node definitions in the policy */
1738     while ((nodeOffset >= RM_DTB_UTIL_STARTING_NODE_OFFSET) &&
1739            (nodeDepth >= RM_DTB_UTIL_STARTING_DEPTH)) {
1741         propOffset = fdt_first_property_offset(policyDtb, nodeOffset);
1742         while (propOffset > RM_DTB_UTIL_STARTING_NODE_OFFSET) {
1743             fdt_getprop_by_offset(policyDtb, propOffset, &propName, NULL);
1744             propType = rmDtbUtilPolicyGetPropertyType(propName);
1745             if (propType == Rm_policyPropType_ASSIGNMENTS) {
1746                 /* Found a resource node's assignment property.  Create an
1747                  * allocator node for the resource and populate it with a
1748                  * policy tree */
1749                 resName = fdt_get_name(policyDtb, nodeOffset, NULL);
1751                 newAllocNode = allocatorInitNode(rmInst, resName, &retVal);
1752                 if (newAllocNode) {
1753                     retVal = rmPolicyPopulateTree((Rm_Handle)rmInst,
1754                                                   newAllocNode->policyRoot,
1755                                                   policyDtb, resName);
1756                     if (retVal != RM_OK) {
1757                         goto errorExit;
1758                     }
1759                 } else {
1760                     goto errorExit;
1761                 }
1763                 /* Move on to next resource node */
1764                 break;
1765             } else if (propType == Rm_policyPropType_UNKNOWN) {
1766                 retVal = RM_ERROR_UNKNOWN_POLICY_RESOURCE_PROPERTY;
1767                 goto errorExit;
1768             }
1769             /* else: fall through to get next property since read property
1770              *       wasn't an assignment */
1772             propOffset = fdt_next_property_offset(policyDtb, propOffset);
1773         }
1774         if (propOffset < -FDT_ERR_NOTFOUND) {
1775             /* Error returned by LIBFDT */
1776             retVal = propOffset;
1777             goto errorExit;
1778         }
1780         nodeOffset = fdt_next_node(policyDtb, nodeOffset, &nodeDepth);
1781         if (nodeOffset < -FDT_ERR_NOTFOUND) {
1782             /* Error returned by LIBFDT */
1783             retVal = nodeOffset;
1784             goto errorExit;
1785         }
1786     }
1788 errorExit:
1789     return(retVal);
1792 /* FUNCTION PURPOSE: Initializes the allocator tree root
1793  ***********************************************************************
1794  * DESCRIPTION: Initializes the allocator tree root structure
1795  */
1796 static int32_t allocatorTreeRootInit(Rm_Inst *rmInst)
1798     Rm_AllocatorTree *root = NULL;
1799     int32_t           retVal = RM_OK;
1801     root = Rm_osalMalloc(sizeof(*root));
1802     if (root) {
1803         RB_INIT(root);
1804         rmInst->allocatorTree = root;
1805     } else {
1806         retVal = RM_ERROR_COULD_NOT_INIT_ALLOC_TREE;
1807     }
1808     return(retVal);
1811 /**********************************************************************
1812  ********************** Internal Functions ****************************
1813  **********************************************************************/
1815 /* FUNCTION PURPOSE: Finds an allocator
1816  ***********************************************************************
1817  * DESCRIPTION: Returns a pointer to an allocator that matches the 
1818  *              provided resource name.
1819  */
1820 Rm_AllocatorNode *rmAllocatorFind(Rm_Handle rmHandle, const char *resourceName)
1822     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1823     Rm_AllocatorTree *tree = rmInst->allocatorTree;
1824     Rm_AllocatorNode  findNode;
1826     memset((void *)&findNode, 0, sizeof(findNode));
1827     rm_strncpy(findNode.resourceName, resourceName, RM_NAME_MAX_CHARS);
1829     return(RB_FIND(_Rm_AllocatorTree, tree, &findNode));
1832 /* FUNCTION PURPOSE: Checks if a resource node is localized
1833  ***********************************************************************
1834  * DESCRIPTION: Checks if a resource node is localized.  A localized
1835  *              node is one that is free and has no neighboring nodes
1836  *              or neighboring nodes that do not have resource values
1837  *              contiguous with the node being checked.  The function
1838  *              will return RM_TRUE if the node is localized.  
1839  *              Otherwise, the function returns RM_FALSE
1840  */
1841 int rmAllocatorGetNodeLocalization(Rm_Handle rmHandle, char *resourceName,
1842                                    int32_t *resBase, uint32_t *resLen)
1844     uint32_t          allocSize;
1845     Rm_AllocatorNode *allocator = NULL;
1846     Rm_ResourceNode   findNode;
1847     Rm_ResourceNode  *matchingNode = NULL;
1848     Rm_ResourceNode  *neighborNode = NULL;
1849     int               nodeIsLocalized = RM_FALSE;
1851     allocator = rmAllocatorFind(rmHandle, resourceName);
1852     allocSize = rmPolicyGetCdAllocSize(allocator->policyRoot);
1854     /* Nothing to free back to server if policy never specified blocks could
1855      * be allocated to CD */
1856     if (allocSize) {
1857         memset((void *)&findNode, 0, sizeof(findNode));
1858         findNode.base = *resBase;
1859         findNode.length = *resLen;
1860         matchingNode = RB_FIND(_Rm_AllocatorResourceTree,
1861                                allocator->resourceRoot, &findNode);
1863         if (matchingNode) {
1864             /* Node can be freed back to Server from CD if:
1865              * - allocationCount == 0
1866              * - node's resource range is multiple of policy allocation size
1867              * - node's resource range boundaries are not contiguous with
1868              *   surrounding nodes */
1869             if (matchingNode->allocationCount) {
1870                 goto exitLocalization;
1871             }
1873             if (matchingNode->length % allocSize) {
1874                 goto exitLocalization;
1875             }
1877             /* Check left neighbor */
1878             neighborNode = RB_PREV(_Rm_AllocatorResourceTree,
1879                                    allocator->resourceRoot, matchingNode);
1880             if (neighborNode &&
1881                 allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1882                 goto exitLocalization; 
1883             }
1885             /* Check right neighbor */
1886             neighborNode = RB_NEXT(_Rm_AllocatorResourceTree,
1887                                    allocator->resourceRoot, matchingNode);
1888             if (neighborNode &&
1889                 allocatorResNodeBoundaryCompare(neighborNode, matchingNode)) {
1890                 goto exitLocalization; 
1891             }
1893             /* All localization checks passed.  Return the base and length of
1894              * localized node. */
1895             nodeIsLocalized = RM_TRUE;
1896             *resBase = matchingNode->base;
1897             *resLen = matchingNode->length;
1898         } else {
1899             nodeIsLocalized = RM_FALSE;
1900         }
1901     }
1903 exitLocalization:
1904     return(nodeIsLocalized);
1907 /* FUNCTION PURPOSE: Issues an allocator operation
1908  ***********************************************************************
1909  * DESCRIPTION: Issues an allocator preallocate, allocate, or free
1910  *              for an RM resource.
1911  */
1912 int32_t rmAllocatorOperation(Rm_Handle rmHandle, Rm_AllocatorOpInfo *opInfo)
1914     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
1915     Rm_AllocatorNode *allocator = NULL;
1916     int32_t           retVal;
1918     if ((allocator = rmAllocatorFind(rmHandle, opInfo->resourceInfo->name))) {
1919         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
1920             rmResourceTreeInv(allocator->resourceRoot);
1921         }
1923         if (opInfo->operation == Rm_allocatorOp_GET_STATUS) {
1924             retVal = allocatorStatus(rmHandle, allocator, opInfo);
1925         } else if ((opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_INIT) ||
1926                    (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE_USE)) {
1927             retVal = allocatorPreAllocate(rmHandle, allocator, opInfo);
1928         } else if ((opInfo->operation == Rm_allocatorOp_ALLOCATE_INIT) ||
1929                    (opInfo->operation == Rm_allocatorOp_ALLOCATE_USE)) {
1930             retVal = allocatorAllocate(rmHandle, allocator, opInfo);
1931         } else if (opInfo->operation == Rm_allocatorOp_FREE) {
1932             retVal = allocatorFree(rmHandle, allocator, opInfo);
1933         } else {
1934             retVal = RM_ERROR_INVALID_SERVICE_TYPE;
1935         }
1937         if ((rmInst->instType == Rm_instType_SHARED_SERVER) &&
1938             (opInfo->operation != Rm_allocatorOp_GET_STATUS) &&
1939             (retVal == RM_SERVICE_APPROVED)) {
1940             rmResourceTreeWb(allocator->resourceRoot);
1941         }
1942     } else {
1943         /* Resource could not be found in policy and/or allocator */
1944         retVal = RM_SERVICE_DENIED_RES_DOES_NOT_EXIST;
1945     }
1946     return(retVal);
1949 /* FUNCTION PURPOSE: Initializes the allocator tree
1950  ***********************************************************************
1951  * DESCRIPTION: Initializes a RM instance's allocator tree using the
1952  *              supplied GRL and policy
1953  */
1954 int32_t rmAllocatorTreeInit(Rm_Handle rmHandle, void *grlDtb,
1955                             void *policyDtb, void *linuxDtb)
1957     Rm_Inst *rmInst = (Rm_Inst *)rmHandle;
1958     int32_t  retVal = RM_OK;
1960     if ((retVal = allocatorTreeRootInit(rmInst)) != RM_OK) {
1961         goto errorExit;
1962     }
1964     if (grlDtb && policyDtb &&
1965         ((rmInst->instType == Rm_instType_SERVER) ||
1966          (rmInst->instType == Rm_instType_SHARED_SERVER))) {
1967         /* Create an allocator for each resource node in GRL.  Companion
1968          * policy info will be pulled and placed into policy tree */
1969         retVal = allocatorPopulateGrlBased(rmInst, grlDtb, policyDtb, linuxDtb);
1970     } else if (policyDtb &&
1971                ((rmInst->instType == Rm_instType_CLIENT_DELEGATE) ||
1972                 (rmInst->instType == Rm_instType_CLIENT))) {
1973         /* Create an allocator for each resource node in the policy.
1974          * Resource tree portion of the allocator will be NULL.  Resource
1975          * trees will be added at run time for Client Delegate instances.
1976          * Client instances with static policy just need allocators with
1977          * policy information for each resource. */
1978         retVal = allocatorPopulatePolicyBased(rmInst, policyDtb);
1979     } else if ((rmInst->instType != Rm_instType_CLIENT) &&
1980                (rmInst->instType != Rm_instType_SHARED_CLIENT)) {
1981         retVal = RM_ERROR_INVALID_ALLOCATOR_INIT;
1982     } else {
1983         retVal = RM_ERROR_INVALID_INST_TYPE;
1984     }
1986 errorExit:
1987     return(retVal);
1990 /* FUNCTION PURPOSE: Adds a node to a resource tree
1991  ***********************************************************************
1992  * DESCRIPTION: Adds a node to an allocator's resource tree based on the
1993  *              given base and length.
1994  */
1995 int32_t rmAllocatorAddResNode(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
1996                               int32_t resBase, uint32_t resLen)
1998     Rm_Inst         *rmInst = (Rm_Inst *)rmHandle;
1999     Rm_ResourceNode *resNode = NULL;
2000     int32_t retVal = RM_OK;
2002     if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2003         rmResourceTreeInv(allocator->resourceRoot);
2004     }
2006     if ((resNode = rmResourceNodeNew(resBase, resLen))) {
2007         if (RB_INSERT(_Rm_AllocatorResourceTree, allocator->resourceRoot,
2008                       resNode)) {
2009             retVal = RM_ERROR_RES_SPECIFIED_MORE_THAN_ONCE;
2010         }
2011     } else {
2012         retVal = RM_ERROR_MALLOC_FAILED_RES_NODE;
2013     }
2015     return(retVal);
2018 /* FUNCTION PURPOSE: Deletes a node from a resource tree
2019  ***********************************************************************
2020  * DESCRIPTION: Deletes a node from an allocator's resource tree based on the
2021  *              given base and length.
2022  */
2023 void rmAllocatorDeleteResNode(Rm_Handle rmHandle, Rm_AllocatorNode *allocator,
2024                               int32_t resBase, uint32_t resLen)
2026     Rm_Inst         *rmInst = (Rm_Inst *)rmHandle;
2027     Rm_ResourceNode  find;
2028     Rm_ResourceNode *match;
2030     memset((void *)&find, 0, sizeof(find));
2031     find.base = resBase;
2032     find.length = resLen;
2033     match = RB_FIND(_Rm_AllocatorResourceTree, allocator->resourceRoot,
2034                     &find);
2035     
2036     if (match) {
2037         RB_REMOVE(_Rm_AllocatorResourceTree, allocator->resourceRoot,
2038                   match);
2039         rmResourceNodeFree(match);
2040         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2041             rmResourceTreeWb(allocator->resourceRoot);
2042         }
2043     }
2046 /* FUNCTION PURPOSE: Deletes allocator tree
2047  ***********************************************************************
2048  * DESCRIPTION: Removes all resource nodes for each allocator node and then
2049  *              deletes the allocator tree root.
2050  */
2051 void rmAllocatorTreeDelete(Rm_Handle rmHandle)
2053     Rm_Inst          *rmInst = (Rm_Inst *)rmHandle;
2054     Rm_AllocatorTree *allocTree = rmInst->allocatorTree;
2055     Rm_AllocatorNode *allocNode;
2056     Rm_AllocatorNode *nextAllocNode;
2057     Rm_ResourceTree  *resTree;
2058     Rm_ResourceNode  *resNode;
2059     Rm_ResourceNode  *nextResNode;
2060     Rm_PolicyTree    *polTree;
2061     Rm_PolicyNode    *polNode;
2062     Rm_PolicyNode    *nextPolNode;
2064     if (allocTree) {
2065         if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2066             rmAllocatorTreeInv(allocTree);
2067         }
2069         for (allocNode = RB_MIN(_Rm_AllocatorTree, allocTree);
2070              allocNode != NULL;
2071              allocNode = nextAllocNode) {
2072             nextAllocNode = RB_NEXT(_Rm_AllocatorTree, allocTree, allocNode);
2074             resTree = allocNode->resourceRoot;
2075             polTree = allocNode->policyRoot;
2077             if (rmInst->instType == Rm_instType_SHARED_SERVER) {
2078                 rmResourceTreeInv(resTree);
2079                 rmPolicyTreeInv(polTree);
2080             }
2082             /* Delete each node in the resource tree */
2083             for (resNode = RB_MIN(_Rm_AllocatorResourceTree, resTree);
2084                  resNode != NULL;
2085                  resNode = nextResNode) {
2086                 nextResNode = RB_NEXT(_Rm_AllocatorResourceTree, resTree,
2087                                       resNode);
2088                 RB_REMOVE(_Rm_AllocatorResourceTree, resTree, resNode);
2089                 if (resNode->allocationCount) {
2090                     /* Delete all the owners in the resource's owner list */
2091                     allocatorResNodeOwnerClear(rmHandle, resNode);
2092                 }
2093                 rmResourceNodeFree(resNode);
2094             }
2095             Rm_osalFree((void *)resTree, sizeof(*resTree));
2097             /* Delete each node in the policy tree */
2098             for (polNode = RB_MIN(_Rm_AllocatorPolicyTree, polTree);
2099                  polNode != NULL;
2100                  polNode = nextPolNode) {
2101                 nextPolNode = RB_NEXT(_Rm_AllocatorPolicyTree, polTree,
2102                                       polNode);
2103                 RB_REMOVE(_Rm_AllocatorPolicyTree, polTree, polNode);
2104                 rmPolicyNodeFree(polNode);
2105             }
2106             Rm_osalFree((void *)polTree, sizeof(*polTree));
2108             RB_REMOVE(_Rm_AllocatorTree, allocTree, allocNode);
2109             rmAllocatorNodeFree(allocNode);
2110         }
2111         Rm_osalFree((void *)allocTree, sizeof(*allocTree));
2112         RM_SS_OBJ_WB(rmInst, rmInst, Rm_Inst);
2113     }