drivers/net/ethernet/mellanox/mlxsw/core_acl_flex_keys.c - arm/linux - Git at Google

 /*
  * drivers/net/ethernet/mellanox/mlxsw/core_acl_flex_keys.c
  * Copyright (c) 2017 Mellanox Technologies. All rights reserved.
  * Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are met:
  *
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  * 3. Neither the names of the copyright holders nor the names of its
  *    contributors may be used to endorse or promote products derived from
  *    this software without specific prior written permission.
  *
  * Alternatively, this software may be distributed under the terms of the
  * GNU General Public License ("GPL") version 2 as published by the Free
  * Software Foundation.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  */

 #include <linux/kernel.h>
 #include <linux/slab.h>
 #include <linux/list.h>
 #include <linux/errno.h>

 #include "item.h"
 #include "core_acl_flex_keys.h"

 struct mlxsw_afk {
 	struct list_head key_info_list;
 	unsigned int max_blocks;
 	const struct mlxsw_afk_block *blocks;
 	unsigned int blocks_count;
 };

 static bool mlxsw_afk_blocks_check(struct mlxsw_afk *mlxsw_afk)
 {
 	int i;
 	int j;

 	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
 		const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];

 		for (j = 0; j < block->instances_count; j++) {
 			struct mlxsw_afk_element_inst *elinst;

 			elinst = &block->instances[j];
 			if (elinst->type != elinst->info->type ||
 			    elinst->item.size.bits !=
 			    elinst->info->item.size.bits)
 				return false;
 		}
 	}
 	return true;
 }

 struct mlxsw_afk *mlxsw_afk_create(unsigned int max_blocks,
 				   const struct mlxsw_afk_block *blocks,
 				   unsigned int blocks_count)
 {
 	struct mlxsw_afk *mlxsw_afk;

 	mlxsw_afk = kzalloc(sizeof(*mlxsw_afk), GFP_KERNEL);
 	if (!mlxsw_afk)
 		return NULL;
 	INIT_LIST_HEAD(&mlxsw_afk->key_info_list);
 	mlxsw_afk->max_blocks = max_blocks;
 	mlxsw_afk->blocks = blocks;
 	mlxsw_afk->blocks_count = blocks_count;
 	WARN_ON(!mlxsw_afk_blocks_check(mlxsw_afk));
 	return mlxsw_afk;
 }
 EXPORT_SYMBOL(mlxsw_afk_create);

 void mlxsw_afk_destroy(struct mlxsw_afk *mlxsw_afk)
 {
 	WARN_ON(!list_empty(&mlxsw_afk->key_info_list));
 	kfree(mlxsw_afk);
 }
 EXPORT_SYMBOL(mlxsw_afk_destroy);

 struct mlxsw_afk_key_info {
 	struct list_head list;
 	unsigned int ref_count;
 	unsigned int blocks_count;
 	int element_to_block[MLXSW_AFK_ELEMENT_MAX]; /* index is element, value
 						      * is index inside "blocks"
 						      */
 	struct mlxsw_afk_element_usage elusage;
 	const struct mlxsw_afk_block *blocks[0];
 };

 static bool
 mlxsw_afk_key_info_elements_eq(struct mlxsw_afk_key_info *key_info,
 			       struct mlxsw_afk_element_usage *elusage)
 {
 	return memcmp(&key_info->elusage, elusage, sizeof(*elusage)) == 0;
 }

 static struct mlxsw_afk_key_info *
 mlxsw_afk_key_info_find(struct mlxsw_afk *mlxsw_afk,
 			struct mlxsw_afk_element_usage *elusage)
 {
 	struct mlxsw_afk_key_info *key_info;

 	list_for_each_entry(key_info, &mlxsw_afk->key_info_list, list) {
 		if (mlxsw_afk_key_info_elements_eq(key_info, elusage))
 			return key_info;
 	}
 	return NULL;
 }

 struct mlxsw_afk_picker {
 	struct {
 		DECLARE_BITMAP(element, MLXSW_AFK_ELEMENT_MAX);
 		unsigned int total;
 	} hits[0];
 };

 static void mlxsw_afk_picker_count_hits(struct mlxsw_afk *mlxsw_afk,
 					struct mlxsw_afk_picker *picker,
 					enum mlxsw_afk_element element)
 {
 	int i;
 	int j;

 	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
 		const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];

 		for (j = 0; j < block->instances_count; j++) {
 			struct mlxsw_afk_element_inst *elinst;

 			elinst = &block->instances[j];
 			if (elinst->info->element == element) {
 				__set_bit(element, picker->hits[i].element);
 				picker->hits[i].total++;
 			}
 		}
 	}
 }

 static void mlxsw_afk_picker_subtract_hits(struct mlxsw_afk *mlxsw_afk,
 					   struct mlxsw_afk_picker *picker,
 					   int block_index)
 {
 	DECLARE_BITMAP(hits_element, MLXSW_AFK_ELEMENT_MAX);
 	int i;
 	int j;

 	memcpy(&hits_element, &picker->hits[block_index].element,
 	       sizeof(hits_element));

 	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
 		for_each_set_bit(j, hits_element, MLXSW_AFK_ELEMENT_MAX) {
 			if (__test_and_clear_bit(j, picker->hits[i].element))
 				picker->hits[i].total--;
 		}
 	}
 }

 static int mlxsw_afk_picker_most_hits_get(struct mlxsw_afk *mlxsw_afk,
 					  struct mlxsw_afk_picker *picker)
 {
 	int most_index = -EINVAL; /* Should never happen to return this */
 	int most_hits = 0;
 	int i;

 	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
 		if (picker->hits[i].total > most_hits) {
 			most_hits = picker->hits[i].total;
 			most_index = i;
 		}
 	}
 	return most_index;
 }

 static int mlxsw_afk_picker_key_info_add(struct mlxsw_afk *mlxsw_afk,
 					 struct mlxsw_afk_picker *picker,
 					 int block_index,
 					 struct mlxsw_afk_key_info *key_info)
 {
 	enum mlxsw_afk_element element;

 	if (key_info->blocks_count == mlxsw_afk->max_blocks)
 		return -EINVAL;

 	for_each_set_bit(element, picker->hits[block_index].element,
 			 MLXSW_AFK_ELEMENT_MAX) {
 		key_info->element_to_block[element] = key_info->blocks_count;
 		mlxsw_afk_element_usage_add(&key_info->elusage, element);
 	}

 	key_info->blocks[key_info->blocks_count] =
 					&mlxsw_afk->blocks[block_index];
 	key_info->blocks_count++;
 	return 0;
 }

 static int mlxsw_afk_picker(struct mlxsw_afk *mlxsw_afk,
 			    struct mlxsw_afk_key_info *key_info,
 			    struct mlxsw_afk_element_usage *elusage)
 {
 	struct mlxsw_afk_picker *picker;
 	enum mlxsw_afk_element element;
 	size_t alloc_size;
 	int err;

 	alloc_size = sizeof(picker->hits[0]) * mlxsw_afk->blocks_count;
 	picker = kzalloc(alloc_size, GFP_KERNEL);
 	if (!picker)
 		return -ENOMEM;

 	/* Since the same elements could be present in multiple blocks,
 	 * we must find out optimal block list in order to make the
 	 * block count as low as possible.
 	 *
 	 * First, we count hits. We go over all available blocks and count
 	 * how many of requested elements are covered by each.
 	 *
 	 * Then in loop, we find block with most hits and add it to
 	 * output key_info. Then we have to subtract this block hits so
 	 * the next iteration will find most suitable block for
 	 * the rest of requested elements.
 	 */

 	mlxsw_afk_element_usage_for_each(element, elusage)
 		mlxsw_afk_picker_count_hits(mlxsw_afk, picker, element);

 	do {
 		int block_index;

 		block_index = mlxsw_afk_picker_most_hits_get(mlxsw_afk, picker);
 		if (block_index < 0) {
 			err = block_index;
 			goto out;
 		}
 		err = mlxsw_afk_picker_key_info_add(mlxsw_afk, picker,
 						    block_index, key_info);
 		if (err)
 			goto out;
 		mlxsw_afk_picker_subtract_hits(mlxsw_afk, picker, block_index);
 	} while (!mlxsw_afk_key_info_elements_eq(key_info, elusage));

 	err = 0;
 out:
 	kfree(picker);
 	return err;
 }

 static struct mlxsw_afk_key_info *
 mlxsw_afk_key_info_create(struct mlxsw_afk *mlxsw_afk,
 			  struct mlxsw_afk_element_usage *elusage)
 {
 	struct mlxsw_afk_key_info *key_info;
 	size_t alloc_size;
 	int err;

 	alloc_size = sizeof(*key_info) +
 		     sizeof(key_info->blocks[0]) * mlxsw_afk->max_blocks;
 	key_info = kzalloc(alloc_size, GFP_KERNEL);
 	if (!key_info)
 		return ERR_PTR(-ENOMEM);
 	err = mlxsw_afk_picker(mlxsw_afk, key_info, elusage);
 	if (err)
 		goto err_picker;
 	list_add(&key_info->list, &mlxsw_afk->key_info_list);
 	key_info->ref_count = 1;
 	return key_info;

 err_picker:
 	kfree(key_info);
 	return ERR_PTR(err);
 }

 static void mlxsw_afk_key_info_destroy(struct mlxsw_afk_key_info *key_info)
 {
 	list_del(&key_info->list);
 	kfree(key_info);
 }

 struct mlxsw_afk_key_info *
 mlxsw_afk_key_info_get(struct mlxsw_afk *mlxsw_afk,
 		       struct mlxsw_afk_element_usage *elusage)
 {
 	struct mlxsw_afk_key_info *key_info;

 	key_info = mlxsw_afk_key_info_find(mlxsw_afk, elusage);
 	if (key_info) {
 		key_info->ref_count++;
 		return key_info;
 	}
 	return mlxsw_afk_key_info_create(mlxsw_afk, elusage);
 }
 EXPORT_SYMBOL(mlxsw_afk_key_info_get);

 void mlxsw_afk_key_info_put(struct mlxsw_afk_key_info *key_info)
 {
 	if (--key_info->ref_count)
 		return;
 	mlxsw_afk_key_info_destroy(key_info);
 }
 EXPORT_SYMBOL(mlxsw_afk_key_info_put);

 bool mlxsw_afk_key_info_subset(struct mlxsw_afk_key_info *key_info,
 			       struct mlxsw_afk_element_usage *elusage)
 {
 	return mlxsw_afk_element_usage_subset(elusage, &key_info->elusage);
 }
 EXPORT_SYMBOL(mlxsw_afk_key_info_subset);

 static const struct mlxsw_afk_element_inst *
 mlxsw_afk_block_elinst_get(const struct mlxsw_afk_block *block,
 			   enum mlxsw_afk_element element)
 {
 	int i;

 	for (i = 0; i < block->instances_count; i++) {
 		struct mlxsw_afk_element_inst *elinst;

 		elinst = &block->instances[i];
 		if (elinst->info->element == element)
 			return elinst;
 	}
 	return NULL;
 }

 static const struct mlxsw_afk_element_inst *
 mlxsw_afk_key_info_elinst_get(struct mlxsw_afk_key_info *key_info,
 			      enum mlxsw_afk_element element,
 			      int *p_block_index)
 {
 	const struct mlxsw_afk_element_inst *elinst;
 	const struct mlxsw_afk_block *block;
 	int block_index;

 	if (WARN_ON(!test_bit(element, key_info->elusage.usage)))
 		return NULL;
 	block_index = key_info->element_to_block[element];
 	block = key_info->blocks[block_index];

 	elinst = mlxsw_afk_block_elinst_get(block, element);
 	if (WARN_ON(!elinst))
 		return NULL;

 	*p_block_index = block_index;
 	return elinst;
 }

 u16
 mlxsw_afk_key_info_block_encoding_get(const struct mlxsw_afk_key_info *key_info,
 				      int block_index)
 {
 	return key_info->blocks[block_index]->encoding;
 }
 EXPORT_SYMBOL(mlxsw_afk_key_info_block_encoding_get);

 unsigned int
 mlxsw_afk_key_info_blocks_count_get(const struct mlxsw_afk_key_info *key_info)
 {
 	return key_info->blocks_count;
 }
 EXPORT_SYMBOL(mlxsw_afk_key_info_blocks_count_get);

 void mlxsw_afk_values_add_u32(struct mlxsw_afk_element_values *values,
 			      enum mlxsw_afk_element element,
 			      u32 key_value, u32 mask_value)
 {
 	const struct mlxsw_afk_element_info *elinfo =
 				&mlxsw_afk_element_infos[element];
 	const struct mlxsw_item *storage_item = &elinfo->item;

 	if (!mask_value)
 		return;
 	if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_U32))
 		return;
 	__mlxsw_item_set32(values->storage.key, storage_item, 0, key_value);
 	__mlxsw_item_set32(values->storage.mask, storage_item, 0, mask_value);
 	mlxsw_afk_element_usage_add(&values->elusage, element);
 }
 EXPORT_SYMBOL(mlxsw_afk_values_add_u32);

 void mlxsw_afk_values_add_buf(struct mlxsw_afk_element_values *values,
 			      enum mlxsw_afk_element element,
 			      const char *key_value, const char *mask_value,
 			      unsigned int len)
 {
 	const struct mlxsw_afk_element_info *elinfo =
 				&mlxsw_afk_element_infos[element];
 	const struct mlxsw_item *storage_item = &elinfo->item;

 	if (!memchr_inv(mask_value, 0, len)) /* If mask is zero */
 		return;
 	if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_BUF) ||
 	    WARN_ON(elinfo->item.size.bytes != len))
 		return;
 	__mlxsw_item_memcpy_to(values->storage.key, key_value,
 			       storage_item, 0);
 	__mlxsw_item_memcpy_to(values->storage.mask, mask_value,
 			       storage_item, 0);
 	mlxsw_afk_element_usage_add(&values->elusage, element);
 }
 EXPORT_SYMBOL(mlxsw_afk_values_add_buf);

 static void mlxsw_afk_encode_u32(const struct mlxsw_item *storage_item,
 				 const struct mlxsw_item *output_item,
 				 char *storage, char *output_indexed)
 {
 	u32 value;

 	value = __mlxsw_item_get32(storage, storage_item, 0);
 	__mlxsw_item_set32(output_indexed, output_item, 0, value);
 }

 static void mlxsw_afk_encode_buf(const struct mlxsw_item *storage_item,
 				 const struct mlxsw_item *output_item,
 				 char *storage, char *output_indexed)
 {
 	char *storage_data = __mlxsw_item_data(storage, storage_item, 0);
 	char *output_data = __mlxsw_item_data(output_indexed, output_item, 0);
 	size_t len = output_item->size.bytes;

 	memcpy(output_data, storage_data, len);
 }

 #define MLXSW_AFK_KEY_BLOCK_SIZE 16

 static void mlxsw_afk_encode_one(const struct mlxsw_afk_element_inst *elinst,
 				 int block_index, char *storage, char *output)
 {
 	char *output_indexed = output + block_index * MLXSW_AFK_KEY_BLOCK_SIZE;
 	const struct mlxsw_item *storage_item = &elinst->info->item;
 	const struct mlxsw_item *output_item = &elinst->item;

 	if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_U32)
 		mlxsw_afk_encode_u32(storage_item, output_item,
 				     storage, output_indexed);
 	else if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_BUF)
 		mlxsw_afk_encode_buf(storage_item, output_item,
 				     storage, output_indexed);
 }

 void mlxsw_afk_encode(struct mlxsw_afk_key_info *key_info,
 		      struct mlxsw_afk_element_values *values,
 		      char *key, char *mask)
 {
 	const struct mlxsw_afk_element_inst *elinst;
 	enum mlxsw_afk_element element;
 	int block_index;

 	mlxsw_afk_element_usage_for_each(element, &values->elusage) {
 		elinst = mlxsw_afk_key_info_elinst_get(key_info, element,
 						       &block_index);
 		if (!elinst)
 			continue;
 		mlxsw_afk_encode_one(elinst, block_index,
 				     values->storage.key, key);
 		mlxsw_afk_encode_one(elinst, block_index,
 				     values->storage.mask, mask);
 	}
 }
 EXPORT_SYMBOL(mlxsw_afk_encode);
	/*
	* drivers/net/ethernet/mellanox/mlxsw/core_acl_flex_keys.c
	* Copyright (c) 2017 Mellanox Technologies. All rights reserved.
	* Copyright (c) 2017 Jiri Pirko <jiri@mellanox.com>
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions are met:
	*
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	* 3. Neither the names of the copyright holders nor the names of its
	* contributors may be used to endorse or promote products derived from
	* this software without specific prior written permission.
	*
	* Alternatively, this software may be distributed under the terms of the
	* GNU General Public License ("GPL") version 2 as published by the Free
	* Software Foundation.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
	* LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
	* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
	* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
	* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
	* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
	* POSSIBILITY OF SUCH DAMAGE.
	*/

	#include <linux/kernel.h>
	#include <linux/slab.h>
	#include <linux/list.h>
	#include <linux/errno.h>

	#include "item.h"
	#include "core_acl_flex_keys.h"

	struct mlxsw_afk {
	struct list_head key_info_list;
	unsigned int max_blocks;
	const struct mlxsw_afk_block *blocks;
	unsigned int blocks_count;
	};

	static bool mlxsw_afk_blocks_check(struct mlxsw_afk *mlxsw_afk)
	{
	int i;
	int j;

	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
	const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];

	for (j = 0; j < block->instances_count; j++) {
	struct mlxsw_afk_element_inst *elinst;

	elinst = &block->instances[j];
	if (elinst->type != elinst->info->type \|\|
	elinst->item.size.bits !=
	elinst->info->item.size.bits)
	return false;
	}
	}
	return true;
	}

	struct mlxsw_afk *mlxsw_afk_create(unsigned int max_blocks,
	const struct mlxsw_afk_block *blocks,
	unsigned int blocks_count)
	{
	struct mlxsw_afk *mlxsw_afk;

	mlxsw_afk = kzalloc(sizeof(*mlxsw_afk), GFP_KERNEL);
	if (!mlxsw_afk)
	return NULL;
	INIT_LIST_HEAD(&mlxsw_afk->key_info_list);
	mlxsw_afk->max_blocks = max_blocks;
	mlxsw_afk->blocks = blocks;
	mlxsw_afk->blocks_count = blocks_count;
	WARN_ON(!mlxsw_afk_blocks_check(mlxsw_afk));
	return mlxsw_afk;
	}
	EXPORT_SYMBOL(mlxsw_afk_create);

	void mlxsw_afk_destroy(struct mlxsw_afk *mlxsw_afk)
	{
	WARN_ON(!list_empty(&mlxsw_afk->key_info_list));
	kfree(mlxsw_afk);
	}
	EXPORT_SYMBOL(mlxsw_afk_destroy);

	struct mlxsw_afk_key_info {
	struct list_head list;
	unsigned int ref_count;
	unsigned int blocks_count;
	int element_to_block[MLXSW_AFK_ELEMENT_MAX]; /* index is element, value
	* is index inside "blocks"
	*/
	struct mlxsw_afk_element_usage elusage;
	const struct mlxsw_afk_block *blocks[0];
	};

	static bool
	mlxsw_afk_key_info_elements_eq(struct mlxsw_afk_key_info *key_info,
	struct mlxsw_afk_element_usage *elusage)
	{
	return memcmp(&key_info->elusage, elusage, sizeof(*elusage)) == 0;
	}

	static struct mlxsw_afk_key_info *
	mlxsw_afk_key_info_find(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_element_usage *elusage)
	{
	struct mlxsw_afk_key_info *key_info;

	list_for_each_entry(key_info, &mlxsw_afk->key_info_list, list) {
	if (mlxsw_afk_key_info_elements_eq(key_info, elusage))
	return key_info;
	}
	return NULL;
	}

	struct mlxsw_afk_picker {
	struct {
	DECLARE_BITMAP(element, MLXSW_AFK_ELEMENT_MAX);
	unsigned int total;
	} hits[0];
	};

	static void mlxsw_afk_picker_count_hits(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_picker *picker,
	enum mlxsw_afk_element element)
	{
	int i;
	int j;

	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
	const struct mlxsw_afk_block *block = &mlxsw_afk->blocks[i];

	for (j = 0; j < block->instances_count; j++) {
	struct mlxsw_afk_element_inst *elinst;

	elinst = &block->instances[j];
	if (elinst->info->element == element) {
	__set_bit(element, picker->hits[i].element);
	picker->hits[i].total++;
	}
	}
	}
	}

	static void mlxsw_afk_picker_subtract_hits(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_picker *picker,
	int block_index)
	{
	DECLARE_BITMAP(hits_element, MLXSW_AFK_ELEMENT_MAX);
	int i;
	int j;

	memcpy(&hits_element, &picker->hits[block_index].element,
	sizeof(hits_element));

	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
	for_each_set_bit(j, hits_element, MLXSW_AFK_ELEMENT_MAX) {
	if (__test_and_clear_bit(j, picker->hits[i].element))
	picker->hits[i].total--;
	}
	}
	}

	static int mlxsw_afk_picker_most_hits_get(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_picker *picker)
	{
	int most_index = -EINVAL; /* Should never happen to return this */
	int most_hits = 0;
	int i;

	for (i = 0; i < mlxsw_afk->blocks_count; i++) {
	if (picker->hits[i].total > most_hits) {
	most_hits = picker->hits[i].total;
	most_index = i;
	}
	}
	return most_index;
	}

	static int mlxsw_afk_picker_key_info_add(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_picker *picker,
	int block_index,
	struct mlxsw_afk_key_info *key_info)
	{
	enum mlxsw_afk_element element;

	if (key_info->blocks_count == mlxsw_afk->max_blocks)
	return -EINVAL;

	for_each_set_bit(element, picker->hits[block_index].element,
	MLXSW_AFK_ELEMENT_MAX) {
	key_info->element_to_block[element] = key_info->blocks_count;
	mlxsw_afk_element_usage_add(&key_info->elusage, element);
	}

	key_info->blocks[key_info->blocks_count] =
	&mlxsw_afk->blocks[block_index];
	key_info->blocks_count++;
	return 0;
	}

	static int mlxsw_afk_picker(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_key_info *key_info,
	struct mlxsw_afk_element_usage *elusage)
	{
	struct mlxsw_afk_picker *picker;
	enum mlxsw_afk_element element;
	size_t alloc_size;
	int err;

	alloc_size = sizeof(picker->hits[0]) * mlxsw_afk->blocks_count;
	picker = kzalloc(alloc_size, GFP_KERNEL);
	if (!picker)
	return -ENOMEM;

	/* Since the same elements could be present in multiple blocks,
	* we must find out optimal block list in order to make the
	* block count as low as possible.
	*
	* First, we count hits. We go over all available blocks and count
	* how many of requested elements are covered by each.
	*
	* Then in loop, we find block with most hits and add it to
	* output key_info. Then we have to subtract this block hits so
	* the next iteration will find most suitable block for
	* the rest of requested elements.
	*/

	mlxsw_afk_element_usage_for_each(element, elusage)
	mlxsw_afk_picker_count_hits(mlxsw_afk, picker, element);

	do {
	int block_index;

	block_index = mlxsw_afk_picker_most_hits_get(mlxsw_afk, picker);
	if (block_index < 0) {
	err = block_index;
	goto out;
	}
	err = mlxsw_afk_picker_key_info_add(mlxsw_afk, picker,
	block_index, key_info);
	if (err)
	goto out;
	mlxsw_afk_picker_subtract_hits(mlxsw_afk, picker, block_index);
	} while (!mlxsw_afk_key_info_elements_eq(key_info, elusage));

	err = 0;
	out:
	kfree(picker);
	return err;
	}

	static struct mlxsw_afk_key_info *
	mlxsw_afk_key_info_create(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_element_usage *elusage)
	{
	struct mlxsw_afk_key_info *key_info;
	size_t alloc_size;
	int err;

	alloc_size = sizeof(*key_info) +
	sizeof(key_info->blocks[0]) * mlxsw_afk->max_blocks;
	key_info = kzalloc(alloc_size, GFP_KERNEL);
	if (!key_info)
	return ERR_PTR(-ENOMEM);
	err = mlxsw_afk_picker(mlxsw_afk, key_info, elusage);
	if (err)
	goto err_picker;
	list_add(&key_info->list, &mlxsw_afk->key_info_list);
	key_info->ref_count = 1;
	return key_info;

	err_picker:
	kfree(key_info);
	return ERR_PTR(err);
	}

	static void mlxsw_afk_key_info_destroy(struct mlxsw_afk_key_info *key_info)
	{
	list_del(&key_info->list);
	kfree(key_info);
	}

	struct mlxsw_afk_key_info *
	mlxsw_afk_key_info_get(struct mlxsw_afk *mlxsw_afk,
	struct mlxsw_afk_element_usage *elusage)
	{
	struct mlxsw_afk_key_info *key_info;

	key_info = mlxsw_afk_key_info_find(mlxsw_afk, elusage);
	if (key_info) {
	key_info->ref_count++;
	return key_info;
	}
	return mlxsw_afk_key_info_create(mlxsw_afk, elusage);
	}
	EXPORT_SYMBOL(mlxsw_afk_key_info_get);

	void mlxsw_afk_key_info_put(struct mlxsw_afk_key_info *key_info)
	{
	if (--key_info->ref_count)
	return;
	mlxsw_afk_key_info_destroy(key_info);
	}
	EXPORT_SYMBOL(mlxsw_afk_key_info_put);

	bool mlxsw_afk_key_info_subset(struct mlxsw_afk_key_info *key_info,
	struct mlxsw_afk_element_usage *elusage)
	{
	return mlxsw_afk_element_usage_subset(elusage, &key_info->elusage);
	}
	EXPORT_SYMBOL(mlxsw_afk_key_info_subset);

	static const struct mlxsw_afk_element_inst *
	mlxsw_afk_block_elinst_get(const struct mlxsw_afk_block *block,
	enum mlxsw_afk_element element)
	{
	int i;

	for (i = 0; i < block->instances_count; i++) {
	struct mlxsw_afk_element_inst *elinst;

	elinst = &block->instances[i];
	if (elinst->info->element == element)
	return elinst;
	}
	return NULL;
	}

	static const struct mlxsw_afk_element_inst *
	mlxsw_afk_key_info_elinst_get(struct mlxsw_afk_key_info *key_info,
	enum mlxsw_afk_element element,
	int *p_block_index)
	{
	const struct mlxsw_afk_element_inst *elinst;
	const struct mlxsw_afk_block *block;
	int block_index;

	if (WARN_ON(!test_bit(element, key_info->elusage.usage)))
	return NULL;
	block_index = key_info->element_to_block[element];
	block = key_info->blocks[block_index];

	elinst = mlxsw_afk_block_elinst_get(block, element);
	if (WARN_ON(!elinst))
	return NULL;

	*p_block_index = block_index;
	return elinst;
	}

	u16
	mlxsw_afk_key_info_block_encoding_get(const struct mlxsw_afk_key_info *key_info,
	int block_index)
	{
	return key_info->blocks[block_index]->encoding;
	}
	EXPORT_SYMBOL(mlxsw_afk_key_info_block_encoding_get);

	unsigned int
	mlxsw_afk_key_info_blocks_count_get(const struct mlxsw_afk_key_info *key_info)
	{
	return key_info->blocks_count;
	}
	EXPORT_SYMBOL(mlxsw_afk_key_info_blocks_count_get);

	void mlxsw_afk_values_add_u32(struct mlxsw_afk_element_values *values,
	enum mlxsw_afk_element element,
	u32 key_value, u32 mask_value)
	{
	const struct mlxsw_afk_element_info *elinfo =
	&mlxsw_afk_element_infos[element];
	const struct mlxsw_item *storage_item = &elinfo->item;

	if (!mask_value)
	return;
	if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_U32))
	return;
	__mlxsw_item_set32(values->storage.key, storage_item, 0, key_value);
	__mlxsw_item_set32(values->storage.mask, storage_item, 0, mask_value);
	mlxsw_afk_element_usage_add(&values->elusage, element);
	}
	EXPORT_SYMBOL(mlxsw_afk_values_add_u32);

	void mlxsw_afk_values_add_buf(struct mlxsw_afk_element_values *values,
	enum mlxsw_afk_element element,
	const char key_value, const char mask_value,
	unsigned int len)
	{
	const struct mlxsw_afk_element_info *elinfo =
	&mlxsw_afk_element_infos[element];
	const struct mlxsw_item *storage_item = &elinfo->item;

	if (!memchr_inv(mask_value, 0, len)) /* If mask is zero */
	return;
	if (WARN_ON(elinfo->type != MLXSW_AFK_ELEMENT_TYPE_BUF) \|\|
	WARN_ON(elinfo->item.size.bytes != len))
	return;
	__mlxsw_item_memcpy_to(values->storage.key, key_value,
	storage_item, 0);
	__mlxsw_item_memcpy_to(values->storage.mask, mask_value,
	storage_item, 0);
	mlxsw_afk_element_usage_add(&values->elusage, element);
	}
	EXPORT_SYMBOL(mlxsw_afk_values_add_buf);

	static void mlxsw_afk_encode_u32(const struct mlxsw_item *storage_item,
	const struct mlxsw_item *output_item,
	char storage, char output_indexed)
	{
	u32 value;

	value = __mlxsw_item_get32(storage, storage_item, 0);
	__mlxsw_item_set32(output_indexed, output_item, 0, value);
	}

	static void mlxsw_afk_encode_buf(const struct mlxsw_item *storage_item,
	const struct mlxsw_item *output_item,
	char storage, char output_indexed)
	{
	char *storage_data = __mlxsw_item_data(storage, storage_item, 0);
	char *output_data = __mlxsw_item_data(output_indexed, output_item, 0);
	size_t len = output_item->size.bytes;

	memcpy(output_data, storage_data, len);
	}

	#define MLXSW_AFK_KEY_BLOCK_SIZE 16

	static void mlxsw_afk_encode_one(const struct mlxsw_afk_element_inst *elinst,
	int block_index, char storage, char output)
	{
	char output_indexed = output + block_index MLXSW_AFK_KEY_BLOCK_SIZE;
	const struct mlxsw_item *storage_item = &elinst->info->item;
	const struct mlxsw_item *output_item = &elinst->item;

	if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_U32)
	mlxsw_afk_encode_u32(storage_item, output_item,
	storage, output_indexed);
	else if (elinst->type == MLXSW_AFK_ELEMENT_TYPE_BUF)
	mlxsw_afk_encode_buf(storage_item, output_item,
	storage, output_indexed);
	}

	void mlxsw_afk_encode(struct mlxsw_afk_key_info *key_info,
	struct mlxsw_afk_element_values *values,
	char key, char mask)
	{
	const struct mlxsw_afk_element_inst *elinst;
	enum mlxsw_afk_element element;
	int block_index;

	mlxsw_afk_element_usage_for_each(element, &values->elusage) {
	elinst = mlxsw_afk_key_info_elinst_get(key_info, element,
	&block_index);
	if (!elinst)
	continue;
	mlxsw_afk_encode_one(elinst, block_index,
	values->storage.key, key);
	mlxsw_afk_encode_one(elinst, block_index,
	values->storage.mask, mask);
	}
	}
	EXPORT_SYMBOL(mlxsw_afk_encode);