drivers/net/bnxt/tf_core/tf_shadow_tcam.c

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  * Copyright(c) 2019-2020 Broadcom
   3  * All rights reserved.
   4  */
   5
   6 #include "tf_common.h"
   7 #include "tf_util.h"
   8 #include "tfp.h"
   9 #include "tf_shadow_tcam.h"
  10
  11 /**
  12  * The implementation includes 3 tables per tcam table type.
  13  * - hash table
  14  *   - sized so that a minimum of 4 slots per shadow entry are available to
  15  *   minimize the likelihood of collisions.
  16  * - shadow key table
  17  *   - sized to the number of entries requested and is directly indexed
  18  *   - the index is zero based and is the tcam index - the base address
  19  *   - the key and mask are stored in the key table.
  20  *   - The stored key is the AND of the key/mask in order to eliminate the need
  21  *   to compare both the key and mask.
  22  * - shadow result table
  23  *   - the result table is stored separately since it only needs to be accessed
  24  *   when the key matches.
  25  *   - the result has a back pointer to the hash table via the hb handle.  The
  26  *   hb handle is a 32 bit represention of the hash with a valid bit, bucket
  27  *   element index, and the hash index.  It is necessary to store the hb handle
  28  *   with the result since subsequent removes only provide the tcam index.
  29  *
  30  * - Max entries is limited in the current implementation since bit 15 is the
  31  *   valid bit in the hash table.
  32  * - A 16bit hash is calculated and masked based on the number of entries
  33  * - 64b wide bucket is used and broken into 4x16bit elements.
  34  *   This decision is based on quicker bucket scanning to determine if any
  35  *   elements are in use.
  36  * - bit 15 of each bucket element is the valid, this is done to prevent having
  37  *   to read the larger key/result data for determining VALID.  It also aids
  38  *   in the more efficient scanning of the bucket for slot usage.
  39  */
  40
  41 /*
  42  * The maximum number of shadow entries supported.  The value also doubles as
  43  * the maximum number of hash buckets.  There are only 15 bits of data per
  44  * bucket to point to the shadow tables.
  45  */
  46 #define TF_SHADOW_TCAM_ENTRIES_MAX (1 << 15)
  47
  48 /* The number of elements(BE) per hash bucket (HB) */
  49 #define TF_SHADOW_TCAM_HB_NUM_ELEM (4)
  50 #define TF_SHADOW_TCAM_BE_VALID (1 << 15)
  51 #define TF_SHADOW_TCAM_BE_IS_VALID(be) (((be) & TF_SHADOW_TCAM_BE_VALID) != 0)
  52
  53 /**
  54  * The hash bucket handle is 32b
  55  * - bit 31, the Valid bit
  56  * - bit 29-30, the element
  57  * - bits 0-15, the hash idx (is masked based on the allocated size)
  58  */
  59 #define TF_SHADOW_TCAM_HB_HANDLE_IS_VALID(hndl) (((hndl) & (1 << 31)) != 0)
  60 #define TF_SHADOW_TCAM_HB_HANDLE_CREATE(idx, be) ((1 << 31) | \
  61                                                   ((be) << 29) | (idx))
  62
  63 #define TF_SHADOW_TCAM_HB_HANDLE_BE_GET(hdl) (((hdl) >> 29) & \
  64                                               (TF_SHADOW_TCAM_HB_NUM_ELEM - 1))
  65
  66 #define TF_SHADOW_TCAM_HB_HANDLE_HASH_GET(ctxt, hdl)((hdl) & \
  67                                                      (ctxt)->hash_ctxt.hid_mask)
  68
  69 /**
  70  * The idx provided by the caller is within a region, so currently the base is
  71  * either added or subtracted from the idx to ensure it can be used as a
  72  * compressed index
  73  */
  74
  75 /* Convert the tcam index to a shadow index */
  76 #define TF_SHADOW_TCAM_IDX_TO_SHIDX(ctxt, idx) ((idx) - \
  77                                                 (ctxt)->shadow_ctxt.base_addr)
  78
  79 /* Convert the shadow index to a tcam index */
  80 #define TF_SHADOW_TCAM_SHIDX_TO_IDX(ctxt, idx) ((idx) + \
  81                                                 (ctxt)->shadow_ctxt.base_addr)
  82
  83 /* Simple helper masks for clearing en element from the bucket */
  84 #define TF_SHADOW_TCAM_BE0_MASK_CLEAR(hb) ((hb) & 0xffffffffffff0000ull)
  85 #define TF_SHADOW_TCAM_BE1_MASK_CLEAR(hb) ((hb) & 0xffffffff0000ffffull)
  86 #define TF_SHADOW_TCAM_BE2_MASK_CLEAR(hb) ((hb) & 0xffff0000ffffffffull)
  87 #define TF_SHADOW_TCAM_BE3_MASK_CLEAR(hb) ((hb) & 0x0000ffffffffffffull)
  88
  89 /**
  90  * This should be coming from external, but for now it is assumed that no key
  91  * is greater than 1K bits and no result is bigger than 128 bits.  This makes
  92  * allocation of the hash table easier without having to allocate on the fly.
  93  */
  94 #define TF_SHADOW_TCAM_MAX_KEY_SZ 128
  95 #define TF_SHADOW_TCAM_MAX_RESULT_SZ 16
  96
  97 /*
  98  * Local only defines for the internal data.
  99  */
 100
 101 /**
 102  * tf_shadow_tcam_shadow_key_entry is the key/mask entry of the key table.
 103  * The key stored in the table is the masked version of the key.  This is done
 104  * to eliminate the need of comparing both the key and mask.
 105  */
 106 struct tf_shadow_tcam_shadow_key_entry {
 107         uint8_t key[TF_SHADOW_TCAM_MAX_KEY_SZ];
 108         uint8_t mask[TF_SHADOW_TCAM_MAX_KEY_SZ];
 109 };
 110
 111 /**
 112  * tf_shadow_tcam_shadow_result_entry is the result table entry.
 113  * The result table writes are broken into two phases:
 114  * - The search phase, which stores the hb_handle and key size and
 115  * - The set phase, which writes the result, refcnt, and result size
 116  */
 117 struct tf_shadow_tcam_shadow_result_entry {
 118         uint8_t result[TF_SHADOW_TCAM_MAX_RESULT_SZ];
 119         uint16_t result_size;
 120         uint16_t key_size;
 121         uint32_t refcnt;
 122         uint32_t hb_handle;
 123 };
 124
 125 /**
 126  * tf_shadow_tcam_shadow_ctxt holds all information for accessing the key and
 127  * result tables.
 128  */
 129 struct tf_shadow_tcam_shadow_ctxt {
 130         struct tf_shadow_tcam_shadow_key_entry *sh_key_tbl;
 131         struct tf_shadow_tcam_shadow_result_entry *sh_res_tbl;
 132         uint32_t base_addr;
 133         uint16_t num_entries;
 134         uint16_t alloc_idx;
 135 };
 136
 137 /**
 138  * tf_shadow_tcam_hash_ctxt holds all information related to accessing the hash
 139  * table.
 140  */
 141 struct tf_shadow_tcam_hash_ctxt {
 142         uint64_t *hashtbl;
 143         uint16_t hid_mask;
 144         uint16_t hash_entries;
 145 };
 146
 147 /**
 148  * tf_shadow_tcam_ctxt holds the hash and shadow tables for the current shadow
 149  * tcam db.  This structure is per tcam table type as each tcam table has it's
 150  * own shadow and hash table.
 151  */
 152 struct tf_shadow_tcam_ctxt {
 153         struct tf_shadow_tcam_shadow_ctxt shadow_ctxt;
 154         struct tf_shadow_tcam_hash_ctxt hash_ctxt;
 155 };
 156
 157 /**
 158  * tf_shadow_tcam_db is the allocated db structure returned as an opaque
 159  * void * pointer to the caller during create db.  It holds the pointers for
 160  * each tcam associated with the db.
 161  */
 162 struct tf_shadow_tcam_db {
 163         /* Each context holds the shadow and hash table information */
 164         struct tf_shadow_tcam_ctxt *ctxt[TF_TCAM_TBL_TYPE_MAX];
 165 };
 166
 167 /* CRC polynomial 0xedb88320 */
 168 static const uint32_t tf_shadow_tcam_crc32tbl[] = {
 169         0x00000000, 0x77073096, 0xee0e612c, 0x990951ba,
 170         0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3,
 171         0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988,
 172         0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91,
 173         0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de,
 174         0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7,
 175         0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec,
 176         0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5,
 177         0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172,
 178         0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b,
 179         0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940,
 180         0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59,
 181         0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116,
 182         0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f,
 183         0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924,
 184         0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d,
 185         0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a,
 186         0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433,
 187         0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818,
 188         0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01,
 189         0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e,
 190         0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457,
 191         0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c,
 192         0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65,
 193         0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2,
 194         0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb,
 195         0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0,
 196         0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9,
 197         0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086,
 198         0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f,
 199         0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4,
 200         0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad,
 201         0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a,
 202         0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683,
 203         0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8,
 204         0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1,
 205         0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe,
 206         0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7,
 207         0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc,
 208         0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5,
 209         0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252,
 210         0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b,
 211         0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60,
 212         0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79,
 213         0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236,
 214         0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f,
 215         0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04,
 216         0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d,
 217         0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a,
 218         0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713,
 219         0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38,
 220         0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21,
 221         0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e,
 222         0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777,
 223         0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c,
 224         0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45,
 225         0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2,
 226         0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db,
 227         0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0,
 228         0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9,
 229         0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6,
 230         0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf,
 231         0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94,
 232         0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d
 233 };
 234
 235 /**
 236  * Returns the number of entries in the contexts shadow table.
 237  */
 238 static inline uint16_t
 239 tf_shadow_tcam_sh_num_entries_get(struct tf_shadow_tcam_ctxt *ctxt)
 240 {
 241         return ctxt->shadow_ctxt.num_entries;
 242 }
 243
 244 /**
 245  * Compare the give key with the key in the shadow table.
 246  *
 247  * Returns 0 if the keys match
 248  */
 249 static int
 250 tf_shadow_tcam_key_cmp(struct tf_shadow_tcam_ctxt *ctxt,
 251                        uint8_t *key,
 252                        uint8_t *mask,
 253                        uint16_t sh_idx,
 254                        uint16_t size)
 255 {
 256         if (size != ctxt->shadow_ctxt.sh_res_tbl[sh_idx].key_size ||
 257             sh_idx >= tf_shadow_tcam_sh_num_entries_get(ctxt) || !key || !mask)
 258                 return -1;
 259
 260         return memcmp(key, ctxt->shadow_ctxt.sh_key_tbl[sh_idx].key, size);
 261 }
 262
 263 /**
 264  * Copies the shadow result to the result.
 265  *
 266  * Returns 0 on failure
 267  */
 268 static void *
 269 tf_shadow_tcam_res_cpy(struct tf_shadow_tcam_ctxt *ctxt,
 270                        uint8_t *result,
 271                        uint16_t sh_idx,
 272                        uint16_t size)
 273 {
 274         if (sh_idx >= tf_shadow_tcam_sh_num_entries_get(ctxt) || !result)
 275                 return 0;
 276
 277         if (ctxt->shadow_ctxt.sh_res_tbl[sh_idx].result_size != size)
 278                 return 0;
 279
 280         return memcpy(result,
 281                       ctxt->shadow_ctxt.sh_res_tbl[sh_idx].result,
 282                       size);
 283 }
 284
 285 /**
 286  * Using a software based CRC function for now, but will look into using hw
 287  * assisted in the future.
 288  */
 289 static uint32_t
 290 tf_shadow_tcam_crc32_calc(uint8_t *key, uint32_t len)
 291 {
 292         uint32_t crc = ~0U;
 293
 294         while (len--)
 295                 crc = tf_shadow_tcam_crc32tbl[(crc ^ key[len]) & 0xff] ^
 296                         (crc >> 8);
 297
 298         return ~crc;
 299 }
 300
 301 /**
 302  * Free the memory associated with the context.
 303  */
 304 static void
 305 tf_shadow_tcam_ctxt_delete(struct tf_shadow_tcam_ctxt *ctxt)
 306 {
 307         if (!ctxt)
 308                 return;
 309
 310         tfp_free(ctxt->hash_ctxt.hashtbl);
 311         tfp_free(ctxt->shadow_ctxt.sh_key_tbl);
 312         tfp_free(ctxt->shadow_ctxt.sh_res_tbl);
 313 }
 314
 315 /**
 316  * The TF Shadow TCAM context is per TCAM and holds all information relating to
 317  * managing the shadow and search capability.  This routine allocated data that
 318  * needs to be deallocated by the tf_shadow_tcam_ctxt_delete prior when deleting
 319  * the shadow db.
 320  */
 321 static int
 322 tf_shadow_tcam_ctxt_create(struct tf_shadow_tcam_ctxt *ctxt,
 323                            uint16_t num_entries,
 324                            uint16_t base_addr)
 325 {
 326         struct tfp_calloc_parms cparms;
 327         uint16_t hash_size = 1;
 328         uint16_t hash_mask;
 329         int rc;
 330
 331         /* Hash table is a power of two that holds the number of entries */
 332         if (num_entries > TF_SHADOW_TCAM_ENTRIES_MAX) {
 333                 TFP_DRV_LOG(ERR, "Too many entries for shadow %d > %d\n",
 334                             num_entries,
 335                             TF_SHADOW_TCAM_ENTRIES_MAX);
 336                 return -ENOMEM;
 337         }
 338
 339         while (hash_size < num_entries)
 340                 hash_size = hash_size << 1;
 341
 342         hash_mask = hash_size - 1;
 343
 344         /* Allocate the hash table */
 345         cparms.nitems = hash_size;
 346         cparms.size = sizeof(uint64_t);
 347         cparms.alignment = 0;
 348         rc = tfp_calloc(&cparms);
 349         if (rc)
 350                 goto error;
 351         ctxt->hash_ctxt.hashtbl = cparms.mem_va;
 352         ctxt->hash_ctxt.hid_mask = hash_mask;
 353         ctxt->hash_ctxt.hash_entries = hash_size;
 354
 355         /* allocate the shadow tables */
 356         /* allocate the shadow key table */
 357         cparms.nitems = num_entries;
 358         cparms.size = sizeof(struct tf_shadow_tcam_shadow_key_entry);
 359         cparms.alignment = 0;
 360         rc = tfp_calloc(&cparms);
 361         if (rc)
 362                 goto error;
 363         ctxt->shadow_ctxt.sh_key_tbl = cparms.mem_va;
 364
 365         /* allocate the shadow result table */
 366         cparms.nitems = num_entries;
 367         cparms.size = sizeof(struct tf_shadow_tcam_shadow_result_entry);
 368         cparms.alignment = 0;
 369         rc = tfp_calloc(&cparms);
 370         if (rc)
 371                 goto error;
 372         ctxt->shadow_ctxt.sh_res_tbl = cparms.mem_va;
 373
 374         ctxt->shadow_ctxt.num_entries = num_entries;
 375         ctxt->shadow_ctxt.base_addr = base_addr;
 376
 377         return 0;
 378 error:
 379         tf_shadow_tcam_ctxt_delete(ctxt);
 380
 381         return -ENOMEM;
 382 }
 383
 384 /**
 385  * Get a shadow TCAM context given the db and the TCAM type
 386  */
 387 static struct tf_shadow_tcam_ctxt *
 388 tf_shadow_tcam_ctxt_get(struct tf_shadow_tcam_db *shadow_db,
 389                         enum tf_tcam_tbl_type type)
 390 {
 391         if (type >= TF_TCAM_TBL_TYPE_MAX ||
 392             !shadow_db ||
 393             !shadow_db->ctxt[type])
 394                 return NULL;
 395
 396         return shadow_db->ctxt[type];
 397 }
 398
 399 /**
 400  * Sets the hash entry into the table given the TCAM context, hash bucket
 401  * handle, and shadow index.
 402  */
 403 static inline int
 404 tf_shadow_tcam_set_hash_entry(struct tf_shadow_tcam_ctxt *ctxt,
 405                               uint32_t hb_handle,
 406                               uint16_t sh_idx)
 407 {
 408         uint16_t hid = TF_SHADOW_TCAM_HB_HANDLE_HASH_GET(ctxt, hb_handle);
 409         uint16_t be = TF_SHADOW_TCAM_HB_HANDLE_BE_GET(hb_handle);
 410         uint64_t entry = sh_idx | TF_SHADOW_TCAM_BE_VALID;
 411
 412         if (hid >= ctxt->hash_ctxt.hash_entries)
 413                 return -EINVAL;
 414
 415         ctxt->hash_ctxt.hashtbl[hid] |= entry << (be * 16);
 416         return 0;
 417 }
 418
 419 /**
 420  * Clears the hash entry given the TCAM context and hash bucket handle.
 421  */
 422 static inline void
 423 tf_shadow_tcam_clear_hash_entry(struct tf_shadow_tcam_ctxt *ctxt,
 424                                 uint32_t hb_handle)
 425 {
 426         uint16_t hid, be;
 427         uint64_t *bucket;
 428
 429         if (!TF_SHADOW_TCAM_HB_HANDLE_IS_VALID(hb_handle))
 430                 return;
 431
 432         hid = TF_SHADOW_TCAM_HB_HANDLE_HASH_GET(ctxt, hb_handle);
 433         be = TF_SHADOW_TCAM_HB_HANDLE_BE_GET(hb_handle);
 434         bucket = &ctxt->hash_ctxt.hashtbl[hid];
 435
 436         switch (be) {
 437         case 0:
 438                 *bucket = TF_SHADOW_TCAM_BE0_MASK_CLEAR(*bucket);
 439                 break;
 440         case 1:
 441                 *bucket = TF_SHADOW_TCAM_BE1_MASK_CLEAR(*bucket);
 442                 break;
 443         case 2:
 444                 *bucket = TF_SHADOW_TCAM_BE2_MASK_CLEAR(*bucket);
 445                 break;
 446         case 3:
 447                 *bucket = TF_SHADOW_TCAM_BE2_MASK_CLEAR(*bucket);
 448                 break;
 449         }
 450 }
 451
 452 /**
 453  * Clears the shadow key and result entries given the TCAM context and
 454  * shadow index.
 455  */
 456 static void
 457 tf_shadow_tcam_clear_sh_entry(struct tf_shadow_tcam_ctxt *ctxt,
 458                               uint16_t sh_idx)
 459 {
 460         struct tf_shadow_tcam_shadow_key_entry *sk_entry;
 461         struct tf_shadow_tcam_shadow_result_entry *sr_entry;
 462
 463         if (sh_idx >= tf_shadow_tcam_sh_num_entries_get(ctxt))
 464                 return;
 465
 466         sk_entry = &ctxt->shadow_ctxt.sh_key_tbl[sh_idx];
 467         sr_entry = &ctxt->shadow_ctxt.sh_res_tbl[sh_idx];
 468
 469         /*
 470          * memset key/result to zero for now, possibly leave the data alone
 471          * in the future and rely on the valid bit in the hash table.
 472          */
 473         memset(sk_entry, 0, sizeof(struct tf_shadow_tcam_shadow_key_entry));
 474         memset(sr_entry, 0, sizeof(struct tf_shadow_tcam_shadow_result_entry));
 475 }
 476
 477 /**
 478  * Binds the allocated tcam index with the hash and shadow tables.
 479  * The entry will be incomplete until the set has happened with the result
 480  * data.
 481  */
 482 int
 483 tf_shadow_tcam_bind_index(struct tf_shadow_tcam_bind_index_parms *parms)
 484 {
 485         int rc;
 486         int i;
 487         uint16_t idx, klen;
 488         struct tf_shadow_tcam_ctxt *ctxt;
 489         struct tf_shadow_tcam_db *shadow_db;
 490         struct tf_shadow_tcam_shadow_key_entry *sk_entry;
 491         struct tf_shadow_tcam_shadow_result_entry *sr_entry;
 492         uint8_t tkey[TF_SHADOW_TCAM_MAX_KEY_SZ];
 493
 494         if (!parms || !TF_SHADOW_TCAM_HB_HANDLE_IS_VALID(parms->hb_handle) ||
 495             !parms->key || !parms->mask) {
 496                 TFP_DRV_LOG(ERR, "Invalid parms\n");
 497                 return -EINVAL;
 498         }
 499
 500         shadow_db = (struct tf_shadow_tcam_db *)parms->shadow_db;
 501         ctxt = tf_shadow_tcam_ctxt_get(shadow_db, parms->type);
 502         if (!ctxt) {
 503                 TFP_DRV_LOG(DEBUG, "%s no ctxt for table\n",
 504                             tf_tcam_tbl_2_str(parms->type));
 505                 return -EINVAL;
 506         }
 507
 508         memset(tkey, 0, sizeof(tkey));
 509         idx = TF_SHADOW_TCAM_IDX_TO_SHIDX(ctxt, parms->idx);
 510         klen = parms->key_size;
 511         if (idx >= tf_shadow_tcam_sh_num_entries_get(ctxt) ||
 512             klen > TF_SHADOW_TCAM_MAX_KEY_SZ) {
 513                 TFP_DRV_LOG(ERR, "%s:%s Invalid len (%d) > %d || oob idx %d\n",
 514                             tf_dir_2_str(parms->dir),
 515                             tf_tcam_tbl_2_str(parms->type),
 516                             klen,
 517                             TF_SHADOW_TCAM_MAX_KEY_SZ, idx);
 518
 519                 return -EINVAL;
 520         }
 521
 522         rc = tf_shadow_tcam_set_hash_entry(ctxt, parms->hb_handle, idx);
 523         if (rc)
 524                 return -EINVAL;
 525
 526         sk_entry = &ctxt->shadow_ctxt.sh_key_tbl[idx];
 527         sr_entry = &ctxt->shadow_ctxt.sh_res_tbl[idx];
 528
 529         /*
 530          * Write the masked key to the table for more efficient comparisons
 531          * later.
 532          */
 533         for (i = 0; i < klen; i++)
 534                 tkey[i] = parms->key[i] & parms->mask[i];
 535
 536         memcpy(sk_entry->key, tkey, klen);
 537         memcpy(sk_entry->mask, parms->mask, klen);
 538
 539         /* Write the result table */
 540         sr_entry->key_size = parms->key_size;
 541         sr_entry->hb_handle = parms->hb_handle;
 542         sr_entry->refcnt = 1;
 543
 544         return 0;
 545 }
 546
 547 /**
 548  * Deletes hash/shadow information if no more references.
 549  *
 550  * Returns 0 - The caller should delete the tcam entry in hardware.
 551  * Returns non-zero - The number of references to the entry
 552  */
 553 int
 554 tf_shadow_tcam_remove(struct tf_shadow_tcam_remove_parms *parms)
 555 {
 556         uint16_t idx;
 557         uint32_t hb_handle;
 558         struct tf_shadow_tcam_ctxt *ctxt;
 559         struct tf_shadow_tcam_db *shadow_db;
 560         struct tf_tcam_free_parms *fparms;
 561         struct tf_shadow_tcam_shadow_result_entry *sr_entry;
 562
 563         if (!parms || !parms->fparms) {
 564                 TFP_DRV_LOG(ERR, "Invalid parms\n");
 565                 return -EINVAL;
 566         }
 567
 568         fparms = parms->fparms;
 569
 570         /*
 571          * Initialize the reference count to zero.  It will only be changed if
 572          * non-zero.
 573          */
 574         fparms->ref_cnt = 0;
 575
 576         shadow_db = (struct tf_shadow_tcam_db *)parms->shadow_db;
 577         ctxt = tf_shadow_tcam_ctxt_get(shadow_db, fparms->type);
 578         if (!ctxt) {
 579                 TFP_DRV_LOG(DEBUG, "%s no ctxt for table\n",
 580                             tf_tcam_tbl_2_str(fparms->type));
 581                 return 0;
 582         }
 583
 584         idx = TF_SHADOW_TCAM_IDX_TO_SHIDX(ctxt, fparms->idx);
 585         if (idx >= tf_shadow_tcam_sh_num_entries_get(ctxt)) {
 586                 TFP_DRV_LOG(DEBUG, "%s %d >= %d\n",
 587                             tf_tcam_tbl_2_str(fparms->type),
 588                             fparms->idx,
 589                             tf_shadow_tcam_sh_num_entries_get(ctxt));
 590                 return 0;
 591         }
 592
 593         sr_entry = &ctxt->shadow_ctxt.sh_res_tbl[idx];
 594         if (sr_entry->refcnt <= 1) {
 595                 hb_handle = sr_entry->hb_handle;
 596                 tf_shadow_tcam_clear_hash_entry(ctxt, hb_handle);
 597                 tf_shadow_tcam_clear_sh_entry(ctxt, idx);
 598         } else {
 599                 sr_entry->refcnt--;
 600                 fparms->ref_cnt = sr_entry->refcnt;
 601         }
 602
 603         return 0;
 604 }
 605
 606 int
 607 tf_shadow_tcam_search(struct tf_shadow_tcam_search_parms *parms)
 608 {
 609         uint16_t len;
 610         uint8_t rcopy;
 611         uint64_t bucket;
 612         uint32_t i, hid32;
 613         struct tf_shadow_tcam_ctxt *ctxt;
 614         struct tf_shadow_tcam_db *shadow_db;
 615         uint16_t hid16, hb_idx, hid_mask, shtbl_idx, shtbl_key, be_valid;
 616         struct tf_tcam_alloc_search_parms *sparms;
 617         uint8_t tkey[TF_SHADOW_TCAM_MAX_KEY_SZ];
 618         uint32_t be_avail = TF_SHADOW_TCAM_HB_NUM_ELEM;
 619
 620         if (!parms || !parms->sparms) {
 621                 TFP_DRV_LOG(ERR, "tcam search with invalid parms\n");
 622                 return -EINVAL;
 623         }
 624
 625         memset(tkey, 0, sizeof(tkey));
 626         sparms = parms->sparms;
 627
 628         /* Initialize return values to invalid */
 629         sparms->hit = 0;
 630         sparms->search_status = REJECT;
 631         parms->hb_handle = 0;
 632         sparms->ref_cnt = 0;
 633         /* see if caller wanted the result */
 634         rcopy = sparms->result && sparms->result_size;
 635
 636         shadow_db = (struct tf_shadow_tcam_db *)parms->shadow_db;
 637         ctxt = tf_shadow_tcam_ctxt_get(shadow_db, sparms->type);
 638         if (!ctxt) {
 639                 TFP_DRV_LOG(ERR, "%s Unable to get tcam mgr context\n",
 640                             tf_tcam_tbl_2_str(sparms->type));
 641                 return -EINVAL;
 642         }
 643
 644         hid_mask = ctxt->hash_ctxt.hid_mask;
 645
 646         len = sparms->key_size;
 647
 648         if (len > TF_SHADOW_TCAM_MAX_KEY_SZ ||
 649             !sparms->key || !sparms->mask || !len) {
 650                 TFP_DRV_LOG(ERR, "%s:%s Invalid parms %d : %p : %p\n",
 651                             tf_dir_2_str(sparms->dir),
 652                             tf_tcam_tbl_2_str(sparms->type),
 653                             len,
 654                             sparms->key,
 655                             sparms->mask);
 656                 return -EINVAL;
 657         }
 658
 659         /* Combine the key and mask */
 660         for (i = 0; i < len; i++)
 661                 tkey[i] = sparms->key[i] & sparms->mask[i];
 662
 663         /*
 664          * Calculate the crc32
 665          * Fold it to create a 16b value
 666          * Reduce it to fit the table
 667          */
 668         hid32 = tf_shadow_tcam_crc32_calc(tkey, len);
 669         hid16 = (uint16_t)(((hid32 >> 16) & 0xffff) ^ (hid32 & 0xffff));
 670         hb_idx = hid16 & hid_mask;
 671
 672         bucket = ctxt->hash_ctxt.hashtbl[hb_idx];
 673
 674         if (!bucket) {
 675                 /* empty bucket means a miss and available entry */
 676                 sparms->search_status = MISS;
 677                 parms->hb_handle = TF_SHADOW_TCAM_HB_HANDLE_CREATE(hb_idx, 0);
 678                 sparms->idx = 0;
 679                 return 0;
 680         }
 681
 682         /* Set the avail to max so we can detect when there is an avail entry */
 683         be_avail = TF_SHADOW_TCAM_HB_NUM_ELEM;
 684         for (i = 0; i < TF_SHADOW_TCAM_HB_NUM_ELEM; i++) {
 685                 shtbl_idx = (uint16_t)((bucket >> (i * 16)) & 0xffff);
 686                 be_valid = TF_SHADOW_TCAM_BE_IS_VALID(shtbl_idx);
 687                 if (!be_valid) {
 688                         /* The element is avail, keep going */
 689                         be_avail = i;
 690                         continue;
 691                 }
 692                 /* There is a valid entry, compare it */
 693                 shtbl_key = shtbl_idx & ~TF_SHADOW_TCAM_BE_VALID;
 694                 if (!tf_shadow_tcam_key_cmp(ctxt,
 695                                             sparms->key,
 696                                             sparms->mask,
 697                                             shtbl_key,
 698                                             sparms->key_size)) {
 699                         /*
 700                          * It matches, increment the ref count if the caller
 701                          * requested allocation and return the info
 702                          */
 703                         if (sparms->alloc)
 704                                 ctxt->shadow_ctxt.sh_res_tbl[shtbl_key].refcnt =
 705                         ctxt->shadow_ctxt.sh_res_tbl[shtbl_key].refcnt + 1;
 706
 707                         sparms->hit = 1;
 708                         sparms->search_status = HIT;
 709                         parms->hb_handle =
 710                                 TF_SHADOW_TCAM_HB_HANDLE_CREATE(hb_idx, i);
 711                         sparms->idx = TF_SHADOW_TCAM_SHIDX_TO_IDX(ctxt,
 712                                                                   shtbl_key);
 713                         sparms->ref_cnt =
 714                                 ctxt->shadow_ctxt.sh_res_tbl[shtbl_key].refcnt;
 715
 716                         /* copy the result, if caller wanted it. */
 717                         if (rcopy &&
 718                             !tf_shadow_tcam_res_cpy(ctxt,
 719                                                     sparms->result,
 720                                                     shtbl_key,
 721                                                     sparms->result_size)) {
 722                                 /*
 723                                  * Should never get here, possible memory
 724                                  * corruption or something unexpected.
 725                                  */
 726                                 TFP_DRV_LOG(ERR, "Error copying result\n");
 727                                 return -EINVAL;
 728                         }
 729
 730                         return 0;
 731                 }
 732         }
 733
 734         /* No hits, return avail entry if exists */
 735         if (be_avail < TF_SHADOW_TCAM_HB_NUM_ELEM) {
 736                 parms->hb_handle =
 737                         TF_SHADOW_TCAM_HB_HANDLE_CREATE(hb_idx, be_avail);
 738                 sparms->search_status = MISS;
 739                 sparms->hit = 0;
 740                 sparms->idx = 0;
 741         } else {
 742                 sparms->search_status = REJECT;
 743         }
 744
 745         return 0;
 746 }
 747
 748 int
 749 tf_shadow_tcam_insert(struct tf_shadow_tcam_insert_parms *parms)
 750 {
 751         uint16_t idx;
 752         struct tf_shadow_tcam_ctxt *ctxt;
 753         struct tf_tcam_set_parms *sparms;
 754         struct tf_shadow_tcam_db *shadow_db;
 755         struct tf_shadow_tcam_shadow_result_entry *sr_entry;
 756
 757         if (!parms || !parms->sparms) {
 758                 TFP_DRV_LOG(ERR, "Null parms\n");
 759                 return -EINVAL;
 760         }
 761
 762         sparms = parms->sparms;
 763         if (!sparms->result || !sparms->result_size) {
 764                 TFP_DRV_LOG(ERR, "%s:%s No result to set.\n",
 765                             tf_dir_2_str(sparms->dir),
 766                             tf_tcam_tbl_2_str(sparms->type));
 767                 return -EINVAL;
 768         }
 769
 770         shadow_db = (struct tf_shadow_tcam_db *)parms->shadow_db;
 771         ctxt = tf_shadow_tcam_ctxt_get(shadow_db, sparms->type);
 772         if (!ctxt) {
 773                 /* We aren't tracking this table, so return success */
 774                 TFP_DRV_LOG(DEBUG, "%s Unable to get tcam mgr context\n",
 775                             tf_tcam_tbl_2_str(sparms->type));
 776                 return 0;
 777         }
 778
 779         idx = TF_SHADOW_TCAM_IDX_TO_SHIDX(ctxt, sparms->idx);
 780         if (idx >= tf_shadow_tcam_sh_num_entries_get(ctxt)) {
 781                 TFP_DRV_LOG(ERR, "%s:%s Invalid idx(0x%x)\n",
 782                             tf_dir_2_str(sparms->dir),
 783                             tf_tcam_tbl_2_str(sparms->type),
 784                             sparms->idx);
 785                 return -EINVAL;
 786         }
 787
 788         /* Write the result table, the key/hash has been written already */
 789         sr_entry = &ctxt->shadow_ctxt.sh_res_tbl[idx];
 790
 791         /*
 792          * If the handle is not valid, the bind was never called.  We aren't
 793          * tracking this entry.
 794          */
 795         if (!TF_SHADOW_TCAM_HB_HANDLE_IS_VALID(sr_entry->hb_handle))
 796                 return 0;
 797
 798         if (sparms->result_size > TF_SHADOW_TCAM_MAX_RESULT_SZ) {
 799                 TFP_DRV_LOG(ERR, "%s:%s Result length %d > %d\n",
 800                             tf_dir_2_str(sparms->dir),
 801                             tf_tcam_tbl_2_str(sparms->type),
 802                             sparms->result_size,
 803                             TF_SHADOW_TCAM_MAX_RESULT_SZ);
 804                 return -EINVAL;
 805         }
 806
 807         memcpy(sr_entry->result, sparms->result, sparms->result_size);
 808         sr_entry->result_size = sparms->result_size;
 809
 810         return 0;
 811 }
 812
 813 int
 814 tf_shadow_tcam_free_db(struct tf_shadow_tcam_free_db_parms *parms)
 815 {
 816         struct tf_shadow_tcam_db *shadow_db;
 817         int i;
 818
 819         TF_CHECK_PARMS1(parms);
 820
 821         shadow_db = (struct tf_shadow_tcam_db *)parms->shadow_db;
 822         if (!shadow_db) {
 823                 TFP_DRV_LOG(DEBUG, "Shadow db is NULL cannot be freed\n");
 824                 return -EINVAL;
 825         }
 826
 827         for (i = 0; i < TF_TCAM_TBL_TYPE_MAX; i++) {
 828                 if (shadow_db->ctxt[i]) {
 829                         tf_shadow_tcam_ctxt_delete(shadow_db->ctxt[i]);
 830                         tfp_free(shadow_db->ctxt[i]);
 831                 }
 832         }
 833
 834         tfp_free(shadow_db);
 835
 836         return 0;
 837 }
 838
 839 /**
 840  * Allocate the TCAM resources for search and allocate
 841  *
 842  */
 843 int tf_shadow_tcam_create_db(struct tf_shadow_tcam_create_db_parms *parms)
 844 {
 845         int rc;
 846         int i;
 847         uint16_t base;
 848         struct tfp_calloc_parms cparms;
 849         struct tf_shadow_tcam_db *shadow_db = NULL;
 850
 851         TF_CHECK_PARMS1(parms);
 852
 853         /* Build the shadow DB per the request */
 854         cparms.nitems = 1;
 855         cparms.size = sizeof(struct tf_shadow_tcam_db);
 856         cparms.alignment = 0;
 857         rc = tfp_calloc(&cparms);
 858         if (rc)
 859                 return rc;
 860         shadow_db = (void *)cparms.mem_va;
 861
 862         for (i = 0; i < TF_TCAM_TBL_TYPE_MAX; i++) {
 863                 /* If the element didn't request an allocation no need
 864                  * to create a pool nor verify if we got a reservation.
 865                  */
 866                 if (!parms->cfg->alloc_cnt[i]) {
 867                         shadow_db->ctxt[i] = NULL;
 868                         continue;
 869                 }
 870
 871                 cparms.nitems = 1;
 872                 cparms.size = sizeof(struct tf_shadow_tcam_ctxt);
 873                 cparms.alignment = 0;
 874                 rc = tfp_calloc(&cparms);
 875                 if (rc)
 876                         goto error;
 877
 878                 shadow_db->ctxt[i] = cparms.mem_va;
 879                 base = parms->cfg->base_addr[i];
 880                 rc = tf_shadow_tcam_ctxt_create(shadow_db->ctxt[i],
 881                                                 parms->cfg->alloc_cnt[i],
 882                                                 base);
 883                 if (rc)
 884                         goto error;
 885         }
 886
 887         *parms->shadow_db = (void *)shadow_db;
 888
 889         TFP_DRV_LOG(INFO,
 890                     "TF SHADOW TCAM - initialized\n");
 891
 892         return 0;
 893 error:
 894         for (i = 0; i < TF_TCAM_TBL_TYPE_MAX; i++) {
 895                 if (shadow_db->ctxt[i]) {
 896                         tf_shadow_tcam_ctxt_delete(shadow_db->ctxt[i]);
 897                         tfp_free(shadow_db->ctxt[i]);
 898                 }
 899         }
 900
 901         tfp_free(shadow_db);
 902
 903         return -ENOMEM;
 904 }