aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--lib/radix-tree.c48
1 files changed, 23 insertions, 25 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 1a82066165db..9d9b4b9af4b6 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -499,12 +499,13 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
499 unsigned order, struct radix_tree_node **nodep, 499 unsigned order, struct radix_tree_node **nodep,
500 void ***slotp) 500 void ***slotp)
501{ 501{
502 struct radix_tree_node *node = NULL, *slot; 502 struct radix_tree_node *node = NULL, *child;
503 void **slot = (void **)&root->rnode;
503 unsigned long maxindex; 504 unsigned long maxindex;
504 unsigned int shift, offset; 505 unsigned int shift, offset = 0;
505 unsigned long max = index | ((1UL << order) - 1); 506 unsigned long max = index | ((1UL << order) - 1);
506 507
507 shift = radix_tree_load_root(root, &slot, &maxindex); 508 shift = radix_tree_load_root(root, &child, &maxindex);
508 509
509 /* Make sure the tree is high enough. */ 510 /* Make sure the tree is high enough. */
510 if (max > maxindex) { 511 if (max > maxindex) {
@@ -512,51 +513,48 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
512 if (error < 0) 513 if (error < 0)
513 return error; 514 return error;
514 shift = error; 515 shift = error;
515 slot = root->rnode; 516 child = root->rnode;
516 if (order == shift) 517 if (order == shift)
517 shift += RADIX_TREE_MAP_SHIFT; 518 shift += RADIX_TREE_MAP_SHIFT;
518 } 519 }
519 520
520 offset = 0; /* uninitialised var warning */
521 while (shift > order) { 521 while (shift > order) {
522 shift -= RADIX_TREE_MAP_SHIFT; 522 shift -= RADIX_TREE_MAP_SHIFT;
523 if (slot == NULL) { 523 if (child == NULL) {
524 /* Have to add a child node. */ 524 /* Have to add a child node. */
525 slot = radix_tree_node_alloc(root); 525 child = radix_tree_node_alloc(root);
526 if (!slot) 526 if (!child)
527 return -ENOMEM; 527 return -ENOMEM;
528 slot->shift = shift; 528 child->shift = shift;
529 slot->offset = offset; 529 child->offset = offset;
530 slot->parent = node; 530 child->parent = node;
531 if (node) { 531 rcu_assign_pointer(*slot, node_to_entry(child));
532 rcu_assign_pointer(node->slots[offset], 532 if (node)
533 node_to_entry(slot));
534 node->count++; 533 node->count++;
535 } else 534 } else if (!radix_tree_is_internal_node(child))
536 rcu_assign_pointer(root->rnode,
537 node_to_entry(slot));
538 } else if (!radix_tree_is_internal_node(slot))
539 break; 535 break;
540 536
541 /* Go a level down */ 537 /* Go a level down */
542 node = entry_to_node(slot); 538 node = entry_to_node(child);
543 offset = (index >> shift) & RADIX_TREE_MAP_MASK; 539 offset = (index >> shift) & RADIX_TREE_MAP_MASK;
544 offset = radix_tree_descend(node, &slot, offset); 540 offset = radix_tree_descend(node, &child, offset);
541 slot = &node->slots[offset];
545 } 542 }
546 543
547#ifdef CONFIG_RADIX_TREE_MULTIORDER 544#ifdef CONFIG_RADIX_TREE_MULTIORDER
548 /* Insert pointers to the canonical entry */ 545 /* Insert pointers to the canonical entry */
549 if (order > shift) { 546 if (order > shift) {
550 int i, n = 1 << (order - shift); 547 unsigned i, n = 1 << (order - shift);
551 offset = offset & ~(n - 1); 548 offset = offset & ~(n - 1);
552 slot = node_to_entry(&node->slots[offset]); 549 slot = &node->slots[offset];
550 child = node_to_entry(slot);
553 for (i = 0; i < n; i++) { 551 for (i = 0; i < n; i++) {
554 if (node->slots[offset + i]) 552 if (slot[i])
555 return -EEXIST; 553 return -EEXIST;
556 } 554 }
557 555
558 for (i = 1; i < n; i++) { 556 for (i = 1; i < n; i++) {
559 rcu_assign_pointer(node->slots[offset + i], slot); 557 rcu_assign_pointer(slot[i], child);
560 node->count++; 558 node->count++;
561 } 559 }
562 } 560 }
@@ -565,7 +563,7 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
565 if (nodep) 563 if (nodep)
566 *nodep = node; 564 *nodep = node;
567 if (slotp) 565 if (slotp)
568 *slotp = node ? node->slots + offset : (void **)&root->rnode; 566 *slotp = slot;
569 return 0; 567 return 0;
570} 568}
571 569