This source file includes following definitions.
- objagg_hints_lookup
- objagg_obj_ref_inc
- objagg_obj_ref_dec
- objagg_obj_stats_inc
- objagg_obj_stats_dec
- objagg_obj_is_root
- objagg_obj_root_priv
- objagg_obj_delta_priv
- objagg_obj_raw
- objagg_obj_lookup
- objagg_obj_parent_assign
- objagg_obj_parent_lookup_assign
- objagg_obj_parent_unassign
- objagg_obj_root_id_alloc
- objagg_obj_root_id_free
- objagg_obj_root_create
- objagg_obj_root_destroy
- objagg_obj_init_with_hints
- objagg_obj_init
- objagg_obj_fini
- objagg_obj_create
- __objagg_obj_get
- objagg_obj_get
- objagg_obj_destroy
- __objagg_obj_put
- objagg_obj_put
- objagg_create
- objagg_destroy
- objagg_stats_info_sort_cmp_func
- objagg_stats_get
- objagg_stats_put
- objagg_hints_node_create
- objagg_hints_flush
- objagg_tmp_graph_edge_index
- objagg_tmp_graph_edge_set
- objagg_tmp_graph_is_edge
- objagg_tmp_graph_node_weight
- objagg_tmp_graph_node_max_weight
- objagg_tmp_graph_create
- objagg_tmp_graph_destroy
- objagg_opt_simple_greedy_fillup_hints
- objagg_hints_obj_cmp
- objagg_hints_get
- objagg_hints_put
- objagg_hints_stats_get
1
2
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;
27 struct list_head list;
28 struct objagg_hints_node *parent;
29 unsigned int root_id;
30 struct objagg_obj_stats_info stats_info;
31 unsigned long obj[0];
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;
56 struct list_head list;
57 struct objagg_obj *parent;
58
59
60 union {
61 void *delta_priv;
62 void *root_priv;
63 };
64 unsigned int root_id;
65 unsigned int refcount;
66
67
68 struct objagg_obj_stats stats;
69 unsigned long obj[0];
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
101
102
103 return !objagg_obj->parent;
104 }
105
106
107
108
109
110
111
112
113
114
115
116
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
129
130
131
132
133
134
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
146
147
148
149
150
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 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
176
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
188 static 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
196
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
208 static void __objagg_obj_put(struct objagg *objagg,
209 struct objagg_obj *objagg_obj);
210
211 static 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
221 static 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
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
239
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
253 static 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
261 static 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
280 err_root_create:
281 objagg_obj_root_id_free(objagg, objagg_obj);
282 return err;
283 }
284
285 static 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
293 static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj);
294
295 static 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
326 err_parent_assign:
327 objagg_obj_put(objagg, parent);
328 return err;
329 }
330
331 static int objagg_obj_init(struct objagg *objagg,
332 struct objagg_obj *objagg_obj)
333 {
334 bool hint_found;
335 int err;
336
337
338
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
348 err = objagg_obj_parent_lookup_assign(objagg, objagg_obj);
349 if (!err)
350 return 0;
351
352 return objagg_obj_root_create(objagg, objagg_obj, NULL);
353 }
354
355 static 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
364 static 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
390 err_ht_insert:
391 objagg_obj_fini(objagg, objagg_obj);
392 err_obj_init:
393 kfree(objagg_obj);
394 return ERR_PTR(err);
395 }
396
397 static struct objagg_obj *__objagg_obj_get(struct objagg *objagg, void *obj)
398 {
399 struct objagg_obj *objagg_obj;
400
401
402
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
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437 struct 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 }
448 EXPORT_SYMBOL(objagg_obj_get);
449
450 static 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
462 static 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
471
472
473
474
475
476
477
478 void 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 }
484 EXPORT_SYMBOL(objagg_obj_put);
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514 struct 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
549 err_rhashtable_init:
550 kfree(objagg);
551 return ERR_PTR(err);
552 }
553 EXPORT_SYMBOL(objagg_create);
554
555
556
557
558
559
560
561 void 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 }
571 EXPORT_SYMBOL(objagg_destroy);
572
573 static 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
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604 const 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 }
634 EXPORT_SYMBOL(objagg_stats_get);
635
636
637
638
639
640
641
642 void objagg_stats_put(const struct objagg_stats *objagg_stats)
643 {
644 kfree(objagg_stats);
645 }
646 EXPORT_SYMBOL(objagg_stats_put);
647
648 static struct objagg_hints_node *
649 objagg_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
682 err_ht_insert:
683 kfree(hnode);
684 return ERR_PTR(err);
685 }
686
687 static 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
699 struct objagg_tmp_node {
700 struct objagg_obj *objagg_obj;
701 bool crossed_out;
702 };
703
704 struct objagg_tmp_graph {
705 struct objagg_tmp_node *nodes;
706 unsigned long nodes_count;
707 unsigned long *edges;
708 };
709
710 static 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
716 static 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
725 static 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
734 static 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
742
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
756 static 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
777 static 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 size_t alloc_size;
785 int i, j;
786
787 graph = kzalloc(sizeof(*graph), GFP_KERNEL);
788 if (!graph)
789 return NULL;
790
791 graph->nodes = kcalloc(nodes_count, sizeof(*graph->nodes), GFP_KERNEL);
792 if (!graph->nodes)
793 goto err_nodes_alloc;
794 graph->nodes_count = nodes_count;
795
796 alloc_size = BITS_TO_LONGS(nodes_count * nodes_count) *
797 sizeof(unsigned long);
798 graph->edges = kzalloc(alloc_size, 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
809
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 kfree(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
857
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 static int objagg_hints_obj_cmp(struct rhashtable_compare_arg *arg,
910 const void *obj)
911 {
912 struct rhashtable *ht = arg->ht;
913 struct objagg_hints *objagg_hints =
914 container_of(ht, struct objagg_hints, node_ht);
915 const struct objagg_ops *ops = objagg_hints->ops;
916 const char *ptr = obj;
917
918 ptr += ht->p.key_offset;
919 return ops->hints_obj_cmp ? ops->hints_obj_cmp(ptr, arg->key) :
920 memcmp(ptr, arg->key, ht->p.key_len);
921 }
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940 struct objagg_hints *objagg_hints_get(struct objagg *objagg,
941 enum objagg_opt_algo_type opt_algo_type)
942 {
943 const struct objagg_opt_algo *algo = objagg_opt_algos[opt_algo_type];
944 struct objagg_hints *objagg_hints;
945 int err;
946
947 objagg_hints = kzalloc(sizeof(*objagg_hints), GFP_KERNEL);
948 if (!objagg_hints)
949 return ERR_PTR(-ENOMEM);
950
951 objagg_hints->ops = objagg->ops;
952 objagg_hints->refcount = 1;
953
954 INIT_LIST_HEAD(&objagg_hints->node_list);
955
956 objagg_hints->ht_params.key_len = objagg->ops->obj_size;
957 objagg_hints->ht_params.key_offset =
958 offsetof(struct objagg_hints_node, obj);
959 objagg_hints->ht_params.head_offset =
960 offsetof(struct objagg_hints_node, ht_node);
961 objagg_hints->ht_params.obj_cmpfn = objagg_hints_obj_cmp;
962
963 err = rhashtable_init(&objagg_hints->node_ht, &objagg_hints->ht_params);
964 if (err)
965 goto err_rhashtable_init;
966
967 err = algo->fillup_hints(objagg_hints, objagg);
968 if (err)
969 goto err_fillup_hints;
970
971 if (WARN_ON(objagg_hints->node_count != objagg->obj_count)) {
972 err = -EINVAL;
973 goto err_node_count_check;
974 }
975
976 return objagg_hints;
977
978 err_node_count_check:
979 err_fillup_hints:
980 objagg_hints_flush(objagg_hints);
981 rhashtable_destroy(&objagg_hints->node_ht);
982 err_rhashtable_init:
983 kfree(objagg_hints);
984 return ERR_PTR(err);
985 }
986 EXPORT_SYMBOL(objagg_hints_get);
987
988
989
990
991
992
993
994 void objagg_hints_put(struct objagg_hints *objagg_hints)
995 {
996 if (--objagg_hints->refcount)
997 return;
998 objagg_hints_flush(objagg_hints);
999 rhashtable_destroy(&objagg_hints->node_ht);
1000 kfree(objagg_hints);
1001 }
1002 EXPORT_SYMBOL(objagg_hints_put);
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021 const struct objagg_stats *
1022 objagg_hints_stats_get(struct objagg_hints *objagg_hints)
1023 {
1024 struct objagg_stats *objagg_stats;
1025 struct objagg_hints_node *hnode;
1026 int i;
1027
1028 objagg_stats = kzalloc(struct_size(objagg_stats, stats_info,
1029 objagg_hints->node_count),
1030 GFP_KERNEL);
1031 if (!objagg_stats)
1032 return ERR_PTR(-ENOMEM);
1033
1034 i = 0;
1035 list_for_each_entry(hnode, &objagg_hints->node_list, list) {
1036 memcpy(&objagg_stats->stats_info[i], &hnode->stats_info,
1037 sizeof(objagg_stats->stats_info[0]));
1038 if (objagg_stats->stats_info[i].is_root)
1039 objagg_stats->root_count++;
1040 i++;
1041 }
1042 objagg_stats->stats_info_count = i;
1043
1044 sort(objagg_stats->stats_info, objagg_stats->stats_info_count,
1045 sizeof(struct objagg_obj_stats_info),
1046 objagg_stats_info_sort_cmp_func, NULL);
1047
1048 return objagg_stats;
1049 }
1050 EXPORT_SYMBOL(objagg_hints_stats_get);
1051
1052 MODULE_LICENSE("Dual BSD/GPL");
1053 MODULE_AUTHOR("Jiri Pirko <jiri@mellanox.com>");
1054 MODULE_DESCRIPTION("Object aggregation manager");