Commit | Line | Data |
---|---|---|
0a020d41 JP |
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/list.h> | |
8 | #include <linux/sort.h> | |
9 | #include <linux/objagg.h> | |
10 | ||
11 | #define CREATE_TRACE_POINTS | |
12 | #include <trace/events/objagg.h> | |
13 | ||
14 | struct objagg { | |
15 | const struct objagg_ops *ops; | |
16 | void *priv; | |
17 | struct rhashtable obj_ht; | |
18 | struct rhashtable_params ht_params; | |
19 | struct list_head obj_list; | |
20 | unsigned int obj_count; | |
21 | }; | |
22 | ||
23 | struct objagg_obj { | |
24 | struct rhash_head ht_node; /* member of objagg->obj_ht */ | |
25 | struct list_head list; /* member of objagg->obj_list */ | |
26 | struct objagg_obj *parent; /* if the object is nested, this | |
27 | * holds pointer to parent, otherwise NULL | |
28 | */ | |
29 | union { | |
30 | void *delta_priv; /* user delta private */ | |
31 | void *root_priv; /* user root private */ | |
32 | }; | |
33 | unsigned int refcount; /* counts number of users of this object | |
34 | * including nested objects | |
35 | */ | |
36 | struct objagg_obj_stats stats; | |
37 | unsigned long obj[0]; | |
38 | }; | |
39 | ||
40 | static unsigned int objagg_obj_ref_inc(struct objagg_obj *objagg_obj) | |
41 | { | |
42 | return ++objagg_obj->refcount; | |
43 | } | |
44 | ||
45 | static unsigned int objagg_obj_ref_dec(struct objagg_obj *objagg_obj) | |
46 | { | |
47 | return --objagg_obj->refcount; | |
48 | } | |
49 | ||
50 | static void objagg_obj_stats_inc(struct objagg_obj *objagg_obj) | |
51 | { | |
52 | objagg_obj->stats.user_count++; | |
53 | objagg_obj->stats.delta_user_count++; | |
54 | if (objagg_obj->parent) | |
55 | objagg_obj->parent->stats.delta_user_count++; | |
56 | } | |
57 | ||
58 | static void objagg_obj_stats_dec(struct objagg_obj *objagg_obj) | |
59 | { | |
60 | objagg_obj->stats.user_count--; | |
61 | objagg_obj->stats.delta_user_count--; | |
62 | if (objagg_obj->parent) | |
63 | objagg_obj->parent->stats.delta_user_count--; | |
64 | } | |
65 | ||
66 | static bool objagg_obj_is_root(const struct objagg_obj *objagg_obj) | |
67 | { | |
68 | /* Nesting is not supported, so we can use ->parent | |
69 | * to figure out if the object is root. | |
70 | */ | |
71 | return !objagg_obj->parent; | |
72 | } | |
73 | ||
74 | /** | |
75 | * objagg_obj_root_priv - obtains root private for an object | |
76 | * @objagg_obj: objagg object instance | |
77 | * | |
78 | * Note: all locking must be provided by the caller. | |
79 | * | |
80 | * Either the object is root itself when the private is returned | |
81 | * directly, or the parent is root and its private is returned | |
82 | * instead. | |
83 | * | |
84 | * Returns a user private root pointer. | |
85 | */ | |
86 | const void *objagg_obj_root_priv(const struct objagg_obj *objagg_obj) | |
87 | { | |
88 | if (objagg_obj_is_root(objagg_obj)) | |
89 | return objagg_obj->root_priv; | |
90 | WARN_ON(!objagg_obj_is_root(objagg_obj->parent)); | |
91 | return objagg_obj->parent->root_priv; | |
92 | } | |
93 | EXPORT_SYMBOL(objagg_obj_root_priv); | |
94 | ||
95 | /** | |
96 | * objagg_obj_delta_priv - obtains delta private for an object | |
97 | * @objagg_obj: objagg object instance | |
98 | * | |
99 | * Note: all locking must be provided by the caller. | |
100 | * | |
101 | * Returns user private delta pointer or NULL in case the passed | |
102 | * object is root. | |
103 | */ | |
104 | const void *objagg_obj_delta_priv(const struct objagg_obj *objagg_obj) | |
105 | { | |
106 | if (objagg_obj_is_root(objagg_obj)) | |
107 | return NULL; | |
108 | return objagg_obj->delta_priv; | |
109 | } | |
110 | EXPORT_SYMBOL(objagg_obj_delta_priv); | |
111 | ||
112 | /** | |
113 | * objagg_obj_raw - obtains object user private pointer | |
114 | * @objagg_obj: objagg object instance | |
115 | * | |
116 | * Note: all locking must be provided by the caller. | |
117 | * | |
118 | * Returns user private pointer as was passed to objagg_obj_get() by "obj" arg. | |
119 | */ | |
120 | const void *objagg_obj_raw(const struct objagg_obj *objagg_obj) | |
121 | { | |
122 | return objagg_obj->obj; | |
123 | } | |
124 | EXPORT_SYMBOL(objagg_obj_raw); | |
125 | ||
126 | static struct objagg_obj *objagg_obj_lookup(struct objagg *objagg, void *obj) | |
127 | { | |
128 | return rhashtable_lookup_fast(&objagg->obj_ht, obj, objagg->ht_params); | |
129 | } | |
130 | ||
131 | static int objagg_obj_parent_assign(struct objagg *objagg, | |
132 | struct objagg_obj *objagg_obj, | |
133 | struct objagg_obj *parent) | |
134 | { | |
135 | void *delta_priv; | |
136 | ||
137 | delta_priv = objagg->ops->delta_create(objagg->priv, parent->obj, | |
138 | objagg_obj->obj); | |
139 | if (IS_ERR(delta_priv)) | |
140 | return PTR_ERR(delta_priv); | |
141 | ||
142 | /* User returned a delta private, that means that | |
143 | * our object can be aggregated into the parent. | |
144 | */ | |
145 | objagg_obj->parent = parent; | |
146 | objagg_obj->delta_priv = delta_priv; | |
147 | objagg_obj_ref_inc(objagg_obj->parent); | |
148 | trace_objagg_obj_parent_assign(objagg, objagg_obj, | |
149 | parent, | |
150 | parent->refcount); | |
151 | return 0; | |
152 | } | |
153 | ||
154 | static int objagg_obj_parent_lookup_assign(struct objagg *objagg, | |
155 | struct objagg_obj *objagg_obj) | |
156 | { | |
157 | struct objagg_obj *objagg_obj_cur; | |
158 | int err; | |
159 | ||
160 | list_for_each_entry(objagg_obj_cur, &objagg->obj_list, list) { | |
161 | /* Nesting is not supported. In case the object | |
162 | * is not root, it cannot be assigned as parent. | |
163 | */ | |
164 | if (!objagg_obj_is_root(objagg_obj_cur)) | |
165 | continue; | |
166 | err = objagg_obj_parent_assign(objagg, objagg_obj, | |
167 | objagg_obj_cur); | |
168 | if (!err) | |
169 | return 0; | |
170 | } | |
171 | return -ENOENT; | |
172 | } | |
173 | ||
174 | static void __objagg_obj_put(struct objagg *objagg, | |
175 | struct objagg_obj *objagg_obj); | |
176 | ||
177 | static void objagg_obj_parent_unassign(struct objagg *objagg, | |
178 | struct objagg_obj *objagg_obj) | |
179 | { | |
180 | trace_objagg_obj_parent_unassign(objagg, objagg_obj, | |
181 | objagg_obj->parent, | |
182 | objagg_obj->parent->refcount); | |
183 | objagg->ops->delta_destroy(objagg->priv, objagg_obj->delta_priv); | |
184 | __objagg_obj_put(objagg, objagg_obj->parent); | |
185 | } | |
186 | ||
187 | static int objagg_obj_root_create(struct objagg *objagg, | |
188 | struct objagg_obj *objagg_obj) | |
189 | { | |
190 | objagg_obj->root_priv = objagg->ops->root_create(objagg->priv, | |
191 | objagg_obj->obj); | |
192 | if (IS_ERR(objagg_obj->root_priv)) | |
193 | return PTR_ERR(objagg_obj->root_priv); | |
194 | ||
195 | trace_objagg_obj_root_create(objagg, objagg_obj); | |
196 | return 0; | |
197 | } | |
198 | ||
199 | static void objagg_obj_root_destroy(struct objagg *objagg, | |
200 | struct objagg_obj *objagg_obj) | |
201 | { | |
202 | trace_objagg_obj_root_destroy(objagg, objagg_obj); | |
203 | objagg->ops->root_destroy(objagg->priv, objagg_obj->root_priv); | |
204 | } | |
205 | ||
206 | static int objagg_obj_init(struct objagg *objagg, | |
207 | struct objagg_obj *objagg_obj) | |
208 | { | |
209 | int err; | |
210 | ||
211 | /* Try to find if the object can be aggregated under an existing one. */ | |
212 | err = objagg_obj_parent_lookup_assign(objagg, objagg_obj); | |
213 | if (!err) | |
214 | return 0; | |
215 | /* If aggregation is not possible, make the object a root. */ | |
216 | return objagg_obj_root_create(objagg, objagg_obj); | |
217 | } | |
218 | ||
219 | static void objagg_obj_fini(struct objagg *objagg, | |
220 | struct objagg_obj *objagg_obj) | |
221 | { | |
222 | if (!objagg_obj_is_root(objagg_obj)) | |
223 | objagg_obj_parent_unassign(objagg, objagg_obj); | |
224 | else | |
225 | objagg_obj_root_destroy(objagg, objagg_obj); | |
226 | } | |
227 | ||
228 | static struct objagg_obj *objagg_obj_create(struct objagg *objagg, void *obj) | |
229 | { | |
230 | struct objagg_obj *objagg_obj; | |
231 | int err; | |
232 | ||
233 | objagg_obj = kzalloc(sizeof(*objagg_obj) + objagg->ops->obj_size, | |
234 | GFP_KERNEL); | |
235 | if (!objagg_obj) | |
236 | return ERR_PTR(-ENOMEM); | |
237 | objagg_obj_ref_inc(objagg_obj); | |
238 | memcpy(objagg_obj->obj, obj, objagg->ops->obj_size); | |
239 | ||
240 | err = objagg_obj_init(objagg, objagg_obj); | |
241 | if (err) | |
242 | goto err_obj_init; | |
243 | ||
244 | err = rhashtable_insert_fast(&objagg->obj_ht, &objagg_obj->ht_node, | |
245 | objagg->ht_params); | |
246 | if (err) | |
247 | goto err_ht_insert; | |
248 | list_add(&objagg_obj->list, &objagg->obj_list); | |
249 | objagg->obj_count++; | |
250 | trace_objagg_obj_create(objagg, objagg_obj); | |
251 | ||
252 | return objagg_obj; | |
253 | ||
254 | err_ht_insert: | |
255 | objagg_obj_fini(objagg, objagg_obj); | |
256 | err_obj_init: | |
257 | kfree(objagg_obj); | |
258 | return ERR_PTR(err); | |
259 | } | |
260 | ||
261 | static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj) | |
262 | { | |
263 | struct objagg_obj *objagg_obj; | |
264 | ||
265 | /* First, try to find the object exactly as user passed it, | |
266 | * perhaps it is already in use. | |
267 | */ | |
268 | objagg_obj = objagg_obj_lookup(objagg, obj); | |
269 | if (objagg_obj) { | |
270 | objagg_obj_ref_inc(objagg_obj); | |
271 | return objagg_obj; | |
272 | } | |
273 | ||
274 | return objagg_obj_create(objagg, obj); | |
275 | } | |
276 | ||
277 | /** | |
278 | * objagg_obj_get - gets an object within objagg instance | |
279 | * @objagg: objagg instance | |
280 | * @obj: user-specific private object pointer | |
281 | * | |
282 | * Note: all locking must be provided by the caller. | |
283 | * | |
284 | * Size of the "obj" memory is specified in "objagg->ops". | |
285 | * | |
286 | * There are 3 main options this function wraps: | |
287 | * 1) The object according to "obj" already exist. In that case | |
288 | * the reference counter is incrementes and the object is returned. | |
289 | * 2) The object does not exist, but it can be aggregated within | |
290 | * another object. In that case, user ops->delta_create() is called | |
291 | * to obtain delta data and a new object is created with returned | |
292 | * user-delta private pointer. | |
293 | * 3) The object does not exist and cannot be aggregated into | |
294 | * any of the existing objects. In that case, user ops->root_create() | |
295 | * is called to create the root and a new object is created with | |
296 | * returned user-root private pointer. | |
297 | * | |
298 | * Returns a pointer to objagg object instance in case of success, | |
299 | * otherwise it returns pointer error using ERR_PTR macro. | |
300 | */ | |
301 | struct objagg_obj *objagg_obj_get(struct objagg *objagg, void *obj) | |
302 | { | |
303 | struct objagg_obj *objagg_obj; | |
304 | ||
305 | objagg_obj = __objagg_obj_get(objagg, obj); | |
306 | if (IS_ERR(objagg_obj)) | |
307 | return objagg_obj; | |
308 | objagg_obj_stats_inc(objagg_obj); | |
309 | trace_objagg_obj_get(objagg, objagg_obj, objagg_obj->refcount); | |
310 | return objagg_obj; | |
311 | } | |
312 | EXPORT_SYMBOL(objagg_obj_get); | |
313 | ||
314 | static void objagg_obj_destroy(struct objagg *objagg, | |
315 | struct objagg_obj *objagg_obj) | |
316 | { | |
317 | trace_objagg_obj_destroy(objagg, objagg_obj); | |
318 | --objagg->obj_count; | |
319 | list_del(&objagg_obj->list); | |
320 | rhashtable_remove_fast(&objagg->obj_ht, &objagg_obj->ht_node, | |
321 | objagg->ht_params); | |
322 | objagg_obj_fini(objagg, objagg_obj); | |
323 | kfree(objagg_obj); | |
324 | } | |
325 | ||
326 | static void __objagg_obj_put(struct objagg *objagg, | |
327 | struct objagg_obj *objagg_obj) | |
328 | { | |
329 | if (!objagg_obj_ref_dec(objagg_obj)) | |
330 | objagg_obj_destroy(objagg, objagg_obj); | |
331 | } | |
332 | ||
333 | /** | |
334 | * objagg_obj_put - puts an object within objagg instance | |
335 | * @objagg: objagg instance | |
336 | * @objagg_obj: objagg object instance | |
337 | * | |
338 | * Note: all locking must be provided by the caller. | |
339 | * | |
340 | * Symmetric to objagg_obj_get(). | |
341 | */ | |
342 | void objagg_obj_put(struct objagg *objagg, struct objagg_obj *objagg_obj) | |
343 | { | |
344 | trace_objagg_obj_put(objagg, objagg_obj, objagg_obj->refcount); | |
345 | objagg_obj_stats_dec(objagg_obj); | |
346 | __objagg_obj_put(objagg, objagg_obj); | |
347 | } | |
348 | EXPORT_SYMBOL(objagg_obj_put); | |
349 | ||
350 | /** | |
351 | * objagg_create - creates a new objagg instance | |
352 | * @ops: user-specific callbacks | |
353 | * @priv: pointer to a private data passed to the ops | |
354 | * | |
355 | * Note: all locking must be provided by the caller. | |
356 | * | |
357 | * The purpose of the library is to provide an infrastructure to | |
358 | * aggregate user-specified objects. Library does not care about the type | |
359 | * of the object. User fills-up ops which take care of the specific | |
360 | * user object manipulation. | |
361 | * | |
362 | * As a very stupid example, consider integer numbers. For example | |
363 | * number 8 as a root object. That can aggregate number 9 with delta 1, | |
364 | * number 10 with delta 2, etc. This example is implemented as | |
365 | * a part of a testing module in test_objagg.c file. | |
366 | * | |
367 | * Each objagg instance contains multiple trees. Each tree node is | |
368 | * represented by "an object". In the current implementation there can be | |
369 | * only roots and leafs nodes. Leaf nodes are called deltas. | |
370 | * But in general, this can be easily extended for intermediate nodes. | |
371 | * In that extension, a delta would be associated with all non-root | |
372 | * nodes. | |
373 | * | |
374 | * Returns a pointer to newly created objagg instance in case of success, | |
375 | * otherwise it returns pointer error using ERR_PTR macro. | |
376 | */ | |
377 | struct objagg *objagg_create(const struct objagg_ops *ops, void *priv) | |
378 | { | |
379 | struct objagg *objagg; | |
380 | int err; | |
381 | ||
382 | if (WARN_ON(!ops || !ops->root_create || !ops->root_destroy || | |
383 | !ops->delta_create || !ops->delta_destroy)) | |
384 | return ERR_PTR(-EINVAL); | |
385 | objagg = kzalloc(sizeof(*objagg), GFP_KERNEL); | |
386 | if (!objagg) | |
387 | return ERR_PTR(-ENOMEM); | |
388 | objagg->ops = ops; | |
389 | objagg->priv = priv; | |
390 | INIT_LIST_HEAD(&objagg->obj_list); | |
391 | ||
392 | objagg->ht_params.key_len = ops->obj_size; | |
393 | objagg->ht_params.key_offset = offsetof(struct objagg_obj, obj); | |
394 | objagg->ht_params.head_offset = offsetof(struct objagg_obj, ht_node); | |
395 | ||
396 | err = rhashtable_init(&objagg->obj_ht, &objagg->ht_params); | |
397 | if (err) | |
398 | goto err_rhashtable_init; | |
399 | ||
400 | trace_objagg_create(objagg); | |
401 | return objagg; | |
402 | ||
403 | err_rhashtable_init: | |
404 | kfree(objagg); | |
405 | return ERR_PTR(err); | |
406 | } | |
407 | EXPORT_SYMBOL(objagg_create); | |
408 | ||
409 | /** | |
410 | * objagg_destroy - destroys a new objagg instance | |
411 | * @objagg: objagg instance | |
412 | * | |
413 | * Note: all locking must be provided by the caller. | |
414 | */ | |
415 | void objagg_destroy(struct objagg *objagg) | |
416 | { | |
417 | trace_objagg_destroy(objagg); | |
418 | WARN_ON(!list_empty(&objagg->obj_list)); | |
419 | rhashtable_destroy(&objagg->obj_ht); | |
420 | kfree(objagg); | |
421 | } | |
422 | EXPORT_SYMBOL(objagg_destroy); | |
423 | ||
424 | static int objagg_stats_info_sort_cmp_func(const void *a, const void *b) | |
425 | { | |
426 | const struct objagg_obj_stats_info *stats_info1 = a; | |
427 | const struct objagg_obj_stats_info *stats_info2 = b; | |
428 | ||
429 | if (stats_info1->is_root != stats_info2->is_root) | |
430 | return stats_info2->is_root - stats_info1->is_root; | |
431 | if (stats_info1->stats.delta_user_count != | |
432 | stats_info2->stats.delta_user_count) | |
433 | return stats_info2->stats.delta_user_count - | |
434 | stats_info1->stats.delta_user_count; | |
435 | return stats_info2->stats.user_count - stats_info1->stats.user_count; | |
436 | } | |
437 | ||
438 | /** | |
439 | * objagg_stats_get - obtains stats of the objagg instance | |
440 | * @objagg: objagg instance | |
441 | * | |
442 | * Note: all locking must be provided by the caller. | |
443 | * | |
444 | * The returned structure contains statistics of all object | |
445 | * currently in use, ordered by following rules: | |
446 | * 1) Root objects are always on lower indexes than the rest. | |
447 | * 2) Objects with higher delta user count are always on lower | |
448 | * indexes. | |
449 | * 3) In case more objects have the same delta user count, | |
450 | * the objects are ordered by user count. | |
451 | * | |
452 | * Returns a pointer to stats instance in case of success, | |
453 | * otherwise it returns pointer error using ERR_PTR macro. | |
454 | */ | |
455 | const struct objagg_stats *objagg_stats_get(struct objagg *objagg) | |
456 | { | |
457 | struct objagg_stats *objagg_stats; | |
458 | struct objagg_obj *objagg_obj; | |
459 | size_t alloc_size; | |
460 | int i; | |
461 | ||
462 | alloc_size = sizeof(*objagg_stats) + | |
463 | sizeof(objagg_stats->stats_info[0]) * objagg->obj_count; | |
464 | objagg_stats = kzalloc(alloc_size, GFP_KERNEL); | |
465 | if (!objagg_stats) | |
466 | return ERR_PTR(-ENOMEM); | |
467 | ||
468 | i = 0; | |
469 | list_for_each_entry(objagg_obj, &objagg->obj_list, list) { | |
470 | memcpy(&objagg_stats->stats_info[i].stats, &objagg_obj->stats, | |
471 | sizeof(objagg_stats->stats_info[0].stats)); | |
472 | objagg_stats->stats_info[i].objagg_obj = objagg_obj; | |
473 | objagg_stats->stats_info[i].is_root = | |
474 | objagg_obj_is_root(objagg_obj); | |
475 | i++; | |
476 | } | |
477 | objagg_stats->stats_info_count = i; | |
478 | ||
479 | sort(objagg_stats->stats_info, objagg_stats->stats_info_count, | |
480 | sizeof(struct objagg_obj_stats_info), | |
481 | objagg_stats_info_sort_cmp_func, NULL); | |
482 | ||
483 | return objagg_stats; | |
484 | } | |
485 | EXPORT_SYMBOL(objagg_stats_get); | |
486 | ||
487 | /** | |
488 | * objagg_stats_puts - puts stats of the objagg instance | |
489 | * @objagg_stats: objagg instance stats | |
490 | * | |
491 | * Note: all locking must be provided by the caller. | |
492 | */ | |
493 | void objagg_stats_put(const struct objagg_stats *objagg_stats) | |
494 | { | |
495 | kfree(objagg_stats); | |
496 | } | |
497 | EXPORT_SYMBOL(objagg_stats_put); | |
498 | ||
499 | MODULE_LICENSE("Dual BSD/GPL"); | |
500 | MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>"); | |
501 | MODULE_DESCRIPTION("Object aggregation manager"); |