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

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