This source file includes following definitions.
- parman_enlarge
- parman_shrink
- parman_prio_used
- parman_prio_first_item
- parman_prio_first_index
- parman_prio_last_item
- parman_prio_last_index
- parman_lsort_new_index_find
- __parman_prio_move
- parman_prio_shift_down
- parman_prio_shift_up
- parman_prio_item_remove
- parman_lsort_item_add
- parman_lsort_item_remove
- parman_create
- parman_destroy
- parman_prio_init
- parman_prio_fini
- parman_item_add
- parman_item_remove
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35 #include <linux/kernel.h>
36 #include <linux/module.h>
37 #include <linux/slab.h>
38 #include <linux/export.h>
39 #include <linux/list.h>
40 #include <linux/err.h>
41 #include <linux/parman.h>
42
43 struct parman_algo {
44 int (*item_add)(struct parman *parman, struct parman_prio *prio,
45 struct parman_item *item);
46 void (*item_remove)(struct parman *parman, struct parman_prio *prio,
47 struct parman_item *item);
48 };
49
50 struct parman {
51 const struct parman_ops *ops;
52 void *priv;
53 const struct parman_algo *algo;
54 unsigned long count;
55 unsigned long limit_count;
56 struct list_head prio_list;
57 };
58
59 static int parman_enlarge(struct parman *parman)
60 {
61 unsigned long new_count = parman->limit_count +
62 parman->ops->resize_step;
63 int err;
64
65 err = parman->ops->resize(parman->priv, new_count);
66 if (err)
67 return err;
68 parman->limit_count = new_count;
69 return 0;
70 }
71
72 static int parman_shrink(struct parman *parman)
73 {
74 unsigned long new_count = parman->limit_count -
75 parman->ops->resize_step;
76 int err;
77
78 if (new_count < parman->ops->base_count)
79 return 0;
80 err = parman->ops->resize(parman->priv, new_count);
81 if (err)
82 return err;
83 parman->limit_count = new_count;
84 return 0;
85 }
86
87 static bool parman_prio_used(struct parman_prio *prio)
88
89 {
90 return !list_empty(&prio->item_list);
91 }
92
93 static struct parman_item *parman_prio_first_item(struct parman_prio *prio)
94 {
95 return list_first_entry(&prio->item_list,
96 typeof(struct parman_item), list);
97 }
98
99 static unsigned long parman_prio_first_index(struct parman_prio *prio)
100 {
101 return parman_prio_first_item(prio)->index;
102 }
103
104 static struct parman_item *parman_prio_last_item(struct parman_prio *prio)
105 {
106 return list_last_entry(&prio->item_list,
107 typeof(struct parman_item), list);
108 }
109
110 static unsigned long parman_prio_last_index(struct parman_prio *prio)
111 {
112 return parman_prio_last_item(prio)->index;
113 }
114
115 static unsigned long parman_lsort_new_index_find(struct parman *parman,
116 struct parman_prio *prio)
117 {
118 list_for_each_entry_from_reverse(prio, &parman->prio_list, list) {
119 if (!parman_prio_used(prio))
120 continue;
121 return parman_prio_last_index(prio) + 1;
122 }
123 return 0;
124 }
125
126 static void __parman_prio_move(struct parman *parman, struct parman_prio *prio,
127 struct parman_item *item, unsigned long to_index,
128 unsigned long count)
129 {
130 parman->ops->move(parman->priv, item->index, to_index, count);
131 }
132
133 static void parman_prio_shift_down(struct parman *parman,
134 struct parman_prio *prio)
135 {
136 struct parman_item *item;
137 unsigned long to_index;
138
139 if (!parman_prio_used(prio))
140 return;
141 item = parman_prio_first_item(prio);
142 to_index = parman_prio_last_index(prio) + 1;
143 __parman_prio_move(parman, prio, item, to_index, 1);
144 list_move_tail(&item->list, &prio->item_list);
145 item->index = to_index;
146 }
147
148 static void parman_prio_shift_up(struct parman *parman,
149 struct parman_prio *prio)
150 {
151 struct parman_item *item;
152 unsigned long to_index;
153
154 if (!parman_prio_used(prio))
155 return;
156 item = parman_prio_last_item(prio);
157 to_index = parman_prio_first_index(prio) - 1;
158 __parman_prio_move(parman, prio, item, to_index, 1);
159 list_move(&item->list, &prio->item_list);
160 item->index = to_index;
161 }
162
163 static void parman_prio_item_remove(struct parman *parman,
164 struct parman_prio *prio,
165 struct parman_item *item)
166 {
167 struct parman_item *last_item;
168 unsigned long to_index;
169
170 last_item = parman_prio_last_item(prio);
171 if (last_item == item) {
172 list_del(&item->list);
173 return;
174 }
175 to_index = item->index;
176 __parman_prio_move(parman, prio, last_item, to_index, 1);
177 list_del(&last_item->list);
178 list_replace(&item->list, &last_item->list);
179 last_item->index = to_index;
180 }
181
182 static int parman_lsort_item_add(struct parman *parman,
183 struct parman_prio *prio,
184 struct parman_item *item)
185 {
186 struct parman_prio *prio2;
187 unsigned long new_index;
188 int err;
189
190 if (parman->count + 1 > parman->limit_count) {
191 err = parman_enlarge(parman);
192 if (err)
193 return err;
194 }
195
196 new_index = parman_lsort_new_index_find(parman, prio);
197 list_for_each_entry_reverse(prio2, &parman->prio_list, list) {
198 if (prio2 == prio)
199 break;
200 parman_prio_shift_down(parman, prio2);
201 }
202 item->index = new_index;
203 list_add_tail(&item->list, &prio->item_list);
204 parman->count++;
205 return 0;
206 }
207
208 static void parman_lsort_item_remove(struct parman *parman,
209 struct parman_prio *prio,
210 struct parman_item *item)
211 {
212 parman_prio_item_remove(parman, prio, item);
213 list_for_each_entry_continue(prio, &parman->prio_list, list)
214 parman_prio_shift_up(parman, prio);
215 parman->count--;
216 if (parman->limit_count - parman->count >= parman->ops->resize_step)
217 parman_shrink(parman);
218 }
219
220 static const struct parman_algo parman_lsort = {
221 .item_add = parman_lsort_item_add,
222 .item_remove = parman_lsort_item_remove,
223 };
224
225 static const struct parman_algo *parman_algos[] = {
226 &parman_lsort,
227 };
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268 struct parman *parman_create(const struct parman_ops *ops, void *priv)
269 {
270 struct parman *parman;
271
272 parman = kzalloc(sizeof(*parman), GFP_KERNEL);
273 if (!parman)
274 return NULL;
275 INIT_LIST_HEAD(&parman->prio_list);
276 parman->ops = ops;
277 parman->priv = priv;
278 parman->limit_count = ops->base_count;
279 parman->algo = parman_algos[ops->algo];
280 return parman;
281 }
282 EXPORT_SYMBOL(parman_create);
283
284
285
286
287
288
289
290 void parman_destroy(struct parman *parman)
291 {
292 WARN_ON(!list_empty(&parman->prio_list));
293 kfree(parman);
294 }
295 EXPORT_SYMBOL(parman_destroy);
296
297
298
299
300
301
302
303
304
305
306
307
308 void parman_prio_init(struct parman *parman, struct parman_prio *prio,
309 unsigned long priority)
310 {
311 struct parman_prio *prio2;
312 struct list_head *pos;
313
314 INIT_LIST_HEAD(&prio->item_list);
315 prio->priority = priority;
316
317
318 list_for_each(pos, &parman->prio_list) {
319 prio2 = list_entry(pos, typeof(*prio2), list);
320 if (prio2->priority > prio->priority)
321 break;
322 }
323 list_add_tail(&prio->list, pos);
324 }
325 EXPORT_SYMBOL(parman_prio_init);
326
327
328
329
330
331
332
333 void parman_prio_fini(struct parman_prio *prio)
334 {
335 WARN_ON(parman_prio_used(prio));
336 list_del(&prio->list);
337 }
338 EXPORT_SYMBOL(parman_prio_fini);
339
340
341
342
343
344
345
346
347
348
349
350
351
352 int parman_item_add(struct parman *parman, struct parman_prio *prio,
353 struct parman_item *item)
354 {
355 return parman->algo->item_add(parman, prio, item);
356 }
357 EXPORT_SYMBOL(parman_item_add);
358
359
360
361
362
363
364
365
366
367 void parman_item_remove(struct parman *parman, struct parman_prio *prio,
368 struct parman_item *item)
369 {
370 parman->algo->item_remove(parman, prio, item);
371 }
372 EXPORT_SYMBOL(parman_item_remove);
373
374 MODULE_LICENSE("Dual BSD/GPL");
375 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
376 MODULE_DESCRIPTION("Priority-based array manager");