1 /* 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> 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions are met: 8 * 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. 17 * 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. 21 * 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. 33 */ 34 35 #include <linux/kernel.h> 36 #include <linux/slab.h> 37 #include <linux/list.h> 38 #include <linux/errno.h> 39 40 #include "item.h" 41 #include "core_acl_flex_keys.h" 42 43 struct mlxsw_afk { 44 struct list_head key_info_list; 45 unsigned int max_blocks; 46 const struct mlxsw_afk_block *blocks; 47 unsigned int blocks_count; 48 }; 49 50 static bool mlxsw_afk_blocks_check(struct mlxsw_afk *mlxsw_afk) 51 { 52 int i; 53 int j; 54 55 for (i = 0; i < mlxsw_afk->blocks_count; i++) { 56 const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i]; 57 58 for (j = 0; j < block->instances_count; j++) { 59 struct mlxsw_afk_element_inst *elinst; 60 61 elinst = &block->instances[j]; 62 if (elinst->type != elinst->info->type || 63 elinst->item.size.bits != 64 elinst->info->item.size.bits) 65 return false; 66 } 67 } 68 return true; 69 } 70 71 struct mlxsw_afk *mlxsw_afk_create(unsigned int max_blocks, 72 const struct mlxsw_afk_block *blocks, 73 unsigned int blocks_count) 74 { 75 struct mlxsw_afk *mlxsw_afk; 76 77 mlxsw_afk = kzalloc(sizeof(*mlxsw_afk), GFP_KERNEL); 78 if (!mlxsw_afk) 79 return NULL; 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)); 85 return mlxsw_afk; 86 } 87 EXPORT_SYMBOL(mlxsw_afk_create); 88 89 void mlxsw_afk_destroy(struct mlxsw_afk *mlxsw_afk) 90 { 91 WARN_ON(!list_empty(&mlxsw_afk->key_info_list)); 92 kfree(mlxsw_afk); 93 } 94 EXPORT_SYMBOL(mlxsw_afk_destroy); 95 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" 102 */ 103 struct mlxsw_afk_element_usage elusage; 104 const struct mlxsw_afk_block *blocks[0]; 105 }; 106 107 static bool 108 mlxsw_afk_key_info_elements_eq(struct mlxsw_afk_key_info *key_info, 109 struct mlxsw_afk_element_usage *elusage) 110 { 111 return memcmp(&key_info->elusage, elusage, sizeof(*elusage)) == 0; 112 } 113 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) 117 { 118 struct mlxsw_afk_key_info *key_info; 119 120 list_for_each_entry(key_info, &mlxsw_afk->key_info_list, list) { 121 if (mlxsw_afk_key_info_elements_eq(key_info, elusage)) 122 return key_info; 123 } 124 return NULL; 125 } 126 127 struct mlxsw_afk_picker { 128 struct { 129 DECLARE_BITMAP(element, MLXSW_AFK_ELEMENT_MAX); 130 unsigned int total; 131 } hits[0]; 132 }; 133 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) 137 { 138 int i; 139 int j; 140 141 for (i = 0; i < mlxsw_afk->blocks_count; i++) { 142 const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i]; 143 144 for (j = 0; j < block->instances_count; j++) { 145 struct mlxsw_afk_element_inst *elinst; 146 147 elinst = &block->instances[j]; 148 if (elinst->info->element == element) { 149 __set_bit(element, picker->hits[i].element); 150 picker->hits[i].total++; 151 } 152 } 153 } 154 } 155 156 static void mlxsw_afk_picker_subtract_hits(struct mlxsw_afk *mlxsw_afk, 157 struct mlxsw_afk_picker *picker, 158 int block_index) 159 { 160 DECLARE_BITMAP(hits_element, MLXSW_AFK_ELEMENT_MAX); 161 int i; 162 int j; 163 164 memcpy(&hits_element, &picker->hits[block_index].element, 165 sizeof(hits_element)); 166 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--; 171 } 172 } 173 } 174 175 static int mlxsw_afk_picker_most_hits_get(struct mlxsw_afk *mlxsw_afk, 176 struct mlxsw_afk_picker *picker) 177 { 178 int most_index = -EINVAL; /* Should never happen to return this */ 179 int most_hits = 0; 180 int i; 181 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; 185 most_index = i; 186 } 187 } 188 return most_index; 189 } 190 191 static int mlxsw_afk_picker_key_info_add(struct mlxsw_afk *mlxsw_afk, 192 struct mlxsw_afk_picker *picker, 193 int block_index, 194 struct mlxsw_afk_key_info *key_info) 195 { 196 enum mlxsw_afk_element element; 197 198 if (key_info->blocks_count == mlxsw_afk->max_blocks) 199 return -EINVAL; 200 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); 205 } 206 207 key_info->blocks[key_info->blocks_count] = 208 &mlxsw_afk->blocks[block_index]; 209 key_info->blocks_count++; 210 return 0; 211 } 212 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) 216 { 217 struct mlxsw_afk_picker *picker; 218 enum mlxsw_afk_element element; 219 size_t alloc_size; 220 int err; 221 222 alloc_size = sizeof(picker->hits[0]) * mlxsw_afk->blocks_count; 223 picker = kzalloc(alloc_size, GFP_KERNEL); 224 if (!picker) 225 return -ENOMEM; 226 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. 230 * 231 * First, we count hits. We go over all available blocks and count 232 * how many of requested elements are covered by each. 233 * 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. 238 */ 239 240 mlxsw_afk_element_usage_for_each(element, elusage) 241 mlxsw_afk_picker_count_hits(mlxsw_afk, picker, element); 242 243 do { 244 int block_index; 245 246 block_index = mlxsw_afk_picker_most_hits_get(mlxsw_afk, picker); 247 if (block_index < 0) { 248 err = block_index; 249 goto out; 250 } 251 err = mlxsw_afk_picker_key_info_add(mlxsw_afk, picker, 252 block_index, key_info); 253 if (err) 254 goto out; 255 mlxsw_afk_picker_subtract_hits(mlxsw_afk, picker, block_index); 256 } while (!mlxsw_afk_key_info_elements_eq(key_info, elusage)); 257 258 err = 0; 259 out: 260 kfree(picker); 261 return err; 262 } 263 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) 267 { 268 struct mlxsw_afk_key_info *key_info; 269 size_t alloc_size; 270 int err; 271 272 alloc_size = sizeof(*key_info) + 273 sizeof(key_info->blocks[0]) * mlxsw_afk->max_blocks; 274 key_info = kzalloc(alloc_size, GFP_KERNEL); 275 if (!key_info) 276 return ERR_PTR(-ENOMEM); 277 err = mlxsw_afk_picker(mlxsw_afk, key_info, elusage); 278 if (err) 279 goto err_picker; 280 list_add(&key_info->list, &mlxsw_afk->key_info_list); 281 key_info->ref_count = 1; 282 return key_info; 283 284 err_picker: 285 kfree(key_info); 286 return ERR_PTR(err); 287 } 288 289 static void mlxsw_afk_key_info_destroy(struct mlxsw_afk_key_info *key_info) 290 { 291 list_del(&key_info->list); 292 kfree(key_info); 293 } 294 295 struct mlxsw_afk_key_info * 296 mlxsw_afk_key_info_get(struct mlxsw_afk *mlxsw_afk, 297 struct mlxsw_afk_element_usage *elusage) 298 { 299 struct mlxsw_afk_key_info *key_info; 300 301 key_info = mlxsw_afk_key_info_find(mlxsw_afk, elusage); 302 if (key_info) { 303 key_info->ref_count++; 304 return key_info; 305 } 306 return mlxsw_afk_key_info_create(mlxsw_afk, elusage); 307 } 308 EXPORT_SYMBOL(mlxsw_afk_key_info_get); 309 310 void mlxsw_afk_key_info_put(struct mlxsw_afk_key_info *key_info) 311 { 312 if (--key_info->ref_count) 313 return; 314 mlxsw_afk_key_info_destroy(key_info); 315 } 316 EXPORT_SYMBOL(mlxsw_afk_key_info_put); 317 318 bool mlxsw_afk_key_info_subset(struct mlxsw_afk_key_info *key_info, 319 struct mlxsw_afk_element_usage *elusage) 320 { 321 return mlxsw_afk_element_usage_subset(elusage, &key_info->elusage); 322 } 323 EXPORT_SYMBOL(mlxsw_afk_key_info_subset); 324 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) 328 { 329 int i; 330 331 for (i = 0; i < block->instances_count; i++) { 332 struct mlxsw_afk_element_inst *elinst; 333 334 elinst = &block->instances[i]; 335 if (elinst->info->element == element) 336 return elinst; 337 } 338 return NULL; 339 } 340 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, 344 int *p_block_index) 345 { 346 const struct mlxsw_afk_element_inst *elinst; 347 const struct mlxsw_afk_block *block; 348 int block_index; 349 350 if (WARN_ON(!test_bit(element, key_info->elusage.usage))) 351 return NULL; 352 block_index = key_info->element_to_block[element]; 353 block = key_info->blocks[block_index]; 354 355 elinst = mlxsw_afk_block_elinst_get(block, element); 356 if (WARN_ON(!elinst)) 357 return NULL; 358 359 *p_block_index = block_index; 360 return elinst; 361 } 362 363 u16 364 mlxsw_afk_key_info_block_encoding_get(const struct mlxsw_afk_key_info *key_info, 365 int block_index) 366 { 367 return key_info->blocks[block_index]->encoding; 368 } 369 EXPORT_SYMBOL(mlxsw_afk_key_info_block_encoding_get); 370 371 unsigned int 372 mlxsw_afk_key_info_blocks_count_get(const struct mlxsw_afk_key_info *key_info) 373 { 374 return key_info->blocks_count; 375 } 376 EXPORT_SYMBOL(mlxsw_afk_key_info_blocks_count_get); 377 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) 381 { 382 const struct mlxsw_afk_element_info *elinfo = 383 &mlxsw_afk_element_infos[element]; 384 const struct mlxsw_item *storage_item = &elinfo->item; 385 386 if (!mask_value) 387 return; 388 if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_U32)) 389 return; 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); 393 } 394 EXPORT_SYMBOL(mlxsw_afk_values_add_u32); 395 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, 399 unsigned int len) 400 { 401 const struct mlxsw_afk_element_info *elinfo = 402 &mlxsw_afk_element_infos[element]; 403 const struct mlxsw_item *storage_item = &elinfo->item; 404 405 if (!memchr_inv(mask_value, 0, len)) /* If mask is zero */ 406 return; 407 if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_BUF) || 408 WARN_ON(elinfo->item.size.bytes != len)) 409 return; 410 __mlxsw_item_memcpy_to(values->storage.key, key_value, 411 storage_item, 0); 412 __mlxsw_item_memcpy_to(values->storage.mask, mask_value, 413 storage_item, 0); 414 mlxsw_afk_element_usage_add(&values->elusage, element); 415 } 416 EXPORT_SYMBOL(mlxsw_afk_values_add_buf); 417 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) 421 { 422 u32 value; 423 424 value = __mlxsw_item_get32(storage, storage_item, 0); 425 __mlxsw_item_set32(output_indexed, output_item, 0, value); 426 } 427 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) 431 { 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; 435 436 memcpy(output_data, storage_data, len); 437 } 438 439 #define MLXSW_AFK_KEY_BLOCK_SIZE 16 440 441 static void mlxsw_afk_encode_one(const struct mlxsw_afk_element_inst *elinst, 442 int block_index, char *storage, char *output) 443 { 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; 447 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); 454 } 455 456 void mlxsw_afk_encode(struct mlxsw_afk_key_info *key_info, 457 struct mlxsw_afk_element_values *values, 458 char *key, char *mask) 459 { 460 const struct mlxsw_afk_element_inst *elinst; 461 enum mlxsw_afk_element element; 462 int block_index; 463 464 mlxsw_afk_element_usage_for_each(element, &values->elusage) { 465 elinst = mlxsw_afk_key_info_elinst_get(key_info, element, 466 &block_index); 467 if (!elinst) 468 continue; 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); 473 } 474 } 475 EXPORT_SYMBOL(mlxsw_afk_encode); 476