1*4882a593Smuzhiyun /*
2*4882a593Smuzhiyun * Copyright (c) 2011 Chelsio Communications. All rights reserved.
3*4882a593Smuzhiyun *
4*4882a593Smuzhiyun * This software is available to you under a choice of one of two
5*4882a593Smuzhiyun * licenses. You may choose to be licensed under the terms of the GNU
6*4882a593Smuzhiyun * General Public License (GPL) Version 2, available from the file
7*4882a593Smuzhiyun * COPYING in the main directory of this source tree, or the
8*4882a593Smuzhiyun * OpenIB.org BSD license below:
9*4882a593Smuzhiyun *
10*4882a593Smuzhiyun * Redistribution and use in source and binary forms, with or
11*4882a593Smuzhiyun * without modification, are permitted provided that the following
12*4882a593Smuzhiyun * conditions are met:
13*4882a593Smuzhiyun *
14*4882a593Smuzhiyun * - Redistributions of source code must retain the above
15*4882a593Smuzhiyun * copyright notice, this list of conditions and the following
16*4882a593Smuzhiyun * disclaimer.
17*4882a593Smuzhiyun *
18*4882a593Smuzhiyun * - Redistributions in binary form must reproduce the above
19*4882a593Smuzhiyun * copyright notice, this list of conditions and the following
20*4882a593Smuzhiyun * disclaimer in the documentation and/or other materials
21*4882a593Smuzhiyun * provided with the distribution.
22*4882a593Smuzhiyun *
23*4882a593Smuzhiyun * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
24*4882a593Smuzhiyun * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
25*4882a593Smuzhiyun * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
26*4882a593Smuzhiyun * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
27*4882a593Smuzhiyun * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
28*4882a593Smuzhiyun * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
29*4882a593Smuzhiyun * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30*4882a593Smuzhiyun * SOFTWARE.
31*4882a593Smuzhiyun */
32*4882a593Smuzhiyun #include <linux/kernel.h>
33*4882a593Smuzhiyun #include <linux/random.h>
34*4882a593Smuzhiyun #include "iw_cxgb4.h"
35*4882a593Smuzhiyun
36*4882a593Smuzhiyun #define RANDOM_SKIP 16
37*4882a593Smuzhiyun
38*4882a593Smuzhiyun /*
39*4882a593Smuzhiyun * Trivial bitmap-based allocator. If the random flag is set, the
40*4882a593Smuzhiyun * allocator is designed to:
41*4882a593Smuzhiyun * - pseudo-randomize the id returned such that it is not trivially predictable.
42*4882a593Smuzhiyun * - avoid reuse of recently used id (at the expense of predictability)
43*4882a593Smuzhiyun */
c4iw_id_alloc(struct c4iw_id_table * alloc)44*4882a593Smuzhiyun u32 c4iw_id_alloc(struct c4iw_id_table *alloc)
45*4882a593Smuzhiyun {
46*4882a593Smuzhiyun unsigned long flags;
47*4882a593Smuzhiyun u32 obj;
48*4882a593Smuzhiyun
49*4882a593Smuzhiyun spin_lock_irqsave(&alloc->lock, flags);
50*4882a593Smuzhiyun
51*4882a593Smuzhiyun obj = find_next_zero_bit(alloc->table, alloc->max, alloc->last);
52*4882a593Smuzhiyun if (obj >= alloc->max)
53*4882a593Smuzhiyun obj = find_first_zero_bit(alloc->table, alloc->max);
54*4882a593Smuzhiyun
55*4882a593Smuzhiyun if (obj < alloc->max) {
56*4882a593Smuzhiyun if (alloc->flags & C4IW_ID_TABLE_F_RANDOM)
57*4882a593Smuzhiyun alloc->last += prandom_u32() % RANDOM_SKIP;
58*4882a593Smuzhiyun else
59*4882a593Smuzhiyun alloc->last = obj + 1;
60*4882a593Smuzhiyun if (alloc->last >= alloc->max)
61*4882a593Smuzhiyun alloc->last = 0;
62*4882a593Smuzhiyun set_bit(obj, alloc->table);
63*4882a593Smuzhiyun obj += alloc->start;
64*4882a593Smuzhiyun } else
65*4882a593Smuzhiyun obj = -1;
66*4882a593Smuzhiyun
67*4882a593Smuzhiyun spin_unlock_irqrestore(&alloc->lock, flags);
68*4882a593Smuzhiyun return obj;
69*4882a593Smuzhiyun }
70*4882a593Smuzhiyun
c4iw_id_free(struct c4iw_id_table * alloc,u32 obj)71*4882a593Smuzhiyun void c4iw_id_free(struct c4iw_id_table *alloc, u32 obj)
72*4882a593Smuzhiyun {
73*4882a593Smuzhiyun unsigned long flags;
74*4882a593Smuzhiyun
75*4882a593Smuzhiyun obj -= alloc->start;
76*4882a593Smuzhiyun
77*4882a593Smuzhiyun spin_lock_irqsave(&alloc->lock, flags);
78*4882a593Smuzhiyun clear_bit(obj, alloc->table);
79*4882a593Smuzhiyun spin_unlock_irqrestore(&alloc->lock, flags);
80*4882a593Smuzhiyun }
81*4882a593Smuzhiyun
c4iw_id_table_alloc(struct c4iw_id_table * alloc,u32 start,u32 num,u32 reserved,u32 flags)82*4882a593Smuzhiyun int c4iw_id_table_alloc(struct c4iw_id_table *alloc, u32 start, u32 num,
83*4882a593Smuzhiyun u32 reserved, u32 flags)
84*4882a593Smuzhiyun {
85*4882a593Smuzhiyun int i;
86*4882a593Smuzhiyun
87*4882a593Smuzhiyun alloc->start = start;
88*4882a593Smuzhiyun alloc->flags = flags;
89*4882a593Smuzhiyun if (flags & C4IW_ID_TABLE_F_RANDOM)
90*4882a593Smuzhiyun alloc->last = prandom_u32() % RANDOM_SKIP;
91*4882a593Smuzhiyun else
92*4882a593Smuzhiyun alloc->last = 0;
93*4882a593Smuzhiyun alloc->max = num;
94*4882a593Smuzhiyun spin_lock_init(&alloc->lock);
95*4882a593Smuzhiyun alloc->table = kmalloc_array(BITS_TO_LONGS(num), sizeof(long),
96*4882a593Smuzhiyun GFP_KERNEL);
97*4882a593Smuzhiyun if (!alloc->table)
98*4882a593Smuzhiyun return -ENOMEM;
99*4882a593Smuzhiyun
100*4882a593Smuzhiyun bitmap_zero(alloc->table, num);
101*4882a593Smuzhiyun if (!(alloc->flags & C4IW_ID_TABLE_F_EMPTY))
102*4882a593Smuzhiyun for (i = 0; i < reserved; ++i)
103*4882a593Smuzhiyun set_bit(i, alloc->table);
104*4882a593Smuzhiyun
105*4882a593Smuzhiyun return 0;
106*4882a593Smuzhiyun }
107*4882a593Smuzhiyun
c4iw_id_table_free(struct c4iw_id_table * alloc)108*4882a593Smuzhiyun void c4iw_id_table_free(struct c4iw_id_table *alloc)
109*4882a593Smuzhiyun {
110*4882a593Smuzhiyun kfree(alloc->table);
111*4882a593Smuzhiyun }
112