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