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

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