Skip to content

Commit 6ce711f

Browse files
author
Matthew Wilcox
committed
idr: Make 1-based IDRs more efficient
About 20% of the IDR users in the kernel want the allocated IDs to start at 1. The implementation currently searches all the way down the left hand side of the tree, finds no free ID other than ID 0, walks all the way back up, and then all the way down again. This patch 'rebases' the ID so we fill the entire radix tree, rather than leave a gap at 0. Chris Wilson says: "I did the quick hack of allocating index 0 of the idr and that eradicated idr_get_free() from being at the top of the profiles for the many-object stress tests. This improvement will be much appreciated." Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
1 parent 72fd6c7 commit 6ce711f

File tree

3 files changed

+103
-40
lines changed

3 files changed

+103
-40
lines changed

‎include/linux/idr.h

Lines changed: 37 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818

1919
struct idr {
2020
struct radix_tree_root idr_rt;
21+
unsigned int idr_base;
2122
unsigned int idr_next;
2223
};
2324

@@ -30,12 +31,20 @@ struct idr {
3031
/* Set the IDR flag and the IDR_FREE tag */
3132
#define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT))
3233

33-
#define IDR_INIT \
34-
{ \
35-
.idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \
34+
#define IDR_INIT_BASE(base) { \
35+
.idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER), \
36+
.idr_base = (base), \
37+
.idr_next = 0, \
3638
}
3739
#define DEFINE_IDR(name) struct idr name = IDR_INIT
3840

41+
/**
42+
* IDR_INIT() - Initialise an IDR.
43+
*
44+
* A freshly-initialised IDR contains no IDs.
45+
*/
46+
#define IDR_INIT IDR_INIT_BASE(0)
47+
3948
/**
4049
* idr_get_cursor - Return the current position of the cyclic allocator
4150
* @idr: idr handle
@@ -81,26 +90,44 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val)
8190

8291
void idr_preload(gfp_t gfp_mask);
8392

84-
int idr_alloc(struct idr *, void *, int start, int end, gfp_t);
85-
int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *nextid,
93+
int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t);
94+
int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id,
8695
unsigned long max, gfp_t);
87-
int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t);
96+
int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t);
97+
void *idr_remove(struct idr *, unsigned long id);
98+
void *idr_find(const struct idr *, unsigned long id);
8899
int idr_for_each(const struct idr *,
89100
int (*fn)(int id, void *p, void *data), void *data);
90101
void *idr_get_next(struct idr *, int *nextid);
91102
void *idr_get_next_ul(struct idr *, unsigned long *nextid);
92103
void *idr_replace(struct idr *, void *, unsigned long id);
93104
void idr_destroy(struct idr *);
94105

95-
static inline void *idr_remove(struct idr *idr, unsigned long id)
106+
/**
107+
* idr_init_base() - Initialise an IDR.
108+
* @idr: IDR handle.
109+
* @base: The base value for the IDR.
110+
*
111+
* This variation of idr_init() creates an IDR which will allocate IDs
112+
* starting at %base.
113+
*/
114+
static inline void idr_init_base(struct idr *idr, int base)
96115
{
97-
return radix_tree_delete_item(&idr->idr_rt, id, NULL);
116+
INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
117+
idr->idr_base = base;
118+
idr->idr_next = 0;
98119
}
99120

121+
/**
122+
* idr_init() - Initialise an IDR.
123+
* @idr: IDR handle.
124+
*
125+
* Initialise a dynamically allocated IDR. To initialise a
126+
* statically allocated IDR, use DEFINE_IDR().
127+
*/
100128
static inline void idr_init(struct idr *idr)
101129
{
102-
INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
103-
idr->idr_next = 0;
130+
idr_init_base(idr, 0);
104131
}
105132

106133
static inline bool idr_is_empty(const struct idr *idr)
@@ -120,25 +147,6 @@ static inline void idr_preload_end(void)
120147
preempt_enable();
121148
}
122149

123-
/**
124-
* idr_find() - Return pointer for given ID.
125-
* @idr: IDR handle.
126-
* @id: Pointer ID.
127-
*
128-
* Looks up the pointer associated with this ID. A %NULL pointer may
129-
* indicate that @id is not allocated or that the %NULL pointer was
130-
* associated with this ID.
131-
*
132-
* This function can be called under rcu_read_lock(), given that the leaf
133-
* pointers lifetimes are correctly managed.
134-
*
135-
* Return: The pointer associated with this ID.
136-
*/
137-
static inline void *idr_find(const struct idr *idr, unsigned long id)
138-
{
139-
return radix_tree_lookup(&idr->idr_rt, id);
140-
}
141-
142150
/**
143151
* idr_for_each_entry() - Iterate over an IDR's elements of a given type.
144152
* @idr: IDR handle.

‎lib/idr.c

Lines changed: 61 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -36,18 +36,21 @@ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid,
3636
{
3737
struct radix_tree_iter iter;
3838
void __rcu **slot;
39+
int base = idr->idr_base;
40+
int id = *nextid;
3941

4042
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
4143
return -EINVAL;
4244
if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR)))
4345
idr->idr_rt.gfp_mask |= IDR_RT_MARKER;
4446

45-
radix_tree_iter_init(&iter, *nextid);
46-
slot = idr_get_free(&idr->idr_rt, &iter, gfp, max);
47+
id = (id < base) ? 0 : id - base;
48+
radix_tree_iter_init(&iter, id);
49+
slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base);
4750
if (IS_ERR(slot))
4851
return PTR_ERR(slot);
4952

50-
*nextid = iter.index;
53+
*nextid = iter.index + base;
5154
/* there is a memory barrier inside radix_tree_iter_replace() */
5255
radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr);
5356
radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE);
@@ -135,6 +138,46 @@ int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp)
135138
}
136139
EXPORT_SYMBOL(idr_alloc_cyclic);
137140

