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