5f56ca10f7eda652a5d0f1224df5454387063bd3
[keystone-rtos/rm-lld.git] / src / rm_tree.c
1 /**
2  *   @file  rm_tree.c
3  *
4  *   @brief   
5  *      Resource Manager Tree Manipulation Source.
6  *
7  *  \par
8  *  ============================================================================
9  *  @n   (C) Copyright 2012-2013, 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 /* Standard includes */
43 #include <string.h>
45 /* RM external API includes */
46 #include <ti/drv/rm/rm.h>
48 /* RM internal API includes */
49 #include <ti/drv/rm/include/rm_internal.h>
50 #include <ti/drv/rm/include/rm_treeloc.h>
52 /* RM OSAL layer */
53 #include <rm_osal.h>
55 /**********************************************************************
56  ********************* NameServer Tree Functions **********************
57  **********************************************************************/
59 /* FUNCTION PURPOSE: Invalidates an entire NameServer tree
60  ***********************************************************************
61  * DESCRIPTION: Uses the cache handling versions of the RB tree
62  *              macros to walk an entire NameServer tree and invalidate
63  *              it.
64  */
65 void rmNameServerTreeInv(Rm_NameServerTree *treeRoot)
66 {
67     Rm_NameServerNode *node;
69     /* Invalidate the tree root */
70     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_NameServerTree));
71     /* Walk the tree which will invalidate each element in the tree */
72     node = RB_MIN_CACHED(_Rm_NameServerTree, treeRoot);
73     while (node) {
74         node = RB_NEXT_CACHED(_Rm_NameServerTree, treeRoot, node);
75     }
76 }
78 /* FUNCTION PURPOSE: Writebacks an entire NameServer tree
79  ***********************************************************************
80  * DESCRIPTION: Walks the entire NameServer tree writing back
81  *              each element to shared memory
82  */
83 void rmNameServerTreeWb(Rm_NameServerTree *treeRoot)
84 {
85     Rm_NameServerNode *node;
87     /* Writeback each element in the tree */
88     node = RB_MIN(_Rm_NameServerTree, treeRoot);
89     do {
90         Rm_osalEndMemAccess((void *)node, sizeof(Rm_NameServerNode));
91         node = RB_NEXT(_Rm_NameServerTree, treeRoot, node);
92     } while (node);
94     /* Writeback the tree root */
95     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_NameServerTree));
96 }
98 /* FUNCTION PURPOSE: Creates a new NameServer tree node
99  ***********************************************************************
100  * DESCRIPTION: Creates a new NameServer tree node with the
101  *              specified name and the resource values it is
102  *              tied to.
103  */
104 Rm_NameServerNode *rmNameServerNodeNew(Rm_NameServerNodeCfg *nodeCfg)
106     Rm_NameServerNode *newNode = NULL;
108     newNode = Rm_osalMalloc(sizeof(Rm_NameServerNode));
109     if (newNode) {
110         strncpy(newNode->objName, nodeCfg->objName, RM_NAME_MAX_CHARS);
111         strncpy(newNode->resourceName, nodeCfg->resourceName, RM_NAME_MAX_CHARS); 
112         newNode->resourceBase = nodeCfg->resourceBase;
113         newNode->resourceLength = nodeCfg->resourceLength;
114     }
115     
116     return(newNode);
119 /* FUNCTION PURPOSE: Deletes a NameServer tree node
120  ***********************************************************************
121  * DESCRIPTION: Deletes the specified NameServer tree node.
122  */
123 void rmNameServerNodeFree(Rm_NameServerNode *node)
125     if (node) {
126         Rm_osalFree((void *)node, sizeof(Rm_NameServerNode));
127     }
130 /* FUNCTION PURPOSE: Compares two NameServer tree nodes
131  ***********************************************************************
132  * DESCRIPTION: Returns the result of a comparison of two 
133  *              NameServer tree node names.
134  *              node1 name < node2 name --> return < 0
135  *              node1 name = node2 name --> return 0
136  *              node1 name > node2 name --> return > 0
137  */
138 int rmNameServerNodeCompare(Rm_NameServerNode *node1, Rm_NameServerNode *node2)
140     return(strncmp(node1->objName, node2->objName, RM_NAME_MAX_CHARS));
143 /* FUNCTION PURPOSE: Invalidates a NameServer tree node
144  ***********************************************************************
145  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
146  *              NameServer tree node.
147  */
148 void rmNameServerNodeInv(Rm_NameServerNode *node)
150     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_NameServerNode));
153 /* Generate the NameServer tree manipulation functions */
154 RB_GENERATE(_Rm_NameServerTree, _Rm_NameServerNode, linkage, rmNameServerNodeCompare, rmNameServerNodeInv);
156 /**********************************************************************
157  *************** Policy Valid Instance Tree Functions *****************
158  **********************************************************************/
160 /* FUNCTION PURPOSE: Invalidates an entire valid instance tree
161  ***********************************************************************
162  * DESCRIPTION: Uses the cache handling versions of the RB tree
163  *              macros to walk an entire valid instance tree and invalidate
164  *              it.
165  */
166 void rmPolicyValidInstTreeInv(Rm_PolicyValidInstTree *treeRoot)
168     Rm_PolicyValidInstNode *node;
170     /* Invalidate the tree root */
171     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
172     /* Walk the tree which will invalidate each element in the tree */
173     node = RB_MIN_CACHED(_Rm_PolicyValidInstTree, treeRoot);
174     while (node) {
175         node = RB_NEXT_CACHED(_Rm_PolicyValidInstTree, treeRoot, node);
176     }
179 /* FUNCTION PURPOSE: Writebacks an entire valid instance tree
180  ***********************************************************************
181  * DESCRIPTION: Walks the entire valid instance tree writing back
182  *              each element to shared memory
183  */
184 void rmPolicyValidInstTreeWb(Rm_PolicyValidInstTree *treeRoot)
186     Rm_PolicyValidInstNode *node;
188     /* Writeback each element in the tree */
189     node = RB_MIN(_Rm_PolicyValidInstTree, treeRoot);
190     do {
191         Rm_osalEndMemAccess((void *)node, sizeof(Rm_PolicyValidInstNode));
192         node = RB_NEXT(_Rm_PolicyValidInstTree, treeRoot, node);
193     } while (node);
195     /* Writeback the tree root */
196     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
199 /* FUNCTION PURPOSE: Creates a new valid instance tree node
200  ***********************************************************************
201  * DESCRIPTION: Creates a new valid instance tree node with the
202  *              specified name.
203  */
204 Rm_PolicyValidInstNode *rmPolicyValidInstNodeNew(char *instName)
206     Rm_PolicyValidInstNode *newNode = NULL;
208     newNode = Rm_osalMalloc(sizeof(Rm_PolicyValidInstNode));
209     
210     strncpy(newNode->name, instName, RM_NAME_MAX_CHARS);
211     newNode->allocRefCount = 0;
212     newNode->deletePending = RM_FALSE;
213     
214     return(newNode);
217 /* FUNCTION PURPOSE: Deletes a valid instance tree node
218  ***********************************************************************
219  * DESCRIPTION: Deletes the specified valind instance tree node
220  *              if it has zero allocation references.
221  */
222 void rmPolicyValidInstNodeFree(Rm_PolicyValidInstNode *node)
224  /* TODO: Add allocation reference count check when reference count addition/subtraction
225   *       bugs are resolved */
226  //   if (node->allocRefCount == 0) {
227         Rm_osalFree((void *)node, sizeof(Rm_PolicyValidInstNode));
228  //   }
231 /* FUNCTION PURPOSE: Compares two valid instance tree nodes
232  ***********************************************************************
233  * DESCRIPTION: Returns the result of a comparison of two 
234  *              valid instance tree node names.
235  *              node1 name < node2 name --> return < 0
236  *              node1 name = node2 name --> return 0
237  *              node1 name > node2 name --> return > 0
238  */
239 int rmPolicyValidInstNodeCompare(Rm_PolicyValidInstNode *node1, Rm_PolicyValidInstNode *node2)
241     return(strncmp(node1->name, node2->name, RM_NAME_MAX_CHARS));
244 /* FUNCTION PURPOSE: Invalidates a valid instance tree node
245  ***********************************************************************
246  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
247  *              valid instance tree node.
248  */
249 void rmPolicyValidInstNodeInv(Rm_PolicyValidInstNode *node)
251     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_PolicyValidInstNode));
254 /* Generate the valid instance tree manipulation functions */
255 RB_GENERATE(_Rm_PolicyValidInstTree, _Rm_PolicyValidInstNode, linkage, rmPolicyValidInstNodeCompare, rmPolicyValidInstNodeInv);
257 /**********************************************************************
258  ***************** Allocator Resource Tree Functions ******************
259  **********************************************************************/
261 /* FUNCTION PURPOSE: Invalidates an entire resource tree
262  ***********************************************************************
263  * DESCRIPTION: Uses the cache handling versions of the RB tree
264  *              macros to walk an entire resource tree and invalidate
265  *              it.
266  */
267 void rmResourceTreeInv(Rm_ResourceTree *treeRoot)
269     Rm_ResourceNode *node;
271     /* Invalidate the tree root */
272     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
273     /* Walk the tree which will invalidate each element in the tree */
274     node = RB_MIN_CACHED(_Rm_AllocatorResourceTree, treeRoot);
275     while (node) {
276         node = RB_NEXT_CACHED(_Rm_AllocatorResourceTree, treeRoot, node);
277     }
280 /* FUNCTION PURPOSE: Writebacks an entire resource tree
281  ***********************************************************************
282  * DESCRIPTION: Walks the entire resource tree writing back
283  *              each element to shared memory
284  */
285 void rmResourceTreeWb(Rm_ResourceTree *treeRoot)
287     Rm_ResourceNode *node;
289     /* Writeback each element in the tree */
290     node = RB_MIN(_Rm_AllocatorResourceTree, treeRoot);
291     do {
292         Rm_osalEndMemAccess((void *)node, sizeof(Rm_ResourceNode));
293         node = RB_NEXT(_Rm_AllocatorResourceTree, treeRoot, node);
294     } while (node);
296     /* Writeback the tree root */
297     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
300 /* FUNCTION PURPOSE: Creates a new resource tree node
301  ***********************************************************************
302  * DESCRIPTION: Creates a new resource tree node with the
303  *              specified name resource values.
304  */
305 Rm_ResourceNode *rmResourceNodeNew(uint32_t resourceBase, uint32_t resourceLength)
307     Rm_ResourceNode *newNode = NULL;
309     newNode = Rm_osalMalloc(sizeof(Rm_ResourceNode));
310     memset((void *)newNode, 0, sizeof(Rm_ResourceNode));
312     newNode->base = resourceBase;
313     newNode->length = resourceLength;
314     newNode->allocationCount = 0;
315     newNode->ownerList = NULL;
317     return(newNode);
320 /* FUNCTION PURPOSE: Deletes a resource tree node
321  ***********************************************************************
322  * DESCRIPTION: Deletes the specified resource tree node
323  *              if its allocation count is zero.
324  */
325 void rmResourceNodeFree(Rm_ResourceNode *node)
327     if (node->allocationCount == 0) {
328         Rm_osalFree((void *)node, sizeof(Rm_ResourceNode));
329     }
332 /* FUNCTION PURPOSE: Compares two resource tree nodes
333  ***********************************************************************
334  * DESCRIPTION: Returns the result of a comparison of two 
335  *              resource tree node value ranges.
336  *
337  *              |node1 range||node2 range| --> return < 0
338  *
339  *                 |node1 range|
340  *                   |node2 range|         --> return 0 (any overlap in ranges)
341  *
342  *              |node2 range||node1 range| --> return > 0
343  */
344 int rmResourceNodeCompare(Rm_ResourceNode *node1, Rm_ResourceNode *node2)
346     uint32_t node1End = node1->base + node1->length - 1;
347     uint32_t node2End = node2->base + node2->length - 1;
349     if (node1End < node2->base) {
350         /* End of node1 range is less than the start of node2's range.  Return a negative
351          * value */
352         return (-1);
353     }
354     else if (node1->base > node2End) {
355         /* Start of node1 range is after end of node2's range.  Return a positive value */
356         return (1);
357     }
358     else {
359         /* If neither of the latter conditions were satisfied there is some overlap between
360          * node1 and node2.  Return 0 since the application must handle this overlap. */
361         return (0);
362     }
365 /* FUNCTION PURPOSE: Invalidates a resource tree node
366  ***********************************************************************
367  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
368  *              resource tree node.
369  */
370 void rmResourceNodeInv(Rm_ResourceNode *node)
372     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_ResourceNode));
375 /* Generate the resource tree manipulation functions */
376 RB_GENERATE(_Rm_AllocatorResourceTree, _Rm_ResourceNode, linkage, rmResourceNodeCompare, rmResourceNodeInv)