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