bc332090ef835f75d0bfc474893f8a748f96d0fc
[keystone-rtos/rm-lld.git] / src / rm_tree.c
1 /**
2  *   @file  rm_tree.c
3  *
4  *   @brief   
5  *      Resource Manager Tree Manipulation.
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 API includes */
43 #include <ti/drv/rm/rm.h>
45 /* RM internal API includes */
46 #include <ti/drv/rm/include/rm_internal.h>
47 #include <ti/drv/rm/include/rm_treeloc.h>
49 /* RM OSAL layer */
50 #include <rm_osal.h>
52 /**********************************************************************
53  ********************* NameServer Tree Functions **********************
54  **********************************************************************/
56 /* FUNCTION PURPOSE: Invalidates an entire NameServer tree
57  ***********************************************************************
58  * DESCRIPTION: Uses the cache handling versions of the RB tree
59  *              macros to walk an entire NameServer tree and invalidate
60  *              it.
61  */
62 void rmNameServerTreeInv(Rm_NameServerTree *treeRoot)
63 {
64     Rm_NameServerNode *node;
66     /* Invalidate the tree root */
67     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_NameServerTree));
68     /* Walk the tree which will invalidate each element in the tree */
69     node = RB_MIN_CACHED(_Rm_NameServerTree, treeRoot);
70     while (node) {
71         node = RB_NEXT_CACHED(_Rm_NameServerTree, treeRoot, node);
72     }
73 }
75 /* FUNCTION PURPOSE: Writebacks an entire NameServer tree
76  ***********************************************************************
77  * DESCRIPTION: Walks the entire NameServer tree writing back
78  *              each element to shared memory
79  */
80 void rmNameServerTreeWb(Rm_NameServerTree *treeRoot)
81 {
82     Rm_NameServerNode *node;
84     /* Writeback each element in the tree */
85     node = RB_MIN(_Rm_NameServerTree, treeRoot);
86     do {
87         Rm_osalEndMemAccess((void *)node, sizeof(Rm_NameServerNode));
88         node = RB_NEXT(_Rm_NameServerTree, treeRoot, node);
89     } while (node);
91     /* Writeback the tree root */
92     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_NameServerTree));
93 }
95 /* FUNCTION PURPOSE: Creates a new NameServer tree node
96  ***********************************************************************
97  * DESCRIPTION: Creates a new NameServer tree node with the
98  *              specified name and the resource values it is
99  *              tied to.
100  */
101 Rm_NameServerNode *rmNameServerNodeNew(Rm_NameServerNodeCfg *nodeCfg)
103     Rm_NameServerNode *newNode = NULL;
105     newNode = Rm_osalMalloc(sizeof(Rm_NameServerNode));
106     if (newNode) {
107         rm_strncpy(newNode->objName, nodeCfg->objName, RM_NAME_MAX_CHARS);
108         rm_strncpy(newNode->resourceName, nodeCfg->resourceName,
109                    RM_NAME_MAX_CHARS);
110         newNode->resourceBase = nodeCfg->resourceBase;
111         newNode->resourceLength = nodeCfg->resourceLength;
112     }
114     return(newNode);
117 /* FUNCTION PURPOSE: Deletes a NameServer tree node
118  ***********************************************************************
119  * DESCRIPTION: Deletes the specified NameServer tree node.
120  */
121 void rmNameServerNodeFree(Rm_NameServerNode *node)
123     if (node) {
124         Rm_osalFree((void *)node, sizeof(*node));
125     }
128 /* FUNCTION PURPOSE: Compares two NameServer tree nodes
129  ***********************************************************************
130  * DESCRIPTION: Returns the result of a comparison of two 
131  *              NameServer tree node names.
132  *              node1 name < node2 name --> return < 0
133  *              node1 name = node2 name --> return 0
134  *              node1 name > node2 name --> return > 0
135  */
136 int rmNameServerNodeCompare(Rm_NameServerNode *node1, Rm_NameServerNode *node2)
138     return(strncmp(node1->objName, node2->objName, RM_NAME_MAX_CHARS));
141 /* FUNCTION PURPOSE: Invalidates a NameServer tree node
142  ***********************************************************************
143  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
144  *              NameServer tree node.
145  */
146 void rmNameServerNodeInv(Rm_NameServerNode *node)
148     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_NameServerNode));
151 /* Generate the NameServer tree manipulation functions */
152 RB_GENERATE(_Rm_NameServerTree, _Rm_NameServerNode, linkage,
153             rmNameServerNodeCompare, rmNameServerNodeInv);
155 /**********************************************************************
156  *************** Policy Valid Instance Tree Functions *****************
157  **********************************************************************/
159 /* FUNCTION PURPOSE: Invalidates an entire valid instance tree
160  ***********************************************************************
161  * DESCRIPTION: Uses the cache handling versions of the RB tree
162  *              macros to walk an entire valid instance tree and invalidate
163  *              it.
164  */
165 void rmPolicyValidInstTreeInv(Rm_PolicyValidInstTree *treeRoot)
167     Rm_PolicyValidInstNode *node;
169     /* Invalidate the tree root */
170     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
171     /* Walk the tree which will invalidate each element in the tree */
172     node = RB_MIN_CACHED(_Rm_PolicyValidInstTree, treeRoot);
173     while (node) {
174         node = RB_NEXT_CACHED(_Rm_PolicyValidInstTree, treeRoot, node);
175     }
178 /* FUNCTION PURPOSE: Writebacks an entire valid instance tree
179  ***********************************************************************
180  * DESCRIPTION: Walks the entire valid instance tree writing back
181  *              each element to shared memory
182  */
183 void rmPolicyValidInstTreeWb(Rm_PolicyValidInstTree *treeRoot)
185     Rm_PolicyValidInstNode *node;
187     /* Writeback each element in the tree */
188     node = RB_MIN(_Rm_PolicyValidInstTree, treeRoot);
189     do {
190         Rm_osalEndMemAccess((void *)node, sizeof(Rm_PolicyValidInstNode));
191         node = RB_NEXT(_Rm_PolicyValidInstTree, treeRoot, node);
192     } while (node);
194     /* Writeback the tree root */
195     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
198 /* FUNCTION PURPOSE: Creates a new valid instance tree node
199  ***********************************************************************
200  * DESCRIPTION: Creates a new valid instance tree node with the
201  *              specified name.
202  */
203 Rm_PolicyValidInstNode *rmPolicyValidInstNodeNew(char *instName)
205     Rm_PolicyValidInstNode *newNode = NULL;
207     newNode = Rm_osalMalloc(sizeof(Rm_PolicyValidInstNode));
209     rm_strncpy(newNode->name, instName, RM_NAME_MAX_CHARS);
210     newNode->allocRefCount = 0;
211     newNode->deletePending = RM_FALSE;
213     return(newNode);
216 /* FUNCTION PURPOSE: Deletes a valid instance tree node
217  ***********************************************************************
218  * DESCRIPTION: Deletes the specified valind instance tree node
219  *              if it has zero allocation references.
220  */
221 void rmPolicyValidInstNodeFree(Rm_PolicyValidInstNode *node)
223  /* TODO: Add allocation reference count check when reference count
224   *       addition/subtraction bugs are resolved */
225  //   if (node->allocRefCount == 0) {
226         Rm_osalFree((void *)node, sizeof(*node));
227  //   }
230 /* FUNCTION PURPOSE: Compares two valid instance tree nodes
231  ***********************************************************************
232  * DESCRIPTION: Returns the result of a comparison of two 
233  *              valid instance tree node names.
234  *              node1 name < node2 name --> return < 0
235  *              node1 name = node2 name --> return 0
236  *              node1 name > node2 name --> return > 0
237  */
238 int rmPolicyValidInstNodeCompare(Rm_PolicyValidInstNode *node1,
239                                  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,
256             rmPolicyValidInstNodeCompare, rmPolicyValidInstNodeInv);
258 /**********************************************************************
259  ***************** Allocator Resource Tree Functions ******************
260  **********************************************************************/
262 /* FUNCTION PURPOSE: Invalidates an entire resource tree
263  ***********************************************************************
264  * DESCRIPTION: Uses the cache handling versions of the RB tree
265  *              macros to walk an entire resource tree and invalidate
266  *              it.
267  */
268 void rmResourceTreeInv(Rm_ResourceTree *treeRoot)
270     Rm_ResourceNode *node;
272     /* Invalidate the tree root */
273     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
274     /* Walk the tree which will invalidate each element in the tree */
275     node = RB_MIN_CACHED(_Rm_AllocatorResourceTree, treeRoot);
276     while (node) {
277         node = RB_NEXT_CACHED(_Rm_AllocatorResourceTree, treeRoot, node);
278     }
281 /* FUNCTION PURPOSE: Writebacks an entire resource tree
282  ***********************************************************************
283  * DESCRIPTION: Walks the entire resource tree writing back
284  *              each element to shared memory
285  */
286 void rmResourceTreeWb(Rm_ResourceTree *treeRoot)
288     Rm_ResourceNode *node;
290     /* Writeback each element in the tree */
291     node = RB_MIN(_Rm_AllocatorResourceTree, treeRoot);
292     do {
293         Rm_osalEndMemAccess((void *)node, sizeof(Rm_ResourceNode));
294         node = RB_NEXT(_Rm_AllocatorResourceTree, treeRoot, node);
295     } while (node);
297     /* Writeback the tree root */
298     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
301 /* FUNCTION PURPOSE: Creates a new resource tree node
302  ***********************************************************************
303  * DESCRIPTION: Creates a new resource tree node with the
304  *              specified name resource values.
305  */
306 Rm_ResourceNode *rmResourceNodeNew(uint32_t resourceBase, 
307                                    uint32_t resourceLength)
309     Rm_ResourceNode *newNode = NULL;
311     newNode = Rm_osalMalloc(sizeof(Rm_ResourceNode));
312     memset((void *)newNode, 0, sizeof(Rm_ResourceNode));
314     newNode->base = resourceBase;
315     newNode->length = resourceLength;
316     newNode->allocationCount = 0;
317     newNode->ownerList = NULL;
319     return(newNode);
322 /* FUNCTION PURPOSE: Deletes a resource tree node
323  ***********************************************************************
324  * DESCRIPTION: Deletes the specified resource tree node
325  *              if its allocation count is zero.
326  */
327 void rmResourceNodeFree(Rm_ResourceNode *node)
329     if (node->allocationCount == 0) {
330         Rm_osalFree((void *)node, sizeof(*node));
331     }
334 /* FUNCTION PURPOSE: Compares two resource tree nodes
335  ***********************************************************************
336  * DESCRIPTION: Returns the result of a comparison of two 
337  *              resource tree node value ranges.
338  *
339  *              |node1 range||node2 range| --> return < 0
340  *
341  *                 |node1 range|
342  *                   |node2 range|         --> return 0 (any overlap in ranges)
343  *
344  *              |node2 range||node1 range| --> return > 0
345  */
346 int rmResourceNodeCompare(Rm_ResourceNode *node1, Rm_ResourceNode *node2)
348     uint32_t node1End = node1->base + node1->length - 1;
349     uint32_t node2End = node2->base + node2->length - 1;
351     if (node1End < node2->base) {
352         /* End of node1 range is less than the start of node2's range.  Return
353          * a negative value */
354         return(-1);
355     }
356     else if (node1->base > node2End) {
357         /* Start of node1 range is after end of node2's range.  Return a
358          * positive value */
359         return(1);
360     }
361     else {
362         /* If neither of the latter conditions were satisfied there is some
363          * overlap between node1 and node2.  Return 0 since the application
364          * must handle this overlap. */
365         return(0);
366     }
369 /* FUNCTION PURPOSE: Invalidates a resource tree node
370  ***********************************************************************
371  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
372  *              resource tree node.
373  */
374 void rmResourceNodeInv(Rm_ResourceNode *node)
376     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_ResourceNode));
379 /* Generate the resource tree manipulation functions */
380 RB_GENERATE(_Rm_AllocatorResourceTree, _Rm_ResourceNode, linkage,
381             rmResourceNodeCompare, rmResourceNodeInv);
383 /**********************************************************************
384  ********************* Allocator Tree Functions ***********************
385  **********************************************************************/
387 /* FUNCTION PURPOSE: Invalidates an entire allocator tree
388  ***********************************************************************
389  * DESCRIPTION: Uses the cache handling versions of the RB tree
390  *              macros to walk and invalidate an entire allocator tree.
391  */
392 void rmAllocatorTreeInv(Rm_AllocatorTree *treeRoot)
394     Rm_AllocatorNode *node;
396     /* Invalidate the tree root */
397     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_AllocatorTree));
398     /* Walk the tree which will invalidate each element in the tree */
399     node = RB_MIN_CACHED(_Rm_AllocatorTree, treeRoot);
400     while (node) {
401         node = RB_NEXT_CACHED(_Rm_AllocatorTree, treeRoot, node);
402     }
405 /* FUNCTION PURPOSE: Writebacks an entire allocator tree
406  ***********************************************************************
407  * DESCRIPTION: Walks the entire allocator tree writing back
408  *              each element to shared memory
409  */
410 void rmAllocatorTreeWb(Rm_AllocatorTree *treeRoot)
412     Rm_AllocatorNode *node;
414     /* Writeback each element in the tree */
415     node = RB_MIN(_Rm_AllocatorTree, treeRoot);
416     do {
417         Rm_osalEndMemAccess((void *)node, sizeof(Rm_AllocatorNode));
418         node = RB_NEXT(_Rm_AllocatorTree, treeRoot, node);
419     } while (node);
421     /* Writeback the tree root */
422     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_AllocatorTree));
425 /* FUNCTION PURPOSE: Creates a new allocator node
426  ***********************************************************************
427  * DESCRIPTION: Creates a new allocator node with the
428  *              specified resource name.
429  */
430 Rm_AllocatorNode *rmAllocatorNodeNew(const char *resourceName)
432     Rm_AllocatorNode *newNode = NULL;
434     newNode = Rm_osalMalloc(sizeof(Rm_AllocatorNode));
436     rm_strncpy(newNode->resourceName, resourceName, RM_NAME_MAX_CHARS);
437     newNode->resourceRootEntry = NULL;
439     return(newNode);
442 /* FUNCTION PURPOSE: Deletes an allocator node
443  ***********************************************************************
444  * DESCRIPTION: Deletes the specified allocator node.
445  */
446 void rmAllocatorNodeFree(Rm_AllocatorNode *node)
448     Rm_osalFree((void *)node, sizeof(*node));
451 /* FUNCTION PURPOSE: Compares two allocator nodes
452  ***********************************************************************
453  * DESCRIPTION: Returns the result of a comparison of two
454  *              allocator node resource names.
455  *              node1 name < node2 name --> return < 0
456  *              node1 name = node2 name --> return 0
457  *              node1 name > node2 name --> return > 0
458  */
459 int rmAllocatorNodeCompare(Rm_AllocatorNode *node1, Rm_AllocatorNode *node2)
461     return(strncmp(node1->resourceName, node2->resourceName,
462                    RM_NAME_MAX_CHARS));
465 /* FUNCTION PURPOSE: Invalidates an allocator tree node
466  ***********************************************************************
467  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
468  *              allocator tree node.
469  */
470 void rmAllocatorNodeInv(Rm_AllocatorNode *node)
472     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_AllocatorNode));
475 /* Generate the allocator tree manipulation functions */
476 RB_GENERATE(_Rm_AllocatorTree, _Rm_AllocatorNode, linkage,
477             rmAllocatorNodeCompare, rmAllocatorNodeInv);