summary | shortlog | log | commit | commitdiff | tree
raw | patch | inline | side by side (parent: 3522411)
raw | patch | inline | side by side (parent: 3522411)
| author | Justin Sobota <jsobota@ti.com> | |
| Wed, 12 Dec 2012 01:21:13 +0000 (20:21 -0500) | ||
| committer | Justin Sobota <jsobota@ti.com> | |
| Wed, 12 Dec 2012 01:21:13 +0000 (20:21 -0500) |
| include/rm_loc.h | patch | blob | history | |
| rm_services.h | patch | blob | history | |
| src/rm.c | patch | blob | history | |
| src/rm_services.c | patch | blob | history |
diff --git a/include/rm_loc.h b/include/rm_loc.h
index 18717972c76af0f180fcaef4c60691ca239fc741..061a9ba95d3af848ff4bbe549be8f46f2224eef7 100644 (file)
--- a/include/rm_loc.h
+++ b/include/rm_loc.h
/** If applicable, start of resource range affected by command. If
* RM_RESOURCE_UNSPECIFIED is assigned the higher level RM agent*/
int32_t base;
- /** If applicable, range of specified resource, starting from base, affected by command */
- uint32_t range;
+ /** If applicable, number of specified resource, starting from base, affected by command */
+ uint32_t length;
/** If applicable, the alignment of the resource affected by the command */
int32_t alignment;
/** If applicable, the NameServer name assigned to the specified
typedef RB_HEAD(_Rm_ResourceTree, _Rm_ResourceTreeNode) Rm_ResourceTree;
/* Prototype for function that allocates new tree nodes */
-Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength);
+Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength,
+ char *allocatedTo);
/* Prototype for function that frees new tree nodes */
void Rm_freeResourceTreeNode(Rm_ResourceTreeNode *treeNode);
/* Prototype for tree node comparison function
diff --git a/rm_services.h b/rm_services.h
index f9914adbeaad9206c4f98fbf5f9ae2f1eaaefca5..194969189764e56fe7174697263eb4b678872ff2 100644 (file)
--- a/rm_services.h
+++ b/rm_services.h
#define RM_SERVICE_DENIED_RESOURCE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN)
/** A resource value within the specifed base+range could not be found within the resource's
* allocator. No action was taken on the resources. */
-#define RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN+1)
+#define RM_SERVICE_DENIED_RESOURCE_VALUE_RANGE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN+1)
/** A resource value within the specifed base+range was not allocated to the RM instance
* that is the source of the request. No action was taken on the resources. */
#define RM_SERVICE_DENIED_RESOURCE_NOT_ALLOCATED_TO_INSTANCE_REQUESTING_THE_SERVICE (RM_SERVICE_DENIED_BEGIN+2)
/** The base value of the returned resource. In the case of a block resource allocation
* response this field will contain the base value of the block. */
int32_t resourceBase;
- /** The range of resources starting from resourceBase allocated in block requests */
- uint32_t resourceRange;
+ /** The number of resources starting from resourceBase allocated in block requests */
+ uint32_t resourceLength;
} Rm_ServiceRespInfo;
/**
#define RM_RESOURCE_BASE_UNSPECIFIED (-1)
/** The resource base value. */
int32_t resourceBase;
- /** The range of the specified resource to be allocated starting from
+ /** The number of the specified resource to be allocated starting from
* resourceBase. Will be greater than one only for block allocate
* and free service requests. */
- uint32_t resourceRange;
+ uint32_t resourceLength;
/** An allocate service can be requested with an unspecified resource alignment.
* WARNING: Only applicapable if resourceBase is unspecified
*
diff --git a/src/rm.c b/src/rm.c
index 16b3dd72ebab462338aba2d5934295e6f44de774..1f1478086273f9b1210a24eae74ee55fc147cf31 100644 (file)
--- a/src/rm.c
+++ b/src/rm.c
************** 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
\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
}\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
\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
}\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
{\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
{\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
\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
\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
diff --git a/src/rm_services.c b/src/rm_services.c
index fbe8119cd12ffa87294f2cf7f7fd087d99615bf2..6d413246b2b2fb29f45f8993439bff3057462cd3 100644 (file)
--- a/src/rm_services.c
+++ b/src/rm_services.c
transaction->state = RM_SERVICE_PROCESSING;
strcpy(&(transaction->resourceInfo.name)[0], serviceRequest->resourceName);
transaction->resourceInfo.base = serviceRequest->resourceBase;
- transaction->resourceInfo.range = serviceRequest->resourceRange;
+ transaction->resourceInfo.length = serviceRequest->resourceLength;
transaction->resourceInfo.alignment = serviceRequest->resourceAlignment;
strcpy(&(transaction->resourceInfo.nsName)[0], serviceRequest->resourceNsName);
(transaction->type == Rm_service_RESOURCE_ALLOCATE_BY_NAME))
{
serviceResponse->resourceBase = transaction->resourceInfo.base;
- serviceResponse->resourceRange = transaction->resourceInfo.range;
+ serviceResponse->resourceLength = transaction->resourceInfo.length;
}
/* Delete the transaction since a response was received immediately */
(transaction->type == Rm_service_RESOURCE_ALLOCATE_BY_NAME)))
{
serviceResponse.resourceBase = transaction->resourceInfo.base;
- serviceResponse.resourceRange = transaction->resourceInfo.range;
+ serviceResponse.resourceLength = transaction->resourceInfo.length;
}
/* Issue the callback to the requesting component with the response information */