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