1 | // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0 |
2 | /* Copyright (c) 2018 Mellanox Technologies. All rights reserved */ |
3 | |
4 | #include <linux/module.h> |
5 | #include <linux/slab.h> |
6 | #include <linux/rhashtable.h> |
7 | #include <linux/idr.h> |
8 | #include <linux/list.h> |
9 | #include <linux/sort.h> |
10 | #include <linux/objagg.h> |
11 | |
12 | #define CREATE_TRACE_POINTS |
13 | #include <trace/events/objagg.h> |
14 | |
15 | struct objagg_hints { |
16 | struct rhashtable node_ht; |
17 | struct rhashtable_params ht_params; |
18 | struct list_head node_list; |
19 | unsigned int node_count; |
20 | unsigned int root_count; |
21 | unsigned int refcount; |
22 | const struct objagg_ops *ops; |
23 | }; |
24 | |
25 | struct objagg_hints_node { |
26 | struct rhash_head ht_node; /* member of objagg_hints->node_ht */ |
27 | struct list_head list; /* member of objagg_hints->node_list */ |
28 | struct objagg_hints_node *parent; |
29 | unsigned int root_id; |
30 | struct objagg_obj_stats_info stats_info; |
31 | unsigned long obj[]; |
32 | }; |
33 | |
34 | static struct objagg_hints_node * |
35 | objagg_hints_lookup(struct objagg_hints *objagg_hints, void *obj) |
36 | { |
37 | if (!objagg_hints) |
38 | return NULL; |
39 | return rhashtable_lookup_fast(ht: &objagg_hints->node_ht, key: obj, |
40 | params: objagg_hints->ht_params); |
41 | } |
42 | |
43 | struct objagg { |
44 | const struct objagg_ops *ops; |
45 | void *priv; |
46 | struct rhashtable obj_ht; |
47 | struct rhashtable_params ht_params; |
48 | struct list_head obj_list; |
49 | unsigned int obj_count; |
50 | struct ida root_ida; |
51 | struct objagg_hints *hints; |
52 | }; |
53 | |
54 | struct objagg_obj { |
55 | struct rhash_head ht_node; /* member of objagg->obj_ht */ |
56 | struct list_head list; /* member of objagg->obj_list */ |
57 | struct objagg_obj *parent; /* if the object is nested, this |
58 | * holds pointer to parent, otherwise NULL |
59 | */ |
60 | union { |
61 | void *delta_priv; /* user delta private */ |
62 | void *root_priv; /* user root private */ |
63 | }; |
64 | unsigned int root_id; |
65 | unsigned int refcount; /* counts number of users of this object |
66 | * including nested objects |
67 | */ |
68 | struct objagg_obj_stats stats; |
69 | unsigned long obj[]; |
70 | }; |
71 | |
72 | static unsigned int objagg_obj_ref_inc(struct objagg_obj *objagg_obj) |
73 | { |
74 | return ++objagg_obj->refcount; |
75 | } |
76 | |
77 | static unsigned int objagg_obj_ref_dec(struct objagg_obj *objagg_obj) |
78 | { |
79 | return --objagg_obj->refcount; |
80 | } |
81 | |
82 | static void objagg_obj_stats_inc(struct objagg_obj *objagg_obj) |
83 | { |
84 | objagg_obj->stats.user_count++; |
85 | objagg_obj->stats.delta_user_count++; |
86 | if (objagg_obj->parent) |
87 | objagg_obj->parent->stats.delta_user_count++; |
88 | } |
89 | |
90 | static void objagg_obj_stats_dec(struct objagg_obj *objagg_obj) |
91 | { |
92 | objagg_obj->stats.user_count--; |
93 | objagg_obj->stats.delta_user_count--; |
94 | if (objagg_obj->parent) |
95 | objagg_obj->parent->stats.delta_user_count--; |
96 | } |
97 | |
98 | static bool objagg_obj_is_root(const struct objagg_obj *objagg_obj) |
99 | { |
100 | /* Nesting is not supported, so we can use ->parent |
101 | * to figure out if the object is root. |
102 | */ |
103 | return !objagg_obj->parent; |
104 | } |
105 | |
106 | /** |
107 | * objagg_obj_root_priv - obtains root private for an object |
108 | * @objagg_obj: objagg object instance |
109 | * |
110 | * Note: all locking must be provided by the caller. |
111 | * |
112 | * Either the object is root itself when the private is returned |
113 | * directly, or the parent is root and its private is returned |
114 | * instead. |
115 | * |
116 | * Returns a user private root pointer. |
117 | */ |
118 | const void *objagg_obj_root_priv(const struct objagg_obj *objagg_obj) |
119 | { |
120 | if (objagg_obj_is_root(objagg_obj)) |
121 | return objagg_obj->root_priv; |
122 | WARN_ON(!objagg_obj_is_root(objagg_obj->parent)); |
123 | return objagg_obj->parent->root_priv; |
124 | } |
125 | EXPORT_SYMBOL(objagg_obj_root_priv); |
126 | |
127 | /** |
128 | * objagg_obj_delta_priv - obtains delta private for an object |
129 | * @objagg_obj: objagg object instance |
130 | * |
131 | * Note: all locking must be provided by the caller. |
132 | * |
133 | * Returns user private delta pointer or NULL in case the passed |
134 | * object is root. |
135 | */ |
136 | const void *objagg_obj_delta_priv(const struct objagg_obj *objagg_obj) |
137 | { |
138 | if (objagg_obj_is_root(objagg_obj)) |
139 | return NULL; |
140 | return objagg_obj->delta_priv; |
141 | } |
142 | EXPORT_SYMBOL(objagg_obj_delta_priv); |
143 | |
144 | /** |
145 | * objagg_obj_raw - obtains object user private pointer |
146 | * @objagg_obj: objagg object instance |
147 | * |
148 | * Note: all locking must be provided by the caller. |
149 | * |
150 | * Returns user private pointer as was passed to objagg_obj_get() by "obj" arg. |
151 | */ |
152 | const void *objagg_obj_raw(const struct objagg_obj *objagg_obj) |
153 | { |
154 | return objagg_obj->obj; |
155 | } |
156 | EXPORT_SYMBOL(objagg_obj_raw); |
157 | |
158 | static struct objagg_obj *objagg_obj_lookup(struct objagg *objagg, void *obj) |
159 | { |
160 | return rhashtable_lookup_fast(ht: &objagg->obj_ht, key: obj, params: objagg->ht_params); |
161 | } |
162 | |
163 | static int objagg_obj_parent_assign(struct objagg *objagg, |
164 | struct objagg_obj *objagg_obj, |
165 | struct objagg_obj *parent, |
166 | bool take_parent_ref) |
167 | { |
168 | void *delta_priv; |
169 | |
170 | delta_priv = objagg->ops->delta_create(objagg->priv, parent->obj, |
171 | objagg_obj->obj); |
172 | if (IS_ERR(ptr: delta_priv)) |
173 | return PTR_ERR(ptr: delta_priv); |
174 | |
175 | /* User returned a delta private, that means that |
176 | * our object can be aggregated into the parent. |
177 | */ |
178 | objagg_obj->parent = parent; |
179 | objagg_obj->delta_priv = delta_priv; |
180 | if (take_parent_ref) |
181 | objagg_obj_ref_inc(objagg_obj: objagg_obj->parent); |
182 | trace_objagg_obj_parent_assign(objagg, obj: objagg_obj, |
183 | parent, |
184 | parent_refcount: parent->refcount); |
185 | return 0; |
186 | } |
187 | |
188 | static int objagg_obj_parent_lookup_assign(struct objagg *objagg, |
189 | struct objagg_obj *objagg_obj) |
190 | { |
191 | struct objagg_obj *objagg_obj_cur; |
192 | int err; |
193 | |
194 | list_for_each_entry(objagg_obj_cur, &objagg->obj_list, list) { |
195 | /* Nesting is not supported. In case the object |
196 | * is not root, it cannot be assigned as parent. |
197 | */ |
198 | if (!objagg_obj_is_root(objagg_obj: objagg_obj_cur)) |
199 | continue; |
200 | err = objagg_obj_parent_assign(objagg, objagg_obj, |
201 | parent: objagg_obj_cur, take_parent_ref: true); |
202 | if (!err) |
203 | return 0; |
204 | } |
205 | return -ENOENT; |
206 | } |
207 | |
208 | static void __objagg_obj_put(struct objagg *objagg, |
209 | struct objagg_obj *objagg_obj); |
210 | |
211 | static void objagg_obj_parent_unassign(struct objagg *objagg, |
212 | struct objagg_obj *objagg_obj) |
213 | { |
214 | trace_objagg_obj_parent_unassign(objagg, obj: objagg_obj, |
215 | parent: objagg_obj->parent, |
216 | parent_refcount: objagg_obj->parent->refcount); |
217 | objagg->ops->delta_destroy(objagg->priv, objagg_obj->delta_priv); |
218 | __objagg_obj_put(objagg, objagg_obj: objagg_obj->parent); |
219 | } |
220 | |
221 | static int objagg_obj_root_id_alloc(struct objagg *objagg, |
222 | struct objagg_obj *objagg_obj, |
223 | struct objagg_hints_node *hnode) |
224 | { |
225 | unsigned int min, max; |
226 | int root_id; |
227 | |
228 | /* In case there are no hints available, the root id is invalid. */ |
229 | if (!objagg->hints) { |
230 | objagg_obj->root_id = OBJAGG_OBJ_ROOT_ID_INVALID; |
231 | return 0; |
232 | } |
233 | |
234 | if (hnode) { |
235 | min = hnode->root_id; |
236 | max = hnode->root_id; |
237 | } else { |
238 | /* For objects with no hint, start after the last |
239 | * hinted root_id. |
240 | */ |
241 | min = objagg->hints->root_count; |
242 | max = ~0; |
243 | } |
244 | |
245 | root_id = ida_alloc_range(&objagg->root_ida, min, max, GFP_KERNEL); |
246 | |
247 | if (root_id < 0) |
248 | return root_id; |
249 | objagg_obj->root_id = root_id; |
250 | return 0; |
251 | } |
252 | |
253 | static void objagg_obj_root_id_free(struct objagg *objagg, |
254 | struct objagg_obj *objagg_obj) |
255 | { |
256 | if (!objagg->hints) |
257 | return; |
258 | ida_free(&objagg->root_ida, id: objagg_obj->root_id); |
259 | } |
260 | |
261 | static int objagg_obj_root_create(struct objagg *objagg, |
262 | struct objagg_obj *objagg_obj, |
263 | struct objagg_hints_node *hnode) |
264 | { |
265 | int err; |
266 | |
267 | err = objagg_obj_root_id_alloc(objagg, objagg_obj, hnode); |
268 | if (err) |
269 | return err; |
270 | objagg_obj->root_priv = objagg->ops->root_create(objagg->priv, |
271 | objagg_obj->obj, |
272 | objagg_obj->root_id); |
273 | if (IS_ERR(ptr: objagg_obj->root_priv)) { |
274 | err = PTR_ERR(ptr: objagg_obj->root_priv); |
275 | goto err_root_create; |
276 | } |
277 | trace_objagg_obj_root_create(objagg, obj: objagg_obj); |
278 | return 0; |
279 | |
280 | err_root_create: |
281 | objagg_obj_root_id_free(objagg, objagg_obj); |
282 | return err; |
283 | } |
284 | |
285 | static void objagg_obj_root_destroy(struct objagg *objagg, |
286 | struct objagg_obj *objagg_obj) |
287 | { |
288 | trace_objagg_obj_root_destroy(objagg, obj: objagg_obj); |
289 | objagg->ops->root_destroy(objagg->priv, objagg_obj->root_priv); |
290 | objagg_obj_root_id_free(objagg, objagg_obj); |
291 | } |
292 | |
293 | static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj); |
294 | |
295 | static int objagg_obj_init_with_hints(struct objagg *objagg, |
296 | struct objagg_obj *objagg_obj, |
297 | bool *hint_found) |
298 | { |
299 | struct objagg_hints_node *hnode; |
300 | struct objagg_obj *parent; |
301 | int err; |
302 | |
303 | hnode = objagg_hints_lookup(objagg_hints: objagg->hints, obj: objagg_obj->obj); |
304 | if (!hnode) { |
305 | *hint_found = false; |
306 | return 0; |
307 | } |
308 | *hint_found = true; |
309 | |
310 | if (!hnode->parent) |
311 | return objagg_obj_root_create(objagg, objagg_obj, hnode); |
312 | |
313 | parent = __objagg_obj_get(objagg, obj: hnode->parent->obj); |
314 | if (IS_ERR(ptr: parent)) |
315 | return PTR_ERR(ptr: parent); |
316 | |
317 | err = objagg_obj_parent_assign(objagg, objagg_obj, parent, take_parent_ref: false); |
318 | if (err) { |
319 | *hint_found = false; |
320 | err = 0; |
321 | goto err_parent_assign; |
322 | } |
323 | |
324 | return 0; |
325 | |
326 | err_parent_assign: |
327 | objagg_obj_put(objagg, objagg_obj: parent); |
328 | return err; |
329 | } |
330 | |
331 | static int objagg_obj_init(struct objagg *objagg, |
332 | struct objagg_obj *objagg_obj) |
333 | { |
334 | bool hint_found; |
335 | int err; |
336 | |
337 | /* First, try to use hints if they are available and |
338 | * if they provide result. |
339 | */ |
340 | err = objagg_obj_init_with_hints(objagg, objagg_obj, hint_found: &hint_found); |
341 | if (err) |
342 | return err; |
343 | |
344 | if (hint_found) |
345 | return 0; |
346 | |
347 | /* Try to find if the object can be aggregated under an existing one. */ |
348 | err = objagg_obj_parent_lookup_assign(objagg, objagg_obj); |
349 | if (!err) |
350 | return 0; |
351 | /* If aggregation is not possible, make the object a root. */ |
352 | return objagg_obj_root_create(objagg, objagg_obj, NULL); |
353 | } |
354 | |
355 | static void objagg_obj_fini(struct objagg *objagg, |
356 | struct objagg_obj *objagg_obj) |
357 | { |
358 | if (!objagg_obj_is_root(objagg_obj)) |
359 | objagg_obj_parent_unassign(objagg, objagg_obj); |
360 | else |
361 | objagg_obj_root_destroy(objagg, objagg_obj); |
362 | } |
363 | |
364 | static struct objagg_obj *objagg_obj_create(struct objagg *objagg, void *obj) |
365 | { |
366 | struct objagg_obj *objagg_obj; |
367 | int err; |
368 | |
369 | objagg_obj = kzalloc(size: sizeof(*objagg_obj) + objagg->ops->obj_size, |
370 | GFP_KERNEL); |
371 | if (!objagg_obj) |
372 | return ERR_PTR(error: -ENOMEM); |
373 | objagg_obj_ref_inc(objagg_obj); |
374 | memcpy(objagg_obj->obj, obj, objagg->ops->obj_size); |
375 | |
376 | err = objagg_obj_init(objagg, objagg_obj); |
377 | if (err) |
378 | goto err_obj_init; |
379 | |
380 | err = rhashtable_insert_fast(ht: &objagg->obj_ht, obj: &objagg_obj->ht_node, |
381 | params: objagg->ht_params); |
382 | if (err) |
383 | goto err_ht_insert; |
384 | list_add(new: &objagg_obj->list, head: &objagg->obj_list); |
385 | objagg->obj_count++; |
386 | trace_objagg_obj_create(objagg, obj: objagg_obj); |
387 | |
388 | return objagg_obj; |
389 | |
390 | err_ht_insert: |
391 | objagg_obj_fini(objagg, objagg_obj); |
392 | err_obj_init: |
393 | kfree(objp: objagg_obj); |
394 | return ERR_PTR(error: err); |
395 | } |
396 | |
397 | static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj) |
398 | { |
399 | struct objagg_obj *objagg_obj; |
400 | |
401 | /* First, try to find the object exactly as user passed it, |
402 | * perhaps it is already in use. |
403 | */ |
404 | objagg_obj = objagg_obj_lookup(objagg, obj); |
405 | if (objagg_obj) { |
406 | objagg_obj_ref_inc(objagg_obj); |
407 | return objagg_obj; |
408 | } |
409 | |
410 | return objagg_obj_create(objagg, obj); |
411 | } |
412 | |
413 | /** |
414 | * objagg_obj_get - gets an object within objagg instance |
415 | * @objagg: objagg instance |
416 | * @obj: user-specific private object pointer |
417 | * |
418 | * Note: all locking must be provided by the caller. |
419 | * |
420 | * Size of the "obj" memory is specified in "objagg->ops". |
421 | * |
422 | * There are 3 main options this function wraps: |
423 | * 1) The object according to "obj" already exist. In that case |
424 | * the reference counter is incrementes and the object is returned. |
425 | * 2) The object does not exist, but it can be aggregated within |
426 | * another object. In that case, user ops->delta_create() is called |
427 | * to obtain delta data and a new object is created with returned |
428 | * user-delta private pointer. |
429 | * 3) The object does not exist and cannot be aggregated into |
430 | * any of the existing objects. In that case, user ops->root_create() |
431 | * is called to create the root and a new object is created with |
432 | * returned user-root private pointer. |
433 | * |
434 | * Returns a pointer to objagg object instance in case of success, |
435 | * otherwise it returns pointer error using ERR_PTR macro. |
436 | */ |
437 | struct objagg_obj *objagg_obj_get(struct objagg *objagg, void *obj) |
438 | { |
439 | struct objagg_obj *objagg_obj; |
440 | |
441 | objagg_obj = __objagg_obj_get(objagg, obj); |
442 | if (IS_ERR(ptr: objagg_obj)) |
443 | return objagg_obj; |
444 | objagg_obj_stats_inc(objagg_obj); |
445 | trace_objagg_obj_get(objagg, obj: objagg_obj, refcount: objagg_obj->refcount); |
446 | return objagg_obj; |
447 | } |
448 | EXPORT_SYMBOL(objagg_obj_get); |
449 | |
450 | static void objagg_obj_destroy(struct objagg *objagg, |
451 | struct objagg_obj *objagg_obj) |
452 | { |
453 | trace_objagg_obj_destroy(objagg, obj: objagg_obj); |
454 | --objagg->obj_count; |
455 | list_del(entry: &objagg_obj->list); |
456 | rhashtable_remove_fast(ht: &objagg->obj_ht, obj: &objagg_obj->ht_node, |
457 | params: objagg->ht_params); |
458 | objagg_obj_fini(objagg, objagg_obj); |
459 | kfree(objp: objagg_obj); |
460 | } |
461 | |
462 | static void __objagg_obj_put(struct objagg *objagg, |
463 | struct objagg_obj *objagg_obj) |
464 | { |
465 | if (!objagg_obj_ref_dec(objagg_obj)) |
466 | objagg_obj_destroy(objagg, objagg_obj); |
467 | } |
468 | |
469 | /** |
470 | * objagg_obj_put - puts an object within objagg instance |
471 | * @objagg: objagg instance |
472 | * @objagg_obj: objagg object instance |
473 | * |
474 | * Note: all locking must be provided by the caller. |
475 | * |
476 | * Symmetric to objagg_obj_get(). |
477 | */ |
478 | void objagg_obj_put(struct objagg *objagg, struct objagg_obj *objagg_obj) |
479 | { |
480 | trace_objagg_obj_put(objagg, obj: objagg_obj, refcount: objagg_obj->refcount); |
481 | objagg_obj_stats_dec(objagg_obj); |
482 | __objagg_obj_put(objagg, objagg_obj); |
483 | } |
484 | EXPORT_SYMBOL(objagg_obj_put); |
485 | |
486 | /** |
487 | * objagg_create - creates a new objagg instance |
488 | * @ops: user-specific callbacks |
489 | * @objagg_hints: hints, can be NULL |
490 | * @priv: pointer to a private data passed to the ops |
491 | * |
492 | * Note: all locking must be provided by the caller. |
493 | * |
494 | * The purpose of the library is to provide an infrastructure to |
495 | * aggregate user-specified objects. Library does not care about the type |
496 | * of the object. User fills-up ops which take care of the specific |
497 | * user object manipulation. |
498 | * |
499 | * As a very stupid example, consider integer numbers. For example |
500 | * number 8 as a root object. That can aggregate number 9 with delta 1, |
501 | * number 10 with delta 2, etc. This example is implemented as |
502 | * a part of a testing module in test_objagg.c file. |
503 | * |
504 | * Each objagg instance contains multiple trees. Each tree node is |
505 | * represented by "an object". In the current implementation there can be |
506 | * only roots and leafs nodes. Leaf nodes are called deltas. |
507 | * But in general, this can be easily extended for intermediate nodes. |
508 | * In that extension, a delta would be associated with all non-root |
509 | * nodes. |
510 | * |
511 | * Returns a pointer to newly created objagg instance in case of success, |
512 | * otherwise it returns pointer error using ERR_PTR macro. |
513 | */ |
514 | struct objagg *objagg_create(const struct objagg_ops *ops, |
515 | struct objagg_hints *objagg_hints, void *priv) |
516 | { |
517 | struct objagg *objagg; |
518 | int err; |
519 | |
520 | if (WARN_ON(!ops || !ops->root_create || !ops->root_destroy || |
521 | !ops->delta_check || !ops->delta_create || |
522 | !ops->delta_destroy)) |
523 | return ERR_PTR(error: -EINVAL); |
524 | |
525 | objagg = kzalloc(size: sizeof(*objagg), GFP_KERNEL); |
526 | if (!objagg) |
527 | return ERR_PTR(error: -ENOMEM); |
528 | objagg->ops = ops; |
529 | if (objagg_hints) { |
530 | objagg->hints = objagg_hints; |
531 | objagg_hints->refcount++; |
532 | } |
533 | objagg->priv = priv; |
534 | INIT_LIST_HEAD(list: &objagg->obj_list); |
535 | |
536 | objagg->ht_params.key_len = ops->obj_size; |
537 | objagg->ht_params.key_offset = offsetof(struct objagg_obj, obj); |
538 | objagg->ht_params.head_offset = offsetof(struct objagg_obj, ht_node); |
539 | |
540 | err = rhashtable_init(ht: &objagg->obj_ht, params: &objagg->ht_params); |
541 | if (err) |
542 | goto err_rhashtable_init; |
543 | |
544 | ida_init(ida: &objagg->root_ida); |
545 | |
546 | trace_objagg_create(objagg); |
547 | return objagg; |
548 | |
549 | err_rhashtable_init: |
550 | kfree(objp: objagg); |
551 | return ERR_PTR(error: err); |
552 | } |
553 | EXPORT_SYMBOL(objagg_create); |
554 | |
555 | /** |
556 | * objagg_destroy - destroys a new objagg instance |
557 | * @objagg: objagg instance |
558 | * |
559 | * Note: all locking must be provided by the caller. |
560 | */ |
561 | void objagg_destroy(struct objagg *objagg) |
562 | { |
563 | trace_objagg_destroy(objagg); |
564 | ida_destroy(ida: &objagg->root_ida); |
565 | WARN_ON(!list_empty(&objagg->obj_list)); |
566 | rhashtable_destroy(ht: &objagg->obj_ht); |
567 | if (objagg->hints) |
568 | objagg_hints_put(objagg_hints: objagg->hints); |
569 | kfree(objp: objagg); |
570 | } |
571 | EXPORT_SYMBOL(objagg_destroy); |
572 | |
573 | static int objagg_stats_info_sort_cmp_func(const void *a, const void *b) |
574 | { |
575 | const struct objagg_obj_stats_info *stats_info1 = a; |
576 | const struct objagg_obj_stats_info *stats_info2 = b; |
577 | |
578 | if (stats_info1->is_root != stats_info2->is_root) |
579 | return stats_info2->is_root - stats_info1->is_root; |
580 | if (stats_info1->stats.delta_user_count != |
581 | stats_info2->stats.delta_user_count) |
582 | return stats_info2->stats.delta_user_count - |
583 | stats_info1->stats.delta_user_count; |
584 | return stats_info2->stats.user_count - stats_info1->stats.user_count; |
585 | } |
586 | |
587 | /** |
588 | * objagg_stats_get - obtains stats of the objagg instance |
589 | * @objagg: objagg instance |
590 | * |
591 | * Note: all locking must be provided by the caller. |
592 | * |
593 | * The returned structure contains statistics of all object |
594 | * currently in use, ordered by following rules: |
595 | * 1) Root objects are always on lower indexes than the rest. |
596 | * 2) Objects with higher delta user count are always on lower |
597 | * indexes. |
598 | * 3) In case more objects have the same delta user count, |
599 | * the objects are ordered by user count. |
600 | * |
601 | * Returns a pointer to stats instance in case of success, |
602 | * otherwise it returns pointer error using ERR_PTR macro. |
603 | */ |
604 | const struct objagg_stats *objagg_stats_get(struct objagg *objagg) |
605 | { |
606 | struct objagg_stats *objagg_stats; |
607 | struct objagg_obj *objagg_obj; |
608 | int i; |
609 | |
610 | objagg_stats = kzalloc(struct_size(objagg_stats, stats_info, |
611 | objagg->obj_count), GFP_KERNEL); |
612 | if (!objagg_stats) |
613 | return ERR_PTR(error: -ENOMEM); |
614 | |
615 | i = 0; |
616 | list_for_each_entry(objagg_obj, &objagg->obj_list, list) { |
617 | memcpy(&objagg_stats->stats_info[i].stats, &objagg_obj->stats, |
618 | sizeof(objagg_stats->stats_info[0].stats)); |
619 | objagg_stats->stats_info[i].objagg_obj = objagg_obj; |
620 | objagg_stats->stats_info[i].is_root = |
621 | objagg_obj_is_root(objagg_obj); |
622 | if (objagg_stats->stats_info[i].is_root) |
623 | objagg_stats->root_count++; |
624 | i++; |
625 | } |
626 | objagg_stats->stats_info_count = i; |
627 | |
628 | sort(base: objagg_stats->stats_info, num: objagg_stats->stats_info_count, |
629 | size: sizeof(struct objagg_obj_stats_info), |
630 | cmp_func: objagg_stats_info_sort_cmp_func, NULL); |
631 | |
632 | return objagg_stats; |
633 | } |
634 | EXPORT_SYMBOL(objagg_stats_get); |
635 | |
636 | /** |
637 | * objagg_stats_put - puts stats of the objagg instance |
638 | * @objagg_stats: objagg instance stats |
639 | * |
640 | * Note: all locking must be provided by the caller. |
641 | */ |
642 | void objagg_stats_put(const struct objagg_stats *objagg_stats) |
643 | { |
644 | kfree(objp: objagg_stats); |
645 | } |
646 | EXPORT_SYMBOL(objagg_stats_put); |
647 | |
648 | static struct objagg_hints_node * |
649 | objagg_hints_node_create(struct objagg_hints *objagg_hints, |
650 | struct objagg_obj *objagg_obj, size_t obj_size, |
651 | struct objagg_hints_node *parent_hnode) |
652 | { |
653 | unsigned int user_count = objagg_obj->stats.user_count; |
654 | struct objagg_hints_node *hnode; |
655 | int err; |
656 | |
657 | hnode = kzalloc(size: sizeof(*hnode) + obj_size, GFP_KERNEL); |
658 | if (!hnode) |
659 | return ERR_PTR(error: -ENOMEM); |
660 | memcpy(hnode->obj, &objagg_obj->obj, obj_size); |
661 | hnode->stats_info.stats.user_count = user_count; |
662 | hnode->stats_info.stats.delta_user_count = user_count; |
663 | if (parent_hnode) { |
664 | parent_hnode->stats_info.stats.delta_user_count += user_count; |
665 | } else { |
666 | hnode->root_id = objagg_hints->root_count++; |
667 | hnode->stats_info.is_root = true; |
668 | } |
669 | hnode->stats_info.objagg_obj = objagg_obj; |
670 | |
671 | err = rhashtable_insert_fast(ht: &objagg_hints->node_ht, obj: &hnode->ht_node, |
672 | params: objagg_hints->ht_params); |
673 | if (err) |
674 | goto err_ht_insert; |
675 | |
676 | list_add(new: &hnode->list, head: &objagg_hints->node_list); |
677 | hnode->parent = parent_hnode; |
678 | objagg_hints->node_count++; |
679 | |
680 | return hnode; |
681 | |
682 | err_ht_insert: |
683 | kfree(objp: hnode); |
684 | return ERR_PTR(error: err); |
685 | } |
686 | |
687 | static void objagg_hints_flush(struct objagg_hints *objagg_hints) |
688 | { |
689 | struct objagg_hints_node *hnode, *tmp; |
690 | |
691 | list_for_each_entry_safe(hnode, tmp, &objagg_hints->node_list, list) { |
692 | list_del(entry: &hnode->list); |
693 | rhashtable_remove_fast(ht: &objagg_hints->node_ht, obj: &hnode->ht_node, |
694 | params: objagg_hints->ht_params); |
695 | kfree(objp: hnode); |
696 | } |
697 | } |
698 | |
699 | struct objagg_tmp_node { |
700 | struct objagg_obj *objagg_obj; |
701 | bool crossed_out; |
702 | }; |
703 | |
704 | struct objagg_tmp_graph { |
705 | struct objagg_tmp_node *nodes; |
706 | unsigned long nodes_count; |
707 | unsigned long *edges; |
708 | }; |
709 | |
710 | static int objagg_tmp_graph_edge_index(struct objagg_tmp_graph *graph, |
711 | int parent_index, int index) |
712 | { |
713 | return index * graph->nodes_count + parent_index; |
714 | } |
715 | |
716 | static void objagg_tmp_graph_edge_set(struct objagg_tmp_graph *graph, |
717 | int parent_index, int index) |
718 | { |
719 | int edge_index = objagg_tmp_graph_edge_index(graph, parent_index: index, |
720 | index: parent_index); |
721 | |
722 | __set_bit(edge_index, graph->edges); |
723 | } |
724 | |
725 | static bool objagg_tmp_graph_is_edge(struct objagg_tmp_graph *graph, |
726 | int parent_index, int index) |
727 | { |
728 | int edge_index = objagg_tmp_graph_edge_index(graph, parent_index: index, |
729 | index: parent_index); |
730 | |
731 | return test_bit(edge_index, graph->edges); |
732 | } |
733 | |
734 | static unsigned int objagg_tmp_graph_node_weight(struct objagg_tmp_graph *graph, |
735 | unsigned int index) |
736 | { |
737 | struct objagg_tmp_node *node = &graph->nodes[index]; |
738 | unsigned int weight = node->objagg_obj->stats.user_count; |
739 | int j; |
740 | |
741 | /* Node weight is sum of node users and all other nodes users |
742 | * that this node can represent with delta. |
743 | */ |
744 | |
745 | for (j = 0; j < graph->nodes_count; j++) { |
746 | if (!objagg_tmp_graph_is_edge(graph, parent_index: index, index: j)) |
747 | continue; |
748 | node = &graph->nodes[j]; |
749 | if (node->crossed_out) |
750 | continue; |
751 | weight += node->objagg_obj->stats.user_count; |
752 | } |
753 | return weight; |
754 | } |
755 | |
756 | static int objagg_tmp_graph_node_max_weight(struct objagg_tmp_graph *graph) |
757 | { |
758 | struct objagg_tmp_node *node; |
759 | unsigned int max_weight = 0; |
760 | unsigned int weight; |
761 | int max_index = -1; |
762 | int i; |
763 | |
764 | for (i = 0; i < graph->nodes_count; i++) { |
765 | node = &graph->nodes[i]; |
766 | if (node->crossed_out) |
767 | continue; |
768 | weight = objagg_tmp_graph_node_weight(graph, index: i); |
769 | if (weight >= max_weight) { |
770 | max_weight = weight; |
771 | max_index = i; |
772 | } |
773 | } |
774 | return max_index; |
775 | } |
776 | |
777 | static struct objagg_tmp_graph *objagg_tmp_graph_create(struct objagg *objagg) |
778 | { |
779 | unsigned int nodes_count = objagg->obj_count; |
780 | struct objagg_tmp_graph *graph; |
781 | struct objagg_tmp_node *node; |
782 | struct objagg_tmp_node *pnode; |
783 | struct objagg_obj *objagg_obj; |
784 | int i, j; |
785 | |
786 | graph = kzalloc(size: sizeof(*graph), GFP_KERNEL); |
787 | if (!graph) |
788 | return NULL; |
789 | |
790 | graph->nodes = kcalloc(n: nodes_count, size: sizeof(*graph->nodes), GFP_KERNEL); |
791 | if (!graph->nodes) |
792 | goto err_nodes_alloc; |
793 | graph->nodes_count = nodes_count; |
794 | |
795 | graph->edges = bitmap_zalloc(nbits: nodes_count * nodes_count, GFP_KERNEL); |
796 | if (!graph->edges) |
797 | goto err_edges_alloc; |
798 | |
799 | i = 0; |
800 | list_for_each_entry(objagg_obj, &objagg->obj_list, list) { |
801 | node = &graph->nodes[i++]; |
802 | node->objagg_obj = objagg_obj; |
803 | } |
804 | |
805 | /* Assemble a temporary graph. Insert edge X->Y in case Y can be |
806 | * in delta of X. |
807 | */ |
808 | for (i = 0; i < nodes_count; i++) { |
809 | for (j = 0; j < nodes_count; j++) { |
810 | if (i == j) |
811 | continue; |
812 | pnode = &graph->nodes[i]; |
813 | node = &graph->nodes[j]; |
814 | if (objagg->ops->delta_check(objagg->priv, |
815 | pnode->objagg_obj->obj, |
816 | node->objagg_obj->obj)) { |
817 | objagg_tmp_graph_edge_set(graph, parent_index: i, index: j); |
818 | |
819 | } |
820 | } |
821 | } |
822 | return graph; |
823 | |
824 | err_edges_alloc: |
825 | kfree(objp: graph->nodes); |
826 | err_nodes_alloc: |
827 | kfree(objp: graph); |
828 | return NULL; |
829 | } |
830 | |
831 | static void objagg_tmp_graph_destroy(struct objagg_tmp_graph *graph) |
832 | { |
833 | bitmap_free(bitmap: graph->edges); |
834 | kfree(objp: graph->nodes); |
835 | kfree(objp: graph); |
836 | } |
837 | |
838 | static int |
839 | objagg_opt_simple_greedy_fillup_hints(struct objagg_hints *objagg_hints, |
840 | struct objagg *objagg) |
841 | { |
842 | struct objagg_hints_node *hnode, *parent_hnode; |
843 | struct objagg_tmp_graph *graph; |
844 | struct objagg_tmp_node *node; |
845 | int index; |
846 | int j; |
847 | int err; |
848 | |
849 | graph = objagg_tmp_graph_create(objagg); |
850 | if (!graph) |
851 | return -ENOMEM; |
852 | |
853 | /* Find the nodes from the ones that can accommodate most users |
854 | * and cross them out of the graph. Save them to the hint list. |
855 | */ |
856 | while ((index = objagg_tmp_graph_node_max_weight(graph)) != -1) { |
857 | node = &graph->nodes[index]; |
858 | node->crossed_out = true; |
859 | hnode = objagg_hints_node_create(objagg_hints, |
860 | objagg_obj: node->objagg_obj, |
861 | obj_size: objagg->ops->obj_size, |
862 | NULL); |
863 | if (IS_ERR(ptr: hnode)) { |
864 | err = PTR_ERR(ptr: hnode); |
865 | goto out; |
866 | } |
867 | parent_hnode = hnode; |
868 | for (j = 0; j < graph->nodes_count; j++) { |
869 | if (!objagg_tmp_graph_is_edge(graph, parent_index: index, index: j)) |
870 | continue; |
871 | node = &graph->nodes[j]; |
872 | if (node->crossed_out) |
873 | continue; |
874 | node->crossed_out = true; |
875 | hnode = objagg_hints_node_create(objagg_hints, |
876 | objagg_obj: node->objagg_obj, |
877 | obj_size: objagg->ops->obj_size, |
878 | parent_hnode); |
879 | if (IS_ERR(ptr: hnode)) { |
880 | err = PTR_ERR(ptr: hnode); |
881 | goto out; |
882 | } |
883 | } |
884 | } |
885 | |
886 | err = 0; |
887 | out: |
888 | objagg_tmp_graph_destroy(graph); |
889 | return err; |
890 | } |
891 | |
892 | struct objagg_opt_algo { |
893 | int (*fillup_hints)(struct objagg_hints *objagg_hints, |
894 | struct objagg *objagg); |
895 | }; |
896 | |
897 | static const struct objagg_opt_algo objagg_opt_simple_greedy = { |
898 | .fillup_hints = objagg_opt_simple_greedy_fillup_hints, |
899 | }; |
900 | |
901 | |
902 | static const struct objagg_opt_algo *objagg_opt_algos[] = { |
903 | [OBJAGG_OPT_ALGO_SIMPLE_GREEDY] = &objagg_opt_simple_greedy, |
904 | }; |
905 | |
906 | static int objagg_hints_obj_cmp(struct rhashtable_compare_arg *arg, |
907 | const void *obj) |
908 | { |
909 | struct rhashtable *ht = arg->ht; |
910 | struct objagg_hints *objagg_hints = |
911 | container_of(ht, struct objagg_hints, node_ht); |
912 | const struct objagg_ops *ops = objagg_hints->ops; |
913 | const char *ptr = obj; |
914 | |
915 | ptr += ht->p.key_offset; |
916 | return ops->hints_obj_cmp ? ops->hints_obj_cmp(ptr, arg->key) : |
917 | memcmp(p: ptr, q: arg->key, size: ht->p.key_len); |
918 | } |
919 | |
920 | /** |
921 | * objagg_hints_get - obtains hints instance |
922 | * @objagg: objagg instance |
923 | * @opt_algo_type: type of hints finding algorithm |
924 | * |
925 | * Note: all locking must be provided by the caller. |
926 | * |
927 | * According to the algo type, the existing objects of objagg instance |
928 | * are going to be went-through to assemble an optimal tree. We call this |
929 | * tree hints. These hints can be later on used for creation of |
930 | * a new objagg instance. There, the future object creations are going |
931 | * to be consulted with these hints in order to find out, where exactly |
932 | * the new object should be put as a root or delta. |
933 | * |
934 | * Returns a pointer to hints instance in case of success, |
935 | * otherwise it returns pointer error using ERR_PTR macro. |
936 | */ |
937 | struct objagg_hints *objagg_hints_get(struct objagg *objagg, |
938 | enum objagg_opt_algo_type opt_algo_type) |
939 | { |
940 | const struct objagg_opt_algo *algo = objagg_opt_algos[opt_algo_type]; |
941 | struct objagg_hints *objagg_hints; |
942 | int err; |
943 | |
944 | objagg_hints = kzalloc(size: sizeof(*objagg_hints), GFP_KERNEL); |
945 | if (!objagg_hints) |
946 | return ERR_PTR(error: -ENOMEM); |
947 | |
948 | objagg_hints->ops = objagg->ops; |
949 | objagg_hints->refcount = 1; |
950 | |
951 | INIT_LIST_HEAD(list: &objagg_hints->node_list); |
952 | |
953 | objagg_hints->ht_params.key_len = objagg->ops->obj_size; |
954 | objagg_hints->ht_params.key_offset = |
955 | offsetof(struct objagg_hints_node, obj); |
956 | objagg_hints->ht_params.head_offset = |
957 | offsetof(struct objagg_hints_node, ht_node); |
958 | objagg_hints->ht_params.obj_cmpfn = objagg_hints_obj_cmp; |
959 | |
960 | err = rhashtable_init(ht: &objagg_hints->node_ht, params: &objagg_hints->ht_params); |
961 | if (err) |
962 | goto err_rhashtable_init; |
963 | |
964 | err = algo->fillup_hints(objagg_hints, objagg); |
965 | if (err) |
966 | goto err_fillup_hints; |
967 | |
968 | if (WARN_ON(objagg_hints->node_count != objagg->obj_count)) { |
969 | err = -EINVAL; |
970 | goto err_node_count_check; |
971 | } |
972 | |
973 | return objagg_hints; |
974 | |
975 | err_node_count_check: |
976 | err_fillup_hints: |
977 | objagg_hints_flush(objagg_hints); |
978 | rhashtable_destroy(ht: &objagg_hints->node_ht); |
979 | err_rhashtable_init: |
980 | kfree(objp: objagg_hints); |
981 | return ERR_PTR(error: err); |
982 | } |
983 | EXPORT_SYMBOL(objagg_hints_get); |
984 | |
985 | /** |
986 | * objagg_hints_put - puts hints instance |
987 | * @objagg_hints: objagg hints instance |
988 | * |
989 | * Note: all locking must be provided by the caller. |
990 | */ |
991 | void objagg_hints_put(struct objagg_hints *objagg_hints) |
992 | { |
993 | if (--objagg_hints->refcount) |
994 | return; |
995 | objagg_hints_flush(objagg_hints); |
996 | rhashtable_destroy(ht: &objagg_hints->node_ht); |
997 | kfree(objp: objagg_hints); |
998 | } |
999 | EXPORT_SYMBOL(objagg_hints_put); |
1000 | |
1001 | /** |
1002 | * objagg_hints_stats_get - obtains stats of the hints instance |
1003 | * @objagg_hints: hints instance |
1004 | * |
1005 | * Note: all locking must be provided by the caller. |
1006 | * |
1007 | * The returned structure contains statistics of all objects |
1008 | * currently in use, ordered by following rules: |
1009 | * 1) Root objects are always on lower indexes than the rest. |
1010 | * 2) Objects with higher delta user count are always on lower |
1011 | * indexes. |
1012 | * 3) In case multiple objects have the same delta user count, |
1013 | * the objects are ordered by user count. |
1014 | * |
1015 | * Returns a pointer to stats instance in case of success, |
1016 | * otherwise it returns pointer error using ERR_PTR macro. |
1017 | */ |
1018 | const struct objagg_stats * |
1019 | objagg_hints_stats_get(struct objagg_hints *objagg_hints) |
1020 | { |
1021 | struct objagg_stats *objagg_stats; |
1022 | struct objagg_hints_node *hnode; |
1023 | int i; |
1024 | |
1025 | objagg_stats = kzalloc(struct_size(objagg_stats, stats_info, |
1026 | objagg_hints->node_count), |
1027 | GFP_KERNEL); |
1028 | if (!objagg_stats) |
1029 | return ERR_PTR(error: -ENOMEM); |
1030 | |
1031 | i = 0; |
1032 | list_for_each_entry(hnode, &objagg_hints->node_list, list) { |
1033 | memcpy(&objagg_stats->stats_info[i], &hnode->stats_info, |
1034 | sizeof(objagg_stats->stats_info[0])); |
1035 | if (objagg_stats->stats_info[i].is_root) |
1036 | objagg_stats->root_count++; |
1037 | i++; |
1038 | } |
1039 | objagg_stats->stats_info_count = i; |
1040 | |
1041 | sort(base: objagg_stats->stats_info, num: objagg_stats->stats_info_count, |
1042 | size: sizeof(struct objagg_obj_stats_info), |
1043 | cmp_func: objagg_stats_info_sort_cmp_func, NULL); |
1044 | |
1045 | return objagg_stats; |
1046 | } |
1047 | EXPORT_SYMBOL(objagg_hints_stats_get); |
1048 | |
1049 | MODULE_LICENSE("Dual BSD/GPL" ); |
1050 | MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>" ); |
1051 | MODULE_DESCRIPTION("Object aggregation manager" ); |
1052 | |