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; 319069a381SJiri Pirko unsigned long obj[0]; 329069a381SJiri Pirko }; 339069a381SJiri Pirko 349069a381SJiri Pirko static struct objagg_hints_node * 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; 690a020d41SJiri Pirko unsigned long obj[0]; 700a020d41SJiri Pirko }; 710a020d41SJiri Pirko 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 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 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 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 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 */ 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 */ 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 */ 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 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 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 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 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 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 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 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 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 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 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 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 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 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 */ 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 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 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 */ 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 */ 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 */ 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 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 */ 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 size_t alloc_size; 6090a020d41SJiri Pirko int i; 6100a020d41SJiri Pirko 6110a020d41SJiri Pirko alloc_size = sizeof(*objagg_stats) + 6120a020d41SJiri Pirko sizeof(objagg_stats->stats_info[0]) * objagg->obj_count; 6130a020d41SJiri Pirko objagg_stats = kzalloc(alloc_size, GFP_KERNEL); 6140a020d41SJiri Pirko if (!objagg_stats) 6150a020d41SJiri Pirko return ERR_PTR(-ENOMEM); 6160a020d41SJiri Pirko 6170a020d41SJiri Pirko i = 0; 6180a020d41SJiri Pirko list_for_each_entry(objagg_obj, &objagg->obj_list, list) { 6190a020d41SJiri Pirko memcpy(&objagg_stats->stats_info[i].stats, &objagg_obj->stats, 6200a020d41SJiri Pirko sizeof(objagg_stats->stats_info[0].stats)); 6210a020d41SJiri Pirko objagg_stats->stats_info[i].objagg_obj = objagg_obj; 6220a020d41SJiri Pirko objagg_stats->stats_info[i].is_root = 6230a020d41SJiri Pirko objagg_obj_is_root(objagg_obj); 624204f6a8cSJiri Pirko if (objagg_stats->stats_info[i].is_root) 625204f6a8cSJiri Pirko objagg_stats->root_count++; 6260a020d41SJiri Pirko i++; 6270a020d41SJiri Pirko } 6280a020d41SJiri Pirko objagg_stats->stats_info_count = i; 6290a020d41SJiri Pirko 6300a020d41SJiri Pirko sort(objagg_stats->stats_info, objagg_stats->stats_info_count, 6310a020d41SJiri Pirko sizeof(struct objagg_obj_stats_info), 6320a020d41SJiri Pirko objagg_stats_info_sort_cmp_func, NULL); 6330a020d41SJiri Pirko 6340a020d41SJiri Pirko return objagg_stats; 6350a020d41SJiri Pirko } 6360a020d41SJiri Pirko EXPORT_SYMBOL(objagg_stats_get); 6370a020d41SJiri Pirko 6380a020d41SJiri Pirko /** 639bb72e68bSJiri Pirko * objagg_stats_put - puts stats of the objagg instance 6400a020d41SJiri Pirko * @objagg_stats: objagg instance stats 6410a020d41SJiri Pirko * 6420a020d41SJiri Pirko * Note: all locking must be provided by the caller. 6430a020d41SJiri Pirko */ 6440a020d41SJiri Pirko void objagg_stats_put(const struct objagg_stats *objagg_stats) 6450a020d41SJiri Pirko { 6460a020d41SJiri Pirko kfree(objagg_stats); 6470a020d41SJiri Pirko } 6480a020d41SJiri Pirko EXPORT_SYMBOL(objagg_stats_put); 6490a020d41SJiri Pirko 6509069a381SJiri Pirko static struct objagg_hints_node * 6519069a381SJiri Pirko objagg_hints_node_create(struct objagg_hints *objagg_hints, 6529069a381SJiri Pirko struct objagg_obj *objagg_obj, size_t obj_size, 6539069a381SJiri Pirko struct objagg_hints_node *parent_hnode) 6549069a381SJiri Pirko { 6559069a381SJiri Pirko unsigned int user_count = objagg_obj->stats.user_count; 6569069a381SJiri Pirko struct objagg_hints_node *hnode; 6579069a381SJiri Pirko int err; 6589069a381SJiri Pirko 6599069a381SJiri Pirko hnode = kzalloc(sizeof(*hnode) + obj_size, GFP_KERNEL); 6609069a381SJiri Pirko if (!hnode) 6619069a381SJiri Pirko return ERR_PTR(-ENOMEM); 6629069a381SJiri Pirko memcpy(hnode->obj, &objagg_obj->obj, obj_size); 6639069a381SJiri Pirko hnode->stats_info.stats.user_count = user_count; 6649069a381SJiri Pirko hnode->stats_info.stats.delta_user_count = user_count; 6659069a381SJiri Pirko if (parent_hnode) { 6669069a381SJiri Pirko parent_hnode->stats_info.stats.delta_user_count += user_count; 6679069a381SJiri Pirko } else { 6689069a381SJiri Pirko hnode->root_id = objagg_hints->root_count++; 6699069a381SJiri Pirko hnode->stats_info.is_root = true; 6709069a381SJiri Pirko } 6719069a381SJiri Pirko hnode->stats_info.objagg_obj = objagg_obj; 6729069a381SJiri Pirko 6739069a381SJiri Pirko err = rhashtable_insert_fast(&objagg_hints->node_ht, &hnode->ht_node, 6749069a381SJiri Pirko objagg_hints->ht_params); 6759069a381SJiri Pirko if (err) 6769069a381SJiri Pirko goto err_ht_insert; 6779069a381SJiri Pirko 6789069a381SJiri Pirko list_add(&hnode->list, &objagg_hints->node_list); 6799069a381SJiri Pirko hnode->parent = parent_hnode; 6809069a381SJiri Pirko objagg_hints->node_count++; 6819069a381SJiri Pirko 6829069a381SJiri Pirko return hnode; 6839069a381SJiri Pirko 6849069a381SJiri Pirko err_ht_insert: 6859069a381SJiri Pirko kfree(hnode); 6869069a381SJiri Pirko return ERR_PTR(err); 6879069a381SJiri Pirko } 6889069a381SJiri Pirko 6899069a381SJiri Pirko static void objagg_hints_flush(struct objagg_hints *objagg_hints) 6909069a381SJiri Pirko { 6919069a381SJiri Pirko struct objagg_hints_node *hnode, *tmp; 6929069a381SJiri Pirko 6939069a381SJiri Pirko list_for_each_entry_safe(hnode, tmp, &objagg_hints->node_list, list) { 6949069a381SJiri Pirko list_del(&hnode->list); 6959069a381SJiri Pirko rhashtable_remove_fast(&objagg_hints->node_ht, &hnode->ht_node, 6969069a381SJiri Pirko objagg_hints->ht_params); 6979069a381SJiri Pirko kfree(hnode); 6989069a381SJiri Pirko } 6999069a381SJiri Pirko } 7009069a381SJiri Pirko 7019069a381SJiri Pirko struct objagg_tmp_node { 7029069a381SJiri Pirko struct objagg_obj *objagg_obj; 7039069a381SJiri Pirko bool crossed_out; 7049069a381SJiri Pirko }; 7059069a381SJiri Pirko 7069069a381SJiri Pirko struct objagg_tmp_graph { 7079069a381SJiri Pirko struct objagg_tmp_node *nodes; 7089069a381SJiri Pirko unsigned long nodes_count; 7099069a381SJiri Pirko unsigned long *edges; 7109069a381SJiri Pirko }; 7119069a381SJiri Pirko 7129069a381SJiri Pirko static int objagg_tmp_graph_edge_index(struct objagg_tmp_graph *graph, 7139069a381SJiri Pirko int parent_index, int index) 7149069a381SJiri Pirko { 7159069a381SJiri Pirko return index * graph->nodes_count + parent_index; 7169069a381SJiri Pirko } 7179069a381SJiri Pirko 7189069a381SJiri Pirko static void objagg_tmp_graph_edge_set(struct objagg_tmp_graph *graph, 7199069a381SJiri Pirko int parent_index, int index) 7209069a381SJiri Pirko { 7219069a381SJiri Pirko int edge_index = objagg_tmp_graph_edge_index(graph, index, 7229069a381SJiri Pirko parent_index); 7239069a381SJiri Pirko 7249069a381SJiri Pirko __set_bit(edge_index, graph->edges); 7259069a381SJiri Pirko } 7269069a381SJiri Pirko 7279069a381SJiri Pirko static bool objagg_tmp_graph_is_edge(struct objagg_tmp_graph *graph, 7289069a381SJiri Pirko int parent_index, int index) 7299069a381SJiri Pirko { 7309069a381SJiri Pirko int edge_index = objagg_tmp_graph_edge_index(graph, index, 7319069a381SJiri Pirko parent_index); 7329069a381SJiri Pirko 7339069a381SJiri Pirko return test_bit(edge_index, graph->edges); 7349069a381SJiri Pirko } 7359069a381SJiri Pirko 7369069a381SJiri Pirko static unsigned int objagg_tmp_graph_node_weight(struct objagg_tmp_graph *graph, 7379069a381SJiri Pirko unsigned int index) 7389069a381SJiri Pirko { 7399069a381SJiri Pirko struct objagg_tmp_node *node = &graph->nodes[index]; 7409069a381SJiri Pirko unsigned int weight = node->objagg_obj->stats.user_count; 7419069a381SJiri Pirko int j; 7429069a381SJiri Pirko 7439069a381SJiri Pirko /* Node weight is sum of node users and all other nodes users 7449069a381SJiri Pirko * that this node can represent with delta. 7459069a381SJiri Pirko */ 7469069a381SJiri Pirko 7479069a381SJiri Pirko if (node->crossed_out) 7489069a381SJiri Pirko return 0; 7499069a381SJiri Pirko for (j = 0; j < graph->nodes_count; j++) { 7509069a381SJiri Pirko if (!objagg_tmp_graph_is_edge(graph, index, j)) 7519069a381SJiri Pirko continue; 7529069a381SJiri Pirko node = &graph->nodes[j]; 7539069a381SJiri Pirko if (node->crossed_out) 7549069a381SJiri Pirko continue; 7559069a381SJiri Pirko weight += node->objagg_obj->stats.user_count; 7569069a381SJiri Pirko } 7579069a381SJiri Pirko return weight; 7589069a381SJiri Pirko } 7599069a381SJiri Pirko 7609069a381SJiri Pirko static int objagg_tmp_graph_node_max_weight(struct objagg_tmp_graph *graph) 7619069a381SJiri Pirko { 7629069a381SJiri Pirko unsigned int max_weight = 0; 7639069a381SJiri Pirko unsigned int weight; 7649069a381SJiri Pirko int max_index = -1; 7659069a381SJiri Pirko int i; 7669069a381SJiri Pirko 7679069a381SJiri Pirko for (i = 0; i < graph->nodes_count; i++) { 7689069a381SJiri Pirko weight = objagg_tmp_graph_node_weight(graph, i); 7699069a381SJiri 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 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 size_t alloc_size; 7859069a381SJiri Pirko int i, j; 7869069a381SJiri Pirko 7879069a381SJiri Pirko graph = kzalloc(sizeof(*graph), GFP_KERNEL); 7889069a381SJiri Pirko if (!graph) 7899069a381SJiri Pirko return NULL; 7909069a381SJiri Pirko 7919069a381SJiri Pirko graph->nodes = kcalloc(nodes_count, sizeof(*graph->nodes), GFP_KERNEL); 7929069a381SJiri Pirko if (!graph->nodes) 7939069a381SJiri Pirko goto err_nodes_alloc; 7949069a381SJiri Pirko graph->nodes_count = nodes_count; 7959069a381SJiri Pirko 7969069a381SJiri Pirko alloc_size = BITS_TO_LONGS(nodes_count * nodes_count) * 7979069a381SJiri Pirko sizeof(unsigned long); 7989069a381SJiri Pirko graph->edges = kzalloc(alloc_size, GFP_KERNEL); 7999069a381SJiri Pirko if (!graph->edges) 8009069a381SJiri Pirko goto err_edges_alloc; 8019069a381SJiri Pirko 8029069a381SJiri Pirko i = 0; 8039069a381SJiri Pirko list_for_each_entry(objagg_obj, &objagg->obj_list, list) { 8049069a381SJiri Pirko node = &graph->nodes[i++]; 8059069a381SJiri Pirko node->objagg_obj = objagg_obj; 8069069a381SJiri Pirko } 8079069a381SJiri Pirko 8089069a381SJiri Pirko /* Assemble a temporary graph. Insert edge X->Y in case Y can be 8099069a381SJiri Pirko * in delta of X. 8109069a381SJiri Pirko */ 8119069a381SJiri Pirko for (i = 0; i < nodes_count; i++) { 8129069a381SJiri Pirko for (j = 0; j < nodes_count; j++) { 8139069a381SJiri Pirko if (i == j) 8149069a381SJiri Pirko continue; 8159069a381SJiri Pirko pnode = &graph->nodes[i]; 8169069a381SJiri Pirko node = &graph->nodes[j]; 8179069a381SJiri Pirko if (objagg->ops->delta_check(objagg->priv, 8189069a381SJiri Pirko pnode->objagg_obj->obj, 8199069a381SJiri Pirko node->objagg_obj->obj)) { 8209069a381SJiri Pirko objagg_tmp_graph_edge_set(graph, i, j); 8219069a381SJiri Pirko 8229069a381SJiri Pirko } 8239069a381SJiri Pirko } 8249069a381SJiri Pirko } 8259069a381SJiri Pirko return graph; 8269069a381SJiri Pirko 8279069a381SJiri Pirko err_edges_alloc: 8289069a381SJiri Pirko kfree(graph->nodes); 8299069a381SJiri Pirko err_nodes_alloc: 8309069a381SJiri Pirko kfree(graph); 8319069a381SJiri Pirko return NULL; 8329069a381SJiri Pirko } 8339069a381SJiri Pirko 8349069a381SJiri Pirko static void objagg_tmp_graph_destroy(struct objagg_tmp_graph *graph) 8359069a381SJiri Pirko { 8369069a381SJiri Pirko kfree(graph->edges); 8379069a381SJiri Pirko kfree(graph->nodes); 8389069a381SJiri Pirko kfree(graph); 8399069a381SJiri Pirko } 8409069a381SJiri Pirko 8419069a381SJiri Pirko static int 8429069a381SJiri Pirko objagg_opt_simple_greedy_fillup_hints(struct objagg_hints *objagg_hints, 8439069a381SJiri Pirko struct objagg *objagg) 8449069a381SJiri Pirko { 8459069a381SJiri Pirko struct objagg_hints_node *hnode, *parent_hnode; 8469069a381SJiri Pirko struct objagg_tmp_graph *graph; 8479069a381SJiri Pirko struct objagg_tmp_node *node; 8489069a381SJiri Pirko int index; 8499069a381SJiri Pirko int j; 8509069a381SJiri Pirko int err; 8519069a381SJiri Pirko 8529069a381SJiri Pirko graph = objagg_tmp_graph_create(objagg); 8539069a381SJiri Pirko if (!graph) 8549069a381SJiri Pirko return -ENOMEM; 8559069a381SJiri Pirko 8569069a381SJiri Pirko /* Find the nodes from the ones that can accommodate most users 8579069a381SJiri Pirko * and cross them out of the graph. Save them to the hint list. 8589069a381SJiri Pirko */ 8599069a381SJiri Pirko while ((index = objagg_tmp_graph_node_max_weight(graph)) != -1) { 8609069a381SJiri Pirko node = &graph->nodes[index]; 8619069a381SJiri Pirko node->crossed_out = true; 8629069a381SJiri Pirko hnode = objagg_hints_node_create(objagg_hints, 8639069a381SJiri Pirko node->objagg_obj, 8649069a381SJiri Pirko objagg->ops->obj_size, 8659069a381SJiri Pirko NULL); 8669069a381SJiri Pirko if (IS_ERR(hnode)) { 8679069a381SJiri Pirko err = PTR_ERR(hnode); 8689069a381SJiri Pirko goto out; 8699069a381SJiri Pirko } 8709069a381SJiri Pirko parent_hnode = hnode; 8719069a381SJiri Pirko for (j = 0; j < graph->nodes_count; j++) { 8729069a381SJiri Pirko if (!objagg_tmp_graph_is_edge(graph, index, j)) 8739069a381SJiri Pirko continue; 8749069a381SJiri Pirko node = &graph->nodes[j]; 8759069a381SJiri Pirko if (node->crossed_out) 8769069a381SJiri Pirko continue; 8779069a381SJiri Pirko node->crossed_out = true; 8789069a381SJiri Pirko hnode = objagg_hints_node_create(objagg_hints, 8799069a381SJiri Pirko node->objagg_obj, 8809069a381SJiri Pirko objagg->ops->obj_size, 8819069a381SJiri Pirko parent_hnode); 8829069a381SJiri Pirko if (IS_ERR(hnode)) { 8839069a381SJiri Pirko err = PTR_ERR(hnode); 8849069a381SJiri Pirko goto out; 8859069a381SJiri Pirko } 8869069a381SJiri Pirko } 8879069a381SJiri Pirko } 8889069a381SJiri Pirko 8899069a381SJiri Pirko err = 0; 8909069a381SJiri Pirko out: 8919069a381SJiri Pirko objagg_tmp_graph_destroy(graph); 8929069a381SJiri Pirko return err; 8939069a381SJiri Pirko } 8949069a381SJiri Pirko 8959069a381SJiri Pirko struct objagg_opt_algo { 8969069a381SJiri Pirko int (*fillup_hints)(struct objagg_hints *objagg_hints, 8979069a381SJiri Pirko struct objagg *objagg); 8989069a381SJiri Pirko }; 8999069a381SJiri Pirko 9009069a381SJiri Pirko static const struct objagg_opt_algo objagg_opt_simple_greedy = { 9019069a381SJiri Pirko .fillup_hints = objagg_opt_simple_greedy_fillup_hints, 9029069a381SJiri Pirko }; 9039069a381SJiri Pirko 9049069a381SJiri Pirko 9059069a381SJiri Pirko static const struct objagg_opt_algo *objagg_opt_algos[] = { 9069069a381SJiri Pirko [OBJAGG_OPT_ALGO_SIMPLE_GREEDY] = &objagg_opt_simple_greedy, 9079069a381SJiri Pirko }; 9089069a381SJiri Pirko 9099069a381SJiri Pirko static int objagg_hints_obj_cmp(struct rhashtable_compare_arg *arg, 9109069a381SJiri Pirko const void *obj) 9119069a381SJiri Pirko { 9129069a381SJiri Pirko struct rhashtable *ht = arg->ht; 9139069a381SJiri Pirko struct objagg_hints *objagg_hints = 9149069a381SJiri Pirko container_of(ht, struct objagg_hints, node_ht); 9159069a381SJiri Pirko const struct objagg_ops *ops = objagg_hints->ops; 9169069a381SJiri Pirko const char *ptr = obj; 9179069a381SJiri Pirko 9189069a381SJiri Pirko ptr += ht->p.key_offset; 9199069a381SJiri Pirko return ops->hints_obj_cmp ? ops->hints_obj_cmp(ptr, arg->key) : 9209069a381SJiri Pirko memcmp(ptr, arg->key, ht->p.key_len); 9219069a381SJiri Pirko } 9229069a381SJiri Pirko 9239069a381SJiri Pirko /** 9249069a381SJiri Pirko * objagg_hints_get - obtains hints instance 9259069a381SJiri Pirko * @objagg: objagg instance 9269069a381SJiri Pirko * @opt_algo_type: type of hints finding algorithm 9279069a381SJiri Pirko * 9289069a381SJiri Pirko * Note: all locking must be provided by the caller. 9299069a381SJiri Pirko * 9309069a381SJiri Pirko * According to the algo type, the existing objects of objagg instance 9319069a381SJiri Pirko * are going to be went-through to assemble an optimal tree. We call this 9329069a381SJiri Pirko * tree hints. These hints can be later on used for creation of 9339069a381SJiri Pirko * a new objagg instance. There, the future object creations are going 9349069a381SJiri Pirko * to be consulted with these hints in order to find out, where exactly 9359069a381SJiri Pirko * the new object should be put as a root or delta. 9369069a381SJiri Pirko * 9379069a381SJiri Pirko * Returns a pointer to hints instance in case of success, 9389069a381SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro. 9399069a381SJiri Pirko */ 9409069a381SJiri Pirko struct objagg_hints *objagg_hints_get(struct objagg *objagg, 9419069a381SJiri Pirko enum objagg_opt_algo_type opt_algo_type) 9429069a381SJiri Pirko { 9439069a381SJiri Pirko const struct objagg_opt_algo *algo = objagg_opt_algos[opt_algo_type]; 9449069a381SJiri Pirko struct objagg_hints *objagg_hints; 9459069a381SJiri Pirko int err; 9469069a381SJiri Pirko 9479069a381SJiri Pirko objagg_hints = kzalloc(sizeof(*objagg_hints), GFP_KERNEL); 9489069a381SJiri Pirko if (!objagg_hints) 9499069a381SJiri Pirko return ERR_PTR(-ENOMEM); 9509069a381SJiri Pirko 9519069a381SJiri Pirko objagg_hints->ops = objagg->ops; 9529069a381SJiri Pirko objagg_hints->refcount = 1; 9539069a381SJiri Pirko 9549069a381SJiri Pirko INIT_LIST_HEAD(&objagg_hints->node_list); 9559069a381SJiri Pirko 9569069a381SJiri Pirko objagg_hints->ht_params.key_len = objagg->ops->obj_size; 9579069a381SJiri Pirko objagg_hints->ht_params.key_offset = 9589069a381SJiri Pirko offsetof(struct objagg_hints_node, obj); 9599069a381SJiri Pirko objagg_hints->ht_params.head_offset = 9609069a381SJiri Pirko offsetof(struct objagg_hints_node, ht_node); 9619069a381SJiri Pirko objagg_hints->ht_params.obj_cmpfn = objagg_hints_obj_cmp; 9629069a381SJiri Pirko 9639069a381SJiri Pirko err = rhashtable_init(&objagg_hints->node_ht, &objagg_hints->ht_params); 9649069a381SJiri Pirko if (err) 9659069a381SJiri Pirko goto err_rhashtable_init; 9669069a381SJiri Pirko 9679069a381SJiri Pirko err = algo->fillup_hints(objagg_hints, objagg); 9689069a381SJiri Pirko if (err) 9699069a381SJiri Pirko goto err_fillup_hints; 9709069a381SJiri Pirko 9714446eb8dSDan Carpenter if (WARN_ON(objagg_hints->node_count != objagg->obj_count)) { 9724446eb8dSDan Carpenter err = -EINVAL; 9739069a381SJiri Pirko goto err_node_count_check; 9744446eb8dSDan Carpenter } 9759069a381SJiri Pirko 9769069a381SJiri Pirko return objagg_hints; 9779069a381SJiri Pirko 9789069a381SJiri Pirko err_node_count_check: 9799069a381SJiri Pirko err_fillup_hints: 9809069a381SJiri Pirko objagg_hints_flush(objagg_hints); 9819069a381SJiri Pirko rhashtable_destroy(&objagg_hints->node_ht); 9829069a381SJiri Pirko err_rhashtable_init: 9839069a381SJiri Pirko kfree(objagg_hints); 9849069a381SJiri Pirko return ERR_PTR(err); 9859069a381SJiri Pirko } 9869069a381SJiri Pirko EXPORT_SYMBOL(objagg_hints_get); 9879069a381SJiri Pirko 9889069a381SJiri Pirko /** 9899069a381SJiri Pirko * objagg_hints_put - puts hints instance 9909069a381SJiri Pirko * @objagg_hints: objagg hints instance 9919069a381SJiri Pirko * 9929069a381SJiri Pirko * Note: all locking must be provided by the caller. 9939069a381SJiri Pirko */ 9949069a381SJiri Pirko void objagg_hints_put(struct objagg_hints *objagg_hints) 9959069a381SJiri Pirko { 9969069a381SJiri Pirko if (--objagg_hints->refcount) 9979069a381SJiri Pirko return; 9989069a381SJiri Pirko objagg_hints_flush(objagg_hints); 9999069a381SJiri Pirko rhashtable_destroy(&objagg_hints->node_ht); 10009069a381SJiri Pirko kfree(objagg_hints); 10019069a381SJiri Pirko } 10029069a381SJiri Pirko EXPORT_SYMBOL(objagg_hints_put); 10039069a381SJiri Pirko 10049069a381SJiri Pirko /** 10059069a381SJiri Pirko * objagg_hints_stats_get - obtains stats of the hints instance 10069069a381SJiri Pirko * @objagg_hints: hints instance 10079069a381SJiri Pirko * 10089069a381SJiri Pirko * Note: all locking must be provided by the caller. 10099069a381SJiri Pirko * 10109069a381SJiri Pirko * The returned structure contains statistics of all objects 10119069a381SJiri Pirko * currently in use, ordered by following rules: 10129069a381SJiri Pirko * 1) Root objects are always on lower indexes than the rest. 10139069a381SJiri Pirko * 2) Objects with higher delta user count are always on lower 10149069a381SJiri Pirko * indexes. 10159069a381SJiri Pirko * 3) In case multiple objects have the same delta user count, 10169069a381SJiri Pirko * the objects are ordered by user count. 10179069a381SJiri Pirko * 10189069a381SJiri Pirko * Returns a pointer to stats instance in case of success, 10199069a381SJiri Pirko * otherwise it returns pointer error using ERR_PTR macro. 10209069a381SJiri Pirko */ 10219069a381SJiri Pirko const struct objagg_stats * 10229069a381SJiri Pirko objagg_hints_stats_get(struct objagg_hints *objagg_hints) 10239069a381SJiri Pirko { 10249069a381SJiri Pirko struct objagg_stats *objagg_stats; 10259069a381SJiri Pirko struct objagg_hints_node *hnode; 10269069a381SJiri Pirko int i; 10279069a381SJiri Pirko 10289069a381SJiri Pirko objagg_stats = kzalloc(struct_size(objagg_stats, stats_info, 10299069a381SJiri Pirko objagg_hints->node_count), 10309069a381SJiri Pirko GFP_KERNEL); 10319069a381SJiri Pirko if (!objagg_stats) 10329069a381SJiri Pirko return ERR_PTR(-ENOMEM); 10339069a381SJiri Pirko 10349069a381SJiri Pirko i = 0; 10359069a381SJiri Pirko list_for_each_entry(hnode, &objagg_hints->node_list, list) { 10369069a381SJiri Pirko memcpy(&objagg_stats->stats_info[i], &hnode->stats_info, 10379069a381SJiri Pirko sizeof(objagg_stats->stats_info[0])); 1038204f6a8cSJiri Pirko if (objagg_stats->stats_info[i].is_root) 1039204f6a8cSJiri Pirko objagg_stats->root_count++; 10409069a381SJiri Pirko i++; 10419069a381SJiri Pirko } 10429069a381SJiri Pirko objagg_stats->stats_info_count = i; 10439069a381SJiri Pirko 10449069a381SJiri Pirko sort(objagg_stats->stats_info, objagg_stats->stats_info_count, 10459069a381SJiri Pirko sizeof(struct objagg_obj_stats_info), 10469069a381SJiri Pirko objagg_stats_info_sort_cmp_func, NULL); 10479069a381SJiri Pirko 10489069a381SJiri Pirko return objagg_stats; 10499069a381SJiri Pirko } 10509069a381SJiri Pirko EXPORT_SYMBOL(objagg_hints_stats_get); 10519069a381SJiri Pirko 10520a020d41SJiri Pirko MODULE_LICENSE("Dual BSD/GPL"); 10530a020d41SJiri Pirko MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>"); 10540a020d41SJiri Pirko MODULE_DESCRIPTION("Object aggregation manager"); 1055