Merge tag 'gvt-fixes-2020-03-10' of https://github.com/intel/gvt-linux into drm-intel...

[linux.git] / kernel / bpf / hashtab.c

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 2d182c4ee9d9964a6ec55ea102a5de9c7b6fc811..a1468e3f5af24e33acbfaa392db9770cea249668 100644 (file)
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -56,6 +56,7 @@ struct htab_elem {
                        union {
                                struct bpf_htab *htab;
                                struct pcpu_freelist_node fnode;
+                               struct htab_elem *batch_flink;
                        };
                };
        };
@@ -126,6 +127,17 @@ static void htab_free_elems(struct bpf_htab *htab)
        bpf_map_area_free(htab->elems);
 }
 
+/* The LRU list has a lock (lru_lock). Each htab bucket has a lock
+ * (bucket_lock). If both locks need to be acquired together, the lock
+ * order is always lru_lock -> bucket_lock and this only happens in
+ * bpf_lru_list.c logic. For example, certain code path of
+ * bpf_lru_pop_free(), which is called by function prealloc_lru_pop(),
+ * will acquire lru_lock first followed by acquiring bucket_lock.
+ *
+ * In hashtab.c, to avoid deadlock, lock acquisition of
+ * bucket_lock followed by lru_lock is not allowed. In such cases,
+ * bucket_lock needs to be released first before acquiring lru_lock.
+ */
 static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key,
                                          u32 hash)
 {
@@ -1256,10 +1268,12 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
        void __user *ukeys = u64_to_user_ptr(attr->batch.keys);
        void *ubatch = u64_to_user_ptr(attr->batch.in_batch);
        u32 batch, max_count, size, bucket_size;
+       struct htab_elem *node_to_free = NULL;
        u64 elem_map_flags, map_flags;
        struct hlist_nulls_head *head;
        struct hlist_nulls_node *n;
-       unsigned long flags;
+       unsigned long flags = 0;
+       bool locked = false;
        struct htab_elem *l;
        struct bucket *b;
        int ret = 0;
@@ -1319,15 +1333,25 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
        dst_val = values;
        b = &htab->buckets[batch];
        head = &b->head;
-       raw_spin_lock_irqsave(&b->lock, flags);
+       /* do not grab the lock unless need it (bucket_cnt > 0). */
+       if (locked)
+               raw_spin_lock_irqsave(&b->lock, flags);
 
        bucket_cnt = 0;
        hlist_nulls_for_each_entry_rcu(l, n, head, hash_node)
                bucket_cnt++;
 
+       if (bucket_cnt && !locked) {
+               locked = true;
+               goto again_nocopy;
+       }
+
        if (bucket_cnt > (max_count - total)) {
                if (total == 0)
                        ret = -ENOSPC;
+               /* Note that since bucket_cnt > 0 here, it is implicit
+                * that the locked was grabbed, so release it.
+                */
                raw_spin_unlock_irqrestore(&b->lock, flags);
                rcu_read_unlock();
                this_cpu_dec(bpf_prog_active);
@@ -1337,6 +1361,9 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
 
        if (bucket_cnt > bucket_size) {
                bucket_size = bucket_cnt;
+               /* Note that since bucket_cnt > 0 here, it is implicit
+                * that the locked was grabbed, so release it.
+                */
                raw_spin_unlock_irqrestore(&b->lock, flags);
                rcu_read_unlock();
                this_cpu_dec(bpf_prog_active);
@@ -1346,6 +1373,10 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
                goto alloc;
        }
 
+       /* Next block is only safe to run if you have grabbed the lock */
+       if (!locked)
+               goto next_batch;
+
        hlist_nulls_for_each_entry_safe(l, n, head, hash_node) {
                memcpy(dst_key, l->key, key_size);
 
@@ -1370,16 +1401,33 @@ __htab_map_lookup_and_delete_batch(struct bpf_map *map,
                }
                if (do_delete) {
                        hlist_nulls_del_rcu(&l->hash_node);
-                       if (is_lru_map)
-                               bpf_lru_push_free(&htab->lru, &l->lru_node);
-                       else
+
+                       /* bpf_lru_push_free() will acquire lru_lock, which
+                        * may cause deadlock. See comments in function
+                        * prealloc_lru_pop(). Let us do bpf_lru_push_free()
+                        * after releasing the bucket lock.
+                        */
+                       if (is_lru_map) {
+                               l->batch_flink = node_to_free;
+                               node_to_free = l;
+                       } else {
                                free_htab_elem(htab, l);
+                       }
                }
                dst_key += key_size;
                dst_val += value_size;
        }
 
        raw_spin_unlock_irqrestore(&b->lock, flags);
+       locked = false;
+
+       while (node_to_free) {
+               l = node_to_free;
+               node_to_free = node_to_free->batch_flink;
+               bpf_lru_push_free(&htab->lru, &l->lru_node);
+       }
+
+next_batch:
        /* If we are not copying data, we can go to next bucket and avoid
         * unlocking the rcu.
         */