1 /*
2 * Copyright (c) 2013-2016 François Tigeot
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice unmodified, this list of conditions, and the following
10 * 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 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27 #ifndef _LINUX_IDR_H_
28 #define _LINUX_IDR_H_
29
30 #include <linux/slab.h>
31
32 #include <sys/idr.h>
33
34 #ifdef MALLOC_DECLARE
35 MALLOC_DECLARE(M_IDR);
36 #endif
37
38 #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */
39 #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1)
40 #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
41
42 struct ida_bitmap {
43 long nr_busy;
44 unsigned long bitmap[IDA_BITMAP_LONGS];
45 };
46
47 struct ida {
48 struct idr idr;
49 struct ida_bitmap *free_bitmap;
50 };
51
52 #define DEFINE_IDA(name) \
53 struct ida name = { \
54 .idr = { .idr_token = LWKT_TOKEN_INITIALIZER("idrtok") }, \
55 .free_bitmap = NULL \
56 } \
57
58 static inline void
ida_init(struct ida * ida)59 ida_init(struct ida *ida)
60 {
61 idr_init(&ida->idr);
62 }
63
64 static inline void
ida_simple_remove(struct ida * ida,unsigned int id)65 ida_simple_remove(struct ida *ida, unsigned int id)
66 {
67 idr_remove(&ida->idr, id);
68 }
69
70 static inline void
ida_remove(struct ida * ida,int id)71 ida_remove(struct ida *ida, int id)
72 {
73 idr_remove(&ida->idr, id);
74 }
75
76 static inline void
ida_destroy(struct ida * ida)77 ida_destroy(struct ida *ida)
78 {
79 idr_destroy(&ida->idr);
80 if (ida->free_bitmap != NULL) {
81 /* kfree() is a linux macro! Work around the cpp pass */
82 _kfree(ida->free_bitmap, M_IDR);
83 }
84 }
85
86 static inline int
ida_simple_get(struct ida * ida,unsigned int start,unsigned int end,gfp_t gfp_mask)87 ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, gfp_t gfp_mask)
88 {
89 int id;
90 unsigned int lim;
91
92 if ((end == 0) || (end > 0x80000000))
93 lim = 0x80000000;
94 else
95 lim = end - 1;
96
97 idr_preload(gfp_mask);
98 id = idr_alloc(&ida->idr, NULL, start, lim, gfp_mask);
99 idr_preload_end();
100
101 return id;
102 }
103
104 static inline void *
idr_get_next(struct idr * idp,int * nextid)105 idr_get_next(struct idr *idp, int *nextid)
106 {
107 void *res = NULL;
108
109 lwkt_gettoken(&idp->idr_token);
110
111 for (int id = *nextid; id < idp->idr_count; id++) {
112 res = idr_find(idp, id);
113 if (res == NULL)
114 continue;
115 *nextid = id;
116 break;
117 }
118
119 lwkt_reltoken(&idp->idr_token);
120 return res;
121 }
122
123 #define idr_for_each_entry(idp, entry, id) \
124 for (id = 0; ((entry) = idr_get_next(idp, &(id))) != NULL; ++id)
125
126 #endif /* _LINUX_IDR_H_ */
127