On Wed, Mar 21, 2018 at 07:42:38PM +0300, Kirill Tkhai wrote:
> On 21.03.2018 19:20, Matthew Wilcox wrote:
> >> Sound great, thanks for explaining this. The big problem I see is
> >> that IDA/IDR add primitives allocate memory, while they will be used
> >> in the places, where they mustn't fail. There is list_lru_add(), and
> >> it's called unconditionally in current kernel code. The patchset makes
> >> the bitmap be populated in this function. So, we can't use IDR there.
> >
> > Maybe we can use GFP_NOFAIL here. They're small allocations, so we're
> > only asking for single-page allocations to not fail, which shouldn't
> > put too much strain on the VM.
>
> Oh. I'm not sure about this. Even if each allocation is small, there is
> theoretically possible a situation, when many lists will want to add first
> element. list_lru_add() is called from iput() for example.
I see. Maybe we could solve this with an IDA_NO_SHRINK flag and an
ida_resize(ida, max); call.
You'll also want something like this:
diff --git a/include/linux/idr.h b/include/linux/idr.h
index 0f650b90ced0..ee7185354fb2 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -273,6 +273,22 @@ static inline void ida_init(struct ida *ida)
ida_alloc_range(ida, start, (end) - 1, gfp)
#define ida_simple_remove(ida, id) ida_free(ida, id)
+int ida_find(struct ida *, unsigned int id);
+
+/**
+ * ida_for_each() - Iterate over all allocated IDs.
+ * @ida: IDA handle.
+ * @id: Loop cursor.
+ *
+ * For each iteration of this loop, @id will be set to an allocated ID.
+ * No locks are held across the body of the loop, so you can call ida_free()
+ * if you want or adjust @id to skip IDs or re-process earlier IDs.
+ *
+ * On successful loop exit, @id will be less than 0.
+ */
+#define ida_for_each(ida, i) \
+ for (i = ida_find(ida, 0); i >= 0; i = ida_find(ida, i + 1))
+
/**
* ida_get_new - allocate new ID
* @ida: idr handle
diff --git a/lib/idr.c b/lib/idr.c
index fab3763e8c2a..ba9fae7eb2f5 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -612,3 +612,54 @@ void ida_free(struct ida *ida, unsigned int id)
spin_unlock_irqrestore(&simple_ida_lock, flags);
}
EXPORT_SYMBOL(ida_free);
+
+/**
+ * ida_find() - Find an allocated ID.
+ * @ida: IDA handle.
+ * @id: Minimum ID to return.
+ *
+ * Context: Any context.
+ * Return: An ID which is at least as large as @id or %-ENOSPC if @id is
+ * higher than any allocated ID.
+ */
+int ida_find(struct ida *ida, unsigned int id)
+{
+ unsigned long flags;
+ unsigned long index = id / IDA_BITMAP_BITS;
+ unsigned bit = id % IDA_BITMAP_BITS;
+ struct ida_bitmap *bitmap;
+ struct radix_tree_iter iter;
+ void __rcu **slot;
+ int ret = -ENOSPC;
+
+ spin_lock_irqsave(&simple_ida_lock, flags);
+advance:
+ slot = radix_tree_iter_find(&ida->ida_rt, &iter, index);
+ if (!slot)
+ goto unlock;
+ bitmap = rcu_dereference_raw(*slot);
+ if (radix_tree_exception(bitmap)) {
+ if (bit < (BITS_PER_LONG - RADIX_TREE_EXCEPTIONAL_SHIFT)) {
+ unsigned long bits = (unsigned long)bitmap;
+
+ bits >>= bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
+ if (bits) {
+ bit += __ffs(bits);
+ goto found;
+ }
+ }
+ } else {
+ bit = find_next_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit);
+ if (bit < IDA_BITMAP_BITS)
+ goto found;
+ }
+ bit = 0;
+ index++;
+ goto advance;
+found:
+ ret = iter.index * IDA_BITMAP_BITS + bit;
+unlock:
+ spin_unlock_irqrestore(&simple_ida_lock, flags);
+ return ret;
+}
+EXPORT_SYMBOL(ida_find);
diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c
index 6c645eb77d42..a9b5a33a4ef3 100644
--- a/tools/testing/radix-tree/idr-test.c
+++ b/tools/testing/radix-tree/idr-test.c
@@ -358,8 +358,12 @@ void ida_check_conv(void)
assert(ida_pre_get(&ida, GFP_KERNEL));
assert(!ida_get_new_above(&ida, i + 1, &id));
assert(id == i + 1);
+ ida_for_each(&ida, id)
+ BUG_ON(id != (i + 1));
assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id));
assert(id == i + BITS_PER_LONG);
+ ida_for_each(&ida, id)
+ BUG_ON((id != (i + 1)) && (id != (i + BITS_PER_LONG)));
ida_remove(&ida, i + 1);
ida_remove(&ida, i + BITS_PER_LONG);
assert(ida_is_empty(&ida));
@@ -484,7 +488,7 @@ void ida_simple_get_remove_test(void)
void ida_checks(void)
{
DEFINE_IDA(ida);
- int id;
+ int id, id2;
unsigned long i;
radix_tree_cpu_dead(1);
@@ -496,8 +500,22 @@ void ida_checks(void)
assert(id == i);
}
+ id2 = 0;
+ ida_for_each(&ida, id) {
+ BUG_ON(id != id2++);
+ }
+ BUG_ON(id >= 0);
+ BUG_ON(id2 != 10000);
+
ida_remove(&ida, 20);
ida_remove(&ida, 21);
+ id2 = 0;
+ ida_for_each(&ida, id) {
+ if (id != id2++) {
+ BUG_ON(id != 22 || id2 != 21);
+ id2 = 23;
+ }
+ }
for (i = 0; i < 3; i++) {
assert(ida_pre_get(&ida, GFP_KERNEL));
assert(!ida_get_new(&ida, &id));
