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 spinlock_t lock;
46};
47
48#define IDR_INIT(name) \
49{ \
50 .lock = __SPIN_LOCK_UNLOCKED(name.lock), \
51}
52#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
53
54/**
55 * DOC: idr sync
56 * idr synchronization (stolen from radix-tree.h)
57 *
58 * idr_find() is able to be called locklessly, using RCU. The caller must
59 * ensure calls to this function are made within rcu_read_lock() regions.
60 * Other readers (lock-free or otherwise) and modifications may be running
61 * concurrently.
62 *
63 * It is still required that the caller manage the synchronization and
64 * lifetimes of the items. So if RCU lock-free lookups are used, typically
65 * this would mean that the items have their own locks, or are amenable to
66 * lock-free access; and that the items are freed by RCU (or only freed after
67 * having been deleted from the idr tree *and* a synchronize_rcu() grace
68 * period).
69 */
70
71/*
72 * This is what we export.
73 */
74
75void *idr_find_slowpath(struct idr *idp, int id);
76void idr_preload(gfp_t gfp_mask);
77int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
78int idr_for_each(struct idr *idp,
79 int (*fn)(int id, void *p, void *data), void *data);
80void *idr_get_next(struct idr *idp, int *nextid);
81void *idr_replace(struct idr *idp, void *ptr, int id);
82void idr_remove(struct idr *idp, int id);
83void idr_free(struct idr *idp, int id);
84void idr_destroy(struct idr *idp);
85void idr_init(struct idr *idp);
86
87/**
88 * idr_preload_end - end preload section started with idr_preload()
89 *
90 * Each idr_preload() should be matched with an invocation of this
91 * function. See idr_preload() for details.
92 */
93static inline void idr_preload_end(void)
94{
95 preempt_enable();
96}
97
98/**
99 * idr_find - return pointer for given id
100 * @idr: idr handle
101 * @id: lookup key
102 *
103 * Return the pointer given the id it has been registered with. A %NULL
104 * return indicates that @id is not valid or you passed %NULL in
105 * idr_get_new().
106 *
107 * This function can be called under rcu_read_lock(), given that the leaf
108 * pointers lifetimes are correctly managed.
109 */
110static inline void *idr_find(struct idr *idr, int id)
111{
112 struct idr_layer *hint = rcu_dereference_raw(idr->hint);
113
114 if (hint && (id & ~IDR_MASK) == hint->prefix)
115 return rcu_dereference_raw(hint->ary[id & IDR_MASK]);
116
117 return idr_find_slowpath(idr, id);
118}
119
120/**
121 * idr_for_each_entry - iterate over an idr's elements of a given type
122 * @idp: idr handle
123 * @entry: the type * to use as cursor
124 * @id: id entry's key
125 */
126#define idr_for_each_entry(idp, entry, id) \
127 for (id = 0, entry = (typeof(entry))idr_get_next((idp), &(id)); \
128 entry != NULL; \
129 ++id, entry = (typeof(entry))idr_get_next((idp), &(id)))
130
131/*
132 * Don't use the following functions. These exist only to suppress
133 * deprecated warnings on EXPORT_SYMBOL()s.
134 */
135int __idr_pre_get(struct idr *idp, gfp_t gfp_mask);
136int __idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);
137void __idr_remove_all(struct idr *idp);
138
139/**
140 * idr_pre_get - reserve resources for idr allocation
141 * @idp: idr handle
142 * @gfp_mask: memory allocation flags
143 *
144 * Part of old alloc interface. This is going away. Use
145 * idr_preload[_end]() and idr_alloc() instead.
146 */
147static inline int __deprecated idr_pre_get(struct idr *idp, gfp_t gfp_mask)
148{
149 return __idr_pre_get(idp, gfp_mask);
150}
151
152/**
153 * idr_get_new_above - allocate new idr entry above or equal to a start id
154 * @idp: idr handle
155 * @ptr: pointer you want associated with the id
156 * @starting_id: id to start search at
157 * @id: pointer to the allocated handle
158 *
159 * Part of old alloc interface. This is going away. Use
160 * idr_preload[_end]() and idr_alloc() instead.
161 */
162static inline int __deprecated idr_get_new_above(struct idr *idp, void *ptr,
163 int starting_id, int *id)
164{
165 return __idr_get_new_above(idp, ptr, starting_id, id);
166}
167
168/**
169 * idr_get_new - allocate new idr entry
170 * @idp: idr handle
171 * @ptr: pointer you want associated with the id
172 * @id: pointer to the allocated handle
173 *
174 * Part of old alloc interface. This is going away. Use
175 * idr_preload[_end]() and idr_alloc() instead.
176 */
177static inline int __deprecated idr_get_new(struct idr *idp, void *ptr, int *id)
178{
179 return __idr_get_new_above(idp, ptr, 0, id);
180}
181
182/**
183 * idr_remove_all - remove all ids from the given idr tree
184 * @idp: idr handle
185 *
186 * If you're trying to destroy @idp, calling idr_destroy() is enough.
187 * This is going away. Don't use.
188 */
189static inline void __deprecated idr_remove_all(struct idr *idp)
190{
191 __idr_remove_all(idp);
192}
193
194/*
195 * IDA - IDR based id allocator, use when translation from id to
196 * pointer isn't necessary.
197 *
198 * IDA_BITMAP_LONGS is calculated to be one less to accommodate
199 * ida_bitmap->nr_busy so that the whole struct fits in 128 bytes.
200 */
201#define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */
202#define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long) - 1)
203#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
204
205struct ida_bitmap {
206 long nr_busy;
207 unsigned long bitmap[IDA_BITMAP_LONGS];
208};
209
210struct ida {
211 struct idr idr;
212 struct ida_bitmap *free_bitmap;
213};
214
215#define IDA_INIT(name) { .idr = IDR_INIT((name).idr), .free_bitmap = NULL, }
216#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
217
218int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
219int ida_get_new_above(struct ida *ida, int starting_id, int *p_id);
220void ida_remove(struct ida *ida, int id);
221void ida_destroy(struct ida *ida);
222void ida_init(struct ida *ida);
223
224int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
225 gfp_t gfp_mask);
226void ida_simple_remove(struct ida *ida, unsigned int id);
227
228/**
229 * ida_get_new - allocate new ID
230 * @ida: idr handle
231 * @p_id: pointer to the allocated handle
232 *
233 * Simple wrapper around ida_get_new_above() w/ @starting_id of zero.
234 */
235static inline int ida_get_new(struct ida *ida, int *p_id)
236{
237 return ida_get_new_above(ida, 0, p_id);
238}
239
240void __init idr_init_cache(void);
241
242#endif /* __IDR_H__ */