Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 1 | /* |
| 2 | * Moving/copying garbage collector |
| 3 | * |
| 4 | * Copyright 2012 Google, Inc. |
| 5 | */ |
| 6 | |
| 7 | #include "bcache.h" |
| 8 | #include "btree.h" |
| 9 | #include "debug.h" |
| 10 | #include "request.h" |
| 11 | |
Kent Overstreet | c37511b | 2013-04-26 15:39:55 -0700 | [diff] [blame] | 12 | #include <trace/events/bcache.h> |
| 13 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 14 | struct moving_io { |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 15 | struct closure cl; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 16 | struct keybuf_key *w; |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 17 | struct data_insert_op op; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 18 | struct bbio bio; |
| 19 | }; |
| 20 | |
| 21 | static bool moving_pred(struct keybuf *buf, struct bkey *k) |
| 22 | { |
| 23 | struct cache_set *c = container_of(buf, struct cache_set, |
| 24 | moving_gc_keys); |
| 25 | unsigned i; |
| 26 | |
Kent Overstreet | 10d9dcf | 2014-02-17 15:48:36 -0800 | [diff] [blame] | 27 | for (i = 0; i < KEY_PTRS(k); i++) |
| 28 | if (ptr_available(c, k, i) && |
| 29 | GC_MOVE(PTR_BUCKET(c, k, i))) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 30 | return true; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 31 | |
| 32 | return false; |
| 33 | } |
| 34 | |
| 35 | /* Moving GC - IO loop */ |
| 36 | |
| 37 | static void moving_io_destructor(struct closure *cl) |
| 38 | { |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 39 | struct moving_io *io = container_of(cl, struct moving_io, cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 40 | kfree(io); |
| 41 | } |
| 42 | |
| 43 | static void write_moving_finish(struct closure *cl) |
| 44 | { |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 45 | struct moving_io *io = container_of(cl, struct moving_io, cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 46 | struct bio *bio = &io->bio.bio; |
Kent Overstreet | 8e51e41 | 2013-06-06 18:15:57 -0700 | [diff] [blame] | 47 | struct bio_vec *bv; |
| 48 | int i; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 49 | |
Kent Overstreet | 8e51e41 | 2013-06-06 18:15:57 -0700 | [diff] [blame] | 50 | bio_for_each_segment_all(bv, bio, i) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 51 | __free_page(bv->bv_page); |
| 52 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 53 | if (io->op.replace_collision) |
Kent Overstreet | c37511b | 2013-04-26 15:39:55 -0700 | [diff] [blame] | 54 | trace_bcache_gc_copy_collision(&io->w->key); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 55 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 56 | bch_keybuf_del(&io->op.c->moving_gc_keys, io->w); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 57 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 58 | up(&io->op.c->moving_in_flight); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 59 | |
| 60 | closure_return_with_destructor(cl, moving_io_destructor); |
| 61 | } |
| 62 | |
| 63 | static void read_moving_endio(struct bio *bio, int error) |
| 64 | { |
Kent Overstreet | 6d3d1a9 | 2013-12-16 14:12:09 -0800 | [diff] [blame] | 65 | struct bbio *b = container_of(bio, struct bbio, bio); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 66 | struct moving_io *io = container_of(bio->bi_private, |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 67 | struct moving_io, cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 68 | |
| 69 | if (error) |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 70 | io->op.error = error; |
Kent Overstreet | 6d3d1a9 | 2013-12-16 14:12:09 -0800 | [diff] [blame] | 71 | else if (!KEY_DIRTY(&b->key) && |
| 72 | ptr_stale(io->op.c, &b->key, 0)) { |
| 73 | io->op.error = -EINTR; |
| 74 | } |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 75 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 76 | bch_bbio_endio(io->op.c, bio, error, "reading data to move"); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 77 | } |
| 78 | |
| 79 | static void moving_init(struct moving_io *io) |
| 80 | { |
| 81 | struct bio *bio = &io->bio.bio; |
| 82 | |
| 83 | bio_init(bio); |
| 84 | bio_get(bio); |
| 85 | bio_set_prio(bio, IOPRIO_PRIO_VALUE(IOPRIO_CLASS_IDLE, 0)); |
| 86 | |
Kent Overstreet | 4f024f3 | 2013-10-11 15:44:27 -0700 | [diff] [blame] | 87 | bio->bi_iter.bi_size = KEY_SIZE(&io->w->key) << 9; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 88 | bio->bi_max_vecs = DIV_ROUND_UP(KEY_SIZE(&io->w->key), |
| 89 | PAGE_SECTORS); |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 90 | bio->bi_private = &io->cl; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 91 | bio->bi_io_vec = bio->bi_inline_vecs; |
Kent Overstreet | 169ef1c | 2013-03-28 12:50:55 -0600 | [diff] [blame] | 92 | bch_bio_map(bio, NULL); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 93 | } |
| 94 | |
| 95 | static void write_moving(struct closure *cl) |
| 96 | { |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 97 | struct moving_io *io = container_of(cl, struct moving_io, cl); |
| 98 | struct data_insert_op *op = &io->op; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 99 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 100 | if (!op->error) { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 101 | moving_init(io); |
| 102 | |
Kent Overstreet | 4f024f3 | 2013-10-11 15:44:27 -0700 | [diff] [blame] | 103 | io->bio.bio.bi_iter.bi_sector = KEY_START(&io->w->key); |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 104 | op->write_prio = 1; |
| 105 | op->bio = &io->bio.bio; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 106 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 107 | op->writeback = KEY_DIRTY(&io->w->key); |
| 108 | op->csum = KEY_CSUM(&io->w->key); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 109 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 110 | bkey_copy(&op->replace_key, &io->w->key); |
| 111 | op->replace = true; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 112 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 113 | closure_call(&op->cl, bch_data_insert, NULL, cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 114 | } |
| 115 | |
Nicholas Swenson | da415a0 | 2014-01-09 16:03:04 -0800 | [diff] [blame] | 116 | continue_at(cl, write_moving_finish, op->wq); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 117 | } |
| 118 | |
| 119 | static void read_moving_submit(struct closure *cl) |
| 120 | { |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 121 | struct moving_io *io = container_of(cl, struct moving_io, cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 122 | struct bio *bio = &io->bio.bio; |
| 123 | |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 124 | bch_submit_bbio(bio, io->op.c, &io->w->key, 0); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 125 | |
Nicholas Swenson | da415a0 | 2014-01-09 16:03:04 -0800 | [diff] [blame] | 126 | continue_at(cl, write_moving, io->op.wq); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 127 | } |
| 128 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 129 | static void read_moving(struct cache_set *c) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 130 | { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 131 | struct keybuf_key *w; |
| 132 | struct moving_io *io; |
| 133 | struct bio *bio; |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 134 | struct closure cl; |
| 135 | |
| 136 | closure_init_stack(&cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 137 | |
| 138 | /* XXX: if we error, background writeback could stall indefinitely */ |
| 139 | |
| 140 | while (!test_bit(CACHE_SET_STOPPING, &c->flags)) { |
Kent Overstreet | 72c2706 | 2013-06-05 06:24:39 -0700 | [diff] [blame] | 141 | w = bch_keybuf_next_rescan(c, &c->moving_gc_keys, |
| 142 | &MAX_KEY, moving_pred); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 143 | if (!w) |
| 144 | break; |
| 145 | |
Kent Overstreet | 6d3d1a9 | 2013-12-16 14:12:09 -0800 | [diff] [blame] | 146 | if (ptr_stale(c, &w->key, 0)) { |
| 147 | bch_keybuf_del(&c->moving_gc_keys, w); |
| 148 | continue; |
| 149 | } |
| 150 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 151 | io = kzalloc(sizeof(struct moving_io) + sizeof(struct bio_vec) |
| 152 | * DIV_ROUND_UP(KEY_SIZE(&w->key), PAGE_SECTORS), |
| 153 | GFP_KERNEL); |
| 154 | if (!io) |
| 155 | goto err; |
| 156 | |
| 157 | w->private = io; |
| 158 | io->w = w; |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 159 | io->op.inode = KEY_INODE(&w->key); |
| 160 | io->op.c = c; |
Nicholas Swenson | da415a0 | 2014-01-09 16:03:04 -0800 | [diff] [blame] | 161 | io->op.wq = c->moving_gc_wq; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 162 | |
| 163 | moving_init(io); |
| 164 | bio = &io->bio.bio; |
| 165 | |
| 166 | bio->bi_rw = READ; |
| 167 | bio->bi_end_io = read_moving_endio; |
| 168 | |
Kent Overstreet | 8e51e41 | 2013-06-06 18:15:57 -0700 | [diff] [blame] | 169 | if (bio_alloc_pages(bio, GFP_KERNEL)) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 170 | goto err; |
| 171 | |
Kent Overstreet | c37511b | 2013-04-26 15:39:55 -0700 | [diff] [blame] | 172 | trace_bcache_gc_copy(&w->key); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 173 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 174 | down(&c->moving_in_flight); |
Kent Overstreet | 220bb38 | 2013-09-10 19:02:45 -0700 | [diff] [blame] | 175 | closure_call(&io->cl, read_moving_submit, NULL, &cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 176 | } |
| 177 | |
| 178 | if (0) { |
| 179 | err: if (!IS_ERR_OR_NULL(w->private)) |
| 180 | kfree(w->private); |
| 181 | |
| 182 | bch_keybuf_del(&c->moving_gc_keys, w); |
| 183 | } |
| 184 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 185 | closure_sync(&cl); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 186 | } |
| 187 | |
Kent Overstreet | b1a67b0 | 2013-03-25 11:46:44 -0700 | [diff] [blame] | 188 | static bool bucket_cmp(struct bucket *l, struct bucket *r) |
| 189 | { |
| 190 | return GC_SECTORS_USED(l) < GC_SECTORS_USED(r); |
| 191 | } |
| 192 | |
| 193 | static unsigned bucket_heap_top(struct cache *ca) |
| 194 | { |
Nicholas Swenson | bee63f4 | 2013-10-31 19:25:18 -0700 | [diff] [blame] | 195 | struct bucket *b; |
| 196 | return (b = heap_peek(&ca->heap)) ? GC_SECTORS_USED(b) : 0; |
Kent Overstreet | b1a67b0 | 2013-03-25 11:46:44 -0700 | [diff] [blame] | 197 | } |
| 198 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 199 | void bch_moving_gc(struct cache_set *c) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 200 | { |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 201 | struct cache *ca; |
| 202 | struct bucket *b; |
| 203 | unsigned i; |
| 204 | |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 205 | if (!c->copy_gc_enabled) |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 206 | return; |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 207 | |
| 208 | mutex_lock(&c->bucket_lock); |
| 209 | |
| 210 | for_each_cache(ca, c, i) { |
| 211 | unsigned sectors_to_move = 0; |
| 212 | unsigned reserve_sectors = ca->sb.bucket_size * |
Kent Overstreet | 7836541 | 2013-12-17 01:29:34 -0800 | [diff] [blame] | 213 | fifo_used(&ca->free[RESERVE_MOVINGGC]); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 214 | |
| 215 | ca->heap.used = 0; |
| 216 | |
| 217 | for_each_bucket(b, ca) { |
Nicholas Swenson | 3f6ef38 | 2014-01-23 15:21:02 -0800 | [diff] [blame] | 218 | if (GC_MARK(b) == GC_MARK_METADATA || |
| 219 | !GC_SECTORS_USED(b) || |
| 220 | GC_SECTORS_USED(b) == ca->sb.bucket_size || |
| 221 | atomic_read(&b->pin)) |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 222 | continue; |
| 223 | |
| 224 | if (!heap_full(&ca->heap)) { |
| 225 | sectors_to_move += GC_SECTORS_USED(b); |
| 226 | heap_add(&ca->heap, b, bucket_cmp); |
| 227 | } else if (bucket_cmp(b, heap_peek(&ca->heap))) { |
Kent Overstreet | b1a67b0 | 2013-03-25 11:46:44 -0700 | [diff] [blame] | 228 | sectors_to_move -= bucket_heap_top(ca); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 229 | sectors_to_move += GC_SECTORS_USED(b); |
| 230 | |
| 231 | ca->heap.data[0] = b; |
| 232 | heap_sift(&ca->heap, 0, bucket_cmp); |
| 233 | } |
| 234 | } |
| 235 | |
| 236 | while (sectors_to_move > reserve_sectors) { |
| 237 | heap_pop(&ca->heap, b, bucket_cmp); |
| 238 | sectors_to_move -= GC_SECTORS_USED(b); |
| 239 | } |
| 240 | |
Nicholas Swenson | 981aa8c | 2013-11-07 17:53:19 -0800 | [diff] [blame] | 241 | while (heap_pop(&ca->heap, b, bucket_cmp)) |
| 242 | SET_GC_MOVE(b, 1); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 243 | } |
| 244 | |
| 245 | mutex_unlock(&c->bucket_lock); |
| 246 | |
| 247 | c->moving_gc_keys.last_scanned = ZERO_KEY; |
| 248 | |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 249 | read_moving(c); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 250 | } |
| 251 | |
| 252 | void bch_moving_init_cache_set(struct cache_set *c) |
| 253 | { |
Kent Overstreet | 72c2706 | 2013-06-05 06:24:39 -0700 | [diff] [blame] | 254 | bch_keybuf_init(&c->moving_gc_keys); |
Kent Overstreet | 72a4451 | 2013-10-24 17:19:26 -0700 | [diff] [blame] | 255 | sema_init(&c->moving_in_flight, 64); |
Kent Overstreet | cafe563 | 2013-03-23 16:11:31 -0700 | [diff] [blame] | 256 | } |