bkey.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0

#include "bcachefs.h"
#include "bkey.h"
#include "bkey_cmp.h"
#include "bkey_methods.h"
#include "bset.h"
#include "util.h"

const struct bkey_format bch2_bkey_format_current = …;

void bch2_bkey_packed_to_binary_text(struct printbuf *out,
				     const struct bkey_format *f,
				     const struct bkey_packed *k)
{ … }

#ifdef CONFIG_BCACHEFS_DEBUG

static void bch2_bkey_pack_verify(const struct bkey_packed *packed,
				  const struct bkey *unpacked,
				  const struct bkey_format *format)
{ … }

#else
static inline void bch2_bkey_pack_verify(const struct bkey_packed *packed,
					const struct bkey *unpacked,
					const struct bkey_format *format) {}
#endif

struct pack_state { … };

__always_inline
static struct pack_state pack_state_init(const struct bkey_format *format,
					 struct bkey_packed *k)
{ … }

__always_inline
static void pack_state_finish(struct pack_state *state,
			      struct bkey_packed *k)
{ … }

struct unpack_state { … };

__always_inline
static struct unpack_state unpack_state_init(const struct bkey_format *format,
					     const struct bkey_packed *k)
{ … }

__always_inline
static u64 get_inc_field(struct unpack_state *state, unsigned field)
{ … }

__always_inline
static void __set_inc_field(struct pack_state *state, unsigned field, u64 v)
{ … }

__always_inline
static bool set_inc_field(struct pack_state *state, unsigned field, u64 v)
{ … }

/*
 * Note: does NOT set out->format (we don't know what it should be here!)
 *
 * Also: doesn't work on extents - it doesn't preserve the invariant that
 * if k is packed bkey_start_pos(k) will successfully pack
 */
static bool bch2_bkey_transform_key(const struct bkey_format *out_f,
				   struct bkey_packed *out,
				   const struct bkey_format *in_f,
				   const struct bkey_packed *in)
{ … }

bool bch2_bkey_transform(const struct bkey_format *out_f,
			struct bkey_packed *out,
			const struct bkey_format *in_f,
			const struct bkey_packed *in)
{ … }

struct bkey __bch2_bkey_unpack_key(const struct bkey_format *format,
			      const struct bkey_packed *in)
{ … }

#ifndef HAVE_BCACHEFS_COMPILED_UNPACK
struct bpos __bkey_unpack_pos(const struct bkey_format *format,
				     const struct bkey_packed *in)
{ … }
#endif

/**
 * bch2_bkey_pack_key -- pack just the key, not the value
 * @out:	packed result
 * @in:		key to pack
 * @format:	format of packed result
 *
 * Returns: true on success, false on failure
 */
bool bch2_bkey_pack_key(struct bkey_packed *out, const struct bkey *in,
			const struct bkey_format *format)
{ … }

/**
 * bch2_bkey_unpack -- unpack the key and the value
 * @b:		btree node of @src key (for packed format)
 * @dst:	unpacked result
 * @src:	packed input
 */
void bch2_bkey_unpack(const struct btree *b, struct bkey_i *dst,
		      const struct bkey_packed *src)
{ … }

/**
 * bch2_bkey_pack -- pack the key and the value
 * @dst:	packed result
 * @src:	unpacked input
 * @format:	format of packed result
 *
 * Returns: true on success, false on failure
 */
bool bch2_bkey_pack(struct bkey_packed *dst, const struct bkey_i *src,
		    const struct bkey_format *format)
{ … }

__always_inline
static bool set_inc_field_lossy(struct pack_state *state, unsigned field, u64 v)
{ … }

#ifdef CONFIG_BCACHEFS_DEBUG
static bool bkey_packed_successor(struct bkey_packed *out,
				  const struct btree *b,
				  struct bkey_packed k)
{ … }

static bool bkey_format_has_too_big_fields(const struct bkey_format *f)
{ … }
#endif

/*
 * Returns a packed key that compares <= in
 *
 * This is used in bset_search_tree(), where we need a packed pos in order to be
 * able to compare against the keys in the auxiliary search tree - and it's
 * legal to use a packed pos that isn't equivalent to the original pos,
 * _provided_ it compares <= to the original pos.
 */
enum bkey_pack_pos_ret bch2_bkey_pack_pos_lossy(struct bkey_packed *out,
					   struct bpos in,
					   const struct btree *b)
{ … }

