1 // SPDX-License-Identifier: GPL-2.0
2
3 /*
4 * Fast, unordered lists
5 *
6 * Supports add, remove, and iterate
7 *
8 * Underneath, they're a radix tree and an IDA, with a percpu buffer for slot
9 * allocation and freeing.
10 *
11 * This means that adding, removing, and iterating over items is lockless,
12 * except when refilling/emptying the percpu slot buffers.
13 */
14
15 #include "fast_list.h"
16
17 struct fast_list_pcpu {
18 u32 nr;
19 u32 entries[31];
20 };
21
fast_list_alloc_idx(struct fast_list * l,gfp_t gfp)22 static int fast_list_alloc_idx(struct fast_list *l, gfp_t gfp)
23 {
24 int idx = ida_alloc_range(&l->slots_allocated, 1, INT_MAX, gfp);
25 if (unlikely(idx < 0))
26 return 0;
27
28 if (unlikely(!genradix_ptr_alloc_inlined(&l->items, idx, gfp))) {
29 ida_free(&l->slots_allocated, idx);
30 return 0;
31 }
32
33 return idx;
34 }
35
36 /**
37 * fast_list_get_idx - get a slot in a fast_list
38 * @l: list to get slot in
39 *
40 * This allocates a slot in the radix tree without storing to it, so that we can
41 * take the potential memory allocation failure early and do the list add later
42 * when we can't take an allocation failure.
43 *
44 * Returns: positive integer on success, -ENOMEM on failure
45 */
fast_list_get_idx(struct fast_list * l)46 int fast_list_get_idx(struct fast_list *l)
47 {
48 unsigned long flags;
49 int idx;
50 retry:
51 local_irq_save(flags);
52 struct fast_list_pcpu *lp = this_cpu_ptr(l->buffer);
53
54 if (unlikely(!lp->nr)) {
55 u32 entries[16], nr = 0;
56
57 local_irq_restore(flags);
58 while (nr < ARRAY_SIZE(entries) &&
59 (idx = fast_list_alloc_idx(l, GFP_KERNEL)))
60 entries[nr++] = idx;
61 local_irq_save(flags);
62
63 lp = this_cpu_ptr(l->buffer);
64
65 while (nr && lp->nr < ARRAY_SIZE(lp->entries))
66 lp->entries[lp->nr++] = entries[--nr];
67
68 if (unlikely(nr)) {
69 local_irq_restore(flags);
70 while (nr)
71 ida_free(&l->slots_allocated, entries[--nr]);
72 goto retry;
73 }
74
75 if (unlikely(!lp->nr)) {
76 local_irq_restore(flags);
77 return -ENOMEM;
78 }
79 }
80
81 idx = lp->entries[--lp->nr];
82 local_irq_restore(flags);
83
84 return idx;
85 }
86
87 /**
88 * fast_list_add - add an item to a fast_list
89 * @l: list
90 * @item: item to add
91 *
92 * Allocates a slot in the radix tree and stores to it and then returns the
93 * slot index, which must be passed to fast_list_remove().
94 *
95 * Returns: positive integer on success, -ENOMEM on failure
96 */
fast_list_add(struct fast_list * l,void * item)97 int fast_list_add(struct fast_list *l, void *item)
98 {
99 int idx = fast_list_get_idx(l);
100 if (idx < 0)
101 return idx;
102
103 *genradix_ptr_inlined(&l->items, idx) = item;
104 return idx;
105 }
106
107 /**
108 * fast_list_remove - remove an item from a fast_list
109 * @l: list
110 * @idx: item's slot index
111 *
112 * Zeroes out the slot in the radix tree and frees the slot for future
113 * fast_list_add() operations.
114 */
fast_list_remove(struct fast_list * l,unsigned idx)115 void fast_list_remove(struct fast_list *l, unsigned idx)
116 {
117 u32 entries[16], nr = 0;
118 unsigned long flags;
119
120 if (!idx)
121 return;
122
123 *genradix_ptr_inlined(&l->items, idx) = NULL;
124
125 local_irq_save(flags);
126 struct fast_list_pcpu *lp = this_cpu_ptr(l->buffer);
127
128 if (unlikely(lp->nr == ARRAY_SIZE(lp->entries)))
129 while (nr < ARRAY_SIZE(entries))
130 entries[nr++] = lp->entries[--lp->nr];
131
132 lp->entries[lp->nr++] = idx;
133 local_irq_restore(flags);
134
135 if (unlikely(nr))
136 while (nr)
137 ida_free(&l->slots_allocated, entries[--nr]);
138 }
139
fast_list_exit(struct fast_list * l)140 void fast_list_exit(struct fast_list *l)
141 {
142 /* XXX: warn if list isn't empty */
143 free_percpu(l->buffer);
144 ida_destroy(&l->slots_allocated);
145 genradix_free(&l->items);
146 }
147
fast_list_init(struct fast_list * l)148 int fast_list_init(struct fast_list *l)
149 {
150 genradix_init(&l->items);
151 ida_init(&l->slots_allocated);
152 l->buffer = alloc_percpu(*l->buffer);
153 if (!l->buffer)
154 return -ENOMEM;
155 return 0;
156 }
157