Linux kernel mirror (for testing)
git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
tjh.dev
kernel
os
linux
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
30struct 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
39struct 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
76void *idr_find_slowpath(struct idr *idp, int id);
77void idr_preload(gfp_t gfp_mask);
78int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
79int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask);
80int idr_for_each(struct idr *idp,
81 int (*fn)(int id, void *p, void *data), void *data);
82void *idr_get_next(struct idr *idp, int *nextid);
83void *idr_replace(struct idr *idp, void *ptr, int id);
84void idr_remove(struct idr *idp, int id);
85void idr_free(struct idr *idp, int id);
86void idr_destroy(struct idr *idp);
87void 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 */
95static inline void idr_preload_end(void)
96{
97 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 */
112static inline void *idr_find(struct idr *idr, int id)
113{
114 struct idr_layer *hint = rcu_dereference_raw(idr->hint);
115
116 if (hint && (id & ~IDR_MASK) == hint->prefix)
117 return rcu_dereference_raw(hint->ary[id & IDR_MASK]);
118
119 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 */
139int __idr_pre_get(struct idr *idp, gfp_t gfp_mask);
140int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
141void __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 */
151static 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 */
166static 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 */
181static 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 */
193static 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
209struct ida_bitmap {
210 long nr_busy;
211 unsigned long bitmap[IDA_BITMAP_LONGS];
212};
213
214struct 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
222int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
223int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
224void ida_remove(struct ida *ida, int id);
225void ida_destroy(struct ida *ida);
226void ida_init(struct ida *ida);
227
228int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
229 gfp_t gfp_mask);
230void 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 */
239static inline int ida_get_new(struct ida *ida, int *p_id)
240{
241 return ida_get_new_above(ida, 0, p_id);
242}
243
244void __init idr_init_cache(void);
245
246#endif /* __IDR_H__ */