diff options
Diffstat (limited to 'libbcachefs/buckets.c')
| -rw-r--r-- | libbcachefs/buckets.c | 750 |
1 files changed, 750 insertions, 0 deletions
diff --git a/libbcachefs/buckets.c b/libbcachefs/buckets.c new file mode 100644 index 00000000..396251d5 --- /dev/null +++ b/libbcachefs/buckets.c @@ -0,0 +1,750 @@ +/* + * Code for manipulating bucket marks for garbage collection. + * + * Copyright 2014 Datera, Inc. + * + * Bucket states: + * - free bucket: mark == 0 + * The bucket contains no data and will not be read + * + * - allocator bucket: owned_by_allocator == 1 + * The bucket is on a free list, or it is an open bucket + * + * - cached bucket: owned_by_allocator == 0 && + * dirty_sectors == 0 && + * cached_sectors > 0 + * The bucket contains data but may be safely discarded as there are + * enough replicas of the data on other cache devices, or it has been + * written back to the backing device + * + * - dirty bucket: owned_by_allocator == 0 && + * dirty_sectors > 0 + * The bucket contains data that we must not discard (either only copy, + * or one of the 'main copies' for data requiring multiple replicas) + * + * - metadata bucket: owned_by_allocator == 0 && is_metadata == 1 + * This is a btree node, journal or gen/prio bucket + * + * Lifecycle: + * + * bucket invalidated => bucket on freelist => open bucket => + * [dirty bucket =>] cached bucket => bucket invalidated => ... + * + * Note that cache promotion can skip the dirty bucket step, as data + * is copied from a deeper tier to a shallower tier, onto a cached + * bucket. + * Note also that a cached bucket can spontaneously become dirty -- + * see below. + * + * Only a traversal of the key space can determine whether a bucket is + * truly dirty or cached. + * + * Transitions: + * + * - free => allocator: bucket was invalidated + * - cached => allocator: bucket was invalidated + * + * - allocator => dirty: open bucket was filled up + * - allocator => cached: open bucket was filled up + * - allocator => metadata: metadata was allocated + * + * - dirty => cached: dirty sectors were copied to a deeper tier + * - dirty => free: dirty sectors were overwritten or moved (copy gc) + * - cached => free: cached sectors were overwritten + * + * - metadata => free: metadata was freed + * + * Oddities: + * - cached => dirty: a device was removed so formerly replicated data + * is no longer sufficiently replicated + * - free => cached: cannot happen + * - free => dirty: cannot happen + * - free => metadata: cannot happen + */ + +#include "bcachefs.h" +#include "alloc.h" +#include "btree_gc.h" +#include "buckets.h" +#include "error.h" + +#include <linux/preempt.h> +#include <trace/events/bcachefs.h> + +#ifdef DEBUG_BUCKETS + +#define lg_local_lock lg_global_lock +#define lg_local_unlock lg_global_unlock + +static void bch2_fs_stats_verify(struct bch_fs *c) +{ + struct bch_fs_usage stats = + __bch2_fs_usage_read(c); + + if ((s64) stats.sectors_dirty < 0) + panic("sectors_dirty underflow: %lli\n", stats.sectors_dirty); + + if ((s64) stats.sectors_cached < 0) + panic("sectors_cached underflow: %lli\n", stats.sectors_cached); + + if ((s64) stats.sectors_meta < 0) + panic("sectors_meta underflow: %lli\n", stats.sectors_meta); + + if ((s64) stats.sectors_persistent_reserved < 0) + panic("sectors_persistent_reserved underflow: %lli\n", stats.sectors_persistent_reserved); + + if ((s64) stats.sectors_online_reserved < 0) + panic("sectors_online_reserved underflow: %lli\n", stats.sectors_online_reserved); +} + +#else + +static void bch2_fs_stats_verify(struct bch_fs *c) {} + +#endif + +/* + * Clear journal_seq_valid for buckets for which it's not needed, to prevent + * wraparound: + */ +void bch2_bucket_seq_cleanup(struct bch_fs *c) +{ + u16 last_seq_ondisk = c->journal.last_seq_ondisk; + struct bch_dev *ca; + struct bucket *g; + struct bucket_mark m; + unsigned i; + + for_each_member_device(ca, c, i) + for_each_bucket(g, ca) { + bucket_cmpxchg(g, m, ({ + if (!m.journal_seq_valid || + bucket_needs_journal_commit(m, last_seq_ondisk)) + break; + + m.journal_seq_valid = 0; + })); + } +} + +#define bch2_usage_add(_acc, _stats) \ +do { \ + typeof(_acc) _a = (_acc), _s = (_stats); \ + unsigned i; \ + \ + for (i = 0; i < sizeof(*_a) / sizeof(u64); i++) \ + ((u64 *) (_a))[i] += ((u64 *) (_s))[i]; \ +} while (0) + +#define bch2_usage_read_raw(_stats) \ +({ \ + typeof(*this_cpu_ptr(_stats)) _acc = { 0 }; \ + int cpu; \ + \ + for_each_possible_cpu(cpu) \ + bch2_usage_add(&_acc, per_cpu_ptr((_stats), cpu)); \ + \ + _acc; \ +}) + +#define bch2_usage_read_cached(_c, _cached, _uncached) \ +({ \ + typeof(_cached) _ret; \ + unsigned _seq; \ + \ + do { \ + _seq = read_seqcount_begin(&(_c)->gc_pos_lock); \ + _ret = (_c)->gc_pos.phase == GC_PHASE_DONE \ + ? bch2_usage_read_raw(_uncached) \ + : (_cached); \ + } while (read_seqcount_retry(&(_c)->gc_pos_lock, _seq)); \ + \ + _ret; \ +}) + +struct bch_dev_usage __bch2_dev_usage_read(struct bch_dev *ca) +{ + return bch2_usage_read_raw(ca->usage_percpu); +} + +struct bch_dev_usage bch2_dev_usage_read(struct bch_dev *ca) +{ + return bch2_usage_read_cached(ca->fs, + ca->usage_cached, + ca->usage_percpu); +} + +struct bch_fs_usage +__bch2_fs_usage_read(struct bch_fs *c) +{ + return bch2_usage_read_raw(c->usage_percpu); +} + +struct bch_fs_usage +bch2_fs_usage_read(struct bch_fs *c) +{ + return bch2_usage_read_cached(c, + c->usage_cached, + c->usage_percpu); +} + +static inline int is_meta_bucket(struct bucket_mark m) +{ + return m.data_type != BUCKET_DATA; +} + +static inline int is_dirty_bucket(struct bucket_mark m) +{ + return m.data_type == BUCKET_DATA && !!m.dirty_sectors; +} + +static inline int is_cached_bucket(struct bucket_mark m) +{ + return m.data_type == BUCKET_DATA && + !m.dirty_sectors && !!m.cached_sectors; +} + +static inline enum s_alloc bucket_type(struct bucket_mark m) +{ + return is_meta_bucket(m) ? S_META : S_DIRTY; +} + +static bool bucket_became_unavailable(struct bch_fs *c, + struct bucket_mark old, + struct bucket_mark new) +{ + return is_available_bucket(old) && + !is_available_bucket(new) && + c && c->gc_pos.phase == GC_PHASE_DONE; +} + +void bch2_fs_usage_apply(struct bch_fs *c, + struct bch_fs_usage *stats, + struct disk_reservation *disk_res, + struct gc_pos gc_pos) +{ + s64 added = + stats->s[S_COMPRESSED][S_META] + + stats->s[S_COMPRESSED][S_DIRTY] + + stats->persistent_reserved + + stats->online_reserved; + + /* + * Not allowed to reduce sectors_available except by getting a + * reservation: + */ + BUG_ON(added > (s64) (disk_res ? disk_res->sectors : 0)); + + if (added > 0) { + disk_res->sectors -= added; + stats->online_reserved -= added; + } + + lg_local_lock(&c->usage_lock); + /* online_reserved not subject to gc: */ + this_cpu_ptr(c->usage_percpu)->online_reserved += + stats->online_reserved; + stats->online_reserved = 0; + + if (!gc_will_visit(c, gc_pos)) + bch2_usage_add(this_cpu_ptr(c->usage_percpu), stats); + + bch2_fs_stats_verify(c); + lg_local_unlock(&c->usage_lock); + + memset(stats, 0, sizeof(*stats)); +} + +static void bch2_fs_usage_update(struct bch_fs_usage *fs_usage, + struct bucket_mark old, struct bucket_mark new) +{ + fs_usage->s[S_COMPRESSED][S_CACHED] += + (int) new.cached_sectors - (int) old.cached_sectors; + fs_usage->s[S_COMPRESSED][bucket_type(old)] -= + old.dirty_sectors; + fs_usage->s[S_COMPRESSED][bucket_type(new)] += + new.dirty_sectors; +} + +static void bch2_dev_usage_update(struct bch_dev *ca, + struct bucket_mark old, struct bucket_mark new) +{ + struct bch_fs *c = ca->fs; + struct bch_dev_usage *dev_usage; + + bch2_fs_inconsistent_on(old.data_type && new.data_type && + old.data_type != new.data_type, c, + "different types of metadata in same bucket: %u, %u", + old.data_type, new.data_type); + + preempt_disable(); + dev_usage = this_cpu_ptr(ca->usage_percpu); + + dev_usage->sectors[S_CACHED] += + (int) new.cached_sectors - (int) old.cached_sectors; + + dev_usage->sectors[bucket_type(old)] -= old.dirty_sectors; + dev_usage->sectors[bucket_type(new)] += new.dirty_sectors; + + dev_usage->buckets_alloc += + (int) new.owned_by_allocator - (int) old.owned_by_allocator; + + dev_usage->buckets_meta += is_meta_bucket(new) - is_meta_bucket(old); + dev_usage->buckets_cached += is_cached_bucket(new) - is_cached_bucket(old); + dev_usage->buckets_dirty += is_dirty_bucket(new) - is_dirty_bucket(old); + preempt_enable(); + + if (!is_available_bucket(old) && is_available_bucket(new)) + bch2_wake_allocator(ca); +} + +#define bucket_data_cmpxchg(ca, g, new, expr) \ +({ \ + struct bucket_mark _old = bucket_cmpxchg(g, new, expr); \ + \ + bch2_dev_usage_update(ca, _old, new); \ + _old; \ +}) + +void bch2_invalidate_bucket(struct bch_dev *ca, struct bucket *g) +{ + struct bch_fs_usage stats = { 0 }; + struct bucket_mark old, new; + + old = bucket_data_cmpxchg(ca, g, new, ({ + new.owned_by_allocator = 1; + new.had_metadata = 0; + new.data_type = 0; + new.cached_sectors = 0; + new.dirty_sectors = 0; + new.copygc = 0; + new.gen++; + })); + + /* XXX: we're not actually updating fs usage's cached sectors... */ + bch2_fs_usage_update(&stats, old, new); + + if (!old.owned_by_allocator && old.cached_sectors) + trace_invalidate(ca, g - ca->buckets, + old.cached_sectors); +} + +void bch2_mark_free_bucket(struct bch_dev *ca, struct bucket *g) +{ + struct bucket_mark old, new; + + old = bucket_data_cmpxchg(ca, g, new, ({ + new.owned_by_allocator = 0; + new.data_type = 0; + new.cached_sectors = 0; + new.dirty_sectors = 0; + })); + + BUG_ON(bucket_became_unavailable(ca->fs, old, new)); +} + +void bch2_mark_alloc_bucket(struct bch_dev *ca, struct bucket *g, + bool owned_by_allocator) +{ + struct bucket_mark new; + + bucket_data_cmpxchg(ca, g, new, ({ + new.owned_by_allocator = owned_by_allocator; + })); +} + +void bch2_mark_metadata_bucket(struct bch_dev *ca, struct bucket *g, + enum bucket_data_type type, + bool may_make_unavailable) +{ + struct bucket_mark old, new; + + BUG_ON(!type); + + old = bucket_data_cmpxchg(ca, g, new, ({ + new.data_type = type; + new.had_metadata = 1; + })); + + BUG_ON(old.cached_sectors); + BUG_ON(old.dirty_sectors); + BUG_ON(!may_make_unavailable && + bucket_became_unavailable(ca->fs, old, new)); +} + +#define saturated_add(ca, dst, src, max) \ +do { \ + BUG_ON((int) (dst) + (src) < 0); \ + if ((dst) == (max)) \ + ; \ + else if ((dst) + (src) <= (max)) \ + dst += (src); \ + else { \ + dst = (max); \ + trace_sectors_saturated(ca); \ + } \ +} while (0) + +#if 0 +/* Reverting this until the copygc + compression issue is fixed: */ + +static unsigned __disk_sectors(const union bch_extent_crc *crc, unsigned sectors) +{ + return crc_compression_type(crc) + ? sectors * crc_compressed_size(crc) / crc_uncompressed_size(crc) + : sectors; +} + +static unsigned __compressed_sectors(const union bch_extent_crc *crc, unsigned sectors) +{ + return crc_compression_type(crc) + ? min_t(unsigned, crc_compressed_size(crc), sectors) + : sectors; +} +#else +static unsigned __disk_sectors(const union bch_extent_crc *crc, unsigned sectors) +{ + return sectors; +} + +static unsigned __compressed_sectors(const union bch_extent_crc *crc, unsigned sectors) +{ + return sectors; +} +#endif + +/* + * Checking against gc's position has to be done here, inside the cmpxchg() + * loop, to avoid racing with the start of gc clearing all the marks - GC does + * that with the gc pos seqlock held. + */ +static void bch2_mark_pointer(struct bch_fs *c, + struct bkey_s_c_extent e, + const union bch_extent_crc *crc, + const struct bch_extent_ptr *ptr, + s64 sectors, enum s_alloc type, + bool may_make_unavailable, + struct bch_fs_usage *stats, + bool gc_will_visit, u64 journal_seq) +{ + struct bucket_mark old, new; + unsigned saturated; + struct bch_dev *ca = c->devs[ptr->dev]; + struct bucket *g = ca->buckets + PTR_BUCKET_NR(ca, ptr); + unsigned old_sectors, new_sectors; + int disk_sectors, compressed_sectors; + + if (sectors > 0) { + old_sectors = 0; + new_sectors = sectors; + } else { + old_sectors = e.k->size; + new_sectors = e.k->size + sectors; + } + + disk_sectors = -__disk_sectors(crc, old_sectors) + + __disk_sectors(crc, new_sectors); + compressed_sectors = -__compressed_sectors(crc, old_sectors) + + __compressed_sectors(crc, new_sectors); + + if (gc_will_visit) { + if (journal_seq) + bucket_cmpxchg(g, new, new.journal_seq = journal_seq); + + goto out; + } + + old = bucket_data_cmpxchg(ca, g, new, ({ + saturated = 0; + + /* + * Check this after reading bucket mark to guard against + * the allocator invalidating a bucket after we've already + * checked the gen + */ + if (gen_after(new.gen, ptr->gen)) { + EBUG_ON(type != S_CACHED && + test_bit(JOURNAL_REPLAY_DONE, &c->journal.flags)); + return; + } + + EBUG_ON(type != S_CACHED && + !may_make_unavailable && + is_available_bucket(new) && + test_bit(JOURNAL_REPLAY_DONE, &c->journal.flags)); + + if (type != S_CACHED && + new.dirty_sectors == GC_MAX_SECTORS_USED && + disk_sectors < 0) + saturated = -disk_sectors; + + if (type == S_CACHED) + saturated_add(ca, new.cached_sectors, disk_sectors, + GC_MAX_SECTORS_USED); + else + saturated_add(ca, new.dirty_sectors, disk_sectors, + GC_MAX_SECTORS_USED); + + if (!new.dirty_sectors && + !new.cached_sectors) { + new.data_type = 0; + + if (journal_seq) { + new.journal_seq_valid = 1; + new.journal_seq = journal_seq; + } + } else { + new.data_type = type == S_META + ? BUCKET_BTREE : BUCKET_DATA; + } + + new.had_metadata |= is_meta_bucket(new); + })); + + BUG_ON(!may_make_unavailable && + bucket_became_unavailable(c, old, new)); + + if (saturated && + atomic_long_add_return(saturated, + &ca->saturated_count) >= + ca->free_inc.size << ca->bucket_bits) { + if (c->gc_thread) { + trace_gc_sectors_saturated(c); + wake_up_process(c->gc_thread); + } + } +out: + stats->s[S_COMPRESSED][type] += compressed_sectors; + stats->s[S_UNCOMPRESSED][type] += sectors; +} + +static void bch2_mark_extent(struct bch_fs *c, struct bkey_s_c_extent e, + s64 sectors, bool metadata, + bool may_make_unavailable, + struct bch_fs_usage *stats, + bool gc_will_visit, u64 journal_seq) +{ + const struct bch_extent_ptr *ptr; + const union bch_extent_crc *crc; + enum s_alloc type = metadata ? S_META : S_DIRTY; + + BUG_ON(metadata && bkey_extent_is_cached(e.k)); + BUG_ON(!sectors); + + extent_for_each_ptr_crc(e, ptr, crc) + bch2_mark_pointer(c, e, crc, ptr, sectors, + ptr->cached ? S_CACHED : type, + may_make_unavailable, + stats, gc_will_visit, journal_seq); +} + +static void __bch2_mark_key(struct bch_fs *c, struct bkey_s_c k, + s64 sectors, bool metadata, + bool may_make_unavailable, + struct bch_fs_usage *stats, + bool gc_will_visit, u64 journal_seq) +{ + switch (k.k->type) { + case BCH_EXTENT: + case BCH_EXTENT_CACHED: + bch2_mark_extent(c, bkey_s_c_to_extent(k), sectors, metadata, + may_make_unavailable, stats, + gc_will_visit, journal_seq); + break; + case BCH_RESERVATION: { + struct bkey_s_c_reservation r = bkey_s_c_to_reservation(k); + + stats->persistent_reserved += r.v->nr_replicas * sectors; + break; + } + } +} + +void __bch2_gc_mark_key(struct bch_fs *c, struct bkey_s_c k, + s64 sectors, bool metadata, + struct bch_fs_usage *stats) +{ + __bch2_mark_key(c, k, sectors, metadata, true, stats, false, 0); +} + +void bch2_gc_mark_key(struct bch_fs *c, struct bkey_s_c k, + s64 sectors, bool metadata) +{ + struct bch_fs_usage stats = { 0 }; + + __bch2_gc_mark_key(c, k, sectors, metadata, &stats); + + preempt_disable(); + bch2_usage_add(this_cpu_ptr(c->usage_percpu), &stats); + preempt_enable(); +} + +void bch2_mark_key(struct bch_fs *c, struct bkey_s_c k, + s64 sectors, bool metadata, struct gc_pos gc_pos, + struct bch_fs_usage *stats, u64 journal_seq) +{ + /* + * synchronization w.r.t. GC: + * + * Normally, bucket sector counts/marks are updated on the fly, as + * references are added/removed from the btree, the lists of buckets the + * allocator owns, other metadata buckets, etc. + * + * When GC is in progress and going to mark this reference, we do _not_ + * mark this reference here, to avoid double counting - GC will count it + * when it gets to it. + * + * To know whether we should mark a given reference (GC either isn't + * running, or has already marked references at this position) we + * construct a total order for everything GC walks. Then, we can simply + * compare the position of the reference we're marking - @gc_pos - with + * GC's current position. If GC is going to mark this reference, GC's + * current position will be less than @gc_pos; if GC's current position + * is greater than @gc_pos GC has either already walked this position, + * or isn't running. + * + * To avoid racing with GC's position changing, we have to deal with + * - GC's position being set to GC_POS_MIN when GC starts: + * usage_lock guards against this + * - GC's position overtaking @gc_pos: we guard against this with + * whatever lock protects the data structure the reference lives in + * (e.g. the btree node lock, or the relevant allocator lock). + */ + lg_local_lock(&c->usage_lock); + __bch2_mark_key(c, k, sectors, metadata, false, stats, + gc_will_visit(c, gc_pos), journal_seq); + + bch2_fs_stats_verify(c); + lg_local_unlock(&c->usage_lock); +} + +static u64 __recalc_sectors_available(struct bch_fs *c) +{ + return c->capacity - bch2_fs_sectors_used(c); +} + +/* Used by gc when it's starting: */ +void bch2_recalc_sectors_available(struct bch_fs *c) +{ + int cpu; + + lg_global_lock(&c->usage_lock); + + for_each_possible_cpu(cpu) + per_cpu_ptr(c->usage_percpu, cpu)->available_cache = 0; + + atomic64_set(&c->sectors_available, + __recalc_sectors_available(c)); + + lg_global_unlock(&c->usage_lock); +} + +void bch2_disk_reservation_put(struct bch_fs *c, + struct disk_reservation *res) +{ + if (res->sectors) { + lg_local_lock(&c->usage_lock); + this_cpu_sub(c->usage_percpu->online_reserved, + res->sectors); + + bch2_fs_stats_verify(c); + lg_local_unlock(&c->usage_lock); + + res->sectors = 0; + } +} + +#define SECTORS_CACHE 1024 + +int bch2_disk_reservation_add(struct bch_fs *c, + struct disk_reservation *res, + unsigned sectors, int flags) +{ + struct bch_fs_usage *stats; + u64 old, new, v; + s64 sectors_available; + int ret; + + sectors *= res->nr_replicas; + + lg_local_lock(&c->usage_lock); + stats = this_cpu_ptr(c->usage_percpu); + + if (sectors >= stats->available_cache) + goto out; + + v = atomic64_read(&c->sectors_available); + do { + old = v; + if (old < sectors) { + lg_local_unlock(&c->usage_lock); + goto recalculate; + } + + new = max_t(s64, 0, old - sectors - SECTORS_CACHE); + } while ((v = atomic64_cmpxchg(&c->sectors_available, + old, new)) != old); + + stats->available_cache += old - new; +out: + stats->available_cache -= sectors; + stats->online_reserved += sectors; + res->sectors += sectors; + + bch2_fs_stats_verify(c); + lg_local_unlock(&c->usage_lock); + return 0; + +recalculate: + /* + * GC recalculates sectors_available when it starts, so that hopefully + * we don't normally end up blocking here: + */ + + /* + * Piss fuck, we can be called from extent_insert_fixup() with btree + * locks held: + */ + + if (!(flags & BCH_DISK_RESERVATION_GC_LOCK_HELD)) { + if (!(flags & BCH_DISK_RESERVATION_BTREE_LOCKS_HELD)) + down_read(&c->gc_lock); + else if (!down_read_trylock(&c->gc_lock)) + return -EINTR; + } + lg_global_lock(&c->usage_lock); + + sectors_available = __recalc_sectors_available(c); + + if (sectors <= sectors_available || + (flags & BCH_DISK_RESERVATION_NOFAIL)) { + atomic64_set(&c->sectors_available, + max_t(s64, 0, sectors_available - sectors)); + stats->online_reserved += sectors; + res->sectors += sectors; + ret = 0; + } else { + atomic64_set(&c->sectors_available, sectors_available); + ret = -ENOSPC; + } + + bch2_fs_stats_verify(c); + lg_global_unlock(&c->usage_lock); + if (!(flags & BCH_DISK_RESERVATION_GC_LOCK_HELD)) + up_read(&c->gc_lock); + + return ret; +} + +int bch2_disk_reservation_get(struct bch_fs *c, + struct disk_reservation *res, + unsigned sectors, int flags) +{ + res->sectors = 0; + res->gen = c->capacity_gen; + res->nr_replicas = (flags & BCH_DISK_RESERVATION_METADATA) + ? c->opts.metadata_replicas + : c->opts.data_replicas; + + return bch2_disk_reservation_add(c, res, sectors, flags); +} |