linux/fs/bcachefs/ec.c

// SPDX-License-Identifier: GPL-2.0

/* erasure coding */

#include "bcachefs.h"
#include "alloc_background.h"
#include "alloc_foreground.h"
#include "backpointers.h"
#include "bkey_buf.h"
#include "bset.h"
#include "btree_gc.h"
#include "btree_update.h"
#include "btree_write_buffer.h"
#include "buckets.h"
#include "checksum.h"
#include "disk_accounting.h"
#include "disk_groups.h"
#include "ec.h"
#include "error.h"
#include "io_read.h"
#include "keylist.h"
#include "recovery.h"
#include "replicas.h"
#include "super-io.h"
#include "util.h"

#include <linux/sort.h>

#ifdef __KERNEL__

#include <linux/raid/pq.h>
#include <linux/raid/xor.h>

static void raid5_recov(unsigned disks, unsigned failed_idx,
			size_t size, void **data)
{ … }

static void raid_gen(int nd, int np, size_t size, void **v)
{ … }

static void raid_rec(int nr, int *ir, int nd, int np, size_t size, void **v)
{ … }

#else

#include <raid/raid.h>

#endif

struct ec_bio { … };

/* Stripes btree keys: */

int bch2_stripe_invalid(struct bch_fs *c, struct bkey_s_c k,
			enum bch_validate_flags flags,
			struct printbuf *err)
{ … }

void bch2_stripe_to_text(struct printbuf *out, struct bch_fs *c,
			 struct bkey_s_c k)
{ … }

/* Triggers: */

static int __mark_stripe_bucket(struct btree_trans *trans,
				struct bch_dev *ca,
				struct bkey_s_c_stripe s,
				unsigned ptr_idx, bool deleting,
				struct bpos bucket,
				struct bch_alloc_v4 *a,
				enum btree_iter_update_trigger_flags flags)
{ … }

static int mark_stripe_bucket(struct btree_trans *trans,
			      struct bkey_s_c_stripe s,
			      unsigned ptr_idx, bool deleting,
			      enum btree_iter_update_trigger_flags flags)
{ … }

static int mark_stripe_buckets(struct btree_trans *trans,
			       struct bkey_s_c old, struct bkey_s_c new,
			       enum btree_iter_update_trigger_flags flags)
{ … }

int bch2_trigger_stripe(struct btree_trans *trans,
			enum btree_id btree, unsigned level,
			struct bkey_s_c old, struct bkey_s _new,
			enum btree_iter_update_trigger_flags flags)
{ … }

/* returns blocknr in stripe that we matched: */
static const struct bch_extent_ptr *bkey_matches_stripe(struct bch_stripe *s,
						struct bkey_s_c k, unsigned *block)
{ … }

static bool extent_has_stripe_ptr(struct bkey_s_c k, u64 idx)
{ … }

/* Stripe bufs: */

static void ec_stripe_buf_exit(struct ec_stripe_buf *buf)
{ … }

/* XXX: this is a non-mempoolified memory allocation: */
static int ec_stripe_buf_init(struct ec_stripe_buf *buf,
			      unsigned offset, unsigned size)
{ … }

/* Checksumming: */

static struct bch_csum ec_block_checksum(struct ec_stripe_buf *buf,
					 unsigned block, unsigned offset)
{ … }

static void ec_generate_checksums(struct ec_stripe_buf *buf)
{ … }

static void ec_validate_checksums(struct bch_fs *c, struct ec_stripe_buf *buf)
{ … }

/* Erasure coding: */

static void ec_generate_ec(struct ec_stripe_buf *buf)
{ … }

static unsigned ec_nr_failed(struct ec_stripe_buf *buf)
{ … }

static int ec_do_recov(struct bch_fs *c, struct ec_stripe_buf *buf)
{ … }

/* IO: */

static void ec_block_endio(struct bio *bio)
{ … }

static void ec_block_io(struct bch_fs *c, struct ec_stripe_buf *buf,
			blk_opf_t opf, unsigned idx, struct closure *cl)
{ … }

static int get_stripe_key_trans(struct btree_trans *trans, u64 idx,
				struct ec_stripe_buf *stripe)
{ … }

/* recovery read path: */
int bch2_ec_read_extent(struct btree_trans *trans, struct bch_read_bio *rbio)
{ … }

/* stripe bucket accounting: */

static int __ec_stripe_mem_alloc(struct bch_fs *c, size_t idx, gfp_t gfp)
{ … }

static int ec_stripe_mem_alloc(struct btree_trans *trans,
			       struct btree_iter *iter)
{ … }

/*
 * Hash table of open stripes:
 * Stripes that are being created or modified are kept in a hash table, so that
 * stripe deletion can skip them.
 */

static bool __bch2_stripe_is_open(struct bch_fs *c, u64 idx)
{ … }

static bool bch2_stripe_is_open(struct bch_fs *c, u64 idx)
{ … }

static bool bch2_try_open_stripe(struct bch_fs *c,
				 struct ec_stripe_new *s,
				 u64 idx)
{ … }

static void bch2_stripe_close(struct bch_fs *c, struct ec_stripe_new *s)
{ … }

/* Heap of all existing stripes, ordered by blocks_nonempty */

static u64 stripe_idx_to_delete(struct bch_fs *c)
{ … }

static inline void ec_stripes_heap_set_backpointer(ec_stripes_heap *h,
						   size_t i)
{ … }

static inline bool ec_stripes_heap_cmp(const void *l, const void *r, void __always_unused *args)
{ … }

