2 * drivers/net/ethernet/mellanox/mlxsw/core_acl_flex_keys.c
3 * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
4 * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * 3. Neither the names of the copyright holders nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
18 * Alternatively, this software may be distributed under the terms of the
19 * GNU General Public License ("GPL") version 2 as published by the Free
20 * Software Foundation.
22 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
23 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
24 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
25 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
26 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
27 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
28 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
29 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
30 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
31 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
35 #include <linux/kernel.h>
36 #include <linux/slab.h>
37 #include <linux/list.h>
38 #include <linux/errno.h>
41 #include "core_acl_flex_keys.h"
44 struct list_head key_info_list;
45 unsigned int max_blocks;
46 const struct mlxsw_afk_block *blocks;
47 unsigned int blocks_count;
50 static bool mlxsw_afk_blocks_check(struct mlxsw_afk *mlxsw_afk)
55 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
56 const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];
58 for (j = 0; j < block->instances_count; j++) {
59 struct mlxsw_afk_element_inst *elinst;
61 elinst = &block->instances[j];
62 if (elinst->type != elinst->info->type ||
63 elinst->item.size.bits !=
64 elinst->info->item.size.bits)
71 struct mlxsw_afk *mlxsw_afk_create(unsigned int max_blocks,
72 const struct mlxsw_afk_block *blocks,
73 unsigned int blocks_count)
75 struct mlxsw_afk *mlxsw_afk;
77 mlxsw_afk = kzalloc(sizeof(*mlxsw_afk), GFP_KERNEL);
80 INIT_LIST_HEAD(&mlxsw_afk->key_info_list);
81 mlxsw_afk->max_blocks = max_blocks;
82 mlxsw_afk->blocks = blocks;
83 mlxsw_afk->blocks_count = blocks_count;
84 WARN_ON(!mlxsw_afk_blocks_check(mlxsw_afk));
87 EXPORT_SYMBOL(mlxsw_afk_create);
89 void mlxsw_afk_destroy(struct mlxsw_afk *mlxsw_afk)
91 WARN_ON(!list_empty(&mlxsw_afk->key_info_list));
94 EXPORT_SYMBOL(mlxsw_afk_destroy);
96 struct mlxsw_afk_key_info {
97 struct list_head list;
98 unsigned int ref_count;
99 unsigned int blocks_count;
100 int element_to_block[MLXSW_AFK_ELEMENT_MAX]; /* index is element, value
101 * is index inside "blocks"
103 struct mlxsw_afk_element_usage elusage;
104 const struct mlxsw_afk_block *blocks[0];
108 mlxsw_afk_key_info_elements_eq(struct mlxsw_afk_key_info *key_info,
109 struct mlxsw_afk_element_usage *elusage)
111 return memcmp(&key_info->elusage, elusage, sizeof(*elusage)) == 0;
114 static struct mlxsw_afk_key_info *
115 mlxsw_afk_key_info_find(struct mlxsw_afk *mlxsw_afk,
116 struct mlxsw_afk_element_usage *elusage)
118 struct mlxsw_afk_key_info *key_info;
120 list_for_each_entry(key_info, &mlxsw_afk->key_info_list, list) {
121 if (mlxsw_afk_key_info_elements_eq(key_info, elusage))
127 struct mlxsw_afk_picker {
129 DECLARE_BITMAP(element, MLXSW_AFK_ELEMENT_MAX);
134 static void mlxsw_afk_picker_count_hits(struct mlxsw_afk *mlxsw_afk,
135 struct mlxsw_afk_picker *picker,
136 enum mlxsw_afk_element element)
141 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
142 const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];
144 for (j = 0; j < block->instances_count; j++) {
145 struct mlxsw_afk_element_inst *elinst;
147 elinst = &block->instances[j];
148 if (elinst->info->element == element) {
149 __set_bit(element, picker->hits[i].element);
150 picker->hits[i].total++;
156 static void mlxsw_afk_picker_subtract_hits(struct mlxsw_afk *mlxsw_afk,
157 struct mlxsw_afk_picker *picker,
160 DECLARE_BITMAP(hits_element, MLXSW_AFK_ELEMENT_MAX);
164 memcpy(&hits_element, &picker->hits[block_index].element,
165 sizeof(hits_element));
167 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
168 for_each_set_bit(j, hits_element, MLXSW_AFK_ELEMENT_MAX) {
169 if (__test_and_clear_bit(j, picker->hits[i].element))
170 picker->hits[i].total--;
175 static int mlxsw_afk_picker_most_hits_get(struct mlxsw_afk *mlxsw_afk,
176 struct mlxsw_afk_picker *picker)
178 int most_index = -EINVAL; /* Should never happen to return this */
182 for (i = 0; i < mlxsw_afk->blocks_count; i++) {
183 if (picker->hits[i].total > most_hits) {
184 most_hits = picker->hits[i].total;
191 static int mlxsw_afk_picker_key_info_add(struct mlxsw_afk *mlxsw_afk,
192 struct mlxsw_afk_picker *picker,
194 struct mlxsw_afk_key_info *key_info)
196 enum mlxsw_afk_element element;
198 if (key_info->blocks_count == mlxsw_afk->max_blocks)
201 for_each_set_bit(element, picker->hits[block_index].element,
202 MLXSW_AFK_ELEMENT_MAX) {
203 key_info->element_to_block[element] = key_info->blocks_count;
204 mlxsw_afk_element_usage_add(&key_info->elusage, element);
207 key_info->blocks[key_info->blocks_count] =
208 &mlxsw_afk->blocks[block_index];
209 key_info->blocks_count++;
213 static int mlxsw_afk_picker(struct mlxsw_afk *mlxsw_afk,
214 struct mlxsw_afk_key_info *key_info,
215 struct mlxsw_afk_element_usage *elusage)
217 struct mlxsw_afk_picker *picker;
218 enum mlxsw_afk_element element;
222 alloc_size = sizeof(picker->hits[0]) * mlxsw_afk->blocks_count;
223 picker = kzalloc(alloc_size, GFP_KERNEL);
227 /* Since the same elements could be present in multiple blocks,
228 * we must find out optimal block list in order to make the
229 * block count as low as possible.
231 * First, we count hits. We go over all available blocks and count
232 * how many of requested elements are covered by each.
234 * Then in loop, we find block with most hits and add it to
235 * output key_info. Then we have to subtract this block hits so
236 * the next iteration will find most suitable block for
237 * the rest of requested elements.
240 mlxsw_afk_element_usage_for_each(element, elusage)
241 mlxsw_afk_picker_count_hits(mlxsw_afk, picker, element);
246 block_index = mlxsw_afk_picker_most_hits_get(mlxsw_afk, picker);
247 if (block_index < 0) {
251 err = mlxsw_afk_picker_key_info_add(mlxsw_afk, picker,
252 block_index, key_info);
255 mlxsw_afk_picker_subtract_hits(mlxsw_afk, picker, block_index);
256 } while (!mlxsw_afk_key_info_elements_eq(key_info, elusage));
264 static struct mlxsw_afk_key_info *
265 mlxsw_afk_key_info_create(struct mlxsw_afk *mlxsw_afk,
266 struct mlxsw_afk_element_usage *elusage)
268 struct mlxsw_afk_key_info *key_info;
272 alloc_size = sizeof(*key_info) +
273 sizeof(key_info->blocks[0]) * mlxsw_afk->max_blocks;
274 key_info = kzalloc(alloc_size, GFP_KERNEL);
276 return ERR_PTR(-ENOMEM);
277 err = mlxsw_afk_picker(mlxsw_afk, key_info, elusage);
280 list_add(&key_info->list, &mlxsw_afk->key_info_list);
281 key_info->ref_count = 1;
289 static void mlxsw_afk_key_info_destroy(struct mlxsw_afk_key_info *key_info)
291 list_del(&key_info->list);
295 struct mlxsw_afk_key_info *
296 mlxsw_afk_key_info_get(struct mlxsw_afk *mlxsw_afk,
297 struct mlxsw_afk_element_usage *elusage)
299 struct mlxsw_afk_key_info *key_info;
301 key_info = mlxsw_afk_key_info_find(mlxsw_afk, elusage);
303 key_info->ref_count++;
306 return mlxsw_afk_key_info_create(mlxsw_afk, elusage);
308 EXPORT_SYMBOL(mlxsw_afk_key_info_get);
310 void mlxsw_afk_key_info_put(struct mlxsw_afk_key_info *key_info)
312 if (--key_info->ref_count)
314 mlxsw_afk_key_info_destroy(key_info);
316 EXPORT_SYMBOL(mlxsw_afk_key_info_put);
318 bool mlxsw_afk_key_info_subset(struct mlxsw_afk_key_info *key_info,
319 struct mlxsw_afk_element_usage *elusage)
321 return mlxsw_afk_element_usage_subset(elusage, &key_info->elusage);
323 EXPORT_SYMBOL(mlxsw_afk_key_info_subset);
325 static const struct mlxsw_afk_element_inst *
326 mlxsw_afk_block_elinst_get(const struct mlxsw_afk_block *block,
327 enum mlxsw_afk_element element)
331 for (i = 0; i < block->instances_count; i++) {
332 struct mlxsw_afk_element_inst *elinst;
334 elinst = &block->instances[i];
335 if (elinst->info->element == element)
341 static const struct mlxsw_afk_element_inst *
342 mlxsw_afk_key_info_elinst_get(struct mlxsw_afk_key_info *key_info,
343 enum mlxsw_afk_element element,
346 const struct mlxsw_afk_element_inst *elinst;
347 const struct mlxsw_afk_block *block;
350 if (WARN_ON(!test_bit(element, key_info->elusage.usage)))
352 block_index = key_info->element_to_block[element];
353 block = key_info->blocks[block_index];
355 elinst = mlxsw_afk_block_elinst_get(block, element);
356 if (WARN_ON(!elinst))
359 *p_block_index = block_index;
364 mlxsw_afk_key_info_block_encoding_get(const struct mlxsw_afk_key_info *key_info,
367 return key_info->blocks[block_index]->encoding;
369 EXPORT_SYMBOL(mlxsw_afk_key_info_block_encoding_get);
372 mlxsw_afk_key_info_blocks_count_get(const struct mlxsw_afk_key_info *key_info)
374 return key_info->blocks_count;
376 EXPORT_SYMBOL(mlxsw_afk_key_info_blocks_count_get);
378 void mlxsw_afk_values_add_u32(struct mlxsw_afk_element_values *values,
379 enum mlxsw_afk_element element,
380 u32 key_value, u32 mask_value)
382 const struct mlxsw_afk_element_info *elinfo =
383 &mlxsw_afk_element_infos[element];
384 const struct mlxsw_item *storage_item = &elinfo->item;
388 if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_U32))
390 __mlxsw_item_set32(values->storage.key, storage_item, 0, key_value);
391 __mlxsw_item_set32(values->storage.mask, storage_item, 0, mask_value);
392 mlxsw_afk_element_usage_add(&values->elusage, element);
394 EXPORT_SYMBOL(mlxsw_afk_values_add_u32);
396 void mlxsw_afk_values_add_buf(struct mlxsw_afk_element_values *values,
397 enum mlxsw_afk_element element,
398 const char *key_value, const char *mask_value,
401 const struct mlxsw_afk_element_info *elinfo =
402 &mlxsw_afk_element_infos[element];
403 const struct mlxsw_item *storage_item = &elinfo->item;
405 if (!memchr_inv(mask_value, 0, len)) /* If mask is zero */
407 if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_BUF) ||
408 WARN_ON(elinfo->item.size.bytes != len))
410 __mlxsw_item_memcpy_to(values->storage.key, key_value,
412 __mlxsw_item_memcpy_to(values->storage.mask, mask_value,
414 mlxsw_afk_element_usage_add(&values->elusage, element);
416 EXPORT_SYMBOL(mlxsw_afk_values_add_buf);
418 static void mlxsw_afk_encode_u32(const struct mlxsw_item *storage_item,
419 const struct mlxsw_item *output_item,
420 char *storage, char *output_indexed)
424 value = __mlxsw_item_get32(storage, storage_item, 0);
425 __mlxsw_item_set32(output_indexed, output_item, 0, value);
428 static void mlxsw_afk_encode_buf(const struct mlxsw_item *storage_item,
429 const struct mlxsw_item *output_item,
430 char *storage, char *output_indexed)
432 char *storage_data = __mlxsw_item_data(storage, storage_item, 0);
433 char *output_data = __mlxsw_item_data(output_indexed, output_item, 0);
434 size_t len = output_item->size.bytes;
436 memcpy(output_data, storage_data, len);
439 #define MLXSW_AFK_KEY_BLOCK_SIZE 16
441 static void mlxsw_afk_encode_one(const struct mlxsw_afk_element_inst *elinst,
442 int block_index, char *storage, char *output)
444 char *output_indexed = output + block_index * MLXSW_AFK_KEY_BLOCK_SIZE;
445 const struct mlxsw_item *storage_item = &elinst->info->item;
446 const struct mlxsw_item *output_item = &elinst->item;
448 if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_U32)
449 mlxsw_afk_encode_u32(storage_item, output_item,
450 storage, output_indexed);
451 else if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_BUF)
452 mlxsw_afk_encode_buf(storage_item, output_item,
453 storage, output_indexed);
456 void mlxsw_afk_encode(struct mlxsw_afk_key_info *key_info,
457 struct mlxsw_afk_element_values *values,
458 char *key, char *mask)
460 const struct mlxsw_afk_element_inst *elinst;
461 enum mlxsw_afk_element element;
464 mlxsw_afk_element_usage_for_each(element, &values->elusage) {
465 elinst = mlxsw_afk_key_info_elinst_get(key_info, element,
469 mlxsw_afk_encode_one(elinst, block_index,
470 values->storage.key, key);
471 mlxsw_afk_encode_one(elinst, block_index,
472 values->storage.mask, mask);
475 EXPORT_SYMBOL(mlxsw_afk_encode);