shr_res_bitmap.h (18389B)
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 #ifndef _SHR_RES_BITMAP_H_ 11 #define _SHR_RES_BITMAP_H_ 12 13 #include <sal/types.h> 14 #include <shared/bitop.h> 15 16 /* 17 * This is a fairly brute-force implementation of bitmap, with minimal 18 * optimisations or improvements. It could probably be enhanced somewhat by 19 * some subtleties, such as checking whether a SHR_BITDCL is all ones before 20 * scanning individual bits when looking for free space. 21 */ 22 23 24 25 /* 26 * This controls certain optimisations that try to more quickly find available 27 * blocks. These optimisations tend to improve allocation performance in many 28 * cases, but they also tend to reduce resource packing efficiency. 29 * 30 * SHR_RES_BITMAP_SEARCH_RESUME: If TRUE, this module will track the first 31 * element of the last freed block and the next element after the last 32 * successful allocation, first trying a new alloc in the place of the last 33 * free, then starting its exhaustive search for available elements after the 34 * last successful alloc, wrapping around if needed. If FALSE, this module 35 * will not check the last freed location for suitability and will always 36 * start the exhaustive search from the low element. 37 */ 38 #define SHR_RES_BITMAP_SEARCH_RESUME TRUE 39 40 /* 41 * Provide WITH_ID when allocating a block and you want to specify the initial 42 * element of that block. 43 * 44 * Provide ALIGN_ZERO when allocating an aligned block and you want that block 45 * to be aligned against zero rather than against the low_id value used when 46 * creating the resource. 47 * 48 * Provide REPLACE when allocating WITH_ID to indicate you want to replace an 49 * existing block. Note this requires that the existing block be there in its 50 * entirety; it is an error to try to change the size of a block this way. 51 */ 52 #define SHR_RES_BITMAP_ALLOC_WITH_ID 0x00000001 53 #define SHR_RES_BITMAP_ALLOC_ALIGN_ZERO 0x00000002 54 #define SHR_RES_BITMAP_ALLOC_REPLACE 0x00000004 55 56 typedef struct _shr_res_bitmap_list_s { 57 int low; 58 int count; 59 int used; 60 #if SHR_RES_BITMAP_SEARCH_RESUME 61 int lastFree; 62 int nextAlloc; 63 #endif /* SHR_RES_BITMAP_SEARCH_RESUME */ 64 SHR_BITDCL data[1]; 65 } _shr_res_bitmap_list_t; 66 67 typedef _shr_res_bitmap_list_t *shr_res_bitmap_handle_t; 68 69 /* 70 * Function 71 * shr_res_bitmap_create 72 * Purpose 73 * Create a tagged bitmap resource 74 * Parameters 75 * (OUT) handle : where to put the handle 76 * (IN) low_id : minimum valid element ID 77 * (IN) count : number of elements total 78 * Returns 79 * BCM_E_NONE if successful 80 * BCM_E_* as appropriate otherwise 81 * Notes 82 */ 83 extern int 84 shr_res_bitmap_create(shr_res_bitmap_handle_t *handle, 85 int low_id, 86 int count); 87 88 /* 89 * Function 90 * shr_res_tag_bitmap_destroy 91 * Purpose 92 * Destroy a tagged bitmap resource 93 * Parameters 94 * (IN) handle : handle for the instance to access 95 * Returns 96 * BCM_E_NONE if successful 97 * BCM_E_* as appropriate otherwise 98 * Notes 99 */ 100 extern int 101 shr_res_bitmap_destroy(shr_res_bitmap_handle_t handle); 102 103 /* 104 * Function 105 * shr_res_bitmap_alloc 106 * Purpose 107 * Allocate an element or block of elements of a particular resource 108 * Parameters 109 * (IN) handle : handle for the instance to access 110 * (IN) flags : flags providing specifics of what/how to allocate 111 * (IN) count : elements to allocate in this block 112 * (IN/OUT) elem : where to put the allocated element (block base) 113 * Returns 114 * BCM_E_NONE if successful 115 * BCM_E_* as appropriate otherwise 116 * Notes 117 * The elem argument is IN if the WITH_ID flag is specified; it is OUT if 118 * the WITH_ID flag is not specified. 119 * 120 * This will allocate a single block of the requested number of elements 121 * of this resource. 122 * 123 * Partial blocks will not be allocated. 124 * 125 * The caller must track how many elements were requested and provide that 126 * number when freeing the block. 127 */ 128 extern int 129 shr_res_bitmap_alloc(shr_res_bitmap_handle_t handle, 130 uint32 flags, 131 int count, 132 int *elem); 133 134 /* 135 * Function 136 * shr_res_bitmap_alloc_align 137 * Purpose 138 * Allocate an element or block of elements of a particular resource, 139 * using a base alignment and an offset. 140 * Parameters 141 * (IN) handle : handle for the instance to access 142 * (IN) flags : flags providing specifics of what/how to allocate 143 * (IN) align : base alignment 144 * (IN) offs : offest from base alignment for first element 145 * (IN) count : elements to allocate in this block 146 * (IN/OUT) elem : where to put the allocated element (block base) 147 * Returns 148 * BCM_E_NONE if successful 149 * BCM_E_* as appropriate otherwise 150 * Notes 151 * The elem argument is IN if the WITH_ID flag is specified; it is OUT if 152 * the WITH_ID flag is not specified. If WITH_ID is specified, and the 153 * requested base element does not comply with the indicated alignment, 154 * BCM_E_PARAM will be returned. 155 * 156 * This will allocate a single block of the requested number of elements 157 * of this resource. 158 * 159 * The first element of the returned block will be at ((n * align) + 160 * offset), where n is some integer. If it is not possible to allocate a 161 * block with the requested constraints, the call will fail. Note that 162 * the alignment is within the specified range of the resource, and not 163 * specifically aligned against the absolute value zero; to request the 164 * alignment be against zero, specify the ALIGN_ZERO flag. 165 * 166 * If offset >= align, BCM_E_PARAM. If align is zero or negative, it will 167 * be treated as if it were 1. 168 * 169 * Partial blocks will not be allocated. 170 * 171 * The caller must track how many elements were requested and provide that 172 * number when freeing the block. 173 */ 174 extern int 175 shr_res_bitmap_alloc_align(shr_res_bitmap_handle_t handle, 176 uint32 flags, 177 int align, 178 int offs, 179 int count, 180 int *elem); 181 182 /* 183 * Function 184 * shr_res_bitmap_alloc_align_sparse 185 * Purpose 186 * Allocate an element or sparse block of elements of a particular 187 * resource, using a base alignment, an offset, a pattern. 188 * Parameters 189 * (IN) handle : handle for the instance to access 190 * (IN) flags : flags providing specifics of what/how to allocate 191 * (IN) align : base alignment 192 * (IN) offs : offest from base alignment for first element 193 * (IN) pattern : bitmapped pattern of elements 194 * (IN) length : length of pattern 195 * (IN) repeats : number of iterations of pattern 196 * (IN/OUT) elem : where to put the allocated element (block base) 197 * Returns 198 * BCM_E_NONE if successful 199 * BCM_E_* as appropriate otherwise 200 * Notes 201 * The elem argument is IN if the WITH_ID flag is specified; it is OUT if 202 * the WITH_ID flag is not specified. If WITH_ID is specified, and the 203 * requested base element does not comply with the indicated alignment, 204 * BCM_E_PARAM will be returned. 205 * 206 * This will allocate a single block of the requested number of elements 207 * of this resource. 208 * 209 * The first element of the returned block will be at ((n * align) + 210 * offset), where n is some integer. If it is not possible to allocate a 211 * block with the requested constraints, the call will fail. Note that 212 * the alignment is within the specified range of the resource, and not 213 * specifically aligned against the absolute value zero; to request the 214 * alignment be against zero, specify the ALIGN_ZERO flag. 215 * 216 * If offset >= align, BCM_E_PARAM. If align is zero or negative, it will 217 * be treated as if it were 1. 218 * 219 * Partial blocks will not be allocated. 220 * 221 * The pattern argument is a bitmap of the elements that are of interest 222 * in a single iteration of the pattern (and only the least significant 223 * 'length' bits are used; higher bits are ignored). The bit with value 224 * (1 << k) set indicates the element at (elem + k) must be in the block; 225 * clear it indicates the element at (elem + k) is not in the block. This 226 * repeats for as many iterations as indicated by 'repeats'. 227 * 228 * For example: 229 * align = 4, offs = 0, pattern = 0x7, length = 8, repeats = 2 would 230 * request a block of three elements, a gap of one element, and then 231 * another block of three elements, with the first allocated element 232 * aligned to a multiple of four. 233 * 234 * align = 8, offs = 1, pattern = 0x1, length = 2, repeats = 4 would 235 * request four oddly numbered elements with the first one allocated at 236 * (8 * n) + 1 where n is some arbitrary number. 237 * 238 * Note the bitmap is considered based at the requested alignment+offset, 239 * even if the least significant bit is not set, so it is probably 240 * simplest to ensure the LSb of pattern is set. 241 * 242 * For example: 243 * align = 4, offs = 0, pattern = 0xA, length = 4, repeats = 1 would 244 * request two elements, but the returned base element number would be 245 * (4 * n), while the actually allocated elements would be (4 * n) + 1 246 * and (4 * n) + 3. 247 * 248 * The caller must track the pattern, length and repeats values and 249 * provide these values along with the elem value when freeing the block. 250 * 251 * Any allocation made through this function must be freed using the 252 * shr_res_bitmap_free_sparse function. 253 */ 254 extern int 255 shr_res_bitmap_alloc_align_sparse(shr_res_bitmap_handle_t handle, 256 uint32 flags, 257 int align, 258 int offs, 259 uint32 pattern, 260 int length, 261 int repeats, 262 int *elem); 263 264 /* 265 * Function 266 * shr_res_bitmap_free 267 * Purpose 268 * Free an element or block of elements of a particular resource 269 * Parameters 270 * (IN) handle : handle for the instance to access 271 * (IN) count : elements in the block to free 272 * (IN) elem : the element to free (or base of the block to free) 273 * Returns 274 * BCM_E_NONE if successful 275 * BCM_E_* as appropriate otherwise 276 * Notes 277 * This will free a single block of the requested number of elements, 278 * starting at the specified element. 279 * 280 * This should only be called with valid data (base element and element 281 * count) against known allocated blocks. Trying to free a block that is 282 * not in use or trying to free something that spans multiple allocated 283 * blocks may not work. 284 * 285 * This function must not be used to free any allocation made through the 286 * shr_res_bitmap_alloc_align_sparse function. 287 */ 288 extern int 289 shr_res_bitmap_free(shr_res_bitmap_handle_t handle, 290 int count, 291 int elem); 292 293 /* 294 * Function 295 * shr_res_bitmap_free_sparse 296 * Purpose 297 * Free a sparse block of elements of a particular resource 298 * Parameters 299 * (IN) handle : handle for the instance to access 300 * (IN) pattern: pattern of elements 301 * (IN) length : length of pattern 302 * (IN) repeats: number of iterations of the pattern 303 * (IN) elem : the element to free (or base of the block to free) 304 * Returns 305 * BCM_E_NONE if successful 306 * BCM_E_* as appropriate otherwise 307 * Notes 308 * This will free a sparse block of elements, starting at the specified 309 * element and proceeding as specified. 310 * 311 * This should only be called with valid data (base element, pattern, 312 * length, repeats). Trying to free a block that is not in use or trying 313 * to free something that spans multiple allocated blocks may not work. 314 * 315 * Anything allocated with shr_res_bitmap_alloc_align_sparse must be freed 316 * using this function. While it is possible to use this function to free 317 * blocks allocated with other functions, it is not advised. 318 */ 319 extern int 320 shr_res_bitmap_free_sparse(shr_res_bitmap_handle_t handle, 321 uint32 pattern, 322 int length, 323 int repeats, 324 int elem); 325 326 /* 327 * Function 328 * shr_res_bitmap_check 329 * Purpose 330 * Check the status of a specific element 331 * Parameters 332 * (IN) handle : handle for the instance to access 333 * (IN) count : elements in the block to check 334 * (IN) elem : the element to check (or base of the block to check) 335 * Returns 336 * BCM_E_NOT_FOUND if the element is not in use 337 * BCM_E_EXISTS if the element is in use 338 * BCM_E_PARAM if the element is not valid 339 * BCM_E_* as appropriate otherwise 340 * Notes 341 * This will check whether the requested block of the resource is 342 * allocated. Note that if any element of the resource in the range of 343 * [elem..(elem+count-1)] (inclusive) is not free, it returns 344 * BCM_E_EXISTS; it will only return BCM_E_NOT_FOUND if all elements 345 * within the specified block are free. 346 * 347 * Normally this should be called to check on a specific block (one that 348 * is thought to exist or in preparation for allocating it WITH_ID. 349 */ 350 extern int 351 shr_res_bitmap_check(shr_res_bitmap_handle_t handle, 352 int count, 353 int elem); 354 355 /* 356 * Function 357 * shr_res_bitmap_check_all 358 * Purpose 359 * Check the status of a specific block of elements 360 * Parameters 361 * (IN) handle : handle for the instance to access 362 * (IN) count : elements in the block to check 363 * (IN) elem : the base of the block to check 364 * Returns 365 * BCM_E_EMPTY if none of the elements are in use 366 * BCM_E_FULL if all of the elements are in use 367 * BCM_E_CONFIG if elements are in use but block(s) do not match 368 * BCM_E_EXISTS if some of the elements are in use but not all of them 369 * BCM_E_PARAM if any of the elements is not valid 370 * BCM_E_* as appropriate otherwise 371 * Notes 372 * This will check whether the requested block of the resource is 373 * allocated. This returns BCM_E_FULL if the entire specified block is 374 * allocated, BCM_E_EMPTY if no element in the entire specified block is 375 * allocated, but if some elements are allocated and some not, it will 376 * return BCM_E_EXISTS. 377 * 378 * Normally this should be called to check on a specific block (one that 379 * is thought to exist or in preparation for allocating it WITH_ID. 380 * 381 * WARNING: The bitmap allocator does not track blocks internally and so 382 * it is possible that if there are two adjacent blocks both allocated and 383 * this is called to check whether safe to 'reallocate', will falsely 384 * indicate that it can be done. Also, 'reallocate' in a similar manner 385 * of a large block to a smaller one could leak underlying resources. 386 */ 387 extern int 388 shr_res_bitmap_check_all(shr_res_bitmap_handle_t handle, 389 int count, 390 int elem); 391 392 /* 393 * Function 394 * shr_res_bitmap_check_all_sparse 395 * Purpose 396 * Check the status of a specific sparse block of elements 397 * Parameters 398 * (IN) handle : handle for the instance to access 399 * (IN) pattern: pattern of elements to check 400 * (IN) length : length of pattern 401 * (IN) repeats: number of time pattern repeats 402 * (IN) elem : the base of the first pattern 403 * Returns 404 * BCM_E_EMPTY if none of the elements are in use 405 * BCM_E_FULL if all of the elements are in use 406 * BCM_E_CONFIG if elements are in use but block(s) do not match 407 * BCM_E_EXISTS if some of the elements are in use but not all of them 408 * BCM_E_PARAM if any of the elements is not valid 409 * BCM_E_* as appropriate otherwise 410 * Notes 411 * This will check whether the requested sparse block of the resource is 412 * allocated. If all of the specified elements are allocated, it will 413 * return BCM_E_FULL; if all of the specified elements are free, it will 414 * return BCM_E_EMPTY; if some of the specified elements are allocated and 415 * some are free, it will return BCM_E_EXISTS. 416 * 417 * See shr_res_bitmap_sparse_alloc_align_sparse for information about 418 * how sparse patterns are specified. 419 * 420 * Normally this should be called to check on a specific block (one that 421 * is thought to exist or in preparation for allocating it WITH_ID. 422 * 423 * WARNING: The bitmap allocator does not track blocks internally and so 424 * it is possible that if there are two adjacent blocks both allocated and 425 * this is called to check whether safe to 'reallocate', will falsely 426 * indicate that it can be done. Also, 'reallocate' in a similar manner 427 * of a large block to a smaller one could leak underlying resources. 428 */ 429 extern int 430 shr_res_bitmap_check_all_sparse(shr_res_bitmap_handle_t handle, 431 uint32 pattern, 432 int length, 433 int repeats, 434 int elem); 435 436 /* 437 * Function 438 * shr_res_bitmap_dump 439 * Purpose 440 * Dump the internal state of a tagged bitmap allocator 441 * Parameters 442 * (IN) handle : handle for instance to dump 443 * Returns 444 * BCM_E_PARAM if handle is clearly bogus 445 * BCM_E_INTERNAL if there is obvious corruption 446 * BCM_E_NONE usually for successful dump 447 * BCM_E_* otherwise as appropriate 448 * Notes 449 * There is very little that can be verified for corruption in the tagged 450 * bitmap allocator, particularly if the search resume feature is off, and 451 * even if it is on, still rather little. 452 */ 453 extern int 454 shr_res_bitmap_dump(const shr_res_bitmap_handle_t handle); 455 456 #endif /* ndef _SHR_RES_BITMAP_H_ */ 457