arch/arm/cpu/ixp/npe/IxEthDBMem.c

   1 /**
   2  * @file IxEthDBDBMem.c
   3  *
   4  * @brief Memory handling routines for the MAC address database
   5  *
   6  * @par
   7  * IXP400 SW Release version 2.0
   8  *
   9  * -- Copyright Notice --
  10  *
  11  * @par
  12  * Copyright 2001-2005, Intel Corporation.
  13  * All rights reserved.
  14  *
  15  * @par
  16  * Redistribution and use in source and binary forms, with or without
  17  * modification, are permitted provided that the following conditions
  18  * are met:
  19  * 1. Redistributions of source code must retain the above copyright
  20  *    notice, this list of conditions and the following disclaimer.
  21  * 2. Redistributions in binary form must reproduce the above copyright
  22  *    notice, this list of conditions and the following disclaimer in the
  23  *    documentation and/or other materials provided with the distribution.
  24  * 3. Neither the name of the Intel Corporation nor the names of its contributors
  25  *    may be used to endorse or promote products derived from this software
  26  *    without specific prior written permission.
  27  *
  28  * @par
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS ``AS IS''
  30  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  31  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  32  * ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
  33  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  34  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  35  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  36  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  37  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  38  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  39  * SUCH DAMAGE.
  40  *
  41  * @par
  42  * -- End of Copyright Notice --
  43  */
  44
  45
  46 #include "IxEthDB_p.h"
  47
  48 IX_ETH_DB_PRIVATE HashNode *nodePool     = NULL;
  49 IX_ETH_DB_PRIVATE MacDescriptor *macPool = NULL;
  50 IX_ETH_DB_PRIVATE MacTreeNode *treePool  = NULL;
  51
  52 IX_ETH_DB_PRIVATE HashNode nodePoolArea[NODE_POOL_SIZE];
  53 IX_ETH_DB_PRIVATE MacDescriptor macPoolArea[MAC_POOL_SIZE];
  54 IX_ETH_DB_PRIVATE MacTreeNode treePoolArea[TREE_POOL_SIZE];
  55
  56 IX_ETH_DB_PRIVATE IxOsalMutex nodePoolLock;
  57 IX_ETH_DB_PRIVATE IxOsalMutex macPoolLock;
  58 IX_ETH_DB_PRIVATE IxOsalMutex treePoolLock;
  59
  60 #define LOCK_NODE_POOL   { ixOsalMutexLock(&nodePoolLock, IX_OSAL_WAIT_FOREVER); }
  61 #define UNLOCK_NODE_POOL { ixOsalMutexUnlock(&nodePoolLock); }
  62
  63 #define LOCK_MAC_POOL    { ixOsalMutexLock(&macPoolLock, IX_OSAL_WAIT_FOREVER); }
  64 #define UNLOCK_MAC_POOL  { ixOsalMutexUnlock(&macPoolLock); }
  65
  66 #define LOCK_TREE_POOL   { ixOsalMutexLock(&treePoolLock, IX_OSAL_WAIT_FOREVER); }
  67 #define UNLOCK_TREE_POOL { ixOsalMutexUnlock(&treePoolLock); }
  68
  69 /* private function prototypes */
  70 IX_ETH_DB_PRIVATE MacDescriptor* ixEthDBPoolAllocMacDescriptor(void);
  71 IX_ETH_DB_PRIVATE void ixEthDBPoolFreeMacDescriptor(MacDescriptor *macDescriptor);
  72
  73 /**
  74  * @addtogroup EthMemoryManagement
  75  *
  76  * @{
  77  */
  78
  79 /**
  80  * @brief initializes the memory pools used by the ethernet database component
  81  *
  82  * Initializes the hash table node, mac descriptor and mac tree node pools.
  83  * Called at initialization time by @ref ixEthDBInit().
  84  *
  85  * @internal
  86  */
  87 IX_ETH_DB_PUBLIC
  88 void ixEthDBInitMemoryPools(void)
  89 {
  90     int local_index;
  91
  92     /* HashNode pool */
  93     ixOsalMutexInit(&nodePoolLock);
  94
  95     for (local_index = 0 ; local_index < NODE_POOL_SIZE ; local_index++)
  96     {
  97         HashNode *freeNode = &nodePoolArea[local_index];
  98
  99         freeNode->nextFree = nodePool;
 100         nodePool           = freeNode;
 101     }
 102
 103     /* MacDescriptor pool */
 104     ixOsalMutexInit(&macPoolLock);
 105
 106     for (local_index = 0 ; local_index < MAC_POOL_SIZE ; local_index++)
 107     {
 108         MacDescriptor *freeDescriptor = &macPoolArea[local_index];
 109
 110         freeDescriptor->nextFree = macPool;
 111         macPool                  = freeDescriptor;
 112     }
 113
 114     /* MacTreeNode pool */
 115     ixOsalMutexInit(&treePoolLock);
 116
 117     for (local_index = 0 ; local_index < TREE_POOL_SIZE ; local_index++)
 118     {
 119         MacTreeNode *freeNode = &treePoolArea[local_index];
 120
 121         freeNode->nextFree = treePool;
 122         treePool           = freeNode;
 123     }
 124 }
 125
 126 /**
 127  * @brief allocates a hash node from the pool
 128  *
 129  * Allocates a hash node and resets its value.
 130  *
 131  * @return the allocated hash node or NULL if the pool is empty
 132  *
 133  * @internal
 134  */
 135 IX_ETH_DB_PUBLIC
 136 HashNode* ixEthDBAllocHashNode(void)
 137 {
 138     HashNode *allocatedNode = NULL;
 139
 140     if (nodePool != NULL)
 141     {
 142         LOCK_NODE_POOL;
 143
 144         allocatedNode = nodePool;
 145         nodePool      = nodePool->nextFree;
 146
 147         UNLOCK_NODE_POOL;
 148
 149         memset(allocatedNode, 0, sizeof(HashNode));
 150     }
 151
 152     return allocatedNode;
 153 }
 154
 155 /**
 156  * @brief frees a hash node into the pool
 157  *
 158  * @param hashNode node to be freed
 159  *
 160  * @internal
 161  */
 162 IX_ETH_DB_PUBLIC
 163 void ixEthDBFreeHashNode(HashNode *hashNode)
 164 {
 165     if (hashNode != NULL)
 166     {
 167         LOCK_NODE_POOL;
 168
 169         hashNode->nextFree = nodePool;
 170         nodePool           = hashNode;
 171
 172         UNLOCK_NODE_POOL;
 173     }
 174 }
 175
 176 /**
 177  * @brief allocates a mac descriptor from the pool
 178  *
 179  * Allocates a mac descriptor and resets its value.
 180  * This function is not used directly, instead @ref ixEthDBAllocMacDescriptor()
 181  * is used, which keeps track of the pointer reference count.
 182  *
 183  * @see ixEthDBAllocMacDescriptor()
 184  *
 185  * @warning this function is not used directly by any other function
 186  * apart from ixEthDBAllocMacDescriptor()
 187  *
 188  * @return the allocated mac descriptor or NULL if the pool is empty
 189  *
 190  * @internal
 191  */
 192 IX_ETH_DB_PRIVATE
 193 MacDescriptor* ixEthDBPoolAllocMacDescriptor(void)
 194 {
 195     MacDescriptor *allocatedDescriptor = NULL;
 196
 197     if (macPool != NULL)
 198     {
 199         LOCK_MAC_POOL;
 200
 201         allocatedDescriptor = macPool;
 202         macPool             = macPool->nextFree;
 203
 204         UNLOCK_MAC_POOL;
 205
 206         memset(allocatedDescriptor, 0, sizeof(MacDescriptor));
 207     }
 208
 209     return allocatedDescriptor;
 210 }
 211
 212 /**
 213  * @brief allocates and initializes a mac descriptor smart pointer
 214  *
 215  * Uses @ref ixEthDBPoolAllocMacDescriptor() to allocate a mac descriptor
 216  * from the pool and initializes its reference count.
 217  *
 218  * @see ixEthDBPoolAllocMacDescriptor()
 219  *
 220  * @return the allocated mac descriptor or NULL if the pool is empty
 221  *
 222  * @internal
 223  */
 224 IX_ETH_DB_PUBLIC
 225 MacDescriptor* ixEthDBAllocMacDescriptor(void)
 226 {
 227     MacDescriptor *allocatedDescriptor = ixEthDBPoolAllocMacDescriptor();
 228
 229     if (allocatedDescriptor != NULL)
 230     {
 231         LOCK_MAC_POOL;
 232
 233         allocatedDescriptor->refCount++;
 234
 235         UNLOCK_MAC_POOL;
 236     }
 237
 238     return allocatedDescriptor;
 239 }
 240
 241 /**
 242  * @brief frees a mac descriptor back into the pool
 243  *
 244  * @param macDescriptor mac descriptor to be freed
 245  *
 246  * @warning this function is not to be called by anyone but
 247  * ixEthDBFreeMacDescriptor()
 248  *
 249  * @see ixEthDBFreeMacDescriptor()
 250  *
 251  * @internal
 252  */
 253 IX_ETH_DB_PRIVATE
 254 void ixEthDBPoolFreeMacDescriptor(MacDescriptor *macDescriptor)
 255 {
 256     LOCK_MAC_POOL;
 257
 258     macDescriptor->nextFree = macPool;
 259     macPool                 = macDescriptor;
 260
 261     UNLOCK_MAC_POOL;
 262 }
 263
 264 /**
 265  * @brief frees or reduces the usage count of a mac descriptor smart pointer
 266  *
 267  * If the reference count reaches 0 (structure is no longer used anywhere)
 268  * then the descriptor is freed back into the pool using ixEthDBPoolFreeMacDescriptor().
 269  *
 270  * @see ixEthDBPoolFreeMacDescriptor()
 271  *
 272  * @internal
 273  */
 274 IX_ETH_DB_PUBLIC
 275 void ixEthDBFreeMacDescriptor(MacDescriptor *macDescriptor)
 276 {
 277     if (macDescriptor != NULL)
 278     {
 279         LOCK_MAC_POOL;
 280
 281         if (macDescriptor->refCount > 0)
 282         {
 283             macDescriptor->refCount--;
 284
 285             if (macDescriptor->refCount == 0)
 286             {
 287                 UNLOCK_MAC_POOL;
 288
 289                 ixEthDBPoolFreeMacDescriptor(macDescriptor);
 290             }
 291             else
 292             {
 293                 UNLOCK_MAC_POOL;
 294             }
 295         }
 296         else
 297         {
 298             UNLOCK_MAC_POOL;
 299         }
 300     }
 301 }
 302
 303 /**
 304  * @brief clones a mac descriptor smart pointer
 305  *
 306  * @param macDescriptor mac descriptor to clone
 307  *
 308  * Increments the usage count of the smart pointer
 309  *
 310  * @returns the cloned smart pointer
 311  *
 312  * @internal
 313  */
 314 IX_ETH_DB_PUBLIC
 315 MacDescriptor* ixEthDBCloneMacDescriptor(MacDescriptor *macDescriptor)
 316 {
 317     LOCK_MAC_POOL;
 318
 319     if (macDescriptor->refCount == 0)
 320     {
 321         UNLOCK_MAC_POOL;
 322
 323         return NULL;
 324     }
 325
 326     macDescriptor->refCount++;
 327
 328     UNLOCK_MAC_POOL;
 329
 330     return macDescriptor;
 331 }
 332
 333 /**
 334  * @brief allocates a mac tree node from the pool
 335  *
 336  * Allocates and initializes a mac tree node from the pool.
 337  *
 338  * @return the allocated mac tree node or NULL if the pool is empty
 339  *
 340  * @internal
 341  */
 342 IX_ETH_DB_PUBLIC
 343 MacTreeNode* ixEthDBAllocMacTreeNode(void)
 344 {
 345     MacTreeNode *allocatedNode = NULL;
 346
 347     if (treePool != NULL)
 348     {
 349         LOCK_TREE_POOL;
 350
 351         allocatedNode = treePool;
 352         treePool      = treePool->nextFree;
 353
 354         UNLOCK_TREE_POOL;
 355
 356         memset(allocatedNode, 0, sizeof(MacTreeNode));
 357     }
 358
 359     return allocatedNode;
 360 }
 361
 362 /**
 363  * @brief frees a mac tree node back into the pool
 364  *
 365  * @param macNode mac tree node to be freed
 366  *
 367  * @warning not to be used except from ixEthDBFreeMacTreeNode().
 368  *
 369  * @see ixEthDBFreeMacTreeNode()
 370  *
 371  * @internal
 372  */
 373 void ixEthDBPoolFreeMacTreeNode(MacTreeNode *macNode)
 374 {
 375     if (macNode != NULL)
 376     {
 377         LOCK_TREE_POOL;
 378
 379         macNode->nextFree = treePool;
 380         treePool          = macNode;
 381
 382         UNLOCK_TREE_POOL;
 383     }
 384 }
 385
 386 /**
 387  * @brief frees or reduces the usage count of a mac tree node smart pointer
 388  *
 389  * @param macNode mac tree node to free
 390  *
 391  * Reduces the usage count of the given mac node. If the usage count
 392  * reaches 0 the node is freed back into the pool using ixEthDBPoolFreeMacTreeNode()
 393  *
 394  * @internal
 395  */
 396 IX_ETH_DB_PUBLIC
 397 void ixEthDBFreeMacTreeNode(MacTreeNode *macNode)
 398 {
 399     if (macNode->descriptor != NULL)
 400     {
 401         ixEthDBFreeMacDescriptor(macNode->descriptor);
 402     }
 403
 404     if (macNode->left != NULL)
 405     {
 406         ixEthDBFreeMacTreeNode(macNode->left);
 407     }
 408
 409     if (macNode->right != NULL)
 410     {
 411         ixEthDBFreeMacTreeNode(macNode->right);
 412     }
 413
 414     ixEthDBPoolFreeMacTreeNode(macNode);
 415 }
 416
 417 /**
 418  * @brief clones a mac tree node
 419  *
 420  * @param macNode mac tree node to be cloned
 421  *
 422  * Increments the usage count of the node, <i>its associated descriptor
 423  * and <b>recursively</b> of all its child nodes</i>.
 424  *
 425  * @warning this function is recursive and clones whole trees/subtrees, use only for
 426  * root nodes
 427  *
 428  * @internal
 429  */
 430 IX_ETH_DB_PUBLIC
 431 MacTreeNode* ixEthDBCloneMacTreeNode(MacTreeNode *macNode)
 432 {
 433     if (macNode != NULL)
 434     {
 435         MacTreeNode *clonedMacNode = ixEthDBAllocMacTreeNode();
 436
 437         if (clonedMacNode != NULL)
 438         {
 439             if (macNode->right != NULL)
 440             {
 441                 clonedMacNode->right = ixEthDBCloneMacTreeNode(macNode->right);
 442             }
 443
 444             if (macNode->left != NULL)
 445             {
 446                 clonedMacNode->left = ixEthDBCloneMacTreeNode(macNode->left);
 447             }
 448
 449             if (macNode->descriptor != NULL)
 450             {
 451                 clonedMacNode->descriptor = ixEthDBCloneMacDescriptor(macNode->descriptor);
 452             }
 453         }
 454
 455         return clonedMacNode;
 456     }
 457     else
 458     {
 459         return NULL;
 460     }
 461 }
 462
 463 #ifndef NDEBUG
 464 /* Debug statistical functions for memory usage */
 465
 466 extern HashTable dbHashtable;
 467 int ixEthDBNumHashElements(void);
 468
 469 int ixEthDBNumHashElements(void)
 470 {
 471     UINT32 bucketIndex;
 472     int numElements = 0;
 473     HashTable *hashTable = &dbHashtable;
 474
 475     for (bucketIndex = 0 ; bucketIndex < hashTable->numBuckets ; bucketIndex++)
 476     {
 477         if (hashTable->hashBuckets[bucketIndex] != NULL)
 478         {
 479             HashNode *node = hashTable->hashBuckets[bucketIndex];
 480
 481             while (node != NULL)
 482             {
 483                 numElements++;
 484
 485                 node = node->next;
 486             }
 487         }
 488     }
 489
 490     return numElements;
 491 }
 492
 493 UINT32 ixEthDBSearchTreeUsageGet(MacTreeNode *tree)
 494 {
 495     if (tree == NULL)
 496     {
 497         return 0;
 498     }
 499     else
 500     {
 501         return 1 /* this node */ + ixEthDBSearchTreeUsageGet(tree->left) + ixEthDBSearchTreeUsageGet(tree->right);
 502     }
 503 }
 504
 505 int ixEthDBShowMemoryStatus(void)
 506 {
 507     MacDescriptor *mac;
 508     MacTreeNode *tree;
 509     HashNode *node;
 510
 511     int macCounter  = 0;
 512     int treeCounter = 0;
 513     int nodeCounter = 0;
 514
 515     int totalTreeUsage            = 0;
 516     int totalDescriptorUsage      = 0;
 517     int totalCloneDescriptorUsage = 0;
 518     int totalNodeUsage            = 0;
 519
 520     UINT32 portIndex;
 521
 522     LOCK_NODE_POOL;
 523     LOCK_MAC_POOL;
 524     LOCK_TREE_POOL;
 525
 526     mac  = macPool;
 527     tree = treePool;
 528     node = nodePool;
 529
 530     while (mac != NULL)
 531     {
 532         macCounter++;
 533
 534         mac = mac->nextFree;
 535
 536         if (macCounter > MAC_POOL_SIZE)
 537         {
 538             break;
 539         }
 540     }
 541
 542     while (tree != NULL)
 543     {
 544         treeCounter++;
 545
 546         tree = tree->nextFree;
 547
 548         if (treeCounter > TREE_POOL_SIZE)
 549         {
 550             break;
 551         }
 552     }
 553
 554     while (node != NULL)
 555     {
 556         nodeCounter++;
 557
 558         node = node->nextFree;
 559
 560         if (nodeCounter > NODE_POOL_SIZE)
 561         {
 562             break;
 563         }
 564     }
 565
 566     for (portIndex = 0 ; portIndex < IX_ETH_DB_NUMBER_OF_PORTS ; portIndex++)
 567     {
 568         int treeUsage = ixEthDBSearchTreeUsageGet(ixEthDBPortInfo[portIndex].updateMethod.searchTree);
 569
 570         totalTreeUsage            += treeUsage;
 571         totalCloneDescriptorUsage += treeUsage; /* each tree node contains a descriptor */
 572     }
 573
 574     totalNodeUsage        = ixEthDBNumHashElements();
 575     totalDescriptorUsage += totalNodeUsage; /* each hash table entry contains a descriptor */
 576
 577     UNLOCK_NODE_POOL;
 578     UNLOCK_MAC_POOL;
 579     UNLOCK_TREE_POOL;
 580
 581     printf("Ethernet database memory usage stats:\n\n");
 582
 583     if (macCounter <= MAC_POOL_SIZE)
 584     {
 585         printf("\tMAC descriptor pool  : %d free out of %d entries (%d%%)\n", macCounter, MAC_POOL_SIZE, macCounter * 100 / MAC_POOL_SIZE);
 586     }
 587     else
 588     {
 589         printf("\tMAC descriptor pool  : invalid state (ring within the pool), normally %d entries\n", MAC_POOL_SIZE);
 590     }
 591
 592     if (treeCounter <= TREE_POOL_SIZE)
 593     {
 594         printf("\tTree node pool       : %d free out of %d entries (%d%%)\n", treeCounter, TREE_POOL_SIZE, treeCounter * 100 / TREE_POOL_SIZE);
 595     }
 596     else
 597     {
 598         printf("\tTREE descriptor pool  : invalid state (ring within the pool), normally %d entries\n", TREE_POOL_SIZE);
 599     }
 600
 601     if (nodeCounter <= NODE_POOL_SIZE)
 602     {
 603         printf("\tHash node pool       : %d free out of %d entries (%d%%)\n", nodeCounter, NODE_POOL_SIZE, nodeCounter * 100 / NODE_POOL_SIZE);
 604     }
 605     else
 606     {
 607         printf("\tNODE descriptor pool  : invalid state (ring within the pool), normally %d entries\n", NODE_POOL_SIZE);
 608     }
 609
 610     printf("\n");
 611     printf("\tMAC descriptor usage : %d entries, %d cloned\n", totalDescriptorUsage, totalCloneDescriptorUsage);
 612     printf("\tTree node usage      : %d entries\n", totalTreeUsage);
 613     printf("\tHash node usage      : %d entries\n", totalNodeUsage);
 614     printf("\n");
 615
 616     /* search for duplicate nodes in the mac pool */
 617     {
 618         MacDescriptor *reference = macPool;
 619
 620         while (reference != NULL)
 621         {
 622             MacDescriptor *comparison = reference->nextFree;
 623
 624             while (comparison != NULL)
 625             {
 626                 if (reference == comparison)
 627                 {
 628                     printf("Warning: reached a duplicate (%p), invalid MAC pool state\n", reference);
 629
 630                     return 1;
 631                 }
 632
 633                 comparison = comparison->nextFree;
 634             }
 635
 636             reference = reference->nextFree;
 637         }
 638     }
 639
 640     printf("No duplicates found in the MAC pool (sanity check ok)\n");
 641
 642     return 0;
 643 }
 644
 645 #endif /* NDEBUG */
 646
 647 /**
 648  * @} EthMemoryManagement
 649  */