Wrote tree allocate and free operations
[keystone-rtos/rm-lld.git] / src / rm.c
index 16b3dd72ebab462338aba2d5934295e6f44de774..1f1478086273f9b1210a24eae74ee55fc147cf31 100644 (file)
--- a/src/rm.c
+++ b/src/rm.c
@@ -79,9 +79,9 @@ const char   rmVersionStr[] = RM_VERSION_STR ":" __DATE__  ":" __TIME__;
  ************** Red-Black BBST Tree Allocator Functions ***************\r
  **********************************************************************/\r
 \r
-/* TODO: This needed? */\r
 /* Prototype for function that allocates new tree nodes */\r
-Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength)\r
+Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength, \r
+                                            char *allocatedTo)\r
 {\r
     Rm_ResourceTreeNode *newNode = NULL;\r
 \r
@@ -90,11 +90,11 @@ Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t reso
     /* Populate the RM relevant fields */\r
     newNode->base = resourceBase;\r
     newNode->length = resourceLength;\r
+    strcpy(newNode->allocatedTo, allocatedTo);\r
 \r
     return(newNode);\r
 }\r
 \r
-/* TODO: This needed? */\r
 /* Prototype for function that frees new tree nodes */\r
 void Rm_freeResourceTreeNode(Rm_ResourceTreeNode *treeNode)\r
 {\r
@@ -562,11 +562,7 @@ int32_t Rm_createTreeAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_Res
     /* Create a node in the tree for resource range and insert them into the tree. */\r
     while (range != NULL)\r
     {\r
-        treeNode = Rm_osalMalloc(sizeof(Rm_ResourceTreeNode));\r
-        treeNode->base = range->base;\r
-        treeNode->length = range->length;\r
-        /* Initialize the allocatedTo field to the NOT_ALLOCATED string */\r
-        strcpy(treeNode->allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+        Rm_newResourceTreeNode(range->base, range->length, RM_NOT_ALLOCATED_STRING);\r
 \r
         /* Insert the node into the tree */\r
         collidingNode = RB_INSERT(_Rm_ResourceTree, treeRootEntry, treeNode);\r
@@ -582,7 +578,7 @@ int32_t Rm_createTreeAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_Res
             {\r
                        nextNode = RB_NEXT(_Rm_ResourceTree, treeRootEntry, treeNode);\r
                        RB_REMOVE(_Rm_ResourceTree, treeRootEntry, nextNode);\r
-                       Rm_osalFree((void *)treeNode, sizeof(Rm_ResourceTreeNode));\r
+                Rm_freeResourceTreeNode(treeNode);\r
                }\r
             /* Delete the tree root entry and the allocator */\r
             Rm_osalFree((void *)treeRootEntry, sizeof(Rm_ResourceTree));\r
@@ -818,9 +814,89 @@ int32_t Rm_parseResourceNode(Rm_Inst *rmInst, void *globalResourceDtb, int32_t n
  * for the rm instance for the specified resource. */\r
 int32_t Rm_integerPreAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
-    \r
+    Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
+    Rm_IntegerEntry *resourceArray = root->resourceArrayBase;\r
+    uint16_t index, i;\r
+    bool resourcesValidated;\r
+    int32_t retVal = RM_SERVICE_PROCESSING;\r
+\r
+    /* Find the specified resource base within the allocator */\r
+    for (index = 0; index < root->numResourceElements; index++)\r
+    {\r
+        if (resourceArray[index].value == opInfo->resourceInfo->base)\r
+        {\r
+            /* Found the resource base in the allocator.  Break from the loop */\r
+            break;\r
+        }\r
+    } \r
+\r
+    /* Only execute the allocate operation if the resource base was found in the allocator\r
+     * and the base+length does not exceed the number of entries in the allocator */\r
+    if ((index + opInfo->resourceInfo->length) <= root->numResourceElements)\r
+    {\r
+        /* Search for a contiguous block of unallocated resources of length "length"\r
+         * and with the alignment specified */\r
+        while ((index + opInfo->resourceInfo->length) <= root->numResourceElements)\r
+        {\r
+            resourcesValidated = FALSE;            \r
+            \r
+            /* Does the resource base value satisfy the alignment? */\r
+            if ((resourceArray[index].value % opInfo->resourceInfo->alignment) == 0)\r
+            {\r
+                /* Check to see all the resource values in the requested range are free */\r
+                resourcesValidated = TRUE;\r
+                for (i = index; i < opInfo->resourceInfo->length; i++)\r
+                {\r
+                    if (strcmp(resourceArray[i].allocatedTo, RM_NOT_ALLOCATED_STRING) != 0)\r
+                    {\r
+                        /* A resource within the range was already allocated.  Update the\r
+                         * index to the resource after the allocated resource and continue \r
+                         * looking. */\r
+                        index = i + 1;\r
+                        resourcesValidated = FALSE;\r
+                        /* Break out of the for loop */\r
+                        break;\r
+                    }\r
+                }\r
+\r
+                if (resourcesValidated)\r
+                {\r
+                    /* Found a set of resources that satisfies the request requirements.  Return\r
+                     * the results to be tested against the policy.  If the policy approves the\r
+                     * resources will be allocated via the Rm_integerAllocate API. */\r
+                    opInfo->resourceInfo->base = resourceArray[index].value;\r
+                    /* Break out of the while loop */\r
+                    break;\r
+                }\r
+            }\r
+            else\r
+            {\r
+                /* Jump to the next resource value that satisfies the alignment */\r
+                for (; index < root->numResourceElements; index++)\r
+                {\r
+                    if ((resourceArray[index].value % opInfo->resourceInfo->alignment) == 0)\r
+                    {\r
+                        /* Found the next resource value that satisfies the alignment */\r
+                        break;\r
+                    }\r
+                }\r
+            }\r
+        }\r
+\r
+        if (!resourcesValidated)\r
+        {\r
+            retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
+        }\r
+    }\r
+    else\r
+    {\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
+    }\r
+\r
+    return(retVal);     \r
 }\r
 \r
+/* Assumes resource range for allocation has already been approved by the policy */\r
 int32_t Rm_integerAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
     Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
@@ -839,19 +915,19 @@ int32_t Rm_integerAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
     }\r
 \r
     /* Only execute the allocate operation if the resource base was found in the allocator\r
-     * and the base+range does not exceed the number of entries in the allocator */\r
-    if (resourceIndex + opInfo->resourceInfo->range <= root->numResourceElements)\r
+     * and the base+length does not exceed the number of entries in the allocator */\r
+    if ((resourceIndex + opInfo->resourceInfo->length) <= root->numResourceElements)\r
     {\r
-        /* Verify all resource values from base to base+range exist in the allocator and\r
+        /* Verify all resource values from base to base+length exist in the allocator and\r
          * are not allocated to another instance. */\r
         for (i = resourceIndex, j = opInfo->resourceInfo->base; \r
-             i < (resourceIndex + opInfo->resourceInfo->range);\r
+             i < (resourceIndex + opInfo->resourceInfo->length);\r
              i++, j++)\r
         {\r
             if (root->resourceArrayBase[i].value != j)\r
             {\r
                 /* A value in the range did not match. */\r
-                retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
                 resourcesValidated = FALSE;\r
                 break;\r
             }\r
@@ -866,8 +942,8 @@ int32_t Rm_integerAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
 \r
         if (resourcesValidated)\r
         {\r
-            /* Allocate all resources from base to base+range */\r
-            for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->range); i++)\r
+            /* Allocate all resources from base to base+length */\r
+            for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->length); i++)\r
             {\r
                 strcpy(root->resourceArrayBase[i].allocatedTo, opInfo->srcInstName);\r
             }\r
@@ -876,12 +952,13 @@ int32_t Rm_integerAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
     }\r
     else\r
     {\r
-        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
     }\r
 \r
     return(retVal); \r
 }\r
 \r
