^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) * Copyright (C) 2011 Red Hat, Inc.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) *
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4) * This file is released under the GPL.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) #ifndef DM_BTREE_INTERNAL_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) #define DM_BTREE_INTERNAL_H
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) #include "dm-btree.h"
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12) /*----------------------------------------------------------------*/
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15) * We'll need 2 accessor functions for n->csum and n->blocknr
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) * to support dm-btree-spine.c in that case.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) enum node_flags {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) INTERNAL_NODE = 1,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) LEAF_NODE = 1 << 1
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25) * Every btree node begins with this structure. Make sure it's a multiple
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) struct node_header {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) __le32 csum;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) __le32 flags;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31) __le64 blocknr; /* Block this node is supposed to live in. */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) __le32 nr_entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) __le32 max_entries;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) __le32 value_size;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) __le32 padding;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) } __attribute__((packed, aligned(8)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39) struct btree_node {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) struct node_header header;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) __le64 keys[];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) } __attribute__((packed, aligned(8)));
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) * Locks a block using the btree node validator.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48) int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) struct dm_block **result);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51) void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) struct dm_btree_value_type *vt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) int new_block(struct dm_btree_info *info, struct dm_block **result);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) void unlock_block(struct dm_btree_info *info, struct dm_block *b);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) * Spines keep track of the rolling locks. There are 2 variants, read-only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) * and one that uses shadowing. These are separate structs to allow the
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) * type checker to spot misuse, for example accidentally calling read_lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61) * on a shadow spine.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) struct ro_spine {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64) struct dm_btree_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) int count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) struct dm_block *nodes[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) void exit_ro_spine(struct ro_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) int ro_step(struct ro_spine *s, dm_block_t new_child);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) void ro_pop(struct ro_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74) struct btree_node *ro_node(struct ro_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) struct shadow_spine {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) struct dm_btree_info *info;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 78)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 79) int count;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 80) struct dm_block *nodes[2];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 81)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 82) dm_block_t root;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 83) };
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 84)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 85) void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 86) int exit_shadow_spine(struct shadow_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 87)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 88) int shadow_step(struct shadow_spine *s, dm_block_t b,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 89) struct dm_btree_value_type *vt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 90)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 91) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 92) * The spine must have at least one entry before calling this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 93) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 94) struct dm_block *shadow_current(struct shadow_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 95)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 96) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 97) * The spine must have at least two entries before calling this.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 98) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 99) struct dm_block *shadow_parent(struct shadow_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 100)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 101) int shadow_has_parent(struct shadow_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 102)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 103) int shadow_root(struct shadow_spine *s);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 104)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 105) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 106) * Some inlines.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 107) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 108) static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 109) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 110) return n->keys + index;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 111) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 112)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 113) static inline void *value_base(struct btree_node *n)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 114) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 115) return &n->keys[le32_to_cpu(n->header.max_entries)];
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 116) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 117)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 118) static inline void *value_ptr(struct btree_node *n, uint32_t index)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 119) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 120) uint32_t value_size = le32_to_cpu(n->header.value_size);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 121) return value_base(n) + (value_size * index);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 122) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 123)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 124) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 125) * Assumes the values are suitably-aligned and converts to core format.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 126) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 127) static inline uint64_t value64(struct btree_node *n, uint32_t index)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 128) {
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 129) __le64 *values_le = value_base(n);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 130)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 131) return le64_to_cpu(values_le[index]);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 132) }
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 133)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 134) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 135) * Searching for a key within a single node.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 136) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 137) int lower_bound(struct btree_node *n, uint64_t key);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 138)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 139) extern struct dm_block_validator btree_node_validator;
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 140)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 141) /*
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 142) * Value type for upper levels of multi-level btrees.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 143) */
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 144) extern void init_le64_type(struct dm_transaction_manager *tm,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 145) struct dm_btree_value_type *vt);
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 146)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 147) #endif /* DM_BTREE_INTERNAL_H */
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags