git.sesse.net Git - bcachefs-tools-debian/blob - libbcache/keybuf.c

   1
   2 #include "bcache.h"
   3 #include "btree_gc.h"
   4 #include "btree_iter.h"
   5 #include "keybuf.h"
   6
   7 #include <trace/events/bcache.h>
   8
   9 /*
  10  * For buffered iteration over the btree, with predicates and ratelimiting and
  11  * whatnot
  12  */
  13
  14 static inline int keybuf_cmp(struct keybuf_key *l, struct keybuf_key *r)
  15 {
  16         /* Overlapping keys compare equal */
  17         if (bkey_cmp(l->key.k.p, bkey_start_pos(&r->key.k)) <= 0)
  18                 return -1;
  19         if (bkey_cmp(bkey_start_pos(&l->key.k), r->key.k.p) >= 0)
  20                 return 1;
  21         return 0;
  22 }
  23
  24 static inline int keybuf_nonoverlapping_cmp(struct keybuf_key *l,
  25                                             struct keybuf_key *r)
  26 {
  27         return clamp_t(s64, bkey_cmp(l->key.k.p, r->key.k.p), -1, 1);
  28 }
  29
  30 void bch_refill_keybuf(struct cache_set *c, struct keybuf *buf,
  31                        struct bpos end, keybuf_pred_fn *pred)
  32 {
  33         struct bpos start = buf->last_scanned;
  34         struct btree_iter iter;
  35         struct bkey_s_c k;
  36         unsigned nr_found = 0;
  37
  38         for_each_btree_key(&iter, c, BTREE_ID_EXTENTS, buf->last_scanned, k) {
  39                 if (bkey_cmp(k.k->p, end) >= 0) {
  40                         buf->last_scanned = k.k->p;
  41                         goto done;
  42                 }
  43
  44                 if (pred(buf, k)) {
  45                         struct keybuf_key *w;
  46
  47                         spin_lock(&buf->lock);
  48
  49                         w = array_alloc(&buf->freelist);
  50                         if (!w) {
  51                                 spin_unlock(&buf->lock);
  52                                 goto done;
  53                         }
  54
  55                         bkey_reassemble(&w->key, k);
  56                         atomic_set(&w->ref, -1); /* -1 means hasn't started */
  57
  58                         if (RB_INSERT(&buf->keys, w, node, keybuf_cmp))
  59                                 array_free(&buf->freelist, w);
  60                         else
  61                                 nr_found++;
  62
  63                         spin_unlock(&buf->lock);
  64                 }
  65
  66                 buf->last_scanned = k.k->p;
  67                 bch_btree_iter_cond_resched(&iter);
  68         }
  69
  70         /* If we end up here, it means:
  71          * - the map_fn didn't fill up the keybuf
  72          * - the map_fn didn't see the end key
  73          * - there were no more keys to map over
  74          * Therefore, we are at the end of the key space */
  75         buf->last_scanned = POS_MAX;
  76 done:
  77         bch_btree_iter_unlock(&iter);
  78
  79         trace_bcache_keyscan(nr_found,
  80                              start.inode, start.offset,
  81                              buf->last_scanned.inode,
  82                              buf->last_scanned.offset);
  83
  84         spin_lock(&buf->lock);
  85
  86         if (!RB_EMPTY_ROOT(&buf->keys)) {
  87                 struct keybuf_key *w;
  88
  89                 w = RB_FIRST(&buf->keys, struct keybuf_key, node);
  90                 buf->start      = bkey_start_pos(&w->key.k);
  91
  92                 w = RB_LAST(&buf->keys, struct keybuf_key, node);
  93                 buf->end        = w->key.k.p;
  94         } else {
  95                 buf->start      = POS_MAX;
  96                 buf->end        = POS_MAX;
  97         }
  98
  99         spin_unlock(&buf->lock);
 100 }
 101
 102 static void bch_keybuf_del(struct keybuf *buf, struct keybuf_key *w)
 103 {
 104         rb_erase(&w->node, &buf->keys);
 105         array_free(&buf->freelist, w);
 106 }
 107
 108 void bch_keybuf_put(struct keybuf *buf, struct keybuf_key *w)
 109 {
 110         BUG_ON(atomic_read(&w->ref) <= 0);
 111
 112         if (atomic_dec_and_test(&w->ref)) {
 113                 up(&buf->in_flight);
 114
 115                 spin_lock(&buf->lock);
 116                 bch_keybuf_del(buf, w);
 117                 spin_unlock(&buf->lock);
 118         }
 119 }
 120
 121 void bch_keybuf_recalc_oldest_gens(struct cache_set *c, struct keybuf *buf)
 122 {
 123         struct keybuf_key *w, *n;
 124
 125         spin_lock(&buf->lock);
 126         rbtree_postorder_for_each_entry_safe(w, n,
 127                                 &buf->keys, node)
 128                 bch_btree_key_recalc_oldest_gen(c, bkey_i_to_s_c(&w->key));
 129         spin_unlock(&buf->lock);
 130 }
 131
 132 bool bch_keybuf_check_overlapping(struct keybuf *buf, struct bpos start,
 133                                   struct bpos end)
 134 {
 135         bool ret = false;
 136         struct keybuf_key *w, *next, s = { .key.k.p = start };
 137
 138         if (bkey_cmp(end, buf->start) <= 0 ||
 139             bkey_cmp(start, buf->end) >= 0)
 140                 return false;
 141
 142         spin_lock(&buf->lock);
 143
 144         for (w = RB_GREATER(&buf->keys, s, node, keybuf_nonoverlapping_cmp);
 145              w && bkey_cmp(bkey_start_pos(&w->key.k), end) < 0;
 146              w = next) {
 147                 next = RB_NEXT(w, node);
 148
 149                 if (atomic_read(&w->ref) == -1)
 150                         bch_keybuf_del(buf, w);
 151                 else
 152                         ret = true;
 153         }
 154
 155         spin_unlock(&buf->lock);
 156         return ret;
 157 }
 158
 159 struct keybuf_key *bch_keybuf_next(struct keybuf *buf)
 160 {
 161         struct keybuf_key *w;
 162
 163         spin_lock(&buf->lock);
 164
 165         w = RB_FIRST(&buf->keys, struct keybuf_key, node);
 166
 167         while (w && atomic_read(&w->ref) != -1)
 168                 w = RB_NEXT(w, node);
 169
 170         if (!w) {
 171                 spin_unlock(&buf->lock);
 172                 return NULL;
 173         }
 174
 175         atomic_set(&w->ref, 1);
 176         spin_unlock(&buf->lock);
 177
 178         down(&buf->in_flight);
 179
 180         return w;
 181 }
 182
 183 void bch_keybuf_init(struct keybuf *buf)
 184 {
 185         sema_init(&buf->in_flight, KEYBUF_REFILL_BATCH / 2);
 186
 187         buf->last_scanned       = POS_MAX;
 188         buf->start              = POS_MIN;
 189         buf->end                = POS_MIN;
 190
 191         buf->keys               = RB_ROOT;
 192
 193         spin_lock_init(&buf->lock);
 194         array_allocator_init(&buf->freelist);
 195 }