From 1c6fdbd8f2465ddfb73a01ec620cbf3d14044e1a Mon Sep 17 00:00:00 2001 From: Kent Overstreet Date: Thu, 16 Mar 2017 22:18:50 -0800 Subject: bcachefs: Initial commit Initially forked from drivers/md/bcache, bcachefs is a new copy-on-write filesystem with every feature you could possibly want. Website: https://bcachefs.org Signed-off-by: Kent Overstreet --- fs/bcachefs/btree_gc.h | 113 +++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 113 insertions(+) create mode 100644 fs/bcachefs/btree_gc.h (limited to 'fs/bcachefs/btree_gc.h') diff --git a/fs/bcachefs/btree_gc.h b/fs/bcachefs/btree_gc.h new file mode 100644 index 000000000000..9d2b9d5953d2 --- /dev/null +++ b/fs/bcachefs/btree_gc.h @@ -0,0 +1,113 @@ +/* SPDX-License-Identifier: GPL-2.0 */ +#ifndef _BCACHEFS_BTREE_GC_H +#define _BCACHEFS_BTREE_GC_H + +#include "btree_types.h" + +enum bkey_type; + +void bch2_coalesce(struct bch_fs *); +void bch2_gc(struct bch_fs *); +void bch2_gc_thread_stop(struct bch_fs *); +int bch2_gc_thread_start(struct bch_fs *); +int bch2_initial_gc(struct bch_fs *, struct list_head *); +u8 bch2_btree_key_recalc_oldest_gen(struct bch_fs *, struct bkey_s_c); +int bch2_btree_mark_key_initial(struct bch_fs *, enum bkey_type, + struct bkey_s_c); +void bch2_mark_dev_superblock(struct bch_fs *, struct bch_dev *, unsigned); + +/* + * For concurrent mark and sweep (with other index updates), we define a total + * ordering of _all_ references GC walks: + * + * Note that some references will have the same GC position as others - e.g. + * everything within the same btree node; in those cases we're relying on + * whatever locking exists for where those references live, i.e. the write lock + * on a btree node. + * + * That locking is also required to ensure GC doesn't pass the updater in + * between the updater adding/removing the reference and updating the GC marks; + * without that, we would at best double count sometimes. + * + * That part is important - whenever calling bch2_mark_pointers(), a lock _must_ + * be held that prevents GC from passing the position the updater is at. + * + * (What about the start of gc, when we're clearing all the marks? GC clears the + * mark with the gc pos seqlock held, and bch_mark_bucket checks against the gc + * position inside its cmpxchg loop, so crap magically works). + */ + +/* Position of (the start of) a gc phase: */ +static inline struct gc_pos gc_phase(enum gc_phase phase) +{ + return (struct gc_pos) { + .phase = phase, + .pos = POS_MIN, + .level = 0, + }; +} + +static inline int gc_pos_cmp(struct gc_pos l, struct gc_pos r) +{ + if (l.phase != r.phase) + return l.phase < r.phase ? -1 : 1; + if (bkey_cmp(l.pos, r.pos)) + return bkey_cmp(l.pos, r.pos); + if (l.level != r.level) + return l.level < r.level ? -1 : 1; + return 0; +} + +static inline struct gc_pos gc_pos_btree(enum btree_id id, + struct bpos pos, unsigned level) +{ + return (struct gc_pos) { + .phase = GC_PHASE_BTREE_EXTENTS + id, + .pos = pos, + .level = level, + }; +} + +/* + * GC position of the pointers within a btree node: note, _not_ for &b->key + * itself, that lives in the parent node: + */ +static inline struct gc_pos gc_pos_btree_node(struct btree *b) +{ + return gc_pos_btree(b->btree_id, b->key.k.p, b->level); +} + +/* + * GC position of the pointer to a btree root: we don't use + * gc_pos_pointer_to_btree_node() here to avoid a potential race with + * btree_split() increasing the tree depth - the new root will have level > the + * old root and thus have a greater gc position than the old root, but that + * would be incorrect since once gc has marked the root it's not coming back. + */ +static inline struct gc_pos gc_pos_btree_root(enum btree_id id) +{ + return gc_pos_btree(id, POS_MAX, BTREE_MAX_DEPTH); +} + +static inline struct gc_pos gc_pos_alloc(struct bch_fs *c, struct open_bucket *ob) +{ + return (struct gc_pos) { + .phase = GC_PHASE_ALLOC, + .pos = POS(ob ? ob - c->open_buckets : 0, 0), + }; +} + +static inline bool gc_will_visit(struct bch_fs *c, struct gc_pos pos) +{ + unsigned seq; + bool ret; + + do { + seq = read_seqcount_begin(&c->gc_pos_lock); + ret = gc_pos_cmp(c->gc_pos, pos) < 0; + } while (read_seqcount_retry(&c->gc_pos_lock, seq)); + + return ret; +} + +#endif /* _BCACHEFS_BTREE_GC_H */ -- cgit v1.2.3