+/* Assumes resource range for free has already been approved by the policy */\r
 int32_t Rm_integerFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
     Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
@@ -900,20 +977,20 @@ int32_t Rm_integerFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
     }\r
 \r
     /* Only execute the free operation if the resource base was found in the allocator\r
-     * and the base+range does not exceed the number of entries in the allocator */\r
-    if (resourceIndex + opInfo->resourceInfo->range <= root->numResourceElements)\r
+     * and the base+length does not exceed the number of entries in the allocator */\r
+    if ((resourceIndex + opInfo->resourceInfo->length) <= root->numResourceElements)\r
     {\r
-        /* Verify all resource values from base to base+range exist in the allocator,\r
+        /* Verify all resource values from base to base+length exist in the allocator,\r
          * were not already free and were allocated to the instance that is the source\r
          * of the free request. */\r
         for (i = resourceIndex, j = opInfo->resourceInfo->base; \r
-             i < (resourceIndex + opInfo->resourceInfo->range);\r
+             i < (resourceIndex + opInfo->resourceInfo->length);\r
              i++, j++)\r
         {\r
             if (root->resourceArrayBase[i].value != j)\r
             {\r
                 /* A value in the range did not match. */\r
-                retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
                 resourcesValidated = FALSE;\r
                 break;\r
             }\r
@@ -936,8 +1013,8 @@ int32_t Rm_integerFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
 \r
         if (resourcesValidated)\r
         {\r
-            /* Free all resources from base to base+range */\r
-            for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->range); i++)\r
+            /* Free all resources from base to base+length */\r
+            for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->length); i++)\r
             {\r
                 strcpy(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING);\r
             }\r
