]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
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 | */ | |
f668ab1a LT |
11 | |
12 | #ifndef __IDR_H__ | |
13 | #define __IDR_H__ | |
14 | ||
0a835c4f MW |
15 | #include <linux/radix-tree.h> |
16 | #include <linux/gfp.h> | |
7ad3d4d8 | 17 | #include <linux/percpu.h> |
0a835c4f MW |
18 | |
19 | struct idr { | |
20 | struct radix_tree_root idr_rt; | |
21 | unsigned int idr_next; | |
22 | }; | |
1da177e4 | 23 | |
050a6b47 | 24 | /* |
0a835c4f MW |
25 | * The IDR API does not expose the tagging functionality of the radix tree |
26 | * to users. Use tag 0 to track whether a node has free space below it. | |
050a6b47 | 27 | */ |
0a835c4f | 28 | #define IDR_FREE 0 |
1da177e4 | 29 | |
0a835c4f MW |
30 | /* Set the IDR flag and the IDR_FREE tag */ |
31 | #define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT)) | |
1da177e4 | 32 | |
0a835c4f | 33 | #define IDR_INIT \ |
4106ecaf | 34 | { \ |
0a835c4f | 35 | .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \ |
1da177e4 | 36 | } |
0a835c4f | 37 | #define DEFINE_IDR(name) struct idr name = IDR_INIT |
1da177e4 | 38 | |
44430612 MW |
39 | /** |
40 | * idr_get_cursor - Return the current position of the cyclic allocator | |
41 | * @idr: idr handle | |
42 | * | |
43 | * The value returned is the value that will be next returned from | |
44 | * idr_alloc_cyclic() if it is free (otherwise the search will start from | |
45 | * this position). | |
46 | */ | |
0a835c4f | 47 | static inline unsigned int idr_get_cursor(const struct idr *idr) |
44430612 | 48 | { |
0a835c4f | 49 | return READ_ONCE(idr->idr_next); |
44430612 MW |
50 | } |
51 | ||
52 | /** | |
53 | * idr_set_cursor - Set the current position of the cyclic allocator | |
54 | * @idr: idr handle | |
55 | * @val: new position | |
56 | * | |
57 | * The next call to idr_alloc_cyclic() will return @val if it is free | |
58 | * (otherwise the search will start from this position). | |
59 | */ | |
60 | static inline void idr_set_cursor(struct idr *idr, unsigned int val) | |
61 | { | |
0a835c4f | 62 | WRITE_ONCE(idr->idr_next, val); |
44430612 MW |
63 | } |
64 | ||
f9c46d6e | 65 | /** |
56083ab1 | 66 | * DOC: idr sync |
f9c46d6e ND |
67 | * idr synchronization (stolen from radix-tree.h) |
68 | * | |
69 | * idr_find() is able to be called locklessly, using RCU. The caller must | |
70 | * ensure calls to this function are made within rcu_read_lock() regions. | |
71 | * Other readers (lock-free or otherwise) and modifications may be running | |
72 | * concurrently. | |
73 | * | |
74 | * It is still required that the caller manage the synchronization and | |
75 | * lifetimes of the items. So if RCU lock-free lookups are used, typically | |
76 | * this would mean that the items have their own locks, or are amenable to | |
77 | * lock-free access; and that the items are freed by RCU (or only freed after | |
78 | * having been deleted from the idr tree *and* a synchronize_rcu() grace | |
79 | * period). | |
80 | */ | |
81 | ||
d5c7409f | 82 | void idr_preload(gfp_t gfp_mask); |
0a835c4f MW |
83 | int idr_alloc(struct idr *, void *entry, int start, int end, gfp_t); |
84 | int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); | |
85 | int idr_for_each(const struct idr *, | |
96d7fa42 | 86 | int (*fn)(int id, void *p, void *data), void *data); |
0a835c4f MW |
87 | void *idr_get_next(struct idr *, int *nextid); |
88 | void *idr_replace(struct idr *, void *, int id); | |
89 | void idr_destroy(struct idr *); | |
90 | ||
d3e709e6 | 91 | static inline void *idr_remove(struct idr *idr, int id) |
0a835c4f | 92 | { |
d3e709e6 | 93 | return radix_tree_delete_item(&idr->idr_rt, id, NULL); |
0a835c4f MW |
94 | } |
95 | ||
96 | static inline void idr_init(struct idr *idr) | |
97 | { | |
98 | INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); | |
99 | idr->idr_next = 0; | |
100 | } | |
101 | ||
102 | static inline bool idr_is_empty(const struct idr *idr) | |
103 | { | |
104 | return radix_tree_empty(&idr->idr_rt) && | |
105 | radix_tree_tagged(&idr->idr_rt, IDR_FREE); | |
106 | } | |
f668ab1a | 107 | |
d5c7409f TH |
108 | /** |
109 | * idr_preload_end - end preload section started with idr_preload() | |
110 | * | |
111 | * Each idr_preload() should be matched with an invocation of this | |
112 | * function. See idr_preload() for details. | |
113 | */ | |
114 | static inline void idr_preload_end(void) | |
115 | { | |
116 | preempt_enable(); | |
117 | } | |
118 | ||
0ffc2a9c TH |
119 | /** |
120 | * idr_find - return pointer for given id | |
5857f70c | 121 | * @idr: idr handle |
0ffc2a9c TH |
122 | * @id: lookup key |
123 | * | |
124 | * Return the pointer given the id it has been registered with. A %NULL | |
125 | * return indicates that @id is not valid or you passed %NULL in | |
126 | * idr_get_new(). | |
127 | * | |
128 | * This function can be called under rcu_read_lock(), given that the leaf | |
129 | * pointers lifetimes are correctly managed. | |
130 | */ | |
0a835c4f | 131 | static inline void *idr_find(const struct idr *idr, int id) |
0ffc2a9c | 132 | { |
0a835c4f | 133 | return radix_tree_lookup(&idr->idr_rt, id); |
0ffc2a9c TH |
134 | } |
135 | ||
49038ef4 TH |
136 | /** |
137 | * idr_for_each_entry - iterate over an idr's elements of a given type | |
0a835c4f | 138 | * @idr: idr handle |
49038ef4 TH |
139 | * @entry: the type * to use as cursor |
140 | * @id: id entry's key | |
b949be58 GS |
141 | * |
142 | * @entry and @id do not need to be initialized before the loop, and | |
143 | * after normal terminatinon @entry is left with the value NULL. This | |
144 | * is convenient for a "not found" value. | |
49038ef4 | 145 | */ |
0a835c4f MW |
146 | #define idr_for_each_entry(idr, entry, id) \ |
147 | for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) | |
49038ef4 | 148 | |
a55bbd37 | 149 | /** |
0a835c4f MW |
150 | * idr_for_each_entry_continue - continue iteration over an idr's elements of a given type |
151 | * @idr: idr handle | |
a55bbd37 AG |
152 | * @entry: the type * to use as cursor |
153 | * @id: id entry's key | |
154 | * | |
155 | * Continue to iterate over list of given type, continuing after | |
156 | * the current position. | |
157 | */ | |
0a835c4f MW |
158 | #define idr_for_each_entry_continue(idr, entry, id) \ |
159 | for ((entry) = idr_get_next((idr), &(id)); \ | |
a55bbd37 | 160 | entry; \ |
0a835c4f | 161 | ++id, (entry) = idr_get_next((idr), &(id))) |
a55bbd37 | 162 | |
72dba584 TH |
163 | /* |
164 | * IDA - IDR based id allocator, use when translation from id to | |
165 | * pointer isn't necessary. | |
166 | */ | |
167 | #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ | |
0a835c4f | 168 | #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) |
ed9f524a | 169 | #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) |
72dba584 TH |
170 | |
171 | struct ida_bitmap { | |
72dba584 TH |
172 | unsigned long bitmap[IDA_BITMAP_LONGS]; |
173 | }; | |
174 | ||
7ad3d4d8 MW |
175 | DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap); |
176 | ||
72dba584 | 177 | struct ida { |
0a835c4f | 178 | struct radix_tree_root ida_rt; |
72dba584 TH |
179 | }; |
180 | ||
0a835c4f MW |
181 | #define IDA_INIT { \ |
182 | .ida_rt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ | |
183 | } | |
184 | #define DEFINE_IDA(name) struct ida name = IDA_INIT | |
72dba584 TH |
185 | |
186 | int ida_pre_get(struct ida *ida, gfp_t gfp_mask); | |
187 | int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); | |
72dba584 TH |
188 | void ida_remove(struct ida *ida, int id); |
189 | void ida_destroy(struct ida *ida); | |
72dba584 | 190 | |
88eca020 RR |
191 | int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, |
192 | gfp_t gfp_mask); | |
193 | void ida_simple_remove(struct ida *ida, unsigned int id); | |
194 | ||
0a835c4f MW |
195 | static inline void ida_init(struct ida *ida) |
196 | { | |
197 | INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); | |
0a835c4f MW |
198 | } |
199 | ||
9749f30f | 200 | /** |
49038ef4 TH |
201 | * ida_get_new - allocate new ID |
202 | * @ida: idr handle | |
203 | * @p_id: pointer to the allocated handle | |
204 | * | |
205 | * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. | |
9749f30f | 206 | */ |
49038ef4 TH |
207 | static inline int ida_get_new(struct ida *ida, int *p_id) |
208 | { | |
209 | return ida_get_new_above(ida, 0, p_id); | |
210 | } | |
211 | ||
0a835c4f | 212 | static inline bool ida_is_empty(const struct ida *ida) |
99c49407 | 213 | { |
0a835c4f | 214 | return radix_tree_empty(&ida->ida_rt); |
99c49407 | 215 | } |
f668ab1a | 216 | #endif /* __IDR_H__ */ |