linux/drivers/md/bcache/extents.c

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2010 Kent Overstreet <[email protected]>
 *
 * Uses a block device as cache for other block devices; optimized for SSDs.
 * All allocation is done in buckets, which should match the erase block size
 * of the device.
 *
 * Buckets containing cached data are kept on a heap sorted by priority;
 * bucket priority is increased on cache hit, and periodically all the buckets
 * on the heap have their priority scaled down. This currently is just used as
 * an LRU but in the future should allow for more intelligent heuristics.
 *
 * Buckets have an 8 bit counter; freeing is accomplished by incrementing the
 * counter. Garbage collection is used to remove stale pointers.
 *
 * Indexing is done via a btree; nodes are not necessarily fully sorted, rather
 * as keys are inserted we only sort the pages that have not yet been written.
 * When garbage collection is run, we resort the entire node.
 *
 * All configuration is done via sysfs; see Documentation/admin-guide/bcache.rst.
 */

#include "bcache.h"
#include "btree.h"
#include "debug.h"
#include "extents.h"
#include "writeback.h"

static void sort_key_next(struct btree_iter *iter,
			  struct btree_iter_set *i)
{ … }

static bool new_bch_key_sort_cmp(const void *l, const void *r, void *args)
{ … }

static bool __ptr_invalid(struct cache_set *c, const struct bkey *k)
{ … }

/* Common among btree and extent ptrs */

static const char *bch_ptr_status(struct cache_set *c, const struct bkey *k)
{ … }

void bch_extent_to_text(char *buf, size_t size, const struct bkey *k)
{ … }

static void bch_bkey_dump(struct btree_keys *keys, const struct bkey *k)
{ … }

/* Btree ptrs */

bool __bch_btree_ptr_invalid(struct cache_set *c, const struct bkey *k)
{ … }

static bool bch_btree_ptr_invalid(struct btree_keys *bk, const struct bkey *k)
{ … }

static bool btree_ptr_bad_expensive(struct btree *b, const struct bkey *k)
{ … }

static bool bch_btree_ptr_bad(struct btree_keys *bk, const struct bkey *k)
{ … }

static bool bch_btree_ptr_insert_fixup(struct btree_keys *bk,
				       struct bkey *insert,
				       struct btree_iter *iter,
				       struct bkey *replace_key)
{ … }

const struct btree_keys_ops bch_btree_keys_ops = …;

/* Extents */

/*
 * Returns true if l > r - unless l == r, in which case returns true if l is
 * older than r.
 *
 * Necessary for btree_sort_fixup() - if there are multiple keys that compare
 * equal in different sets, we have to process them newest to oldest.
 */

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

static inline void new_btree_iter_swap(void *iter1, void *iter2, void __always_unused *args)
{ … }

static struct bkey *bch_extent_sort_fixup(struct btree_iter *iter,
					  struct bkey *tmp)
{ … }

static void bch_subtract_dirty(struct bkey *k,
			   struct cache_set *c,
			   uint64_t offset,
			   int sectors)
{ … }

static bool bch_extent_insert_fixup(struct btree_keys *b,
				    struct bkey *insert,
				    struct btree_iter *iter,
				    struct bkey *replace_key)
{ … }

bool __bch_extent_invalid(struct cache_set *c, const struct bkey *k)
{ … }

static bool bch_extent_invalid(struct btree_keys *bk, const struct bkey *k)
{ … }

static bool bch_extent_bad_expensive(struct btree *b, const struct bkey *k,
				     unsigned int ptr)
{ … }

static bool bch_extent_bad(struct btree_keys *bk, const struct bkey *k)
{ … }

static uint64_t merge_chksums(struct bkey *l, struct bkey *r)
{ … }

static bool bch_extent_merge(struct btree_keys *bk,
			     struct bkey *l,
			     struct bkey *r)
{ … }

const struct btree_keys_ops bch_extent_keys_ops = …;