10a020d41SJiri Pirko // SPDX-License-Identifier: BSD-3-Clause OR GPL-2.0
20a020d41SJiri Pirko /* Copyright (c) 2018 Mellanox Technologies. All rights reserved */
30a020d41SJiri Pirko
40a020d41SJiri Pirko #include <linux/module.h>
50a020d41SJiri Pirko #include <linux/slab.h>
60a020d41SJiri Pirko #include <linux/rhashtable.h>
79069a381SJiri Pirko #include <linux/idr.h>
80a020d41SJiri Pirko #include <linux/list.h>
90a020d41SJiri Pirko #include <linux/sort.h>
100a020d41SJiri Pirko #include <linux/objagg.h>
110a020d41SJiri Pirko
120a020d41SJiri Pirko #define CREATE_TRACE_POINTS
130a020d41SJiri Pirko #include <trace/events/objagg.h>
140a020d41SJiri Pirko
159069a381SJiri Pirko struct objagg_hints {
169069a381SJiri Pirko struct rhashtable node_ht;
179069a381SJiri Pirko struct rhashtable_params ht_params;
189069a381SJiri Pirko struct list_head node_list;
199069a381SJiri Pirko unsigned int node_count;
209069a381SJiri Pirko unsigned int root_count;
219069a381SJiri Pirko unsigned int refcount;
229069a381SJiri Pirko const struct objagg_ops *ops;
239069a381SJiri Pirko };
249069a381SJiri Pirko
259069a381SJiri Pirko struct objagg_hints_node {
269069a381SJiri Pirko struct rhash_head ht_node; /* member of objagg_hints->node_ht */
279069a381SJiri Pirko struct list_head list; /* member of objagg_hints->node_list */
289069a381SJiri Pirko struct objagg_hints_node *parent;
299069a381SJiri Pirko unsigned int root_id;
309069a381SJiri Pirko struct objagg_obj_stats_info stats_info;
311f4c51deSGustavo A. R. Silva unsigned long obj[];
329069a381SJiri Pirko };
339069a381SJiri Pirko
349069a381SJiri Pirko static struct objagg_hints_node *
objagg_hints_lookup(struct objagg_hints * objagg_hints,void * obj)359069a381SJiri Pirko objagg_hints_lookup(struct objagg_hints *objagg_hints, void *obj)
369069a381SJiri Pirko {
379069a381SJiri Pirko if (!objagg_hints)
389069a381SJiri Pirko return NULL;
399069a381SJiri Pirko return rhashtable_lookup_fast(&objagg_hints->node_ht, obj,
409069a381SJiri Pirko objagg_hints->ht_params);
419069a381SJiri Pirko }
429069a381SJiri Pirko
430a020d41SJiri Pirko struct objagg {
440a020d41SJiri Pirko const struct objagg_ops *ops;
450a020d41SJiri Pirko void *priv;
460a020d41SJiri Pirko struct rhashtable obj_ht;
470a020d41SJiri Pirko struct rhashtable_params ht_params;
480a020d41SJiri Pirko struct list_head obj_list;
490a020d41SJiri Pirko unsigned int obj_count;
509069a381SJiri Pirko struct ida root_ida;
519069a381SJiri Pirko struct objagg_hints *hints;
520a020d41SJiri Pirko };
530a020d41SJiri Pirko
540a020d41SJiri Pirko struct objagg_obj {
550a020d41SJiri Pirko struct rhash_head ht_node; /* member of objagg->obj_ht */
560a020d41SJiri Pirko struct list_head list; /* member of objagg->obj_list */
570a020d41SJiri Pirko struct objagg_obj *parent; /* if the object is nested, this
580a020d41SJiri Pirko * holds pointer to parent, otherwise NULL
590a020d41SJiri Pirko */
600a020d41SJiri Pirko union {
610a020d41SJiri Pirko void *delta_priv; /* user delta private */
620a020d41SJiri Pirko void *root_priv; /* user root private */
630a020d41SJiri Pirko };
649069a381SJiri Pirko unsigned int root_id;
650a020d41SJiri Pirko unsigned int refcount; /* counts number of users of this object
660a020d41SJiri Pirko * including nested objects
670a020d41SJiri Pirko */
680a020d41SJiri Pirko struct objagg_obj_stats stats;
691f4c51deSGustavo A. R. Silva unsigned long obj[];
700a020d41SJiri Pirko };
710a020d41SJiri Pirko
objagg_obj_ref_inc(struct objagg_obj * objagg_obj)720a020d41SJiri Pirko static unsigned int objagg_obj_ref_inc(struct objagg_obj *objagg_obj)
730a020d41SJiri Pirko {
740a020d41SJiri Pirko return ++objagg_obj->refcount;
750a020d41SJiri Pirko }
760a020d41SJiri Pirko
objagg_obj_ref_dec(struct objagg_obj * objagg_obj)770a020d41SJiri Pirko static unsigned int objagg_obj_ref_dec(struct objagg_obj *objagg_obj)
780a020d41SJiri Pirko {
790a020d41SJiri Pirko return --objagg_obj->refcount;
800a020d41SJiri Pirko }
810a020d41SJiri Pirko
objagg_obj_stats_inc(struct objagg_obj * objagg_obj)820a020d41SJiri Pirko static void objagg_obj_stats_inc(struct objagg_obj *objagg_obj)
830a020d41SJiri Pirko {
840a020d41SJiri Pirko objagg_obj->stats.user_count++;
850a020d41SJiri Pirko objagg_obj->stats.delta_user_count++;
860a020d41SJiri Pirko if (objagg_obj->parent)
870a020d41SJiri Pirko objagg_obj->parent->stats.delta_user_count++;
880a020d41SJiri Pirko }
890a020d41SJiri Pirko
objagg_obj_stats_dec(struct objagg_obj * objagg_obj)900a020d41SJiri Pirko static void objagg_obj_stats_dec(struct objagg_obj *objagg_obj)
910a020d41SJiri Pirko {
920a020d41SJiri Pirko objagg_obj->stats.user_count--;
930a020d41SJiri Pirko objagg_obj->stats.delta_user_count--;
940a020d41SJiri Pirko if (objagg_obj->parent)
950a020d41SJiri Pirko objagg_obj->parent->stats.delta_user_count--;
960a020d41SJiri Pirko }
970a020d41SJiri Pirko
objagg_obj_is_root(const struct objagg_obj * objagg_obj)980a020d41SJiri Pirko static bool objagg_obj_is_root(const struct objagg_obj *objagg_obj)
990a020d41SJiri Pirko {
1000a020d41SJiri Pirko /* Nesting is not supported, so we can use ->parent
1010a020d41SJiri Pirko * to figure out if the object is root.
1020a020d41SJiri Pirko */
1030a020d41SJiri Pirko return !objagg_obj->parent;
1040a020d41SJiri Pirko }
1050a020d41SJiri Pirko
1060a020d41SJiri Pirko /**
1070a020d41SJiri Pirko * objagg_obj_root_priv - obtains root private for an object
1080a020d41SJiri Pirko * @objagg_obj: objagg object instance
1090a020d41SJiri Pirko *
1100a020d41SJiri Pirko * Note: all locking must be provided by the caller.
1110a020d41SJiri Pirko *
1120a020d41SJiri Pirko * Either the object is root itself when the private is returned
1130a020d41SJiri Pirko * directly, or the parent is root and its private is returned
1140a020d41SJiri Pirko * instead.
1150a020d41SJiri Pirko *
1160a020d41SJiri Pirko * Returns a user private root pointer.
1170a020d41SJiri Pirko */
objagg_obj_root_priv(const struct objagg_obj * objagg_obj)1180a020d41SJiri Pirko const void *objagg_obj_root_priv(const struct objagg_obj *objagg_obj)
1190a020d41SJiri Pirko {
1200a020d41SJiri Pirko if (objagg_obj_is_root(objagg_obj))
1210a020d41SJiri Pirko return objagg_obj->root_priv;
1220a020d41SJiri Pirko WARN_ON(!objagg_obj_is_root(objagg_obj->parent));
1230a020d41SJiri Pirko return objagg_obj->parent->root_priv;
1240a020d41SJiri Pirko }
1250a020d41SJiri Pirko EXPORT_SYMBOL(objagg_obj_root_priv);
1260a020d41SJiri Pirko
1270a020d41SJiri Pirko /**
1280a020d41SJiri Pirko * objagg_obj_delta_priv - obtains delta private for an object
1290a020d41SJiri Pirko * @objagg_obj: objagg object instance
1300a020d41SJiri Pirko *
1310a020d41SJiri Pirko * Note: all locking must be provided by the caller.
1320a020d41SJiri Pirko *
1330a020d41SJiri Pirko * Returns user private delta pointer or NULL in case the passed
1340a020d41SJiri Pirko * object is root.
1350a020d41SJiri Pirko */
objagg_obj_delta_priv(const struct objagg_obj * objagg_obj)1360a020d41SJiri Pirko const void *objagg_obj_delta_priv(const struct objagg_obj *objagg_obj)
1370a020d41SJiri Pirko {
1380a020d41SJiri Pirko if (objagg_obj_is_root(objagg_obj))
1390a020d41SJiri Pirko return NULL;
1400a020d41SJiri Pirko return objagg_obj->delta_priv;
1410a020d41SJiri Pirko }
1420a020d41SJiri Pirko EXPORT_SYMBOL(objagg_obj_delta_priv);
1430a020d41SJiri Pirko
1440a020d41SJiri Pirko /**
1450a020d41SJiri Pirko * objagg_obj_raw - obtains object user private pointer
1460a020d41SJiri Pirko * @objagg_obj: objagg object instance
1470a020d41SJiri Pirko *
1480a020d41SJiri Pirko * Note: all locking must be provided by the caller.
1490a020d41SJiri Pirko *
1500a020d41SJiri Pirko * Returns user private pointer as was passed to objagg_obj_get() by "obj" arg.
1510a020d41SJiri Pirko */
objagg_obj_raw(const struct objagg_obj * objagg_obj)1520a020d41SJiri Pirko const void *objagg_obj_raw(const struct objagg_obj *objagg_obj)
1530a020d41SJiri Pirko {
1540a020d41SJiri Pirko return objagg_obj->obj;
1550a020d41SJiri Pirko }
1560a020d41SJiri Pirko EXPORT_SYMBOL(objagg_obj_raw);
1570a020d41SJiri Pirko
objagg_obj_lookup(struct objagg * objagg,void * obj)1580a020d41SJiri Pirko static struct objagg_obj *objagg_obj_lookup(struct objagg *objagg, void *obj)
1590a020d41SJiri Pirko {
1600a020d41SJiri Pirko return rhashtable_lookup_fast(&objagg->obj_ht, obj, objagg->ht_params);
1610a020d41SJiri Pirko }
1620a020d41SJiri Pirko
objagg_obj_parent_assign(struct objagg * objagg,struct objagg_obj * objagg_obj,struct objagg_obj * parent,bool take_parent_ref)1630a020d41SJiri Pirko static int objagg_obj_parent_assign(struct objagg *objagg,
1640a020d41SJiri Pirko struct objagg_obj *objagg_obj,
1659069a381SJiri Pirko struct objagg_obj *parent,
1669069a381SJiri Pirko bool take_parent_ref)
1670a020d41SJiri Pirko {
1680a020d41SJiri Pirko void *delta_priv;
1690a020d41SJiri Pirko
1700a020d41SJiri Pirko delta_priv = objagg->ops->delta_create(objagg->priv, parent->obj,
1710a020d41SJiri Pirko objagg_obj->obj);
1720a020d41SJiri Pirko if (IS_ERR(delta_priv))
1730a020d41SJiri Pirko return PTR_ERR(delta_priv);
1740a020d41SJiri Pirko
1750a020d41SJiri Pirko /* User returned a delta private, that means that
1760a020d41SJiri Pirko * our object can be aggregated into the parent.
1770a020d41SJiri Pirko */
1780a020d41SJiri Pirko objagg_obj->parent = parent;
1790a020d41SJiri Pirko objagg_obj->delta_priv = delta_priv;
1809069a381SJiri Pirko if (take_parent_ref)
1810a020d41SJiri Pirko objagg_obj_ref_inc(objagg_obj->parent);
1820a020d41SJiri Pirko trace_objagg_obj_parent_assign(objagg, objagg_obj,
1830a020d41SJiri Pirko parent,
1840a020d41SJiri Pirko parent->refcount);
1850a020d41SJiri Pirko return 0;
1860a020d41SJiri Pirko }
1870a020d41SJiri Pirko
objagg_obj_parent_lookup_assign(struct objagg * objagg,struct objagg_obj * objagg_obj)1880a020d41SJiri Pirko static int objagg_obj_parent_lookup_assign(struct objagg *objagg,
1890a020d41SJiri Pirko struct objagg_obj *objagg_obj)
1900a020d41SJiri Pirko {
1910a020d41SJiri Pirko struct objagg_obj *objagg_obj_cur;
1920a020d41SJiri Pirko int err;
1930a020d41SJiri Pirko
1940a020d41SJiri Pirko list_for_each_entry(objagg_obj_cur, &objagg->obj_list, list) {
1950a020d41SJiri Pirko /* Nesting is not supported. In case the object
1960a020d41SJiri Pirko * is not root, it cannot be assigned as parent.
1970a020d41SJiri Pirko */
1980a020d41SJiri Pirko if (!objagg_obj_is_root(objagg_obj_cur))
1990a020d41SJiri Pirko continue;
2000a020d41SJiri Pirko err = objagg_obj_parent_assign(objagg, objagg_obj,
2019069a381SJiri Pirko objagg_obj_cur, true);
2020a020d41SJiri Pirko if (!err)
2030a020d41SJiri Pirko return 0;
2040a020d41SJiri Pirko }
2050a020d41SJiri Pirko return -ENOENT;
2060a020d41SJiri Pirko }
2070a020d41SJiri Pirko
2080a020d41SJiri Pirko static void __objagg_obj_put(struct objagg *objagg,
2090a020d41SJiri Pirko struct objagg_obj *objagg_obj);
2100a020d41SJiri Pirko
objagg_obj_parent_unassign(struct objagg * objagg,struct objagg_obj * objagg_obj)2110a020d41SJiri Pirko static void objagg_obj_parent_unassign(struct objagg *objagg,
2120a020d41SJiri Pirko struct objagg_obj *objagg_obj)
2130a020d41SJiri Pirko {
2140a020d41SJiri Pirko trace_objagg_obj_parent_unassign(objagg, objagg_obj,
2150a020d41SJiri Pirko objagg_obj->parent,
2160a020d41SJiri Pirko objagg_obj->parent->refcount);
2170a020d41SJiri Pirko objagg->ops->delta_destroy(objagg->priv, objagg_obj->delta_priv);
2180a020d41SJiri Pirko __objagg_obj_put(objagg, objagg_obj->parent);
2190a020d41SJiri Pirko }
2200a020d41SJiri Pirko
objagg_obj_root_id_alloc(struct objagg * objagg,struct objagg_obj * objagg_obj,struct objagg_hints_node * hnode)2219069a381SJiri Pirko static int objagg_obj_root_id_alloc(struct objagg *objagg,
2229069a381SJiri Pirko struct objagg_obj *objagg_obj,
2239069a381SJiri Pirko struct objagg_hints_node *hnode)
2249069a381SJiri Pirko {
2259069a381SJiri Pirko unsigned int min, max;
2269069a381SJiri Pirko int root_id;
2279069a381SJiri Pirko
2289069a381SJiri Pirko /* In case there are no hints available, the root id is invalid. */
2299069a381SJiri Pirko if (!objagg->hints) {
2309069a381SJiri Pirko objagg_obj->root_id = OBJAGG_OBJ_ROOT_ID_INVALID;
2319069a381SJiri Pirko return 0;
2329069a381SJiri Pirko }
2339069a381SJiri Pirko
2349069a381SJiri Pirko if (hnode) {
2359069a381SJiri Pirko min = hnode->root_id;
2369069a381SJiri Pirko max = hnode->root_id;
2379069a381SJiri Pirko } else {
2389069a381SJiri Pirko /* For objects with no hint, start after the last
2399069a381SJiri Pirko * hinted root_id.
2409069a381SJiri Pirko */
2419069a381SJiri Pirko min = objagg->hints->root_count;
2429069a381SJiri Pirko max = ~0;
2439069a381SJiri Pirko }
2449069a381SJiri Pirko
2459069a381SJiri Pirko root_id = ida_alloc_range(&objagg->root_ida, min, max, GFP_KERNEL);
2469069a381SJiri Pirko
2479069a381SJiri Pirko if (root_id < 0)
2489069a381SJiri Pirko return root_id;
2499069a381SJiri Pirko objagg_obj->root_id = root_id;
2509069a381SJiri Pirko return 0;
2519069a381SJiri Pirko }
2529069a381SJiri Pirko
objagg_obj_root_id_free(struct objagg * objagg,struct objagg_obj * objagg_obj)2539069a381SJiri Pirko static void objagg_obj_root_id_free(struct objagg *objagg,
2540a020d41SJiri Pirko struct objagg_obj *objagg_obj)
2550a020d41SJiri Pirko {
2569069a381SJiri Pirko if (!objagg->hints)
2579069a381SJiri Pirko return;
2589069a381SJiri Pirko ida_free(&objagg->root_ida, objagg_obj->root_id);
2599069a381SJiri Pirko }
2600a020d41SJiri Pirko
objagg_obj_root_create(struct objagg * objagg,struct objagg_obj * objagg_obj,struct objagg_hints_node * hnode)2619069a381SJiri Pirko static int objagg_obj_root_create(struct objagg *objagg,
2629069a381SJiri Pirko struct objagg_obj *objagg_obj,
2639069a381SJiri Pirko struct objagg_hints_node *hnode)
2649069a381SJiri Pirko {
2659069a381SJiri Pirko int err;
2669069a381SJiri Pirko
2679069a381SJiri Pirko err = objagg_obj_root_id_alloc(objagg, objagg_obj, hnode);
2689069a381SJiri Pirko if (err)
2699069a381SJiri Pirko return err;
2709069a381SJiri Pirko objagg_obj->root_priv = objagg->ops->root_create(objagg->priv,
2719069a381SJiri Pirko objagg_obj->obj,
2729069a381SJiri Pirko objagg_obj->root_id);
2739069a381SJiri Pirko if (IS_ERR(objagg_obj->root_priv)) {
2749069a381SJiri Pirko err = PTR_ERR(objagg_obj->root_priv);
2759069a381SJiri Pirko goto err_root_create;
2769069a381SJiri Pirko }
2770a020d41SJiri Pirko trace_objagg_obj_root_create(objagg, objagg_obj);
2780a020d41SJiri Pirko return 0;
2799069a381SJiri Pirko
2809069a381SJiri Pirko err_root_create:
2819069a381SJiri Pirko objagg_obj_root_id_free(objagg, objagg_obj);
2829069a381SJiri Pirko return err;
2830a020d41SJiri Pirko }
2840a020d41SJiri Pirko
objagg_obj_root_destroy(struct objagg * objagg,struct objagg_obj * objagg_obj)2850a020d41SJiri Pirko static void objagg_obj_root_destroy(struct objagg *objagg,
2860a020d41SJiri Pirko struct objagg_obj *objagg_obj)
2870a020d41SJiri Pirko {
2880a020d41SJiri Pirko trace_objagg_obj_root_destroy(objagg, objagg_obj);
2890a020d41SJiri Pirko objagg->ops->root_destroy(objagg->priv, objagg_obj->root_priv);
2909069a381SJiri Pirko objagg_obj_root_id_free(objagg, objagg_obj);
2919069a381SJiri Pirko }
2929069a381SJiri Pirko
2939069a381SJiri Pirko static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj);
2949069a381SJiri Pirko
objagg_obj_init_with_hints(struct objagg * objagg,struct objagg_obj * objagg_obj,bool * hint_found)2959069a381SJiri Pirko static int objagg_obj_init_with_hints(struct objagg *objagg,
2969069a381SJiri Pirko struct objagg_obj *objagg_obj,
2979069a381SJiri Pirko bool *hint_found)
2989069a381SJiri Pirko {
2999069a381SJiri Pirko struct objagg_hints_node *hnode;
3009069a381SJiri Pirko struct objagg_obj *parent;
3019069a381SJiri Pirko int err;
3029069a381SJiri Pirko
3039069a381SJiri Pirko hnode = objagg_hints_lookup(objagg->hints, objagg_obj->obj);
3049069a381SJiri Pirko if (!hnode) {
3059069a381SJiri Pirko *hint_found = false;
3069069a381SJiri Pirko return 0;
3079069a381SJiri Pirko }
3089069a381SJiri Pirko *hint_found = true;
3099069a381SJiri Pirko
3109069a381SJiri Pirko if (!hnode->parent)
3119069a381SJiri Pirko return objagg_obj_root_create(objagg, objagg_obj, hnode);
3129069a381SJiri Pirko
3139069a381SJiri Pirko parent = __objagg_obj_get(objagg, hnode->parent->obj);
3149069a381SJiri Pirko if (IS_ERR(parent))
3159069a381SJiri Pirko return PTR_ERR(parent);
3169069a381SJiri Pirko
3179069a381SJiri Pirko err = objagg_obj_parent_assign(objagg, objagg_obj, parent, false);
3189069a381SJiri Pirko if (err) {
3199069a381SJiri Pirko *hint_found = false;
3209069a381SJiri Pirko err = 0;
3219069a381SJiri Pirko goto err_parent_assign;
3229069a381SJiri Pirko }
3239069a381SJiri Pirko
3249069a381SJiri Pirko return 0;
3259069a381SJiri Pirko
3269069a381SJiri Pirko err_parent_assign:
3279069a381SJiri Pirko objagg_obj_put(objagg, parent);
3289069a381SJiri Pirko return err;
3290a020d41SJiri Pirko }
3300a020d41SJiri Pirko
objagg_obj_init(struct objagg * objagg,struct objagg_obj * objagg_obj)3310a020d41SJiri Pirko static int objagg_obj_init(struct objagg *objagg,
3320a020d41SJiri Pirko struct objagg_obj *objagg_obj)
3330a020d41SJiri Pirko {
3349069a381SJiri Pirko bool hint_found;
3350a020d41SJiri Pirko int err;
3360a020d41SJiri Pirko
3379069a381SJiri Pirko /* First, try to use hints if they are available and
3389069a381SJiri Pirko * if they provide result.
3399069a381SJiri Pirko */
3409069a381SJiri Pirko err = objagg_obj_init_with_hints(objagg, objagg_obj, &hint_found);
3419069a381SJiri Pirko if (err)
3429069a381SJiri Pirko return err;
3439069a381SJiri Pirko
3449069a381SJiri Pirko if (hint_found)
3459069a381SJiri Pirko return 0;
3469069a381SJiri Pirko
3470a020d41SJiri Pirko /* Try to find if the object can be aggregated under an existing one. */
3480a020d41SJiri Pirko err = objagg_obj_parent_lookup_assign(objagg, objagg_obj);
3490a020d41SJiri Pirko if (!err)
3500a020d41SJiri Pirko return 0;
3510a020d41SJiri Pirko /* If aggregation is not possible, make the object a root. */
3529069a381SJiri Pirko return objagg_obj_root_create(objagg, objagg_obj, NULL);
3530a020d41SJiri Pirko }
3540a020d41SJiri Pirko
objagg_obj_fini(struct objagg * objagg,struct objagg_obj * objagg_obj)3550a020d41SJiri Pirko static void objagg_obj_fini(struct objagg *objagg,
3560a020d41SJiri Pirko struct objagg_obj *objagg_obj)
3570a020d41SJiri Pirko {
3580a020d41SJiri Pirko if (!objagg_obj_is_root(objagg_obj))
3590a020d41SJiri Pirko objagg_obj_parent_unassign(objagg, objagg_obj);
3600a020d41SJiri Pirko else
3610a020d41SJiri Pirko objagg_obj_root_destroy(objagg, objagg_obj);
3620a020d41SJiri Pirko }
3630a020d41SJiri Pirko
objagg_obj_create(struct objagg * objagg,void * obj)3640a020d41SJiri Pirko static struct objagg_obj *objagg_obj_create(struct objagg *objagg, void *obj)
3650a020d41SJiri Pirko {
3660a020d41SJiri Pirko struct objagg_obj *objagg_obj;
3670a020d41SJiri Pirko int err;
3680a020d41SJiri Pirko
3690a020d41SJiri Pirko objagg_obj = kzalloc(sizeof(*objagg_obj) + objagg->ops->obj_size,
3700a020d41SJiri Pirko GFP_KERNEL);
3710a020d41SJiri Pirko if (!objagg_obj)
3720a020d41SJiri Pirko return ERR_PTR(-ENOMEM);
3730a020d41SJiri Pirko objagg_obj_ref_inc(objagg_obj);
3740a020d41SJiri Pirko memcpy(objagg_obj->obj, obj, objagg->ops->obj_size);
3750a020d41SJiri Pirko
3760a020d41SJiri Pirko err = objagg_obj_init(objagg, objagg_obj);
3770a020d41SJiri Pirko if (err)
3780a020d41SJiri Pirko goto err_obj_init;
3790a020d41SJiri Pirko
3800a020d41SJiri Pirko err = rhashtable_insert_fast(&objagg->obj_ht, &objagg_obj->ht_node,
3810a020d41SJiri Pirko objagg->ht_params);
3820a020d41SJiri Pirko if (err)
3830a020d41SJiri Pirko goto err_ht_insert;
3840a020d41SJiri Pirko list_add(&objagg_obj->list, &objagg->obj_list);
3850a020d41SJiri Pirko objagg->obj_count++;
3860a020d41SJiri Pirko trace_objagg_obj_create(objagg, objagg_obj);
3870a020d41SJiri Pirko
3880a020d41SJiri Pirko return objagg_obj;
3890a020d41SJiri Pirko
3900a020d41SJiri Pirko err_ht_insert:
3910a020d41SJiri Pirko objagg_obj_fini(objagg, objagg_obj);
3920a020d41SJiri Pirko err_obj_init:
3930a020d41SJiri Pirko kfree(objagg_obj);
3940a020d41SJiri Pirko return ERR_PTR(err);
3950a020d41SJiri Pirko }
3960a020d41SJiri Pirko
__objagg_obj_get(struct objagg * objagg,void * obj)3970a020d41SJiri Pirko static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj)
3980a020d41SJiri Pirko {
3990a020d41SJiri Pirko struct objagg_obj *objagg_obj;
4000a020d41SJiri Pirko
4010a020d41SJiri Pirko /* First, try to find the object exactly as user passed it,
4020a020d41SJiri Pirko * perhaps it is already in use.
4030a020d41SJiri Pirko */
4040a020d41SJiri Pirko objagg_obj = objagg_obj_lookup(objagg, obj);
4050a020d41SJiri Pirko if (objagg_obj) {
4060a020d41SJiri Pirko objagg_obj_ref_inc(objagg_obj);
4070a020d41SJiri Pirko return objagg_obj;
4080a020d41SJiri Pirko }
4090a020d41SJiri Pirko
4100a020d41SJiri Pirko return objagg_obj_create(objagg, obj);
4110a020d41SJiri Pirko }
4120a020d41SJiri Pirko
4130a020d41SJiri Pirko /**
4140a020d41SJiri Pirko * objagg_obj_get - gets an object within objagg instance
4150a020d41SJiri Pirko * @objagg: objagg instance
4160a020d41SJiri Pirko * @obj: user-specific private object pointer
4170a020d41SJiri Pirko *
4180a020d41SJiri Pirko * Note: all locking must be provided by the caller.
4190a020d41SJiri Pirko *
4200a020d41SJiri Pirko * Size of the "obj" memory is specified in "objagg->ops".
4210a020d41SJiri Pirko *
4220a020d41SJiri Pirko * There are 3 main options this function wraps:
4230a020d41SJiri Pirko * 1) The object according to "obj" already exist. In that case
4240a020d41SJiri Pirko * the reference counter is incrementes and the object is returned.
4250a020d41SJiri Pirko * 2) The object does not exist, but it can be aggregated within
4260a020d41SJiri Pirko * another object. In that case, user ops->delta_create() is called
4270a020d41SJiri Pirko * to obtain delta data and a new object is created with returned
4280a020d41SJiri Pirko * user-delta private pointer.
4290a020d41SJiri Pirko * 3) The object does not exist and cannot be aggregated into
4300a020d41SJiri Pirko * any of the existing objects. In that case, user ops->root_create()
4310a020d41SJiri Pirko * is called to create the root and a new object is created with
4320a020d41SJiri Pirko * returned user-root private pointer.
4330a020d41SJiri Pirko *
4340a020d41SJiri Pirko * Returns a pointer to objagg object instance in case of success,
4350a020d41SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro.
4360a020d41SJiri Pirko */
objagg_obj_get(struct objagg * objagg,void * obj)4370a020d41SJiri Pirko struct objagg_obj *objagg_obj_get(struct objagg *objagg, void *obj)
4380a020d41SJiri Pirko {
4390a020d41SJiri Pirko struct objagg_obj *objagg_obj;
4400a020d41SJiri Pirko
4410a020d41SJiri Pirko objagg_obj = __objagg_obj_get(objagg, obj);
4420a020d41SJiri Pirko if (IS_ERR(objagg_obj))
4430a020d41SJiri Pirko return objagg_obj;
4440a020d41SJiri Pirko objagg_obj_stats_inc(objagg_obj);
4450a020d41SJiri Pirko trace_objagg_obj_get(objagg, objagg_obj, objagg_obj->refcount);
4460a020d41SJiri Pirko return objagg_obj;
4470a020d41SJiri Pirko }
4480a020d41SJiri Pirko EXPORT_SYMBOL(objagg_obj_get);
4490a020d41SJiri Pirko
objagg_obj_destroy(struct objagg * objagg,struct objagg_obj * objagg_obj)4500a020d41SJiri Pirko static void objagg_obj_destroy(struct objagg *objagg,
4510a020d41SJiri Pirko struct objagg_obj *objagg_obj)
4520a020d41SJiri Pirko {
4530a020d41SJiri Pirko trace_objagg_obj_destroy(objagg, objagg_obj);
4540a020d41SJiri Pirko --objagg->obj_count;
4550a020d41SJiri Pirko list_del(&objagg_obj->list);
4560a020d41SJiri Pirko rhashtable_remove_fast(&objagg->obj_ht, &objagg_obj->ht_node,
4570a020d41SJiri Pirko objagg->ht_params);
4580a020d41SJiri Pirko objagg_obj_fini(objagg, objagg_obj);
4590a020d41SJiri Pirko kfree(objagg_obj);
4600a020d41SJiri Pirko }
4610a020d41SJiri Pirko
__objagg_obj_put(struct objagg * objagg,struct objagg_obj * objagg_obj)4620a020d41SJiri Pirko static void __objagg_obj_put(struct objagg *objagg,
4630a020d41SJiri Pirko struct objagg_obj *objagg_obj)
4640a020d41SJiri Pirko {
4650a020d41SJiri Pirko if (!objagg_obj_ref_dec(objagg_obj))
4660a020d41SJiri Pirko objagg_obj_destroy(objagg, objagg_obj);
4670a020d41SJiri Pirko }
4680a020d41SJiri Pirko
4690a020d41SJiri Pirko /**
4700a020d41SJiri Pirko * objagg_obj_put - puts an object within objagg instance
4710a020d41SJiri Pirko * @objagg: objagg instance
4720a020d41SJiri Pirko * @objagg_obj: objagg object instance
4730a020d41SJiri Pirko *
4740a020d41SJiri Pirko * Note: all locking must be provided by the caller.
4750a020d41SJiri Pirko *
4760a020d41SJiri Pirko * Symmetric to objagg_obj_get().
4770a020d41SJiri Pirko */
objagg_obj_put(struct objagg * objagg,struct objagg_obj * objagg_obj)4780a020d41SJiri Pirko void objagg_obj_put(struct objagg *objagg, struct objagg_obj *objagg_obj)
4790a020d41SJiri Pirko {
4800a020d41SJiri Pirko trace_objagg_obj_put(objagg, objagg_obj, objagg_obj->refcount);
4810a020d41SJiri Pirko objagg_obj_stats_dec(objagg_obj);
4820a020d41SJiri Pirko __objagg_obj_put(objagg, objagg_obj);
4830a020d41SJiri Pirko }
4840a020d41SJiri Pirko EXPORT_SYMBOL(objagg_obj_put);
4850a020d41SJiri Pirko
4860a020d41SJiri Pirko /**
4870a020d41SJiri Pirko * objagg_create - creates a new objagg instance
4880a020d41SJiri Pirko * @ops: user-specific callbacks
4899069a381SJiri Pirko * @objagg_hints: hints, can be NULL
4900a020d41SJiri Pirko * @priv: pointer to a private data passed to the ops
4910a020d41SJiri Pirko *
4920a020d41SJiri Pirko * Note: all locking must be provided by the caller.
4930a020d41SJiri Pirko *
4940a020d41SJiri Pirko * The purpose of the library is to provide an infrastructure to
4950a020d41SJiri Pirko * aggregate user-specified objects. Library does not care about the type
4960a020d41SJiri Pirko * of the object. User fills-up ops which take care of the specific
4970a020d41SJiri Pirko * user object manipulation.
4980a020d41SJiri Pirko *
4990a020d41SJiri Pirko * As a very stupid example, consider integer numbers. For example
5000a020d41SJiri Pirko * number 8 as a root object. That can aggregate number 9 with delta 1,
5010a020d41SJiri Pirko * number 10 with delta 2, etc. This example is implemented as
5020a020d41SJiri Pirko * a part of a testing module in test_objagg.c file.
5030a020d41SJiri Pirko *
5040a020d41SJiri Pirko * Each objagg instance contains multiple trees. Each tree node is
5050a020d41SJiri Pirko * represented by "an object". In the current implementation there can be
5060a020d41SJiri Pirko * only roots and leafs nodes. Leaf nodes are called deltas.
5070a020d41SJiri Pirko * But in general, this can be easily extended for intermediate nodes.
5080a020d41SJiri Pirko * In that extension, a delta would be associated with all non-root
5090a020d41SJiri Pirko * nodes.
5100a020d41SJiri Pirko *
5110a020d41SJiri Pirko * Returns a pointer to newly created objagg instance in case of success,
5120a020d41SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro.
5130a020d41SJiri Pirko */
objagg_create(const struct objagg_ops * ops,struct objagg_hints * objagg_hints,void * priv)5149069a381SJiri Pirko struct objagg *objagg_create(const struct objagg_ops *ops,
5159069a381SJiri Pirko struct objagg_hints *objagg_hints, void *priv)
5160a020d41SJiri Pirko {
5170a020d41SJiri Pirko struct objagg *objagg;
5180a020d41SJiri Pirko int err;
5190a020d41SJiri Pirko
5200a020d41SJiri Pirko if (WARN_ON(!ops || !ops->root_create || !ops->root_destroy ||
5219069a381SJiri Pirko !ops->delta_check || !ops->delta_create ||
5229069a381SJiri Pirko !ops->delta_destroy))
5230a020d41SJiri Pirko return ERR_PTR(-EINVAL);
5249069a381SJiri Pirko
5250a020d41SJiri Pirko objagg = kzalloc(sizeof(*objagg), GFP_KERNEL);
5260a020d41SJiri Pirko if (!objagg)
5270a020d41SJiri Pirko return ERR_PTR(-ENOMEM);
5280a020d41SJiri Pirko objagg->ops = ops;
5299069a381SJiri Pirko if (objagg_hints) {
5309069a381SJiri Pirko objagg->hints = objagg_hints;
5319069a381SJiri Pirko objagg_hints->refcount++;
5329069a381SJiri Pirko }
5330a020d41SJiri Pirko objagg->priv = priv;
5340a020d41SJiri Pirko INIT_LIST_HEAD(&objagg->obj_list);
5350a020d41SJiri Pirko
5360a020d41SJiri Pirko objagg->ht_params.key_len = ops->obj_size;
5370a020d41SJiri Pirko objagg->ht_params.key_offset = offsetof(struct objagg_obj, obj);
5380a020d41SJiri Pirko objagg->ht_params.head_offset = offsetof(struct objagg_obj, ht_node);
5390a020d41SJiri Pirko
5400a020d41SJiri Pirko err = rhashtable_init(&objagg->obj_ht, &objagg->ht_params);
5410a020d41SJiri Pirko if (err)
5420a020d41SJiri Pirko goto err_rhashtable_init;
5430a020d41SJiri Pirko
5449069a381SJiri Pirko ida_init(&objagg->root_ida);
5459069a381SJiri Pirko
5460a020d41SJiri Pirko trace_objagg_create(objagg);
5470a020d41SJiri Pirko return objagg;
5480a020d41SJiri Pirko
5490a020d41SJiri Pirko err_rhashtable_init:
5500a020d41SJiri Pirko kfree(objagg);
5510a020d41SJiri Pirko return ERR_PTR(err);
5520a020d41SJiri Pirko }
5530a020d41SJiri Pirko EXPORT_SYMBOL(objagg_create);
5540a020d41SJiri Pirko
5550a020d41SJiri Pirko /**
5560a020d41SJiri Pirko * objagg_destroy - destroys a new objagg instance
5570a020d41SJiri Pirko * @objagg: objagg instance
5580a020d41SJiri Pirko *
5590a020d41SJiri Pirko * Note: all locking must be provided by the caller.
5600a020d41SJiri Pirko */
objagg_destroy(struct objagg * objagg)5610a020d41SJiri Pirko void objagg_destroy(struct objagg *objagg)
5620a020d41SJiri Pirko {
5630a020d41SJiri Pirko trace_objagg_destroy(objagg);
5649069a381SJiri Pirko ida_destroy(&objagg->root_ida);
5650a020d41SJiri Pirko WARN_ON(!list_empty(&objagg->obj_list));
5660a020d41SJiri Pirko rhashtable_destroy(&objagg->obj_ht);
5679069a381SJiri Pirko if (objagg->hints)
5689069a381SJiri Pirko objagg_hints_put(objagg->hints);
5690a020d41SJiri Pirko kfree(objagg);
5700a020d41SJiri Pirko }
5710a020d41SJiri Pirko EXPORT_SYMBOL(objagg_destroy);
5720a020d41SJiri Pirko
objagg_stats_info_sort_cmp_func(const void * a,const void * b)5730a020d41SJiri Pirko static int objagg_stats_info_sort_cmp_func(const void *a, const void *b)
5740a020d41SJiri Pirko {
5750a020d41SJiri Pirko const struct objagg_obj_stats_info *stats_info1 = a;
5760a020d41SJiri Pirko const struct objagg_obj_stats_info *stats_info2 = b;
5770a020d41SJiri Pirko
5780a020d41SJiri Pirko if (stats_info1->is_root != stats_info2->is_root)
5790a020d41SJiri Pirko return stats_info2->is_root - stats_info1->is_root;
5800a020d41SJiri Pirko if (stats_info1->stats.delta_user_count !=
5810a020d41SJiri Pirko stats_info2->stats.delta_user_count)
5820a020d41SJiri Pirko return stats_info2->stats.delta_user_count -
5830a020d41SJiri Pirko stats_info1->stats.delta_user_count;
5840a020d41SJiri Pirko return stats_info2->stats.user_count - stats_info1->stats.user_count;
5850a020d41SJiri Pirko }
5860a020d41SJiri Pirko
5870a020d41SJiri Pirko /**
5880a020d41SJiri Pirko * objagg_stats_get - obtains stats of the objagg instance
5890a020d41SJiri Pirko * @objagg: objagg instance
5900a020d41SJiri Pirko *
5910a020d41SJiri Pirko * Note: all locking must be provided by the caller.
5920a020d41SJiri Pirko *
5930a020d41SJiri Pirko * The returned structure contains statistics of all object
5940a020d41SJiri Pirko * currently in use, ordered by following rules:
5950a020d41SJiri Pirko * 1) Root objects are always on lower indexes than the rest.
5960a020d41SJiri Pirko * 2) Objects with higher delta user count are always on lower
5970a020d41SJiri Pirko * indexes.
5980a020d41SJiri Pirko * 3) In case more objects have the same delta user count,
5990a020d41SJiri Pirko * the objects are ordered by user count.
6000a020d41SJiri Pirko *
6010a020d41SJiri Pirko * Returns a pointer to stats instance in case of success,
6020a020d41SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro.
6030a020d41SJiri Pirko */
objagg_stats_get(struct objagg * objagg)6040a020d41SJiri Pirko const struct objagg_stats *objagg_stats_get(struct objagg *objagg)
6050a020d41SJiri Pirko {
6060a020d41SJiri Pirko struct objagg_stats *objagg_stats;
6070a020d41SJiri Pirko struct objagg_obj *objagg_obj;
6080a020d41SJiri Pirko int i;
6090a020d41SJiri Pirko
610e736bf72SGustavo A. R. Silva objagg_stats = kzalloc(struct_size(objagg_stats, stats_info,
611e736bf72SGustavo A. R. Silva objagg->obj_count), GFP_KERNEL);
6120a020d41SJiri Pirko if (!objagg_stats)
6130a020d41SJiri Pirko return ERR_PTR(-ENOMEM);
6140a020d41SJiri Pirko
6150a020d41SJiri Pirko i = 0;
6160a020d41SJiri Pirko list_for_each_entry(objagg_obj, &objagg->obj_list, list) {
6170a020d41SJiri Pirko memcpy(&objagg_stats->stats_info[i].stats, &objagg_obj->stats,
6180a020d41SJiri Pirko sizeof(objagg_stats->stats_info[0].stats));
6190a020d41SJiri Pirko objagg_stats->stats_info[i].objagg_obj = objagg_obj;
6200a020d41SJiri Pirko objagg_stats->stats_info[i].is_root =
6210a020d41SJiri Pirko objagg_obj_is_root(objagg_obj);
622204f6a8cSJiri Pirko if (objagg_stats->stats_info[i].is_root)
623204f6a8cSJiri Pirko objagg_stats->root_count++;
6240a020d41SJiri Pirko i++;
6250a020d41SJiri Pirko }
6260a020d41SJiri Pirko objagg_stats->stats_info_count = i;
6270a020d41SJiri Pirko
6280a020d41SJiri Pirko sort(objagg_stats->stats_info, objagg_stats->stats_info_count,
6290a020d41SJiri Pirko sizeof(struct objagg_obj_stats_info),
6300a020d41SJiri Pirko objagg_stats_info_sort_cmp_func, NULL);
6310a020d41SJiri Pirko
6320a020d41SJiri Pirko return objagg_stats;
6330a020d41SJiri Pirko }
6340a020d41SJiri Pirko EXPORT_SYMBOL(objagg_stats_get);
6350a020d41SJiri Pirko
6360a020d41SJiri Pirko /**
637bb72e68bSJiri Pirko * objagg_stats_put - puts stats of the objagg instance
6380a020d41SJiri Pirko * @objagg_stats: objagg instance stats
6390a020d41SJiri Pirko *
6400a020d41SJiri Pirko * Note: all locking must be provided by the caller.
6410a020d41SJiri Pirko */
objagg_stats_put(const struct objagg_stats * objagg_stats)6420a020d41SJiri Pirko void objagg_stats_put(const struct objagg_stats *objagg_stats)
6430a020d41SJiri Pirko {
6440a020d41SJiri Pirko kfree(objagg_stats);
6450a020d41SJiri Pirko }
6460a020d41SJiri Pirko EXPORT_SYMBOL(objagg_stats_put);
6470a020d41SJiri Pirko
6489069a381SJiri Pirko static struct objagg_hints_node *
objagg_hints_node_create(struct objagg_hints * objagg_hints,struct objagg_obj * objagg_obj,size_t obj_size,struct objagg_hints_node * parent_hnode)6499069a381SJiri Pirko objagg_hints_node_create(struct objagg_hints *objagg_hints,
6509069a381SJiri Pirko struct objagg_obj *objagg_obj, size_t obj_size,
6519069a381SJiri Pirko struct objagg_hints_node *parent_hnode)
6529069a381SJiri Pirko {
6539069a381SJiri Pirko unsigned int user_count = objagg_obj->stats.user_count;
6549069a381SJiri Pirko struct objagg_hints_node *hnode;
6559069a381SJiri Pirko int err;
6569069a381SJiri Pirko
6579069a381SJiri Pirko hnode = kzalloc(sizeof(*hnode) + obj_size, GFP_KERNEL);
6589069a381SJiri Pirko if (!hnode)
6599069a381SJiri Pirko return ERR_PTR(-ENOMEM);
6609069a381SJiri Pirko memcpy(hnode->obj, &objagg_obj->obj, obj_size);
6619069a381SJiri Pirko hnode->stats_info.stats.user_count = user_count;
6629069a381SJiri Pirko hnode->stats_info.stats.delta_user_count = user_count;
6639069a381SJiri Pirko if (parent_hnode) {
6649069a381SJiri Pirko parent_hnode->stats_info.stats.delta_user_count += user_count;
6659069a381SJiri Pirko } else {
6669069a381SJiri Pirko hnode->root_id = objagg_hints->root_count++;
6679069a381SJiri Pirko hnode->stats_info.is_root = true;
6689069a381SJiri Pirko }
6699069a381SJiri Pirko hnode->stats_info.objagg_obj = objagg_obj;
6709069a381SJiri Pirko
6719069a381SJiri Pirko err = rhashtable_insert_fast(&objagg_hints->node_ht, &hnode->ht_node,
6729069a381SJiri Pirko objagg_hints->ht_params);
6739069a381SJiri Pirko if (err)
6749069a381SJiri Pirko goto err_ht_insert;
6759069a381SJiri Pirko
6769069a381SJiri Pirko list_add(&hnode->list, &objagg_hints->node_list);
6779069a381SJiri Pirko hnode->parent = parent_hnode;
6789069a381SJiri Pirko objagg_hints->node_count++;
6799069a381SJiri Pirko
6809069a381SJiri Pirko return hnode;
6819069a381SJiri Pirko
6829069a381SJiri Pirko err_ht_insert:
6839069a381SJiri Pirko kfree(hnode);
6849069a381SJiri Pirko return ERR_PTR(err);
6859069a381SJiri Pirko }
6869069a381SJiri Pirko
objagg_hints_flush(struct objagg_hints * objagg_hints)6879069a381SJiri Pirko static void objagg_hints_flush(struct objagg_hints *objagg_hints)
6889069a381SJiri Pirko {
6899069a381SJiri Pirko struct objagg_hints_node *hnode, *tmp;
6909069a381SJiri Pirko
6919069a381SJiri Pirko list_for_each_entry_safe(hnode, tmp, &objagg_hints->node_list, list) {
6929069a381SJiri Pirko list_del(&hnode->list);
6939069a381SJiri Pirko rhashtable_remove_fast(&objagg_hints->node_ht, &hnode->ht_node,
6949069a381SJiri Pirko objagg_hints->ht_params);
6959069a381SJiri Pirko kfree(hnode);
6969069a381SJiri Pirko }
6979069a381SJiri Pirko }
6989069a381SJiri Pirko
6999069a381SJiri Pirko struct objagg_tmp_node {
7009069a381SJiri Pirko struct objagg_obj *objagg_obj;
7019069a381SJiri Pirko bool crossed_out;
7029069a381SJiri Pirko };
7039069a381SJiri Pirko
7049069a381SJiri Pirko struct objagg_tmp_graph {
7059069a381SJiri Pirko struct objagg_tmp_node *nodes;
7069069a381SJiri Pirko unsigned long nodes_count;
7079069a381SJiri Pirko unsigned long *edges;
7089069a381SJiri Pirko };
7099069a381SJiri Pirko
objagg_tmp_graph_edge_index(struct objagg_tmp_graph * graph,int parent_index,int index)7109069a381SJiri Pirko static int objagg_tmp_graph_edge_index(struct objagg_tmp_graph *graph,
7119069a381SJiri Pirko int parent_index, int index)
7129069a381SJiri Pirko {
7139069a381SJiri Pirko return index * graph->nodes_count + parent_index;
7149069a381SJiri Pirko }
7159069a381SJiri Pirko
objagg_tmp_graph_edge_set(struct objagg_tmp_graph * graph,int parent_index,int index)7169069a381SJiri Pirko static void objagg_tmp_graph_edge_set(struct objagg_tmp_graph *graph,
7179069a381SJiri Pirko int parent_index, int index)
7189069a381SJiri Pirko {
7199069a381SJiri Pirko int edge_index = objagg_tmp_graph_edge_index(graph, index,
7209069a381SJiri Pirko parent_index);
7219069a381SJiri Pirko
7229069a381SJiri Pirko __set_bit(edge_index, graph->edges);
7239069a381SJiri Pirko }
7249069a381SJiri Pirko
objagg_tmp_graph_is_edge(struct objagg_tmp_graph * graph,int parent_index,int index)7259069a381SJiri Pirko static bool objagg_tmp_graph_is_edge(struct objagg_tmp_graph *graph,
7269069a381SJiri Pirko int parent_index, int index)
7279069a381SJiri Pirko {
7289069a381SJiri Pirko int edge_index = objagg_tmp_graph_edge_index(graph, index,
7299069a381SJiri Pirko parent_index);
7309069a381SJiri Pirko
7319069a381SJiri Pirko return test_bit(edge_index, graph->edges);
7329069a381SJiri Pirko }
7339069a381SJiri Pirko
objagg_tmp_graph_node_weight(struct objagg_tmp_graph * graph,unsigned int index)7349069a381SJiri Pirko static unsigned int objagg_tmp_graph_node_weight(struct objagg_tmp_graph *graph,
7359069a381SJiri Pirko unsigned int index)
7369069a381SJiri Pirko {
7379069a381SJiri Pirko struct objagg_tmp_node *node = &graph->nodes[index];
7389069a381SJiri Pirko unsigned int weight = node->objagg_obj->stats.user_count;
7399069a381SJiri Pirko int j;
7409069a381SJiri Pirko
7419069a381SJiri Pirko /* Node weight is sum of node users and all other nodes users
7429069a381SJiri Pirko * that this node can represent with delta.
7439069a381SJiri Pirko */
7449069a381SJiri Pirko
7459069a381SJiri Pirko for (j = 0; j < graph->nodes_count; j++) {
7469069a381SJiri Pirko if (!objagg_tmp_graph_is_edge(graph, index, j))
7479069a381SJiri Pirko continue;
7489069a381SJiri Pirko node = &graph->nodes[j];
7499069a381SJiri Pirko if (node->crossed_out)
7509069a381SJiri Pirko continue;
7519069a381SJiri Pirko weight += node->objagg_obj->stats.user_count;
7529069a381SJiri Pirko }
7539069a381SJiri Pirko return weight;
7549069a381SJiri Pirko }
7559069a381SJiri Pirko
objagg_tmp_graph_node_max_weight(struct objagg_tmp_graph * graph)7569069a381SJiri Pirko static int objagg_tmp_graph_node_max_weight(struct objagg_tmp_graph *graph)
7579069a381SJiri Pirko {
758fa8ba2cbSJiri Pirko struct objagg_tmp_node *node;
7599069a381SJiri Pirko unsigned int max_weight = 0;
7609069a381SJiri Pirko unsigned int weight;
7619069a381SJiri Pirko int max_index = -1;
7629069a381SJiri Pirko int i;
7639069a381SJiri Pirko
7649069a381SJiri Pirko for (i = 0; i < graph->nodes_count; i++) {
765fa8ba2cbSJiri Pirko node = &graph->nodes[i];
766fa8ba2cbSJiri Pirko if (node->crossed_out)
767fa8ba2cbSJiri Pirko continue;
7689069a381SJiri Pirko weight = objagg_tmp_graph_node_weight(graph, i);
769fa8ba2cbSJiri Pirko if (weight >= max_weight) {
7709069a381SJiri Pirko max_weight = weight;
7719069a381SJiri Pirko max_index = i;
7729069a381SJiri Pirko }
7739069a381SJiri Pirko }
7749069a381SJiri Pirko return max_index;
7759069a381SJiri Pirko }
7769069a381SJiri Pirko
objagg_tmp_graph_create(struct objagg * objagg)7779069a381SJiri Pirko static struct objagg_tmp_graph *objagg_tmp_graph_create(struct objagg *objagg)
7789069a381SJiri Pirko {
7799069a381SJiri Pirko unsigned int nodes_count = objagg->obj_count;
7809069a381SJiri Pirko struct objagg_tmp_graph *graph;
7819069a381SJiri Pirko struct objagg_tmp_node *node;
7829069a381SJiri Pirko struct objagg_tmp_node *pnode;
7839069a381SJiri Pirko struct objagg_obj *objagg_obj;
7849069a381SJiri Pirko int i, j;
7859069a381SJiri Pirko
7869069a381SJiri Pirko graph = kzalloc(sizeof(*graph), GFP_KERNEL);
7879069a381SJiri Pirko if (!graph)
7889069a381SJiri Pirko return NULL;
7899069a381SJiri Pirko
7909069a381SJiri Pirko graph->nodes = kcalloc(nodes_count, sizeof(*graph->nodes), GFP_KERNEL);
7919069a381SJiri Pirko if (!graph->nodes)
7929069a381SJiri Pirko goto err_nodes_alloc;
7939069a381SJiri Pirko graph->nodes_count = nodes_count;
7949069a381SJiri Pirko
795*7c63f26cSChristophe JAILLET graph->edges = bitmap_zalloc(nodes_count * nodes_count, GFP_KERNEL);
7969069a381SJiri Pirko if (!graph->edges)
7979069a381SJiri Pirko goto err_edges_alloc;
7989069a381SJiri Pirko
7999069a381SJiri Pirko i = 0;
8009069a381SJiri Pirko list_for_each_entry(objagg_obj, &objagg->obj_list, list) {
8019069a381SJiri Pirko node = &graph->nodes[i++];
8029069a381SJiri Pirko node->objagg_obj = objagg_obj;
8039069a381SJiri Pirko }
8049069a381SJiri Pirko
8059069a381SJiri Pirko /* Assemble a temporary graph. Insert edge X->Y in case Y can be
8069069a381SJiri Pirko * in delta of X.
8079069a381SJiri Pirko */
8089069a381SJiri Pirko for (i = 0; i < nodes_count; i++) {
8099069a381SJiri Pirko for (j = 0; j < nodes_count; j++) {
8109069a381SJiri Pirko if (i == j)
8119069a381SJiri Pirko continue;
8129069a381SJiri Pirko pnode = &graph->nodes[i];
8139069a381SJiri Pirko node = &graph->nodes[j];
8149069a381SJiri Pirko if (objagg->ops->delta_check(objagg->priv,
8159069a381SJiri Pirko pnode->objagg_obj->obj,
8169069a381SJiri Pirko node->objagg_obj->obj)) {
8179069a381SJiri Pirko objagg_tmp_graph_edge_set(graph, i, j);
8189069a381SJiri Pirko
8199069a381SJiri Pirko }
8209069a381SJiri Pirko }
8219069a381SJiri Pirko }
8229069a381SJiri Pirko return graph;
8239069a381SJiri Pirko
8249069a381SJiri Pirko err_edges_alloc:
8259069a381SJiri Pirko kfree(graph->nodes);
8269069a381SJiri Pirko err_nodes_alloc:
8279069a381SJiri Pirko kfree(graph);
8289069a381SJiri Pirko return NULL;
8299069a381SJiri Pirko }
8309069a381SJiri Pirko
objagg_tmp_graph_destroy(struct objagg_tmp_graph * graph)8319069a381SJiri Pirko static void objagg_tmp_graph_destroy(struct objagg_tmp_graph *graph)
8329069a381SJiri Pirko {
833*7c63f26cSChristophe JAILLET bitmap_free(graph->edges);
8349069a381SJiri Pirko kfree(graph->nodes);
8359069a381SJiri Pirko kfree(graph);
8369069a381SJiri Pirko }
8379069a381SJiri Pirko
8389069a381SJiri Pirko static int
objagg_opt_simple_greedy_fillup_hints(struct objagg_hints * objagg_hints,struct objagg * objagg)8399069a381SJiri Pirko objagg_opt_simple_greedy_fillup_hints(struct objagg_hints *objagg_hints,
8409069a381SJiri Pirko struct objagg *objagg)
8419069a381SJiri Pirko {
8429069a381SJiri Pirko struct objagg_hints_node *hnode, *parent_hnode;
8439069a381SJiri Pirko struct objagg_tmp_graph *graph;
8449069a381SJiri Pirko struct objagg_tmp_node *node;
8459069a381SJiri Pirko int index;
8469069a381SJiri Pirko int j;
8479069a381SJiri Pirko int err;
8489069a381SJiri Pirko
8499069a381SJiri Pirko graph = objagg_tmp_graph_create(objagg);
8509069a381SJiri Pirko if (!graph)
8519069a381SJiri Pirko return -ENOMEM;
8529069a381SJiri Pirko
8539069a381SJiri Pirko /* Find the nodes from the ones that can accommodate most users
8549069a381SJiri Pirko * and cross them out of the graph. Save them to the hint list.
8559069a381SJiri Pirko */
8569069a381SJiri Pirko while ((index = objagg_tmp_graph_node_max_weight(graph)) != -1) {
8579069a381SJiri Pirko node = &graph->nodes[index];
8589069a381SJiri Pirko node->crossed_out = true;
8599069a381SJiri Pirko hnode = objagg_hints_node_create(objagg_hints,
8609069a381SJiri Pirko node->objagg_obj,
8619069a381SJiri Pirko objagg->ops->obj_size,
8629069a381SJiri Pirko NULL);
8639069a381SJiri Pirko if (IS_ERR(hnode)) {
8649069a381SJiri Pirko err = PTR_ERR(hnode);
8659069a381SJiri Pirko goto out;
8669069a381SJiri Pirko }
8679069a381SJiri Pirko parent_hnode = hnode;
8689069a381SJiri Pirko for (j = 0; j < graph->nodes_count; j++) {
8699069a381SJiri Pirko if (!objagg_tmp_graph_is_edge(graph, index, j))
8709069a381SJiri Pirko continue;
8719069a381SJiri Pirko node = &graph->nodes[j];
8729069a381SJiri Pirko if (node->crossed_out)
8739069a381SJiri Pirko continue;
8749069a381SJiri Pirko node->crossed_out = true;
8759069a381SJiri Pirko hnode = objagg_hints_node_create(objagg_hints,
8769069a381SJiri Pirko node->objagg_obj,
8779069a381SJiri Pirko objagg->ops->obj_size,
8789069a381SJiri Pirko parent_hnode);
8799069a381SJiri Pirko if (IS_ERR(hnode)) {
8809069a381SJiri Pirko err = PTR_ERR(hnode);
8819069a381SJiri Pirko goto out;
8829069a381SJiri Pirko }
8839069a381SJiri Pirko }
8849069a381SJiri Pirko }
8859069a381SJiri Pirko
8869069a381SJiri Pirko err = 0;
8879069a381SJiri Pirko out:
8889069a381SJiri Pirko objagg_tmp_graph_destroy(graph);
8899069a381SJiri Pirko return err;
8909069a381SJiri Pirko }
8919069a381SJiri Pirko
8929069a381SJiri Pirko struct objagg_opt_algo {
8939069a381SJiri Pirko int (*fillup_hints)(struct objagg_hints *objagg_hints,
8949069a381SJiri Pirko struct objagg *objagg);
8959069a381SJiri Pirko };
8969069a381SJiri Pirko
8979069a381SJiri Pirko static const struct objagg_opt_algo objagg_opt_simple_greedy = {
8989069a381SJiri Pirko .fillup_hints = objagg_opt_simple_greedy_fillup_hints,
8999069a381SJiri Pirko };
9009069a381SJiri Pirko
9019069a381SJiri Pirko
9029069a381SJiri Pirko static const struct objagg_opt_algo *objagg_opt_algos[] = {
9039069a381SJiri Pirko [OBJAGG_OPT_ALGO_SIMPLE_GREEDY] = &objagg_opt_simple_greedy,
9049069a381SJiri Pirko };
9059069a381SJiri Pirko
objagg_hints_obj_cmp(struct rhashtable_compare_arg * arg,const void * obj)9069069a381SJiri Pirko static int objagg_hints_obj_cmp(struct rhashtable_compare_arg *arg,
9079069a381SJiri Pirko const void *obj)
9089069a381SJiri Pirko {
9099069a381SJiri Pirko struct rhashtable *ht = arg->ht;
9109069a381SJiri Pirko struct objagg_hints *objagg_hints =
9119069a381SJiri Pirko container_of(ht, struct objagg_hints, node_ht);
9129069a381SJiri Pirko const struct objagg_ops *ops = objagg_hints->ops;
9139069a381SJiri Pirko const char *ptr = obj;
9149069a381SJiri Pirko
9159069a381SJiri Pirko ptr += ht->p.key_offset;
9169069a381SJiri Pirko return ops->hints_obj_cmp ? ops->hints_obj_cmp(ptr, arg->key) :
9179069a381SJiri Pirko memcmp(ptr, arg->key, ht->p.key_len);
9189069a381SJiri Pirko }
9199069a381SJiri Pirko
9209069a381SJiri Pirko /**
9219069a381SJiri Pirko * objagg_hints_get - obtains hints instance
9229069a381SJiri Pirko * @objagg: objagg instance
9239069a381SJiri Pirko * @opt_algo_type: type of hints finding algorithm
9249069a381SJiri Pirko *
9259069a381SJiri Pirko * Note: all locking must be provided by the caller.
9269069a381SJiri Pirko *
9279069a381SJiri Pirko * According to the algo type, the existing objects of objagg instance
9289069a381SJiri Pirko * are going to be went-through to assemble an optimal tree. We call this
9299069a381SJiri Pirko * tree hints. These hints can be later on used for creation of
9309069a381SJiri Pirko * a new objagg instance. There, the future object creations are going
9319069a381SJiri Pirko * to be consulted with these hints in order to find out, where exactly
9329069a381SJiri Pirko * the new object should be put as a root or delta.
9339069a381SJiri Pirko *
9349069a381SJiri Pirko * Returns a pointer to hints instance in case of success,
9359069a381SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro.
9369069a381SJiri Pirko */
objagg_hints_get(struct objagg * objagg,enum objagg_opt_algo_type opt_algo_type)9379069a381SJiri Pirko struct objagg_hints *objagg_hints_get(struct objagg *objagg,
9389069a381SJiri Pirko enum objagg_opt_algo_type opt_algo_type)
9399069a381SJiri Pirko {
9409069a381SJiri Pirko const struct objagg_opt_algo *algo = objagg_opt_algos[opt_algo_type];
9419069a381SJiri Pirko struct objagg_hints *objagg_hints;
9429069a381SJiri Pirko int err;
9439069a381SJiri Pirko
9449069a381SJiri Pirko objagg_hints = kzalloc(sizeof(*objagg_hints), GFP_KERNEL);
9459069a381SJiri Pirko if (!objagg_hints)
9469069a381SJiri Pirko return ERR_PTR(-ENOMEM);
9479069a381SJiri Pirko
9489069a381SJiri Pirko objagg_hints->ops = objagg->ops;
9499069a381SJiri Pirko objagg_hints->refcount = 1;
9509069a381SJiri Pirko
9519069a381SJiri Pirko INIT_LIST_HEAD(&objagg_hints->node_list);
9529069a381SJiri Pirko
9539069a381SJiri Pirko objagg_hints->ht_params.key_len = objagg->ops->obj_size;
9549069a381SJiri Pirko objagg_hints->ht_params.key_offset =
9559069a381SJiri Pirko offsetof(struct objagg_hints_node, obj);
9569069a381SJiri Pirko objagg_hints->ht_params.head_offset =
9579069a381SJiri Pirko offsetof(struct objagg_hints_node, ht_node);
9589069a381SJiri Pirko objagg_hints->ht_params.obj_cmpfn = objagg_hints_obj_cmp;
9599069a381SJiri Pirko
9609069a381SJiri Pirko err = rhashtable_init(&objagg_hints->node_ht, &objagg_hints->ht_params);
9619069a381SJiri Pirko if (err)
9629069a381SJiri Pirko goto err_rhashtable_init;
9639069a381SJiri Pirko
9649069a381SJiri Pirko err = algo->fillup_hints(objagg_hints, objagg);
9659069a381SJiri Pirko if (err)
9669069a381SJiri Pirko goto err_fillup_hints;
9679069a381SJiri Pirko
9684446eb8dSDan Carpenter if (WARN_ON(objagg_hints->node_count != objagg->obj_count)) {
9694446eb8dSDan Carpenter err = -EINVAL;
9709069a381SJiri Pirko goto err_node_count_check;
9714446eb8dSDan Carpenter }
9729069a381SJiri Pirko
9739069a381SJiri Pirko return objagg_hints;
9749069a381SJiri Pirko
9759069a381SJiri Pirko err_node_count_check:
9769069a381SJiri Pirko err_fillup_hints:
9779069a381SJiri Pirko objagg_hints_flush(objagg_hints);
9789069a381SJiri Pirko rhashtable_destroy(&objagg_hints->node_ht);
9799069a381SJiri Pirko err_rhashtable_init:
9809069a381SJiri Pirko kfree(objagg_hints);
9819069a381SJiri Pirko return ERR_PTR(err);
9829069a381SJiri Pirko }
9839069a381SJiri Pirko EXPORT_SYMBOL(objagg_hints_get);
9849069a381SJiri Pirko
9859069a381SJiri Pirko /**
9869069a381SJiri Pirko * objagg_hints_put - puts hints instance
9879069a381SJiri Pirko * @objagg_hints: objagg hints instance
9889069a381SJiri Pirko *
9899069a381SJiri Pirko * Note: all locking must be provided by the caller.
9909069a381SJiri Pirko */
objagg_hints_put(struct objagg_hints * objagg_hints)9919069a381SJiri Pirko void objagg_hints_put(struct objagg_hints *objagg_hints)
9929069a381SJiri Pirko {
9939069a381SJiri Pirko if (--objagg_hints->refcount)
9949069a381SJiri Pirko return;
9959069a381SJiri Pirko objagg_hints_flush(objagg_hints);
9969069a381SJiri Pirko rhashtable_destroy(&objagg_hints->node_ht);
9979069a381SJiri Pirko kfree(objagg_hints);
9989069a381SJiri Pirko }
9999069a381SJiri Pirko EXPORT_SYMBOL(objagg_hints_put);
10009069a381SJiri Pirko
10019069a381SJiri Pirko /**
10029069a381SJiri Pirko * objagg_hints_stats_get - obtains stats of the hints instance
10039069a381SJiri Pirko * @objagg_hints: hints instance
10049069a381SJiri Pirko *
10059069a381SJiri Pirko * Note: all locking must be provided by the caller.
10069069a381SJiri Pirko *
10079069a381SJiri Pirko * The returned structure contains statistics of all objects
10089069a381SJiri Pirko * currently in use, ordered by following rules:
10099069a381SJiri Pirko * 1) Root objects are always on lower indexes than the rest.
10109069a381SJiri Pirko * 2) Objects with higher delta user count are always on lower
10119069a381SJiri Pirko * indexes.
10129069a381SJiri Pirko * 3) In case multiple objects have the same delta user count,
10139069a381SJiri Pirko * the objects are ordered by user count.
10149069a381SJiri Pirko *
10159069a381SJiri Pirko * Returns a pointer to stats instance in case of success,
10169069a381SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro.
10179069a381SJiri Pirko */
10189069a381SJiri Pirko const struct objagg_stats *
objagg_hints_stats_get(struct objagg_hints * objagg_hints)10199069a381SJiri Pirko objagg_hints_stats_get(struct objagg_hints *objagg_hints)
10209069a381SJiri Pirko {
10219069a381SJiri Pirko struct objagg_stats *objagg_stats;
10229069a381SJiri Pirko struct objagg_hints_node *hnode;
10239069a381SJiri Pirko int i;
10249069a381SJiri Pirko
10259069a381SJiri Pirko objagg_stats = kzalloc(struct_size(objagg_stats, stats_info,
10269069a381SJiri Pirko objagg_hints->node_count),
10279069a381SJiri Pirko GFP_KERNEL);
10289069a381SJiri Pirko if (!objagg_stats)
10299069a381SJiri Pirko return ERR_PTR(-ENOMEM);
10309069a381SJiri Pirko
10319069a381SJiri Pirko i = 0;
10329069a381SJiri Pirko list_for_each_entry(hnode, &objagg_hints->node_list, list) {
10339069a381SJiri Pirko memcpy(&objagg_stats->stats_info[i], &hnode->stats_info,
10349069a381SJiri Pirko sizeof(objagg_stats->stats_info[0]));
1035204f6a8cSJiri Pirko if (objagg_stats->stats_info[i].is_root)
1036204f6a8cSJiri Pirko objagg_stats->root_count++;
10379069a381SJiri Pirko i++;
10389069a381SJiri Pirko }
10399069a381SJiri Pirko objagg_stats->stats_info_count = i;
10409069a381SJiri Pirko
10419069a381SJiri Pirko sort(objagg_stats->stats_info, objagg_stats->stats_info_count,
10429069a381SJiri Pirko sizeof(struct objagg_obj_stats_info),
10439069a381SJiri Pirko objagg_stats_info_sort_cmp_func, NULL);
10449069a381SJiri Pirko
10459069a381SJiri Pirko return objagg_stats;
10469069a381SJiri Pirko }
10479069a381SJiri Pirko EXPORT_SYMBOL(objagg_hints_stats_get);
10489069a381SJiri Pirko
10490a020d41SJiri Pirko MODULE_LICENSE("Dual BSD/GPL");
10500a020d41SJiri Pirko MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
10510a020d41SJiri Pirko MODULE_DESCRIPTION("Object aggregation manager");
1052