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-2014, 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 /* RM external API includes */
  43 #include <ti/drv/rm/rm.h>
  44
  45 /* RM internal API includes */
  46 #include <ti/drv/rm/include/rm_internal.h>
  47 #include <ti/drv/rm/include/rm_treeloc.h>
  48
  49 /* RM OSAL layer */
  50 #include <rm_osal.h>
  51
  52 /**********************************************************************
  53  ********************* NameServer Tree Functions **********************
  54  **********************************************************************/
  55
  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;
  65
  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 }
  74
  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;
  83
  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);
  90
  91     /* Writeback the tree root */
  92     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_NameServerTree));
  93 }
  94
  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)
 102 {
 103     Rm_NameServerNode *newNode = NULL;
 104
 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, RM_NAME_MAX_CHARS);
 109         newNode->resourceBase = nodeCfg->resourceBase;
 110         newNode->resourceLength = nodeCfg->resourceLength;
 111     }
 112
 113     return(newNode);
 114 }
 115
 116 /* FUNCTION PURPOSE: Deletes a NameServer tree node
 117  ***********************************************************************
 118  * DESCRIPTION: Deletes the specified NameServer tree node.
 119  */
 120 void rmNameServerNodeFree(Rm_NameServerNode *node)
 121 {
 122     if (node) {
 123         Rm_osalFree((void *)node, sizeof(Rm_NameServerNode));
 124     }
 125 }
 126
 127 /* FUNCTION PURPOSE: Compares two NameServer tree nodes
 128  ***********************************************************************
 129  * DESCRIPTION: Returns the result of a comparison of two
 130  *              NameServer tree node names.
 131  *              node1 name < node2 name --> return < 0
 132  *              node1 name = node2 name --> return 0
 133  *              node1 name > node2 name --> return > 0
 134  */
 135 int rmNameServerNodeCompare(Rm_NameServerNode *node1, Rm_NameServerNode *node2)
 136 {
 137     return(strncmp(node1->objName, node2->objName, RM_NAME_MAX_CHARS));
 138 }
 139
 140 /* FUNCTION PURPOSE: Invalidates a NameServer tree node
 141  ***********************************************************************
 142  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
 143  *              NameServer tree node.
 144  */
 145 void rmNameServerNodeInv(Rm_NameServerNode *node)
 146 {
 147     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_NameServerNode));
 148 }
 149
 150 /* Generate the NameServer tree manipulation functions */
 151 RB_GENERATE(_Rm_NameServerTree, _Rm_NameServerNode, linkage, rmNameServerNodeCompare, rmNameServerNodeInv);
 152
 153 /**********************************************************************
 154  *************** Policy Valid Instance Tree Functions *****************
 155  **********************************************************************/
 156
 157 /* FUNCTION PURPOSE: Invalidates an entire valid instance tree
 158  ***********************************************************************
 159  * DESCRIPTION: Uses the cache handling versions of the RB tree
 160  *              macros to walk an entire valid instance tree and invalidate
 161  *              it.
 162  */
 163 void rmPolicyValidInstTreeInv(Rm_PolicyValidInstTree *treeRoot)
 164 {
 165     Rm_PolicyValidInstNode *node;
 166
 167     /* Invalidate the tree root */
 168     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
 169     /* Walk the tree which will invalidate each element in the tree */
 170     node = RB_MIN_CACHED(_Rm_PolicyValidInstTree, treeRoot);
 171     while (node) {
 172         node = RB_NEXT_CACHED(_Rm_PolicyValidInstTree, treeRoot, node);
 173     }
 174 }
 175
 176 /* FUNCTION PURPOSE: Writebacks an entire valid instance tree
 177  ***********************************************************************
 178  * DESCRIPTION: Walks the entire valid instance tree writing back
 179  *              each element to shared memory
 180  */
 181 void rmPolicyValidInstTreeWb(Rm_PolicyValidInstTree *treeRoot)
 182 {
 183     Rm_PolicyValidInstNode *node;
 184
 185     /* Writeback each element in the tree */
 186     node = RB_MIN(_Rm_PolicyValidInstTree, treeRoot);
 187     do {
 188         Rm_osalEndMemAccess((void *)node, sizeof(Rm_PolicyValidInstNode));
 189         node = RB_NEXT(_Rm_PolicyValidInstTree, treeRoot, node);
 190     } while (node);
 191
 192     /* Writeback the tree root */
 193     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_PolicyValidInstTree));
 194 }
 195
 196 /* FUNCTION PURPOSE: Creates a new valid instance tree node
 197  ***********************************************************************
 198  * DESCRIPTION: Creates a new valid instance tree node with the
 199  *              specified name.
 200  */
 201 Rm_PolicyValidInstNode *rmPolicyValidInstNodeNew(char *instName)
 202 {
 203     Rm_PolicyValidInstNode *newNode = NULL;
 204
 205     newNode = Rm_osalMalloc(sizeof(Rm_PolicyValidInstNode));
 206
 207     rm_strncpy(newNode->name, instName, RM_NAME_MAX_CHARS);
 208     newNode->allocRefCount = 0;
 209     newNode->deletePending = RM_FALSE;
 210
 211     return(newNode);
 212 }
 213
 214 /* FUNCTION PURPOSE: Deletes a valid instance tree node
 215  ***********************************************************************
 216  * DESCRIPTION: Deletes the specified valind instance tree node
 217  *              if it has zero allocation references.
 218  */
 219 void rmPolicyValidInstNodeFree(Rm_PolicyValidInstNode *node)
 220 {
 221  /* TODO: Add allocation reference count check when reference count addition/subtraction
 222   *       bugs are resolved */
 223  //   if (node->allocRefCount == 0) {
 224         Rm_osalFree((void *)node, sizeof(Rm_PolicyValidInstNode));
 225  //   }
 226 }
 227
 228 /* FUNCTION PURPOSE: Compares two valid instance tree nodes
 229  ***********************************************************************
 230  * DESCRIPTION: Returns the result of a comparison of two
 231  *              valid instance tree node names.
 232  *              node1 name < node2 name --> return < 0
 233  *              node1 name = node2 name --> return 0
 234  *              node1 name > node2 name --> return > 0
 235  */
 236 int rmPolicyValidInstNodeCompare(Rm_PolicyValidInstNode *node1, Rm_PolicyValidInstNode *node2)
 237 {
 238     return(strncmp(node1->name, node2->name, RM_NAME_MAX_CHARS));
 239 }
 240
 241 /* FUNCTION PURPOSE: Invalidates a valid instance tree node
 242  ***********************************************************************
 243  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
 244  *              valid instance tree node.
 245  */
 246 void rmPolicyValidInstNodeInv(Rm_PolicyValidInstNode *node)
 247 {
 248     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_PolicyValidInstNode));
 249 }
 250
 251 /* Generate the valid instance tree manipulation functions */
 252 RB_GENERATE(_Rm_PolicyValidInstTree, _Rm_PolicyValidInstNode, linkage, rmPolicyValidInstNodeCompare, rmPolicyValidInstNodeInv);
 253
 254 /**********************************************************************
 255  ***************** Allocator Resource Tree Functions ******************
 256  **********************************************************************/
 257
 258 /* FUNCTION PURPOSE: Invalidates an entire resource tree
 259  ***********************************************************************
 260  * DESCRIPTION: Uses the cache handling versions of the RB tree
 261  *              macros to walk an entire resource tree and invalidate
 262  *              it.
 263  */
 264 void rmResourceTreeInv(Rm_ResourceTree *treeRoot)
 265 {
 266     Rm_ResourceNode *node;
 267
 268     /* Invalidate the tree root */
 269     Rm_osalBeginMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
 270     /* Walk the tree which will invalidate each element in the tree */
 271     node = RB_MIN_CACHED(_Rm_AllocatorResourceTree, treeRoot);
 272     while (node) {
 273         node = RB_NEXT_CACHED(_Rm_AllocatorResourceTree, treeRoot, node);
 274     }
 275 }
 276
 277 /* FUNCTION PURPOSE: Writebacks an entire resource tree
 278  ***********************************************************************
 279  * DESCRIPTION: Walks the entire resource tree writing back
 280  *              each element to shared memory
 281  */
 282 void rmResourceTreeWb(Rm_ResourceTree *treeRoot)
 283 {
 284     Rm_ResourceNode *node;
 285
 286     /* Writeback each element in the tree */
 287     node = RB_MIN(_Rm_AllocatorResourceTree, treeRoot);
 288     do {
 289         Rm_osalEndMemAccess((void *)node, sizeof(Rm_ResourceNode));
 290         node = RB_NEXT(_Rm_AllocatorResourceTree, treeRoot, node);
 291     } while (node);
 292
 293     /* Writeback the tree root */
 294     Rm_osalEndMemAccess((void *)treeRoot, sizeof(Rm_ResourceTree));
 295 }
 296
 297 /* FUNCTION PURPOSE: Creates a new resource tree node
 298  ***********************************************************************
 299  * DESCRIPTION: Creates a new resource tree node with the
 300  *              specified name resource values.
 301  */
 302 Rm_ResourceNode *rmResourceNodeNew(uint32_t resourceBase, uint32_t resourceLength)
 303 {
 304     Rm_ResourceNode *newNode = NULL;
 305
 306     newNode = Rm_osalMalloc(sizeof(Rm_ResourceNode));
 307     memset((void *)newNode, 0, sizeof(Rm_ResourceNode));
 308
 309     newNode->base = resourceBase;
 310     newNode->length = resourceLength;
 311     newNode->allocationCount = 0;
 312     newNode->ownerList = NULL;
 313
 314     return(newNode);
 315 }
 316
 317 /* FUNCTION PURPOSE: Deletes a resource tree node
 318  ***********************************************************************
 319  * DESCRIPTION: Deletes the specified resource tree node
 320  *              if its allocation count is zero.
 321  */
 322 void rmResourceNodeFree(Rm_ResourceNode *node)
 323 {
 324     if (node->allocationCount == 0) {
 325         Rm_osalFree((void *)node, sizeof(Rm_ResourceNode));
 326     }
 327 }
 328
 329 /* FUNCTION PURPOSE: Compares two resource tree nodes
 330  ***********************************************************************
 331  * DESCRIPTION: Returns the result of a comparison of two
 332  *              resource tree node value ranges.
 333  *
 334  *              |node1 range||node2 range| --> return < 0
 335  *
 336  *                 |node1 range|
 337  *                   |node2 range|         --> return 0 (any overlap in ranges)
 338  *
 339  *              |node2 range||node1 range| --> return > 0
 340  */
 341 int rmResourceNodeCompare(Rm_ResourceNode *node1, Rm_ResourceNode *node2)
 342 {
 343     uint32_t node1End = node1->base + node1->length - 1;
 344     uint32_t node2End = node2->base + node2->length - 1;
 345
 346     if (node1End < node2->base) {
 347         /* End of node1 range is less than the start of node2's range.  Return a negative
 348          * value */
 349         return (-1);
 350     }
 351     else if (node1->base > node2End) {
 352         /* Start of node1 range is after end of node2's range.  Return a positive value */
 353         return (1);
 354     }
 355     else {
 356         /* If neither of the latter conditions were satisfied there is some overlap between
 357          * node1 and node2.  Return 0 since the application must handle this overlap. */
 358         return (0);
 359     }
 360 }
 361
 362 /* FUNCTION PURPOSE: Invalidates a resource tree node
 363  ***********************************************************************
 364  * DESCRIPTION: Uses RM OSAL layer to invalidate the specified
 365  *              resource tree node.
 366  */
 367 void rmResourceNodeInv(Rm_ResourceNode *node)
 368 {
 369     Rm_osalBeginMemAccess((void *)node, sizeof(Rm_ResourceNode));
 370 }
 371
 372 /* Generate the resource tree manipulation functions */
 373 RB_GENERATE(_Rm_AllocatorResourceTree, _Rm_ResourceNode, linkage, rmResourceNodeCompare, rmResourceNodeInv)
 374