lib: radix-tree: check accounting of existing slot replacement users

[linux-2.6-microblaze.git] / include / linux / radix-tree.h

diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 52b97db..2d1b9b8 100644 (file)
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -85,9 +85,10 @@ static inline bool radix_tree_is_internal_node(void *ptr)
 #define RADIX_TREE_COUNT_MASK  ((1UL << RADIX_TREE_COUNT_SHIFT) - 1)
 
 struct radix_tree_node {
-       unsigned char   shift;  /* Bits remaining in each slot */
-       unsigned char   offset; /* Slot offset in parent */
-       unsigned int    count;
+       unsigned char   shift;          /* Bits remaining in each slot */
+       unsigned char   offset;         /* Slot offset in parent */
+       unsigned int    count;          /* Total entry count */
+       unsigned char   exceptional;    /* Exceptional entry count */
        union {
                struct {
                        /* Used when ascending tree */
@@ -248,20 +249,6 @@ static inline int radix_tree_exception(void *arg)
        return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
 }
 
-/**
- * radix_tree_replace_slot     - replace item in a slot
- * @pslot:     pointer to slot, returned by radix_tree_lookup_slot
- * @item:      new item to store in the slot.
- *
- * For use with radix_tree_lookup_slot().  Caller must hold tree write locked
- * across slot lookup and replacement.
- */
-static inline void radix_tree_replace_slot(void **pslot, void *item)
-{
-       BUG_ON(radix_tree_is_internal_node(item));
-       rcu_assign_pointer(*pslot, item);
-}
-
 int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
                        unsigned order, struct radix_tree_node **nodep,
                        void ***slotp);
@@ -276,6 +263,11 @@ void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index,
                          struct radix_tree_node **nodep, void ***slotp);
 void *radix_tree_lookup(struct radix_tree_root *, unsigned long);
 void **radix_tree_lookup_slot(struct radix_tree_root *, unsigned long);
+void __radix_tree_replace(struct radix_tree_root *root,
+                         struct radix_tree_node *node,
+                         void **slot, void *item);
+void radix_tree_replace_slot(struct radix_tree_root *root,
+                            void **slot, void *item);
 bool __radix_tree_delete_node(struct radix_tree_root *root,
                              struct radix_tree_node *node);
 void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
@@ -461,6 +453,14 @@ static inline struct radix_tree_node *entry_to_node(void *ptr)
  *
  * This function updates @iter->index in the case of a successful lookup.
  * For tagged lookup it also eats @iter->tags.
+ *
+ * There are several cases where 'slot' can be passed in as NULL to this
+ * function.  These cases result from the use of radix_tree_iter_next() or
+ * radix_tree_iter_retry().  In these cases we don't end up dereferencing
+ * 'slot' because either:
+ * a) we are doing tagged iteration and iter->tags has been set to 0, or
+ * b) we are doing non-tagged iteration, and iter->index and iter->next_index
+ *    have been set up so that radix_tree_chunk_size() returns 1 or 0.
  */
 static __always_inline void **
 radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)