Added policy tree elements
[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(*treeRoot));
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(*node));
88         node = RB_NEXT(_Rm_NameServerTree, treeRoot, node);
89     } while (node);
91     /* Writeback the tree root */
92     Rm_osalEndMemAccess((void *)treeRoot, sizeof(*treeRoot));
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(*node));
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(*treeRoot));
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(*node));
191         node = RB_NEXT(_Rm_PolicyValidInstTree, treeRoot, node);
192     } while (node);
194     /* Writeback the tree root */
195     Rm_osalEndMemAccess((void *)treeRoot, sizeof(*treeRoot));
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(const char *instName,
204                                                  const int32_t instIdx)
206     Rm_PolicyValidInstNode *newNode = NULL;
208     newNode = Rm_osalMalloc(sizeof(Rm_PolicyValidInstNode));
209     if (newNode) {
210         rm_strncpy(newNode->name, instName, RM_NAME_MAX_CHARS);
211         newNode->allocRefCount = 0;
212         newNode->deletePending = RM_FALSE;
213         newNode->instIdx       = instIdx;
214     }
215     return(newNode);
218 /* FUNCTION PURPOSE: Deletes a valid instance tree node
219  ***********************************************************************
220  * DESCRIPTION: Deletes the specified valind instance tree node
221  *              if it has zero allocation references.
222  */
223 void rmPolicyValidInstNodeFree(Rm_PolicyValidInstNode *node)
225  /* TODO: Add allocation reference count check when reference count
226   *       addition/subtraction bugs are resolved */
227  //   if (node->allocRefCount == 0) {
228         Rm_osalFree((void *)node, sizeof(*node));
229  //   }
232 /* FUNCTION PURPOSE: Compares two valid instance tree nodes
233  ***********************************************************************
234  * DESCRIPTION: Returns the result of a comparison of two 
235  *              valid instance tree node names.
236  *              node1 name < node2 name --> return < 0
237  *              node1 name = node2 name --> return 0
238  *              node1 name > node2 name --> return > 0
239  */
240 int rmPolicyValidInstNodeCompare(Rm_PolicyValidInstNode *node1,
241                                  Rm_PolicyValidInstNode *node2)
243     return(strncmp(node1->name, node2->name, RM_NAME_MAX_CHARS));
246 /* FUNCTION PURPOSE: Invalidates a valid instance tree node
247  ***********************************************************************
248  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
249  *              valid instance tree node.
250  */
251 void rmPolicyValidInstNodeInv(Rm_PolicyValidInstNode *node)
253     Rm_osalBeginMemAccess((void *)node, sizeof(*node));
256 /* Generate the valid instance tree manipulation functions */
257 RB_GENERATE(_Rm_PolicyValidInstTree, _Rm_PolicyValidInstNode, linkage,
258             rmPolicyValidInstNodeCompare, rmPolicyValidInstNodeInv);
260 /**********************************************************************
261  ***************** Allocator Resource Tree Functions ******************
262  **********************************************************************/
264 /* FUNCTION PURPOSE: Invalidates an entire resource tree
265  ***********************************************************************
266  * DESCRIPTION: Uses the cache handling versions of the RB tree
267  *              macros to walk an entire resource tree and invalidate
268  *              it.
269  */
270 void rmResourceTreeInv(Rm_ResourceTree *treeRoot)
272     Rm_ResourceNode *node;
274     /* Invalidate the tree root */
275     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(*treeRoot));
276     /* Walk the tree which will invalidate each element in the tree */
277     node = RB_MIN_CACHED(_Rm_AllocatorResourceTree, treeRoot);
278     while (node) {
279         node = RB_NEXT_CACHED(_Rm_AllocatorResourceTree, treeRoot, node);
280     }
283 /* FUNCTION PURPOSE: Writebacks an entire resource tree
284  ***********************************************************************
285  * DESCRIPTION: Walks the entire resource tree writing back
286  *              each element to shared memory
287  */
288 void rmResourceTreeWb(Rm_ResourceTree *treeRoot)
290     Rm_ResourceNode *node;
292     /* Writeback each element in the tree */
293     node = RB_MIN(_Rm_AllocatorResourceTree, treeRoot);
294     do {
295         Rm_osalEndMemAccess((void *)node, sizeof(*node));
296         node = RB_NEXT(_Rm_AllocatorResourceTree, treeRoot, node);
297     } while (node);
299     /* Writeback the tree root */
300     Rm_osalEndMemAccess((void *)treeRoot, sizeof(*treeRoot));
303 /* FUNCTION PURPOSE: Creates a new resource tree node
304  ***********************************************************************
305  * DESCRIPTION: Creates a new resource tree node with the
306  *              specified resource values.
307  */
308 Rm_ResourceNode *rmResourceNodeNew(uint32_t resourceBase,
309                                    uint32_t resourceLength)
311     Rm_ResourceNode *newNode = NULL;
313     newNode = Rm_osalMalloc(sizeof(*newNode));
314     if (newNode) {
315         newNode->base            = resourceBase;
316         newNode->length          = resourceLength;
317         newNode->allocationCount = 0;
318         newNode->ownerList       = NULL;
319     }
320     return(newNode);
323 /* FUNCTION PURPOSE: Deletes a resource tree node
324  ***********************************************************************
325  * DESCRIPTION: Deletes the specified resource tree node
326  *              if its allocation count is zero.
327  */
328 void rmResourceNodeFree(Rm_ResourceNode *node)
330     if (node->allocationCount == 0) {
331         Rm_osalFree((void *)node, sizeof(*node));
332     }
335 /* FUNCTION PURPOSE: Compares two resource tree nodes
336  ***********************************************************************
337  * DESCRIPTION: Returns the result of a comparison of two 
338  *              resource tree node value ranges.
339  *
340  *              |node1 range||node2 range| --> return < 0
341  *
342  *                 |node1 range|
343  *                   |node2 range|         --> return 0 (any overlap in ranges)
344  *
345  *              |node2 range||node1 range| --> return > 0
346  */
347 int rmResourceNodeCompare(Rm_ResourceNode *node1, Rm_ResourceNode *node2)
349     uint32_t node1End = node1->base + node1->length - 1;
350     uint32_t node2End = node2->base + node2->length - 1;
352     if (node1End < node2->base) {
353         /* End of node1 range is less than the start of node2's range.  Return
354          * a negative value */
355         return(-1);
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     } else {
361         /* If neither of the latter conditions were satisfied there is some
362          * overlap between node1 and node2.  Return 0 since the application
363          * must handle this overlap. */
364         return(0);
365     }
368 /* FUNCTION PURPOSE: Invalidates a resource tree node
369  ***********************************************************************
370  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
371  *              resource tree node.
372  */
373 void rmResourceNodeInv(Rm_ResourceNode *node)
375     Rm_osalBeginMemAccess((void *)node, sizeof(*node));
378 /* Generate the resource tree manipulation functions */
379 RB_GENERATE(_Rm_AllocatorResourceTree, _Rm_ResourceNode, linkage,
380             rmResourceNodeCompare, rmResourceNodeInv);
382 /**********************************************************************
383  ****************** Allocator Policy Tree Functions *******************
384  **********************************************************************/
386 /* FUNCTION PURPOSE: Invalidates an entire policy tree
387  ***********************************************************************
388  * DESCRIPTION: Uses the cache handling versions of the RB tree
389  *              macros to walk an entire policy tree and invalidate
390  *              it.
391  */
392 void rmPolicyTreeInv(Rm_PolicyTree *treeRoot)
394     Rm_PolicyNode *node;
396     /* Invalidate the tree root */
397     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(*treeRoot));
398     /* Walk the tree which will invalidate each element in the tree */
399     node = RB_MIN_CACHED(_Rm_AllocatorPolicyTree, treeRoot);
400     while (node) {
401         node = RB_NEXT_CACHED(_Rm_AllocatorPolicyTree, treeRoot, node);
402     }
405 /* FUNCTION PURPOSE: Writebacks an entire policy tree
406  ***********************************************************************
407  * DESCRIPTION: Walks the entire policy tree writing back
408  *              each element to shared memory
409  */
410 void rmPolicyTreeWb(Rm_PolicyTree *treeRoot)
412     Rm_PolicyNode *node;
414     /* Writeback each element in the tree */
415     node = RB_MIN(_Rm_AllocatorPolicyTree, treeRoot);
416     do {
417         Rm_osalEndMemAccess((void *)node, sizeof(*node));
418         Rm_osalEndMemAccess((void *)node->perms, node->permsLen);
419         node = RB_NEXT(_Rm_AllocatorPolicyTree, treeRoot, node);
420     } while (node);
422     /* Writeback the tree root */
423     Rm_osalEndMemAccess((void *)treeRoot, sizeof(*treeRoot));
426 /* FUNCTION PURPOSE: Creates a new policy tree node
427  ***********************************************************************
428  * DESCRIPTION: Creates a new policy tree node with the
429  *              specified policy values.
430  */
431 Rm_PolicyNode *rmPolicyNodeNew(uint32_t resourceBase, uint32_t resourceLength)
433     Rm_PolicyNode *newNode = NULL;
435     newNode = Rm_osalMalloc(sizeof(*newNode));
436     if (newNode) {
437         newNode->base  = resourceBase;
438         newNode->len   = resourceLength;
439         newNode->perms = NULL;
440         newNode->permsLen = 0;
441     }
442     return(newNode);
445 /* FUNCTION PURPOSE: Deletes a policy tree node
446  ***********************************************************************
447  * DESCRIPTION: Deletes the specified policy tree node.
448  */
449 void rmPolicyNodeFree(Rm_PolicyNode *node)
451     if (node->perms) {
452         Rm_osalFree((void *)node->perms, node->permsLen);
453     }
454     Rm_osalFree((void *)node, sizeof(*node));
457 /* FUNCTION PURPOSE: Compares two policy tree nodes
458  ***********************************************************************
459  * DESCRIPTION: Returns the result of a comparison of two 
460  *              policy tree node value ranges.
461  *
462  *              |node1 range||node2 range| --> return < 0
463  *
464  *                 |node1 range|
465  *                   |node2 range|         --> return 0 (any overlap in ranges)
466  *
467  *              |node2 range||node1 range| --> return > 0
468  */
469 int rmPolicyNodeCompare(Rm_PolicyNode *node1, Rm_PolicyNode *node2)
471     uint32_t node1End = node1->base + node1->len - 1;
472     uint32_t node2End = node2->base + node2->len - 1;
474     if (node1End < node2->base) {
475         /* End of node1 range is less than the start of node2's range.  Return
476          * a negative value */
477         return(-1);
478     } else if (node1->base > node2End) {
479         /* Start of node1 range is after end of node2's range.  Return a
480          * positive value */
481         return(1);
482     } else {
483         /* If neither of the latter conditions were satisfied there is some
484          * overlap between node1 and node2.  Return 0 since the application
485          * must handle this overlap. */
486         return(0);
487     }
490 /* FUNCTION PURPOSE: Invalidates a policy tree node
491  ***********************************************************************
492  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
493  *              policy tree node.
494  */
495 void rmPolicyNodeInv(Rm_PolicyNode *node)
497     Rm_osalBeginMemAccess((void *)node, sizeof(*node));
498     Rm_osalBeginMemAccess((void *)node->perms, node->permsLen);
501 /* Generate the policy tree manipulation functions */
502 RB_GENERATE(_Rm_AllocatorPolicyTree, _Rm_PolicyNode, linkage,
503             rmPolicyNodeCompare, rmPolicyNodeInv);
505 /**********************************************************************
506  ********************* Allocator Tree Functions ***********************
507  **********************************************************************/
509 /* FUNCTION PURPOSE: Invalidates an entire allocator tree
510  ***********************************************************************
511  * DESCRIPTION: Uses the cache handling versions of the RB tree
512  *              macros to walk and invalidate an entire allocator tree.
513  */
514 void rmAllocatorTreeInv(Rm_AllocatorTree *treeRoot)
516     Rm_AllocatorNode *node;
518     /* Invalidate the tree root */
519     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(*treeRoot));
520     /* Walk the tree which will invalidate each element in the tree */
521     node = RB_MIN_CACHED(_Rm_AllocatorTree, treeRoot);
522     while (node) {
523         node = RB_NEXT_CACHED(_Rm_AllocatorTree, treeRoot, node);
524     }
527 /* FUNCTION PURPOSE: Writebacks an entire allocator tree
528  ***********************************************************************
529  * DESCRIPTION: Walks the entire allocator tree writing back
530  *              each element to shared memory
531  */
532 void rmAllocatorTreeWb(Rm_AllocatorTree *treeRoot)
534     Rm_AllocatorNode *node;
536     /* Writeback each element in the tree */
537     node = RB_MIN(_Rm_AllocatorTree, treeRoot);
538     do {
539         Rm_osalEndMemAccess((void *)node, sizeof(*node));
540         node = RB_NEXT(_Rm_AllocatorTree, treeRoot, node);
541     } while (node);
543     /* Writeback the tree root */
544     Rm_osalEndMemAccess((void *)treeRoot, sizeof(*treeRoot));
547 /* FUNCTION PURPOSE: Creates a new allocator node
548  ***********************************************************************
549  * DESCRIPTION: Creates a new allocator node with the
550  *              specified resource name.
551  */
552 Rm_AllocatorNode *rmAllocatorNodeNew(const char *resourceName)
554     Rm_AllocatorNode *newNode = NULL;
556     newNode = Rm_osalMalloc(sizeof(*newNode));
557     if (newNode) {
558         rm_strncpy(newNode->resourceName, resourceName, RM_NAME_MAX_CHARS);
559         newNode->resourceRoot = NULL;
560         newNode->policyRoot   = NULL;
561     }
562     return(newNode);
565 /* FUNCTION PURPOSE: Deletes an allocator node
566  ***********************************************************************
567  * DESCRIPTION: Deletes the specified allocator node.
568  */
569 void rmAllocatorNodeFree(Rm_AllocatorNode *node)
571     Rm_osalFree((void *)node, sizeof(*node));
574 /* FUNCTION PURPOSE: Compares two allocator nodes
575  ***********************************************************************
576  * DESCRIPTION: Returns the result of a comparison of two
577  *              allocator node resource names.
578  *              node1 name < node2 name --> return < 0
579  *              node1 name = node2 name --> return 0
580  *              node1 name > node2 name --> return > 0
581  */
582 int rmAllocatorNodeCompare(Rm_AllocatorNode *node1, Rm_AllocatorNode *node2)
584     return(strncmp(node1->resourceName, node2->resourceName,
585                    RM_NAME_MAX_CHARS));
588 /* FUNCTION PURPOSE: Invalidates an allocator tree node
589  ***********************************************************************
590  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
591  *              allocator tree node.
592  */
593 void rmAllocatorNodeInv(Rm_AllocatorNode *node)
595     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_AllocatorNode));
598 /* Generate the allocator tree manipulation functions */
599 RB_GENERATE(_Rm_AllocatorTree, _Rm_AllocatorNode, linkage,
600             rmAllocatorNodeCompare, rmAllocatorNodeInv);