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[0], idx, gfp))
 549                 return -ENOMEM;
 550
 551         if (c->gc_pos.phase != GC_PHASE_NOT_RUNNING &&
 552             !genradix_ptr_alloc(&c->stripes[1], 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[0], 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[0], 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[0], 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 bch_fs *c,
 706                                  struct bkey_i_stripe *stripe,
 707                                  struct disk_reservation *res)
 708 {
 709         struct btree_trans trans;
 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         bch2_trans_init(&trans, c, 0, 0);
 717 retry:
 718         bch2_trans_begin(&trans);
 719
 720         for_each_btree_key(&trans, iter, BTREE_ID_stripes, start_pos,
 721                            BTREE_ITER_SLOTS|BTREE_ITER_INTENT, k, ret) {
 722                 if (bkey_cmp(k.k->p, POS(0, U32_MAX)) > 0) {
 723                         if (start_pos.offset) {
 724                                 start_pos = min_pos;
 725                                 bch2_btree_iter_set_pos(&iter, start_pos);
 726                                 continue;
 727                         }
 728
 729                         ret = -ENOSPC;
 730                         break;
 731                 }
 732
 733                 if (bkey_deleted(k.k))
 734                         goto found_slot;
 735         }
 736
 737         goto err;
 738 found_slot:
 739         start_pos = iter.pos;
 740
 741         ret = ec_stripe_mem_alloc(&trans, &iter);
 742         if (ret)
 743                 goto err;
 744
 745         stripe->k.p = iter.pos;
 746
 747         ret   = bch2_trans_update(&trans, &iter, &stripe->k_i, 0) ?:
 748                 bch2_trans_commit(&trans, res, NULL,
 749                                 BTREE_INSERT_NOFAIL);
 750 err:
 751         bch2_trans_iter_exit(&trans, &iter);
 752
 753         if (ret == -EINTR)
 754                 goto retry;
 755
 756         c->ec_stripe_hint = ret ? start_pos.offset : start_pos.offset + 1;
 757         bch2_trans_exit(&trans);
 758
 759         return ret;
 760 }
 761
 762 static int ec_stripe_bkey_update(struct btree_trans *trans,
 763                                  struct bkey_i_stripe *new)
 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_ptrs(struct bch_fs *c,
 822                                  struct ec_stripe_buf *s,
 823                                  struct bkey *pos)
 824 {
 825         struct btree_trans trans;
 826         struct btree_iter iter;
 827         struct bkey_s_c k;
 828         struct bkey_s_extent e;
 829         struct bkey_buf sk;
 830         struct bpos next_pos;
 831         int ret = 0, dev, block;
 832
 833         bch2_bkey_buf_init(&sk);
 834         bch2_trans_init(&trans, c, BTREE_ITER_MAX, 0);
 835
 836         /* XXX this doesn't support the reflink btree */
 837
 838         bch2_trans_iter_init(&trans, &iter, BTREE_ID_extents,
 839                              bkey_start_pos(pos),
 840                              BTREE_ITER_INTENT);
 841 retry:
 842         while (bch2_trans_begin(&trans),
 843                (k = bch2_btree_iter_peek(&iter)).k &&
 844                !(ret = bkey_err(k)) &&
 845                bkey_cmp(bkey_start_pos(k.k), pos->p) < 0) {
 846                 struct bch_extent_ptr *ptr, *ec_ptr = NULL;
 847
 848                 if (extent_has_stripe_ptr(k, s->key.k.p.offset)) {
 849                         bch2_btree_iter_advance(&iter);
 850                         continue;
 851                 }
 852
 853                 block = bkey_matches_stripe(&s->key.v, k);
 854                 if (block < 0) {
 855                         bch2_btree_iter_advance(&iter);
 856                         continue;
 857                 }
 858
 859                 dev = s->key.v.ptrs[block].dev;
 860
 861                 bch2_bkey_buf_reassemble(&sk, c, k);
 862                 e = bkey_i_to_s_extent(sk.k);
 863
 864                 bch2_bkey_drop_ptrs(e.s, ptr, ptr->dev != dev);
 865                 ec_ptr = (void *) bch2_bkey_has_device(e.s_c, dev);
 866                 BUG_ON(!ec_ptr);
 867
 868                 extent_stripe_ptr_add(e, s, ec_ptr, block);
 869
 870                 bch2_btree_iter_set_pos(&iter, bkey_start_pos(&sk.k->k));
 871                 next_pos = sk.k->k.p;
 872
 873                 ret   = bch2_btree_iter_traverse(&iter) ?:
 874                         bch2_trans_update(&trans, &iter, sk.k, 0) ?:
 875                         bch2_trans_commit(&trans, NULL, NULL,
 876                                         BTREE_INSERT_NOFAIL);
 877                 if (!ret)
 878                         bch2_btree_iter_set_pos(&iter, next_pos);
 879                 if (ret)
 880                         break;
 881         }
 882         if (ret == -EINTR)
 883                 goto retry;
 884         bch2_trans_iter_exit(&trans, &iter);
 885
 886         bch2_trans_exit(&trans);
 887         bch2_bkey_buf_exit(&sk, c);
 888
 889         return ret;
 890 }
 891
 892 /*
 893  * data buckets of new stripe all written: create the stripe
 894  */
 895 static void ec_stripe_create(struct ec_stripe_new *s)
 896 {
 897         struct bch_fs *c = s->c;
 898         struct open_bucket *ob;
 899         struct bkey_i *k;
 900         struct stripe *m;
 901         struct bch_stripe *v = &s->new_stripe.key.v;
 902         unsigned i, nr_data = v->nr_blocks - v->nr_redundant;
 903         int ret;
 904
 905         BUG_ON(s->h->s == s);
 906
 907         closure_sync(&s->iodone);
 908
 909         if (s->err) {
 910                 if (s->err != -EROFS)
 911                         bch_err(c, "error creating stripe: error writing data buckets");
 912                 goto err;
 913         }
 914
 915         if (s->have_existing_stripe) {
 916                 ec_validate_checksums(c, &s->existing_stripe);
 917
 918                 if (ec_do_recov(c, &s->existing_stripe)) {
 919                         bch_err(c, "error creating stripe: error reading existing stripe");
 920                         goto err;
 921                 }
 922
 923                 for (i = 0; i < nr_data; i++)
 924                         if (stripe_blockcount_get(&s->existing_stripe.key.v, i))
 925                                 swap(s->new_stripe.data[i],
 926                                      s->existing_stripe.data[i]);
 927
 928                 ec_stripe_buf_exit(&s->existing_stripe);
 929         }
 930
 931         BUG_ON(!s->allocated);
 932
 933         if (!percpu_ref_tryget(&c->writes))
 934                 goto err;
 935
 936         ec_generate_ec(&s->new_stripe);
 937
 938         ec_generate_checksums(&s->new_stripe);
 939
 940         /* write p/q: */
 941         for (i = nr_data; i < v->nr_blocks; i++)
 942                 ec_block_io(c, &s->new_stripe, REQ_OP_WRITE, i, &s->iodone);
 943         closure_sync(&s->iodone);
 944
 945         if (ec_nr_failed(&s->new_stripe)) {
 946                 bch_err(c, "error creating stripe: error writing redundancy buckets");
 947                 goto err_put_writes;
 948         }
 949
 950         ret = s->have_existing_stripe
 951                 ? bch2_trans_do(c, &s->res, NULL, BTREE_INSERT_NOFAIL,
 952                                 ec_stripe_bkey_update(&trans, &s->new_stripe.key))
 953                 : ec_stripe_bkey_insert(c, &s->new_stripe.key, &s->res);
 954         if (ret) {
 955                 bch_err(c, "error creating stripe: error creating stripe key");
 956                 goto err_put_writes;
 957         }
 958
 959         for_each_keylist_key(&s->keys, k) {
 960                 ret = ec_stripe_update_ptrs(c, &s->new_stripe, &k->k);
 961                 if (ret) {
 962                         bch_err(c, "error creating stripe: error %i updating pointers", ret);
 963                         break;
 964                 }
 965         }
 966
 967         spin_lock(&c->ec_stripes_heap_lock);
 968         m = genradix_ptr(&c->stripes[0], s->new_stripe.key.k.p.offset);
 969
 970         BUG_ON(m->on_heap);
 971         bch2_stripes_heap_insert(c, m, s->new_stripe.key.k.p.offset);
 972         spin_unlock(&c->ec_stripes_heap_lock);
 973 err_put_writes:
 974         percpu_ref_put(&c->writes);
 975 err:
 976         bch2_disk_reservation_put(c, &s->res);
 977
 978         for (i = 0; i < v->nr_blocks; i++)
 979                 if (s->blocks[i]) {
 980                         ob = c->open_buckets + s->blocks[i];
 981
 982                         if (i < nr_data) {
 983                                 ob->ec = NULL;
 984                                 __bch2_open_bucket_put(c, ob);
 985                         } else {
 986                                 bch2_open_bucket_put(c, ob);
 987                         }
 988                 }
 989
 990         bch2_keylist_free(&s->keys, s->inline_keys);
 991
 992         ec_stripe_buf_exit(&s->existing_stripe);
 993         ec_stripe_buf_exit(&s->new_stripe);
 994         closure_debug_destroy(&s->iodone);
 995         kfree(s);
 996 }
 997
 998 static void ec_stripe_create_work(struct work_struct *work)
 999 {
1000         struct bch_fs *c = container_of(work,
1001                 struct bch_fs, ec_stripe_create_work);
1002         struct ec_stripe_new *s, *n;
1003 restart:
1004         mutex_lock(&c->ec_stripe_new_lock);
1005         list_for_each_entry_safe(s, n, &c->ec_stripe_new_list, list)
1006                 if (!atomic_read(&s->pin)) {
1007                         list_del(&s->list);
1008                         mutex_unlock(&c->ec_stripe_new_lock);
1009                         ec_stripe_create(s);
1010                         goto restart;
1011                 }
1012         mutex_unlock(&c->ec_stripe_new_lock);
1013 }
1014
1015 static void ec_stripe_new_put(struct bch_fs *c, struct ec_stripe_new *s)
1016 {
1017         BUG_ON(atomic_read(&s->pin) <= 0);
1018
1019         if (atomic_dec_and_test(&s->pin)) {
1020                 BUG_ON(!s->pending);
1021                 queue_work(system_long_wq, &c->ec_stripe_create_work);
1022         }
1023 }
1024
1025 static void ec_stripe_set_pending(struct bch_fs *c, struct ec_stripe_head *h)
1026 {
1027         struct ec_stripe_new *s = h->s;
1028
1029         BUG_ON(!s->allocated && !s->err);
1030
1031         h->s            = NULL;
1032         s->pending      = true;
1033
1034         mutex_lock(&c->ec_stripe_new_lock);
1035         list_add(&s->list, &c->ec_stripe_new_list);
1036         mutex_unlock(&c->ec_stripe_new_lock);
1037
1038         ec_stripe_new_put(c, s);
1039 }
1040
1041 /* have a full bucket - hand it off to be erasure coded: */
1042 void bch2_ec_bucket_written(struct bch_fs *c, struct open_bucket *ob)
1043 {
1044         struct ec_stripe_new *s = ob->ec;
1045
1046         if (ob->sectors_free)
1047                 s->err = -1;
1048
1049         ec_stripe_new_put(c, s);
1050 }
1051
1052 void bch2_ec_bucket_cancel(struct bch_fs *c, struct open_bucket *ob)
1053 {
1054         struct ec_stripe_new *s = ob->ec;
1055
1056         s->err = -EIO;
1057 }
1058
1059 void *bch2_writepoint_ec_buf(struct bch_fs *c, struct write_point *wp)
1060 {
1061         struct open_bucket *ob = ec_open_bucket(c, &wp->ptrs);
1062         struct bch_dev *ca;
1063         unsigned offset;
1064
1065         if (!ob)
1066                 return NULL;
1067
1068         ca      = bch_dev_bkey_exists(c, ob->ptr.dev);
1069         offset  = ca->mi.bucket_size - ob->sectors_free;
1070
1071         return ob->ec->new_stripe.data[ob->ec_idx] + (offset << 9);
1072 }
1073
1074 void bch2_ob_add_backpointer(struct bch_fs *c, struct open_bucket *ob,
1075                              struct bkey *k)
1076 {
1077         struct ec_stripe_new *ec = ob->ec;
1078
1079         if (!ec)
1080                 return;
1081
1082         mutex_lock(&ec->lock);
1083
1084         if (bch2_keylist_realloc(&ec->keys, ec->inline_keys,
1085                                  ARRAY_SIZE(ec->inline_keys),
1086                                  BKEY_U64s)) {
1087                 BUG();
1088         }
1089
1090         bkey_init(&ec->keys.top->k);
1091         ec->keys.top->k.p       = k->p;
1092         ec->keys.top->k.size    = k->size;
1093         bch2_keylist_push(&ec->keys);
1094
1095         mutex_unlock(&ec->lock);
1096 }
1097
1098 static int unsigned_cmp(const void *_l, const void *_r)
1099 {
1100         unsigned l = *((const unsigned *) _l);
1101         unsigned r = *((const unsigned *) _r);
1102
1103         return cmp_int(l, r);
1104 }
1105
1106 /* pick most common bucket size: */
1107 static unsigned pick_blocksize(struct bch_fs *c,
1108                                struct bch_devs_mask *devs)
1109 {
1110         struct bch_dev *ca;
1111         unsigned i, nr = 0, sizes[BCH_SB_MEMBERS_MAX];
1112         struct {
1113                 unsigned nr, size;
1114         } cur = { 0, 0 }, best = { 0, 0 };
1115
1116         for_each_member_device_rcu(ca, c, i, devs)
1117                 sizes[nr++] = ca->mi.bucket_size;
1118
1119         sort(sizes, nr, sizeof(unsigned), unsigned_cmp, NULL);
1120
1121         for (i = 0; i < nr; i++) {
1122                 if (sizes[i] != cur.size) {
1123                         if (cur.nr > best.nr)
1124                                 best = cur;
1125
1126                         cur.nr = 0;
1127                         cur.size = sizes[i];
1128                 }
1129
1130                 cur.nr++;
1131         }
1132
1133         if (cur.nr > best.nr)
1134                 best = cur;
1135
1136         return best.size;
1137 }
1138
1139 static bool may_create_new_stripe(struct bch_fs *c)
1140 {
1141         return false;
1142 }
1143
1144 static void ec_stripe_key_init(struct bch_fs *c,
1145                                struct bkey_i_stripe *s,
1146                                unsigned nr_data,
1147                                unsigned nr_parity,
1148                                unsigned stripe_size)
1149 {
1150         unsigned u64s;
1151
1152         bkey_stripe_init(&s->k_i);
1153         s->v.sectors                    = cpu_to_le16(stripe_size);
1154         s->v.algorithm                  = 0;
1155         s->v.nr_blocks                  = nr_data + nr_parity;
1156         s->v.nr_redundant               = nr_parity;
1157         s->v.csum_granularity_bits      = ilog2(c->sb.encoded_extent_max);
1158         s->v.csum_type                  = BCH_CSUM_crc32c;
1159         s->v.pad                        = 0;
1160
1161         while ((u64s = stripe_val_u64s(&s->v)) > BKEY_VAL_U64s_MAX) {
1162                 BUG_ON(1 << s->v.csum_granularity_bits >=
1163                        le16_to_cpu(s->v.sectors) ||
1164                        s->v.csum_granularity_bits == U8_MAX);
1165                 s->v.csum_granularity_bits++;
1166         }
1167
1168         set_bkey_val_u64s(&s->k, u64s);
1169 }
1170
1171 static int ec_new_stripe_alloc(struct bch_fs *c, struct ec_stripe_head *h)
1172 {
1173         struct ec_stripe_new *s;
1174
1175         lockdep_assert_held(&h->lock);
1176
1177         s = kzalloc(sizeof(*s), GFP_KERNEL);
1178         if (!s)
1179                 return -ENOMEM;
1180
1181         mutex_init(&s->lock);
1182         closure_init(&s->iodone, NULL);
1183         atomic_set(&s->pin, 1);
1184         s->c            = c;
1185         s->h            = h;
1186         s->nr_data      = min_t(unsigned, h->nr_active_devs,
1187                                 BCH_BKEY_PTRS_MAX) - h->redundancy;
1188         s->nr_parity    = h->redundancy;
1189
1190         bch2_keylist_init(&s->keys, s->inline_keys);
1191
1192         ec_stripe_key_init(c, &s->new_stripe.key, s->nr_data,
1193                            s->nr_parity, h->blocksize);
1194
1195         h->s = s;
1196         return 0;
1197 }
1198
1199 static struct ec_stripe_head *
1200 ec_new_stripe_head_alloc(struct bch_fs *c, unsigned target,
1201                          unsigned algo, unsigned redundancy,
1202                          bool copygc)
1203 {
1204         struct ec_stripe_head *h;
1205         struct bch_dev *ca;
1206         unsigned i;
1207
1208         h = kzalloc(sizeof(*h), GFP_KERNEL);
1209         if (!h)
1210                 return NULL;
1211
1212         mutex_init(&h->lock);
1213         mutex_lock(&h->lock);
1214
1215         h->target       = target;
1216         h->algo         = algo;
1217         h->redundancy   = redundancy;
1218         h->copygc       = copygc;
1219
1220         rcu_read_lock();
1221         h->devs = target_rw_devs(c, BCH_DATA_user, target);
1222
1223         for_each_member_device_rcu(ca, c, i, &h->devs)
1224                 if (!ca->mi.durability)
1225                         __clear_bit(i, h->devs.d);
1226
1227         h->blocksize = pick_blocksize(c, &h->devs);
1228
1229         for_each_member_device_rcu(ca, c, i, &h->devs)
1230                 if (ca->mi.bucket_size == h->blocksize)
1231                         h->nr_active_devs++;
1232
1233         rcu_read_unlock();
1234         list_add(&h->list, &c->ec_stripe_head_list);
1235         return h;
1236 }
1237
1238 void bch2_ec_stripe_head_put(struct bch_fs *c, struct ec_stripe_head *h)
1239 {
1240         if (h->s &&
1241             h->s->allocated &&
1242             bitmap_weight(h->s->blocks_allocated,
1243                           h->s->nr_data) == h->s->nr_data)
1244                 ec_stripe_set_pending(c, h);
1245
1246         mutex_unlock(&h->lock);
1247 }
1248
1249 struct ec_stripe_head *__bch2_ec_stripe_head_get(struct bch_fs *c,
1250                                                  unsigned target,
1251                                                  unsigned algo,
1252                                                  unsigned redundancy,
1253                                                  bool copygc)
1254 {
1255         struct ec_stripe_head *h;
1256
1257         if (!redundancy)
1258                 return NULL;
1259
1260         mutex_lock(&c->ec_stripe_head_lock);
1261         list_for_each_entry(h, &c->ec_stripe_head_list, list)
1262                 if (h->target           == target &&
1263                     h->algo             == algo &&
1264                     h->redundancy       == redundancy &&
1265                     h->copygc           == copygc) {
1266                         mutex_lock(&h->lock);
1267                         goto found;
1268                 }
1269
1270         h = ec_new_stripe_head_alloc(c, target, algo, redundancy, copygc);
1271 found:
1272         mutex_unlock(&c->ec_stripe_head_lock);
1273         return h;
1274 }
1275
1276 static int new_stripe_alloc_buckets(struct bch_fs *c, struct ec_stripe_head *h,
1277                                     struct closure *cl)
1278 {
1279         struct bch_devs_mask devs = h->devs;
1280         struct open_bucket *ob;
1281         struct open_buckets buckets;
1282         unsigned i, j, nr_have_parity = 0, nr_have_data = 0;
1283         bool have_cache = true;
1284         int ret = 0;
1285
1286         for (i = 0; i < h->s->new_stripe.key.v.nr_blocks; i++) {
1287                 if (test_bit(i, h->s->blocks_gotten)) {
1288                         __clear_bit(h->s->new_stripe.key.v.ptrs[i].dev, devs.d);
1289                         if (i < h->s->nr_data)
1290                                 nr_have_data++;
1291                         else
1292                                 nr_have_parity++;
1293                 }
1294         }
1295
1296         BUG_ON(nr_have_data     > h->s->nr_data);
1297         BUG_ON(nr_have_parity   > h->s->nr_parity);
1298
1299         percpu_down_read(&c->mark_lock);
1300         rcu_read_lock();
1301
1302         buckets.nr = 0;
1303         if (nr_have_parity < h->s->nr_parity) {
1304                 ret = bch2_bucket_alloc_set(c, &buckets,
1305                                             &h->parity_stripe,
1306                                             &devs,
1307                                             h->s->nr_parity,
1308                                             &nr_have_parity,
1309                                             &have_cache,
1310                                             h->copygc
1311                                             ? RESERVE_MOVINGGC
1312                                             : RESERVE_NONE,
1313                                             0,
1314                                             cl);
1315
1316                 open_bucket_for_each(c, &buckets, ob, i) {
1317                         j = find_next_zero_bit(h->s->blocks_gotten,
1318                                                h->s->nr_data + h->s->nr_parity,
1319                                                h->s->nr_data);
1320                         BUG_ON(j >= h->s->nr_data + h->s->nr_parity);
1321
1322                         h->s->blocks[j] = buckets.v[i];
1323                         h->s->new_stripe.key.v.ptrs[j] = ob->ptr;
1324                         __set_bit(j, h->s->blocks_gotten);
1325                 }
1326
1327                 if (ret)
1328                         goto err;
1329         }
1330
1331         buckets.nr = 0;
1332         if (nr_have_data < h->s->nr_data) {
1333                 ret = bch2_bucket_alloc_set(c, &buckets,
1334                                             &h->block_stripe,
1335                                             &devs,
1336                                             h->s->nr_data,
1337                                             &nr_have_data,
1338                                             &have_cache,
1339                                             h->copygc
1340                                             ? RESERVE_MOVINGGC
1341                                             : RESERVE_NONE,
1342                                             0,
1343                                             cl);
1344
1345                 open_bucket_for_each(c, &buckets, ob, i) {
1346                         j = find_next_zero_bit(h->s->blocks_gotten,
1347                                                h->s->nr_data, 0);
1348                         BUG_ON(j >= h->s->nr_data);
1349
1350                         h->s->blocks[j] = buckets.v[i];
1351                         h->s->new_stripe.key.v.ptrs[j] = ob->ptr;
1352                         __set_bit(j, h->s->blocks_gotten);
1353                 }
1354
1355                 if (ret)
1356                         goto err;
1357         }
1358 err:
1359         rcu_read_unlock();
1360         percpu_up_read(&c->mark_lock);
1361         return ret;
1362 }
1363
1364 /* XXX: doesn't obey target: */
1365 static s64 get_existing_stripe(struct bch_fs *c,
1366                                struct ec_stripe_head *head)
1367 {
1368         ec_stripes_heap *h = &c->ec_stripes_heap;
1369         struct stripe *m;
1370         size_t heap_idx;
1371         u64 stripe_idx;
1372         s64 ret = -1;
1373
1374         if (may_create_new_stripe(c))
1375                 return -1;
1376
1377         spin_lock(&c->ec_stripes_heap_lock);
1378         for (heap_idx = 0; heap_idx < h->used; heap_idx++) {
1379                 /* No blocks worth reusing, stripe will just be deleted: */
1380                 if (!h->data[heap_idx].blocks_nonempty)
1381                         continue;
1382
1383                 stripe_idx = h->data[heap_idx].idx;
1384                 m = genradix_ptr(&c->stripes[0], stripe_idx);
1385
1386                 if (m->algorithm        == head->algo &&
1387                     m->nr_redundant     == head->redundancy &&
1388                     m->sectors          == head->blocksize &&
1389                     m->blocks_nonempty  < m->nr_blocks - m->nr_redundant) {
1390                         bch2_stripes_heap_del(c, m, stripe_idx);
1391                         ret = stripe_idx;
1392                         break;
1393                 }
1394         }
1395         spin_unlock(&c->ec_stripes_heap_lock);
1396         return ret;
1397 }
1398
1399 static int __bch2_ec_stripe_head_reuse(struct bch_fs *c,
1400                                                    struct ec_stripe_head *h)
1401 {
1402         unsigned i;
1403         s64 idx;
1404         int ret;
1405
1406         idx = get_existing_stripe(c, h);
1407         if (idx < 0) {
1408                 bch_err(c, "failed to find an existing stripe");
1409                 return -ENOSPC;
1410         }
1411
1412         h->s->have_existing_stripe = true;
1413         ret = get_stripe_key(c, idx, &h->s->existing_stripe);
1414         if (ret) {
1415                 bch2_fs_fatal_error(c, "error reading stripe key: %i", ret);
1416                 return ret;
1417         }
1418
1419         if (ec_stripe_buf_init(&h->s->existing_stripe, 0, h->blocksize)) {
1420                 /*
1421                  * this is a problem: we have deleted from the
1422                  * stripes heap already
1423                  */
1424                 BUG();
1425         }
1426
1427         BUG_ON(h->s->existing_stripe.size != h->blocksize);
1428         BUG_ON(h->s->existing_stripe.size != h->s->existing_stripe.key.v.sectors);
1429
1430         for (i = 0; i < h->s->existing_stripe.key.v.nr_blocks; i++) {
1431                 if (stripe_blockcount_get(&h->s->existing_stripe.key.v, i)) {
1432                         __set_bit(i, h->s->blocks_gotten);
1433                         __set_bit(i, h->s->blocks_allocated);
1434                 }
1435
1436                 ec_block_io(c, &h->s->existing_stripe, READ, i, &h->s->iodone);
1437         }
1438
1439         bkey_copy(&h->s->new_stripe.key.k_i,
1440                         &h->s->existing_stripe.key.k_i);
1441
1442         return 0;
1443 }
1444
1445 static int __bch2_ec_stripe_head_reserve(struct bch_fs *c,
1446                                                         struct ec_stripe_head *h)
1447 {
1448         int ret;
1449
1450         ret = bch2_disk_reservation_get(c, &h->s->res,
1451                         h->blocksize,
1452                         h->s->nr_parity, 0);
1453
1454         if (ret) {
1455                 /*
1456                  * This means we need to wait for copygc to
1457                  * empty out buckets from existing stripes:
1458                  */
1459                 bch_err(c, "failed to reserve stripe");
1460         }
1461
1462         return ret;
1463 }
1464
1465 struct ec_stripe_head *bch2_ec_stripe_head_get(struct bch_fs *c,
1466                                                unsigned target,
1467                                                unsigned algo,
1468                                                unsigned redundancy,
1469                                                bool copygc,
1470                                                struct closure *cl)
1471 {
1472         struct ec_stripe_head *h;
1473         int ret;
1474         bool needs_stripe_new;
1475
1476         h = __bch2_ec_stripe_head_get(c, target, algo, redundancy, copygc);
1477         if (!h) {
1478                 bch_err(c, "no stripe head");
1479                 return NULL;
1480         }
1481
1482         needs_stripe_new = !h->s;
1483         if (needs_stripe_new) {
1484                 if (ec_new_stripe_alloc(c, h)) {
1485                         ret = -ENOMEM;
1486                         bch_err(c, "failed to allocate new stripe");
1487                         goto err;
1488                 }
1489
1490                 if (ec_stripe_buf_init(&h->s->new_stripe, 0, h->blocksize))
1491                         BUG();
1492         }
1493
1494         /*
1495          * Try reserve a new stripe before reusing an
1496          * existing stripe. This will prevent unnecessary
1497          * read amplification during write oriented workloads.
1498          */
1499         ret = 0;
1500         if (!h->s->allocated && !h->s->res.sectors && !h->s->have_existing_stripe)
1501                 ret = __bch2_ec_stripe_head_reserve(c, h);
1502         if (ret && needs_stripe_new)
1503                 ret = __bch2_ec_stripe_head_reuse(c, h);
1504         if (ret)
1505                 goto err;
1506
1507         if (!h->s->allocated) {
1508                 ret = new_stripe_alloc_buckets(c, h, cl);
1509                 if (ret)
1510                         goto err;
1511
1512                 h->s->allocated = true;
1513         }
1514
1515         return h;
1516
1517 err:
1518         bch2_ec_stripe_head_put(c, h);
1519         return ERR_PTR(ret);
1520 }
1521
1522 void bch2_ec_stop_dev(struct bch_fs *c, struct bch_dev *ca)
1523 {
1524         struct ec_stripe_head *h;
1525         struct open_bucket *ob;
1526         unsigned i;
1527
1528         mutex_lock(&c->ec_stripe_head_lock);
1529         list_for_each_entry(h, &c->ec_stripe_head_list, list) {
1530
1531                 mutex_lock(&h->lock);
1532                 if (!h->s)
1533                         goto unlock;
1534
1535                 for (i = 0; i < h->s->new_stripe.key.v.nr_blocks; i++) {
1536                         if (!h->s->blocks[i])
1537                                 continue;
1538
1539                         ob = c->open_buckets + h->s->blocks[i];
1540                         if (ob->ptr.dev == ca->dev_idx)
1541                                 goto found;
1542                 }
1543                 goto unlock;
1544 found:
1545                 h->s->err = -EROFS;
1546                 ec_stripe_set_pending(c, h);
1547 unlock:
1548                 mutex_unlock(&h->lock);
1549         }
1550         mutex_unlock(&c->ec_stripe_head_lock);
1551 }
1552
1553 void bch2_stripes_heap_start(struct bch_fs *c)
1554 {
1555         struct genradix_iter iter;
1556         struct stripe *m;
1557
1558         genradix_for_each(&c->stripes[0], iter, m)
1559                 if (m->alive)
1560                         bch2_stripes_heap_insert(c, m, iter.pos);
1561 }
1562
1563 static int __bch2_stripe_write_key(struct btree_trans *trans,
1564                                    struct btree_iter *iter,
1565                                    struct stripe *m,
1566                                    size_t idx,
1567                                    struct bkey_i_stripe *new_key)
1568 {
1569         const struct bch_stripe *v;
1570         struct bkey_s_c k;
1571         unsigned i;
1572         int ret;
1573
1574         bch2_btree_iter_set_pos(iter, POS(0, idx));
1575
1576         k = bch2_btree_iter_peek_slot(iter);
1577         ret = bkey_err(k);
1578         if (ret)
1579                 return ret;
1580
1581         if (k.k->type != KEY_TYPE_stripe)
1582                 return -EIO;
1583
1584         v = bkey_s_c_to_stripe(k).v;
1585         for (i = 0; i < v->nr_blocks; i++)
1586                 if (m->block_sectors[i] != stripe_blockcount_get(v, i))
1587                         goto write;
1588         return 0;
1589 write:
1590         bkey_reassemble(&new_key->k_i, k);
1591
1592         for (i = 0; i < new_key->v.nr_blocks; i++)
1593                 stripe_blockcount_set(&new_key->v, i,
1594                                       m->block_sectors[i]);
1595
1596         return bch2_trans_update(trans, iter, &new_key->k_i, 0);
1597 }
1598
1599 int bch2_stripes_write(struct bch_fs *c, unsigned flags)
1600 {
1601         struct btree_trans trans;
1602         struct btree_iter iter;
1603         struct genradix_iter giter;
1604         struct bkey_i_stripe *new_key;
1605         struct stripe *m;
1606         int ret = 0;
1607
1608         new_key = kmalloc(255 * sizeof(u64), GFP_KERNEL);
1609         BUG_ON(!new_key);
1610
1611         bch2_trans_init(&trans, c, 0, 0);
1612
1613         bch2_trans_iter_init(&trans, &iter, BTREE_ID_stripes, POS_MIN,
1614                              BTREE_ITER_SLOTS|BTREE_ITER_INTENT);
1615
1616         genradix_for_each(&c->stripes[0], giter, m) {
1617                 if (!m->alive)
1618                         continue;
1619
1620                 ret = __bch2_trans_do(&trans, NULL, NULL,
1621                                       BTREE_INSERT_NOFAIL|flags,
1622                         __bch2_stripe_write_key(&trans, &iter, m,
1623                                         giter.pos, new_key));
1624
1625                 if (ret)
1626                         break;
1627         }
1628         bch2_trans_iter_exit(&trans, &iter);
1629
1630         bch2_trans_exit(&trans);
1631
1632         kfree(new_key);
1633
1634         return ret;
1635 }
1636
1637 static int bch2_stripes_read_fn(struct btree_trans *trans, struct bkey_s_c k)
1638 {
1639         const struct bch_stripe *s;
1640         struct bch_fs *c = trans->c;
1641         struct stripe *m;
1642         unsigned i;
1643         int ret = 0;
1644
1645         if (k.k->type != KEY_TYPE_stripe)
1646                 return 0;
1647
1648         ret = __ec_stripe_mem_alloc(c, k.k->p.offset, GFP_KERNEL);
1649         if (ret)
1650                 return ret;
1651
1652         s = bkey_s_c_to_stripe(k).v;
1653
1654         m = genradix_ptr(&c->stripes[0], k.k->p.offset);
1655         m->alive        = true;
1656         m->sectors      = le16_to_cpu(s->sectors);
1657         m->algorithm    = s->algorithm;
1658         m->nr_blocks    = s->nr_blocks;
1659         m->nr_redundant = s->nr_redundant;
1660         m->blocks_nonempty = 0;
1661
1662         for (i = 0; i < s->nr_blocks; i++) {
1663                 m->block_sectors[i] =
1664                         stripe_blockcount_get(s, i);
1665                 m->blocks_nonempty += !!m->block_sectors[i];
1666                 m->ptrs[i] = s->ptrs[i];
1667         }
1668
1669         bch2_bkey_to_replicas(&m->r.e, k);
1670
1671         spin_lock(&c->ec_stripes_heap_lock);
1672         bch2_stripes_heap_update(c, m, k.k->p.offset);
1673         spin_unlock(&c->ec_stripes_heap_lock);
1674
1675         return ret;
1676 }
1677
1678 int bch2_stripes_read(struct bch_fs *c)
1679 {
1680         struct btree_trans trans;
1681         int ret;
1682
1683         bch2_trans_init(&trans, c, 0, 0);
1684         ret = bch2_btree_and_journal_walk(&trans, BTREE_ID_stripes,
1685                                           bch2_stripes_read_fn);
1686         bch2_trans_exit(&trans);
1687         if (ret)
1688                 bch_err(c, "error reading stripes: %i", ret);
1689
1690         return ret;
1691 }
1692
1693 int bch2_ec_mem_alloc(struct bch_fs *c, bool gc)
1694 {
1695         struct btree_trans trans;
1696         struct btree_iter iter;
1697         struct bkey_s_c k;
1698         size_t i, idx = 0;
1699         int ret = 0;
1700
1701         bch2_trans_init(&trans, c, 0, 0);
1702         bch2_trans_iter_init(&trans, &iter, BTREE_ID_stripes, POS(0, U64_MAX), 0);
1703
1704         k = bch2_btree_iter_prev(&iter);
1705         ret = bkey_err(k);
1706         if (!ret && k.k)
1707                 idx = k.k->p.offset + 1;
1708
1709         bch2_trans_iter_exit(&trans, &iter);
1710         bch2_trans_exit(&trans);
1711         if (ret)
1712                 return ret;
1713
1714         if (!idx)
1715                 return 0;
1716
1717         if (!gc &&
1718             !init_heap(&c->ec_stripes_heap, roundup_pow_of_two(idx),
1719                        GFP_KERNEL))
1720                 return -ENOMEM;
1721 #if 0
1722         ret = genradix_prealloc(&c->stripes[gc], idx, GFP_KERNEL);
1723 #else
1724         for (i = 0; i < idx; i++)
1725                 if (!genradix_ptr_alloc(&c->stripes[gc], i, GFP_KERNEL))
1726                         return -ENOMEM;
1727 #endif
1728         return 0;
1729 }
1730
1731 void bch2_stripes_heap_to_text(struct printbuf *out, struct bch_fs *c)
1732 {
1733         ec_stripes_heap *h = &c->ec_stripes_heap;
1734         struct stripe *m;
1735         size_t i;
1736
1737         spin_lock(&c->ec_stripes_heap_lock);
1738         for (i = 0; i < min_t(size_t, h->used, 20); i++) {
1739                 m = genradix_ptr(&c->stripes[0], h->data[i].idx);
1740
1741                 pr_buf(out, "%zu %u/%u+%u\n", h->data[i].idx,
1742                        h->data[i].blocks_nonempty,
1743                        m->nr_blocks - m->nr_redundant,
1744                        m->nr_redundant);
1745         }
1746         spin_unlock(&c->ec_stripes_heap_lock);
1747 }
1748
1749 void bch2_new_stripes_to_text(struct printbuf *out, struct bch_fs *c)
1750 {
1751         struct ec_stripe_head *h;
1752         struct ec_stripe_new *s;
1753
1754         mutex_lock(&c->ec_stripe_head_lock);
1755         list_for_each_entry(h, &c->ec_stripe_head_list, list) {
1756                 pr_buf(out, "target %u algo %u redundancy %u:\n",
1757                        h->target, h->algo, h->redundancy);
1758
1759                 if (h->s)
1760                         pr_buf(out, "\tpending: blocks %u+%u allocated %u\n",
1761                                h->s->nr_data, h->s->nr_parity,
1762                                bitmap_weight(h->s->blocks_allocated,
1763                                              h->s->nr_data));
1764         }
1765         mutex_unlock(&c->ec_stripe_head_lock);
1766
1767         mutex_lock(&c->ec_stripe_new_lock);
1768         list_for_each_entry(s, &c->ec_stripe_new_list, list) {
1769                 pr_buf(out, "\tin flight: blocks %u+%u pin %u\n",
1770                        s->nr_data, s->nr_parity,
1771                        atomic_read(&s->pin));
1772         }
1773         mutex_unlock(&c->ec_stripe_new_lock);
1774 }
1775
1776 void bch2_fs_ec_exit(struct bch_fs *c)
1777 {
1778         struct ec_stripe_head *h;
1779
1780         while (1) {
1781                 mutex_lock(&c->ec_stripe_head_lock);
1782                 h = list_first_entry_or_null(&c->ec_stripe_head_list,
1783                                              struct ec_stripe_head, list);
1784                 if (h)
1785                         list_del(&h->list);
1786                 mutex_unlock(&c->ec_stripe_head_lock);
1787                 if (!h)
1788                         break;
1789
1790                 BUG_ON(h->s);
1791                 kfree(h);
1792         }
1793
1794         BUG_ON(!list_empty(&c->ec_stripe_new_list));
1795
1796         free_heap(&c->ec_stripes_heap);
1797         genradix_free(&c->stripes[0]);
1798         bioset_exit(&c->ec_bioset);
1799 }
1800
1801 int bch2_fs_ec_init(struct bch_fs *c)
1802 {
1803         INIT_WORK(&c->ec_stripe_create_work, ec_stripe_create_work);
1804         INIT_WORK(&c->ec_stripe_delete_work, ec_stripe_delete_work);
1805
1806         return bioset_init(&c->ec_bioset, 1, offsetof(struct ec_bio, bio),
1807                            BIOSET_NEED_BVECS);
1808 }