+/*
+ * For the case which data is linked with sequence increased index, the
+ * array table will be more efficiect than hash table once need to serarch
+ * one data entry in large numbers of entries. Since the traditional hash
+ * tables has fixed table size, when huge numbers of data saved to the hash
+ * table, it also comes lots of hash conflict.
+ *
+ * But simple array table also has fixed size, allocates all the needed
+ * memory at once will waste lots of memory. For the case don't know the
+ * exactly number of entries will be impossible to allocate the array.
+ *
+ * Then the multiple level table helps to balance the two disadvantages.
+ * Allocate a global high level table with sub table entries at first,
+ * the global table contains the sub table entries, and the sub table will
+ * be allocated only once the corresponding index entry need to be saved.
+ * e.g. for up to 32-bits index, three level table with 10-10-12 splitting,
+ * with sequence increased index, the memory grows with every 4K entries.
+ *
+ * The currently implementation introduces 10-10-12 32-bits splitting
+ * Three-Level table to help the cases which have millions of enties to
+ * save. The index entries can be addressed directly by the index, no
+ * search will be needed.q
+ */
+
+/* L3 table global table define. */
+#define MLX5_L3T_GT_OFFSET 22
+#define MLX5_L3T_GT_SIZE (1 << 10)
+#define MLX5_L3T_GT_MASK (MLX5_L3T_GT_SIZE - 1)
+
+/* L3 table middle table define. */
+#define MLX5_L3T_MT_OFFSET 12
+#define MLX5_L3T_MT_SIZE (1 << 10)
+#define MLX5_L3T_MT_MASK (MLX5_L3T_MT_SIZE - 1)
+
+/* L3 table entry table define. */
+#define MLX5_L3T_ET_OFFSET 0
+#define MLX5_L3T_ET_SIZE (1 << 12)
+#define MLX5_L3T_ET_MASK (MLX5_L3T_ET_SIZE - 1)
+
+/* L3 table type. */
+enum mlx5_l3t_type {
+ MLX5_L3T_TYPE_WORD = 0,
+ MLX5_L3T_TYPE_DWORD,
+ MLX5_L3T_TYPE_QWORD,
+ MLX5_L3T_TYPE_PTR,
+ MLX5_L3T_TYPE_MAX,
+};
+
+struct mlx5_indexed_pool;
+
+/* Generic data struct. */
+union mlx5_l3t_data {
+ uint16_t word;
+ uint32_t dword;
+ uint64_t qword;
+ void *ptr;
+};
+
+/* L3 level table data structure. */
+struct mlx5_l3t_level_tbl {
+ uint64_t ref_cnt; /* Table ref_cnt. */
+ void *tbl[]; /* Table array. */
+};
+
+/* L3 word entry table data structure. */
+struct mlx5_l3t_entry_word {
+ uint32_t idx; /* Table index. */
+ uint64_t ref_cnt; /* Table ref_cnt. */
+ struct {
+ uint16_t data;
+ uint32_t ref_cnt;
+ } entry[MLX5_L3T_ET_SIZE]; /* Entry array */
+} __rte_packed;
+
+/* L3 double word entry table data structure. */
+struct mlx5_l3t_entry_dword {
+ uint32_t idx; /* Table index. */
+ uint64_t ref_cnt; /* Table ref_cnt. */
+ struct {
+ uint32_t data;
+ int32_t ref_cnt;
+ } entry[MLX5_L3T_ET_SIZE]; /* Entry array */
+} __rte_packed;
+
+/* L3 quad word entry table data structure. */
+struct mlx5_l3t_entry_qword {
+ uint32_t idx; /* Table index. */
+ uint64_t ref_cnt; /* Table ref_cnt. */
+ struct {
+ uint64_t data;
+ uint32_t ref_cnt;
+ } entry[MLX5_L3T_ET_SIZE]; /* Entry array */
+} __rte_packed;
+
+/* L3 pointer entry table data structure. */
+struct mlx5_l3t_entry_ptr {
+ uint32_t idx; /* Table index. */
+ uint64_t ref_cnt; /* Table ref_cnt. */
+ struct {
+ void *data;
+ uint32_t ref_cnt;
+ } entry[MLX5_L3T_ET_SIZE]; /* Entry array */
+} __rte_packed;
+
+/* L3 table data structure. */
+struct mlx5_l3t_tbl {
+ enum mlx5_l3t_type type; /* Table type. */
+ struct mlx5_indexed_pool *eip;
+ /* Table index pool handles. */
+ struct mlx5_l3t_level_tbl *tbl; /* Global table index. */
+ rte_spinlock_t sl; /* The table lock. */
+};
+
+/** Type of function that is used to handle the data before freeing. */
+typedef int32_t (*mlx5_l3t_alloc_callback_fn)(void *ctx,
+ union mlx5_l3t_data *data);
+
+/*
+ * The indexed memory entry index is made up of trunk index and offset of
+ * the entry in the trunk. Since the entry index is 32 bits, in case user
+ * prefers to have small trunks, user can change the macro below to a big
+ * number which helps the pool contains more trunks with lots of entries
+ * allocated.
+ */
+#define TRUNK_IDX_BITS 16
+#define TRUNK_MAX_IDX ((1 << TRUNK_IDX_BITS) - 1)
+#define TRUNK_INVALID TRUNK_MAX_IDX
+#define MLX5_IPOOL_DEFAULT_TRUNK_SIZE (1 << (28 - TRUNK_IDX_BITS))
+#ifdef RTE_LIBRTE_MLX5_DEBUG
+#define POOL_DEBUG 1
+#endif
+
+struct mlx5_indexed_pool_config {
+ uint32_t size; /* Pool entry size. */
+ uint32_t trunk_size:22;
+ /*
+ * Trunk entry number. Must be power of 2. It can be increased
+ * if trunk_grow enable. The trunk entry number increases with
+ * left shift grow_shift. Trunks with index are after grow_trunk
+ * will keep the entry number same with the last grow trunk.
+ */
+ uint32_t grow_trunk:4;
+ /*
+ * Trunks with entry number increase in the pool. Set it to 0
+ * to make the pool works as trunk entry fixed pool. It works
+ * only if grow_shift is not 0.
+ */
+ uint32_t grow_shift:4;
+ /*
+ * Trunk entry number increase shift value, stop after grow_trunk.
+ * It works only if grow_trunk is not 0.
+ */
+ uint32_t need_lock:1;
+ /* Lock is needed for multiple thread usage. */
+ uint32_t release_mem_en:1; /* Rlease trunk when it is free. */
+ uint32_t max_idx; /* The maximum index can be allocated. */
+ uint32_t per_core_cache;
+ /*
+ * Cache entry number per core for performance. Should not be
+ * set with release_mem_en.
+ */
+ const char *type; /* Memory allocate type name. */
+ void *(*malloc)(uint32_t flags, size_t size, unsigned int align,
+ int socket);
+ /* User defined memory allocator. */
+ void (*free)(void *addr); /* User defined memory release. */
+};
+
+struct mlx5_indexed_trunk {
+ uint32_t idx; /* Trunk id. */
+ uint32_t prev; /* Previous free trunk in free list. */
+ uint32_t next; /* Next free trunk in free list. */
+ uint32_t free; /* Free entries available */
+ struct rte_bitmap *bmp;
+ uint8_t data[] __rte_cache_aligned; /* Entry data start. */
+};
+
+struct mlx5_indexed_cache {
+ struct mlx5_indexed_trunk **trunks;
+ volatile uint32_t n_trunk_valid; /* Trunks allocated. */
+ uint32_t n_trunk; /* Trunk pointer array size. */
+ uint32_t ref_cnt;
+ uint32_t len;
+ uint32_t idx[];
+};
+
+struct mlx5_ipool_per_lcore {
+ struct mlx5_indexed_cache *lc;
+ uint32_t len; /**< Current cache count. */
+ uint32_t idx[]; /**< Cache objects. */
+};
+
+struct mlx5_indexed_pool {
+ struct mlx5_indexed_pool_config cfg; /* Indexed pool configuration. */
+ rte_spinlock_t rsz_lock; /* Pool lock for multiple thread usage. */
+ rte_spinlock_t lcore_lock;
+ /* Dim of trunk pointer array. */
+ union {
+ struct {
+ uint32_t n_trunk_valid; /* Trunks allocated. */
+ uint32_t n_trunk; /* Trunk pointer array size. */
+ struct mlx5_indexed_trunk **trunks;
+ uint32_t free_list; /* Index to first free trunk. */
+ };
+ struct {
+ struct mlx5_indexed_cache *gc;
+ /* Global cache. */
+ struct mlx5_ipool_per_lcore *cache[RTE_MAX_LCORE + 1];
+ /* Local cache. */
+ struct rte_bitmap *ibmp;
+ void *bmp_mem;
+ /* Allocate objects bitmap. Use during flush. */
+ };
+ };
+#ifdef POOL_DEBUG
+ uint32_t n_entry;
+ uint32_t trunk_new;
+ uint32_t trunk_avail;
+ uint32_t trunk_empty;
+ uint32_t trunk_free;
+#endif
+ uint32_t grow_tbl[]; /* Save the index offset for the grow trunks. */
+};