@@ -946,7 +1023,7 @@ int32_t Rm_integerFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
     }\r
     else\r
     {\r
-        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
     }\r
 \r
     return(retVal);\r
@@ -961,14 +1038,354 @@ int32_t Rm_treePreAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)
 \r
 }\r
 \r
+/* Assume the policy has already approved of the allocation */\r
 int32_t Rm_treeAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
-    \r
+    Rm_ResourceTreeNode findNode;\r
+    Rm_ResourceTreeNode *matchingNode = NULL;\r
+    Rm_ResourceTreeNode *leftNode = NULL;\r
+    Rm_ResourceTreeNode *rightNode = NULL;\r
+    uint32_t findEnd, matchingEnd;\r
+    int32_t retVal;\r
+\r
+    /* Find the tree node that contains the specified resource range */\r
+    findNode.base = opInfo->resourceInfo->base;\r
+    findNode.length = opInfo->resourceInfo->length;\r
+    matchingNode = RB_FIND(_Rm_ResourceTree, allocator->allocatorRootEntry, &findNode);\r
+\r
+    if (matchingNode != NULL)\r
+    {\r
+        findEnd = findNode.base + findNode.length - 1;\r
+        matchingEnd = matchingNode->base + matchingNode->length - 1;\r
+        \r
+        /* Does the request range fit within the matching nodes entire range? */\r
+        if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd))\r
+        {\r
+            /* Handle requested resource range that is isolated to a single node\r
+             *\r
+             *\r
+             * base0                                  base0+length0-1\r
+             *   |<---------------length0------------------->|  => existing node\r
+             *         |<---------length1---------->|  => requested resources\r
+             *       base1                   base1+length1-1\r
+             */             \r
+            if (strcmp(matchingNode->allocatedTo, RM_NOT_ALLOCATED_STRING) == 0)\r
+            {\r
+                /* Resources are available - split up the node into potentially\r
+                 * three new nodes:\r
+                 * left node - free resources to left of newly allocated resources\r
+                 * middle node - newly allocated resources that satisfy the request\r
+                 * right node - free resources to the right of newly allocated resources\r
+                 *\r
+                 * There also may be combine possibilities to the left and right of the\r
+                 * matching node.  Need to extract those as well to check */\r
+                leftNode = RB_PREV(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+                rightNode = RB_NEXT(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+\r
+                /* Remove the matching node from the tree and the nodes to the left and\r
+                 * right of the matching node.  Removing from tree will not\r
+                 * wipe any of the base+length data in the node.  Can reuse since they won't\r
+                 * be freed */\r
+                RB_REMOVE(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+                if (leftNode)\r
+                {\r
+                    RB_REMOVE(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                }\r
+                if (rightNode)\r
+                {\r
+                    RB_REMOVE(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);\r
+                }\r
+\r
+                /* Create the left node if needed.  If the bases are equal the matchingNode can\r
+                 * be reused as the left bound of the range. */\r
+                if (findNode.base > matchingNode->base)\r
+                {\r
+                    /* Can the left node be combined with the node to the left of the matching\r
+                     * node */\r
+                    if (leftNode && (strcmp(leftNode->allocatedTo, opInfo->srcInstName) == 0))\r
+                    {\r
+                        /* Combine the left node and what's leftover on the left side of the \r
+                         * matchingNode range after the allocation */\r
+                        leftNode->length += (findNode.base - matchingNode->base);\r
+                    }\r
+                    else\r
+                    {\r
+                        /* Reinsert left node and create a new node to left of range to be allocated */\r
+                        if (leftNode)\r
+                        {\r
+                            RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                        }\r
+                        \r
+                        /* New left node attributes:\r
+                         * base: base of the matching node\r
+                         * length: base of requested resources - base of matching node */\r
+                        leftNode = Rm_newResourceTreeNode(matchingNode->base, findNode.base - matchingNode->base,\r
+                                                          RM_NOT_ALLOCATED_STRING);\r
+                    }\r
+\r
+                }\r
+\r
+                /* Create the right node if needed.  If the end ranges are equal the matchingNode\r
+                 * can be reused as the right bound of the range */\r
+                if (findEnd < matchingEnd)\r
+                {\r
+                    /* Can the right node be combined with the node to the right of the matching\r
+                     * node */\r
+                    if (rightNode && (strcmp(rightNode->allocatedTo, opInfo->srcInstName) == 0))\r
+                    {\r
+                        /* Combine the right node and what's leftover on the right side of the \r
+                         * matchingNode range after the allocation */\r
+                        rightNode->base = findNode.base + findNode.length;\r
+                        rightNode->length += (matchingEnd - findEnd);\r
+                    }\r
+                    else\r
+                    {\r
+                        /* Reinsert right node and create a new node to right of range to be allocated */\r
+                        if (rightNode)\r
+                        {\r
+                            RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);\r
+                        }\r
+                                            \r
+                        /* New right node attributes:\r
+                         * base: base of the requested resources + length of requested resources\r
+                         * length: right bound of matching node - right bound of request resources */\r
+                        rightNode = Rm_newResourceTreeNode(findNode.base + findNode.length,\r
+                                                           matchingEnd - findEnd, RM_NOT_ALLOCATED_STRING);\r
+                    }\r
+                }\r
+\r
+                /* Reinsert the left node into the tree if it was modified or created. */\r
+                if (leftNode)\r
+                {\r
+                    RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                }\r
+                /* Reinsert the right node into the tree if it was modified or created. */\r
+                if (rightNode)\r
+                {\r
+                    RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);\r
+                }\r
+\r
+                /* Base and length of matching node becomes the base and length of the requested resources */\r
+                matchingNode->base = findNode.base;                                    \r
+                matchingNode->length = findNode.length;\r
+                /* Reserve the resources and insert them into the tree */\r
+                strcpy(matchingNode->allocatedTo, opInfo->srcInstName);\r
+                RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+\r
+                retVal = RM_SERVICE_APPROVED_AND_COMPLETED;\r
+            }\r
+            else\r
+            {\r
+                /* A resource superset containing the requested range has\r
+                 * already been allocated. */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_ALLOCATED;\r
+            }\r
+        }\r
+        else\r
+        {\r
+            /* Request ranges that span multiple nodes signify resources are\r
+             * not available because nodes are combined into larger contiguous ranges\r
+             * on resource free operations. */\r
+            retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_ALLOCATED;\r
+        }\r
+    }\r
+    else\r
+    {\r
+        /* The requested resources could not be found in the allocator */\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
+    }\r
+\r
+    return(retVal);        \r
 }\r
 \r
