git.sesse.net Git - bcachefs-tools-debian/blob - libbcachefs/ec.c

   1 // SPDX-License-Identifier: GPL-2.0
   2
   3 /* erasure coding */
   4
   5 #include "bcachefs.h"
   6 #include "alloc_foreground.h"
   7 #include "backpointers.h"
   8 #include "bkey_buf.h"
   9 #include "bset.h"
  10 #include "btree_gc.h"
  11 #include "btree_update.h"
  12 #include "buckets.h"
  13 #include "disk_groups.h"
  14 #include "ec.h"
  15 #include "error.h"
  16 #include "io.h"
  17 #include "keylist.h"
  18 #include "recovery.h"
  19 #include "replicas.h"
  20 #include "super-io.h"
  21 #include "util.h"
  22
  23 #include <linux/sort.h>
  24
  25 #ifdef __KERNEL__
  26
  27 #include <linux/raid/pq.h>
  28 #include <linux/raid/xor.h>
  29
  30 static void raid5_recov(unsigned disks, unsigned failed_idx,
  31                         size_t size, void **data)
  32 {
  33         unsigned i = 2, nr;
  34
  35         BUG_ON(failed_idx >= disks);
  36
  37         swap(data[0], data[failed_idx]);
  38         memcpy(data[0], data[1], size);
  39
  40         while (i < disks) {
  41                 nr = min_t(unsigned, disks - i, MAX_XOR_BLOCKS);
  42                 xor_blocks(nr, size, data[0], data + i);
  43                 i += nr;
  44         }
  45
  46         swap(data[0], data[failed_idx]);
  47 }
  48
  49 static void raid_gen(int nd, int np, size_t size, void **v)
  50 {
  51         if (np >= 1)
  52                 raid5_recov(nd + np, nd, size, v);
  53         if (np >= 2)
  54                 raid6_call.gen_syndrome(nd + np, size, v);
  55         BUG_ON(np > 2);
  56 }
  57
  58 static void raid_rec(int nr, int *ir, int nd, int np, size_t size, void **v)
  59 {
  60         switch (nr) {
  61         case 0:
  62                 break;
  63         case 1:
  64                 if (ir[0] < nd + 1)
  65                         raid5_recov(nd + 1, ir[0], size, v);
  66                 else
  67                         raid6_call.gen_syndrome(nd + np, size, v);
  68                 break;
  69         case 2:
  70                 if (ir[1] < nd) {
  71                         /* data+data failure. */
  72                         raid6_2data_recov(nd + np, size, ir[0], ir[1], v);
  73                 } else if (ir[0] < nd) {
  74                         /* data + p/q failure */
  75
  76                         if (ir[1] == nd) /* data + p failure */
  77                                 raid6_datap_recov(nd + np, size, ir[0], v);
  78                         else { /* data + q failure */
  79                                 raid5_recov(nd + 1, ir[0], size, v);
  80                                 raid6_call.gen_syndrome(nd + np, size, v);
  81                         }
  82                 } else {
  83                         raid_gen(nd, np, size, v);
  84                 }
  85                 break;
  86         default:
  87                 BUG();
  88         }
  89 }
  90
  91 #else
  92
  93 #include <raid/raid.h>
  94
  95 #endif
  96
  97 struct ec_bio {
  98         struct bch_dev          *ca;
  99         struct ec_stripe_buf    *buf;
 100         size_t                  idx;
 101         struct bio              bio;
 102 };
 103
 104 /* Stripes btree keys: */
 105
 106 int bch2_stripe_invalid(const struct bch_fs *c, struct bkey_s_c k,
 107                         int rw, struct printbuf *err)
 108 {
 109         const struct bch_stripe *s = bkey_s_c_to_stripe(k).v;
 110
 111         if (bkey_eq(k.k->p, POS_MIN)) {
 112                 prt_printf(err, "stripe at POS_MIN");
 113                 return -BCH_ERR_invalid_bkey;
 114         }
 115
 116         if (k.k->p.inode) {
 117                 prt_printf(err, "nonzero inode field");
 118                 return -BCH_ERR_invalid_bkey;
 119         }
 120
 121         if (bkey_val_bytes(k.k) < sizeof(*s)) {
 122                 prt_printf(err, "incorrect value size (%zu < %zu)",
 123                        bkey_val_bytes(k.k), sizeof(*s));
 124                 return -BCH_ERR_invalid_bkey;
 125         }
 126
 127         if (bkey_val_u64s(k.k) < stripe_val_u64s(s)) {
 128                 prt_printf(err, "incorrect value size (%zu < %u)",
 129                        bkey_val_u64s(k.k), stripe_val_u64s(s));
 130                 return -BCH_ERR_invalid_bkey;
 131         }
 132
 133         return bch2_bkey_ptrs_invalid(c, k, rw, err);
 134 }
 135
 136 void bch2_stripe_to_text(struct printbuf *out, struct bch_fs *c,
 137                          struct bkey_s_c k)
 138 {
 139         const struct bch_stripe *s = bkey_s_c_to_stripe(k).v;
 140         unsigned i;
 141
 142         prt_printf(out, "algo %u sectors %u blocks %u:%u csum %u gran %u",
 143                s->algorithm,
 144                le16_to_cpu(s->sectors),
 145                s->nr_blocks - s->nr_redundant,
 146                s->nr_redundant,
 147                s->csum_type,
 148                1U << s->csum_granularity_bits);
 149
 150         for (i = 0; i < s->nr_blocks; i++)
 151                 prt_printf(out, " %u:%llu:%u", s->ptrs[i].dev,
 152                        (u64) s->ptrs[i].offset,
 153                        stripe_blockcount_get(s, i));
 154 }
 155
 156 /* returns blocknr in stripe that we matched: */
 157 static const struct bch_extent_ptr *bkey_matches_stripe(struct bch_stripe *s,
 158                                                 struct bkey_s_c k, unsigned *block)
 159 {
 160         struct bkey_ptrs_c ptrs = bch2_bkey_ptrs_c(k);
 161         const struct bch_extent_ptr *ptr;
 162         unsigned i, nr_data = s->nr_blocks - s->nr_redundant;
 163
 164         bkey_for_each_ptr(ptrs, ptr)
 165                 for (i = 0; i < nr_data; i++)
 166                         if (__bch2_ptr_matches_stripe(&s->ptrs[i], ptr,
 167                                                       le16_to_cpu(s->sectors))) {
 168                                 *block = i;
 169                                 return ptr;
 170                         }
 171
 172         return NULL;
 173 }
 174
 175 static bool extent_has_stripe_ptr(struct bkey_s_c k, u64 idx)
 176 {
 177         switch (k.k->type) {
 178         case KEY_TYPE_extent: {
 179                 struct bkey_s_c_extent e = bkey_s_c_to_extent(k);
 180                 const union bch_extent_entry *entry;
 181
 182                 extent_for_each_entry(e, entry)
 183                         if (extent_entry_type(entry) ==
 184                             BCH_EXTENT_ENTRY_stripe_ptr &&
 185                             entry->stripe_ptr.idx == idx)
 186                                 return true;
 187
 188                 break;
 189         }
 190         }
 191
 192         return false;
 193 }
 194
 195 /* Stripe bufs: */
 196
 197 static void ec_stripe_buf_exit(struct ec_stripe_buf *buf)
 198 {
 199         unsigned i;
 200
 201         for (i = 0; i < buf->key.v.nr_blocks; i++) {
 202                 kvpfree(buf->data[i], buf->size << 9);
 203                 buf->data[i] = NULL;
 204         }
 205 }
 206
 207 static int ec_stripe_buf_init(struct ec_stripe_buf *buf,
 208                                unsigned offset, unsigned size)
 209 {
 210         struct bch_stripe *v = &buf->key.v;
 211         unsigned csum_granularity = 1U << v->csum_granularity_bits;
 212         unsigned end = offset + size;
 213         unsigned i;
 214
 215         BUG_ON(end > le16_to_cpu(v->sectors));
 216
 217         offset  = round_down(offset, csum_granularity);
 218         end     = min_t(unsigned, le16_to_cpu(v->sectors),
 219                         round_up(end, csum_granularity));
 220
 221         buf->offset     = offset;
 222         buf->size       = end - offset;
 223
 224         memset(buf->valid, 0xFF, sizeof(buf->valid));
 225
 226         for (i = 0; i < buf->key.v.nr_blocks; i++) {
 227                 buf->data[i] = kvpmalloc(buf->size << 9, GFP_KERNEL);
 228                 if (!buf->data[i])
 229                         goto err;
 230         }
 231
 232         return 0;
 233 err:
 234         ec_stripe_buf_exit(buf);
 235         return -ENOMEM;
 236 }
 237
 238 /* Checksumming: */
 239
 240 static struct bch_csum ec_block_checksum(struct ec_stripe_buf *buf,
 241                                          unsigned block, unsigned offset)
 242 {
 243         struct bch_stripe *v = &buf->key.v;
 244         unsigned csum_granularity = 1 << v->csum_granularity_bits;
 245         unsigned end = buf->offset + buf->size;
 246         unsigned len = min(csum_granularity, end - offset);
 247
 248         BUG_ON(offset >= end);
 249         BUG_ON(offset <  buf->offset);
 250         BUG_ON(offset & (csum_granularity - 1));
 251         BUG_ON(offset + len != le16_to_cpu(v->sectors) &&
 252                (len & (csum_granularity - 1)));
 253
 254         return bch2_checksum(NULL, v->csum_type,
 255                              null_nonce(),
 256                              buf->data[block] + ((offset - buf->offset) << 9),
 257                              len << 9);
 258 }
 259
 260 static void ec_generate_checksums(struct ec_stripe_buf *buf)
 261 {
 262         struct bch_stripe *v = &buf->key.v;
 263         unsigned i, j, csums_per_device = stripe_csums_per_device(v);
 264
 265         if (!v->csum_type)
 266                 return;
 267
 268         BUG_ON(buf->offset);
 269         BUG_ON(buf->size != le16_to_cpu(v->sectors));
 270
 271         for (i = 0; i < v->nr_blocks; i++)
 272                 for (j = 0; j < csums_per_device; j++)
 273                         stripe_csum_set(v, i, j,
 274                                 ec_block_checksum(buf, i, j << v->csum_granularity_bits));
 275 }
 276
 277 static void ec_validate_checksums(struct bch_fs *c, struct ec_stripe_buf *buf)
 278 {
 279         struct bch_stripe *v = &buf->key.v;
 280         unsigned csum_granularity = 1 << v->csum_granularity_bits;
 281         unsigned i;
 282
 283         if (!v->csum_type)
 284                 return;
 285
 286         for (i = 0; i < v->nr_blocks; i++) {
 287                 unsigned offset = buf->offset;
 288                 unsigned end = buf->offset + buf->size;
 289
 290                 if (!test_bit(i, buf->valid))
 291                         continue;
 292
 293                 while (offset < end) {
 294                         unsigned j = offset >> v->csum_granularity_bits;
 295                         unsigned len = min(csum_granularity, end - offset);
 296                         struct bch_csum want = stripe_csum_get(v, i, j);
 297                         struct bch_csum got = ec_block_checksum(buf, i, offset);
 298
 299                         if (bch2_crc_cmp(want, got)) {
 300                                 struct printbuf buf2 = PRINTBUF;
 301
 302                                 bch2_bkey_val_to_text(&buf2, c, bkey_i_to_s_c(&buf->key.k_i));
 303
 304                                 bch_err_ratelimited(c,
 305                                         "stripe checksum error for %ps at %u:%u: csum type %u, expected %llx got %llx\n%s",
 306                                         (void *) _RET_IP_, i, j, v->csum_type,
 307                                         want.lo, got.lo, buf2.buf);
 308                                 printbuf_exit(&buf2);
 309                                 clear_bit(i, buf->valid);
 310                                 break;
 311                         }
 312
 313                         offset += len;
 314                 }
 315         }
 316 }
 317
 318 /* Erasure coding: */
 319
 320 static void ec_generate_ec(struct ec_stripe_buf *buf)
 321 {
 322         struct bch_stripe *v = &buf->key.v;
 323         unsigned nr_data = v->nr_blocks - v->nr_redundant;
 324         unsigned bytes = le16_to_cpu(v->sectors) << 9;
 325
 326         raid_gen(nr_data, v->nr_redundant, bytes, buf->data);
 327 }
 328
 329 static unsigned ec_nr_failed(struct ec_stripe_buf *buf)
 330 {
 331         return buf->key.v.nr_blocks -
 332                 bitmap_weight(buf->valid, buf->key.v.nr_blocks);
 333 }
 334
 335 static int ec_do_recov(struct bch_fs *c, struct ec_stripe_buf *buf)
 336 {
 337         struct bch_stripe *v = &buf->key.v;
 338         unsigned i, failed[BCH_BKEY_PTRS_MAX], nr_failed = 0;
 339         unsigned nr_data = v->nr_blocks - v->nr_redundant;
 340         unsigned bytes = buf->size << 9;
 341
 342         if (ec_nr_failed(buf) > v->nr_redundant) {
 343                 bch_err_ratelimited(c,
 344                         "error doing reconstruct read: unable to read enough blocks");
 345                 return -1;
 346         }
 347
 348         for (i = 0; i < nr_data; i++)
 349                 if (!test_bit(i, buf->valid))
 350                         failed[nr_failed++] = i;
 351
 352         raid_rec(nr_failed, failed, nr_data, v->nr_redundant, bytes, buf->data);
 353         return 0;
 354 }
 355
 356 /* IO: */
 357
 358 static void ec_block_endio(struct bio *bio)
 359 {
 360         struct ec_bio *ec_bio = container_of(bio, struct ec_bio, bio);
 361         struct bch_stripe *v = &ec_bio->buf->key.v;
 362         struct bch_extent_ptr *ptr = &v->ptrs[ec_bio->idx];
 363         struct bch_dev *ca = ec_bio->ca;
 364         struct closure *cl = bio->bi_private;
 365
 366         if (bch2_dev_io_err_on(bio->bi_status, ca, "erasure coding %s error: %s",
 367                                bio_data_dir(bio) ? "write" : "read",
 368                                bch2_blk_status_to_str(bio->bi_status)))
 369                 clear_bit(ec_bio->idx, ec_bio->buf->valid);
 370
 371         if (ptr_stale(ca, ptr)) {
 372                 bch_err_ratelimited(ca->fs,
 373                                     "error %s stripe: stale pointer after io",
 374                                     bio_data_dir(bio) == READ ? "reading from" : "writing to");
 375                 clear_bit(ec_bio->idx, ec_bio->buf->valid);
 376         }
 377
 378         bio_put(&ec_bio->bio);
 379         percpu_ref_put(&ca->io_ref);
 380         closure_put(cl);
 381 }
 382
 383 static void ec_block_io(struct bch_fs *c, struct ec_stripe_buf *buf,
 384                         unsigned rw, unsigned idx, struct closure *cl)
 385 {
 386         struct bch_stripe *v = &buf->key.v;
 387         unsigned offset = 0, bytes = buf->size << 9;
 388         struct bch_extent_ptr *ptr = &v->ptrs[idx];
 389         struct bch_dev *ca = bch_dev_bkey_exists(c, ptr->dev);
 390         enum bch_data_type data_type = idx < buf->key.v.nr_blocks - buf->key.v.nr_redundant
 391                 ? BCH_DATA_user
 392                 : BCH_DATA_parity;
 393
 394         if (ptr_stale(ca, ptr)) {
 395                 bch_err_ratelimited(c,
 396                                     "error %s stripe: stale pointer",
 397                                     rw == READ ? "reading from" : "writing to");
 398                 clear_bit(idx, buf->valid);
 399                 return;
 400         }
 401
 402         if (!bch2_dev_get_ioref(ca, rw)) {
 403                 clear_bit(idx, buf->valid);
 404                 return;
 405         }
 406
 407         this_cpu_add(ca->io_done->sectors[rw][data_type], buf->size);
 408
 409         while (offset < bytes) {
 410                 unsigned nr_iovecs = min_t(size_t, BIO_MAX_VECS,
 411                                            DIV_ROUND_UP(bytes, PAGE_SIZE));
 412                 unsigned b = min_t(size_t, bytes - offset,
 413                                    nr_iovecs << PAGE_SHIFT);
 414                 struct ec_bio *ec_bio;
 415
 416                 ec_bio = container_of(bio_alloc_bioset(ca->disk_sb.bdev,
 417                                                        nr_iovecs,
 418                                                        rw,
 419                                                        GFP_KERNEL,
 420                                                        &c->ec_bioset),
 421                                       struct ec_bio, bio);
 422
 423                 ec_bio->ca                      = ca;
 424                 ec_bio->buf                     = buf;
 425                 ec_bio->idx                     = idx;
 426
 427                 ec_bio->bio.bi_iter.bi_sector   = ptr->offset + buf->offset + (offset >> 9);
 428                 ec_bio->bio.bi_end_io           = ec_block_endio;
 429                 ec_bio->bio.bi_private          = cl;
 430
 431                 bch2_bio_map(&ec_bio->bio, buf->data[idx] + offset, b);
 432
 433                 closure_get(cl);
 434                 percpu_ref_get(&ca->io_ref);
 435
 436                 submit_bio(&ec_bio->bio);
 437
 438                 offset += b;
 439         }
 440
 441         percpu_ref_put(&ca->io_ref);
 442 }
 443
 444 static int get_stripe_key(struct bch_fs *c, u64 idx, struct ec_stripe_buf *stripe)
 445 {
 446         struct btree_trans trans;
 447         struct btree_iter iter;
 448         struct bkey_s_c k;
 449         int ret;
 450
 451         bch2_trans_init(&trans, c, 0, 0);
 452         bch2_trans_iter_init(&trans, &iter, BTREE_ID_stripes,
 453                              POS(0, idx), BTREE_ITER_SLOTS);
 454         k = bch2_btree_iter_peek_slot(&iter);
 455         ret = bkey_err(k);
 456         if (ret)
 457                 goto err;
 458         if (k.k->type != KEY_TYPE_stripe) {
 459                 ret = -ENOENT;
 460                 goto err;
 461         }
 462         bkey_reassemble(&stripe->key.k_i, k);
 463 err:
 464         bch2_trans_iter_exit(&trans, &iter);
 465         bch2_trans_exit(&trans);
 466         return ret;
 467 }
 468
 469 /* recovery read path: */
 470 int bch2_ec_read_extent(struct bch_fs *c, struct bch_read_bio *rbio)
 471 {
 472         struct ec_stripe_buf *buf;
 473         struct closure cl;
 474         struct bch_stripe *v;
 475         unsigned i, offset;
 476         int ret = 0;
 477
 478         closure_init_stack(&cl);
 479
 480         BUG_ON(!rbio->pick.has_ec);
 481
 482         buf = kzalloc(sizeof(*buf), GFP_NOIO);
 483         if (!buf)
 484                 return -ENOMEM;
 485
 486         ret = get_stripe_key(c, rbio->pick.ec.idx, buf);
 487         if (ret) {
 488                 bch_err_ratelimited(c,
 489                         "error doing reconstruct read: error %i looking up stripe", ret);
 490                 kfree(buf);
 491                 return -EIO;
 492         }
 493
 494         v = &buf->key.v;
 495
 496         if (!bch2_ptr_matches_stripe(v, rbio->pick)) {
 497                 bch_err_ratelimited(c,
 498                         "error doing reconstruct read: pointer doesn't match stripe");
 499                 ret = -EIO;
 500                 goto err;
 501         }
 502
 503         offset = rbio->bio.bi_iter.bi_sector - v->ptrs[rbio->pick.ec.block].offset;
 504         if (offset + bio_sectors(&rbio->bio) > le16_to_cpu(v->sectors)) {
 505                 bch_err_ratelimited(c,
 506                         "error doing reconstruct read: read is bigger than stripe");
 507                 ret = -EIO;
 508                 goto err;
 509         }
 510
 511         ret = ec_stripe_buf_init(buf, offset, bio_sectors(&rbio->bio));
 512         if (ret)
 513                 goto err;
 514
 515         for (i = 0; i < v->nr_blocks; i++)
 516                 ec_block_io(c, buf, REQ_OP_READ, i, &cl);
 517
 518         closure_sync(&cl);
 519
 520         if (ec_nr_failed(buf) > v->nr_redundant) {
 521                 bch_err_ratelimited(c,
 522                         "error doing reconstruct read: unable to read enough blocks");
 523                 ret = -EIO;
 524                 goto err;
 525         }
 526
 527         ec_validate_checksums(c, buf);
 528
 529         ret = ec_do_recov(c, buf);
 530         if (ret)
 531                 goto err;
 532
 533         memcpy_to_bio(&rbio->bio, rbio->bio.bi_iter,
 534                       buf->data[rbio->pick.ec.block] + ((offset - buf->offset) << 9));
 535 err:
 536         ec_stripe_buf_exit(buf);
 537         kfree(buf);
 538         return ret;
 539 }
 540
 541 /* stripe bucket accounting: */
 542
 543 static int __ec_stripe_mem_alloc(struct bch_fs *c, size_t idx, gfp_t gfp)
 544 {
 545         ec_stripes_heap n, *h = &c->ec_stripes_heap;
 546
 547         if (idx >= h->size) {
 548                 if (!init_heap(&n, max(1024UL, roundup_pow_of_two(idx + 1)), gfp))
 549                         return -ENOMEM;
 550
 551                 spin_lock(&c->ec_stripes_heap_lock);
 552                 if (n.size > h->size) {
 553                         memcpy(n.data, h->data, h->used * sizeof(h->data[0]));
 554                         n.used = h->used;
 555                         swap(*h, n);
 556                 }
 557                 spin_unlock(&c->ec_stripes_heap_lock);
 558
 559                 free_heap(&n);
 560         }
 561
 562         if (!genradix_ptr_alloc(&c->stripes, idx, gfp))
 563                 return -ENOMEM;
 564
 565         if (c->gc_pos.phase != GC_PHASE_NOT_RUNNING &&
 566             !genradix_ptr_alloc(&c->gc_stripes, idx, gfp))
 567                 return -ENOMEM;
 568
 569         return 0;
 570 }
 571
 572 static int ec_stripe_mem_alloc(struct btree_trans *trans,
 573                                struct btree_iter *iter)
 574 {
 575         size_t idx = iter->pos.offset;
 576
 577         if (!__ec_stripe_mem_alloc(trans->c, idx, GFP_NOWAIT|__GFP_NOWARN))
 578                 return 0;
 579
 580         bch2_trans_unlock(trans);
 581
 582         return   __ec_stripe_mem_alloc(trans->c, idx, GFP_KERNEL) ?:
 583                 bch2_trans_relock(trans);
 584 }
 585
 586 static ssize_t stripe_idx_to_delete(struct bch_fs *c)
 587 {
 588         ec_stripes_heap *h = &c->ec_stripes_heap;
 589
 590         return h->used && h->data[0].blocks_nonempty == 0
 591                 ? h->data[0].idx : -1;
 592 }
 593
 594 static inline int ec_stripes_heap_cmp(ec_stripes_heap *h,
 595                                       struct ec_stripe_heap_entry l,
 596                                       struct ec_stripe_heap_entry r)
 597 {
 598         return ((l.blocks_nonempty > r.blocks_nonempty) -
 599                 (l.blocks_nonempty < r.blocks_nonempty));
 600 }
 601
 602 static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h,
 603                                                    size_t i)
 604 {
 605         struct bch_fs *c = container_of(h, struct bch_fs, ec_stripes_heap);
 606
 607         genradix_ptr(&c->stripes, h->data[i].idx)->heap_idx = i;
 608 }
 609
 610 static void heap_verify_backpointer(struct bch_fs *c, size_t idx)
 611 {
 612         ec_stripes_heap *h = &c->ec_stripes_heap;
 613         struct stripe *m = genradix_ptr(&c->stripes, idx);
 614
 615         BUG_ON(!m->alive);
 616         BUG_ON(m->heap_idx >= h->used);
 617         BUG_ON(h->data[m->heap_idx].idx != idx);
 618 }
 619
 620 void bch2_stripes_heap_del(struct bch_fs *c,
 621                            struct stripe *m, size_t idx)
 622 {
 623         if (!m->on_heap)
 624                 return;
 625
 626         m->on_heap = false;
 627
 628         heap_verify_backpointer(c, idx);
 629
 630         heap_del(&c->ec_stripes_heap, m->heap_idx,
 631                  ec_stripes_heap_cmp,
 632                  ec_stripes_heap_set_backpointer);
 633 }
 634
 635 void bch2_stripes_heap_insert(struct bch_fs *c,
 636                               struct stripe *m, size_t idx)
 637 {
 638         if (m->on_heap)
 639                 return;
 640
 641         BUG_ON(heap_full(&c->ec_stripes_heap));
 642
 643         m->on_heap = true;
 644
 645         heap_add(&c->ec_stripes_heap, ((struct ec_stripe_heap_entry) {
 646                         .idx = idx,
 647                         .blocks_nonempty = m->blocks_nonempty,
 648                 }),
 649                  ec_stripes_heap_cmp,
 650                  ec_stripes_heap_set_backpointer);
 651
 652         heap_verify_backpointer(c, idx);
 653 }
 654
 655 void bch2_stripes_heap_update(struct bch_fs *c,
 656                               struct stripe *m, size_t idx)
 657 {
 658         ec_stripes_heap *h = &c->ec_stripes_heap;
 659         size_t i;
 660
 661         if (!m->on_heap)
 662                 return;
 663
 664         heap_verify_backpointer(c, idx);
 665
 666         h->data[m->heap_idx].blocks_nonempty = m->blocks_nonempty;
 667
 668         i = m->heap_idx;
 669         heap_sift_up(h,   i, ec_stripes_heap_cmp,
 670                      ec_stripes_heap_set_backpointer);
 671         heap_sift_down(h, i, ec_stripes_heap_cmp,
 672                        ec_stripes_heap_set_backpointer);
 673
 674         heap_verify_backpointer(c, idx);
 675
 676         if (stripe_idx_to_delete(c) >= 0 &&
 677             !percpu_ref_is_dying(&c->writes))
 678                 schedule_work(&c->ec_stripe_delete_work);
 679 }
 680
 681 /* stripe deletion */
 682
 683 static int ec_stripe_delete(struct bch_fs *c, size_t idx)
 684 {
 685         return bch2_btree_delete_range(c, BTREE_ID_stripes,
 686                                        POS(0, idx),
 687                                        POS(0, idx),
 688                                        0, NULL);
 689 }
 690
 691 static void ec_stripe_delete_work(struct work_struct *work)
 692 {
 693         struct bch_fs *c =
 694                 container_of(work, struct bch_fs, ec_stripe_delete_work);
 695         ssize_t idx;
 696
 697         while (1) {
 698                 spin_lock(&c->ec_stripes_heap_lock);
 699                 idx = stripe_idx_to_delete(c);
 700                 if (idx < 0) {
 701                         spin_unlock(&c->ec_stripes_heap_lock);
 702                         break;
 703                 }
 704
 705                 bch2_stripes_heap_del(c, genradix_ptr(&c->stripes, idx), idx);
 706                 spin_unlock(&c->ec_stripes_heap_lock);
 707
 708                 if (ec_stripe_delete(c, idx))
 709                         break;
 710         }
 711 }
 712
 713 /* stripe creation: */
 714
 715 static int ec_stripe_bkey_insert(struct btree_trans *trans,
 716                                  struct bkey_i_stripe *stripe,
 717                                  struct disk_reservation *res)
 718 {
 719         struct bch_fs *c = trans->c;
 720         struct btree_iter iter;
 721         struct bkey_s_c k;
 722         struct bpos min_pos = POS(0, 1);
 723         struct bpos start_pos = bpos_max(min_pos, POS(0, c->ec_stripe_hint));
 724         int ret;
 725
 726         for_each_btree_key_norestart(trans, iter, BTREE_ID_stripes, start_pos,
 727                            BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) {
 728                 if (bkey_gt(k.k->p, POS(0, U32_MAX))) {
 729                         if (start_pos.offset) {
 730                                 start_pos = min_pos;
 731                                 bch2_btree_iter_set_pos(&iter, start_pos);
 732                                 continue;
 733                         }
 734
 735                         ret = -BCH_ERR_ENOSPC_stripe_create;
 736                         break;
 737                 }
 738
 739                 if (bkey_deleted(k.k))
 740                         break;
 741         }
 742
 743         c->ec_stripe_hint = iter.pos.offset;
 744
 745         if (ret)
 746                 goto err;
 747
 748         ret = ec_stripe_mem_alloc(trans, &iter);
 749         if (ret)
 750                 goto err;
 751
 752         stripe->k.p = iter.pos;
 753
 754         ret = bch2_trans_update(trans, &iter, &stripe->k_i, 0);
 755 err:
 756         bch2_trans_iter_exit(trans, &iter);
 757
 758         return ret;
 759 }
 760
 761 static int ec_stripe_bkey_update(struct btree_trans *trans,
 762                                  struct bkey_i_stripe *new,
 763                                  struct disk_reservation *res)
 764 {
 765         struct btree_iter iter;
 766         struct bkey_s_c k;
 767         const struct bch_stripe *existing;
 768         unsigned i;
 769         int ret;
 770
 771         bch2_trans_iter_init(trans, &iter, BTREE_ID_stripes,
 772                              new->k.p, BTREE_ITER_INTENT);
 773         k = bch2_btree_iter_peek_slot(&iter);
 774         ret = bkey_err(k);
 775         if (ret)
 776                 goto err;
 777
 778         if (!k.k || k.k->type != KEY_TYPE_stripe) {
 779                 bch_err(trans->c, "error updating stripe: not found");
 780                 ret = -ENOENT;
 781                 goto err;
 782         }
 783
 784         existing = bkey_s_c_to_stripe(k).v;
 785
 786         if (existing->nr_blocks != new->v.nr_blocks) {
 787                 bch_err(trans->c, "error updating stripe: nr_blocks does not match");
 788                 ret = -EINVAL;
 789                 goto err;
 790         }
 791
 792         for (i = 0; i < new->v.nr_blocks; i++)
 793                 stripe_blockcount_set(&new->v, i,
 794                         stripe_blockcount_get(existing, i));
 795
 796         ret = bch2_trans_update(trans, &iter, &new->k_i, 0);
 797 err:
 798         bch2_trans_iter_exit(trans, &iter);
 799         return ret;
 800 }
 801
 802 static void extent_stripe_ptr_add(struct bkey_s_extent e,
 803                                   struct ec_stripe_buf *s,
 804                                   struct bch_extent_ptr *ptr,
 805                                   unsigned block)
 806 {
 807         struct bch_extent_stripe_ptr *dst = (void *) ptr;
 808         union bch_extent_entry *end = extent_entry_last(e);
 809
 810         memmove_u64s_up(dst + 1, dst, (u64 *) end - (u64 *) dst);
 811         e.k->u64s += sizeof(*dst) / sizeof(u64);
 812
 813         *dst = (struct bch_extent_stripe_ptr) {
 814                 .type = 1 << BCH_EXTENT_ENTRY_stripe_ptr,
 815                 .block          = block,
 816                 .redundancy     = s->key.v.nr_redundant,
 817                 .idx            = s->key.k.p.offset,
 818         };
 819 }
 820
 821 static int ec_stripe_update_extent(struct btree_trans *trans,
 822                                    struct btree_iter *iter,
 823                                    struct bkey_s_c k,
 824                                    struct ec_stripe_buf *s)
 825 {
 826         const struct bch_extent_ptr *ptr_c;
 827         struct bch_extent_ptr *ptr, *ec_ptr = NULL;
 828         struct bkey_i *n;
 829         int ret, dev, block;
 830
 831         if (extent_has_stripe_ptr(k, s->key.k.p.offset))
 832                 return 0;
 833
 834         ptr_c = bkey_matches_stripe(&s->key.v, k, &block);
 835         /*
 836          * It doesn't generally make sense to erasure code cached ptrs:
 837          * XXX: should we be incrementing a counter?
 838          */
 839         if (!ptr_c || ptr_c->cached)
 840                 return 0;
 841
 842         dev = s->key.v.ptrs[block].dev;
 843
 844         n = bch2_bkey_make_mut(trans, k);
 845         ret = PTR_ERR_OR_ZERO(n);
 846         if (ret)
 847                 return ret;
 848
 849         bch2_bkey_drop_ptrs(bkey_i_to_s(n), ptr, ptr->dev != dev);
 850         ec_ptr = (void *) bch2_bkey_has_device(bkey_i_to_s_c(n), dev);
 851         BUG_ON(!ec_ptr);
 852
 853         extent_stripe_ptr_add(bkey_i_to_s_extent(n), s, ec_ptr, block);
 854
 855         return bch2_trans_update(trans, iter, n, 0);
 856 }
 857
 858 static int ec_stripe_update_bucket(struct btree_trans *trans, struct ec_stripe_buf *s,
 859                                    unsigned block)
 860 {
 861         struct bch_fs *c = trans->c;
 862         struct bch_extent_ptr bucket = s->key.v.ptrs[block];
 863         struct bpos bucket_pos = PTR_BUCKET_POS(c, &bucket);
 864         struct bch_backpointer bp;
 865         struct btree_iter iter;
 866         struct bkey_s_c k;
 867         u64 bp_offset = 0;
 868         int ret = 0;
 869 retry:
 870         while (1) {
 871                 bch2_trans_begin(trans);
 872
 873                 ret = bch2_get_next_backpointer(trans, bucket_pos, bucket.gen,
 874                                                 &bp_offset, &bp,
 875                                                 BTREE_ITER_CACHED);
 876                 if (ret)
 877                         break;
 878                 if (bp_offset == U64_MAX)
 879                         break;
 880
 881                 if (bch2_fs_inconsistent_on(bp.level, c, "found btree node in erasure coded bucket!?")) {
 882                         ret = -EIO;
 883                         break;
 884                 }
 885
 886                 k = bch2_backpointer_get_key(trans, &iter, bucket_pos, bp_offset, bp);
 887                 ret = bkey_err(k);
 888                 if (ret)
 889                         break;
 890                 if (!k.k)
 891                         continue;
 892
 893                 ret = ec_stripe_update_extent(trans, &iter, k, s);
 894                 bch2_trans_iter_exit(trans, &iter);
 895                 if (ret)
 896                         break;
 897
 898                 bp_offset++;
 899         }
 900
 901         if (bch2_err_matches(ret, BCH_ERR_transaction_restart))
 902                 goto retry;
 903
 904         return ret;
 905 }
 906
 907 static int ec_stripe_update_extents(struct bch_fs *c, struct ec_stripe_buf *s)
 908 {
 909         struct btree_trans trans;
 910         struct bch_stripe *v = &s->key.v;
 911         unsigned i, nr_data = v->nr_blocks - v->nr_redundant;
 912         int ret = 0;
 913
 914         bch2_trans_init(&trans, c, 0, 0);
 915
 916         for (i = 0; i < nr_data; i++) {
 917                 ret = ec_stripe_update_bucket(&trans, s, i);
 918                 if (ret)
 919                         break;
 920         }
 921
 922
 923         bch2_trans_exit(&trans);
 924
 925         return ret;
 926 }
 927
 928 /*
 929  * data buckets of new stripe all written: create the stripe
 930  */
 931 static void ec_stripe_create(struct ec_stripe_new *s)
 932 {
 933         struct bch_fs *c = s->c;
 934         struct open_bucket *ob;
 935         struct stripe *m;
 936         struct bch_stripe *v = &s->new_stripe.key.v;
 937         unsigned i, nr_data = v->nr_blocks - v->nr_redundant;
 938         int ret;
 939
 940         BUG_ON(s->h->s == s);
 941
 942         closure_sync(&s->iodone);
 943
 944         if (s->err) {
 945                 if (s->err != -EROFS)
 946                         bch_err(c, "error creating stripe: error writing data buckets");
 947                 goto err;
 948         }
 949
 950         if (s->have_existing_stripe) {
 951                 ec_validate_checksums(c, &s->existing_stripe);
 952
 953                 if (ec_do_recov(c, &s->existing_stripe)) {
 954                         bch_err(c, "error creating stripe: error reading existing stripe");
 955                         goto err;
 956                 }
 957
 958                 for (i = 0; i < nr_data; i++)
 959                         if (stripe_blockcount_get(&s->existing_stripe.key.v, i))
 960                                 swap(s->new_stripe.data[i],
 961                                      s->existing_stripe.data[i]);
 962
 963                 ec_stripe_buf_exit(&s->existing_stripe);
 964         }
 965
 966         BUG_ON(!s->allocated);
 967
 968         if (!percpu_ref_tryget_live(&c->writes))
 969                 goto err;
 970
 971         ec_generate_ec(&s->new_stripe);
 972
 973         ec_generate_checksums(&s->new_stripe);
 974
 975         /* write p/q: */
 976         for (i = nr_data; i < v->nr_blocks; i++)
 977                 ec_block_io(c, &s->new_stripe, REQ_OP_WRITE, i, &s->iodone);
 978         closure_sync(&s->iodone);
 979
 980         if (ec_nr_failed(&s->new_stripe)) {
 981                 bch_err(c, "error creating stripe: error writing redundancy buckets");
 982                 goto err_put_writes;
 983         }
 984
 985         ret = bch2_trans_do(c, &s->res, NULL, BTREE_INSERT_NOFAIL,
 986                             s->have_existing_stripe
 987                             ? ec_stripe_bkey_update(&trans, &s->new_stripe.key, &s->res)
 988                             : ec_stripe_bkey_insert(&trans, &s->new_stripe.key, &s->res));
 989         if (ret) {
 990                 bch_err(c, "error creating stripe: error creating stripe key");
 991                 goto err_put_writes;
 992         }
 993
 994         ret = ec_stripe_update_extents(c, &s->new_stripe);
 995         if (ret)
 996                 bch_err(c, "error creating stripe: error updating pointers: %s",
 997                         bch2_err_str(ret));
 998
 999         spin_lock(&c->ec_stripes_heap_lock);
1000         m = genradix_ptr(&c->stripes, s->new_stripe.key.k.p.offset);
1001
1002         BUG_ON(m->on_heap);
1003         bch2_stripes_heap_insert(c, m, s->new_stripe.key.k.p.offset);
1004         spin_unlock(&c->ec_stripes_heap_lock);
1005 err_put_writes:
1006         percpu_ref_put(&c->writes);
1007 err:
1008         bch2_disk_reservation_put(c, &s->res);
1009
1010         for (i = 0; i < v->nr_blocks; i++)
1011                 if (s->blocks[i]) {
1012                         ob = c->open_buckets + s->blocks[i];
1013
1014                         if (i < nr_data) {
1015                                 ob->ec = NULL;
1016                                 __bch2_open_bucket_put(c, ob);
1017                         } else {
1018                                 bch2_open_bucket_put(c, ob);
1019                         }
1020                 }
1021
1022         ec_stripe_buf_exit(&s->existing_stripe);
1023         ec_stripe_buf_exit(&s->new_stripe);
1024         closure_debug_destroy(&s->iodone);
1025         kfree(s);
1026 }
1027
1028 static void ec_stripe_create_work(struct work_struct *work)
1029 {
1030         struct bch_fs *c = container_of(work,
1031                 struct bch_fs, ec_stripe_create_work);
1032         struct ec_stripe_new *s, *n;
1033 restart:
1034         mutex_lock(&c->ec_stripe_new_lock);
1035         list_for_each_entry_safe(s, n, &c->ec_stripe_new_list, list)
1036                 if (!atomic_read(&s->pin)) {
1037                         list_del(&s->list);
1038                         mutex_unlock(&c->ec_stripe_new_lock);
1039                         ec_stripe_create(s);
1040                         goto restart;
1041                 }
1042         mutex_unlock(&c->ec_stripe_new_lock);
1043 }
1044
1045 static void ec_stripe_new_put(struct bch_fs *c, struct ec_stripe_new *s)
1046 {
1047         BUG_ON(atomic_read(&s->pin) <= 0);
1048
1049         if (atomic_dec_and_test(&s->pin)) {
1050                 BUG_ON(!s->pending);
1051                 queue_work(system_long_wq, &c->ec_stripe_create_work);
1052         }
1053 }
1054
1055 static void ec_stripe_set_pending(struct bch_fs *c, struct ec_stripe_head *h)
1056 {
1057         struct ec_stripe_new *s = h->s;
1058
1059         BUG_ON(!s->allocated && !s->err);
1060
1061         h->s            = NULL;
1062         s->pending      = true;
1063
1064         mutex_lock(&c->ec_stripe_new_lock);
1065         list_add(&s->list, &c->ec_stripe_new_list);
1066         mutex_unlock(&c->ec_stripe_new_lock);
1067
1068         ec_stripe_new_put(c, s);
1069 }
1070
1071 /* have a full bucket - hand it off to be erasure coded: */
1072 void bch2_ec_bucket_written(struct bch_fs *c, struct open_bucket *ob)
1073 {
1074         struct ec_stripe_new *s = ob->ec;
1075
1076         if (ob->sectors_free)
1077                 s->err = -1;
1078
1079         ec_stripe_new_put(c, s);
1080 }
1081
1082 void bch2_ec_bucket_cancel(struct bch_fs *c, struct open_bucket *ob)
1083 {
1084         struct ec_stripe_new *s = ob->ec;
1085
1086         s->err = -EIO;
1087 }
1088
1089 void *bch2_writepoint_ec_buf(struct bch_fs *c, struct write_point *wp)
1090 {
1091         struct open_bucket *ob = ec_open_bucket(c, &wp->ptrs);
1092         struct bch_dev *ca;
1093         unsigned offset;
1094
1095         if (!ob)
1096                 return NULL;
1097
1098         ca      = bch_dev_bkey_exists(c, ob->dev);
1099         offset  = ca->mi.bucket_size - ob->sectors_free;
1100
1101         return ob->ec->new_stripe.data[ob->ec_idx] + (offset << 9);
1102 }
1103
1104 static int unsigned_cmp(const void *_l, const void *_r)
1105 {
1106         unsigned l = *((const unsigned *) _l);
1107         unsigned r = *((const unsigned *) _r);
1108
1109         return cmp_int(l, r);
1110 }
1111
1112 /* pick most common bucket size: */
1113 static unsigned pick_blocksize(struct bch_fs *c,
1114                                struct bch_devs_mask *devs)
1115 {
1116         struct bch_dev *ca;
1117         unsigned i, nr = 0, sizes[BCH_SB_MEMBERS_MAX];
1118         struct {
1119                 unsigned nr, size;
1120         } cur = { 0, 0 }, best = { 0, 0 };
1121
1122         for_each_member_device_rcu(ca, c, i, devs)
1123                 sizes[nr++] = ca->mi.bucket_size;
1124
1125         sort(sizes, nr, sizeof(unsigned), unsigned_cmp, NULL);
1126
1127         for (i = 0; i < nr; i++) {
1128                 if (sizes[i] != cur.size) {
1129                         if (cur.nr > best.nr)
1130                                 best = cur;
1131
1132                         cur.nr = 0;
1133                         cur.size = sizes[i];
1134                 }
1135
1136                 cur.nr++;
1137         }
1138
1139         if (cur.nr > best.nr)
1140                 best = cur;
1141
1142         return best.size;
1143 }
1144
1145 static bool may_create_new_stripe(struct bch_fs *c)
1146 {
1147         return false;
1148 }
1149
1150 static void ec_stripe_key_init(struct bch_fs *c,
1151                                struct bkey_i_stripe *s,
1152                                unsigned nr_data,
1153                                unsigned nr_parity,
1154                                unsigned stripe_size)
1155 {
1156         unsigned u64s;
1157
1158         bkey_stripe_init(&s->k_i);
1159         s->v.sectors                    = cpu_to_le16(stripe_size);
1160         s->v.algorithm                  = 0;
1161         s->v.nr_blocks                  = nr_data + nr_parity;
1162         s->v.nr_redundant               = nr_parity;
1163         s->v.csum_granularity_bits      = ilog2(c->opts.encoded_extent_max >> 9);
1164         s->v.csum_type                  = BCH_CSUM_crc32c;
1165         s->v.pad                        = 0;
1166
1167         while ((u64s = stripe_val_u64s(&s->v)) > BKEY_VAL_U64s_MAX) {
1168                 BUG_ON(1 << s->v.csum_granularity_bits >=
1169                        le16_to_cpu(s->v.sectors) ||
1170                        s->v.csum_granularity_bits == U8_MAX);
1171                 s->v.csum_granularity_bits++;
1172         }
1173
1174         set_bkey_val_u64s(&s->k, u64s);
1175 }
1176
1177 static int ec_new_stripe_alloc(struct bch_fs *c, struct ec_stripe_head *h)
1178 {
1179         struct ec_stripe_new *s;
1180
1181         lockdep_assert_held(&h->lock);
1182
1183         s = kzalloc(sizeof(*s), GFP_KERNEL);
1184         if (!s)
1185                 return -ENOMEM;
1186
1187         mutex_init(&s->lock);
1188         closure_init(&s->iodone, NULL);
1189         atomic_set(&s->pin, 1);
1190         s->c            = c;
1191         s->h            = h;
1192         s->nr_data      = min_t(unsigned, h->nr_active_devs,
1193                                 BCH_BKEY_PTRS_MAX) - h->redundancy;
1194         s->nr_parity    = h->redundancy;
1195
1196         ec_stripe_key_init(c, &s->new_stripe.key, s->nr_data,
1197                            s->nr_parity, h->blocksize);
1198
1199         h->s = s;
1200         return 0;
1201 }
1202
1203 static struct ec_stripe_head *
1204 ec_new_stripe_head_alloc(struct bch_fs *c, unsigned target,
1205                          unsigned algo, unsigned redundancy,
1206                          bool copygc)
1207 {
1208         struct ec_stripe_head *h;
1209         struct bch_dev *ca;
1210         unsigned i;
1211
1212         h = kzalloc(sizeof(*h), GFP_KERNEL);
1213         if (!h)
1214                 return NULL;
1215
1216         mutex_init(&h->lock);
1217         mutex_lock(&h->lock);
1218
1219         h->target       = target;
1220         h->algo         = algo;
1221         h->redundancy   = redundancy;
1222         h->copygc       = copygc;
1223
1224         rcu_read_lock();
1225         h->devs = target_rw_devs(c, BCH_DATA_user, target);
1226
1227         for_each_member_device_rcu(ca, c, i, &h->devs)
1228                 if (!ca->mi.durability)
1229                         __clear_bit(i, h->devs.d);
1230
1231         h->blocksize = pick_blocksize(c, &h->devs);
1232
1233         for_each_member_device_rcu(ca, c, i, &h->devs)
1234                 if (ca->mi.bucket_size == h->blocksize)
1235                         h->nr_active_devs++;
1236
1237         rcu_read_unlock();
1238         list_add(&h->list, &c->ec_stripe_head_list);
1239         return h;
1240 }
1241
1242 void bch2_ec_stripe_head_put(struct bch_fs *c, struct ec_stripe_head *h)
1243 {
1244         if (h->s &&
1245             h->s->allocated &&
1246             bitmap_weight(h->s->blocks_allocated,
1247                           h->s->nr_data) == h->s->nr_data)
1248                 ec_stripe_set_pending(c, h);
1249
1250         mutex_unlock(&h->lock);
1251 }
1252
1253 struct ec_stripe_head *__bch2_ec_stripe_head_get(struct bch_fs *c,
1254                                                  unsigned target,
1255                                                  unsigned algo,
1256                                                  unsigned redundancy,
1257                                                  bool copygc)
1258 {
1259         struct ec_stripe_head *h;
1260
1261         if (!redundancy)
1262                 return NULL;
1263
1264         mutex_lock(&c->ec_stripe_head_lock);
1265         list_for_each_entry(h, &c->ec_stripe_head_list, list)
1266                 if (h->target           == target &&
1267                     h->algo             == algo &&
1268                     h->redundancy       == redundancy &&
1269                     h->copygc           == copygc) {
1270                         mutex_lock(&h->lock);
1271                         goto found;
1272                 }
1273
1274         h = ec_new_stripe_head_alloc(c, target, algo, redundancy, copygc);
1275 found:
1276         mutex_unlock(&c->ec_stripe_head_lock);
1277         return h;
1278 }
1279
1280 static int new_stripe_alloc_buckets(struct bch_fs *c, struct ec_stripe_head *h,
1281                                     struct closure *cl)
1282 {
1283         struct bch_devs_mask devs = h->devs;
1284         struct open_bucket *ob;
1285         struct open_buckets buckets;
1286         unsigned i, j, nr_have_parity = 0, nr_have_data = 0;
1287         bool have_cache = true;
1288         int ret = 0;
1289
1290         for (i = 0; i < h->s->new_stripe.key.v.nr_blocks; i++) {
1291                 if (test_bit(i, h->s->blocks_gotten)) {
1292                         __clear_bit(h->s->new_stripe.key.v.ptrs[i].dev, devs.d);
1293                         if (i < h->s->nr_data)
1294                                 nr_have_data++;
1295                         else
1296                                 nr_have_parity++;
1297                 }
1298         }
1299
1300         BUG_ON(nr_have_data     > h->s->nr_data);
1301         BUG_ON(nr_have_parity   > h->s->nr_parity);
1302
1303         buckets.nr = 0;
1304         if (nr_have_parity < h->s->nr_parity) {
1305                 ret = bch2_bucket_alloc_set(c, &buckets,
1306                                             &h->parity_stripe,
1307                                             &devs,
1308                                             h->s->nr_parity,
1309                                             &nr_have_parity,
1310                                             &have_cache,
1311                                             h->copygc
1312                                             ? RESERVE_movinggc
1313                                             : RESERVE_none,
1314                                             0,
1315                                             cl);
1316
1317                 open_bucket_for_each(c, &buckets, ob, i) {
1318                         j = find_next_zero_bit(h->s->blocks_gotten,
1319                                                h->s->nr_data + h->s->nr_parity,
1320                                                h->s->nr_data);
1321                         BUG_ON(j >= h->s->nr_data + h->s->nr_parity);
1322
1323                         h->s->blocks[j] = buckets.v[i];
1324                         h->s->new_stripe.key.v.ptrs[j] = bch2_ob_ptr(c, ob);
1325                         __set_bit(j, h->s->blocks_gotten);
1326                 }
1327
1328                 if (ret)
1329                         return ret;
1330         }
1331
1332         buckets.nr = 0;
1333         if (nr_have_data < h->s->nr_data) {
1334                 ret = bch2_bucket_alloc_set(c, &buckets,
1335                                             &h->block_stripe,
1336                                             &devs,
1337                                             h->s->nr_data,
1338                                             &nr_have_data,
1339                                             &have_cache,
1340                                             h->copygc
1341                                             ? RESERVE_movinggc
1342                                             : RESERVE_none,
1343                                             0,
1344                                             cl);
1345
1346                 open_bucket_for_each(c, &buckets, ob, i) {
1347                         j = find_next_zero_bit(h->s->blocks_gotten,
1348                                                h->s->nr_data, 0);
1349                         BUG_ON(j >= h->s->nr_data);
1350
1351                         h->s->blocks[j] = buckets.v[i];
1352                         h->s->new_stripe.key.v.ptrs[j] = bch2_ob_ptr(c, ob);
1353                         __set_bit(j, h->s->blocks_gotten);
1354                 }
1355
1356                 if (ret)
1357                         return ret;
1358         }
1359
1360         return 0;
1361 }
1362
1363 /* XXX: doesn't obey target: */
1364 static s64 get_existing_stripe(struct bch_fs *c,
1365                                struct ec_stripe_head *head)
1366 {
1367         ec_stripes_heap *h = &c->ec_stripes_heap;
1368         struct stripe *m;
1369         size_t heap_idx;
1370         u64 stripe_idx;
1371         s64 ret = -1;
1372
1373         if (may_create_new_stripe(c))
1374                 return -1;
1375
1376         spin_lock(&c->ec_stripes_heap_lock);
1377         for (heap_idx = 0; heap_idx < h->used; heap_idx++) {
1378                 /* No blocks worth reusing, stripe will just be deleted: */
1379                 if (!h->data[heap_idx].blocks_nonempty)
1380                         continue;
1381
1382                 stripe_idx = h->data[heap_idx].idx;
1383                 m = genradix_ptr(&c->stripes, stripe_idx);
1384
1385                 if (m->algorithm        == head->algo &&
1386                     m->nr_redundant     == head->redundancy &&
1387                     m->sectors          == head->blocksize &&
1388                     m->blocks_nonempty  < m->nr_blocks - m->nr_redundant) {
1389                         bch2_stripes_heap_del(c, m, stripe_idx);
1390                         ret = stripe_idx;
1391                         break;
1392                 }
1393         }
1394         spin_unlock(&c->ec_stripes_heap_lock);
1395         return ret;
1396 }
1397
1398 static int __bch2_ec_stripe_head_reuse(struct bch_fs *c,
1399                                                    struct ec_stripe_head *h)
1400 {
1401         unsigned i;
1402         s64 idx;
1403         int ret;
1404
1405         idx = get_existing_stripe(c, h);
1406         if (idx < 0)
1407                 return -BCH_ERR_ENOSPC_stripe_reuse;
1408
1409         h->s->have_existing_stripe = true;
1410         ret = get_stripe_key(c, idx, &h->s->existing_stripe);
1411         if (ret) {
1412                 bch2_fs_fatal_error(c, "error reading stripe key: %i", ret);
1413                 return ret;
1414         }
1415
1416         if (ec_stripe_buf_init(&h->s->existing_stripe, 0, h->blocksize)) {
1417                 /*
1418                  * this is a problem: we have deleted from the
1419                  * stripes heap already
1420                  */
1421                 BUG();
1422         }
1423
1424         BUG_ON(h->s->existing_stripe.size != h->blocksize);
1425         BUG_ON(h->s->existing_stripe.size != h->s->existing_stripe.key.v.sectors);
1426
1427         for (i = 0; i < h->s->existing_stripe.key.v.nr_blocks; i++) {
1428                 if (stripe_blockcount_get(&h->s->existing_stripe.key.v, i)) {
1429                         __set_bit(i, h->s->blocks_gotten);
1430                         __set_bit(i, h->s->blocks_allocated);
1431                 }
1432
1433                 ec_block_io(c, &h->s->existing_stripe, READ, i, &h->s->iodone);
1434         }
1435
1436         bkey_copy(&h->s->new_stripe.key.k_i,
1437                         &h->s->existing_stripe.key.k_i);
1438
1439         return 0;
1440 }
1441
1442 static int __bch2_ec_stripe_head_reserve(struct bch_fs *c,
1443                                                         struct ec_stripe_head *h)
1444 {
1445         return bch2_disk_reservation_get(c, &h->s->res,
1446                                          h->blocksize,
1447                                          h->s->nr_parity, 0);
1448 }
1449
1450 struct ec_stripe_head *bch2_ec_stripe_head_get(struct bch_fs *c,
1451                                                unsigned target,
1452                                                unsigned algo,
1453                                                unsigned redundancy,
1454                                                bool copygc,
1455                                                struct closure *cl)
1456 {
1457         struct ec_stripe_head *h;
1458         int ret;
1459         bool needs_stripe_new;
1460
1461         h = __bch2_ec_stripe_head_get(c, target, algo, redundancy, copygc);
1462         if (!h) {
1463                 bch_err(c, "no stripe head");
1464                 return NULL;
1465         }
1466
1467         needs_stripe_new = !h->s;
1468         if (needs_stripe_new) {
1469                 if (ec_new_stripe_alloc(c, h)) {
1470                         ret = -ENOMEM;
1471                         bch_err(c, "failed to allocate new stripe");
1472                         goto err;
1473                 }
1474
1475                 if (ec_stripe_buf_init(&h->s->new_stripe, 0, h->blocksize))
1476                         BUG();
1477         }
1478
1479         /*
1480          * Try reserve a new stripe before reusing an
1481          * existing stripe. This will prevent unnecessary
1482          * read amplification during write oriented workloads.
1483          */
1484         ret = 0;
1485         if (!h->s->allocated && !h->s->res.sectors && !h->s->have_existing_stripe)
1486                 ret = __bch2_ec_stripe_head_reserve(c, h);
1487         if (ret && needs_stripe_new)
1488                 ret = __bch2_ec_stripe_head_reuse(c, h);
1489         if (ret) {
1490                 bch_err_ratelimited(c, "failed to get stripe: %s", bch2_err_str(ret));
1491                 goto err;
1492         }
1493
1494         if (!h->s->allocated) {
1495                 ret = new_stripe_alloc_buckets(c, h, cl);
1496                 if (ret)
1497                         goto err;
1498
1499                 h->s->allocated = true;
1500         }
1501
1502         return h;
1503
1504 err:
1505         bch2_ec_stripe_head_put(c, h);
1506         return ERR_PTR(ret);
1507 }
1508
1509 void bch2_ec_stop_dev(struct bch_fs *c, struct bch_dev *ca)
1510 {
1511         struct ec_stripe_head *h;
1512         struct open_bucket *ob;
1513         unsigned i;
1514
1515         mutex_lock(&c->ec_stripe_head_lock);
1516         list_for_each_entry(h, &c->ec_stripe_head_list, list) {
1517
1518                 mutex_lock(&h->lock);
1519                 if (!h->s)
1520                         goto unlock;
1521
1522                 for (i = 0; i < h->s->new_stripe.key.v.nr_blocks; i++) {
1523                         if (!h->s->blocks[i])
1524                                 continue;
1525
1526                         ob = c->open_buckets + h->s->blocks[i];
1527                         if (ob->dev == ca->dev_idx)
1528                                 goto found;
1529                 }
1530                 goto unlock;
1531 found:
1532                 h->s->err = -EROFS;
1533                 ec_stripe_set_pending(c, h);
1534 unlock:
1535                 mutex_unlock(&h->lock);
1536         }
1537         mutex_unlock(&c->ec_stripe_head_lock);
1538 }
1539
1540 void bch2_stripes_heap_start(struct bch_fs *c)
1541 {
1542         struct genradix_iter iter;
1543         struct stripe *m;
1544
1545         genradix_for_each(&c->stripes, iter, m)
1546                 if (m->alive)
1547                         bch2_stripes_heap_insert(c, m, iter.pos);
1548 }
1549
1550 int bch2_stripes_read(struct bch_fs *c)
1551 {
1552         struct btree_trans trans;
1553         struct btree_iter iter;
1554         struct bkey_s_c k;
1555         const struct bch_stripe *s;
1556         struct stripe *m;
1557         unsigned i;
1558         int ret;
1559
1560         bch2_trans_init(&trans, c, 0, 0);
1561
1562         for_each_btree_key(&trans, iter, BTREE_ID_stripes, POS_MIN,
1563                            BTREE_ITER_PREFETCH, k, ret) {
1564                 if (k.k->type != KEY_TYPE_stripe)
1565                         continue;
1566
1567                 ret = __ec_stripe_mem_alloc(c, k.k->p.offset, GFP_KERNEL);
1568                 if (ret)
1569                         break;
1570
1571                 s = bkey_s_c_to_stripe(k).v;
1572
1573                 m = genradix_ptr(&c->stripes, k.k->p.offset);
1574                 m->alive        = true;
1575                 m->sectors      = le16_to_cpu(s->sectors);
1576                 m->algorithm    = s->algorithm;
1577                 m->nr_blocks    = s->nr_blocks;
1578                 m->nr_redundant = s->nr_redundant;
1579                 m->blocks_nonempty = 0;
1580
1581                 for (i = 0; i < s->nr_blocks; i++)
1582                         m->blocks_nonempty += !!stripe_blockcount_get(s, i);
1583
1584                 spin_lock(&c->ec_stripes_heap_lock);
1585                 bch2_stripes_heap_update(c, m, k.k->p.offset);
1586                 spin_unlock(&c->ec_stripes_heap_lock);
1587         }
1588         bch2_trans_iter_exit(&trans, &iter);
1589
1590         bch2_trans_exit(&trans);
1591
1592         if (ret)
1593                 bch_err(c, "error reading stripes: %i", ret);
1594
1595         return ret;
1596 }
1597
1598 void bch2_stripes_heap_to_text(struct printbuf *out, struct bch_fs *c)
1599 {
1600         ec_stripes_heap *h = &c->ec_stripes_heap;
1601         struct stripe *m;
1602         size_t i;
1603
1604         spin_lock(&c->ec_stripes_heap_lock);
1605         for (i = 0; i < min_t(size_t, h->used, 20); i++) {
1606                 m = genradix_ptr(&c->stripes, h->data[i].idx);
1607
1608                 prt_printf(out, "%zu %u/%u+%u\n", h->data[i].idx,
1609                        h->data[i].blocks_nonempty,
1610                        m->nr_blocks - m->nr_redundant,
1611                        m->nr_redundant);
1612         }
1613         spin_unlock(&c->ec_stripes_heap_lock);
1614 }
1615
1616 void bch2_new_stripes_to_text(struct printbuf *out, struct bch_fs *c)
1617 {
1618         struct ec_stripe_head *h;
1619         struct ec_stripe_new *s;
1620
1621         mutex_lock(&c->ec_stripe_head_lock);
1622         list_for_each_entry(h, &c->ec_stripe_head_list, list) {
1623                 prt_printf(out, "target %u algo %u redundancy %u:\n",
1624                        h->target, h->algo, h->redundancy);
1625
1626                 if (h->s)
1627                         prt_printf(out, "\tpending: blocks %u+%u allocated %u\n",
1628                                h->s->nr_data, h->s->nr_parity,
1629                                bitmap_weight(h->s->blocks_allocated,
1630                                              h->s->nr_data));
1631         }
1632         mutex_unlock(&c->ec_stripe_head_lock);
1633
1634         mutex_lock(&c->ec_stripe_new_lock);
1635         list_for_each_entry(s, &c->ec_stripe_new_list, list) {
1636                 prt_printf(out, "\tin flight: blocks %u+%u pin %u\n",
1637                        s->nr_data, s->nr_parity,
1638                        atomic_read(&s->pin));
1639         }
1640         mutex_unlock(&c->ec_stripe_new_lock);
1641 }
1642
1643 void bch2_fs_ec_exit(struct bch_fs *c)
1644 {
1645         struct ec_stripe_head *h;
1646
1647         while (1) {
1648                 mutex_lock(&c->ec_stripe_head_lock);
1649                 h = list_first_entry_or_null(&c->ec_stripe_head_list,
1650                                              struct ec_stripe_head, list);
1651                 if (h)
1652                         list_del(&h->list);
1653                 mutex_unlock(&c->ec_stripe_head_lock);
1654                 if (!h)
1655                         break;
1656
1657                 BUG_ON(h->s);
1658                 kfree(h);
1659         }
1660
1661         BUG_ON(!list_empty(&c->ec_stripe_new_list));
1662
1663         free_heap(&c->ec_stripes_heap);
1664         genradix_free(&c->stripes);
1665         bioset_exit(&c->ec_bioset);
1666 }
1667
1668 void bch2_fs_ec_init_early(struct bch_fs *c)
1669 {
1670         INIT_WORK(&c->ec_stripe_create_work, ec_stripe_create_work);
1671         INIT_WORK(&c->ec_stripe_delete_work, ec_stripe_delete_work);
1672 }
1673
1674 int bch2_fs_ec_init(struct bch_fs *c)
1675 {
1676         return bioset_init(&c->ec_bioset, 1, offsetof(struct ec_bio, bio),
1677                            BIOSET_NEED_BVECS);
1678 }