static inline void ec_stripes_heap_swap(void *l, void *r, void *h)
{ … }

static void heap_verify_backpointer(struct bch_fs *c, size_t idx)
{ … }

void bch2_stripes_heap_del(struct bch_fs *c,
			   struct stripe *m, size_t idx)
{ … }

void bch2_stripes_heap_insert(struct bch_fs *c,
			      struct stripe *m, size_t idx)
{ … }

void bch2_stripes_heap_update(struct bch_fs *c,
			      struct stripe *m, size_t idx)
{ … }

/* stripe deletion */

static int ec_stripe_delete(struct btree_trans *trans, u64 idx)
{ … }

static void ec_stripe_delete_work(struct work_struct *work)
{ … }

void bch2_do_stripe_deletes(struct bch_fs *c)
{ … }

/* stripe creation: */

static int ec_stripe_key_update(struct btree_trans *trans,
				struct bkey_i_stripe *new,
				bool create)
{ … }

static int ec_stripe_update_extent(struct btree_trans *trans,
				   struct bch_dev *ca,
				   struct bpos bucket, u8 gen,
				   struct ec_stripe_buf *s,
				   struct bpos *bp_pos)
{ … }

static int ec_stripe_update_bucket(struct btree_trans *trans, struct ec_stripe_buf *s,
				   unsigned block)
{ … }

static int ec_stripe_update_extents(struct bch_fs *c, struct ec_stripe_buf *s)
{ … }

static void zero_out_rest_of_ec_bucket(struct bch_fs *c,
				       struct ec_stripe_new *s,
				       unsigned block,
				       struct open_bucket *ob)
{ … }

void bch2_ec_stripe_new_free(struct bch_fs *c, struct ec_stripe_new *s)
{ … }

/*
 * data buckets of new stripe all written: create the stripe
 */
static void ec_stripe_create(struct ec_stripe_new *s)
{ … }

static struct ec_stripe_new *get_pending_stripe(struct bch_fs *c)
{ … }

static void ec_stripe_create_work(struct work_struct *work)
{ … }

void bch2_ec_do_stripe_creates(struct bch_fs *c)
{ … }

static void ec_stripe_set_pending(struct bch_fs *c, struct ec_stripe_head *h)
{ … }

void bch2_ec_bucket_cancel(struct bch_fs *c, struct open_bucket *ob)
{ … }

void *bch2_writepoint_ec_buf(struct bch_fs *c, struct write_point *wp)
{ … }

static int unsigned_cmp(const void *_l, const void *_r)
{ … }

/* pick most common bucket size: */
static unsigned pick_blocksize(struct bch_fs *c,
			       struct bch_devs_mask *devs)
{ … }

static bool may_create_new_stripe(struct bch_fs *c)
{ … }

static void ec_stripe_key_init(struct bch_fs *c,
			       struct bkey_i *k,
			       unsigned nr_data,
			       unsigned nr_parity,
			       unsigned stripe_size)
{ … }

static int ec_new_stripe_alloc(struct bch_fs *c, struct ec_stripe_head *h)
{ … }

static struct ec_stripe_head *
ec_new_stripe_head_alloc(struct bch_fs *c, unsigned target,
			 unsigned algo, unsigned redundancy,
			 enum bch_watermark watermark)
{ … }

void bch2_ec_stripe_head_put(struct bch_fs *c, struct ec_stripe_head *h)
{ … }

static struct ec_stripe_head *
__bch2_ec_stripe_head_get(struct btree_trans *trans,
			  unsigned target,
			  unsigned algo,
			  unsigned redundancy,
			  enum bch_watermark watermark)
{ … }

static int new_stripe_alloc_buckets(struct btree_trans *trans, struct ec_stripe_head *h,
				    enum bch_watermark watermark, struct closure *cl)
{ … }

/* XXX: doesn't obey target: */
static s64 get_existing_stripe(struct bch_fs *c,
			       struct ec_stripe_head *head)
{ … }

static int __bch2_ec_stripe_head_reuse(struct btree_trans *trans, struct ec_stripe_head *h)
{ … }

static int __bch2_ec_stripe_head_reserve(struct btree_trans *trans, struct ec_stripe_head *h)
{ … }

struct ec_stripe_head *bch2_ec_stripe_head_get(struct btree_trans *trans,
					       unsigned target,
					       unsigned algo,
					       unsigned redundancy,
					       enum bch_watermark watermark,
					       struct closure *cl)
{ … }

static void __bch2_ec_stop(struct bch_fs *c, struct bch_dev *ca)
{ … }

void bch2_ec_stop_dev(struct bch_fs *c, struct bch_dev *ca)
{ … }

void bch2_fs_ec_stop(struct bch_fs *c)
{ … }

static bool bch2_fs_ec_flush_done(struct bch_fs *c)
{ … }

void bch2_fs_ec_flush(struct bch_fs *c)
{ … }

int bch2_stripes_read(struct bch_fs *c)
{ … }

void bch2_stripes_heap_to_text(struct printbuf *out, struct bch_fs *c)
{ … }

static void bch2_new_stripe_to_text(struct printbuf *out, struct bch_fs *c,
				    struct ec_stripe_new *s)
{ … }

void bch2_new_stripes_to_text(struct printbuf *out, struct bch_fs *c)
{ … }

void bch2_fs_ec_exit(struct bch_fs *c)
{ … }

void bch2_fs_ec_init_early(struct bch_fs *c)
{ … }

int bch2_fs_ec_init(struct bch_fs *c)
{ … }