+/* Assume policy has already approved of the free */\r
 int32_t Rm_treeFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
 {\r
+    Rm_ResourceTreeNode findNode;\r
+    Rm_ResourceTreeNode *matchingNode = NULL;\r
+    Rm_ResourceTreeNode *leftNode = NULL;\r
+    Rm_ResourceTreeNode *rightNode = NULL;\r
+    bool combineLeft = FALSE;\r
+    bool combineRight = FALSE;\r
+    uint32_t findEnd, matchingEnd;\r
+    int32_t retVal;\r
+\r
+    /* Find the tree node that contains the specified resource range */\r
+    findNode.base = opInfo->resourceInfo->base;\r
+    findNode.length = opInfo->resourceInfo->length;\r
+    matchingNode = RB_FIND(_Rm_ResourceTree, allocator->allocatorRootEntry, &findNode);\r
+\r
+    if (matchingNode != NULL)\r
+    {\r
+        findEnd = findNode.base + findNode.length - 1;\r
+        matchingEnd = matchingNode->base + matchingNode->length - 1;\r
+        \r
+        /* Does the free range fit within the matching nodes entire range?  It should\r
+         * either be the entire range or a subset set of the found range. (the latter\r
+         * satisfies the case where an entity allocated a contiguous block of resources\r
+         * then attempts to free a contiguous subset of the allocated block. */\r
+        if ((findNode.base >= matchingNode->base) && (findEnd <= matchingEnd))\r
+        {            \r
+            if (strcmp(matchingNode->allocatedTo, opInfo->srcInstName) == 0)\r
+            {\r
+                /* Resources can be freed */\r
+\r
+                if ((findNode.base == matchingNode->base) && (findEnd == matchingEnd))\r
+                {\r
+                    /* Case 1: free range equals allocated matched node exactly. Attempt to combine \r
+                     *         the range to be freed with the resource nodes to the left and\r
+                     *         right of the free range.\r
+                     *\r
+                     * |<--left node-->||<---matched node--->||<--right node-->|\r
+                     *                  |<---free request--->|\r
+                     */ \r
+\r
+                    leftNode = RB_PREV(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+                    rightNode = RB_NEXT(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+\r
+                    /* Remove the matching node from the tree and the nodes to the left and\r
+                     * right of the matching node.  Removing from tree will not\r
+                     * wipe any of the base+length data in the node.  Can reuse since they won't\r
+                     * be freed */\r
+                    RB_REMOVE(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+                    if (leftNode)\r
+                    {\r
+                        RB_REMOVE(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                    }\r
+                    if (rightNode)\r
+                    {\r
+                        RB_REMOVE(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);\r
+                    }\r
+\r
+                    /* See if the left or right or both nodes can be combined with the matching\r
+                     * node that will be freed. */\r
+                    if (leftNode && (strcmp(leftNode->allocatedTo, RM_NOT_ALLOCATED_STRING) == 0))\r
+                    {\r
+                        /* Combine the left node and the matching node */\r
+                        combineLeft = TRUE;\r
+                    }\r
+                    if (rightNode && (strcmp(rightNode->allocatedTo, RM_NOT_ALLOCATED_STRING) == 0))\r
+                    {\r
+                        /* Combine the right node and the matching node */\r
+                        combineRight = TRUE;\r
+                    }\r
+\r
+                    /* Perform any combines, insert the leftover nodes, and free any memory associated\r
+                     * with any nodes that weren't reinserted into the tree */\r
+                    if (combineLeft && combineRight)\r
+                    {\r
+                        /* Combine all three nodes into the matchingNode.  Insert the freed cumulative\r
+                         * matching node and delete the memory for the old left and right nodes */\r
+                        matchingNode->base = leftNode->base;\r
+                        matchingNode->length = leftNode->length + matchingNode->length + rightNode->length;\r
+\r
+                        Rm_freeResourceTreeNode(leftNode);\r
+                        Rm_freeResourceTreeNode(rightNode);                        \r
+                    }\r
+                    else if (combineLeft)\r
+                    {\r
+                        /* Combine the left and matching nodes.  Reinsert the right. */\r
+                        matchingNode->base = leftNode->base;\r
+                        matchingNode->length += leftNode->length;\r
+                        \r
+                        Rm_freeResourceTreeNode(leftNode);\r
+                        RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);                        \r
+                    }\r
+                    else if (combineRight)\r
+                    {\r
+                        /* Combine the right and matching nodes.  Reinsert the left. */\r
+                        matchingNode->length += rightNode->length;\r
+                        \r
+                        Rm_freeResourceTreeNode(rightNode);\r
+                        RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                    }\r
+                    else\r
+                    {\r
+                        /* Combine cannot be performed.  Reinsert the left and right nodes then\r
+                         * free the matching node and reinsert it */\r
+                        RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                        RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);\r
+                    }\r
+\r
+                    /* No matter the combine route taken the matching node will always be declared\r
+                     * free and reinserted */\r
+                    strcpy(matchingNode->allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+                    RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);                    \r
+                }\r
+                else\r
+                {\r
+                    /* Case 2: free range is less than range in matched node. Need to split\r
+                     *         the matched node into three nodes.\r
+                     *\r
+                     * |<----------matched node---------->|\r
+                     *        |<---free request--->|\r
+                     */ \r
+\r
+                    /* Create the left node if needed.  If the bases are equal the matchingNode can\r
+                     * be reused as the left bound of the range. */\r
+                    if (findNode.base > matchingNode->base)\r
+                    {\r
+                        /* New left node attributes:\r
+                         * base: base of the matching node\r
+                         * length: base of requested resources - base of matching node */\r
+                        leftNode = Rm_newResourceTreeNode(matchingNode->base, findNode.base - matchingNode->base,\r
+                                                          matchingNode->allocatedTo); \r
+                    }\r
+\r
+                    /* Create the right node if needed.  If the end ranges are equal the matchingNode\r
+                     * can be reused as the right bound of the range */\r
+                    if (findEnd < matchingEnd)\r
+                    {                       \r
+                        /* New right node attributes:\r
+                         * base: base of the requested resources + length of requested resources\r
+                         * length: right bound of matching node - right bound of request resources */\r
+                        rightNode = Rm_newResourceTreeNode(findNode.base + findNode.length,\r
+                                                           matchingEnd - findEnd, matchingNode->allocatedTo);\r
+                    }\r
+\r
+                    /* Insert the left node into the tree if it was created. */\r
+                    if (leftNode)\r
+                    {\r
+                        RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, leftNode);\r
+                    }\r
+                    /* Insert the right node into the tree if it was created. */\r
+                    if (rightNode)\r
+                    {\r
+                        RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, rightNode);\r
+                    }\r
+\r
+                    /* Base and length of matching node becomes the base and length of the freed resources */\r
+                    matchingNode->base = findNode.base;                                    \r
+                    matchingNode->length = findNode.length;\r
+                    /* Free the resources and insert them into the tree */\r
+                    strcpy(matchingNode->allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+                    RB_INSERT(_Rm_ResourceTree, allocator->allocatorRootEntry, matchingNode);\r
+                }\r
+\r
+                retVal = RM_SERVICE_APPROVED_AND_COMPLETED;\r
+            }\r
+            else\r
+            {\r
+                /* The matching allocated range to be freed was allocated to a different instance. */\r
+                retVal = RM_SERVICE_DENIED_RESOURCE_NOT_ALLOCATED_TO_INSTANCE_REQUESTING_THE_SERVICE;\r
+            }\r
+\r
+        }\r
+        else\r
+        {\r
+            /* Free resource range crosses over node boundaries.  This signifies a\r
+             * free of both allocated and unallocated resources since nodes are combined\r
+             * on allocate and free operations if possible. */\r
+            retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_FREE;\r
+        }\r
+    }\r
+    else\r
+    {\r
+        /* The free resources could not be found in the allocator */\r
+        retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST;\r
+    }\r
 \r
+    return(retVal);  \r
 }\r
 \r
 int32_t Rm_allocatorOperation(Rm_Inst *rmInst, Rm_AllocatorOpInfo *opInfo)\r
@@ -990,7 +1407,7 @@ int32_t Rm_allocatorOperation(Rm_Inst *rmInst, Rm_AllocatorOpInfo *opInfo)
         {\r
             if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE)\r
             {\r
-                retVal = Rm_integerPreAllocateUnspecified(allocator, opInfo);\r
+                retVal = Rm_integerPreAllocate(allocator, opInfo);\r
             }            \r
             else if (opInfo->operation == Rm_allocatorOp_ALLOCATE)\r
             {\r
@@ -1005,7 +1422,7 @@ int32_t Rm_allocatorOperation(Rm_Inst *rmInst, Rm_AllocatorOpInfo *opInfo)
         {\r
             if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE)\r
             {\r
-                retVal = Rm_treePreAllocateUnspecified(allocator, opInfo);\r
+                retVal = Rm_treePreAllocate(allocator, opInfo);\r
             }               \r
             else if (opInfo->operation == Rm_allocatorOp_ALLOCATE)\r
             {\r
@@ -1102,7 +1519,7 @@ void Rm_allocationHandler (Rm_Inst *rmInst, Rm_Transaction *transaction)
 \r
             transaction->state = approve or deny reason;\r
             transaction->resourceInfo.base = ...;\r
-            transaction->resourceInfo.range = ...;\r
+            transaction->resourceInfo.length = ...;\r
 \r
             /* If source instance name does not match the current instance\r
              * name the allocation request came from a Client.  The result\r
@@ -1176,7 +1593,7 @@ void Rm_freeHandler (Rm_Inst *rmInst, Rm_Transaction *transaction)
             \r
         transaction->state = approve or deny reason;\r
         transaction->resourceInfo.base = ...;\r
-        transaction->resourceInfo.range = ...;\r
+        transaction->resourceInfo.length = ...;\r
 \r
         /* If source instance name does not match the current instance\r
          * name the allocation request came from a client.  The result\r