drivers/md/persistent-data/dm-btree-internal.h

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