void bch2_bkey_format_init(struct bkey_format_state *s)
{ … }

void bch2_bkey_format_add_pos(struct bkey_format_state *s, struct bpos p)
{ … }

/*
 * We don't want it to be possible for the packed format to represent fields
 * bigger than a u64... that will cause confusion and issues (like with
 * bkey_packed_successor())
 */
static void set_format_field(struct bkey_format *f, enum bch_bkey_fields i,
			     unsigned bits, u64 offset)
{ … }

struct bkey_format bch2_bkey_format_done(struct bkey_format_state *s)
{ … }

int bch2_bkey_format_invalid(struct bch_fs *c,
			     struct bkey_format *f,
			     enum bch_validate_flags flags,
			     struct printbuf *err)
{ … }

void bch2_bkey_format_to_text(struct printbuf *out, const struct bkey_format *f)
{ … }

/*
 * Most significant differing bit
 * Bits are indexed from 0 - return is [0, nr_key_bits)
 */
__pure
unsigned bch2_bkey_greatest_differing_bit(const struct btree *b,
					  const struct bkey_packed *l_k,
					  const struct bkey_packed *r_k)
{ … }

/*
 * First set bit
 * Bits are indexed from 0 - return is [0, nr_key_bits)
 */
__pure
unsigned bch2_bkey_ffs(const struct btree *b, const struct bkey_packed *k)
{ … }

#ifdef HAVE_BCACHEFS_COMPILED_UNPACK

#define I …
#define I1 …
#define I2 …
#define I3 …
#define I4 …
#define I5 …

static u8 *compile_bkey_field(const struct bkey_format *format, u8 *out,
			      enum bch_bkey_fields field,
			      unsigned dst_offset, unsigned dst_size,
			      bool *eax_zeroed)
{
	unsigned bits = format->bits_per_field[field];
	u64 offset = le64_to_cpu(format->field_offset[field]);
	unsigned i, byte, bit_offset, align, shl, shr;

	if (!bits && !offset) {
		if (!*eax_zeroed) {
			/* xor eax, eax */
			I2(0x31, 0xc0);
		}

		*eax_zeroed = true;
		goto set_field;
	}

	if (!bits) {
		/* just return offset: */

		switch (dst_size) {
		case 8:
			if (offset > S32_MAX) {
				/* mov [rdi + dst_offset], offset */
				I3(0xc7, 0x47, dst_offset);
				memcpy(out, &offset, 4);
				out += 4;

				I3(0xc7, 0x47, dst_offset + 4);
				memcpy(out, (void *) &offset + 4, 4);
				out += 4;
			} else {
				/* mov [rdi + dst_offset], offset */
				/* sign extended */
				I4(0x48, 0xc7, 0x47, dst_offset);
				memcpy(out, &offset, 4);
				out += 4;
			}
			break;
		case 4:
			/* mov [rdi + dst_offset], offset */
			I3(0xc7, 0x47, dst_offset);
			memcpy(out, &offset, 4);
			out += 4;
			break;
		default:
			BUG();
		}

		return out;
	}

	bit_offset = format->key_u64s * 64;
	for (i = 0; i <= field; i++)
		bit_offset -= format->bits_per_field[i];

	byte = bit_offset / 8;
	bit_offset -= byte * 8;

	*eax_zeroed = false;

	if (bit_offset == 0 && bits == 8) {
		/* movzx eax, BYTE PTR [rsi + imm8] */
		I4(0x0f, 0xb6, 0x46, byte);
	} else if (bit_offset == 0 && bits == 16) {
		/* movzx eax, WORD PTR [rsi + imm8] */
		I4(0x0f, 0xb7, 0x46, byte);
	} else if (bit_offset + bits <= 32) {
		align = min(4 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 3);
		byte -= align;
		bit_offset += align * 8;

		BUG_ON(bit_offset + bits > 32);

		/* mov eax, [rsi + imm8] */
		I3(0x8b, 0x46, byte);

		if (bit_offset) {
			/* shr eax, imm8 */
			I3(0xc1, 0xe8, bit_offset);
		}

		if (bit_offset + bits < 32) {
			unsigned mask = ~0U >> (32 - bits);

			/* and eax, imm32 */
			I1(0x25);
			memcpy(out, &mask, 4);
			out += 4;
		}
	} else if (bit_offset + bits <= 64) {
		align = min(8 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 7);
		byte -= align;
		bit_offset += align * 8;

		BUG_ON(bit_offset + bits > 64);

		/* mov rax, [rsi + imm8] */
		I4(0x48, 0x8b, 0x46, byte);

		shl = 64 - bit_offset - bits;
		shr = bit_offset + shl;

		if (shl) {
			/* shl rax, imm8 */
			I4(0x48, 0xc1, 0xe0, shl);
		}

		if (shr) {
			/* shr rax, imm8 */
			I4(0x48, 0xc1, 0xe8, shr);
		}
	} else {
		align = min(4 - DIV_ROUND_UP(bit_offset + bits, 8), byte & 3);
		byte -= align;
		bit_offset += align * 8;

		BUG_ON(bit_offset + bits > 96);

		/* mov rax, [rsi + byte] */
		I4(0x48, 0x8b, 0x46, byte);

		/* mov edx, [rsi + byte + 8] */
		I3(0x8b, 0x56, byte + 8);

		/* bits from next word: */
		shr = bit_offset + bits - 64;
		BUG_ON(shr > bit_offset);

		/* shr rax, bit_offset */
		I4(0x48, 0xc1, 0xe8, shr);

		/* shl rdx, imm8 */
		I4(0x48, 0xc1, 0xe2, 64 - shr);

		/* or rax, rdx */
		I3(0x48, 0x09, 0xd0);

		shr = bit_offset - shr;

		if (shr) {
			/* shr rax, imm8 */
			I4(0x48, 0xc1, 0xe8, shr);
		}
	}

	/* rax += offset: */
	if (offset > S32_MAX) {
		/* mov rdx, imm64 */
		I2(0x48, 0xba);
		memcpy(out, &offset, 8);
		out += 8;
		/* add %rdx, %rax */
		I3(0x48, 0x01, 0xd0);
	} else if (offset + (~0ULL >> (64 - bits)) > U32_MAX) {
		/* add rax, imm32 */
		I2(0x48, 0x05);
		memcpy(out, &offset, 4);
		out += 4;
	} else if (offset) {
		/* add eax, imm32 */
		I1(0x05);
		memcpy(out, &offset, 4);
		out += 4;
	}
set_field:
	switch (dst_size) {
	case 8:
		/* mov [rdi + dst_offset], rax */
		I4(0x48, 0x89, 0x47, dst_offset);
		break;
	case 4:
		/* mov [rdi + dst_offset], eax */
		I3(0x89, 0x47, dst_offset);
		break;
	default:
		BUG();
	}

	return out;
}

