aboutsummaryrefslogtreecommitdiffstats
path: root/lib/radix-tree.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/radix-tree.c')
-rw-r--r--lib/radix-tree.c41
1 files changed, 20 insertions, 21 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c
index 92cdd9936e3d..05da38bcc298 100644
--- a/lib/radix-tree.c
+++ b/lib/radix-tree.c
@@ -28,7 +28,6 @@
28#include <linux/slab.h> 28#include <linux/slab.h>
29#include <linux/notifier.h> 29#include <linux/notifier.h>
30#include <linux/cpu.h> 30#include <linux/cpu.h>
31#include <linux/gfp.h>
32#include <linux/string.h> 31#include <linux/string.h>
33#include <linux/bitops.h> 32#include <linux/bitops.h>
34#include <linux/rcupdate.h> 33#include <linux/rcupdate.h>
@@ -364,7 +363,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
364 unsigned int height, shift; 363 unsigned int height, shift;
365 struct radix_tree_node *node, **slot; 364 struct radix_tree_node *node, **slot;
366 365
367 node = rcu_dereference(root->rnode); 366 node = rcu_dereference_raw(root->rnode);
368 if (node == NULL) 367 if (node == NULL)
369 return NULL; 368 return NULL;
370 369
@@ -384,7 +383,7 @@ static void *radix_tree_lookup_element(struct radix_tree_root *root,
384 do { 383 do {
385 slot = (struct radix_tree_node **) 384 slot = (struct radix_tree_node **)
386 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); 385 (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
387 node = rcu_dereference(*slot); 386 node = rcu_dereference_raw(*slot);
388 if (node == NULL) 387 if (node == NULL)
389 return NULL; 388 return NULL;
390 389
@@ -556,6 +555,10 @@ EXPORT_SYMBOL(radix_tree_tag_clear);
556 * 555 *
557 * 0: tag not present or not set 556 * 0: tag not present or not set
558 * 1: tag set 557 * 1: tag set
558 *
559 * Note that the return value of this function may not be relied on, even if
560 * the RCU lock is held, unless tag modification and node deletion are excluded
561 * from concurrency.
559 */ 562 */
560int radix_tree_tag_get(struct radix_tree_root *root, 563int radix_tree_tag_get(struct radix_tree_root *root,
561 unsigned long index, unsigned int tag) 564 unsigned long index, unsigned int tag)
@@ -568,7 +571,7 @@ int radix_tree_tag_get(struct radix_tree_root *root,
568 if (!root_tag_get(root, tag)) 571 if (!root_tag_get(root, tag))
569 return 0; 572 return 0;
570 573
571 node = rcu_dereference(root->rnode); 574 node = rcu_dereference_raw(root->rnode);
572 if (node == NULL) 575 if (node == NULL)
573 return 0; 576 return 0;
574 577
@@ -596,13 +599,9 @@ int radix_tree_tag_get(struct radix_tree_root *root,
596 */ 599 */
597 if (!tag_get(node, tag, offset)) 600 if (!tag_get(node, tag, offset))
598 saw_unset_tag = 1; 601 saw_unset_tag = 1;
599 if (height == 1) { 602 if (height == 1)
600 int ret = tag_get(node, tag, offset); 603 return !!tag_get(node, tag, offset);
601 604 node = rcu_dereference_raw(node->slots[offset]);
602 BUG_ON(ret && saw_unset_tag);
603 return !!ret;
604 }
605 node = rcu_dereference(node->slots[offset]);
606 shift -= RADIX_TREE_MAP_SHIFT; 605 shift -= RADIX_TREE_MAP_SHIFT;
607 height--; 606 height--;
608 } 607 }
@@ -657,7 +656,7 @@ EXPORT_SYMBOL(radix_tree_next_hole);
657 * 656 *
658 * Returns: the index of the hole if found, otherwise returns an index 657 * Returns: the index of the hole if found, otherwise returns an index
659 * outside of the set specified (in which case 'index - return >= max_scan' 658 * outside of the set specified (in which case 'index - return >= max_scan'
660 * will be true). In rare cases of wrap-around, LONG_MAX will be returned. 659 * will be true). In rare cases of wrap-around, ULONG_MAX will be returned.
661 * 660 *
662 * radix_tree_next_hole may be called under rcu_read_lock. However, like 661 * radix_tree_next_hole may be called under rcu_read_lock. However, like
663 * radix_tree_gang_lookup, this will not atomically search a snapshot of 662 * radix_tree_gang_lookup, this will not atomically search a snapshot of
@@ -675,7 +674,7 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
675 if (!radix_tree_lookup(root, index)) 674 if (!radix_tree_lookup(root, index))
676 break; 675 break;
677 index--; 676 index--;
678 if (index == LONG_MAX) 677 if (index == ULONG_MAX)
679 break; 678 break;
680 } 679 }
681 680
@@ -711,7 +710,7 @@ __lookup(struct radix_tree_node *slot, void ***results, unsigned long index,
711 } 710 }
712 711
713 shift -= RADIX_TREE_MAP_SHIFT; 712 shift -= RADIX_TREE_MAP_SHIFT;
714 slot = rcu_dereference(slot->slots[i]); 713 slot = rcu_dereference_raw(slot->slots[i]);
715 if (slot == NULL) 714 if (slot == NULL)
716 goto out; 715 goto out;
717 } 716 }
@@ -758,7 +757,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
758 unsigned long cur_index = first_index; 757 unsigned long cur_index = first_index;
759 unsigned int ret; 758 unsigned int ret;
760 759
761 node = rcu_dereference(root->rnode); 760 node = rcu_dereference_raw(root->rnode);
762 if (!node) 761 if (!node)
763 return 0; 762 return 0;
764 763
@@ -787,7 +786,7 @@ radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
787 slot = *(((void ***)results)[ret + i]); 786 slot = *(((void ***)results)[ret + i]);
788 if (!slot) 787 if (!slot)
789 continue; 788 continue;
790 results[ret + nr_found] = rcu_dereference(slot); 789 results[ret + nr_found] = rcu_dereference_raw(slot);
791 nr_found++; 790 nr_found++;
792 } 791 }
793 ret += nr_found; 792 ret += nr_found;
@@ -826,7 +825,7 @@ radix_tree_gang_lookup_slot(struct radix_tree_root *root, void ***results,
826 unsigned long cur_index = first_index; 825 unsigned long cur_index = first_index;
827 unsigned int ret; 826 unsigned int ret;
828 827
829 node = rcu_dereference(root->rnode); 828 node = rcu_dereference_raw(root->rnode);
830 if (!node) 829 if (!node)
831 return 0; 830 return 0;
832 831
@@ -915,7 +914,7 @@ __lookup_tag(struct radix_tree_node *slot, void ***results, unsigned long index,
915 } 914 }
916 } 915 }
917 shift -= RADIX_TREE_MAP_SHIFT; 916 shift -= RADIX_TREE_MAP_SHIFT;
918 slot = rcu_dereference(slot->slots[i]); 917 slot = rcu_dereference_raw(slot->slots[i]);
919 if (slot == NULL) 918 if (slot == NULL)
920 break; 919 break;
921 } 920 }
@@ -951,7 +950,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
951 if (!root_tag_get(root, tag)) 950 if (!root_tag_get(root, tag))
952 return 0; 951 return 0;
953 952
954 node = rcu_dereference(root->rnode); 953 node = rcu_dereference_raw(root->rnode);
955 if (!node) 954 if (!node)
956 return 0; 955 return 0;
957 956
@@ -980,7 +979,7 @@ radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
980 slot = *(((void ***)results)[ret + i]); 979 slot = *(((void ***)results)[ret + i]);
981 if (!slot) 980 if (!slot)
982 continue; 981 continue;
983 results[ret + nr_found] = rcu_dereference(slot); 982 results[ret + nr_found] = rcu_dereference_raw(slot);
984 nr_found++; 983 nr_found++;
985 } 984 }
986 ret += nr_found; 985 ret += nr_found;
@@ -1020,7 +1019,7 @@ radix_tree_gang_lookup_tag_slot(struct radix_tree_root *root, void ***results,
1020 if (!root_tag_get(root, tag)) 1019 if (!root_tag_get(root, tag))
1021 return 0; 1020 return 0;
1022 1021
1023 node = rcu_dereference(root->rnode); 1022 node = rcu_dereference_raw(root->rnode);
1024 if (!node) 1023 if (!node)
1025 return 0; 1024 return 0;
1026 1025