141+
/**
142+
* idr_remove() - Remove an ID from the IDR.
143+
* @idr: IDR handle.
144+
* @id: Pointer ID.
145+
*
146+
* Removes this ID from the IDR. If the ID was not previously in the IDR,
147+
* this function returns %NULL.
148+
*
149+
* Since this function modifies the IDR, the caller should provide their
150+
* own locking to ensure that concurrent modification of the same IDR is
151+
* not possible.
152+
*
153+
* Return: The pointer formerly associated with this ID.
154+
*/
155+
void *idr_remove(struct idr *idr, unsigned long id)
156+
{
157+
return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
158+
}
159+
EXPORT_SYMBOL_GPL(idr_remove);
160+
161+
/**
162+
* idr_find() - Return pointer for given ID.
163+
* @idr: IDR handle.
164+
* @id: Pointer ID.
165+
*
166+
* Looks up the pointer associated with this ID. A %NULL pointer may
167+
* indicate that @id is not allocated or that the %NULL pointer was
168+
* associated with this ID.
169+
*
170+
* This function can be called under rcu_read_lock(), given that the leaf
171+
* pointers lifetimes are correctly managed.
172+
*
173+
* Return: The pointer associated with this ID.
174+
*/
175+
void *idr_find(const struct idr *idr, unsigned long id)
176+
{
177+
return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
178+
}
179+
EXPORT_SYMBOL_GPL(idr_find);
180+
138181
/**
139182
* idr_for_each() - Iterate through all stored pointers.
140183
* @idr: IDR handle.
@@ -157,13 +200,14 @@ int idr_for_each(const struct idr *idr,
157200
{
158201
struct radix_tree_iter iter;
159202
void __rcu **slot;
203+
int base = idr->idr_base;
160204

161205
radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
162206
int ret;
163207

164208
if (WARN_ON_ONCE(iter.index > INT_MAX))
165209
break;
166-
ret = fn(iter.index, rcu_dereference_raw(*slot), data);
210+
ret = fn(iter.index + base, rcu_dereference_raw(*slot), data);
167211
if (ret)
168212
return ret;
169213
}
@@ -186,15 +230,19 @@ void *idr_get_next(struct idr *idr, int *nextid)
186230
{
187231
struct radix_tree_iter iter;
188232
void __rcu **slot;
233+
int base = idr->idr_base;
234+
int id = *nextid;
189235

190-
slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
236+
id = (id < base) ? 0 : id - base;
237+
slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
191238
if (!slot)
192239
return NULL;
240+
id = iter.index + base;
193241

194-
if (WARN_ON_ONCE(iter.index > INT_MAX))
242+
if (WARN_ON_ONCE(id > INT_MAX))
195243
return NULL;
196244

197-
*nextid = iter.index;
245+
*nextid = id;
198246
return rcu_dereference_raw(*slot);
199247
}
200248
EXPORT_SYMBOL(idr_get_next);
@@ -213,12 +261,15 @@ void *idr_get_next_ul(struct idr *idr, unsigned long *nextid)
213261
{
214262
struct radix_tree_iter iter;
215263
void __rcu **slot;
264+
unsigned long base = idr->idr_base;
265+
unsigned long id = *nextid;
216266

217-
slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid);
267+
id = (id < base) ? 0 : id - base;
268+
slot = radix_tree_iter_find(&idr->idr_rt, &iter, id);
218269
if (!slot)
219270
return NULL;
220271

221-
*nextid = iter.index;
272+
*nextid = iter.index + base;
222273
return rcu_dereference_raw(*slot);
223274
}
224275
EXPORT_SYMBOL(idr_get_next_ul);
@@ -245,6 +296,7 @@ void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
245296

246297
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr)))
247298
return ERR_PTR(-EINVAL);
299+
id -= idr->idr_base;
248300

249301
entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot);
250302
if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE))

‎tools/testing/radix-tree/idr-test.c

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -153,11 +153,12 @@ void idr_nowait_test(void)
153153
idr_destroy(&idr);
154154
}
155155

156-
void idr_get_next_test(void)
156+
void idr_get_next_test(int base)
157157
{
158158
unsigned long i;
159159
int nextid;
160160
DEFINE_IDR(idr);
161+
idr_init_base(&idr, base);
161162

162163
int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
163164

@@ -244,7 +245,9 @@ void idr_checks(void)
244245
idr_alloc_test();
245246
idr_null_test();
246247
idr_nowait_test();
247-
idr_get_next_test();
248+
idr_get_next_test(0);
249+
idr_get_next_test(1);
250+
idr_get_next_test(4);
248251
}
249252

250253
/*

0 commit comments

Comments
 (0)