int bch2_compile_bkey_format(const struct bkey_format *format, void *_out)
{
	bool eax_zeroed = false;
	u8 *out = _out;

	/*
	 * rdi: dst - unpacked key
	 * rsi: src - packed key
	 */

	/* k->u64s, k->format, k->type */

	/* mov eax, [rsi] */
	I2(0x8b, 0x06);

	/* add eax, BKEY_U64s - format->key_u64s */
	I5(0x05, BKEY_U64s - format->key_u64s, KEY_FORMAT_CURRENT, 0, 0);

	/* and eax, imm32: mask out k->pad: */
	I5(0x25, 0xff, 0xff, 0xff, 0);

	/* mov [rdi], eax */
	I2(0x89, 0x07);

#define x …
	bkey_fields()
#undef x

	/* retq */
	I1(0xc3);

	return (void *) out - _out;
}

#else
#endif

__pure
int __bch2_bkey_cmp_packed_format_checked(const struct bkey_packed *l,
					  const struct bkey_packed *r,
					  const struct btree *b)
{ … }

__pure __flatten
int __bch2_bkey_cmp_left_packed_format_checked(const struct btree *b,
					       const struct bkey_packed *l,
					       const struct bpos *r)
{ … }

__pure __flatten
int bch2_bkey_cmp_packed(const struct btree *b,
			 const struct bkey_packed *l,
			 const struct bkey_packed *r)
{ … }

__pure __flatten
int __bch2_bkey_cmp_left_packed(const struct btree *b,
				const struct bkey_packed *l,
				const struct bpos *r)
{ … }

void bch2_bpos_swab(struct bpos *p)
{ … }

void bch2_bkey_swab_key(const struct bkey_format *_f, struct bkey_packed *k)
{ … }

#ifdef CONFIG_BCACHEFS_DEBUG
void bch2_bkey_pack_test(void)
{ … }
#endif
linux/fs/bcachefs/bkey.c
