trie_util.c (10370B)
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 * File: trie_util.c 7 * Purpose: Trident2 Trie utility functions 8 * Requires: 9 */ 10 11 #include <soc/types.h> 12 #include <soc/drv.h> 13 #include <shared/bsl.h> 14 #ifdef ALPM_ENABLE 15 #ifdef BCM_TRIDENT2_SUPPORT 16 #ifndef ALPM_IPV6_128_SUPPORT 17 18 #include <soc/esw/trie.h> 19 #include <soc/esw/trie_util.h> 20 21 static int _taps_util_debug = FALSE; 22 /* 23 * 24 * Function: 25 * taps_show_prefix 26 * Input: 27 * key -- uint32 array head. Only "length" number of bits 28 * is passed in. 29 * for ipv4. Key[0].bit15-0 is key bits 47-32 30 * Key[1] is key bits 31-0 31 * for ipv6. Key[0].bit15-0 is key bits 143-128 32 * Key[1-4] is key bits 127-0 33 * length-- number of valid bits in key array. This would be 34 * valid MSB bits of the route. For example, 35 * (vrf=0x1234, ip=0xf0000000, length=20) would store 36 * as key[0] = 0, key[1]=0x1234F, length=20. 37 * Purpose: 38 * print a prefix if "dbm soc verbose" 39 */ 40 int taps_show_prefix(uint32 max_key_size, uint32 *key, uint32 length) 41 { 42 int word, max_words, key_words; 43 44 if ((key == NULL) || 45 (length > max_key_size) || 46 ((max_key_size != TAPS_IPV4_KEY_SIZE) && 47 (max_key_size != TAPS_IPV6_KEY_SIZE))) { 48 return SOC_E_PARAM; 49 } 50 51 LOG_VERBOSE(BSL_LS_SOC_COMMON, 52 (BSL_META("prefix length %d key 0x"), length)); 53 54 key_words = (length+31)/32; 55 max_words = (max_key_size+31)/32; 56 for (word = 0; word < max_words; word++) { 57 if (word == (max_words-key_words)) { 58 LOG_VERBOSE(BSL_LS_SOC_COMMON, 59 (BSL_META("%x"), key[word])); 60 } else if (word > (max_words-key_words)) { 61 LOG_VERBOSE(BSL_LS_SOC_COMMON, 62 (BSL_META("%08x"), key[word])); 63 } 64 } 65 66 LOG_VERBOSE(BSL_LS_SOC_COMMON, 67 (BSL_META("\n"))); 68 69 return SOC_E_NONE; 70 } 71 72 /* 73 * 74 * Function: 75 * taps_key_shift 76 * Input: 77 * max_key_size -- max number of bits in the key 78 * ipv4 == 48 79 * ipv4 == 144 80 * key -- uint32 array head. Only "length" number of bits 81 * is passed in. 82 * for ipv4. Key[0].bit15-0 is key bits 47-32 83 * Key[1] is key bits 31-0 84 * for ipv6. Key[0].bit15-0 is key bits 143-128 85 * Key[1-4] is key bits 127-0 86 * length-- number of valid bits in key array. This would be 87 * valid MSB bits of the route. For example, 88 * (vrf=0x1234, ip=0xf0000000, length=20) would store 89 * as key[0] = 0, key[1]=0x1234F, length=20. 90 * shift -- positive means right shift, negative means left shift 91 * routine will check if the shifted key is out of 92 * max_key_size boundary. 93 */ 94 int taps_key_shift(uint32 max_key_size, uint32 *key, uint32 length, int32 shift) 95 { 96 int word_idx, lsb; 97 98 if ((key == NULL) || 99 (length > max_key_size) || 100 ((max_key_size != TAPS_IPV4_KEY_SIZE) && 101 (max_key_size != TAPS_IPV6_KEY_SIZE))) { 102 return SOC_E_PARAM; 103 } 104 105 if (((length - shift) > max_key_size) || 106 ((shift > 0) && (shift > length))) { 107 /* left shift resulted in key longer than max_key_size or 108 * right shift resulted in key shorter than 0 109 */ 110 return SOC_E_PARAM; 111 } 112 113 if (_taps_util_debug) { 114 LOG_VERBOSE(BSL_LS_SOC_COMMON, 115 (BSL_META("Original key before shift:\n"))); 116 taps_show_prefix(max_key_size, key, length); 117 } 118 119 if (shift > 0) { 120 /* right shift */ 121 for (lsb = shift, word_idx=BITS2WORDS(max_key_size)-1; 122 word_idx >=0; 123 lsb+=32, word_idx--) { 124 if (lsb < length) { 125 key[word_idx] = _TAPS_GET_KEY_BITS(key, lsb, ((length-lsb)>=32)?32:(length-lsb), 126 max_key_size); 127 } else { 128 key[word_idx] = 0; 129 } 130 } 131 } else if (shift < 0) { 132 /* left shift */ 133 shift = 0 - shift; 134 135 /* whole words shifting first */ 136 for (word_idx = 0; 137 ((shift/32)!=0) && (word_idx < BITS2WORDS(max_key_size)); 138 word_idx++) { 139 if ((word_idx + (shift/32)) >= BITS2WORDS(max_key_size)) { 140 key[word_idx]=0; 141 } else { 142 key[word_idx] = key[word_idx + (shift/32)]; 143 } 144 } 145 146 /* shifting remaining bits */ 147 for (word_idx = 0; 148 ((shift%32)!=0) && (word_idx < BITS2WORDS(max_key_size)); 149 word_idx++) { 150 if (word_idx == TP_BITS2IDX(0, max_key_size)) { 151 /* at bit 0 word, next word doesn't exist */ 152 key[word_idx] = TP_SHL(key[word_idx], (shift%32)); 153 } else { 154 key[word_idx] = TP_SHL(key[word_idx], (shift%32)) | \ 155 TP_SHR(key[word_idx+1], 32-(shift%32)); 156 } 157 } 158 159 /* mask off bits higher than max_key_size */ 160 key[0] &= TP_MASK(max_key_size%32); 161 } 162 163 if (_taps_util_debug) { 164 LOG_VERBOSE(BSL_LS_SOC_COMMON, 165 (BSL_META("Resulted key after shift:\n"))); 166 taps_show_prefix(max_key_size, key, length-shift); 167 } 168 169 return SOC_E_NONE; 170 } 171 172 /* 173 * 174 * Function: 175 * taps_key_match 176 * Input: 177 * max_key_size -- max number of bits in the key 178 * ipv4 == 48 179 * ipv4 == 144 180 * key1 -- uint32 array head for first key. Only "length1" number of bits 181 * is passed in. 182 * for ipv4. Key[0].bit15-0 is key bits 47-32 183 * Key[1] is key bits 31-0 184 * for ipv6. Key[0].bit15-0 is key bits 143-128 185 * Key[1-4] is key bits 127-0 186 * length1-- number of valid bits in key1 array. This would be 187 * valid MSB bits of the route. For example, 188 * (vrf=0x1234, ip=0xf0000000, length=20) would store 189 * as key[0] = 0, key[1]=0x1234F, length=20. 190 * key2 -- uint32 array head for second key. Only "length2" number of bits 191 * is passed in. 192 * for ipv4. Key[0].bit15-0 is key bits 47-32 193 * Key[1] is key bits 31-0 194 * for ipv6. Key[0].bit15-0 is key bits 143-128 195 * Key[1-4] is key bits 127-0 196 * length2-- number of valid bits in key2 array. This would be 197 * valid MSB bits of the route. For example, 198 * (vrf=0x1234, ip=0xf0000000, length=20) would store 199 * as key[0] = 0, key[1]=0x1234F, length=20. 200 * Purpose: 201 * Return TRUE if the all the valid bits of the shorter key matches 202 * the corresponding bits of the longer key. Otherwise return FALSE. 203 * 204 * This function does NOT modify either keys. 205 * 206 * max_key_length supported is 256 bits. 207 */ 208 int taps_key_match(uint32 max_key_size, uint32 *key1, uint32 length1, 209 uint32 *key2, uint32 length2) 210 { 211 #define _TAPS_UTIL_MAX_MATCH_KEY_SIZE (256) 212 213 uint32 tmp_key1[BITS2WORDS(_TAPS_UTIL_MAX_MATCH_KEY_SIZE)]; 214 uint32 tmp_key2[BITS2WORDS(_TAPS_UTIL_MAX_MATCH_KEY_SIZE)]; 215 int rv = SOC_E_NONE; 216 int index; 217 218 if (_taps_util_debug) { 219 LOG_VERBOSE(BSL_LS_SOC_COMMON, 220 (BSL_META("key1:\n"))); 221 taps_show_prefix(max_key_size, key1, length1); 222 223 LOG_VERBOSE(BSL_LS_SOC_COMMON, 224 (BSL_META("key2:\n"))); 225 taps_show_prefix(max_key_size, key2, length2); 226 } 227 228 /* copy key bits */ 229 for (index=0; index<BITS2WORDS(max_key_size); index++) { 230 tmp_key1[index] = key1[index]; 231 tmp_key2[index] = key2[index]; 232 } 233 234 /* shift out the LSBs of the longer key */ 235 if (length1 > length2) { 236 rv = taps_key_shift(max_key_size, tmp_key1, length1, (length1-length2)); 237 } else if (length2 > length1) { 238 rv = taps_key_shift(max_key_size, tmp_key2, length2, (length2-length1)); 239 } 240 if (rv != SOC_E_NONE) { 241 LOG_VERBOSE(BSL_LS_SOC_COMMON, 242 (BSL_META("taps key shift failed 0x%x\n"),rv)); 243 } 244 245 for (index=0; index<BITS2WORDS(max_key_size); index++) { 246 if (tmp_key1[index] != tmp_key2[index]) { 247 /* some bits not matching */ 248 if (_taps_util_debug) { 249 LOG_VERBOSE(BSL_LS_SOC_COMMON, 250 (BSL_META("Key1 and key2 not matching:\n"))); 251 } 252 return FALSE; 253 } 254 } 255 256 /* all matched */ 257 if (_taps_util_debug) { 258 LOG_VERBOSE(BSL_LS_SOC_COMMON, 259 (BSL_META("Key1 and key2 matched:\n"))); 260 } 261 return TRUE; 262 } 263 264 /* 265 * 266 * Function: 267 * taps_get_lsb 268 * Input: 269 * max_mask_size -- number of bits in the mask 270 * ipv4 == 48 271 * ipv6 == 144 272 * mask -- uint32 array head. 273 * for ipv4. Mask[0].bit15-0 is mask bits 47-32 274 * Mask[1] is mask bits 31-0 275 * for ipv6. Mask[0].bit15-0 is mask bits 143-128 276 * Mask[1-4] is mask bits 127-0 277 * lsb -- -1 if no bit is set. bit position of the least 278 * significant bit that is set to 1 279 * Purpose: 280 * get the bit position of the least significant bit that is set in mask. 281 * for example: 282 * for ipv4, max_mask_size == 48 283 * mask[0]=0, mask[1]=0x30 will return lsb=4 284 * mask[0]=3, mask[1]=0 will return lsb=32 285 */ 286 int taps_get_lsb(uint32 max_mask_size, uint32 *mask, int32 *lsb) 287 { 288 int word_idx, bit_idx; 289 290 if (!mask || !lsb) { 291 return SOC_E_PARAM; 292 } 293 294 *lsb = -1; 295 for (word_idx = (BITS2WORDS(max_mask_size)-1); word_idx >=0; word_idx--) { 296 if (mask[word_idx]!=0) { 297 for (bit_idx=0; bit_idx<32; bit_idx++) { 298 if ((mask[word_idx] & (1<<bit_idx)) && 299 (((BITS2WORDS(max_mask_size) - 1 - word_idx) * 32 + bit_idx) < max_mask_size)) { 300 *lsb = (BITS2WORDS(max_mask_size) - 1 - word_idx) * 32 + bit_idx; 301 return SOC_E_NONE; 302 } 303 } 304 } 305 } 306 307 return SOC_E_NONE; 308 } 309 310 /* 311 * Function: 312 * taps_get_bpm_pfx 313 * Purpose: 314 * finds best prefix match length given a bpm bitmap & key 315 */ 316 int taps_get_bpm_pfx(unsigned int *bpm, 317 unsigned int key_len, 318 unsigned int max_key_len, 319 /* OUT */ 320 unsigned int *pfx_len) 321 { 322 int rv = SOC_E_NONE, pos=0; 323 324 if (!bpm || !pfx_len || (key_len > max_key_len)) { 325 return SOC_E_PARAM; 326 } 327 328 *pfx_len = 0; 329 330 rv = taps_get_lsb(max_key_len, bpm, &pos); 331 if (SOC_SUCCESS(rv)) { 332 *pfx_len = (pos < 0)?0:(key_len - pos); 333 } 334 return rv; 335 } 336 #endif /* ALPM_IPV6_128_SUPPORT */ 337 #endif /* BCM_TRIDENT2_SUPPORT */ 338 #endif /* ALPM_ENABLE */