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 */
  41
  42 /* Standard includes */
  43 #include <string.h>
  44
  45 /* RM external API includes */
  46 #include <ti/drv/rm/rm.h>
  47
  48 /* RM internal API includes */
  49 #include <ti/drv/rm/include/rm_internal.h>
  50 #include <ti/drv/rm/include/rm_treeloc.h>
  51
  52 /* RM OSAL layer */
  53 #include <rm_osal.h>
  54
  55 /**********************************************************************
  56  ********************* NameServer Tree Functions **********************
  57  **********************************************************************/
  58
  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;
  68
  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 }
  77
  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;
  86
  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);
  93
  94     /* Writeback the tree root */
  95     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_NameServerTree));
  96 }
  97
  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)
 105 {
 106     Rm_NameServerNode *newNode = NULL;
 107
 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);
 117 }
 118
 119 /* FUNCTION PURPOSE: Deletes a NameServer tree node
 120  ***********************************************************************
 121  * DESCRIPTION: Deletes the specified NameServer tree node.
 122  */
 123 void rmNameServerNodeFree(Rm_NameServerNode *node)
 124 {
 125     if (node) {
 126         Rm_osalFree((void *)node, sizeof(Rm_NameServerNode));
 127     }
 128 }
 129
 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)
 139 {
 140     return(strncmp(node1->objName, node2->objName, RM_NAME_MAX_CHARS));
 141 }
 142
 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)
 149 {
 150     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_NameServerNode));
 151 }
 152
 153 /* Generate the NameServer tree manipulation functions */
 154 RB_GENERATE(_Rm_NameServerTree, _Rm_NameServerNode, linkage, rmNameServerNodeCompare, rmNameServerNodeInv);
 155
 156 /**********************************************************************
 157  *************** Policy Valid Instance Tree Functions *****************
 158  **********************************************************************/
 159
 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)
 167 {
 168     Rm_PolicyValidInstNode *node;
 169
 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     }
 177 }
 178
 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)
 185 {
 186     Rm_PolicyValidInstNode *node;
 187
 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);
 194
 195     /* Writeback the tree root */
 196     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
 197 }
 198
 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)
 205 {
 206     Rm_PolicyValidInstNode *newNode = NULL;
 207
 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);
 215 }
 216
 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)
 223 {
 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  //   }
 229 }
 230
 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)
 240 {
 241     return(strncmp(node1->name, node2->name, RM_NAME_MAX_CHARS));
 242 }
 243
 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)
 250 {
 251     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_PolicyValidInstNode));
 252 }
 253
 254 /* Generate the valid instance tree manipulation functions */
 255 RB_GENERATE(_Rm_PolicyValidInstTree, _Rm_PolicyValidInstNode, linkage, rmPolicyValidInstNodeCompare, rmPolicyValidInstNodeInv);
 256
 257 /**********************************************************************
 258  ***************** Allocator Resource Tree Functions ******************
 259  **********************************************************************/
 260
 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)
 268 {
 269     Rm_ResourceNode *node;
 270
 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     }
 278 }
 279
 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)
 286 {
 287     Rm_ResourceNode *node;
 288
 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);
 295
 296     /* Writeback the tree root */
 297     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
 298 }
 299
 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)
 306 {
 307     Rm_ResourceNode *newNode = NULL;
 308
 309     newNode = Rm_osalMalloc(sizeof(Rm_ResourceNode));
 310     memset((void *)newNode, 0, sizeof(Rm_ResourceNode));
 311
 312     newNode->base = resourceBase;
 313     newNode->length = resourceLength;
 314     newNode->allocationCount = 0;
 315     newNode->ownerList = NULL;
 316
 317     return(newNode);
 318 }
 319
 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)
 326 {
 327     if (node->allocationCount == 0) {
 328         Rm_osalFree((void *)node, sizeof(Rm_ResourceNode));
 329     }
 330 }
 331
 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)
 345 {
 346     uint32_t node1End = node1->base + node1->length - 1;
 347     uint32_t node2End = node2->base + node2->length - 1;
 348
 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     }
 363 }
 364
 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)
 371 {
 372     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_ResourceNode));
 373 }
 374
 375 /* Generate the resource tree manipulation functions */
 376 RB_GENERATE(_Rm_AllocatorResourceTree, _Rm_ResourceNode, linkage, rmResourceNodeCompare, rmResourceNodeInv)
 377