idxres_fl.c (54313B)
1 /* 2 * 3 * This license is set out in https://raw.githubusercontent.com/Broadcom-Network-Switching-Software/OpenBCM/master/Legal/LICENSE file. 4 * 5 * Copyright 2007-2019 Broadcom Inc. All rights reserved. 6 * 7 * Module: Indexed resource management, using banked lists 8 */ 9 10 /* 11 * This is an implementation of a high-speed linked-list based freelist 12 * manager for indexed resources. This particular implementation is designed 13 * to work for sets of resources that are up to 2^31 elements in total, while 14 * allowing as many as four bytes per element (flat mode) or few as one byte 15 * per element (banked mode, also for two bytes per element). Banked mode 16 * adds a linear time overhead to alloc, but other operations should maintain 17 * their performance ('reserve' actualy gets faster with smaller banks!). 18 * 19 * There is no dynamic memory allocation involved in the allocate or free 20 * functions; the only places that use dynamic memory are the create list and 21 * destroy list functions. 22 * 23 * When in banked mode, each bank only tracks elements within that bank. A 24 * list of banks with free elements is also kept. This list is updated as 25 * elements are allocated and freed so that it always contains only banks with 26 * at least one free element. 27 * 28 * Also, because we're using banks and want to use bit shifting operations 29 * instead of multiply and divide, we need to steal a bit from the number of 30 * elements per bank to indicate special cases (the high bit set indicates a 31 * member of the allocated list). 32 * 33 * Please note that the lists used here are free lists -- that is, an element 34 * is in the list if it is *not* in use, and is marked in use otherwise. A 35 * list of the 'in use' elements is not maintained but could be obtained by a 36 * linear traversal of the structures, collecting those elements whose slot in 37 * the list marks them as 'in use'. The primary reason for not maintaining an 38 * in-use list as well as a free list is simple: in-use elements could be 39 * freed out-of-order and this would make list management an O(n) task; 40 * without that, we can alloc from head of free list and free to tail of free 41 * list in a pure O(1) manner. 42 * 43 * Note that this resource manager also allows the list to be biased -- for 44 * example, if a specific resource starts at index 8192, the list can be 45 * created so that 8192 is, in fact, the initial entry internally. This saves 46 * the caller the effort of translating inputs and outputs for simple mappings 47 * of that nature. It is possible that more complex mappings (resources with 48 * holes in their indices, for example) can be managed just as easily, though 49 * at the cost of wasting space in the list, by using the reserve function 50 * right after list creation to reserve the holes so they will never be 51 * allocated. 52 */ 53 54 #include <shared/bsl.h> 55 #include <soc/drv.h> 56 #include <bcm/error.h> 57 #include <shared/idxres_fl.h> 58 59 /* 60 * Older versions of this code imposed a lock on created lists. This seems 61 * wasteful because list management should only occur at times where the 62 * applicable resources (including the list) are protected by a lock at a 63 * higher level in the code. 64 * 65 * Set _SHR_IDXRES_SELF_LOCKING to TRUE to impose a lock on created lists. 66 * Doing this was the default behaviour for a long time, but it uses more 67 * resources and takes longer to manipulate lists due to the locking overhead. 68 * 69 * Set _SHR_IDXRES_SELF_LOCKING to FALSE to not do this. Not doing it will 70 * avoid setting up a lock, and skip the overhead of tracking the lock, 71 * reducing resource usage marginally. 72 */ 73 #define _SHR_IDXRES_SELF_LOCKING FALSE 74 75 /* 76 * Definitions of list entries within a bank 77 * 78 * Must be sure the #defines describe the type accurately. 79 * 80 * These may need to be reoptimised for 64b cores; also the calculations are 81 * for 32b cores and they'll probably be wrong (nearly a factor of two for 82 * bytes, but time should not be affected) on 64b cores. 83 * 84 * The supported IDXLIST_BASE values are 8, 16, 32. The value indicates the 85 * number of bits used to represent a single element of the free list, but 86 * there is a tradeoff... 87 * 88 * 8 16 32 89 * ---------------- ----------- ----------- ----------- 90 * Create Linear(n) Linear(n) Linear(n) 91 * Allocate Constant(2) Constant(2) Constant(2) 92 * Free Constant(2) Constant(2) Constant(2) 93 * Status Constant(1) Constant(1) Constant(1) 94 * Reserve Linear(k) Linear(k) Linear(k) 95 * ---------------- ----------- ----------- ----------- 96 * Size of element 1 2 4 97 * Needed banks (n/128) (n/32768) 1 98 * Bank overhead 8*m 12*m 20 99 * List overhead 48 48 48 100 * ---------------- ----------- ----------- ----------- 101 * 102 * For performance: linear() indicates strictly linear performance (some 103 * constant times the parameter; Constant() indicates constant performance 104 * (the parameter indicates relative complexity of the operation). The 105 * performance of 'reserve' is a bit more complex -- it is linear for the 106 * number of elements to reserve PLUS linear for the number of elements not 107 * already allocated in the list, so it's actually worse unless there are 108 * limited free elements other than those to be reserved. However, reserve is 109 * primarily intended to be called at initialisation, so this should not be 110 * such a big problem. 111 * 112 * For arguments: (n) indicates the number of elements in the list; (m) 113 * indicates the number of banks in the list; (e) indicates the number of 114 * elements used by the call, on calls where it can be nonunit. 115 * 116 * For sizes, all are in bytes. Any divide operation that results in a 117 * nonzero remainder must be rounded up to the next interval (so the result of 118 * (32769 / 32768) must be rounded to 2 -- it may not be truncated to 1). If 119 * the number of elements in the final bank does not fill the bank, only 120 * enough memory is allocated for the actual elements plus the bank overhead 121 * (it does not allocate the entire worst case bank data, but the entire bank 122 * overhead is required). Memory use for a list is fixed at time of creation 123 * for that list -- there is no alloc/free activity except by the create and 124 * destroy functions, and they do so with a single (though potentially quite 125 * large) block. Also, all size calculations assume a compiler that will 126 * operate in 'packed' mode on records and arrays; on some architectures this 127 * may cost dearly in terms of processor time to use anything below 32; also 128 * on some architectures the default mode is 'unpacked', so there may be no 129 * memory savings by going below 32. Best to examine on a platform basis. 130 * 131 * Alocations will either fail immediately (no free elements in any banks) or 132 * succeed in constant time, despite the number of banks. This is accomplised 133 * at small memory cost (four extra bytes per bank plus eight extra bytes 134 * overall) and minor time during the allocate (if a bank has no more free 135 * elements, it is removed from the list) and free (if a bank is not already 136 * in the list of banks with free elements, it is added to the list). Both 137 * maintenance operations on the banks-with-free-elements list are, as for the 138 * elements list, constant time operations. 139 * 140 * Thrashing will be maintained to a single bank if the number of elements 141 * being thrashed is at least one less than the number of elements in a bank. 142 * This has the happy consequence of improving locality and thence potentially 143 * improving cacheability of the thrashed elements. If, however, the number 144 * of elements being thrashed is not at least one less than the number of 145 * elements in a bank, the thrashing set will 'creep' through the entire free 146 * set given enough time. 147 */ 148 #ifndef IDXLIST_BASE 149 #define IDXLIST_BASE 8 150 #endif 151 #undef IDXRES_ENTRY_IS_FREE 152 #if (32 == IDXLIST_BASE) 153 typedef uint32 _idxres_list_entry_t; /* an element in a list bank */ 154 #define IDXRES_LAST_ENTRY (0xFFFFFFFF) /* last entry in this list */ 155 #define IDXRES_USED_ENTRY (0xFFFFFFFE) /* used entry */ 156 #define IDXRES_MAX_ENTRY (0x7FFFFFFF) /* max entry value */ 157 #define IDXRES_BITS_ENTRY (31) /* usable bits per entry */ 158 #define IDXRES_MAX_BANK (0) /* max bank value */ 159 #define IDXRES_FORMAT_ENTRY " %08X" /* format for dumping entry */ 160 #define IDXRES_FORMAT_MASK (0x03) /* mask for entries per line */ 161 #define IDXRES_ENTRY_IS_FREE(entry) ((0==((entry)&0x80000000))||(IDXRES_LAST_ENTRY==(entry))) 162 #endif 163 #if (16 == IDXLIST_BASE) 164 typedef uint16 _idxres_list_entry_t; /* an element in a list bank */ 165 #define IDXRES_LAST_ENTRY (0xFFFF) /* last entry in this list */ 166 #define IDXRES_USED_ENTRY (0xFFFE) /* used entry */ 167 #define IDXRES_MAX_ENTRY (0x7FFF) /* max entry value */ 168 #define IDXRES_BITS_ENTRY (15) /* usable bits per entry */ 169 #define IDXRES_MAX_BANK (0xFFFFul) /* max bank value */ 170 #define IDXRES_FORMAT_ENTRY " %04X" /* format for dumping entry */ 171 #define IDXRES_FORMAT_MASK (0x07) /* mask for entries per line */ 172 #define IDXRES_ENTRY_IS_FREE(entry) ((0==((entry)&0x8000))||(IDXRES_LAST_ENTRY==(entry))) 173 #endif 174 #if (8 == IDXLIST_BASE) 175 typedef uint8 _idxres_list_entry_t; /* an element in a list bank */ 176 #define IDXRES_LAST_ENTRY (0xFF) /* last entry in this list */ 177 #define IDXRES_USED_ENTRY (0xFE) /* used entry */ 178 #define IDXRES_MAX_ENTRY (0x7F) /* max entry value */ 179 #define IDXRES_BITS_ENTRY (7) /* usable bits per entry */ 180 #define IDXRES_MAX_BANK (0xFFFFFFul) /* max bank value */ 181 #define IDXRES_FORMAT_ENTRY " %02X" /* format for dumping entry */ 182 #define IDXRES_FORMAT_MASK (0x0F) /* mask for entries per line */ 183 #define IDXRES_ENTRY_IS_FREE(entry) ((0==((entry)&0x80))||(IDXRES_LAST_ENTRY==(entry))) 184 #endif 185 /* 186 * Note 4 bits per entry is meant for debugging and testing only; it is more 187 * expensive than 8 bits per entry for total memory allocation and also more 188 * expensive in terms of total processor time. 189 */ 190 #if (4 == IDXLIST_BASE) 191 typedef uint8 _idxres_list_entry_t; /* an element in a list bank */ 192 #define IDXRES_LAST_ENTRY (0xF) /* last entry in this list */ 193 #define IDXRES_USED_ENTRY (0xE) /* used entry */ 194 #define IDXRES_MAX_ENTRY (0x7) /* max entry value */ 195 #define IDXRES_BITS_ENTRY (3) /* usable bits per entry */ 196 #define IDXRES_MAX_BANK (0xFFFFFFFul) /* max bank value */ 197 #define IDXRES_FORMAT_ENTRY " %01X" /* format for dumping entry */ 198 #define IDXRES_FORMAT_MASK (0x0F) /* mask for entries per line */ 199 #define IDXRES_ENTRY_IS_FREE(entry) ((0==((entry)&0x8))||(IDXRES_LAST_ENTRY==(entry))) 200 #endif 201 /* 202 * This just makes sure a valid IDXLIST_BASE is selected above. 203 */ 204 #ifndef IDXRES_ENTRY_IS_FREE 205 #error IDXLIST_BASE must be one of: 8; 16; 32. 206 #endif 207 /* 208 * Additional macros using the constants defined in the sections above. These 209 * are not unique per storage size of list entry. 210 */ 211 #define IDXRES_ENTRY_IS_USED(entry) (IDXRES_USED_ENTRY==(entry)) 212 #define IDXRES_ENTRY_IS_VALID(entry) (IDXRES_ENTRY_IS_FREE(entry)||IDXRES_ENTRY_IS_USED(entry)) 213 #define IDXRES_LAST_BANK (0xFFFFFFFF) 214 #define IDXRES_USED_BANK (0xFFFFFFFE) 215 216 /* 217 * This structure describes a single bank within the resource free list. It 218 * contains all that is needed to locate the next free element in that bank, 219 * to return freed elements to the bank, and to track the active number of 220 * free and allocated elements in this bank. 221 */ 222 typedef struct _idxres_list_bank_s { 223 _idxres_list_entry_t free_head; /* head of free list */ 224 _idxres_list_entry_t free_tail; /* tail of free list */ 225 _idxres_list_entry_t free_count; /* number of free elements */ 226 _idxres_list_entry_t count; /* number of elements */ 227 } _idxres_list_bank_t; 228 229 /* 230 * This structure describes the entire list. Note that the data pointer does 231 * not point to another memory block; the entire structure is part of the one 232 * large block of memory -- the index, the bank descriptors, and the bank 233 * data are all in the single alloc cell. 234 * 235 * This is here instead of the .h file because we don't want it manipulated 236 * by functions that should be calling the API provided here. 237 */ 238 typedef struct _shr_idxres_list_s { 239 #if _SHR_IDXRES_SELF_LOCKING 240 sal_mutex_t lock; /* lock for this list */ 241 #endif /* _SHR_IDXRES_SELF_LOCKING */ 242 shr_idxres_element_t first; /* lowest elem managed by list */ 243 shr_idxres_element_t last; /* highest elem managed by list */ 244 shr_idxres_element_t valid_low; /* lowest valid element number */ 245 shr_idxres_element_t valid_high; /* highest valid element number */ 246 shr_idxres_element_t free_count; /* number of free elements */ 247 shr_idxres_element_t alloc_count; /* number of allocated elements */ 248 shr_idxres_element_t scale; /* scaling factor for elements */ 249 shr_idxres_element_t bank_max; /* highest bank number */ 250 shr_idxres_element_t bank_head; /* first bank with free elems */ 251 shr_idxres_element_t bank_tail; /* last bank with free elems */ 252 shr_idxres_element_t *bank_list; /* pointer to free bank list */ 253 _idxres_list_entry_t *data; /* pointer to start of data */ 254 _idxres_list_bank_t bank[1]; /* bank descriptors */ 255 /* a bank descriptor exists for each bank */ 256 /* actual free lists follow the bank descriptors */ 257 } _idxres_list_t; 258 #define ELEMENT_BNK(element) ((element) >> IDXRES_BITS_ENTRY) 259 #define ELEMENT_IDX(element) ((element) & IDXRES_MAX_ENTRY) 260 #define ELEMENT_NUM(bank, entry) (((bank) << IDXRES_BITS_ENTRY)+(entry)) 261 #define BANK_IS_LEGAL(list, bank) ((bank) <= (list)->bank_max) 262 #define INDEX_IS_LEGAL(list, bank, index) ((index) < (list)->bank[bank].count) 263 264 /* 265 * Generally, IDXRES_DEBUG should NOT be defined. Then it won't try to do 266 * things like printing status. 267 * 268 * The lists are not traversed by the dump function; I didn't want them to be 269 * traversed (that can be done by hand in the output, but you can also check 270 * for crosslinks and other problems this way). 271 */ 272 #undef IDXRES_DEBUG 273 #ifdef IDXRES_DEBUG 274 #define IDXRES_DUMP(stuff) bsl_printf stuff 275 #define IDXRES_DUMP_LIST(list) _shr_idxres_dump_list(list) 276 static void 277 _shr_idxres_dump_list(const shr_idxres_list_handle_t list){ 278 unsigned int _bank; 279 unsigned int _index; 280 IDXRES_DUMP(("Resource list attributes\n")); 281 IDXRES_DUMP((" first = %08X last = %08X low = %08X high = %08X\n", 282 list->first, 283 list->last, 284 list->valid_low, 285 list->valid_high)); 286 IDXRES_DUMP((" free = %08X alloc = %08X bMax = %08X\n", 287 list->free_count, 288 list->alloc_count, 289 list->bank_max)); 290 IDXRES_DUMP(("Free banks list\n")); 291 IDXRES_DUMP((" head = %08X tail = %08X", 292 list->bank_head, 293 list->bank_tail)); 294 for (_bank = 0; _bank <= list->bank_max; _bank++) { 295 if (0 == (_bank & 0x03)) { 296 IDXRES_DUMP(("\n bank # %08X : ",_bank)); 297 } 298 IDXRES_DUMP((" %08X", list->bank_list[_bank])); 299 } 300 for (_bank = 0; _bank <= list->bank_max; _bank++) { 301 IDXRES_DUMP(("\nBank %08X\n",_bank)); 302 IDXRES_DUMP((" head = %08X tail = %08X free = %08X count = %08X", 303 list->bank[_bank].free_head, 304 list->bank[_bank].free_tail, 305 list->bank[_bank].free_count, 306 list->bank[_bank].count)); 307 for (_index = 0; _index < list->bank[_bank].count; _index++) { 308 if (0 == (_index & IDXRES_FORMAT_MASK)) { 309 IDXRES_DUMP(("\n elem # %08X : ",_index)); 310 } 311 IDXRES_DUMP((IDXRES_FORMAT_ENTRY,list->data[ELEMENT_NUM(_bank,_index)])); 312 } 313 } 314 IDXRES_DUMP(("\n")); 315 } 316 #else 317 #define IDXRES_DUMP(stuff) 318 #define IDXRES_DUMP_LIST(list) 319 #endif 320 321 /* 322 * Function 323 * _shr_idxres_list_alloc 324 * Purpose 325 * Allocate the next available element from a list 326 * Parameters 327 * (in) shr_idxres_list_handle_t list = list from which to allocate 328 * (out) shr_idxres_element_t *element = where to put alloced elem num 329 * Returns 330 * BCM_E_NONE if element allocated successfully 331 * BCM_E_* as appropriate otherwise 332 * Notes 333 * No locking or parameter checking is performed. This is used internally 334 * for alloc and alloc_set operations. 335 */ 336 static int 337 _shr_idxres_list_alloc(shr_idxres_list_handle_t list, 338 shr_idxres_element_t *element) 339 { 340 shr_idxres_element_t bank; /* working bank during scan */ 341 shr_idxres_element_t addr; /* working current element address */ 342 _idxres_list_entry_t curr; /* working current entry in list */ 343 _idxres_list_entry_t next; /* working next entry in list */ 344 int result; /* value to be returned to caller */ 345 346 /* be optimistic about results */ 347 result = BCM_E_NONE; 348 349 /* see if there are any entries; allocate if so */ 350 if (list->free_count) { 351 /* start with current bank */ 352 bank = list->bank_head; 353 /* okay; this bank has free elements; get head of list */ 354 curr = list->bank[bank].free_head; 355 /* validate the head of the list */ 356 if (INDEX_IS_LEGAL(list, bank, curr)) { 357 /* get the head of the list's address */ 358 addr = ELEMENT_NUM(bank, curr); 359 /* read and verify the head of the list */ 360 next = list->data[addr]; 361 if (IDXRES_ENTRY_IS_FREE(next)) { 362 /* head entry is valid */ 363 /* advance head to next element in list */ 364 list->bank[bank].free_head = next; 365 /* mark the former head as in-use */ 366 list->data[addr] = IDXRES_USED_ENTRY; 367 /* return the overall element number of the former head */ 368 /* note this is biased against the first managed element */ 369 if (list->scale) { 370 (*element) = list->first + (addr * list->scale); 371 } else { 372 (*element) = list->first + addr; 373 } 374 /* account for allocating this element */ 375 list->free_count--; 376 list->alloc_count++; 377 list->bank[bank].free_count--; 378 if (0 == list->bank[bank].free_count) { 379 /* no more free entries in this bank; remove from list */ 380 list->bank_head = list->bank_list[bank]; 381 list->bank_list[bank] = IDXRES_USED_BANK; 382 } 383 } else { /* if (ENTRY_IS_FREE(entry)) */ 384 /* should have had valid head pointer; internal error */ 385 result = BCM_E_INTERNAL; 386 } /* if (!ENTRY_IS_FREE(entry)) */ 387 } else { /* if (INDEX_IS_LEGAL(list, bank, index)) */ 388 /* should have had a valid head pointer; internal error */ 389 result = BCM_E_INTERNAL; 390 } /* if (INDEX_IS_LEGAL(list, bank, index)) */ 391 } else { /* if (list->free_count) */ 392 /* no entries available; indicate resource shortage */ 393 result = BCM_E_RESOURCE; 394 } /* if (list->free_count) */ 395 396 /* return the actual result */ 397 return result; 398 } 399 400 /* 401 * Function 402 * _shr_idxres_list_free 403 * Purpose 404 * Free an element back to a list 405 * Parameters 406 * (in) shr_idxres_list_handle_t list = list from which elem was alloced 407 * (in) shr_idxres_element_t element = element number to free 408 * Returns 409 * BCM_E_NONE if element freed successfully 410 * BCM_E_* as appropriate otherwise 411 * Notes 412 * Freeing an entry already in the list is checked, as well as freeing an 413 * entry outside of the list-managed range. 414 * No locking and limited parameter checking is performed. This is used 415 * internally for alloc and alloc_set operations. 416 */ 417 static int 418 _shr_idxres_list_free(shr_idxres_list_handle_t list, 419 shr_idxres_element_t element) 420 { 421 shr_idxres_element_t bank; /* working bank */ 422 _idxres_list_entry_t tail; /* working tail entry */ 423 _idxres_list_entry_t index; /* working element in list */ 424 int result; /* value to be returned to caller */ 425 426 /* validate parameters */ 427 if ((element < list->valid_low) || 428 (element > list->valid_high)) { 429 /* completely invalid parameters */ 430 return BCM_E_PARAM; 431 } 432 433 /* further validation */ 434 if ((element < list->first) || 435 (element > list->last)) { 436 /* trying to free elments not managed by the list */ 437 return BCM_E_RESOURCE; 438 } 439 440 /* remove bias on entry number */ 441 if (list->scale) { 442 element = (element - list->first) / list->scale; 443 } else { 444 element = element - list->first; 445 } 446 447 /* decode into bank and entry */ 448 bank = ELEMENT_BNK(element); 449 index = ELEMENT_IDX(element); 450 tail = list->data[element]; 451 452 /* hope for the best */ 453 result = BCM_E_NONE; 454 455 /* make sure the element is currenyly in use */ 456 if (IDXRES_ENTRY_IS_USED(tail)) { 457 /* this element is in use; put it back in the free list */ 458 list->data[element] = IDXRES_LAST_ENTRY; 459 if (list->bank[bank].free_count) { 460 /* not creating a new list; append to existing one */ 461 tail = list->bank[bank].free_tail; 462 if (INDEX_IS_LEGAL(list,bank,tail)) { 463 /* old tail pointer was good */ 464 list->data[ELEMENT_NUM(bank, tail)] = index; 465 } else { 466 /* but the old tail pointer was invalid */ 467 result = BCM_E_INTERNAL; 468 } 469 } else { /* if (list->bank[bank].free_count) */ 470 /* creating a new list; set head pointer */ 471 list->bank[bank].free_head = index; 472 } /* if (list->bank[bank].free_count) */ 473 list->bank[bank].free_tail = index; 474 /* adjust accounting for freeing the element */ 475 if (0 == list->bank[bank].free_count) { 476 /* the bank is not in the free list; add it */ 477 list->bank_list[bank] = IDXRES_LAST_BANK; 478 if (IDXRES_LAST_BANK != list->bank_head) { 479 /* not the first in the list; just append */ 480 list->bank_list[list->bank_tail] = bank; 481 } else { 482 /* first in the list; create new list */ 483 list->bank_head = bank; 484 } 485 list->bank_tail = bank; 486 } 487 list->bank[bank].free_count++; 488 list->free_count++; 489 list->alloc_count--; 490 } else if (IDXRES_ENTRY_IS_FREE(tail)) { 491 /* this element is not in use */ 492 result = BCM_E_RESOURCE; 493 } else { 494 /* something is wrong with this element */ 495 result = BCM_E_INTERNAL; 496 } 497 498 /* return the actual result */ 499 return result; 500 } 501 502 /* 503 * Function 504 * shr_idxres_list_create_scaled 505 * Purpose 506 * Create a banked free list (with element scaling) 507 * Parameters 508 * (out) shr_idxres_list_handle_t *list = place to put list handle 509 * (in) shr_idxres_element_t first = number of first entry to manage 510 * (in) shr_idxres_element_t last = number of last entry to manage 511 * (in) shr_idxres_element_t validLow = low valid entry value 512 * (in) shr_idxres_element_t validHigh = high valid entry value 513 * (in) shr_idxres_element_t scale = scaling factor 514 * (in) char *name = name for the list (used for sal_alloc) 515 * Returns 516 * BCM_E_NONE if list created successfully 517 * BCM_E_* as appropriate otherwise 518 * Notes 519 * The validLow and validHigh values are used to specify the valid range 520 * of entries for querying 'free/used' status of an entry; any value not 521 * in this range is considered an invalid argument, but values that are 522 * not between first and last will be permanently 'used' and not allowed 523 * by the free operation nor ever provided by the allocate operation. 524 * Zero for scale disables scaling function. Scaling factor applies to 525 * all parameters if it is enabled. Caller must ensure the size of the 526 * range is an integral multiple of scaling factor. 527 */ 528 int 529 shr_idxres_list_create_scaled(shr_idxres_list_handle_t *list, 530 shr_idxres_element_t first, 531 shr_idxres_element_t last, 532 shr_idxres_element_t valid_low, 533 shr_idxres_element_t valid_high, 534 shr_idxres_element_t scale, 535 char *name) 536 { 537 shr_idxres_list_handle_t work_list; /* working list */ 538 shr_idxres_element_t banks; /* banks in this list */ 539 shr_idxres_element_t count; /* elements in this list */ 540 shr_idxres_element_t bank; /* working bank number */ 541 shr_idxres_element_t addr; /* working element address */ 542 _idxres_list_entry_t entry; /* working entry number */ 543 _idxres_list_entry_t fcount; /* working free count number */ 544 545 /* check parameter validity */ 546 if ((valid_low > first) || 547 (valid_high < last) || 548 (first > last) || 549 #if IDXRES_MAX_BANK 550 ((((IDXRES_MAX_BANK + 1) << IDXRES_BITS_ENTRY) - 1) < (valid_high - valid_low)) 551 #else 552 (IDXRES_MAX_ENTRY < (valid_high - valid_low)) 553 #endif 554 ) { 555 /* something's not valid on input */ 556 return BCM_E_PARAM; 557 } 558 559 /* compute the parameters for the memory block */ 560 if (scale) { 561 count = ((last - first) + scale) / scale; 562 } else { 563 count = last - first + 1; 564 } 565 #if IDXRES_MAX_BANK 566 banks = (count + IDXRES_MAX_ENTRY) >> IDXRES_BITS_ENTRY; 567 if ((IDXRES_MAX_BANK+1) < banks) { 568 /* it's too big still */ 569 return BCM_E_PARAM; 570 } 571 #else 572 banks = 1; 573 #endif 574 575 /* try to allocate enough space for the list */ 576 IDXRES_DUMP(("Allocate %d byte cell for %s.\n", 577 ((sizeof(_idxres_list_t) - sizeof(_idxres_list_bank_t)) + 578 (banks * (sizeof(_idxres_list_bank_t) + sizeof(shr_idxres_element_t))) + 579 (count * sizeof(_idxres_list_entry_t))), 580 name)); 581 work_list = sal_alloc((sizeof(_idxres_list_t) - sizeof(_idxres_list_bank_t)) + 582 (banks * (sizeof(_idxres_list_bank_t) + sizeof(shr_idxres_element_t))) + 583 (count * sizeof(_idxres_list_entry_t)), 584 name); 585 if (!work_list) { 586 /* unable to allocate the needed memory */ 587 (*list) = NULL; 588 return BCM_E_MEMORY; 589 } 590 591 #if _SHR_IDXRES_SELF_LOCKING 592 /* create and then take the mutex */ 593 IDXRES_DUMP(("Creating mutex/lock for %s\n",name)); 594 work_list->lock = sal_mutex_create(name); 595 if (!(work_list->lock)) { 596 /* unable to create the lock */ 597 sal_free(work_list); 598 (*list) = NULL; 599 return BCM_E_RESOURCE; 600 } 601 IDXRES_DUMP(("Taking lock for %s\n",name)); 602 if (sal_mutex_take(work_list->lock, sal_mutex_FOREVER)) { 603 /* Cound not obtain lock */ 604 sal_mutex_destroy(work_list->lock); 605 sal_free(work_list); 606 (*list) = NULL; 607 return BCM_E_INTERNAL; 608 } 609 #endif /* _SHR_IDXRES_SELF_LOCKING */ 610 611 /* initialise the list */ 612 work_list->first = first; 613 work_list->last = last; 614 work_list->valid_low = valid_low; 615 work_list->valid_high = valid_high; 616 work_list->scale = scale; 617 work_list->free_count = count; 618 work_list->alloc_count = 0; 619 work_list->bank_list = (shr_idxres_element_t*) 620 (((uint8*)(work_list)) + 621 sizeof(_idxres_list_t) + 622 ((banks - 1) * sizeof(_idxres_list_bank_t))); 623 work_list->data = (_idxres_list_entry_t*) 624 ((uint8*)(work_list->bank_list) + 625 (banks * sizeof(shr_idxres_element_t))); 626 work_list->bank_max = banks - 1; 627 work_list->bank_head = 0; 628 work_list->bank_tail = banks - 1; 629 /* initialise each bank of the list */ 630 for (bank = 0, addr = 0; bank < banks; bank++) { 631 /* initialise this bank */ 632 work_list->bank_list[bank] = bank + 1; 633 work_list->bank[bank].free_head = 0; 634 #if IDXRES_MAX_BANK 635 if (IDXRES_MAX_ENTRY < count) { 636 fcount = IDXRES_MAX_ENTRY + 1; 637 count -= fcount; 638 } else { 639 #endif 640 fcount = count; 641 #if IDXRES_MAX_BANK 642 } 643 #endif 644 work_list->bank[bank].count = fcount; 645 work_list->bank[bank].free_count = fcount; 646 fcount--; 647 work_list->bank[bank].free_tail = fcount; 648 /* initialise each entry of this bank */ 649 for (entry = 1; 650 entry <= fcount; 651 entry++, addr++) { 652 work_list->data[addr] = entry; 653 } 654 work_list->data[addr] = IDXRES_LAST_ENTRY; 655 addr++; 656 } 657 work_list->bank_list[banks - 1] = IDXRES_LAST_BANK; 658 659 /* debugging */ 660 IDXRES_DUMP_LIST(work_list); 661 662 #if _SHR_IDXRES_SELF_LOCKING 663 /* release the lock now */ 664 if (sal_mutex_give(work_list->lock)) { 665 /* could not release lock */ 666 sal_mutex_destroy(work_list->lock); 667 sal_free(work_list); 668 (*list) = NULL; 669 return BCM_E_INTERNAL; 670 } 671 #endif /* _SHR_IDXRES_SELF_LOCKING */ 672 673 /* all done */ 674 (*list) = work_list; 675 return BCM_E_NONE; 676 } 677 678 /* 679 * Function 680 * shr_idxres_list_create 681 * Purpose 682 * Create a banked free list 683 * Parameters 684 * (out) shr_idxres_list_handle_t *list = place to put list handle 685 * (in) shr_idxres_element_t first = number of first entry to manage 686 * (in) shr_idxres_element_t last = number of last entry to manage 687 * (in) shr_idxres_element_t validLow = low valid entry value 688 * (in) shr_idxres_element_t validHigh = high valid entry value 689 * (in) char *name = name for the list (used for sal_alloc) 690 * Returns 691 * BCM_E_NONE if list created successfully 692 * BCM_E_* as appropriate otherwise 693 * Notes 694 * The validLow and validHigh values are used to specify the valid range 695 * of entries for querying 'free/used' status of an entry; any value not 696 * in this range is considered an invalid argument, but values that are 697 * not between first and last will be permanently 'used' and not allowed 698 * by the free operation nor ever provided by the allocate operation. 699 * This function assumes scaling disabled. 700 */ 701 int 702 shr_idxres_list_create(shr_idxres_list_handle_t *list, 703 shr_idxres_element_t first, 704 shr_idxres_element_t last, 705 shr_idxres_element_t valid_low, 706 shr_idxres_element_t valid_high, 707 char *name) 708 { 709 return shr_idxres_list_create_scaled(list, 710 first, 711 last, 712 valid_low, 713 valid_high, 714 0, 715 name); 716 } 717 718 /* 719 * Function 720 * shr_idxres_list_destroy 721 * Purpose 722 * Destroy a list 723 * Parameters 724 * (in) shr_idxres_list_handle_t list = the list handle 725 * Returns 726 * BCM_E_NONE if list created successfully 727 * BCM_E_* as appropriate otherwise 728 * Notes 729 * This destroys the list, but does not claim the semaphore first, so the 730 * caller must take care not to destroy the list while it's being used. 731 * It is possible that some OSes will not permit the destruction of a lock 732 * that is in use, so maybe that at least helps. It is also willing to 733 * destroy the list even if there are still allocated entries. 734 */ 735 int 736 shr_idxres_list_destroy(shr_idxres_list_handle_t list) 737 { 738 shr_idxres_element_t count; /* elements in this list */ 739 shr_idxres_element_t banks; /* banks in this list */ 740 741 /* check parameter validity */ 742 if (!list) { 743 return BCM_E_PARAM; 744 } 745 746 /* debugging */ 747 IDXRES_DUMP_LIST(list); 748 749 #if _SHR_IDXRES_SELF_LOCKING 750 /* destroy the semaphore */ 751 sal_mutex_destroy(list->lock); 752 #endif /* _SHR_IDXRES_SELF_LOCKING */ 753 754 /* compute the parameters for the memory block */ 755 if (list->scale) { 756 count = ((list->last - list->first) + list->scale) / list->scale; 757 } else { 758 count = list->last - list->first + 1; 759 } 760 banks = list->bank_max + 1; 761 762 /* poison the list */ 763 764 sal_memset(list, 765 0x00, 766 ((sizeof(_idxres_list_t) - sizeof(_idxres_list_bank_t)) + 767 (banks * (sizeof(_idxres_list_bank_t) + sizeof(shr_idxres_element_t))) + 768 (count * sizeof(_idxres_list_entry_t)))); 769 770 /* now free the list */ 771 sal_free(list); 772 773 /* all done */ 774 return BCM_E_NONE; 775 } 776 777 /* 778 * Function 779 * shr_idxres_list_alloc 780 * Purpose 781 * Allocate the next available element from a list 782 * Parameters 783 * (in) shr_idxres_list_handle_t list = list from which to allocate 784 * (out) shr_idxres_element_t *element = where to put alloced elem num 785 * Returns 786 * BCM_E_NONE if element allocated successfully 787 * BCM_E_* as appropriate otherwise 788 * Notes 789 */ 790 int 791 shr_idxres_list_alloc(shr_idxres_list_handle_t list, 792 shr_idxres_element_t *element) 793 { 794 int result; /* value to be returned to caller */ 795 796 /* validate parameters */ 797 if (!list) { 798 return BCM_E_PARAM; 799 } 800 801 #if _SHR_IDXRES_SELF_LOCKING 802 /* claim the lock for the list */ 803 if (sal_mutex_take(list->lock, sal_mutex_FOREVER)) { 804 /* Cound not obtain lock */ 805 return BCM_E_INTERNAL; 806 } 807 #endif /* _SHR_IDXRES_SELF_LOCKING */ 808 809 /* allocate an element */ 810 result = _shr_idxres_list_alloc(list, element); 811 812 /* debugging */ 813 IDXRES_DUMP_LIST(list); 814 815 #if _SHR_IDXRES_SELF_LOCKING 816 /* release the lock for the list */ 817 if (sal_mutex_give(list->lock)) { 818 /* could not release lock */ 819 return BCM_E_INTERNAL; 820 } 821 #endif /* _SHR_IDXRES_SELF_LOCKING */ 822 823 /* return the actual result */ 824 return result; 825 } 826 827 /* 828 * Function 829 * shr_idxres_list_alloc_set 830 * Purpose 831 * Allocate the next available element from a list 832 * Parameters 833 * (in) shr_idxres_list_handle_t list = list from which to allocate 834 * (in) shr_idxres_element_t count = number of elements to allocate 835 * (out) shr_idxres_element_t *elements = ptr to array for alloced elems 836 * (out) shr_idxres_element_t *done = ptr for number of successful allocs 837 * Returns 838 * BCM_E_NONE if element allocated successfully 839 * BCM_E_* as appropriate otherwise 840 * Notes 841 * This uses the same function as shr_idxres_list_alloc, except that it 842 * verifies that there are enough elements free to fulfill the request 843 * before it tries to allocate any of them. It is still possible that an 844 * error prevents completion, however, so if the result is not success, 845 * the done value must be verified (and any elements that were done that 846 * can not be used must be freed). 847 * The set is NOT guaranteed to be contiguous. 848 */ 849 int 850 shr_idxres_list_alloc_set(shr_idxres_list_handle_t list, 851 shr_idxres_element_t count, 852 shr_idxres_element_t *elements, 853 shr_idxres_element_t *done) 854 { 855 int result; /* value to be returned to caller */ 856 857 /* validate parameters */ 858 if ((!list) || (!elements) || (!done)) { 859 return BCM_E_PARAM; 860 } 861 862 /* set initial conditions */ 863 (*done) = 0; 864 result = BCM_E_NONE; 865 866 #if _SHR_IDXRES_SELF_LOCKING 867 /* claim the lock for the list */ 868 if (sal_mutex_take(list->lock, sal_mutex_FOREVER)) { 869 /* Cound not obtain lock */ 870 return BCM_E_INTERNAL; 871 } 872 #endif /* _SHR_IDXRES_SELF_LOCKING */ 873 874 /* make sure we have enough free elements */ 875 if (list->free_count < count) { 876 /* not enough free elements to comply */ 877 result = BCM_E_RESOURCE; 878 } 879 880 /* allocate elements */ 881 while ((0 < count) && (BCM_E_NONE == result)) { 882 /* allocate this element */ 883 result = _shr_idxres_list_alloc(list, elements); 884 if (BCM_E_NONE == result) { 885 /* success; update accounting */ 886 elements++; 887 count--; 888 (*done)++; 889 } 890 } 891 892 /* debugging */ 893 IDXRES_DUMP_LIST(list); 894 895 #if _SHR_IDXRES_SELF_LOCKING 896 /* release the lock for the list */ 897 if (sal_mutex_give(list->lock)) { 898 /* could not release lock */ 899 return BCM_E_INTERNAL; 900 } 901 #endif /* _SHR_IDXRES_SELF_LOCKING */ 902 903 /* return the actual result */ 904 return result; 905 } 906 907 /* 908 * Function 909 * shr_idxres_list_free 910 * Purpose 911 * Free an element back to a list 912 * Parameters 913 * (in) shr_idxres_list_handle_t list = list from which elem was alloced 914 * (in) shr_idxres_element_t entry = element number to free 915 * Returns 916 * BCM_E_NONE if element freed successfully 917 * BCM_E_* as appropriate otherwise 918 * Notes 919 * Freeing an entry already in the list is checked, as well as freeing an 920 * entry outside of the list-managed range. Elements can be freed using 921 * either free call, no matter which alloc call was used to obtain them. 922 */ 923 int 924 shr_idxres_list_free(shr_idxres_list_handle_t list, 925 shr_idxres_element_t element) 926 { 927 int result; /* value to be returned to caller */ 928 929 /* validate parameters */ 930 if (!list) { 931 /* completely invalid parameters */ 932 return BCM_E_PARAM; 933 } 934 935 #if _SHR_IDXRES_SELF_LOCKING 936 /* claim the lock for the list */ 937 if (sal_mutex_take(list->lock, sal_mutex_FOREVER)) { 938 /* Cound not obtain lock */ 939 return BCM_E_INTERNAL; 940 } 941 #endif /* _SHR_IDXRES_SELF_LOCKING */ 942 943 result = _shr_idxres_list_free(list, element); 944 945 /* debugging */ 946 IDXRES_DUMP_LIST(list); 947 948 #if _SHR_IDXRES_SELF_LOCKING 949 /* release the lock for the list */ 950 if (sal_mutex_give(list->lock)) { 951 /* could not release lock */ 952 return BCM_E_INTERNAL; 953 } 954 #endif /* _SHR_IDXRES_SELF_LOCKING */ 955 956 /* return the actual result */ 957 return result; 958 } 959 960 /* 961 * Function 962 * shr_idxres_list_free_set 963 * Purpose 964 * Free a set of elements back to a list 965 * Parameters 966 * (in) shr_idxres_list_handle_t list = list to which to free 967 * (in) shr_idxres_element_t count = number of elements to free 968 * (in) shr_idxres_element_t *elements = ptr to array for elems to free 969 * (out) shr_idxres_element_t *done = ptr for number of successful frees 970 * Returns 971 * BCM_E_NONE if element allocated successfully 972 * BCM_E_* as appropriate otherwise 973 * Notes 974 * This uses the same function as shr_idxres_list_free. It is possible 975 * that an error prevents completion, so if the result is not success, the 976 * done value must be verified (and any elements that were not done that 977 * can not be reused must still be freed). Elements can be freed using 978 * either free call, no matter which alloc method was used to obtain them. 979 */ 980 int 981 shr_idxres_list_free_set(shr_idxres_list_handle_t list, 982 shr_idxres_element_t count, 983 shr_idxres_element_t *elements, 984 shr_idxres_element_t *done) 985 { 986 int result; /* value to be returned to caller */ 987 988 /* validate parameters */ 989 if ((!list) || (!elements) || (!done)) { 990 return BCM_E_PARAM; 991 } 992 993 /* set initial conditions */ 994 (*done) = 0; 995 result = BCM_E_NONE; 996 997 #if _SHR_IDXRES_SELF_LOCKING 998 /* claim the lock for the list */ 999 if (sal_mutex_take(list->lock, sal_mutex_FOREVER)) { 1000 /* Cound not obtain lock */ 1001 return BCM_E_INTERNAL; 1002 } 1003 #endif /* _SHR_IDXRES_SELF_LOCKING */ 1004 1005 /* free elements */ 1006 while ((0 < count) && (BCM_E_NONE == result)) { 1007 /* free this element */ 1008 result = _shr_idxres_list_free(list, *elements); 1009 if (BCM_E_NONE == result) { 1010 /* success; update accounting */ 1011 elements++; 1012 count--; 1013 (*done)++; 1014 } 1015 } 1016 1017 /* debugging */ 1018 IDXRES_DUMP_LIST(list); 1019 1020 #if _SHR_IDXRES_SELF_LOCKING 1021 /* release the lock for the list */ 1022 if (sal_mutex_give(list->lock)) { 1023 /* could not release lock */ 1024 return BCM_E_INTERNAL; 1025 } 1026 #endif /* _SHR_IDXRES_SELF_LOCKING */ 1027 1028 /* return the actual result */ 1029 return result; 1030 } 1031 1032 /* 1033 * Function 1034 * shr_idxres_list_state_scaled 1035 * Purpose 1036 * Get status of the list itself 1037 * Parameters 1038 * (in) shr_idxres_list_handle_t list = list to check 1039 * (out) shr_idxres_element_t *first = buffer for first value 1040 * (out) shr_idxres_element_t *last = buffer for last value 1041 * (out) shr_idxres_element_t *valid_low = buffer for valid_low value 1042 * (out) shr_idxres_element_t *valid_high = buffer for valid_high value 1043 * (out) shr_idxres_element_t *free_count = buffer for free_count value 1044 * (out) shr_idxres_element_t *alloc_count = buffer for alloc_count value 1045 * (out) shr_idxres_element_t *scale = buffer for scale value 1046 * Returns 1047 * BCM_E_NONE if successful 1048 * BCM_E_* as appropriate otherwise 1049 * Notes 1050 * If you don't want to fetch a specific attribute of the list, pass 1051 * NULL for the pointer to that attribute's location. 1052 * There is no set function for these items; most are set at creation of 1053 * list and the others are current state of list. 1054 */ 1055 int 1056 shr_idxres_list_state_scaled(shr_idxres_list_handle_t list, 1057 shr_idxres_element_t *first, 1058 shr_idxres_element_t *last, 1059 shr_idxres_element_t *valid_low, 1060 shr_idxres_element_t *valid_high, 1061 shr_idxres_element_t *free_count, 1062 shr_idxres_element_t *alloc_count, 1063 shr_idxres_element_t *scale) 1064 { 1065 if (!list) { 1066 /* the list has to be valid */ 1067 return BCM_E_PARAM; 1068 } 1069 1070 /* Return the values requested by the caller */ 1071 if (first) { 1072 (*first) = list->first; 1073 } 1074 if (last) { 1075 (*last) = list->last; 1076 } 1077 if (valid_low) { 1078 (*valid_low) = list->valid_low; 1079 } 1080 if (valid_high) { 1081 (*valid_high) = list->valid_high; 1082 } 1083 if (free_count) { 1084 if (list->scale) { 1085 (*free_count) = list->free_count * list->scale; 1086 } else { 1087 (*free_count) = list->free_count; 1088 } 1089 } 1090 if (alloc_count) { 1091 if (list->scale) { 1092 (*alloc_count) = list->alloc_count * list->scale; 1093 } else { 1094 (*alloc_count) = list->alloc_count; 1095 } 1096 } 1097 if (scale) { 1098 (*scale) = list->scale; 1099 } 1100 return BCM_E_NONE; 1101 } 1102 1103 /* 1104 * Function 1105 * shr_idxres_list_state 1106 * Purpose 1107 * Get status of the list itself 1108 * Parameters 1109 * (in) shr_idxres_list_handle_t list = list to check 1110 * (out) shr_idxres_element_t *first = buffer for first value 1111 * (out) shr_idxres_element_t *last = buffer for last value 1112 * (out) shr_idxres_element_t *valid_low = buffer for valid_low value 1113 * (out) shr_idxres_element_t *valid_high = buffer for valid_high value 1114 * (out) shr_idxres_element_t *free_count = buffer for free_count value 1115 * (out) shr_idxres_element_t *alloc_count = buffer for alloc_count value 1116 * Returns 1117 * BCM_E_NONE if successful 1118 * BCM_E_* as appropriate otherwise 1119 * Notes 1120 * If you don't want to fetch a specific attribute of the list, pass 1121 * NULL for the pointer to that attribute's location. 1122 * There is no set function for these items; most are set at creation of 1123 * list and the others are current state of list. 1124 */ 1125 int 1126 shr_idxres_list_state(shr_idxres_list_handle_t list, 1127 shr_idxres_element_t *first, 1128 shr_idxres_element_t *last, 1129 shr_idxres_element_t *valid_low, 1130 shr_idxres_element_t *valid_high, 1131 shr_idxres_element_t *free_count, 1132 shr_idxres_element_t *alloc_count) 1133 { 1134 return shr_idxres_list_state_scaled(list, 1135 first, 1136 last, 1137 valid_low, 1138 valid_high, 1139 free_count, 1140 alloc_count, 1141 NULL); 1142 } 1143 1144 /* 1145 * Function 1146 * shr_idxres_list_elem_state 1147 * Purpose 1148 * See if an element is currently in use 1149 * Parameters 1150 * (in) shr_idxres_list_handle_t list = list to check 1151 * (in) shr_idxres_element_t entry = element number to check 1152 * Returns 1153 * BCM_E_EXISTS if element is in use 1154 * BCM_E_NOT_FOUND if element is not in use 1155 * BCM_E_* as appropriate otherwise 1156 * Notes 1157 * This function ALWAYS returns an error (never BCM_E_NONE). 1158 */ 1159 int 1160 shr_idxres_list_elem_state(shr_idxres_list_handle_t list, 1161 shr_idxres_element_t element) 1162 { 1163 _idxres_list_entry_t entry; /* working entry in list */ 1164 1165 /* validate parameters */ 1166 if ((!list) || 1167 (element < list->valid_low) || 1168 (element > list->valid_high)) { 1169 /* completely invalid parameters */ 1170 return BCM_E_PARAM; 1171 } 1172 1173 /* further validation */ 1174 if ((element < list->first) || 1175 (element > list->last)) { 1176 /* getting state for elments not managed by the list (in use) */ 1177 return BCM_E_EXISTS; 1178 } 1179 1180 /* remove bias on entry number */ 1181 if (list->scale) { 1182 element = (element - list->first) / list->scale; 1183 } else { 1184 element = element - list->first; 1185 } 1186 1187 /* get the element state and parse it */ 1188 entry = list->data[element]; 1189 if (IDXRES_ENTRY_IS_USED(entry)) { 1190 /* the entry is in use */ 1191 return BCM_E_EXISTS; 1192 } else if (IDXRES_ENTRY_IS_FREE(entry)) { 1193 /* the entry is free */ 1194 return BCM_E_NOT_FOUND; 1195 } else { 1196 /* something is wrong with the entry */ 1197 return BCM_E_INTERNAL; 1198 } 1199 } 1200 1201 /* 1202 * Function 1203 * shr_idxres_list_reserve 1204 * Purpose 1205 * Reserve a range of elements in a list 1206 * Parameters 1207 * (in) shr_idxres_list_handle_t list = list handle 1208 * (in) shr_idxres_element_t first = first entry to reserve 1209 * (in) shr_idxres_element_t last = last entry to reserve 1210 * Returns 1211 * BCM_E_NONE if elements reserved successfully 1212 * BCM_E_* as appropriate otherwise 1213 * Notes 1214 * This is truly an inefficient way to manage top and bottom reservations 1215 * unless they are not known at list creation time, as this does not do 1216 * anything to adjust the physical size of the list's workspace; it merely 1217 * takes the requested range out of the available elements. 1218 * Elements reserved in this manner can be returned using free. 1219 */ 1220 int 1221 shr_idxres_list_reserve(shr_idxres_list_handle_t list, 1222 shr_idxres_element_t first, 1223 shr_idxres_element_t last) 1224 { 1225 int result; /* value to be returned to caller */ 1226 shr_idxres_element_t curr_elem; /* working current element address */ 1227 shr_idxres_element_t prev_elem; /* working previous element address*/ 1228 shr_idxres_element_t bank; /* working bank */ 1229 shr_idxres_element_t prev_bank; /* working previous bank */ 1230 shr_idxres_element_t next_bank; /* working next bank */ 1231 _idxres_list_entry_t curr_ent; /* working current entry number */ 1232 _idxres_list_entry_t prev_ent; /* working previous entry number */ 1233 _idxres_list_entry_t next_ent; /* working next entry number */ 1234 1235 /* validate parameters */ 1236 if ((!list) || 1237 (first < list->valid_low) || 1238 (last > list->valid_high) || 1239 (last < first)) { 1240 return BCM_E_PARAM; 1241 } 1242 1243 /* ensure the requrested range is entirely allocatable */ 1244 if ((first < list->first) || 1245 (last > list->last)) { 1246 return BCM_E_RESOURCE; 1247 } 1248 1249 #if _SHR_IDXRES_SELF_LOCKING 1250 /* claim the lock for the list */ 1251 if (sal_mutex_take(list->lock, sal_mutex_FOREVER)) { 1252 /* Cound not obtain lock */ 1253 return BCM_E_INTERNAL; 1254 } 1255 #endif /* _SHR_IDXRES_SELF_LOCKING */ 1256 1257 /* remove bias on range */ 1258 if (list->scale) { 1259 first = (first - list->first) / list->scale; 1260 last = (last - list->first) / list->scale; 1261 } else { 1262 first -= list->first; 1263 last -= list->first; 1264 } 1265 1266 /* scan the entire range to ensure availability */ 1267 result = BCM_E_NONE; 1268 for (curr_elem = first; curr_elem <= last; curr_elem++) { 1269 IDXRES_DUMP(("element %08X =" IDXRES_FORMAT_ENTRY " (%d)\n", 1270 curr_elem, 1271 list->data[curr_elem], 1272 IDXRES_ENTRY_IS_FREE(list->data[curr_elem]))); 1273 if (!IDXRES_ENTRY_IS_FREE(list->data[curr_elem])) { 1274 /* at least one element is not available */ 1275 result = BCM_E_RESOURCE; 1276 break; 1277 } 1278 } 1279 1280 /* if all is well so far, reserve the entries in question */ 1281 if (BCM_E_NONE == result) { 1282 prev_elem = 0; /* this value is overwritten before it is read */ 1283 /* need to reserve the entries */ 1284 for (bank = list->bank_head, 1285 prev_bank = IDXRES_USED_BANK; 1286 bank <= list->bank_max; 1287 bank = next_bank) { 1288 IDXRES_DUMP(("reserving in bank %08X\n",bank)); 1289 next_bank = list->bank_list[bank]; 1290 if ((ELEMENT_BNK(first) <= bank) || 1291 (ELEMENT_BNK(last) >= bank)) { 1292 prev_ent = IDXRES_LAST_ENTRY; 1293 curr_ent = list->bank[bank].free_head; 1294 do { /* while (LAST_ENTRY != curr_ent) */ 1295 /* while we're on this bank's list */ 1296 /* compute parameters for this iteration */ 1297 curr_elem = ELEMENT_NUM(bank, curr_ent); 1298 next_ent = list->data[curr_elem]; 1299 /* see if this element needs to be reserved */ 1300 if ((first <= curr_elem) && (last >= curr_elem)) { 1301 /* this element needs to be reserved */ 1302 if (IDXRES_LAST_ENTRY == prev_ent) { 1303 /* this is head of the list; set head to next */ 1304 list->bank[bank].free_head = next_ent; 1305 } else { 1306 /* this is not head of the list; remove this entry */ 1307 list->data[prev_elem] = next_ent; 1308 } 1309 /* mark this entry in use */ 1310 list->data[curr_elem] = IDXRES_USED_ENTRY; 1311 list->free_count--; 1312 list->alloc_count++; 1313 list->bank[bank].free_count--; 1314 /* go to next entry */ 1315 curr_ent = next_ent; 1316 } else { /* if ((first <= curr_elem) && (last >= curr_elem)) */ 1317 /* this element should not be reserved; move to next */ 1318 prev_ent = curr_ent; 1319 prev_elem = curr_elem; 1320 curr_ent = next_ent; 1321 } /* if ((first <= curr_elem) && (last >= curr_elem)) */ 1322 } while (IDXRES_LAST_ENTRY != curr_ent); 1323 /* now, we may need to adjust the tail pointer */ 1324 if (IDXRES_LAST_ENTRY != prev_ent) { 1325 /* yes, we need to adjust tail pointer */ 1326 list->bank[bank].free_tail = prev_ent; 1327 } 1328 if (0 == list->bank[bank].free_count) { 1329 /* no more free entries in this bank; remove from list */ 1330 if (IDXRES_USED_BANK == prev_bank) { 1331 /* first bank in the list; remove from head */ 1332 list->bank_head = list->bank_list[bank]; 1333 } else { 1334 /* not first bank in the list */ 1335 list->bank_list[prev_bank] = list->bank_list[bank]; 1336 } 1337 list->bank_list[bank] = IDXRES_USED_BANK; 1338 if (list->bank_tail == bank) { 1339 /* last bank in the list; adjust tail */ 1340 list->bank_tail = prev_bank; 1341 } 1342 } /* if (0 == list->bank[bank].free_count) */ 1343 } 1344 if (IDXRES_USED_BANK != list->bank_list[bank]) { 1345 /* update prev_bank only if the current bank was not removed 1346 * from the free list and is now empty, otherwise keep the 1347 * existing prev_bank for the next update 1348 */ 1349 prev_bank = bank; 1350 } 1351 } /* for (all banks containing the elements to reserve) */ 1352 } /* if (BCM_E_NONE == result) */ 1353 1354 /* debugging */ 1355 IDXRES_DUMP_LIST(list); 1356 1357 #if _SHR_IDXRES_SELF_LOCKING 1358 /* release the lock for the list */ 1359 if (sal_mutex_give(list->lock)) { 1360 /* could not release lock */ 1361 return BCM_E_INTERNAL; 1362 } 1363 #endif /* _SHR_IDXRES_SELF_LOCKING */ 1364 1365 /* return the actual result */ 1366 return result; 1367 } 1368 1369