lib/radix-tree.c: change to simpler include

[firefly-linux-kernel-4.4.55.git] / lib / rhashtable.c

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index c2c39495fac6a038c968fa2791f79e41465397ce..9cc4c4a90d00686228bebdfe55b212c34e98206f 100644 (file)
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -23,6 +23,7 @@
 #include <linux/jhash.h>
 #include <linux/random.h>
 #include <linux/rhashtable.h>
+#include <linux/err.h>
 
 #define HASH_DEFAULT_SIZE      64UL
 #define HASH_MIN_SIZE          4UL
@@ -348,9 +349,11 @@ static bool hashtable_chain_unzip(struct rhashtable *ht,
        return !rht_is_a_nulls(p);
 }
 
-static void link_old_to_new(struct bucket_table *new_tbl,
+static void link_old_to_new(struct rhashtable *ht, struct bucket_table *new_tbl,
                            unsigned int new_hash, struct rhash_head *entry)
 {
+       ASSERT_BUCKET_LOCK(ht, new_tbl, new_hash);
+
        rcu_assign_pointer(*bucket_tail(new_tbl, new_hash), entry);
 }
 
@@ -406,19 +409,13 @@ int rhashtable_expand(struct rhashtable *ht)
                lock_buckets(new_tbl, old_tbl, new_hash);
                rht_for_each(he, old_tbl, old_hash) {
                        if (head_hashfn(ht, new_tbl, he) == new_hash) {
-                               link_old_to_new(new_tbl, new_hash, he);
+                               link_old_to_new(ht, new_tbl, new_hash, he);
                                break;
                        }
                }
                unlock_buckets(new_tbl, old_tbl, new_hash);
        }
 
-       /* Publish the new table pointer. Lookups may now traverse
-        * the new table, but they will not benefit from any
-        * additional efficiency until later steps unzip the buckets.
-        */
-       rcu_assign_pointer(ht->tbl, new_tbl);
-
        /* Unzip interleaved hash chains */
        while (!complete && !ht->being_destroyed) {
                /* Wait for readers. All new readers will see the new
@@ -443,6 +440,7 @@ int rhashtable_expand(struct rhashtable *ht)
                }
        }
 
+       rcu_assign_pointer(ht->tbl, new_tbl);
        synchronize_rcu();
 
        bucket_table_free(old_tbl);
@@ -492,6 +490,7 @@ int rhashtable_shrink(struct rhashtable *ht)
 
                rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
                                   tbl->buckets[new_hash]);
+               ASSERT_BUCKET_LOCK(ht, tbl, new_hash + new_tbl->size);
                rcu_assign_pointer(*bucket_tail(new_tbl, new_hash),
                                   tbl->buckets[new_hash + new_tbl->size]);
 
@@ -554,8 +553,12 @@ static void rhashtable_wakeup_worker(struct rhashtable *ht)
 static void __rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj,
                                struct bucket_table *tbl, u32 hash)
 {
-       struct rhash_head *head = rht_dereference_bucket(tbl->buckets[hash],
-                                                        tbl, hash);
+       struct rhash_head *head;
+
+       hash = rht_bucket_index(tbl, hash);
+       head = rht_dereference_bucket(tbl->buckets[hash], tbl, hash);
+
+       ASSERT_BUCKET_LOCK(ht, tbl, hash);
 
        if (rht_is_a_nulls(head))
                INIT_RHT_NULLS_HEAD(obj->next, ht, hash);
@@ -593,7 +596,7 @@ void rhashtable_insert(struct rhashtable *ht, struct rhash_head *obj)
 
        tbl = rht_dereference_rcu(ht->future_tbl, ht);
        old_tbl = rht_dereference_rcu(ht->tbl, ht);
-       hash = head_hashfn(ht, tbl, obj);
+       hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
        lock_buckets(tbl, old_tbl, hash);
        __rhashtable_insert(ht, obj, tbl, hash);
@@ -622,14 +625,14 @@ bool rhashtable_remove(struct rhashtable *ht, struct rhash_head *obj)
 {
        struct bucket_table *tbl, *new_tbl, *old_tbl;
        struct rhash_head __rcu **pprev;
-       struct rhash_head *he;
+       struct rhash_head *he, *he2;
        unsigned int hash, new_hash;
        bool ret = false;
 
        rcu_read_lock();
-       tbl = old_tbl = rht_dereference_rcu(ht->tbl, ht);
-       new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-       new_hash = head_hashfn(ht, new_tbl, obj);
+       old_tbl = rht_dereference_rcu(ht->tbl, ht);
+       tbl = new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
+       new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
        lock_buckets(new_tbl, old_tbl, new_hash);
 restart:
@@ -641,8 +644,26 @@ restart:
                        continue;
                }
 
-               rcu_assign_pointer(*pprev, obj->next);
+               ASSERT_BUCKET_LOCK(ht, tbl, hash);
+
+               if (old_tbl->size > new_tbl->size && tbl == old_tbl &&
+                   !rht_is_a_nulls(obj->next) &&
+                   head_hashfn(ht, tbl, obj->next) != hash) {
+                       rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
+               } else if (unlikely(old_tbl->size < new_tbl->size && tbl == new_tbl)) {
+                       rht_for_each_continue(he2, obj->next, tbl, hash) {
+                               if (head_hashfn(ht, tbl, he2) == hash) {
+                                       rcu_assign_pointer(*pprev, he2);
+                                       goto found;
+                               }
+                       }
 
+                       rcu_assign_pointer(*pprev, (struct rhash_head *) rht_marker(ht, hash));
+               } else {
+                       rcu_assign_pointer(*pprev, obj->next);
+               }
+
+found:
                ret = true;
                break;
        }
@@ -652,8 +673,8 @@ restart:
         * resizing. Thus traversing both is fine and the added cost is
         * very rare.
         */
-       if (tbl != new_tbl) {
-               tbl = new_tbl;
+       if (tbl != old_tbl) {
+               tbl = old_tbl;
                goto restart;
        }
 
@@ -821,7 +842,7 @@ bool rhashtable_lookup_compare_insert(struct rhashtable *ht,
        rcu_read_lock();
        old_tbl = rht_dereference_rcu(ht->tbl, ht);
        new_tbl = rht_dereference_rcu(ht->future_tbl, ht);
-       new_hash = head_hashfn(ht, new_tbl, obj);
+       new_hash = obj_raw_hashfn(ht, rht_obj(ht, obj));
 
        lock_buckets(new_tbl, old_tbl, new_hash);