hw/cxgb4/id_table.c

0001 /*
0002  * Copyright (c) 2011 Chelsio Communications.  All rights reserved.
0003  *
0004  * This software is available to you under a choice of one of two
0005  * licenses.  You may choose to be licensed under the terms of the GNU
0006  * General Public License (GPL) Version 2, available from the file
0007  * COPYING in the main directory of this source tree, or the
0008  * OpenIB.org BSD license below:
0009  *
0010  *     Redistribution and use in source and binary forms, with or
0011  *     without modification, are permitted provided that the following
0012  *     conditions are met:
0013  *
0014  *      - Redistributions of source code must retain the above
0015  *        copyright notice, this list of conditions and the following
0016  *        disclaimer.
0017  *
0018  *      - Redistributions in binary form must reproduce the above
0019  *        copyright notice, this list of conditions and the following
0020  *        disclaimer in the documentation and/or other materials
0021  *        provided with the distribution.
0022  *
0023  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
0024  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
0025  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
0026  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
0027  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
0028  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
0029  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
0030  * SOFTWARE.
0031  */
0032 #include <linux/kernel.h>
0033 #include <linux/random.h>
0034 #include "iw_cxgb4.h"
0035
0036 #define RANDOM_SKIP 16
0037
0038 /*
0039  * Trivial bitmap-based allocator. If the random flag is set, the
0040  * allocator is designed to:
0041  * - pseudo-randomize the id returned such that it is not trivially predictable.
0042  * - avoid reuse of recently used id (at the expense of predictability)
0043  */
0044 u32 c4iw_id_alloc(struct c4iw_id_table *alloc)
0045 {
0046     unsigned long flags;
0047     u32 obj;
0048
0049     spin_lock_irqsave(&alloc->lock, flags);
0050
0051     obj = find_next_zero_bit(alloc->table, alloc->max, alloc->last);
0052     if (obj >= alloc->max)
0053         obj = find_first_zero_bit(alloc->table, alloc->max);
0054
0055     if (obj < alloc->max) {
0056         if (alloc->flags & C4IW_ID_TABLE_F_RANDOM)
0057             alloc->last += prandom_u32() % RANDOM_SKIP;
0058         else
0059             alloc->last = obj + 1;
0060         if (alloc->last >= alloc->max)
0061             alloc->last = 0;
0062         __set_bit(obj, alloc->table);
0063         obj += alloc->start;
0064     } else
0065         obj = -1;
0066
0067     spin_unlock_irqrestore(&alloc->lock, flags);
0068     return obj;
0069 }
0070
0071 void c4iw_id_free(struct c4iw_id_table *alloc, u32 obj)
0072 {
0073     unsigned long flags;
0074
0075     obj -= alloc->start;
0076
0077     spin_lock_irqsave(&alloc->lock, flags);
0078     __clear_bit(obj, alloc->table);
0079     spin_unlock_irqrestore(&alloc->lock, flags);
0080 }
0081
0082 int c4iw_id_table_alloc(struct c4iw_id_table *alloc, u32 start, u32 num,
0083             u32 reserved, u32 flags)
0084 {
0085     alloc->start = start;
0086     alloc->flags = flags;
0087     if (flags & C4IW_ID_TABLE_F_RANDOM)
0088         alloc->last = prandom_u32() % RANDOM_SKIP;
0089     else
0090         alloc->last = 0;
0091     alloc->max = num;
0092     spin_lock_init(&alloc->lock);
0093     alloc->table = bitmap_zalloc(num, GFP_KERNEL);
0094     if (!alloc->table)
0095         return -ENOMEM;
0096
0097     if (!(alloc->flags & C4IW_ID_TABLE_F_EMPTY))
0098         bitmap_set(alloc->table, 0, reserved);
0099
0100     return 0;
0101 }
0102
0103 void c4iw_id_table_free(struct c4iw_id_table *alloc)
0104 {
0105     bitmap_free(alloc->table);
0106 }