defragment.c (9403B)
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 * Provides generic routines for defragmenting member tables. 8 */ 9 10 #include <soc/defragment.h> 11 #include <soc/drv.h> 12 13 /* 14 * Function: 15 * soc_defragment_block_cmp 16 * Purpose: 17 * Compare two blocks of member table entries based on their starting 18 * index. 19 * Parameters: 20 * a - (IN) First block. 21 * b - (IN) Second block. 22 * Returns: 23 * -1 if a < b, 0 if a = b, 1 if a > b. 24 */ 25 STATIC int 26 soc_defragment_block_cmp(void *a, void *b) 27 { 28 soc_defragment_block_t *block_a, *block_b; 29 30 block_a = (soc_defragment_block_t *)a; 31 block_b = (soc_defragment_block_t *)b; 32 33 if (block_a->base_ptr < block_b->base_ptr) { 34 return -1; 35 } 36 37 if (block_a->base_ptr == block_b->base_ptr) { 38 return 0; 39 } 40 41 return 1; 42 } 43 44 /* 45 * Function: 46 * soc_defragment_block_move 47 * Purpose: 48 * Move a block of member table entries. 49 * Parameters: 50 * unit - (IN) Unit 51 * src_base_ptr - (IN) Starting index of the source block. 52 * dst_base_ptr - (IN) Starting index of the destination block. 53 * block_size - (IN) Number of entries to move. 54 * member_op - (IN) Operations on member table entry 55 * group - (IN) The group this block belongs to 56 * group_op - (IN) Operations on group table entry 57 * Returns: 58 * SOC_E_xxx 59 */ 60 int 61 soc_defragment_block_move(int unit, int src_base_ptr, int dst_base_ptr, 62 int block_size, soc_defragment_member_op_t *member_op, 63 int group, soc_defragment_group_op_t *group_op) 64 { 65 int i; 66 int rv; 67 68 /* Copy source block to destination block */ 69 for (i = 0; i < block_size; i++) { 70 rv = (*member_op->member_copy)(unit, src_base_ptr + i, dst_base_ptr + i); 71 SOC_IF_ERROR_RETURN(rv); 72 } 73 74 /* Update group's base pointer to point to destination block */ 75 rv = (*group_op->group_base_ptr_update)(unit, group, dst_base_ptr); 76 SOC_IF_ERROR_RETURN(rv); 77 78 /* Clear source block */ 79 for (i = 0; i < block_size; i++) { 80 rv = (*member_op->member_clear)(unit, src_base_ptr + i); 81 SOC_IF_ERROR_RETURN(rv); 82 } 83 84 return SOC_E_NONE; 85 } 86 87 /* 88 * Function: 89 * soc_defragment 90 * Purpose: 91 * Defragment a member table. 92 * Parameters: 93 * unit - (IN) Unit 94 * block_count - (IN) Number of blocks in block_array 95 * block_array - (IN) Used blocks of member table entries 96 * reserved_block - (IN) Reserved block of member table entries used as 97 * defragmentation buffer 98 * member_table_size - (IN) Number of entries in member table 99 * member_op - (IN) Operations on member table entry 100 * group_op - (IN) Operations on group table entry 101 * free_block_base_ptr - (IN) pointer to the beginning of the member table 102 * Returns: 103 * SOC_E_xxx 104 */ 105 int 106 soc_defragment(int unit, int block_count, 107 soc_defragment_block_t *block_array, 108 soc_defragment_block_t *reserved_block, 109 int member_table_size, 110 soc_defragment_member_op_t *member_op, 111 soc_defragment_group_op_t *group_op, 112 int free_block_base_ptr) 113 { 114 soc_defragment_block_t *sorted_block_array = NULL; 115 int reserved_block_base_ptr, reserved_block_size; 116 int free_block_size; 117 int gap_base_ptr, gap_size; 118 int block_base_ptr, block_size; 119 int max_block_size; 120 int group; 121 int i; 122 int rv; 123 124 if (0 == block_count) { 125 /* If no member entries are used, there is no need to defragment. */ 126 return SOC_E_NONE; 127 } 128 129 if (NULL == block_array) { 130 return SOC_E_PARAM; 131 } 132 133 if (NULL == reserved_block) { 134 return SOC_E_PARAM; 135 } 136 137 if (NULL == group_op) { 138 return SOC_E_PARAM; 139 } 140 141 if (NULL == member_op) { 142 return SOC_E_PARAM; 143 } 144 145 /* Sort the block array by block's base pointer */ 146 sorted_block_array = sal_alloc(block_count * sizeof(soc_defragment_block_t), 147 "sorted block array"); 148 if (NULL == sorted_block_array) { 149 return SOC_E_MEMORY; 150 } 151 sal_memcpy(sorted_block_array, block_array, 152 block_count * sizeof(soc_defragment_block_t)); 153 _shr_sort(sorted_block_array, block_count, sizeof(soc_defragment_block_t), 154 soc_defragment_block_cmp); 155 156 /* Gap compression should start from this base */ 157 gap_base_ptr = free_block_base_ptr; 158 159 /* Get defragmentation buffer */ 160 if (0 == reserved_block->size) { 161 /* If a reserved block is not given, find the largest free block of 162 * entries in the member table and use it as the defragmentation 163 * buffer. 164 */ 165 reserved_block_size = 0; 166 reserved_block_base_ptr = 0; 167 for (i = 0; i < block_count; i++) { 168 free_block_size = sorted_block_array[i].base_ptr - 169 free_block_base_ptr; 170 if (free_block_size > reserved_block_size) { 171 reserved_block_size = free_block_size; 172 reserved_block_base_ptr = free_block_base_ptr; 173 } 174 free_block_base_ptr = sorted_block_array[i].base_ptr + 175 sorted_block_array[i].size; 176 } 177 178 /* Also need to compute the free block size between the end of the 179 * final used block and the end of the member table. 180 */ 181 free_block_size = member_table_size - free_block_base_ptr; 182 if (free_block_size > reserved_block_size) { 183 reserved_block_size = free_block_size; 184 reserved_block_base_ptr = free_block_base_ptr; 185 } 186 } else { 187 reserved_block_size = reserved_block->size; 188 reserved_block_base_ptr = reserved_block->base_ptr; 189 } 190 191 /* Find maximum block size */ 192 max_block_size = 0; 193 for (i = 0; i < block_count; i++) { 194 if (sorted_block_array[i].size > max_block_size) { 195 max_block_size = sorted_block_array[i].size; 196 } 197 } 198 199 /* Compress the gaps between used blocks */ 200 for (i = 0; i < block_count; i++) { 201 block_base_ptr = sorted_block_array[i].base_ptr; 202 block_size = sorted_block_array[i].size; 203 group = sorted_block_array[i].group; 204 205 gap_size = block_base_ptr - gap_base_ptr; 206 if (block_base_ptr > reserved_block_base_ptr) { 207 if (gap_base_ptr <= reserved_block_base_ptr) { 208 if (0 == reserved_block->size) { 209 if (gap_size < max_block_size) { 210 /* Skip over the reserved block */ 211 gap_base_ptr = reserved_block_base_ptr + 212 reserved_block_size; 213 gap_size = block_base_ptr - gap_base_ptr; 214 } 215 } else { 216 gap_size = reserved_block_base_ptr - gap_base_ptr; 217 if (gap_size < block_size) { 218 /* Skip over the reserved block */ 219 gap_base_ptr = reserved_block_base_ptr + 220 reserved_block_size; 221 gap_size = block_base_ptr - gap_base_ptr; 222 } 223 } 224 } 225 } 226 227 if (gap_size == 0) { 228 gap_base_ptr = block_base_ptr + block_size; 229 } else if (gap_size > 0) { 230 if (block_size <= gap_size) { 231 /* Block fits into the gap. Move it directly into the gap. */ 232 rv = soc_defragment_block_move(unit, block_base_ptr, 233 gap_base_ptr, block_size, member_op, group, group_op); 234 if (SOC_FAILURE(rv)) { 235 sal_free(sorted_block_array); 236 return rv; 237 } 238 239 /* Move gap_base_ptr */ 240 gap_base_ptr += block_size; 241 242 } else if (block_size <= reserved_block_size) { 243 /* Block is bigger than the gap but fits into the 244 * defragmentation buffer. Move it first into the 245 * defragmentation buffer, then into the gap. 246 */ 247 rv = soc_defragment_block_move(unit, block_base_ptr, 248 reserved_block_base_ptr, block_size, member_op, 249 group, group_op); 250 if (SOC_FAILURE(rv)) { 251 sal_free(sorted_block_array); 252 return rv; 253 } 254 rv = soc_defragment_block_move(unit, reserved_block_base_ptr, 255 gap_base_ptr, block_size, member_op, group, group_op); 256 if (SOC_FAILURE(rv)) { 257 sal_free(sorted_block_array); 258 return rv; 259 } 260 261 /* Move gap_base_ptr */ 262 gap_base_ptr += block_size; 263 264 } else { 265 /* Block is bigger than the gap and the defragmentation 266 * buffer. It cannot be moved. Skip over it. 267 */ 268 gap_base_ptr = block_base_ptr + block_size; 269 } 270 } else { 271 /* Gap size shoud never be negative. */ 272 sal_free(sorted_block_array); 273 return SOC_E_INTERNAL; 274 } 275 } 276 277 sal_free(sorted_block_array); 278 return SOC_E_NONE; 279 } 280