shr_res_bitmap.c (47128B)
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 * Indexed resource management -- simple bitmap 8 */ 9 10 #include <shared/bsl.h> 11 #include <shared/alloc.h> 12 #include <bcm/error.h> 13 #include <soc/cm.h> 14 #include <shared/shr_res_bitmap.h> 15 16 /* 17 * Macros and other things that change according to settings... 18 */ 19 #if SHR_RES_BITMAP_SEARCH_RESUME 20 #define SHR_RES_BITMAP_FINAL_SEARCH_LIMIT (handle->nextAlloc) 21 #else /* SHR_RES_BITMAP_SEARCH_RESUME */ 22 #define SHR_RES_BITMAP_FINAL_SEARCH_LIMIT (handle->count - count) 23 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 24 25 /* inline */ static int 26 _shr_res_bitmap_check_all(shr_res_bitmap_handle_t handle, 27 int count, 28 int index) 29 { 30 int offset; 31 int freed = 0; 32 int inuse = 0; 33 34 /* scan the block */ 35 for (offset = 0; offset < count; offset++) { 36 if (SHR_BITGET(handle->data, index + offset)) { 37 inuse++; 38 } else { 39 freed++; 40 } 41 } /* for (offset = 0; offset < count; offset++) */ 42 if (inuse == count) { 43 /* block is entirely in use */ 44 return BCM_E_FULL; 45 } else if (freed == count) { 46 /* block is entirely free */ 47 return BCM_E_EMPTY; 48 } else { 49 /* block is partially free and partially in use */ 50 return BCM_E_EXISTS; 51 } 52 } 53 54 /* inline */ static int 55 _shr_res_bitmap_check_all_sparse(shr_res_bitmap_handle_t handle, 56 uint32 pattern, 57 int length, 58 int repeats, 59 int base) 60 { 61 int index; 62 int offset; 63 int elem; 64 int elemCount; 65 int usedCount; 66 67 for (index = 0, elem = base, elemCount = 0, usedCount = 0; 68 index < repeats; 69 index++) { 70 for (offset = 0; offset < length; offset++, elem++) { 71 if (pattern & (1 << offset)) { 72 /* this element is in the pattern */ 73 elemCount++; 74 if (SHR_BITGET(handle->data, elem)) { 75 /* this element is in use */ 76 usedCount++; 77 } 78 } /* if (pattern & (1 << offset)) */ 79 } /* for (the length of the pattern) */ 80 } /* for (as many times as the pattern repeats) */ 81 if (elemCount == usedCount) { 82 /* block is entirely in use */ 83 return BCM_E_FULL; 84 } else if (0 == usedCount) { 85 /* block is entirely free */ 86 return BCM_E_EMPTY; 87 } else { 88 /* block is partially free and partially in use */ 89 return BCM_E_EXISTS; 90 } 91 } 92 93 int 94 shr_res_bitmap_create(shr_res_bitmap_handle_t *handle, 95 int low_id, 96 int count) 97 { 98 shr_res_bitmap_handle_t desc; 99 100 /* check arguments */ 101 if (0 >= count) { 102 LOG_ERROR(BSL_LS_SOC_COMMON, 103 (BSL_META("must have a positive number of elements\n"))); 104 return BCM_E_PARAM; 105 } 106 if (!handle) { 107 LOG_ERROR(BSL_LS_SOC_COMMON, 108 (BSL_META("obligatory out argument must not be NULL\n"))); 109 return BCM_E_PARAM; 110 } 111 /* alloc memory for descriptor & data */ 112 desc = sal_alloc(sizeof(*desc) + 113 SHR_BITALLOCSIZE(count) - 114 sizeof(SHR_BITDCL), 115 "bitmap resource data"); 116 if (!desc) { 117 /* alloc failed */ 118 LOG_ERROR(BSL_LS_SOC_COMMON, 119 (BSL_META("unable to allocate %u bytes for data\n"), 120 (unsigned int)(sizeof(*desc) + 121 SHR_BITALLOCSIZE(count) - 122 sizeof(SHR_BITDCL)))); 123 return BCM_E_MEMORY; 124 } 125 /* init descriptor and data */ 126 sal_memset(desc, 127 0x00, 128 sizeof(*desc) + 129 SHR_BITALLOCSIZE(count) - 130 sizeof(SHR_BITDCL)); 131 desc->low = low_id; 132 desc->count = count; 133 *handle = desc; 134 /* all's well if we got here */ 135 return BCM_E_NONE; 136 } 137 138 int 139 shr_res_bitmap_destroy(shr_res_bitmap_handle_t handle) 140 { 141 if (handle) { 142 sal_free(handle); 143 return BCM_E_NONE; 144 } else { 145 LOG_ERROR(BSL_LS_SOC_COMMON, 146 (BSL_META("unable to free NULL handle\n"))); 147 return BCM_E_PARAM; 148 } 149 } 150 151 int 152 shr_res_bitmap_alloc(shr_res_bitmap_handle_t handle, 153 uint32 flags, 154 int count, 155 int *elem) 156 { 157 int index; 158 int offset; 159 int result = BCM_E_NONE; 160 161 /* check arguments */ 162 if (!handle) { 163 LOG_ERROR(BSL_LS_SOC_COMMON, 164 (BSL_META("unable to alloc from NULL descriptor\n"))); 165 return BCM_E_PARAM; 166 } 167 if (!elem) { 168 LOG_ERROR(BSL_LS_SOC_COMMON, 169 (BSL_META("obligatory in/out argument must not be NULL\n"))); 170 return BCM_E_PARAM; 171 } 172 if (0 >= count) { 173 LOG_ERROR(BSL_LS_SOC_COMMON, 174 (BSL_META("must allocate at least one element\n"))); 175 return BCM_E_PARAM; 176 } 177 if (SHR_RES_BITMAP_ALLOC_REPLACE == 178 (flags & (SHR_RES_BITMAP_ALLOC_REPLACE | 179 SHR_RES_BITMAP_ALLOC_WITH_ID))) { 180 LOG_ERROR(BSL_LS_SOC_COMMON, 181 (BSL_META("must use WITH_ID when using REPLACE\n"))); 182 return BCM_E_PARAM; 183 } 184 185 if (flags & SHR_RES_BITMAP_ALLOC_WITH_ID) { 186 /* WITH_ID, so only try the specifically requested block */ 187 if (*elem < handle->low) { 188 /* not valid ID */ 189 result = BCM_E_PARAM; 190 } 191 index = *elem - handle->low; 192 if (index + count > handle->count) { 193 /* not valid ID */ 194 result = BCM_E_PARAM; 195 } 196 if (BCM_E_NONE == result) { 197 result = _shr_res_bitmap_check_all(handle, count, index); 198 switch (result) { 199 case BCM_E_FULL: 200 if (flags & SHR_RES_BITMAP_ALLOC_REPLACE) { 201 result = BCM_E_NONE; 202 } else { 203 LOG_ERROR(BSL_LS_SOC_COMMON, 204 (BSL_META("proposed block %p base %d count %d" 205 " already exists\n"), 206 (void*)handle, 207 *elem, 208 count)); 209 result = BCM_E_RESOURCE; 210 } 211 break; 212 case BCM_E_EMPTY: 213 if (flags & SHR_RES_BITMAP_ALLOC_REPLACE) { 214 LOG_ERROR(BSL_LS_SOC_COMMON, 215 (BSL_META("proposed block %p base %d count %d" 216 " does not exist\n"), 217 (void*)handle, 218 *elem, 219 count)); 220 result = BCM_E_NOT_FOUND; 221 } else { 222 result = BCM_E_NONE; 223 } 224 break; 225 case BCM_E_EXISTS: 226 LOG_ERROR(BSL_LS_SOC_COMMON, 227 (BSL_META("proposed block %p base %d count %d" 228 " would merge/expand existing block(s)\n"), 229 (void*)handle, 230 *elem, 231 count)); 232 result = BCM_E_RESOURCE; 233 break; 234 default: 235 /* should never see this */ 236 LOG_ERROR(BSL_LS_SOC_COMMON, 237 (BSL_META("unexpected result checking proposed block:" 238 " %d (%s)\n"), 239 result, 240 _SHR_ERRMSG(result))); 241 if (BCM_E_NONE == result) { 242 result = BCM_E_INTERNAL; 243 } 244 } 245 } 246 /* don't adjust last free or next alloc for WITH_ID */ 247 } else { /* if (flags & SHR_RES_ALLOC_WITH_ID) */ 248 #if SHR_RES_BITMAP_SEARCH_RESUME 249 /* see if there are enough elements after last free */ 250 index = handle->lastFree; 251 if (index + count < handle->count) { 252 /* it might fit */ 253 for (offset = 0; offset < count; offset++) { 254 if (SHR_BITGET(handle->data, index + offset)) { 255 result = BCM_E_EXISTS; 256 break; 257 } 258 } 259 } else { 260 result = BCM_E_EXISTS; 261 } 262 if (BCM_E_NONE == result) { 263 /* looks good; adjust last free to miss this block */ 264 handle->lastFree = index + count; 265 } else { /* if (BCM_E_NONE == result) */ 266 /* start searching after last successful alloc */ 267 index = handle->nextAlloc; 268 while (index <= handle->count - count) { 269 while (SHR_BITGET(handle->data, index) && 270 (index > handle->count - count)) { 271 index++; 272 } 273 if (index <= handle->count - count) { 274 /* have a candidate; see if block is big enough */ 275 result = BCM_E_NONE; 276 for (offset = 0; offset < count; offset++) { 277 if (SHR_BITGET(handle->data, index + offset)) { 278 /* not big enough; skip this block */ 279 result = BCM_E_EXISTS; 280 index += offset + 1; 281 break; 282 } 283 } /* for (offset = 0; offset < count; offset++) */ 284 } /* if (index <= desc->count - count) */ 285 if (BCM_E_NONE == result) { 286 /* found a sufficient block */ 287 break; 288 } 289 } /* while (index <= desc->count - count) */ 290 if (BCM_E_NONE != result) { 291 /* no space, so try space before last successful alloc */ 292 #else /* SHR_RES_BITMAP_SEARCH_RESUME */ 293 result = BCM_E_RESOURCE; 294 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 295 index = 0; 296 while (index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) { 297 while ((index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) && 298 SHR_BITGET(handle->data, index)) { 299 index++; 300 } 301 if (index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) { 302 /* have a candidate; see if block is big enough */ 303 result = BCM_E_NONE; 304 for (offset = 0; offset < count; offset++) { 305 if (SHR_BITGET(handle->data, index + offset)) { 306 /* not big enough; skip this block */ 307 result = BCM_E_EXISTS; 308 index += offset + 1; 309 break; 310 } 311 } /* for (offset = 0; offset < count; offset++) */ 312 } /* if (index < data->next_alloc) */ 313 if (BCM_E_NONE == result) { 314 /* found a sufficient block */ 315 break; 316 } 317 } /* while (index < data->next_alloc) */ 318 #if SHR_RES_BITMAP_SEARCH_RESUME 319 } /* if (BCM_E_NONE != result) */ 320 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 321 if (BCM_E_NONE != result) { 322 /* still no space; give up */ 323 result = BCM_E_RESOURCE; 324 #if SHR_RES_BITMAP_SEARCH_RESUME 325 } else { 326 /* got some space; update next alloc */ 327 handle->nextAlloc = index + count; 328 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 329 } 330 #if SHR_RES_BITMAP_SEARCH_RESUME 331 } /* if (BCM_E_NONE == result) */ 332 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 333 } /* if (flags & SHR_RES_ALLOC_WITH_ID) */ 334 if (BCM_E_NONE == result) { 335 /* return the beginning element */ 336 *elem = index + handle->low; 337 /* mark the block as in use */ 338 SHR_BITSET_RANGE(handle->data, index, count); 339 if (0 == (flags & SHR_RES_BITMAP_ALLOC_REPLACE)) { 340 /* only adjust accounting if not replacing existing block */ 341 handle->used += count; 342 } 343 } /* if (BCM_E_NONE == result) */ 344 return result; 345 } 346 347 int 348 shr_res_bitmap_alloc_align(shr_res_bitmap_handle_t handle, 349 uint32 flags, 350 int align, 351 int offs, 352 int count, 353 int *elem) 354 { 355 int index; 356 int offset; 357 int result = BCM_E_NONE; 358 359 /* check arguments */ 360 if (!handle) { 361 LOG_ERROR(BSL_LS_SOC_COMMON, 362 (BSL_META("unable to alloc from NULL descriptor\n"))); 363 return BCM_E_PARAM; 364 } 365 if (!elem) { 366 LOG_ERROR(BSL_LS_SOC_COMMON, 367 (BSL_META("obligatory in/out argument must not be NULL\n"))); 368 return BCM_E_PARAM; 369 } 370 if (0 >= count) { 371 LOG_ERROR(BSL_LS_SOC_COMMON, 372 (BSL_META("must allocate at least one element\n"))); 373 return BCM_E_PARAM; 374 } 375 if (SHR_RES_BITMAP_ALLOC_REPLACE == 376 (flags & (SHR_RES_BITMAP_ALLOC_REPLACE | 377 SHR_RES_BITMAP_ALLOC_WITH_ID))) { 378 LOG_ERROR(BSL_LS_SOC_COMMON, 379 (BSL_META("must use WITH_ID when using REPLACE\n"))); 380 return BCM_E_PARAM; 381 } 382 383 if (flags & SHR_RES_BITMAP_ALLOC_WITH_ID) { 384 /* WITH_ID, so only try the specifically requested block */ 385 if (*elem < handle->low) { 386 /* not valid ID */ 387 result = BCM_E_PARAM; 388 } 389 index = *elem - handle->low; 390 if (index + count > handle->count) { 391 /* not valid ID */ 392 result = BCM_E_PARAM; 393 } 394 if (BCM_E_NONE == result) { 395 /* make sure caller's request is valid */ 396 if (flags & SHR_RES_BITMAP_ALLOC_ALIGN_ZERO) { 397 /* alignment is against zero */ 398 offset = (*elem) % align; 399 } else { 400 /* alignment is against low */ 401 offset = ((*elem) - handle->low) % align; 402 } 403 if (offset != offs) { 404 LOG_ERROR(BSL_LS_SOC_COMMON, 405 (BSL_META("provided first element %d does not conform" 406 " to provided align %d + offset %d values" 407 " (actual offset = %d)\n"), 408 *elem, 409 align, 410 offset, 411 offs)); 412 result = BCM_E_PARAM; 413 } 414 } 415 if (BCM_E_NONE == result) { 416 result = _shr_res_bitmap_check_all(handle, count, index); 417 switch (result) { 418 case BCM_E_FULL: 419 if (flags & SHR_RES_BITMAP_ALLOC_REPLACE) { 420 result = BCM_E_NONE; 421 } else { 422 LOG_ERROR(BSL_LS_SOC_COMMON, 423 (BSL_META("proposed block %p base %d count %d" 424 " already exists\n"), 425 (void*)handle, 426 *elem, 427 count)); 428 result = BCM_E_RESOURCE; 429 } 430 break; 431 case BCM_E_EMPTY: 432 if (flags & SHR_RES_BITMAP_ALLOC_REPLACE) { 433 LOG_ERROR(BSL_LS_SOC_COMMON, 434 (BSL_META("proposed block %p base %d count %d" 435 " does not exist\n"), 436 (void*)handle, 437 *elem, 438 count)); 439 result = BCM_E_NOT_FOUND; 440 } else { 441 result = BCM_E_NONE; 442 } 443 break; 444 case BCM_E_EXISTS: 445 LOG_ERROR(BSL_LS_SOC_COMMON, 446 (BSL_META("proposed block %p base %d count %d" 447 " would merge/expand existing block(s)\n"), 448 (void*)handle, 449 *elem, 450 count)); 451 result = BCM_E_RESOURCE; 452 break; 453 default: 454 /* should never see this */ 455 LOG_ERROR(BSL_LS_SOC_COMMON, 456 (BSL_META("unexpected result checking proposed block:" 457 " %d (%s)\n"), 458 result, 459 _SHR_ERRMSG(result))); 460 if (BCM_E_NONE == result) { 461 result = BCM_E_INTERNAL; 462 } 463 } 464 } 465 /* don't adjust last free or next alloc for WITH_ID */ 466 } else { /* if (flags & SHR_RES_ALLOC_WITH_ID) */ 467 if (flags & SHR_RES_BITMAP_ALLOC_ALIGN_ZERO) { 468 /* alignment is against zero, not start of pool */ 469 offs += align - (handle->low % align); 470 } 471 #if SHR_RES_BITMAP_SEARCH_RESUME 472 /* see if there are enough elements after last free */ 473 index = (((handle->lastFree + align - 1) / align) * align) + offs; 474 if (index + count < handle->count) { 475 /* it might fit */ 476 for (offset = 0; offset < count; offset++) { 477 if (SHR_BITGET(handle->data, index + offset)) { 478 result = BCM_E_EXISTS; 479 break; 480 } 481 } 482 } else { 483 result = BCM_E_EXISTS; 484 } 485 if (BCM_E_NONE == result) { 486 /* looks good; adjust last free to miss this block */ 487 if (0 == offs) { 488 handle->lastFree = index + count; 489 } 490 } else { /* if (BCM_E_NONE == result) */ 491 /* start searching after last successful alloc */ 492 index = (((handle->nextAlloc + align - 1) / align) * align) + offs; 493 while (index <= handle->count - count) { 494 while ((index <= handle->count - count) && 495 SHR_BITGET(handle->data, index)) { 496 index += align; 497 } 498 if (index <= handle->count - count) { 499 /* have a candidate; see if block is big enough */ 500 result = BCM_E_NONE; 501 for (offset = 0; offset < count; offset++) { 502 if (SHR_BITGET(handle->data, index + offset)) { 503 /* not big enough; skip this block */ 504 result = BCM_E_EXISTS; 505 index = (((index + offset + align) / align) * align) + offs; 506 break; 507 } 508 } /* for (offset = 0; offset < count; offset++) */ 509 } /* if (index <= desc->count - count) */ 510 if (BCM_E_NONE == result) { 511 /* found a sufficient block */ 512 break; 513 } 514 } /* while (index <= desc->count - count) */ 515 if (BCM_E_NONE != result) { 516 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 517 /* no space, so try space before last successful alloc */ 518 index = offs; 519 while (index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) { 520 while ((index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) && 521 SHR_BITGET(handle->data, index)) { 522 index += align; 523 } 524 if (index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) { 525 /* have a candidate; see if block is big enough */ 526 result = BCM_E_NONE; 527 for (offset = 0; offset < count; offset++) { 528 if (SHR_BITGET(handle->data, index + offset)) { 529 /* not big enough; skip this block */ 530 result = BCM_E_EXISTS; 531 index = (((index + offset + align) / align) * align) + offs; 532 break; 533 } 534 } /* for (offset = 0; offset < count; offset++) */ 535 } /* if (index < data->next_alloc) */ 536 if (BCM_E_NONE == result) { 537 /* found a sufficient block */ 538 break; 539 } 540 } /* while (index < data->next_alloc) */ 541 #if SHR_RES_BITMAP_SEARCH_RESUME 542 } /* if (BCM_E_NONE != result) */ 543 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 544 if (BCM_E_NONE != result) { 545 /* still no space; give up */ 546 result = BCM_E_RESOURCE; 547 #if SHR_RES_BITMAP_SEARCH_RESUME 548 } else { 549 /* got some space; update next alloc */ 550 handle->nextAlloc = index + count; 551 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 552 } 553 #if SHR_RES_BITMAP_SEARCH_RESUME 554 } /* if (BCM_E_NONE == result) */ 555 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 556 } /* if (flags & SHR_RES_ALLOC_WITH_ID) */ 557 if (BCM_E_NONE == result) { 558 /* return the beginning element */ 559 *elem = index + handle->low; 560 /* mark the block as in use */ 561 SHR_BITSET_RANGE(handle->data, index, count); 562 if (0 == (flags & SHR_RES_BITMAP_ALLOC_REPLACE)) { 563 /* only adjust accounting if not replacing existing block */ 564 handle->used += count; 565 } 566 } /* if (BCM_E_NONE == result) */ 567 return result; 568 } 569 570 int 571 shr_res_bitmap_alloc_align_sparse(shr_res_bitmap_handle_t handle, 572 uint32 flags, 573 int align, 574 int offs, 575 uint32 pattern, 576 int length, 577 int repeats, 578 int *elem) 579 { 580 int index; 581 int offset; 582 int repeat; 583 int current; 584 int first; 585 int count; 586 int result = BCM_E_NONE; 587 uint32 pattern_mask; 588 589 /* check arguments */ 590 if (!handle) { 591 LOG_ERROR(BSL_LS_SOC_COMMON, 592 (BSL_META("unable to alloc from NULL descriptor\n"))); 593 return BCM_E_PARAM; 594 } 595 if (!elem) { 596 LOG_ERROR(BSL_LS_SOC_COMMON, 597 (BSL_META("obligatory in/out argument must not be NULL\n"))); 598 return BCM_E_PARAM; 599 } 600 if (0 >= length) { 601 LOG_ERROR(BSL_LS_SOC_COMMON, 602 (BSL_META("pattern must be at least one long\n"))); 603 return BCM_E_PARAM; 604 } 605 if (32 < length) { 606 LOG_ERROR(BSL_LS_SOC_COMMON, 607 (BSL_META("pattern must not be longer than 32\n"))); 608 return BCM_E_PARAM; 609 } 610 if (0 >= repeats) { 611 LOG_ERROR(BSL_LS_SOC_COMMON, 612 (BSL_META("must allocate at least one pattern\n"))); 613 return BCM_E_PARAM; 614 } 615 pattern_mask = (((uint32)1 << (length - 1)) - 1) | ((uint32)1 << (length - 1)); 616 if (0 == (pattern & pattern_mask)) { 617 LOG_ERROR(BSL_LS_SOC_COMMON, 618 (BSL_META("pattern must contain at least one element\n"))); 619 return BCM_E_PARAM; 620 } 621 if (pattern & ~pattern_mask) { 622 LOG_ERROR(BSL_LS_SOC_COMMON, 623 (BSL_META("pattern must not contain unused bits\n"))); 624 return BCM_E_PARAM; 625 } 626 if (SHR_RES_BITMAP_ALLOC_REPLACE == 627 (flags & (SHR_RES_BITMAP_ALLOC_REPLACE | 628 SHR_RES_BITMAP_ALLOC_WITH_ID))) { 629 LOG_ERROR(BSL_LS_SOC_COMMON, 630 (BSL_META("must use WITH_ID when using REPLACE\n"))); 631 return BCM_E_PARAM; 632 } 633 /* find the final set bit of the repeated pattern */ 634 index = length; 635 count = 0; 636 do { 637 index--; 638 if (pattern & (1 << index)) { 639 count = index; 640 break; 641 } 642 } while (index > 0); 643 count += (length * (repeats - 1)); 644 /* find the first set bit of the repeated pattern */ 645 for (first = 0; first < length; first++) { 646 if (pattern & (1 << first)) { 647 break; 648 } 649 } 650 #if 0 651 if (first) { 652 LOG_WARN(BSL_LS_SOC_COMMON, 653 (BSL_META("first element is not at zero; the returned block" 654 " will not point to the first element allocated," 655 " but will point %d elements before it\n"), 656 first)); 657 } 658 #endif 659 660 if (flags & SHR_RES_BITMAP_ALLOC_WITH_ID) { 661 /* WITH_ID, so only try the specifically requested block */ 662 if (*elem < handle->low) { 663 LOG_ERROR(BSL_LS_SOC_COMMON, 664 (BSL_META("first element is too low\n"))); 665 result = BCM_E_PARAM; 666 } 667 index = *elem - handle->low; 668 if (index + count > handle->count) { 669 LOG_ERROR(BSL_LS_SOC_COMMON, 670 (BSL_META("final element is too high\n"))); 671 result = BCM_E_PARAM; 672 } 673 if (BCM_E_NONE == result) { 674 /* make sure caller's request is valid */ 675 if (flags & SHR_RES_BITMAP_ALLOC_ALIGN_ZERO) { 676 /* alignment is against zero */ 677 offset = (*elem) % align; 678 } else { 679 /* alignment is against low */ 680 offset = ((*elem) - handle->low) % align; 681 } 682 if (offset != offs) { 683 LOG_ERROR(BSL_LS_SOC_COMMON, 684 (BSL_META("provided first element %d does not conform" 685 " to provided align %d + offset %d values" 686 " (actual offset = %d)\n"), 687 *elem, 688 align, 689 offset, 690 offs)); 691 result = BCM_E_PARAM; 692 } 693 } /* if (BCM_E_NONE == result) */ 694 if (BCM_E_NONE == result) { 695 result = _shr_res_bitmap_check_all_sparse(handle, 696 pattern, 697 length, 698 repeats, 699 index); 700 switch (result) { 701 case BCM_E_FULL: 702 if (flags & SHR_RES_BITMAP_ALLOC_REPLACE) { 703 result = BCM_E_NONE; 704 } else { 705 LOG_ERROR(BSL_LS_SOC_COMMON, 706 (BSL_META("proposed block %p base %d pattern %08X" 707 " length %d repeat %d already exists\n"), 708 (void*)handle, 709 *elem, 710 pattern, 711 length, 712 repeats)); 713 result = BCM_E_RESOURCE; 714 } 715 break; 716 case BCM_E_EMPTY: 717 if (flags & SHR_RES_BITMAP_ALLOC_REPLACE) { 718 LOG_ERROR(BSL_LS_SOC_COMMON, 719 (BSL_META("proposed block %p base %d pattern %08X" 720 " length %d repeat %d does not exist\n"), 721 (void*)handle, 722 *elem, 723 pattern, 724 length, 725 repeats)); 726 result = BCM_E_NOT_FOUND; 727 } else { 728 result = BCM_E_NONE; 729 } 730 break; 731 case BCM_E_EXISTS: 732 LOG_ERROR(BSL_LS_SOC_COMMON, 733 (BSL_META("proposed block %p base %d pattern %08X" 734 " length %d repeat %d would merge/expand" 735 " existing block(s)\n"), 736 (void*)handle, 737 *elem, 738 pattern, 739 length, 740 repeats)); 741 result = BCM_E_RESOURCE; 742 break; 743 default: 744 /* should never see this */ 745 LOG_ERROR(BSL_LS_SOC_COMMON, 746 (BSL_META("unexpected result checking proposed block:" 747 " %d (%s)\n"), 748 result, 749 _SHR_ERRMSG(result))); 750 if (BCM_E_NONE == result) { 751 result = BCM_E_INTERNAL; 752 } 753 } /* switch (result) */ 754 } /* if (BCM_E_NONE == result) */ 755 /* don't adjust last free or next alloc for WITH_ID */ 756 } else { /* if (flags & SHR_RES_ALLOC_WITH_ID) */ 757 if (flags & SHR_RES_BITMAP_ALLOC_ALIGN_ZERO) { 758 /* alignment is against zero, not start of pool */ 759 offs += align - (handle->low % align); 760 } 761 #if SHR_RES_BITMAP_SEARCH_RESUME 762 /* see if it fits after the last free */ 763 index = (((handle->lastFree + align - 1) / align) * align) + offs; 764 if (index + count < handle->count) { 765 /* it might fit */ 766 for (repeat = 0, current = index; repeat < repeats; repeat++) { 767 for (offset = 0; offset < length; offset++, current++) { 768 if (pattern & (1 << offset)) { 769 if (SHR_BITGET(handle->data, current)) { 770 result = BCM_E_EXISTS; 771 break; 772 } 773 } 774 } 775 } 776 } else { 777 result = BCM_E_EXISTS; 778 } 779 if (BCM_E_NONE == result) { 780 /* looks good; adjust last free to miss this block */ 781 if (0 == offs) { 782 handle->lastFree = index + count; 783 } 784 } else { /* if (BCM_E_NONE == result) */ 785 /* start searching after last successful alloc */ 786 index = (((handle->nextAlloc + align - 1) / align) * align) + offs; 787 while (index <= handle->count - count) { 788 while ((index <= handle->count - count) && 789 SHR_BITGET(handle->data, index + first)) { 790 index += align; 791 } 792 if (index <= handle->count - count) { 793 /* have a candidate; see if block is big enough */ 794 result = BCM_E_NONE; 795 for (repeat = 0, current = index; 796 repeat < repeats; 797 repeat++) { 798 for (offset = 0; offset < length; offset++, current++) { 799 if (pattern & (1 << offset)) { 800 if (SHR_BITGET(handle->data, current)) { 801 /* an element is in use */ 802 result = BCM_E_EXISTS; 803 /* skip to next alignment point */ 804 index += align; 805 /* start comparing again */ 806 break; 807 } /* if (this element is in use) */ 808 } /* if (this element is in the pattern) */ 809 } /* for (length of the pattern) */ 810 } /* for (number of repetitions of the pattern) */ 811 } /* if (index <= desc->count - count) */ 812 if (BCM_E_NONE == result) { 813 /* found a sufficient block */ 814 break; 815 } 816 } /* while (index <= desc->count - count) */ 817 if (BCM_E_NONE != result) { 818 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 819 /* no space, so try space before last successful alloc */ 820 index = offs; 821 while (index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) { 822 while ((index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) && 823 SHR_BITGET(handle->data, index + first)) { 824 index += align; 825 } 826 if (index < SHR_RES_BITMAP_FINAL_SEARCH_LIMIT) { 827 /* have a candidate; see if block is big enough */ 828 result = BCM_E_NONE; 829 for (repeat = 0, current = index; 830 repeat < repeats; 831 repeat++) { 832 for (offset = 0; 833 offset < length; 834 offset++, current++) { 835 if (pattern & (1 << offset)) { 836 if (SHR_BITGET(handle->data, current)) { 837 /* an element is in use */ 838 result = BCM_E_EXISTS; 839 /* skip to next alignment point */ 840 index += align; 841 /* start comparing again */ 842 break; 843 } /* if (this element is in use) */ 844 } /* if (this element is in the pattern) */ 845 } /* for (length of the pattern) */ 846 } /* for (number of repetitions of the pattern) */ 847 } /* if (index < end of possible space) */ 848 if (BCM_E_NONE == result) { 849 /* found a sufficient block */ 850 break; 851 } 852 } /* while (index < data->next_alloc) */ 853 #if SHR_RES_BITMAP_SEARCH_RESUME 854 } /* if (BCM_E_NONE != result) */ 855 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 856 if (BCM_E_NONE != result) { 857 /* still no space; give up */ 858 result = BCM_E_RESOURCE; 859 #if SHR_RES_BITMAP_SEARCH_RESUME 860 } else { 861 /* got some space; update next alloc */ 862 handle->nextAlloc = index + count; 863 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 864 } 865 #if SHR_RES_BITMAP_SEARCH_RESUME 866 } /* if (BCM_E_NONE == result) */ 867 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 868 } /* if (flags & SHR_RES_ALLOC_WITH_ID) */ 869 if (BCM_E_NONE == result) { 870 /* return the beginning element */ 871 *elem = index + handle->low; 872 /* mark the block as in use */ 873 for (repeat = 0, count = 0, current = index; 874 repeat < repeats; 875 repeat++) { 876 for (offset = 0; offset < length; offset++, current++) { 877 if (pattern & (1 << offset)) { 878 SHR_BITSET(handle->data, current); 879 count++; 880 } /* if (this element is in the pattern) */ 881 } /* for (length of the pattern) */ 882 } /* for (number of repetitions of the pattern) */ 883 if (0 == (flags & SHR_RES_BITMAP_ALLOC_REPLACE)) { 884 /* only adjust accounting if not replacing existing block */ 885 handle->used += count; 886 } 887 } /* if (BCM_E_NONE == result) */ 888 return result; 889 } 890 891 int 892 shr_res_bitmap_free(shr_res_bitmap_handle_t handle, 893 int count, 894 int elem) 895 { 896 int index; 897 int offset; 898 int result = BCM_E_NONE; 899 900 /* check arguments */ 901 if (!handle) { 902 LOG_ERROR(BSL_LS_SOC_COMMON, 903 (BSL_META("unable to alloc from NULL descriptor\n"))); 904 return BCM_E_PARAM; 905 } 906 if (elem < handle->low) { 907 /* not valid ID */ 908 result = BCM_E_PARAM; 909 } 910 if (0 >= count) { 911 LOG_ERROR(BSL_LS_SOC_COMMON, 912 (BSL_META("must free at least one element\n"))); 913 return BCM_E_PARAM; 914 } 915 916 index = elem - handle->low; 917 if (index + count > handle->count) { 918 /* not valid ID */ 919 result = BCM_E_PARAM; 920 } 921 if (BCM_E_NONE == result) { 922 /* check whether the block is in use */ 923 for (offset = 0; offset < count; offset++) { 924 if (!SHR_BITGET(handle->data, index + offset)) { 925 /* not entirely in use */ 926 result = BCM_E_NOT_FOUND; 927 break; 928 } 929 } /* for (offset = 0; offset < count; offset++) */ 930 } /* if (BCM_E_NONE == result) */ 931 if (BCM_E_NONE == result) { 932 /* looks fine, so mark the block as free */ 933 SHR_BITCLR_RANGE(handle->data, index, count); 934 handle->used -= count; 935 #if SHR_RES_BITMAP_SEARCH_RESUME 936 handle->lastFree = index; 937 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 938 } /* if (BCM_E_NONE == result) */ 939 /* return the result */ 940 return result; 941 } 942 943 int 944 shr_res_bitmap_free_sparse(shr_res_bitmap_handle_t handle, 945 uint32 pattern, 946 int length, 947 int repeats, 948 int elem) 949 { 950 int index; 951 int offset; 952 int final; 953 int result = BCM_E_NONE; 954 uint32 pattern_mask; 955 956 /* check arguments */ 957 if (!handle) { 958 LOG_ERROR(BSL_LS_SOC_COMMON, 959 (BSL_META("unable to alloc from NULL descriptor\n"))); 960 return BCM_E_PARAM; 961 } 962 if (elem < handle->low) { 963 LOG_ERROR(BSL_LS_SOC_COMMON, 964 (BSL_META("first element is too low\n"))); 965 result = BCM_E_PARAM; 966 } 967 if (0 >= length) { 968 LOG_ERROR(BSL_LS_SOC_COMMON, 969 (BSL_META("pattern must be at least one long\n"))); 970 return BCM_E_PARAM; 971 } 972 if (32 < length) { 973 LOG_ERROR(BSL_LS_SOC_COMMON, 974 (BSL_META("pattern must not be longer than 32\n"))); 975 return BCM_E_PARAM; 976 } 977 if (0 >= repeats) { 978 LOG_ERROR(BSL_LS_SOC_COMMON, 979 (BSL_META("must check at least one pattern\n"))); 980 return BCM_E_PARAM; 981 } 982 pattern_mask = (((uint32)1 << (length - 1)) - 1) | ((uint32)1 << (length - 1)); 983 if (0 == (pattern & pattern_mask)) { 984 LOG_ERROR(BSL_LS_SOC_COMMON, 985 (BSL_META("pattern must contain at least one element\n"))); 986 return BCM_E_PARAM; 987 } 988 if (pattern & ~pattern_mask) { 989 LOG_ERROR(BSL_LS_SOC_COMMON, 990 (BSL_META("pattern must not contain unused bits\n"))); 991 return BCM_E_PARAM; 992 } 993 index = length; 994 final = 0; 995 do { 996 index--; 997 if (pattern & (1 << index)) { 998 final = index; 999 break; 1000 } 1001 } while (index > 0); 1002 final += (length * (repeats - 1)); 1003 1004 elem -= handle->low; 1005 if (elem + final > handle->count) { 1006 LOG_ERROR(BSL_LS_SOC_COMMON, 1007 (BSL_META("last element is too high\n"))); 1008 result = BCM_E_PARAM; 1009 } 1010 if (BCM_E_NONE == result) { 1011 /* check whether the block is in use */ 1012 result = _shr_res_bitmap_check_all_sparse(handle, 1013 pattern, 1014 length, 1015 repeats, 1016 elem); 1017 if (BCM_E_FULL == result) { 1018 /* block is fully in use */ 1019 #if SHR_RES_BITMAP_SEARCH_RESUME 1020 handle->lastFree = elem; 1021 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 1022 for (index = 0; index < repeats; index++) { 1023 for (offset = 0; offset < length; offset++, elem++) { 1024 if (pattern & (1 << offset)) { 1025 SHR_BITCLR(handle->data, elem); 1026 handle->used--; 1027 } /* if (this element is in the pattern) */ 1028 } /* for (pattern length) */ 1029 } /* for (all repeats) */ 1030 result = BCM_E_NONE; 1031 } else { /* if (BCM_E_FULL == result) */ 1032 /* not entirely in use */ 1033 result = BCM_E_NOT_FOUND; 1034 } /* if (BCM_E_FULL == result) */ 1035 } /* if (BCM_E_NONE == result) */ 1036 /* return the result */ 1037 return result; 1038 } 1039 1040 int 1041 shr_res_bitmap_check(shr_res_bitmap_handle_t handle, 1042 int count, 1043 int elem) 1044 { 1045 int index; 1046 int offset; 1047 int result = BCM_E_NONE; 1048 1049 /* check arguments */ 1050 if (!handle) { 1051 LOG_ERROR(BSL_LS_SOC_COMMON, 1052 (BSL_META("unable to alloc from NULL descriptor\n"))); 1053 return BCM_E_PARAM; 1054 } 1055 if (elem < handle->low) { 1056 /* not valid ID */ 1057 result = BCM_E_PARAM; 1058 } 1059 if (0 >= count) { 1060 LOG_ERROR(BSL_LS_SOC_COMMON, 1061 (BSL_META("must check at least one element\n"))); 1062 return BCM_E_PARAM; 1063 } 1064 1065 index = elem - handle->low; 1066 if (index + count > handle->count) { 1067 /* not valid ID */ 1068 result = BCM_E_PARAM; 1069 } 1070 if (BCM_E_NONE == result) { 1071 /* check whether the block is in use */ 1072 result = BCM_E_NOT_FOUND; 1073 for (offset = 0; offset < count; offset++) { 1074 if (SHR_BITGET(handle->data, index + offset)) { 1075 /* not entirely free */ 1076 result = BCM_E_EXISTS; 1077 break; 1078 } 1079 } /* for (offset = 0; offset < count; offset++) */ 1080 } /* if (BCM_E_NONE == result) */ 1081 /* return the result */ 1082 return result; 1083 } 1084 1085 int 1086 shr_res_bitmap_check_all(shr_res_bitmap_handle_t handle, 1087 int count, 1088 int elem) 1089 { 1090 int index; 1091 int result = BCM_E_NONE; 1092 1093 /* check arguments */ 1094 if (!handle) { 1095 LOG_ERROR(BSL_LS_SOC_COMMON, 1096 (BSL_META("unable to alloc from NULL descriptor\n"))); 1097 return BCM_E_PARAM; 1098 } 1099 if (elem < handle->low) { 1100 /* not valid ID */ 1101 result = BCM_E_PARAM; 1102 } 1103 if (0 >= count) { 1104 LOG_ERROR(BSL_LS_SOC_COMMON, 1105 (BSL_META("must check at least one element\n"))); 1106 return BCM_E_PARAM; 1107 } 1108 1109 index = elem - handle->low; 1110 if (index + count > handle->count) { 1111 /* not valid ID */ 1112 result = BCM_E_PARAM; 1113 } 1114 if (BCM_E_NONE == result) { 1115 result = _shr_res_bitmap_check_all(handle, count, index); 1116 } 1117 /* return the result */ 1118 return result; 1119 } 1120 1121 int 1122 shr_res_bitmap_check_all_sparse(shr_res_bitmap_handle_t handle, 1123 uint32 pattern, 1124 int length, 1125 int repeats, 1126 int elem) 1127 { 1128 int index; 1129 int final; 1130 int result = BCM_E_NONE; 1131 uint32 pattern_mask; 1132 1133 /* check arguments */ 1134 if (!handle) { 1135 LOG_ERROR(BSL_LS_SOC_COMMON, 1136 (BSL_META("unable to alloc from NULL descriptor\n"))); 1137 return BCM_E_PARAM; 1138 } 1139 if (elem < handle->low) { 1140 LOG_ERROR(BSL_LS_SOC_COMMON, 1141 (BSL_META("first element is too low\n"))); 1142 result = BCM_E_PARAM; 1143 } 1144 if (0 >= length) { 1145 LOG_ERROR(BSL_LS_SOC_COMMON, 1146 (BSL_META("pattern must be at least one long\n"))); 1147 return BCM_E_PARAM; 1148 } 1149 if (32 < length) { 1150 LOG_ERROR(BSL_LS_SOC_COMMON, 1151 (BSL_META("pattern must not be longer than 32\n"))); 1152 return BCM_E_PARAM; 1153 } 1154 if (0 >= repeats) { 1155 LOG_ERROR(BSL_LS_SOC_COMMON, 1156 (BSL_META("must check at least one pattern\n"))); 1157 return BCM_E_PARAM; 1158 } 1159 pattern_mask = (((uint32)1 << (length - 1)) - 1) | ((uint32)1 << (length - 1)); 1160 if (0 == (pattern & pattern_mask)) { 1161 LOG_ERROR(BSL_LS_SOC_COMMON, 1162 (BSL_META("pattern must contain at least one element\n"))); 1163 return BCM_E_PARAM; 1164 } 1165 if (pattern & ~pattern_mask) { 1166 LOG_ERROR(BSL_LS_SOC_COMMON, 1167 (BSL_META("pattern must not contain unused bits\n"))); 1168 return BCM_E_PARAM; 1169 } 1170 /* find the final set bit of the repeated pattern */ 1171 index = length; 1172 final = 0; 1173 do { 1174 index--; 1175 if (pattern & (1 << index)) { 1176 final = index; 1177 break; 1178 } 1179 } while (index > 0); 1180 final += (length * (repeats - 1)); 1181 1182 elem -= handle->low; 1183 if (elem + final > handle->count) { 1184 LOG_ERROR(BSL_LS_SOC_COMMON, 1185 (BSL_META("last element is too high\n"))); 1186 result = BCM_E_PARAM; 1187 } 1188 if (BCM_E_NONE == result) { 1189 result = _shr_res_bitmap_check_all_sparse(handle, 1190 pattern, 1191 length, 1192 repeats, 1193 elem); 1194 } 1195 /* return the result */ 1196 return result; 1197 } 1198 1199 int 1200 shr_res_bitmap_dump(const shr_res_bitmap_handle_t handle) 1201 { 1202 int result; 1203 int error = FALSE; 1204 int elemsUsed; 1205 int index; 1206 int offset; 1207 int elemOffset; 1208 int rowUse; 1209 1210 if (!handle) { 1211 LOG_ERROR(BSL_LS_SOC_COMMON, 1212 (BSL_META("must provide non-NULL handle\n"))); 1213 return BCM_E_PARAM; 1214 } 1215 LOG_CLI((BSL_META("shr_res_bitmap at %p:\n"), (const void*)handle)); 1216 LOG_CLI((BSL_META(" lowest ID = %08X\n"), handle->low)); 1217 LOG_CLI((BSL_META(" element count = %08X\n"), handle->count)); 1218 LOG_CLI((BSL_META(" used elements = %08X\n"), handle->used)); 1219 #if SHR_RES_BITMAP_SEARCH_RESUME 1220 LOG_CLI((BSL_META(" last free = %08X %s\n"), 1221 handle->lastFree, 1222 (error |= (handle->lastFree > handle->count))?"INVALID":"")); 1223 LOG_CLI((BSL_META(" next alloc = %08X %s\n"), 1224 handle->nextAlloc, 1225 (error |= (handle->nextAlloc > handle->count))?"INVALID":"")); 1226 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 1227 LOG_CLI((BSL_META(" element map:\n"))); 1228 LOG_CLI((BSL_META(" 1st Elem (index) State of elements (1 = used)\n"))); 1229 LOG_CLI((BSL_META(" -------- -------- --------------------------------------------------\n"))); 1230 elemsUsed = 0; 1231 for (index = 0; index < handle->count; /* increment in loop */) { 1232 LOG_CLI((BSL_META(" %08X %08X "), index + handle->low, index)); 1233 elemOffset = 0; 1234 rowUse = 0; 1235 for (offset = 0; offset < 48; offset++) { 1236 if ((16 == offset) || (32 == offset)) { 1237 LOG_CLI((BSL_META(" "))); 1238 } 1239 if (index < handle->count) { 1240 if (SHR_BITGET(handle->data, index + elemOffset)) { 1241 LOG_CLI((BSL_META("1"))); 1242 rowUse++; 1243 } else { 1244 LOG_CLI((BSL_META("0"))); 1245 } 1246 index++; 1247 } 1248 } 1249 LOG_CLI((BSL_META("\n"))); 1250 elemsUsed += rowUse; 1251 } /* for all grains */ 1252 LOG_CLI((BSL_META(" counted elems = %08X %s\n"), 1253 elemsUsed, 1254 (error |= (elemsUsed != handle->used))?"INVALID":"")); 1255 if (error) { 1256 LOG_CLI((BSL_META("bitmap %p appears to be corrupt\n"), 1257 (void*)handle)); 1258 result = BCM_E_INTERNAL; 1259 } else { 1260 result = BCM_E_NONE; 1261 } 1262 return result; 1263 } 1264 1265