Branch data Line data Source code
1 : : /*
2 : : * include/linux/idr.h
3 : : *
4 : : * 2002-10-18 written by Jim Houston jim.houston@ccur.com
5 : : * Copyright (C) 2002 by Concurrent Computer Corporation
6 : : * Distributed under the GNU GPL license version 2.
7 : : *
8 : : * Small id to pointer translation service avoiding fixed sized
9 : : * tables.
10 : : */
11 : :
12 : : #ifndef __IDR_H__
13 : : #define __IDR_H__
14 : :
15 : : #include <linux/types.h>
16 : : #include <linux/bitops.h>
17 : : #include <linux/init.h>
18 : : #include <linux/rcupdate.h>
19 : :
20 : : /*
21 : : * We want shallower trees and thus more bits covered at each layer. 8
22 : : * bits gives us large enough first layer for most use cases and maximum
23 : : * tree depth of 4. Each idr_layer is slightly larger than 2k on 64bit and
24 : : * 1k on 32bit.
25 : : */
26 : : #define IDR_BITS 8
27 : : #define IDR_SIZE (1 << IDR_BITS)
28 : : #define IDR_MASK ((1 << IDR_BITS)-1)
29 : :
30 : : struct idr_layer {
31 : : int prefix; /* the ID prefix of this idr_layer */
32 : : DECLARE_BITMAP(bitmap, IDR_SIZE); /* A zero bit means "space here" */
33 : : struct idr_layer __rcu *ary[1<<IDR_BITS];
34 : : int count; /* When zero, we can release it */
35 : : int layer; /* distance from leaf */
36 : : struct rcu_head rcu_head;
37 : : };
38 : :
39 : : struct idr {
40 : : struct idr_layer __rcu *hint; /* the last layer allocated from */
41 : : struct idr_layer __rcu *top;
42 : : struct idr_layer *id_free;
43 : : int layers; /* only valid w/o concurrent changes */
44 : : int id_free_cnt;
45 : : int cur; /* current pos for cyclic allocation */
46 : : spinlock_t lock;
47 : : };
48 : :
49 : : #define IDR_INIT(name) \
50 : : { \
51 : : .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
52 : : }
53 : : #define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
54 : :
55 : : /**
56 : : * DOC: idr sync
57 : : * idr synchronization (stolen from radix-tree.h)
58 : : *
59 : : * idr_find() is able to be called locklessly, using RCU. The caller must
60 : : * ensure calls to this function are made within rcu_read_lock() regions.
61 : : * Other readers (lock-free or otherwise) and modifications may be running
62 : : * concurrently.
63 : : *
64 : : * It is still required that the caller manage the synchronization and
65 : : * lifetimes of the items. So if RCU lock-free lookups are used, typically
66 : : * this would mean that the items have their own locks, or are amenable to
67 : : * lock-free access; and that the items are freed by RCU (or only freed after
68 : : * having been deleted from the idr tree *and* a synchronize_rcu() grace
69 : : * period).
70 : : */
71 : :
72 : : /*
73 : : * This is what we export.
74 : : */
75 : :
76 : : void *idr_find_slowpath(struct idr *idp, int id);
77 : : void idr_preload(gfp_t gfp_mask);
78 : : int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
79 : : int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask);
80 : : int idr_for_each(struct idr *idp,
81 : : int (*fn)(int id, void *p, void *data), void *data);
82 : : void *idr_get_next(struct idr *idp, int *nextid);
83 : : void *idr_replace(struct idr *idp, void *ptr, int id);
84 : : void idr_remove(struct idr *idp, int id);
85 : : void idr_free(struct idr *idp, int id);
86 : : void idr_destroy(struct idr *idp);
87 : : void idr_init(struct idr *idp);
88 : :
89 : : /**
90 : : * idr_preload_end - end preload section started with idr_preload()
91 : : *
92 : : * Each idr_preload() should be matched with an invocation of this
93 : : * function. See idr_preload() for details.
94 : : */
95 : : static inline void idr_preload_end(void)
96 : : {
97 : 9124 : preempt_enable();
98 : : }
99 : :
100 : : /**
101 : : * idr_find - return pointer for given id
102 : : * @idr: idr handle
103 : : * @id: lookup key
104 : : *
105 : : * Return the pointer given the id it has been registered with. A %NULL
106 : : * return indicates that @id is not valid or you passed %NULL in
107 : : * idr_get_new().
108 : : *
109 : : * This function can be called under rcu_read_lock(), given that the leaf
110 : : * pointers lifetimes are correctly managed.
111 : : */
112 : : static inline void *idr_find(struct idr *idr, int id)
113 : : {
114 : 50128847 : struct idr_layer *hint = rcu_dereference_raw(idr->hint);
115 : :
116 [ # # ]: 50128847 : if (hint && (id & ~IDR_MASK) == hint->prefix)
[ # # + - ]
[ + + # # ]
[ # # # # ]
[ # # ][ + ]
[ + + ][ + - ]
[ + - ][ + - ]
[ + + ]
117 : 49247381 : return rcu_dereference_raw(hint->ary[id & IDR_MASK]);
118 : :
119 : 881466 : return idr_find_slowpath(idr, id);
120 : : }
121 : :
122 : : /**
123 : : * idr_for_each_entry - iterate over an idr's elements of a given type
124 : : * @idp: idr handle
125 : : * @entry: the type * to use as cursor
126 : : * @id: id entry's key
127 : : *
128 : : * @entry and @id do not need to be initialized before the loop, and
129 : : * after normal terminatinon @entry is left with the value NULL. This
130 : : * is convenient for a "not found" value.
131 : : */
132 : : #define idr_for_each_entry(idp, entry, id) \
133 : : for (id = 0; ((entry) = idr_get_next(idp, &(id))) != NULL; ++id)
134 : :
135 : : /*
136 : : * Don't use the following functions. These exist only to suppress
137 : : * deprecated warnings on EXPORT_SYMBOL()s.
138 : : */
139 : : int __idr_pre_get(struct idr *idp, gfp_t gfp_mask);
140 : : int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
141 : : void __idr_remove_all(struct idr *idp);
142 : :
143 : : /**
144 : : * idr_pre_get - reserve resources for idr allocation
145 : : * @idp: idr handle
146 : : * @gfp_mask: memory allocation flags
147 : : *
148 : : * Part of old alloc interface. This is going away. Use
149 : : * idr_preload[_end]() and idr_alloc() instead.
150 : : */
151 : : static inline int __deprecated idr_pre_get(struct idr *idp, gfp_t gfp_mask)
152 : : {
153 : : return __idr_pre_get(idp, gfp_mask);
154 : : }
155 : :
156 : : /**
157 : : * idr_get_new_above - allocate new idr entry above or equal to a start id
158 : : * @idp: idr handle
159 : : * @ptr: pointer you want associated with the id
160 : : * @starting_id: id to start search at
161 : : * @id: pointer to the allocated handle
162 : : *
163 : : * Part of old alloc interface. This is going away. Use
164 : : * idr_preload[_end]() and idr_alloc() instead.
165 : : */
166 : : static inline int __deprecated idr_get_new_above(struct idr *idp, void *ptr,
167 : : int starting_id, int *id)
168 : : {
169 : : return __idr_get_new_above(idp, ptr, starting_id, id);
170 : : }
171 : :
172 : : /**
173 : : * idr_get_new - allocate new idr entry
174 : : * @idp: idr handle
175 : : * @ptr: pointer you want associated with the id
176 : : * @id: pointer to the allocated handle
177 : : *
178 : : * Part of old alloc interface. This is going away. Use
179 : : * idr_preload[_end]() and idr_alloc() instead.
180 : : */
181 : : static inline int __deprecated idr_get_new(struct idr *idp, void *ptr, int *id)
182 : : {
183 : : return __idr_get_new_above(idp, ptr, 0, id);
184 : : }
185 : :
186 : : /**
187 : : * idr_remove_all - remove all ids from the given idr tree
188 : : * @idp: idr handle
189 : : *
190 : : * If you're trying to destroy @idp, calling idr_destroy() is enough.
191 : : * This is going away. Don't use.
192 : : */
193 : : static inline void __deprecated idr_remove_all(struct idr *idp)
194 : : {
195 : : __idr_remove_all(idp);
196 : : }
197 : :
198 : : /*
199 : : * IDA - IDR based id allocator, use when translation from id to
200 : : * pointer isn't necessary.
201 : : *
202 : : * IDA_BITMAP_LONGS is calculated to be one less to accommodate
203 : : * ida_bitmap->nr_busy so that the whole struct fits in 128 bytes.
204 : : */
205 : : #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */
206 : : #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1)
207 : : #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
208 : :
209 : : struct ida_bitmap {
210 : : long nr_busy;
211 : : unsigned long bitmap[IDA_BITMAP_LONGS];
212 : : };
213 : :
214 : : struct ida {
215 : : struct idr idr;
216 : : struct ida_bitmap *free_bitmap;
217 : : };
218 : :
219 : : #define IDA_INIT(name) { .idr = IDR_INIT((name).idr), .free_bitmap = NULL, }
220 : : #define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
221 : :
222 : : int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
223 : : int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
224 : : void ida_remove(struct ida *ida, int id);
225 : : void ida_destroy(struct ida *ida);
226 : : void ida_init(struct ida *ida);
227 : :
228 : : int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
229 : : gfp_t gfp_mask);
230 : : void ida_simple_remove(struct ida *ida, unsigned int id);
231 : :
232 : : /**
233 : : * ida_get_new - allocate new ID
234 : : * @ida: idr handle
235 : : * @p_id: pointer to the allocated handle
236 : : *
237 : : * Simple wrapper around ida_get_new_above() w/ @starting_id of zero.
238 : : */
239 : : static inline int ida_get_new(struct ida *ida, int *p_id)
240 : : {
241 : 97 : return ida_get_new_above(ida, 0, p_id);
242 : : }
243 : :
244 : : void __init idr_init_cache(void);
245 : :
246 : : #endif /* __IDR_H__ */
|
