hash.c (15779B)
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 * File: hash.c 8 * Purpose: Katana2 hash table calculation routines 9 * Requires: 10 */ 11 12 #include <soc/drv.h> 13 #include <soc/mem.h> 14 #include <soc/debug.h> 15 #include <soc/hash.h> 16 #include <shared/bsl.h> 17 #if defined(BCM_KATANA2_SUPPORT) 18 19 #include <soc/katana2.h> 20 21 22 STATIC int 23 _soc_kt2_hash_generic_entry_to_key(int unit, void *entry, uint8 *key, 24 soc_mem_t mem, soc_field_t *field_list) 25 { 26 soc_field_t field; 27 int index, key_index, val_index, fval_index; 28 int right_shift_count, left_shift_count; 29 uint32 val[SOC_MAX_MEM_WORDS], fval[SOC_MAX_MEM_WORDS]; 30 int bits, val_bits, fval_bits; 31 int8 field_length[16]; 32 33 val_bits = 0; 34 for (index = 0; field_list[index] != INVALIDf; index++) { 35 field = field_list[index]; 36 field_length[index] = soc_mem_field_length(unit, mem, field); 37 #ifdef BCM_METROLITE_SUPPORT 38 if ((field == L3_IIFf) && SOC_IS_METROLITE(unit)) { 39 /* L3_IIF field is 9 bits but hash key considers it as 13 bits */ 40 field_length[index] += 4; /*13 - 9*/ 41 } 42 #endif 43 val_bits += field_length[index]; 44 } 45 46 switch (mem) { 47 case L2Xm: 48 val_bits = soc_mem_field_length(unit, L2Xm, L2__KEYf); 49 break; 50 case L3_ENTRY_ONLYm: 51 case L3_ENTRY_IPV4_UNICASTm: 52 case L3_ENTRY_IPV6_UNICASTm: 53 case L3_ENTRY_IPV4_MULTICASTm: 54 case L3_ENTRY_IPV6_MULTICASTm: 55 val_bits = 274; 56 #ifdef BCM_SABER2_SUPPORT 57 if (SOC_IS_SABER2(unit)) { 58 val_bits = 271; 59 } 60 #endif 61 break; 62 case VLAN_XLATEm: 63 case VLAN_MACm: 64 val_bits = 52; 65 break; 66 case EGR_VLAN_XLATEm: 67 val_bits = 42; 68 break; 69 case MPLS_ENTRYm: 70 val_bits = 63; 71 break; 72 default: 73 break; 74 } 75 76 bits = (val_bits + 7) & ~0x7; 77 sal_memset(val, 0, sizeof(val)); 78 val_bits = bits - val_bits; 79 for (index = 0; field_list[index] != INVALIDf; index++) { 80 field = field_list[index]; 81 #ifdef BCM_METROLITE_SUPPORT 82 sal_memset(fval, 0, sizeof(fval)); 83 #endif 84 soc_mem_field_get(unit, mem, entry, field, fval); 85 fval_bits = field_length[index]; 86 87 val_index = val_bits >> 5; 88 fval_index = 0; 89 left_shift_count = val_bits & 0x1f; 90 right_shift_count = 32 - left_shift_count; 91 val_bits += fval_bits; 92 93 if (left_shift_count) { 94 for (; fval_bits > 0; fval_bits -= 32) { 95 val[val_index++] |= fval[fval_index] << left_shift_count; 96 val[val_index] |= fval[fval_index++] >> right_shift_count; 97 } 98 } else { 99 for (; fval_bits > 0; fval_bits -= 32) { 100 val[val_index++] = fval[fval_index++]; 101 } 102 } 103 } 104 105 key_index = 0; 106 for (val_index = 0; val_bits > 0; val_index++) { 107 for (right_shift_count = 0; right_shift_count < 32; 108 right_shift_count += 8) { 109 if (val_bits <= 0) { 110 break; 111 } 112 key[key_index++] = (val[val_index] >> right_shift_count) & 0xff; 113 val_bits -= 8; 114 } 115 } 116 117 if ((bits + 7) / 8 > key_index) { 118 sal_memset(&key[key_index], 0, (bits + 7) / 8 - key_index); 119 } 120 121 return bits; 122 } 123 124 int 125 soc_kt2_l2x_base_entry_to_key(int unit, uint32 *entry, uint8 *key) 126 { 127 soc_field_t field_list[2]; 128 129 switch (soc_mem_field32_get(unit, L2Xm, entry, KEY_TYPEf)) { 130 case KT2_L2_HASH_KEY_TYPE_BRIDGE: 131 case KT2_L2_HASH_KEY_TYPE_VFI: 132 field_list[0] = L2__KEYf; 133 break; 134 case KT2_L2_HASH_KEY_TYPE_SINGLE_CROSS_CONNECT: 135 case KT2_L2_HASH_KEY_TYPE_DOUBLE_CROSS_CONNECT: 136 field_list[0] = VLAN__KEYf; 137 break; 138 case KT2_L2_HASH_KEY_TYPE_VIF: 139 field_list[0] = VIF__KEYf; 140 break; 141 case KT2_L2_HASH_KEY_TYPE_BFD: 142 field_list[0] = BFD__KEYf; 143 break; 144 case KT2_L2_HASH_KEY_TYPE_PE_VID: 145 field_list[0] = PE_VID__KEYf; 146 break; 147 default: 148 return 0; 149 } 150 field_list[1] = INVALIDf; 151 return _soc_kt2_hash_generic_entry_to_key(unit, entry, key, L2Xm, 152 field_list); 153 } 154 155 156 int 157 soc_kt2_l3x_base_entry_to_key(int unit, uint32 *entry, uint8 *key) 158 { 159 soc_mem_t mem; 160 soc_field_t field_list[8]; 161 void *ptr; 162 163 ptr = entry; 164 165 switch (soc_mem_field32_get(unit, L3_ENTRY_ONLYm, entry, KEY_TYPEf)) { 166 case KT2_L3_HASH_KEY_TYPE_V4UC: 167 mem = L3_ENTRY_IPV4_UNICASTm; 168 field_list[0] = IP_ADDRf; 169 field_list[1] = VRF_IDf; 170 field_list[2] = KEY_TYPEf; 171 field_list[3] = INVALIDf; 172 break; 173 case KT2_L3_HASH_KEY_TYPE_V4MC: 174 mem = L3_ENTRY_IPV4_MULTICASTm; 175 field_list[0] = GROUP_IP_ADDRf; 176 field_list[1] = SOURCE_IP_ADDRf; 177 field_list[2] = L3_IIFf; 178 field_list[3] = VRF_IDf; 179 field_list[4] = KEY_TYPE_0f; 180 field_list[5] = INVALIDf; 181 break; 182 case KT2_L3_HASH_KEY_TYPE_V6UC: 183 mem = L3_ENTRY_IPV6_UNICASTm; 184 field_list[0] = IP_ADDR_LWR_64f; 185 field_list[1] = IP_ADDR_UPR_64f; 186 field_list[2] = VRF_IDf; 187 field_list[3] = KEY_TYPE_0f; 188 field_list[4] = INVALIDf; 189 break; 190 case KT2_L3_HASH_KEY_TYPE_V6MC: 191 mem = L3_ENTRY_IPV6_MULTICASTm; 192 field_list[0] = GROUP_IP_ADDR_LWR_64f; 193 field_list[1] = GROUP_IP_ADDR_UPR_56f; 194 field_list[2] = SOURCE_IP_ADDR_LWR_64f; 195 field_list[3] = SOURCE_IP_ADDR_UPR_64f; 196 field_list[4] = L3_IIFf; 197 field_list[5] = VRF_IDf; 198 field_list[6] = KEY_TYPE_0f; 199 field_list[7] = INVALIDf; 200 break; 201 default: 202 return 0; 203 } 204 return _soc_kt2_hash_generic_entry_to_key(unit, ptr, key, mem, field_list); 205 } 206 207 208 int 209 soc_kt2_vlan_xlate_base_entry_to_key(int unit, void *entry, uint8 *key) 210 { 211 soc_mem_t mem; 212 soc_field_t field_list[8]; 213 214 switch (soc_mem_field32_get(unit, VLAN_XLATEm, entry, KEY_TYPEf)) { 215 case KT2_VLXLT_HASH_KEY_TYPE_IVID_OVID: 216 case KT2_VLXLT_HASH_KEY_TYPE_OTAG: 217 case KT2_VLXLT_HASH_KEY_TYPE_ITAG: 218 case KT2_VLXLT_HASH_KEY_TYPE_OVID: 219 case KT2_VLXLT_HASH_KEY_TYPE_IVID: 220 case KT2_VLXLT_HASH_KEY_TYPE_PRI_CFI: 221 mem = VLAN_XLATEm; 222 field_list[0] = XLATE__KEYf; 223 field_list[1] = INVALIDf; 224 break; 225 case KT2_VLXLT_HASH_KEY_TYPE_VIF: 226 case KT2_VLXLT_HASH_KEY_TYPE_VIF_VLAN: 227 case KT2_VLXLT_HASH_KEY_TYPE_VIF_CVLAN: 228 case KT2_VLXLT_HASH_KEY_TYPE_VIF_OTAG: 229 case KT2_VLXLT_HASH_KEY_TYPE_VIF_ITAG: 230 mem = VLAN_XLATEm; 231 field_list[0] = VIF__KEYf; 232 field_list[1] = INVALIDf; 233 break; 234 235 case KT2_VLXLT_HASH_KEY_TYPE_LLTAG_VID: 236 case KT2_VLXLT_HASH_KEY_TYPE_LLVID_IVID: 237 case KT2_VLXLT_HASH_KEY_TYPE_LLVID_OVID: 238 mem = VLAN_XLATEm; 239 field_list[0] = LLTAG__KEYf; 240 field_list[1] = INVALIDf; 241 break; 242 case KT2_VLXLT_HASH_KEY_TYPE_VLAN_MAC: 243 mem = VLAN_MACm; 244 field_list[0] = MAC__KEYf; 245 field_list[1] = INVALIDf; 246 break; 247 case KT2_VLXLT_HASH_KEY_TYPE_HPAE: 248 mem = VLAN_MACm; 249 field_list[0] = MAC_IP_BIND__KEYf; 250 field_list[1] = INVALIDf; 251 break; 252 default: 253 return 0; 254 } 255 return _soc_kt2_hash_generic_entry_to_key(unit, entry, key, mem, 256 field_list); 257 } 258 259 int 260 soc_kt2_egr_vlan_xlate_base_entry_to_key(int unit, void *entry, uint8 *key) 261 { 262 soc_field_t field_list[2]; 263 264 switch (soc_mem_field32_get(unit, EGR_VLAN_XLATEm, entry, ENTRY_TYPEf)) { 265 case KT2_EVLXLT_HASH_KEY_TYPE_VLAN_XLATE: 266 case KT2_EVLXLT_HASH_KEY_TYPE_VLAN_XLATE_DVP: 267 field_list[0] = XLATE__KEYf; 268 break; 269 case KT2_EVLXLT_HASH_KEY_TYPE_ISID_XLATE: 270 case KT2_EVLXLT_HASH_KEY_TYPE_ISID_DVP_XLATE: 271 field_list[0] = MIM_ISID__KEYf; 272 break; 273 default: 274 return 0; 275 } 276 field_list[1] = INVALIDf; 277 return _soc_kt2_hash_generic_entry_to_key(unit, entry, key, 278 EGR_VLAN_XLATEm, field_list); 279 } 280 281 int 282 soc_kt2_mpls_base_entry_to_key(int unit, void *entry, uint8 *key) 283 { 284 soc_field_t field_list[2]; 285 286 switch (soc_mem_field32_get(unit, MPLS_ENTRYm, entry, KEY_TYPEf)) { 287 case KT2_MPLS_HASH_KEY_TYPE_MPLS: 288 field_list[0] = MPLS__KEYf; 289 break; 290 case KT2_MPLS_HASH_KEY_TYPE_MIM_NVP: 291 field_list[0] = MIM_NVP__KEYf; 292 break; 293 case KT2_MPLS_HASH_KEY_TYPE_MIM_ISID: 294 case KT2_MPLS_HASH_KEY_TYPE_MIM_ISID_SVP: 295 field_list[0] = MIM_ISID__KEYf; 296 break; 297 default: 298 return 0; 299 } 300 field_list[1] = INVALIDf; 301 return _soc_kt2_hash_generic_entry_to_key(unit, entry, key, MPLS_ENTRYm, 302 field_list); 303 } 304 305 uint32 306 soc_kt2_vlan_xlate_hash(int unit, int hash_sel, int key_nbits, 307 void *base_entry, uint8 *key) 308 { 309 uint32 rv = 0; 310 311 /* 312 * Cache bucket mask and shift amount for upper crc 313 */ 314 if (SOC_CONTROL(unit)->hash_mask_vlan_mac == 0) { 315 uint32 mask; 316 int bits; 317 318 /* 16 Entries per bucket */ 319 mask = soc_mem_index_max(unit, VLAN_MACm) >> 4; 320 bits = 0; 321 rv = 1; 322 while (rv && (mask & rv)) { 323 bits += 1; 324 rv <<= 1; 325 } 326 327 /* For the Variants whose VLAN_XLATE (and VLAN_MAC) memory size are 328 limited by Bond Option, The shift amount should be based on the "Original" 329 memory size 330 */ 331 #ifdef BCM_SABER2_SUPPORT 332 /* Saber2 variants has VLAN_XLATE limited by bond option, 333 use the original 16K = 10 bits 334 */ 335 if (SOC_IS_SABER2(unit)) { 336 bits = 10; 337 } 338 #endif 339 340 341 SOC_CONTROL(unit)->hash_mask_vlan_mac = mask; 342 SOC_CONTROL(unit)->hash_bits_vlan_mac = bits; 343 } 344 345 switch (hash_sel) { 346 case FB_HASH_CRC16_UPPER: 347 rv = soc_crc16b(key, key_nbits); 348 rv >>= 16 - SOC_CONTROL(unit)->hash_bits_vlan_mac; 349 break; 350 351 case FB_HASH_CRC16_LOWER: 352 rv = soc_crc16b(key, key_nbits); 353 break; 354 355 case FB_HASH_LSB: 356 if (key_nbits == 0) { 357 return 0; 358 } 359 switch (soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, 360 KEY_TYPEf)) { 361 362 case KT2_VLXLT_HASH_KEY_TYPE_IVID_OVID: 363 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, OVIDf); 364 break; 365 case KT2_VLXLT_HASH_KEY_TYPE_OTAG: 366 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, OTAGf); 367 break; 368 case KT2_VLXLT_HASH_KEY_TYPE_ITAG: 369 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, ITAGf); 370 break; 371 case KT2_VLXLT_HASH_KEY_TYPE_OVID: 372 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, OVIDf); 373 break; 374 case KT2_VLXLT_HASH_KEY_TYPE_IVID: 375 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, IVIDf); 376 break; 377 case KT2_VLXLT_HASH_KEY_TYPE_PRI_CFI: 378 /* Use only the upper 4 bit of OTAG */ 379 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, OTAGf) >> 380 12; 381 break; 382 case KT2_VLXLT_HASH_KEY_TYPE_VIF: 383 case KT2_VLXLT_HASH_KEY_TYPE_VIF_VLAN: 384 case KT2_VLXLT_HASH_KEY_TYPE_VIF_CVLAN: 385 case KT2_VLXLT_HASH_KEY_TYPE_VIF_OTAG: 386 case KT2_VLXLT_HASH_KEY_TYPE_VIF_ITAG: 387 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, 388 VIF__SRC_VIFf); 389 break; 390 case KT2_VLXLT_HASH_KEY_TYPE_LLTAG_VID: 391 case KT2_VLXLT_HASH_KEY_TYPE_LLVID_IVID: 392 case KT2_VLXLT_HASH_KEY_TYPE_LLVID_OVID: 393 rv = soc_mem_field32_get(unit, VLAN_XLATEm, base_entry, 394 LLTAG__LLVIDf); 395 break; 396 case KT2_VLXLT_HASH_KEY_TYPE_VLAN_MAC: 397 rv = soc_mem_field32_get(unit, VLAN_MACm, base_entry, 398 MAC__MAC_ADDRf); 399 break; 400 case KT2_VLXLT_HASH_KEY_TYPE_HPAE: 401 rv = soc_mem_field32_get(unit, VLAN_MACm, base_entry, 402 MAC_IP_BIND__SIPf); 403 break; 404 default: 405 rv = 0; 406 break; 407 } 408 break; 409 410 case FB_HASH_ZERO: 411 rv = 0; 412 break; 413 414 case FB_HASH_CRC32_UPPER: 415 rv = soc_crc32b(key, key_nbits); 416 rv >>= 32 - SOC_CONTROL(unit)->hash_bits_vlan_mac; 417 break; 418 419 case FB_HASH_CRC32_LOWER: 420 rv = soc_crc32b(key, key_nbits); 421 break; 422 423 default: 424 LOG_ERROR(BSL_LS_SOC_HASH, 425 (BSL_META_U(unit, 426 "soc_kt2_vlan_xlate_hash: invalid hash_sel %d\n"), 427 hash_sel)); 428 rv = 0; 429 break; 430 } 431 432 return rv & SOC_CONTROL(unit)->hash_mask_vlan_mac; 433 } 434 435 uint32 436 soc_kt2_egr_vlan_xlate_hash(int unit, int hash_sel, int key_nbits, 437 void *base_entry, uint8 *key) 438 { 439 uint32 rv = 0; 440 441 /* 442 * Cache bucket mask and shift amount for upper crc 443 */ 444 if (SOC_CONTROL(unit)->hash_mask_egr_vlan_xlate == 0) { 445 uint32 mask; 446 int bits; 447 448 /* 16 Entries per bucket */ 449 mask = soc_mem_index_max(unit, EGR_VLAN_XLATEm) >> 4; 450 bits = 0; 451 rv = 1; 452 while (rv && (mask & rv)) { 453 bits += 1; 454 rv <<= 1; 455 } 456 SOC_CONTROL(unit)->hash_mask_egr_vlan_xlate = mask; 457 SOC_CONTROL(unit)->hash_bits_egr_vlan_xlate = bits; 458 } 459 460 switch (hash_sel) { 461 case FB_HASH_CRC16_UPPER: 462 rv = soc_crc16b(key, key_nbits); 463 rv >>= 16 - SOC_CONTROL(unit)->hash_bits_egr_vlan_xlate; 464 break; 465 466 case FB_HASH_CRC16_LOWER: 467 rv = soc_crc16b(key, key_nbits); 468 break; 469 470 case FB_HASH_LSB: 471 if (key_nbits == 0) { 472 return 0; 473 } 474 switch (soc_mem_field32_get(unit, EGR_VLAN_XLATEm, base_entry, 475 ENTRY_TYPEf)) { 476 case KT2_EVLXLT_HASH_KEY_TYPE_VLAN_XLATE: 477 case KT2_EVLXLT_HASH_KEY_TYPE_VLAN_XLATE_DVP: 478 rv = soc_mem_field32_get(unit, EGR_VLAN_XLATEm, base_entry, 479 OVIDf); 480 break; 481 case KT2_EVLXLT_HASH_KEY_TYPE_ISID_XLATE: 482 case KT2_EVLXLT_HASH_KEY_TYPE_ISID_DVP_XLATE: 483 rv = soc_mem_field32_get(unit, EGR_VLAN_XLATEm, base_entry, 484 MIM_ISID__VFIf) | 485 (soc_mem_field32_get(unit, EGR_VLAN_XLATEm, base_entry, 486 MIM_ISID__DVPf) << 487 soc_mem_field_length(unit, EGR_VLAN_XLATEm, 488 MIM_ISID__VFIf)); 489 break; 490 default: 491 rv = 0; 492 break; 493 } 494 break; 495 496 case FB_HASH_ZERO: 497 rv = 0; 498 break; 499 500 case FB_HASH_CRC32_UPPER: 501 rv = soc_crc32b(key, key_nbits); 502 rv >>= 32 - SOC_CONTROL(unit)->hash_bits_egr_vlan_xlate; 503 break; 504 505 case FB_HASH_CRC32_LOWER: 506 rv = soc_crc32b(key, key_nbits); 507 break; 508 509 default: 510 LOG_ERROR(BSL_LS_SOC_HASH, 511 (BSL_META_U(unit, 512 "soc_kt2_egr_vlan_xlate_hash: invalid hash_sel %d\n"), 513 hash_sel)); 514 rv = 0; 515 break; 516 } 517 518 return rv & SOC_CONTROL(unit)->hash_mask_egr_vlan_xlate; 519 } 520 521 #endif /* BCM_KATANA2_SUPPORT */