1 // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
2 /* Copyright (c) 2017-2018 Mellanox Technologies. All rights reserved */
4 #include <linux/kernel.h>
5 #include <linux/slab.h>
6 #include <linux/list.h>
7 #include <linux/errno.h>
8 #include <linux/refcount.h>
11 #include "core_acl_flex_keys.h"
13 /* For the purpose of the driver, define an internal storage scratchpad
14 * that will be used to store key/mask values. For each defined element type
15 * define an internal storage geometry.
17 * When adding new elements, MLXSW_AFK_ELEMENT_STORAGE_SIZE must be increased
20 static const struct mlxsw_afk_element_info mlxsw_afk_element_infos[] = {
21 MLXSW_AFK_ELEMENT_INFO_U32(SRC_SYS_PORT, 0x00, 16, 16),
22 MLXSW_AFK_ELEMENT_INFO_BUF(DMAC_32_47, 0x04, 2),
23 MLXSW_AFK_ELEMENT_INFO_BUF(DMAC_0_31, 0x06, 4),
24 MLXSW_AFK_ELEMENT_INFO_BUF(SMAC_32_47, 0x0A, 2),
25 MLXSW_AFK_ELEMENT_INFO_BUF(SMAC_0_31, 0x0C, 4),
26 MLXSW_AFK_ELEMENT_INFO_U32(ETHERTYPE, 0x00, 0, 16),
27 MLXSW_AFK_ELEMENT_INFO_U32(IP_PROTO, 0x10, 0, 8),
28 MLXSW_AFK_ELEMENT_INFO_U32(VID, 0x10, 8, 12),
29 MLXSW_AFK_ELEMENT_INFO_U32(PCP, 0x10, 20, 3),
30 MLXSW_AFK_ELEMENT_INFO_U32(TCP_FLAGS, 0x10, 23, 9),
31 MLXSW_AFK_ELEMENT_INFO_U32(DST_L4_PORT, 0x14, 0, 16),
32 MLXSW_AFK_ELEMENT_INFO_U32(SRC_L4_PORT, 0x14, 16, 16),
33 MLXSW_AFK_ELEMENT_INFO_U32(IP_TTL_, 0x18, 0, 8),
34 MLXSW_AFK_ELEMENT_INFO_U32(IP_ECN, 0x18, 9, 2),
35 MLXSW_AFK_ELEMENT_INFO_U32(IP_DSCP, 0x18, 11, 6),
36 MLXSW_AFK_ELEMENT_INFO_U32(VIRT_ROUTER, 0x18, 17, 12),
37 MLXSW_AFK_ELEMENT_INFO_BUF(SRC_IP_96_127, 0x20, 4),
38 MLXSW_AFK_ELEMENT_INFO_BUF(SRC_IP_64_95, 0x24, 4),
39 MLXSW_AFK_ELEMENT_INFO_BUF(SRC_IP_32_63, 0x28, 4),
40 MLXSW_AFK_ELEMENT_INFO_BUF(SRC_IP_0_31, 0x2C, 4),
41 MLXSW_AFK_ELEMENT_INFO_BUF(DST_IP_96_127, 0x30, 4),
42 MLXSW_AFK_ELEMENT_INFO_BUF(DST_IP_64_95, 0x34, 4),
43 MLXSW_AFK_ELEMENT_INFO_BUF(DST_IP_32_63, 0x38, 4),
44 MLXSW_AFK_ELEMENT_INFO_BUF(DST_IP_0_31, 0x3C, 4),
45 MLXSW_AFK_ELEMENT_INFO_U32(FDB_MISS, 0x40, 0, 1),
46 MLXSW_AFK_ELEMENT_INFO_U32(L4_PORT_RANGE, 0x40, 1, 16),
47 MLXSW_AFK_ELEMENT_INFO_U32(VIRT_ROUTER_0_3, 0x40, 17, 4),
48 MLXSW_AFK_ELEMENT_INFO_U32(VIRT_ROUTER_4_7, 0x40, 21, 4),
49 MLXSW_AFK_ELEMENT_INFO_U32(VIRT_ROUTER_MSB, 0x40, 25, 4),
53 struct list_head key_info_list;
54 unsigned int max_blocks;
55 const struct mlxsw_afk_ops *ops;
56 const struct mlxsw_afk_block *blocks;
57 unsigned int blocks_count;
60 static bool mlxsw_afk_blocks_check(struct mlxsw_afk *mlxsw_afk)
65 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
66 const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];
68 for (j = 0; j < block->instances_count; j++) {
69 const struct mlxsw_afk_element_info *elinfo;
70 struct mlxsw_afk_element_inst *elinst;
72 elinst = &block->instances[j];
73 elinfo = &mlxsw_afk_element_infos[elinst->element];
74 if (elinst->type != elinfo->type ||
75 (!elinst->avoid_size_check &&
76 elinst->item.size.bits !=
77 elinfo->item.size.bits))
84 struct mlxsw_afk *mlxsw_afk_create(unsigned int max_blocks,
85 const struct mlxsw_afk_ops *ops)
87 struct mlxsw_afk *mlxsw_afk;
89 mlxsw_afk = kzalloc(sizeof(*mlxsw_afk), GFP_KERNEL);
92 INIT_LIST_HEAD(&mlxsw_afk->key_info_list);
93 mlxsw_afk->max_blocks = max_blocks;
95 mlxsw_afk->blocks = ops->blocks;
96 mlxsw_afk->blocks_count = ops->blocks_count;
97 WARN_ON(!mlxsw_afk_blocks_check(mlxsw_afk));
100 EXPORT_SYMBOL(mlxsw_afk_create);
102 void mlxsw_afk_destroy(struct mlxsw_afk *mlxsw_afk)
104 WARN_ON(!list_empty(&mlxsw_afk->key_info_list));
107 EXPORT_SYMBOL(mlxsw_afk_destroy);
109 struct mlxsw_afk_key_info {
110 struct list_head list;
111 refcount_t ref_count;
112 unsigned int blocks_count;
113 int element_to_block[MLXSW_AFK_ELEMENT_MAX]; /* index is element, value
114 * is index inside "blocks"
116 struct mlxsw_afk_element_usage elusage;
117 const struct mlxsw_afk_block *blocks[];
121 mlxsw_afk_key_info_elements_eq(struct mlxsw_afk_key_info *key_info,
122 struct mlxsw_afk_element_usage *elusage)
124 return memcmp(&key_info->elusage, elusage, sizeof(*elusage)) == 0;
127 static struct mlxsw_afk_key_info *
128 mlxsw_afk_key_info_find(struct mlxsw_afk *mlxsw_afk,
129 struct mlxsw_afk_element_usage *elusage)
131 struct mlxsw_afk_key_info *key_info;
133 list_for_each_entry(key_info, &mlxsw_afk->key_info_list, list) {
134 if (mlxsw_afk_key_info_elements_eq(key_info, elusage))
140 struct mlxsw_afk_picker {
141 DECLARE_BITMAP(element, MLXSW_AFK_ELEMENT_MAX);
142 DECLARE_BITMAP(chosen_element, MLXSW_AFK_ELEMENT_MAX);
146 static void mlxsw_afk_picker_count_hits(struct mlxsw_afk *mlxsw_afk,
147 struct mlxsw_afk_picker *picker,
148 enum mlxsw_afk_element element)
153 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
154 const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];
156 for (j = 0; j < block->instances_count; j++) {
157 struct mlxsw_afk_element_inst *elinst;
159 elinst = &block->instances[j];
160 if (elinst->element == element) {
161 __set_bit(element, picker[i].element);
168 static void mlxsw_afk_picker_subtract_hits(struct mlxsw_afk *mlxsw_afk,
169 struct mlxsw_afk_picker *picker,
172 DECLARE_BITMAP(hits_element, MLXSW_AFK_ELEMENT_MAX);
176 memcpy(&hits_element, &picker[block_index].element,
177 sizeof(hits_element));
179 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
180 for_each_set_bit(j, hits_element, MLXSW_AFK_ELEMENT_MAX) {
181 if (__test_and_clear_bit(j, picker[i].element))
187 static int mlxsw_afk_picker_most_hits_get(struct mlxsw_afk *mlxsw_afk,
188 struct mlxsw_afk_picker *picker)
190 int most_index = -EINVAL; /* Should never happen to return this */
194 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
195 if (picker[i].total > most_hits) {
196 most_hits = picker[i].total;
203 static int mlxsw_afk_picker_key_info_add(struct mlxsw_afk *mlxsw_afk,
204 struct mlxsw_afk_picker *picker,
206 struct mlxsw_afk_key_info *key_info)
208 enum mlxsw_afk_element element;
210 if (key_info->blocks_count == mlxsw_afk->max_blocks)
213 for_each_set_bit(element, picker[block_index].chosen_element,
214 MLXSW_AFK_ELEMENT_MAX) {
215 key_info->element_to_block[element] = key_info->blocks_count;
216 mlxsw_afk_element_usage_add(&key_info->elusage, element);
219 key_info->blocks[key_info->blocks_count] =
220 &mlxsw_afk->blocks[block_index];
221 key_info->blocks_count++;
225 static int mlxsw_afk_keys_fill(struct mlxsw_afk *mlxsw_afk,
226 unsigned long *chosen_blocks_bm,
227 struct mlxsw_afk_picker *picker,
228 struct mlxsw_afk_key_info *key_info)
232 /* First fill only key blocks with high_entropy. */
233 for_each_set_bit(i, chosen_blocks_bm, mlxsw_afk->blocks_count) {
234 if (!mlxsw_afk->blocks[i].high_entropy)
237 err = mlxsw_afk_picker_key_info_add(mlxsw_afk, picker, i,
241 __clear_bit(i, chosen_blocks_bm);
244 /* Fill the rest of key blocks. */
245 for_each_set_bit(i, chosen_blocks_bm, mlxsw_afk->blocks_count) {
246 err = mlxsw_afk_picker_key_info_add(mlxsw_afk, picker, i,
255 static int mlxsw_afk_picker(struct mlxsw_afk *mlxsw_afk,
256 struct mlxsw_afk_key_info *key_info,
257 struct mlxsw_afk_element_usage *elusage)
259 DECLARE_BITMAP(elusage_chosen, MLXSW_AFK_ELEMENT_MAX) = {0};
260 struct mlxsw_afk_picker *picker;
261 unsigned long *chosen_blocks_bm;
262 enum mlxsw_afk_element element;
265 picker = kcalloc(mlxsw_afk->blocks_count, sizeof(*picker), GFP_KERNEL);
269 chosen_blocks_bm = bitmap_zalloc(mlxsw_afk->blocks_count, GFP_KERNEL);
270 if (!chosen_blocks_bm) {
272 goto err_bitmap_alloc;
275 /* Since the same elements could be present in multiple blocks,
276 * we must find out optimal block list in order to make the
277 * block count as low as possible.
279 * First, we count hits. We go over all available blocks and count
280 * how many of requested elements are covered by each.
282 * Then in loop, we find block with most hits and add it to
283 * output key_info. Then we have to subtract this block hits so
284 * the next iteration will find most suitable block for
285 * the rest of requested elements.
288 mlxsw_afk_element_usage_for_each(element, elusage)
289 mlxsw_afk_picker_count_hits(mlxsw_afk, picker, element);
294 block_index = mlxsw_afk_picker_most_hits_get(mlxsw_afk, picker);
295 if (block_index < 0) {
300 __set_bit(block_index, chosen_blocks_bm);
302 bitmap_copy(picker[block_index].chosen_element,
303 picker[block_index].element, MLXSW_AFK_ELEMENT_MAX);
305 bitmap_or(elusage_chosen, elusage_chosen,
306 picker[block_index].chosen_element,
307 MLXSW_AFK_ELEMENT_MAX);
309 mlxsw_afk_picker_subtract_hits(mlxsw_afk, picker, block_index);
311 } while (!bitmap_equal(elusage_chosen, elusage->usage,
312 MLXSW_AFK_ELEMENT_MAX));
314 err = mlxsw_afk_keys_fill(mlxsw_afk, chosen_blocks_bm, picker,
317 bitmap_free(chosen_blocks_bm);
323 static struct mlxsw_afk_key_info *
324 mlxsw_afk_key_info_create(struct mlxsw_afk *mlxsw_afk,
325 struct mlxsw_afk_element_usage *elusage)
327 struct mlxsw_afk_key_info *key_info;
330 key_info = kzalloc(struct_size(key_info, blocks, mlxsw_afk->max_blocks),
333 return ERR_PTR(-ENOMEM);
334 err = mlxsw_afk_picker(mlxsw_afk, key_info, elusage);
337 list_add(&key_info->list, &mlxsw_afk->key_info_list);
338 refcount_set(&key_info->ref_count, 1);
346 static void mlxsw_afk_key_info_destroy(struct mlxsw_afk_key_info *key_info)
348 list_del(&key_info->list);
352 struct mlxsw_afk_key_info *
353 mlxsw_afk_key_info_get(struct mlxsw_afk *mlxsw_afk,
354 struct mlxsw_afk_element_usage *elusage)
356 struct mlxsw_afk_key_info *key_info;
358 key_info = mlxsw_afk_key_info_find(mlxsw_afk, elusage);
360 refcount_inc(&key_info->ref_count);
363 return mlxsw_afk_key_info_create(mlxsw_afk, elusage);
365 EXPORT_SYMBOL(mlxsw_afk_key_info_get);
367 void mlxsw_afk_key_info_put(struct mlxsw_afk_key_info *key_info)
369 if (!refcount_dec_and_test(&key_info->ref_count))
371 mlxsw_afk_key_info_destroy(key_info);
373 EXPORT_SYMBOL(mlxsw_afk_key_info_put);
375 bool mlxsw_afk_key_info_subset(struct mlxsw_afk_key_info *key_info,
376 struct mlxsw_afk_element_usage *elusage)
378 return mlxsw_afk_element_usage_subset(elusage, &key_info->elusage);
380 EXPORT_SYMBOL(mlxsw_afk_key_info_subset);
382 static const struct mlxsw_afk_element_inst *
383 mlxsw_afk_block_elinst_get(const struct mlxsw_afk_block *block,
384 enum mlxsw_afk_element element)
388 for (i = 0; i < block->instances_count; i++) {
389 struct mlxsw_afk_element_inst *elinst;
391 elinst = &block->instances[i];
392 if (elinst->element == element)
398 static const struct mlxsw_afk_element_inst *
399 mlxsw_afk_key_info_elinst_get(struct mlxsw_afk_key_info *key_info,
400 enum mlxsw_afk_element element,
403 const struct mlxsw_afk_element_inst *elinst;
404 const struct mlxsw_afk_block *block;
407 if (WARN_ON(!test_bit(element, key_info->elusage.usage)))
409 block_index = key_info->element_to_block[element];
410 block = key_info->blocks[block_index];
412 elinst = mlxsw_afk_block_elinst_get(block, element);
413 if (WARN_ON(!elinst))
416 *p_block_index = block_index;
421 mlxsw_afk_key_info_block_encoding_get(const struct mlxsw_afk_key_info *key_info,
424 return key_info->blocks[block_index]->encoding;
426 EXPORT_SYMBOL(mlxsw_afk_key_info_block_encoding_get);
429 mlxsw_afk_key_info_blocks_count_get(const struct mlxsw_afk_key_info *key_info)
431 return key_info->blocks_count;
433 EXPORT_SYMBOL(mlxsw_afk_key_info_blocks_count_get);
435 void mlxsw_afk_values_add_u32(struct mlxsw_afk_element_values *values,
436 enum mlxsw_afk_element element,
437 u32 key_value, u32 mask_value)
439 const struct mlxsw_afk_element_info *elinfo =
440 &mlxsw_afk_element_infos[element];
441 const struct mlxsw_item *storage_item = &elinfo->item;
445 if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_U32))
447 __mlxsw_item_set32(values->storage.key, storage_item, 0, key_value);
448 __mlxsw_item_set32(values->storage.mask, storage_item, 0, mask_value);
449 mlxsw_afk_element_usage_add(&values->elusage, element);
451 EXPORT_SYMBOL(mlxsw_afk_values_add_u32);
453 void mlxsw_afk_values_add_buf(struct mlxsw_afk_element_values *values,
454 enum mlxsw_afk_element element,
455 const char *key_value, const char *mask_value,
458 const struct mlxsw_afk_element_info *elinfo =
459 &mlxsw_afk_element_infos[element];
460 const struct mlxsw_item *storage_item = &elinfo->item;
462 if (!memchr_inv(mask_value, 0, len)) /* If mask is zero */
464 if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_BUF) ||
465 WARN_ON(elinfo->item.size.bytes != len))
467 __mlxsw_item_memcpy_to(values->storage.key, key_value,
469 __mlxsw_item_memcpy_to(values->storage.mask, mask_value,
471 mlxsw_afk_element_usage_add(&values->elusage, element);
473 EXPORT_SYMBOL(mlxsw_afk_values_add_buf);
475 static void mlxsw_sp_afk_encode_u32(const struct mlxsw_item *storage_item,
476 const struct mlxsw_item *output_item,
477 char *storage, char *output, int diff)
481 value = __mlxsw_item_get32(storage, storage_item, 0);
482 __mlxsw_item_set32(output, output_item, 0, value + diff);
485 static void mlxsw_sp_afk_encode_buf(const struct mlxsw_item *storage_item,
486 const struct mlxsw_item *output_item,
487 char *storage, char *output)
489 char *storage_data = __mlxsw_item_data(storage, storage_item, 0);
490 char *output_data = __mlxsw_item_data(output, output_item, 0);
491 size_t len = output_item->size.bytes;
493 memcpy(output_data, storage_data, len);
497 mlxsw_sp_afk_encode_one(const struct mlxsw_afk_element_inst *elinst,
498 char *output, char *storage, int u32_diff)
500 const struct mlxsw_item *output_item = &elinst->item;
501 const struct mlxsw_afk_element_info *elinfo;
502 const struct mlxsw_item *storage_item;
504 elinfo = &mlxsw_afk_element_infos[elinst->element];
505 storage_item = &elinfo->item;
506 if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_U32)
507 mlxsw_sp_afk_encode_u32(storage_item, output_item,
508 storage, output, u32_diff);
509 else if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_BUF)
510 mlxsw_sp_afk_encode_buf(storage_item, output_item,
514 #define MLXSW_SP_AFK_KEY_BLOCK_MAX_SIZE 16
516 void mlxsw_afk_encode(struct mlxsw_afk *mlxsw_afk,
517 struct mlxsw_afk_key_info *key_info,
518 struct mlxsw_afk_element_values *values,
519 char *key, char *mask)
521 unsigned int blocks_count =
522 mlxsw_afk_key_info_blocks_count_get(key_info);
523 char block_mask[MLXSW_SP_AFK_KEY_BLOCK_MAX_SIZE];
524 char block_key[MLXSW_SP_AFK_KEY_BLOCK_MAX_SIZE];
525 const struct mlxsw_afk_element_inst *elinst;
526 enum mlxsw_afk_element element;
529 for (i = 0; i < blocks_count; i++) {
530 memset(block_key, 0, MLXSW_SP_AFK_KEY_BLOCK_MAX_SIZE);
531 memset(block_mask, 0, MLXSW_SP_AFK_KEY_BLOCK_MAX_SIZE);
533 mlxsw_afk_element_usage_for_each(element, &values->elusage) {
534 elinst = mlxsw_afk_key_info_elinst_get(key_info,
537 if (!elinst || block_index != i)
540 mlxsw_sp_afk_encode_one(elinst, block_key,
542 elinst->u32_key_diff);
543 mlxsw_sp_afk_encode_one(elinst, block_mask,
544 values->storage.mask, 0);
547 mlxsw_afk->ops->encode_block(key, i, block_key);
548 mlxsw_afk->ops->encode_block(mask, i, block_mask);
551 EXPORT_SYMBOL(mlxsw_afk_encode);
553 void mlxsw_afk_clear(struct mlxsw_afk *mlxsw_afk, char *key,
554 int block_start, int block_end)
558 for (i = block_start; i <= block_end; i++)
559 mlxsw_afk->ops->clear_block(key, i);
561 EXPORT_SYMBOL(mlxsw_afk_clear);