1
2
3
4
5
6
7
8
9
10
11
12
13
14#include <linux/slab.h>
15#include <linux/err.h>
16#include <linux/assoc_array_priv.h>
17
18
19
20
21
22static int assoc_array_subtree_iterate(const struct assoc_array_ptr *root,
23 const struct assoc_array_ptr *stop,
24 int (*iterator)(const void *leaf,
25 void *iterator_data),
26 void *iterator_data)
27{
28 const struct assoc_array_shortcut *shortcut;
29 const struct assoc_array_node *node;
30 const struct assoc_array_ptr *cursor, *ptr, *parent;
31 unsigned long has_meta;
32 int slot, ret;
33
34 cursor = root;
35
36begin_node:
37 if (assoc_array_ptr_is_shortcut(cursor)) {
38
39 shortcut = assoc_array_ptr_to_shortcut(cursor);
40 smp_read_barrier_depends();
41 cursor = ACCESS_ONCE(shortcut->next_node);
42 }
43
44 node = assoc_array_ptr_to_node(cursor);
45 smp_read_barrier_depends();
46 slot = 0;
47
48
49
50
51
52
53
54
55 has_meta = 0;
56 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
57 ptr = ACCESS_ONCE(node->slots[slot]);
58 has_meta |= (unsigned long)ptr;
59 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
60
61
62
63
64 smp_read_barrier_depends();
65
66
67 ret = iterator(assoc_array_ptr_to_leaf(ptr),
68 iterator_data);
69 if (ret)
70 return ret;
71 }
72 }
73
74
75
76
77
78
79
80
81
82 if (!(has_meta & ASSOC_ARRAY_PTR_META_TYPE))
83 goto finished_node;
84 slot = 0;
85
86continue_node:
87 node = assoc_array_ptr_to_node(cursor);
88 smp_read_barrier_depends();
89
90 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
91 ptr = ACCESS_ONCE(node->slots[slot]);
92 if (assoc_array_ptr_is_meta(ptr)) {
93 cursor = ptr;
94 goto begin_node;
95 }
96 }
97
98finished_node:
99
100 parent = ACCESS_ONCE(node->back_pointer);
101 slot = node->parent_slot;
102 if (parent == stop)
103 return 0;
104
105 if (assoc_array_ptr_is_shortcut(parent)) {
106 shortcut = assoc_array_ptr_to_shortcut(parent);
107 smp_read_barrier_depends();
108 cursor = parent;
109 parent = ACCESS_ONCE(shortcut->back_pointer);
110 slot = shortcut->parent_slot;
111 if (parent == stop)
112 return 0;
113 }
114
115
116 cursor = parent;
117 slot++;
118 goto continue_node;
119}
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144int assoc_array_iterate(const struct assoc_array *array,
145 int (*iterator)(const void *object,
146 void *iterator_data),
147 void *iterator_data)
148{
149 struct assoc_array_ptr *root = ACCESS_ONCE(array->root);
150
151 if (!root)
152 return 0;
153 return assoc_array_subtree_iterate(root, NULL, iterator, iterator_data);
154}
155
156enum assoc_array_walk_status {
157 assoc_array_walk_tree_empty,
158 assoc_array_walk_found_terminal_node,
159 assoc_array_walk_found_wrong_shortcut,
160} status;
161
162struct assoc_array_walk_result {
163 struct {
164 struct assoc_array_node *node;
165 int level;
166 int slot;
167 } terminal_node;
168 struct {
169 struct assoc_array_shortcut *shortcut;
170 int level;
171 int sc_level;
172 unsigned long sc_segments;
173 unsigned long dissimilarity;
174 } wrong_shortcut;
175};
176
177
178
179
180static enum assoc_array_walk_status
181assoc_array_walk(const struct assoc_array *array,
182 const struct assoc_array_ops *ops,
183 const void *index_key,
184 struct assoc_array_walk_result *result)
185{
186 struct assoc_array_shortcut *shortcut;
187 struct assoc_array_node *node;
188 struct assoc_array_ptr *cursor, *ptr;
189 unsigned long sc_segments, dissimilarity;
190 unsigned long segments;
191 int level, sc_level, next_sc_level;
192 int slot;
193
194 pr_devel("-->%s()\n", __func__);
195
196 cursor = ACCESS_ONCE(array->root);
197 if (!cursor)
198 return assoc_array_walk_tree_empty;
199
200 level = 0;
201
202
203
204
205
206
207
208
209jumped:
210 segments = ops->get_key_chunk(index_key, level);
211 pr_devel("segments[%d]: %lx\n", level, segments);
212
213 if (assoc_array_ptr_is_shortcut(cursor))
214 goto follow_shortcut;
215
216consider_node:
217 node = assoc_array_ptr_to_node(cursor);
218 smp_read_barrier_depends();
219
220 slot = segments >> (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
221 slot &= ASSOC_ARRAY_FAN_MASK;
222 ptr = ACCESS_ONCE(node->slots[slot]);
223
224 pr_devel("consider slot %x [ix=%d type=%lu]\n",
225 slot, level, (unsigned long)ptr & 3);
226
227 if (!assoc_array_ptr_is_meta(ptr)) {
228
229
230
231 result->terminal_node.node = node;
232 result->terminal_node.level = level;
233 result->terminal_node.slot = slot;
234 pr_devel("<--%s() = terminal_node\n", __func__);
235 return assoc_array_walk_found_terminal_node;
236 }
237
238 if (assoc_array_ptr_is_node(ptr)) {
239
240
241
242 cursor = ptr;
243 level += ASSOC_ARRAY_LEVEL_STEP;
244 if ((level & ASSOC_ARRAY_KEY_CHUNK_MASK) != 0)
245 goto consider_node;
246 goto jumped;
247 }
248
249
250
251
252
253 cursor = ptr;
254follow_shortcut:
255 shortcut = assoc_array_ptr_to_shortcut(cursor);
256 smp_read_barrier_depends();
257 pr_devel("shortcut to %d\n", shortcut->skip_to_level);
258 sc_level = level + ASSOC_ARRAY_LEVEL_STEP;
259 BUG_ON(sc_level > shortcut->skip_to_level);
260
261 do {
262
263
264
265
266 if ((sc_level & ASSOC_ARRAY_KEY_CHUNK_MASK) == 0)
267 segments = ops->get_key_chunk(index_key, sc_level);
268
269 sc_segments = shortcut->index_key[sc_level >> ASSOC_ARRAY_KEY_CHUNK_SHIFT];
270 dissimilarity = segments ^ sc_segments;
271
272 if (round_up(sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE) > shortcut->skip_to_level) {
273
274 int shift = shortcut->skip_to_level & ASSOC_ARRAY_KEY_CHUNK_MASK;
275 dissimilarity &= ~(ULONG_MAX << shift);
276 next_sc_level = shortcut->skip_to_level;
277 } else {
278 next_sc_level = sc_level + ASSOC_ARRAY_KEY_CHUNK_SIZE;
279 next_sc_level = round_down(next_sc_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
280 }
281
282 if (dissimilarity != 0) {
283
284 result->wrong_shortcut.shortcut = shortcut;
285 result->wrong_shortcut.level = level;
286 result->wrong_shortcut.sc_level = sc_level;
287 result->wrong_shortcut.sc_segments = sc_segments;
288 result->wrong_shortcut.dissimilarity = dissimilarity;
289 return assoc_array_walk_found_wrong_shortcut;
290 }
291
292 sc_level = next_sc_level;
293 } while (sc_level < shortcut->skip_to_level);
294
295
296 cursor = ACCESS_ONCE(shortcut->next_node);
297 if (((level ^ sc_level) & ~ASSOC_ARRAY_KEY_CHUNK_MASK) != 0) {
298 level = sc_level;
299 goto jumped;
300 } else {
301 level = sc_level;
302 goto consider_node;
303 }
304}
305
306
307
308
309
310
311
312
313
314
315
316
317
318void *assoc_array_find(const struct assoc_array *array,
319 const struct assoc_array_ops *ops,
320 const void *index_key)
321{
322 struct assoc_array_walk_result result;
323 const struct assoc_array_node *node;
324 const struct assoc_array_ptr *ptr;
325 const void *leaf;
326 int slot;
327
328 if (assoc_array_walk(array, ops, index_key, &result) !=
329 assoc_array_walk_found_terminal_node)
330 return NULL;
331
332 node = result.terminal_node.node;
333 smp_read_barrier_depends();
334
335
336
337
338 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
339 ptr = ACCESS_ONCE(node->slots[slot]);
340 if (ptr && assoc_array_ptr_is_leaf(ptr)) {
341
342
343
344
345 leaf = assoc_array_ptr_to_leaf(ptr);
346 smp_read_barrier_depends();
347 if (ops->compare_object(leaf, index_key))
348 return (void *)leaf;
349 }
350 }
351
352 return NULL;
353}
354
355
356
357
358
359static void assoc_array_destroy_subtree(struct assoc_array_ptr *root,
360 const struct assoc_array_ops *ops)
361{
362 struct assoc_array_shortcut *shortcut;
363 struct assoc_array_node *node;
364 struct assoc_array_ptr *cursor, *parent = NULL;
365 int slot = -1;
366
367 pr_devel("-->%s()\n", __func__);
368
369 cursor = root;
370 if (!cursor) {
371 pr_devel("empty\n");
372 return;
373 }
374
375move_to_meta:
376 if (assoc_array_ptr_is_shortcut(cursor)) {
377
378 pr_devel("[%d] shortcut\n", slot);
379 BUG_ON(!assoc_array_ptr_is_shortcut(cursor));
380 shortcut = assoc_array_ptr_to_shortcut(cursor);
381 BUG_ON(shortcut->back_pointer != parent);
382 BUG_ON(slot != -1 && shortcut->parent_slot != slot);
383 parent = cursor;
384 cursor = shortcut->next_node;
385 slot = -1;
386 BUG_ON(!assoc_array_ptr_is_node(cursor));
387 }
388
389 pr_devel("[%d] node\n", slot);
390 node = assoc_array_ptr_to_node(cursor);
391 BUG_ON(node->back_pointer != parent);
392 BUG_ON(slot != -1 && node->parent_slot != slot);
393 slot = 0;
394
395continue_node:
396 pr_devel("Node %p [back=%p]\n", node, node->back_pointer);
397 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
398 struct assoc_array_ptr *ptr = node->slots[slot];
399 if (!ptr)
400 continue;
401 if (assoc_array_ptr_is_meta(ptr)) {
402 parent = cursor;
403 cursor = ptr;
404 goto move_to_meta;
405 }
406
407 if (ops) {
408 pr_devel("[%d] free leaf\n", slot);
409 ops->free_object(assoc_array_ptr_to_leaf(ptr));
410 }
411 }
412
413 parent = node->back_pointer;
414 slot = node->parent_slot;
415 pr_devel("free node\n");
416 kfree(node);
417 if (!parent)
418 return;
419
420
421
422 if (assoc_array_ptr_is_shortcut(parent)) {
423 shortcut = assoc_array_ptr_to_shortcut(parent);
424 BUG_ON(shortcut->next_node != cursor);
425 cursor = parent;
426 parent = shortcut->back_pointer;
427 slot = shortcut->parent_slot;
428 pr_devel("free shortcut\n");
429 kfree(shortcut);
430 if (!parent)
431 return;
432
433 BUG_ON(!assoc_array_ptr_is_node(parent));
434 }
435
436
437 pr_devel("ascend to %p[%d]\n", parent, slot);
438 cursor = parent;
439 node = assoc_array_ptr_to_node(cursor);
440 slot++;
441 goto continue_node;
442}
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457void assoc_array_destroy(struct assoc_array *array,
458 const struct assoc_array_ops *ops)
459{
460 assoc_array_destroy_subtree(array->root, ops);
461 array->root = NULL;
462}
463
464
465
466
467static bool assoc_array_insert_in_empty_tree(struct assoc_array_edit *edit)
468{
469 struct assoc_array_node *new_n0;
470
471 pr_devel("-->%s()\n", __func__);
472
473 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
474 if (!new_n0)
475 return false;
476
477 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
478 edit->leaf_p = &new_n0->slots[0];
479 edit->adjust_count_on = new_n0;
480 edit->set[0].ptr = &edit->array->root;
481 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
482
483 pr_devel("<--%s() = ok [no root]\n", __func__);
484 return true;
485}
486
487
488
489
490static bool assoc_array_insert_into_terminal_node(struct assoc_array_edit *edit,
491 const struct assoc_array_ops *ops,
492 const void *index_key,
493 struct assoc_array_walk_result *result)
494{
495 struct assoc_array_shortcut *shortcut, *new_s0;
496 struct assoc_array_node *node, *new_n0, *new_n1, *side;
497 struct assoc_array_ptr *ptr;
498 unsigned long dissimilarity, base_seg, blank;
499 size_t keylen;
500 bool have_meta;
501 int level, diff;
502 int slot, next_slot, free_slot, i, j;
503
504 node = result->terminal_node.node;
505 level = result->terminal_node.level;
506 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = result->terminal_node.slot;
507
508 pr_devel("-->%s()\n", __func__);
509
510
511
512
513
514
515 free_slot = -1;
516
517
518
519
520 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
521 ptr = node->slots[i];
522 if (!ptr) {
523 free_slot = i;
524 continue;
525 }
526 if (assoc_array_ptr_is_leaf(ptr) &&
527 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
528 index_key)) {
529 pr_devel("replace in slot %d\n", i);
530 edit->leaf_p = &node->slots[i];
531 edit->dead_leaf = node->slots[i];
532 pr_devel("<--%s() = ok [replace]\n", __func__);
533 return true;
534 }
535 }
536
537
538
539
540 if (free_slot >= 0) {
541 pr_devel("insert in free slot %d\n", free_slot);
542 edit->leaf_p = &node->slots[free_slot];
543 edit->adjust_count_on = node;
544 pr_devel("<--%s() = ok [insert]\n", __func__);
545 return true;
546 }
547
548
549
550
551
552
553
554
555 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
556 if (!new_n0)
557 return false;
558 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
559 new_n1 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
560 if (!new_n1)
561 return false;
562 edit->new_meta[1] = assoc_array_node_to_ptr(new_n1);
563
564
565 pr_devel("no spare slots\n");
566 have_meta = false;
567 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
568 ptr = node->slots[i];
569 if (assoc_array_ptr_is_meta(ptr)) {
570 edit->segment_cache[i] = 0xff;
571 have_meta = true;
572 continue;
573 }
574 base_seg = ops->get_object_key_chunk(
575 assoc_array_ptr_to_leaf(ptr), level);
576 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
577 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
578 }
579
580 if (have_meta) {
581 pr_devel("have meta\n");
582 goto split_node;
583 }
584
585
586 dissimilarity = 0;
587 base_seg = edit->segment_cache[0];
588 for (i = 1; i < ASSOC_ARRAY_FAN_OUT; i++)
589 dissimilarity |= edit->segment_cache[i] ^ base_seg;
590
591 pr_devel("only leaves; dissimilarity=%lx\n", dissimilarity);
592
593 if ((dissimilarity & ASSOC_ARRAY_FAN_MASK) == 0) {
594
595
596
597 if ((edit->segment_cache[ASSOC_ARRAY_FAN_OUT] ^ base_seg) == 0)
598 goto all_leaves_cluster_together;
599
600
601
602
603 goto present_leaves_cluster_but_not_new_leaf;
604 }
605
606split_node:
607 pr_devel("split node\n");
608
609
610
611
612
613
614
615
616
617
618
619 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
620 new_n0->back_pointer = node->back_pointer;
621 new_n0->parent_slot = node->parent_slot;
622 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
623 new_n1->parent_slot = -1;
624
625do_split_node:
626 pr_devel("do_split_node\n");
627
628 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
629 new_n1->nr_leaves_on_branch = 0;
630
631
632
633
634
635
636
637 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
638 slot = edit->segment_cache[i];
639 if (slot != 0xff)
640 for (j = i + 1; j < ASSOC_ARRAY_FAN_OUT + 1; j++)
641 if (edit->segment_cache[j] == slot)
642 goto found_slot_for_multiple_occupancy;
643 }
644found_slot_for_multiple_occupancy:
645 pr_devel("same slot: %x %x [%02x]\n", i, j, slot);
646 BUG_ON(i >= ASSOC_ARRAY_FAN_OUT);
647 BUG_ON(j >= ASSOC_ARRAY_FAN_OUT + 1);
648 BUG_ON(slot >= ASSOC_ARRAY_FAN_OUT);
649
650 new_n1->parent_slot = slot;
651
652
653 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
654 if (assoc_array_ptr_is_meta(node->slots[i]))
655 new_n0->slots[i] = node->slots[i];
656 else
657 new_n0->slots[i] = NULL;
658 BUG_ON(new_n0->slots[slot] != NULL);
659 new_n0->slots[slot] = assoc_array_node_to_ptr(new_n1);
660
661
662 free_slot = -1;
663 next_slot = 0;
664 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
665 if (assoc_array_ptr_is_meta(node->slots[i]))
666 continue;
667 if (edit->segment_cache[i] == slot) {
668 new_n1->slots[next_slot++] = node->slots[i];
669 new_n1->nr_leaves_on_branch++;
670 } else {
671 do {
672 free_slot++;
673 } while (new_n0->slots[free_slot] != NULL);
674 new_n0->slots[free_slot] = node->slots[i];
675 }
676 }
677
678 pr_devel("filtered: f=%x n=%x\n", free_slot, next_slot);
679
680 if (edit->segment_cache[ASSOC_ARRAY_FAN_OUT] != slot) {
681 do {
682 free_slot++;
683 } while (new_n0->slots[free_slot] != NULL);
684 edit->leaf_p = &new_n0->slots[free_slot];
685 edit->adjust_count_on = new_n0;
686 } else {
687 edit->leaf_p = &new_n1->slots[next_slot++];
688 edit->adjust_count_on = new_n1;
689 }
690
691 BUG_ON(next_slot <= 1);
692
693 edit->set_backpointers_to = assoc_array_node_to_ptr(new_n0);
694 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
695 if (edit->segment_cache[i] == 0xff) {
696 ptr = node->slots[i];
697 BUG_ON(assoc_array_ptr_is_leaf(ptr));
698 if (assoc_array_ptr_is_node(ptr)) {
699 side = assoc_array_ptr_to_node(ptr);
700 edit->set_backpointers[i] = &side->back_pointer;
701 } else {
702 shortcut = assoc_array_ptr_to_shortcut(ptr);
703 edit->set_backpointers[i] = &shortcut->back_pointer;
704 }
705 }
706 }
707
708 ptr = node->back_pointer;
709 if (!ptr)
710 edit->set[0].ptr = &edit->array->root;
711 else if (assoc_array_ptr_is_node(ptr))
712 edit->set[0].ptr = &assoc_array_ptr_to_node(ptr)->slots[node->parent_slot];
713 else
714 edit->set[0].ptr = &assoc_array_ptr_to_shortcut(ptr)->next_node;
715 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
716 pr_devel("<--%s() = ok [split node]\n", __func__);
717 return true;
718
719present_leaves_cluster_but_not_new_leaf:
720
721
722
723
724 pr_devel("present leaves cluster but not new leaf\n");
725
726 new_n0->back_pointer = node->back_pointer;
727 new_n0->parent_slot = node->parent_slot;
728 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
729 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
730 new_n1->parent_slot = edit->segment_cache[0];
731 new_n1->nr_leaves_on_branch = node->nr_leaves_on_branch;
732 edit->adjust_count_on = new_n0;
733
734 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++)
735 new_n1->slots[i] = node->slots[i];
736
737 new_n0->slots[edit->segment_cache[0]] = assoc_array_node_to_ptr(new_n0);
738 edit->leaf_p = &new_n0->slots[edit->segment_cache[ASSOC_ARRAY_FAN_OUT]];
739
740 edit->set[0].ptr = &assoc_array_ptr_to_node(node->back_pointer)->slots[node->parent_slot];
741 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
742 edit->excised_meta[0] = assoc_array_node_to_ptr(node);
743 pr_devel("<--%s() = ok [insert node before]\n", __func__);
744 return true;
745
746all_leaves_cluster_together:
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761 pr_devel("all leaves cluster together\n");
762 diff = INT_MAX;
763 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
764 int x = ops->diff_objects(assoc_array_ptr_to_leaf(node->slots[i]),
765 index_key);
766 if (x < diff) {
767 BUG_ON(x < 0);
768 diff = x;
769 }
770 }
771 BUG_ON(diff == INT_MAX);
772 BUG_ON(diff < level + ASSOC_ARRAY_LEVEL_STEP);
773
774 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
775 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
776
777 new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
778 keylen * sizeof(unsigned long), GFP_KERNEL);
779 if (!new_s0)
780 return false;
781 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s0);
782
783 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
784 new_s0->back_pointer = node->back_pointer;
785 new_s0->parent_slot = node->parent_slot;
786 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
787 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
788 new_n0->parent_slot = 0;
789 new_n1->back_pointer = assoc_array_node_to_ptr(new_n0);
790 new_n1->parent_slot = -1;
791
792 new_s0->skip_to_level = level = diff & ~ASSOC_ARRAY_LEVEL_STEP_MASK;
793 pr_devel("skip_to_level = %d [diff %d]\n", level, diff);
794 BUG_ON(level <= 0);
795
796 for (i = 0; i < keylen; i++)
797 new_s0->index_key[i] =
798 ops->get_key_chunk(index_key, i * ASSOC_ARRAY_KEY_CHUNK_SIZE);
799
800 blank = ULONG_MAX << (level & ASSOC_ARRAY_KEY_CHUNK_MASK);
801 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, level, blank);
802 new_s0->index_key[keylen - 1] &= ~blank;
803
804
805
806
807 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
808 ptr = node->slots[i];
809 base_seg = ops->get_object_key_chunk(assoc_array_ptr_to_leaf(ptr),
810 level);
811 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
812 edit->segment_cache[i] = base_seg & ASSOC_ARRAY_FAN_MASK;
813 }
814
815 base_seg = ops->get_key_chunk(index_key, level);
816 base_seg >>= level & ASSOC_ARRAY_KEY_CHUNK_MASK;
817 edit->segment_cache[ASSOC_ARRAY_FAN_OUT] = base_seg & ASSOC_ARRAY_FAN_MASK;
818 goto do_split_node;
819}
820
821
822
823
824static bool assoc_array_insert_mid_shortcut(struct assoc_array_edit *edit,
825 const struct assoc_array_ops *ops,
826 struct assoc_array_walk_result *result)
827{
828 struct assoc_array_shortcut *shortcut, *new_s0, *new_s1;
829 struct assoc_array_node *node, *new_n0, *side;
830 unsigned long sc_segments, dissimilarity, blank;
831 size_t keylen;
832 int level, sc_level, diff;
833 int sc_slot;
834
835 shortcut = result->wrong_shortcut.shortcut;
836 level = result->wrong_shortcut.level;
837 sc_level = result->wrong_shortcut.sc_level;
838 sc_segments = result->wrong_shortcut.sc_segments;
839 dissimilarity = result->wrong_shortcut.dissimilarity;
840
841 pr_devel("-->%s(ix=%d dis=%lx scix=%d)\n",
842 __func__, level, dissimilarity, sc_level);
843
844
845
846
847
848
849
850 diff = __ffs(dissimilarity);
851 diff &= ~ASSOC_ARRAY_LEVEL_STEP_MASK;
852 diff += sc_level & ~ASSOC_ARRAY_KEY_CHUNK_MASK;
853 pr_devel("diff=%d\n", diff);
854
855 if (!shortcut->back_pointer) {
856 edit->set[0].ptr = &edit->array->root;
857 } else if (assoc_array_ptr_is_node(shortcut->back_pointer)) {
858 node = assoc_array_ptr_to_node(shortcut->back_pointer);
859 edit->set[0].ptr = &node->slots[shortcut->parent_slot];
860 } else {
861 BUG();
862 }
863
864 edit->excised_meta[0] = assoc_array_shortcut_to_ptr(shortcut);
865
866
867 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
868 if (!new_n0)
869 return false;
870 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
871 edit->adjust_count_on = new_n0;
872
873
874
875
876
877 level += ASSOC_ARRAY_LEVEL_STEP;
878 if (diff > level) {
879 pr_devel("pre-shortcut %d...%d\n", level, diff);
880 keylen = round_up(diff, ASSOC_ARRAY_KEY_CHUNK_SIZE);
881 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
882
883 new_s0 = kzalloc(sizeof(struct assoc_array_shortcut) +
884 keylen * sizeof(unsigned long), GFP_KERNEL);
885 if (!new_s0)
886 return false;
887 edit->new_meta[1] = assoc_array_shortcut_to_ptr(new_s0);
888 edit->set[0].to = assoc_array_shortcut_to_ptr(new_s0);
889 new_s0->back_pointer = shortcut->back_pointer;
890 new_s0->parent_slot = shortcut->parent_slot;
891 new_s0->next_node = assoc_array_node_to_ptr(new_n0);
892 new_s0->skip_to_level = diff;
893
894 new_n0->back_pointer = assoc_array_shortcut_to_ptr(new_s0);
895 new_n0->parent_slot = 0;
896
897 memcpy(new_s0->index_key, shortcut->index_key,
898 keylen * sizeof(unsigned long));
899
900 blank = ULONG_MAX << (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
901 pr_devel("blank off [%zu] %d: %lx\n", keylen - 1, diff, blank);
902 new_s0->index_key[keylen - 1] &= ~blank;
903 } else {
904 pr_devel("no pre-shortcut\n");
905 edit->set[0].to = assoc_array_node_to_ptr(new_n0);
906 new_n0->back_pointer = shortcut->back_pointer;
907 new_n0->parent_slot = shortcut->parent_slot;
908 }
909
910 side = assoc_array_ptr_to_node(shortcut->next_node);
911 new_n0->nr_leaves_on_branch = side->nr_leaves_on_branch;
912
913
914
915
916 sc_slot = sc_segments >> (diff & ASSOC_ARRAY_KEY_CHUNK_MASK);
917 sc_slot &= ASSOC_ARRAY_FAN_MASK;
918
919 pr_devel("new slot %lx >> %d -> %d\n",
920 sc_segments, diff & ASSOC_ARRAY_KEY_CHUNK_MASK, sc_slot);
921
922
923
924
925
926
927 level = diff + ASSOC_ARRAY_LEVEL_STEP;
928 if (level < shortcut->skip_to_level) {
929 pr_devel("post-shortcut %d...%d\n", level, shortcut->skip_to_level);
930 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
931 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
932
933 new_s1 = kzalloc(sizeof(struct assoc_array_shortcut) +
934 keylen * sizeof(unsigned long), GFP_KERNEL);
935 if (!new_s1)
936 return false;
937 edit->new_meta[2] = assoc_array_shortcut_to_ptr(new_s1);
938
939 new_s1->back_pointer = assoc_array_node_to_ptr(new_n0);
940 new_s1->parent_slot = sc_slot;
941 new_s1->next_node = shortcut->next_node;
942 new_s1->skip_to_level = shortcut->skip_to_level;
943
944 new_n0->slots[sc_slot] = assoc_array_shortcut_to_ptr(new_s1);
945
946 memcpy(new_s1->index_key, shortcut->index_key,
947 keylen * sizeof(unsigned long));
948
949 edit->set[1].ptr = &side->back_pointer;
950 edit->set[1].to = assoc_array_shortcut_to_ptr(new_s1);
951 } else {
952 pr_devel("no post-shortcut\n");
953
954
955
956
957
958
959 new_n0->slots[sc_slot] = shortcut->next_node;
960 edit->set_parent_slot[0].p = &side->parent_slot;
961 edit->set_parent_slot[0].to = sc_slot;
962 edit->set[1].ptr = &side->back_pointer;
963 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
964 }
965
966
967 if (sc_slot == 0)
968 edit->leaf_p = &new_n0->slots[1];
969 else
970 edit->leaf_p = &new_n0->slots[0];
971
972 pr_devel("<--%s() = ok [split shortcut]\n", __func__);
973 return edit;
974}
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995struct assoc_array_edit *assoc_array_insert(struct assoc_array *array,
996 const struct assoc_array_ops *ops,
997 const void *index_key,
998 void *object)
999{
1000 struct assoc_array_walk_result result;
1001 struct assoc_array_edit *edit;
1002
1003 pr_devel("-->%s()\n", __func__);
1004
1005
1006
1007
1008
1009
1010 BUG_ON(assoc_array_ptr_is_meta(object));
1011
1012 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1013 if (!edit)
1014 return ERR_PTR(-ENOMEM);
1015 edit->array = array;
1016 edit->ops = ops;
1017 edit->leaf = assoc_array_leaf_to_ptr(object);
1018 edit->adjust_count_by = 1;
1019
1020 switch (assoc_array_walk(array, ops, index_key, &result)) {
1021 case assoc_array_walk_tree_empty:
1022
1023 if (!assoc_array_insert_in_empty_tree(edit))
1024 goto enomem;
1025 return edit;
1026
1027 case assoc_array_walk_found_terminal_node:
1028
1029
1030
1031
1032 if (!assoc_array_insert_into_terminal_node(edit, ops, index_key,
1033 &result))
1034 goto enomem;
1035 return edit;
1036
1037 case assoc_array_walk_found_wrong_shortcut:
1038
1039
1040
1041 if (!assoc_array_insert_mid_shortcut(edit, ops, &result))
1042 goto enomem;
1043 return edit;
1044 }
1045
1046enomem:
1047
1048 pr_devel("enomem\n");
1049 assoc_array_cancel_edit(edit);
1050 return ERR_PTR(-ENOMEM);
1051}
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062void assoc_array_insert_set_object(struct assoc_array_edit *edit, void *object)
1063{
1064 BUG_ON(!object);
1065 edit->leaf = assoc_array_leaf_to_ptr(object);
1066}
1067
1068struct assoc_array_delete_collapse_context {
1069 struct assoc_array_node *node;
1070 const void *skip_leaf;
1071 int slot;
1072};
1073
1074
1075
1076
1077static int assoc_array_delete_collapse_iterator(const void *leaf,
1078 void *iterator_data)
1079{
1080 struct assoc_array_delete_collapse_context *collapse = iterator_data;
1081
1082 if (leaf == collapse->skip_leaf)
1083 return 0;
1084
1085 BUG_ON(collapse->slot >= ASSOC_ARRAY_FAN_OUT);
1086
1087 collapse->node->slots[collapse->slot++] = assoc_array_leaf_to_ptr(leaf);
1088 return 0;
1089}
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110struct assoc_array_edit *assoc_array_delete(struct assoc_array *array,
1111 const struct assoc_array_ops *ops,
1112 const void *index_key)
1113{
1114 struct assoc_array_delete_collapse_context collapse;
1115 struct assoc_array_walk_result result;
1116 struct assoc_array_node *node, *new_n0;
1117 struct assoc_array_edit *edit;
1118 struct assoc_array_ptr *ptr;
1119 bool has_meta;
1120 int slot, i;
1121
1122 pr_devel("-->%s()\n", __func__);
1123
1124 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1125 if (!edit)
1126 return ERR_PTR(-ENOMEM);
1127 edit->array = array;
1128 edit->ops = ops;
1129 edit->adjust_count_by = -1;
1130
1131 switch (assoc_array_walk(array, ops, index_key, &result)) {
1132 case assoc_array_walk_found_terminal_node:
1133
1134
1135
1136 pr_devel("terminal_node\n");
1137 node = result.terminal_node.node;
1138
1139 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1140 ptr = node->slots[slot];
1141 if (ptr &&
1142 assoc_array_ptr_is_leaf(ptr) &&
1143 ops->compare_object(assoc_array_ptr_to_leaf(ptr),
1144 index_key))
1145 goto found_leaf;
1146 }
1147 case assoc_array_walk_tree_empty:
1148 case assoc_array_walk_found_wrong_shortcut:
1149 default:
1150 assoc_array_cancel_edit(edit);
1151 pr_devel("not found\n");
1152 return NULL;
1153 }
1154
1155found_leaf:
1156 BUG_ON(array->nr_leaves_on_tree <= 0);
1157
1158
1159
1160
1161 edit->dead_leaf = node->slots[slot];
1162 edit->set[0].ptr = &node->slots[slot];
1163 edit->set[0].to = NULL;
1164 edit->adjust_count_on = node;
1165
1166
1167
1168
1169 if (array->nr_leaves_on_tree == 1) {
1170 edit->set[1].ptr = &array->root;
1171 edit->set[1].to = NULL;
1172 edit->adjust_count_on = NULL;
1173 edit->excised_subtree = array->root;
1174 pr_devel("all gone\n");
1175 return edit;
1176 }
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188 if (node->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1189 struct assoc_array_node *parent, *grandparent;
1190 struct assoc_array_ptr *ptr;
1191
1192
1193
1194
1195
1196 has_meta = false;
1197 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1198 ptr = node->slots[i];
1199 if (assoc_array_ptr_is_meta(ptr)) {
1200 has_meta = true;
1201 break;
1202 }
1203 }
1204
1205 pr_devel("leaves: %ld [m=%d]\n",
1206 node->nr_leaves_on_branch - 1, has_meta);
1207
1208
1209
1210
1211 parent = node;
1212 collapse_up:
1213 pr_devel("collapse subtree: %ld\n", parent->nr_leaves_on_branch);
1214
1215 ptr = parent->back_pointer;
1216 if (!ptr)
1217 goto do_collapse;
1218 if (assoc_array_ptr_is_shortcut(ptr)) {
1219 struct assoc_array_shortcut *s = assoc_array_ptr_to_shortcut(ptr);
1220 ptr = s->back_pointer;
1221 if (!ptr)
1222 goto do_collapse;
1223 }
1224
1225 grandparent = assoc_array_ptr_to_node(ptr);
1226 if (grandparent->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT + 1) {
1227 parent = grandparent;
1228 goto collapse_up;
1229 }
1230
1231 do_collapse:
1232
1233
1234
1235
1236 if (has_meta || parent != node) {
1237 node = parent;
1238
1239
1240 new_n0 = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
1241 if (!new_n0)
1242 goto enomem;
1243 edit->new_meta[0] = assoc_array_node_to_ptr(new_n0);
1244
1245 new_n0->back_pointer = node->back_pointer;
1246 new_n0->parent_slot = node->parent_slot;
1247 new_n0->nr_leaves_on_branch = node->nr_leaves_on_branch;
1248 edit->adjust_count_on = new_n0;
1249
1250 collapse.node = new_n0;
1251 collapse.skip_leaf = assoc_array_ptr_to_leaf(edit->dead_leaf);
1252 collapse.slot = 0;
1253 assoc_array_subtree_iterate(assoc_array_node_to_ptr(node),
1254 node->back_pointer,
1255 assoc_array_delete_collapse_iterator,
1256 &collapse);
1257 pr_devel("collapsed %d,%lu\n", collapse.slot, new_n0->nr_leaves_on_branch);
1258 BUG_ON(collapse.slot != new_n0->nr_leaves_on_branch - 1);
1259
1260 if (!node->back_pointer) {
1261 edit->set[1].ptr = &array->root;
1262 } else if (assoc_array_ptr_is_leaf(node->back_pointer)) {
1263 BUG();
1264 } else if (assoc_array_ptr_is_node(node->back_pointer)) {
1265 struct assoc_array_node *p =
1266 assoc_array_ptr_to_node(node->back_pointer);
1267 edit->set[1].ptr = &p->slots[node->parent_slot];
1268 } else if (assoc_array_ptr_is_shortcut(node->back_pointer)) {
1269 struct assoc_array_shortcut *s =
1270 assoc_array_ptr_to_shortcut(node->back_pointer);
1271 edit->set[1].ptr = &s->next_node;
1272 }
1273 edit->set[1].to = assoc_array_node_to_ptr(new_n0);
1274 edit->excised_subtree = assoc_array_node_to_ptr(node);
1275 }
1276 }
1277
1278 return edit;
1279
1280enomem:
1281
1282 pr_devel("enomem\n");
1283 assoc_array_cancel_edit(edit);
1284 return ERR_PTR(-ENOMEM);
1285}
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305struct assoc_array_edit *assoc_array_clear(struct assoc_array *array,
1306 const struct assoc_array_ops *ops)
1307{
1308 struct assoc_array_edit *edit;
1309
1310 pr_devel("-->%s()\n", __func__);
1311
1312 if (!array->root)
1313 return NULL;
1314
1315 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1316 if (!edit)
1317 return ERR_PTR(-ENOMEM);
1318 edit->array = array;
1319 edit->ops = ops;
1320 edit->set[1].ptr = &array->root;
1321 edit->set[1].to = NULL;
1322 edit->excised_subtree = array->root;
1323 edit->ops_for_excised_subtree = ops;
1324 pr_devel("all gone\n");
1325 return edit;
1326}
1327
1328
1329
1330
1331static void assoc_array_rcu_cleanup(struct rcu_head *head)
1332{
1333 struct assoc_array_edit *edit =
1334 container_of(head, struct assoc_array_edit, rcu);
1335 int i;
1336
1337 pr_devel("-->%s()\n", __func__);
1338
1339 if (edit->dead_leaf)
1340 edit->ops->free_object(assoc_array_ptr_to_leaf(edit->dead_leaf));
1341 for (i = 0; i < ARRAY_SIZE(edit->excised_meta); i++)
1342 if (edit->excised_meta[i])
1343 kfree(assoc_array_ptr_to_node(edit->excised_meta[i]));
1344
1345 if (edit->excised_subtree) {
1346 BUG_ON(assoc_array_ptr_is_leaf(edit->excised_subtree));
1347 if (assoc_array_ptr_is_node(edit->excised_subtree)) {
1348 struct assoc_array_node *n =
1349 assoc_array_ptr_to_node(edit->excised_subtree);
1350 n->back_pointer = NULL;
1351 } else {
1352 struct assoc_array_shortcut *s =
1353 assoc_array_ptr_to_shortcut(edit->excised_subtree);
1354 s->back_pointer = NULL;
1355 }
1356 assoc_array_destroy_subtree(edit->excised_subtree,
1357 edit->ops_for_excised_subtree);
1358 }
1359
1360 kfree(edit);
1361}
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376void assoc_array_apply_edit(struct assoc_array_edit *edit)
1377{
1378 struct assoc_array_shortcut *shortcut;
1379 struct assoc_array_node *node;
1380 struct assoc_array_ptr *ptr;
1381 int i;
1382
1383 pr_devel("-->%s()\n", __func__);
1384
1385 smp_wmb();
1386 if (edit->leaf_p)
1387 *edit->leaf_p = edit->leaf;
1388
1389 smp_wmb();
1390 for (i = 0; i < ARRAY_SIZE(edit->set_parent_slot); i++)
1391 if (edit->set_parent_slot[i].p)
1392 *edit->set_parent_slot[i].p = edit->set_parent_slot[i].to;
1393
1394 smp_wmb();
1395 for (i = 0; i < ARRAY_SIZE(edit->set_backpointers); i++)
1396 if (edit->set_backpointers[i])
1397 *edit->set_backpointers[i] = edit->set_backpointers_to;
1398
1399 smp_wmb();
1400 for (i = 0; i < ARRAY_SIZE(edit->set); i++)
1401 if (edit->set[i].ptr)
1402 *edit->set[i].ptr = edit->set[i].to;
1403
1404 if (edit->array->root == NULL) {
1405 edit->array->nr_leaves_on_tree = 0;
1406 } else if (edit->adjust_count_on) {
1407 node = edit->adjust_count_on;
1408 for (;;) {
1409 node->nr_leaves_on_branch += edit->adjust_count_by;
1410
1411 ptr = node->back_pointer;
1412 if (!ptr)
1413 break;
1414 if (assoc_array_ptr_is_shortcut(ptr)) {
1415 shortcut = assoc_array_ptr_to_shortcut(ptr);
1416 ptr = shortcut->back_pointer;
1417 if (!ptr)
1418 break;
1419 }
1420 BUG_ON(!assoc_array_ptr_is_node(ptr));
1421 node = assoc_array_ptr_to_node(ptr);
1422 }
1423
1424 edit->array->nr_leaves_on_tree += edit->adjust_count_by;
1425 }
1426
1427 call_rcu(&edit->rcu, assoc_array_rcu_cleanup);
1428}
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440void assoc_array_cancel_edit(struct assoc_array_edit *edit)
1441{
1442 struct assoc_array_ptr *ptr;
1443 int i;
1444
1445 pr_devel("-->%s()\n", __func__);
1446
1447
1448 for (i = 0; i < ARRAY_SIZE(edit->new_meta); i++) {
1449 ptr = edit->new_meta[i];
1450 if (ptr) {
1451 if (assoc_array_ptr_is_node(ptr))
1452 kfree(assoc_array_ptr_to_node(ptr));
1453 else
1454 kfree(assoc_array_ptr_to_shortcut(ptr));
1455 }
1456 }
1457 kfree(edit);
1458}
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484int assoc_array_gc(struct assoc_array *array,
1485 const struct assoc_array_ops *ops,
1486 bool (*iterator)(void *object, void *iterator_data),
1487 void *iterator_data)
1488{
1489 struct assoc_array_shortcut *shortcut, *new_s;
1490 struct assoc_array_node *node, *new_n;
1491 struct assoc_array_edit *edit;
1492 struct assoc_array_ptr *cursor, *ptr;
1493 struct assoc_array_ptr *new_root, *new_parent, **new_ptr_pp;
1494 unsigned long nr_leaves_on_tree;
1495 int keylen, slot, nr_free, next_slot, i;
1496
1497 pr_devel("-->%s()\n", __func__);
1498
1499 if (!array->root)
1500 return 0;
1501
1502 edit = kzalloc(sizeof(struct assoc_array_edit), GFP_KERNEL);
1503 if (!edit)
1504 return -ENOMEM;
1505 edit->array = array;
1506 edit->ops = ops;
1507 edit->ops_for_excised_subtree = ops;
1508 edit->set[0].ptr = &array->root;
1509 edit->excised_subtree = array->root;
1510
1511 new_root = new_parent = NULL;
1512 new_ptr_pp = &new_root;
1513 cursor = array->root;
1514
1515descend:
1516
1517
1518
1519 if (assoc_array_ptr_is_shortcut(cursor)) {
1520 shortcut = assoc_array_ptr_to_shortcut(cursor);
1521 keylen = round_up(shortcut->skip_to_level, ASSOC_ARRAY_KEY_CHUNK_SIZE);
1522 keylen >>= ASSOC_ARRAY_KEY_CHUNK_SHIFT;
1523 new_s = kmalloc(sizeof(struct assoc_array_shortcut) +
1524 keylen * sizeof(unsigned long), GFP_KERNEL);
1525 if (!new_s)
1526 goto enomem;
1527 pr_devel("dup shortcut %p -> %p\n", shortcut, new_s);
1528 memcpy(new_s, shortcut, (sizeof(struct assoc_array_shortcut) +
1529 keylen * sizeof(unsigned long)));
1530 new_s->back_pointer = new_parent;
1531 new_s->parent_slot = shortcut->parent_slot;
1532 *new_ptr_pp = new_parent = assoc_array_shortcut_to_ptr(new_s);
1533 new_ptr_pp = &new_s->next_node;
1534 cursor = shortcut->next_node;
1535 }
1536
1537
1538 node = assoc_array_ptr_to_node(cursor);
1539 new_n = kzalloc(sizeof(struct assoc_array_node), GFP_KERNEL);
1540 if (!new_n)
1541 goto enomem;
1542 pr_devel("dup node %p -> %p\n", node, new_n);
1543 new_n->back_pointer = new_parent;
1544 new_n->parent_slot = node->parent_slot;
1545 *new_ptr_pp = new_parent = assoc_array_node_to_ptr(new_n);
1546 new_ptr_pp = NULL;
1547 slot = 0;
1548
1549continue_node:
1550
1551 for (; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1552 ptr = node->slots[slot];
1553 if (!ptr)
1554 continue;
1555
1556 if (assoc_array_ptr_is_leaf(ptr)) {
1557 if (iterator(assoc_array_ptr_to_leaf(ptr),
1558 iterator_data))
1559
1560
1561
1562 new_n->slots[slot] = ptr;
1563 continue;
1564 }
1565
1566 new_ptr_pp = &new_n->slots[slot];
1567 cursor = ptr;
1568 goto descend;
1569 }
1570
1571 pr_devel("-- compress node %p --\n", new_n);
1572
1573
1574
1575
1576 new_n->nr_leaves_on_branch = 0;
1577 nr_free = 0;
1578 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1579 ptr = new_n->slots[slot];
1580 if (!ptr)
1581 nr_free++;
1582 else if (assoc_array_ptr_is_leaf(ptr))
1583 new_n->nr_leaves_on_branch++;
1584 }
1585 pr_devel("free=%d, leaves=%lu\n", nr_free, new_n->nr_leaves_on_branch);
1586
1587
1588 next_slot = 0;
1589 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++) {
1590 struct assoc_array_shortcut *s;
1591 struct assoc_array_node *child;
1592
1593 ptr = new_n->slots[slot];
1594 if (!ptr || assoc_array_ptr_is_leaf(ptr))
1595 continue;
1596
1597 s = NULL;
1598 if (assoc_array_ptr_is_shortcut(ptr)) {
1599 s = assoc_array_ptr_to_shortcut(ptr);
1600 ptr = s->next_node;
1601 }
1602
1603 child = assoc_array_ptr_to_node(ptr);
1604 new_n->nr_leaves_on_branch += child->nr_leaves_on_branch;
1605
1606 if (child->nr_leaves_on_branch <= nr_free + 1) {
1607
1608 pr_devel("[%d] fold node %lu/%d [nx %d]\n",
1609 slot, child->nr_leaves_on_branch, nr_free + 1,
1610 next_slot);
1611
1612
1613
1614
1615 BUG_ON(s);
1616
1617 new_n->slots[slot] = NULL;
1618 nr_free++;
1619 if (slot < next_slot)
1620 next_slot = slot;
1621 for (i = 0; i < ASSOC_ARRAY_FAN_OUT; i++) {
1622 struct assoc_array_ptr *p = child->slots[i];
1623 if (!p)
1624 continue;
1625 BUG_ON(assoc_array_ptr_is_meta(p));
1626 while (new_n->slots[next_slot])
1627 next_slot++;
1628 BUG_ON(next_slot >= ASSOC_ARRAY_FAN_OUT);
1629 new_n->slots[next_slot++] = p;
1630 nr_free--;
1631 }
1632 kfree(child);
1633 } else {
1634 pr_devel("[%d] retain node %lu/%d [nx %d]\n",
1635 slot, child->nr_leaves_on_branch, nr_free + 1,
1636 next_slot);
1637 }
1638 }
1639
1640 pr_devel("after: %lu\n", new_n->nr_leaves_on_branch);
1641
1642 nr_leaves_on_tree = new_n->nr_leaves_on_branch;
1643
1644
1645 if (nr_free == ASSOC_ARRAY_FAN_OUT - 1) {
1646 for (slot = 0; slot < ASSOC_ARRAY_FAN_OUT; slot++)
1647 if ((ptr = new_n->slots[slot]))
1648 break;
1649
1650 if (assoc_array_ptr_is_meta(ptr) &&
1651 assoc_array_ptr_is_shortcut(ptr)) {
1652 pr_devel("excise node %p with 1 shortcut\n", new_n);
1653 new_s = assoc_array_ptr_to_shortcut(ptr);
1654 new_parent = new_n->back_pointer;
1655 slot = new_n->parent_slot;
1656 kfree(new_n);
1657 if (!new_parent) {
1658 new_s->back_pointer = NULL;
1659 new_s->parent_slot = 0;
1660 new_root = ptr;
1661 goto gc_complete;
1662 }
1663
1664 if (assoc_array_ptr_is_shortcut(new_parent)) {
1665
1666 struct assoc_array_shortcut *s =
1667 assoc_array_ptr_to_shortcut(new_parent);
1668
1669 pr_devel("excise preceding shortcut\n");
1670
1671 new_parent = new_s->back_pointer = s->back_pointer;
1672 slot = new_s->parent_slot = s->parent_slot;
1673 kfree(s);
1674 if (!new_parent) {
1675 new_s->back_pointer = NULL;
1676 new_s->parent_slot = 0;
1677 new_root = ptr;
1678 goto gc_complete;
1679 }
1680 }
1681
1682 new_s->back_pointer = new_parent;
1683 new_s->parent_slot = slot;
1684 new_n = assoc_array_ptr_to_node(new_parent);
1685 new_n->slots[slot] = ptr;
1686 goto ascend_old_tree;
1687 }
1688 }
1689
1690
1691
1692
1693 ptr = new_n->back_pointer;
1694 if (!ptr)
1695 goto gc_complete;
1696
1697 if (assoc_array_ptr_is_shortcut(ptr)) {
1698 new_s = assoc_array_ptr_to_shortcut(ptr);
1699 new_parent = new_s->back_pointer;
1700 slot = new_s->parent_slot;
1701
1702 if (new_n->nr_leaves_on_branch <= ASSOC_ARRAY_FAN_OUT) {
1703 struct assoc_array_node *n;
1704
1705 pr_devel("excise shortcut\n");
1706 new_n->back_pointer = new_parent;
1707 new_n->parent_slot = slot;
1708 kfree(new_s);
1709 if (!new_parent) {
1710 new_root = assoc_array_node_to_ptr(new_n);
1711 goto gc_complete;
1712 }
1713
1714 n = assoc_array_ptr_to_node(new_parent);
1715 n->slots[slot] = assoc_array_node_to_ptr(new_n);
1716 }
1717 } else {
1718 new_parent = ptr;
1719 }
1720 new_n = assoc_array_ptr_to_node(new_parent);
1721
1722ascend_old_tree:
1723 ptr = node->back_pointer;
1724 if (assoc_array_ptr_is_shortcut(ptr)) {
1725 shortcut = assoc_array_ptr_to_shortcut(ptr);
1726 slot = shortcut->parent_slot;
1727 cursor = shortcut->back_pointer;
1728 if (!cursor)
1729 goto gc_complete;
1730 } else {
1731 slot = node->parent_slot;
1732 cursor = ptr;
1733 }
1734 BUG_ON(!cursor);
1735 node = assoc_array_ptr_to_node(cursor);
1736 slot++;
1737 goto continue_node;
1738
1739gc_complete:
1740 edit->set[0].to = new_root;
1741 assoc_array_apply_edit(edit);
1742 array->nr_leaves_on_tree = nr_leaves_on_tree;
1743 return 0;
1744
1745enomem:
1746 pr_devel("enomem\n");
1747 assoc_array_destroy_subtree(new_root, edit->ops);
1748 kfree(edit);
1749 return -ENOMEM;
1750}
1751