objagg.c 28 KB

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