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 } __packed;
  38
  39 struct btree_node {
  40         struct node_header header;
  41         __le64 keys[0];
  42 } __packed;
  43
  44
  45 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
  46                   struct dm_btree_value_type *vt);
  47
  48 int new_block(struct dm_btree_info *info, struct dm_block **result);
  49 int unlock_block(struct dm_btree_info *info, struct dm_block *b);
  50
  51 /*
  52  * Spines keep track of the rolling locks.  There are 2 variants, read-only
  53  * and one that uses shadowing.  These are separate structs to allow the
  54  * type checker to spot misuse, for example accidentally calling read_lock
  55  * on a shadow spine.
  56  */
  57 struct ro_spine {
  58         struct dm_btree_info *info;
  59
  60         int count;
  61         struct dm_block *nodes[2];
  62 };
  63
  64 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
  65 int exit_ro_spine(struct ro_spine *s);
  66 int ro_step(struct ro_spine *s, dm_block_t new_child);
  67 void ro_pop(struct ro_spine *s);
  68 struct btree_node *ro_node(struct ro_spine *s);
  69
  70 struct shadow_spine {
  71         struct dm_btree_info *info;
  72
  73         int count;
  74         struct dm_block *nodes[2];
  75
  76         dm_block_t root;
  77 };
  78
  79 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
  80 int exit_shadow_spine(struct shadow_spine *s);
  81
  82 int shadow_step(struct shadow_spine *s, dm_block_t b,
  83                 struct dm_btree_value_type *vt);
  84
  85 /*
  86  * The spine must have at least one entry before calling this.
  87  */
  88 struct dm_block *shadow_current(struct shadow_spine *s);
  89
  90 /*
  91  * The spine must have at least two entries before calling this.
  92  */
  93 struct dm_block *shadow_parent(struct shadow_spine *s);
  94
  95 int shadow_has_parent(struct shadow_spine *s);
  96
  97 int shadow_root(struct shadow_spine *s);
  98
  99 /*
 100  * Some inlines.
 101  */
 102 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
 103 {
 104         return n->keys + index;
 105 }
 106
 107 static inline void *value_base(struct btree_node *n)
 108 {
 109         return &n->keys[le32_to_cpu(n->header.max_entries)];
 110 }
 111
 112 static inline void *value_ptr(struct btree_node *n, uint32_t index)
 113 {
 114         uint32_t value_size = le32_to_cpu(n->header.value_size);
 115         return value_base(n) + (value_size * index);
 116 }
 117
 118 /*
 119  * Assumes the values are suitably-aligned and converts to core format.
 120  */
 121 static inline uint64_t value64(struct btree_node *n, uint32_t index)
 122 {
 123         __le64 *values_le = value_base(n);
 124
 125         return le64_to_cpu(values_le[index]);
 126 }
 127
 128 /*
 129  * Searching for a key within a single node.
 130  */
 131 int lower_bound(struct btree_node *n, uint64_t key);
 132
 133 extern struct dm_block_validator btree_node_validator;
 134
 135 #endif  /* DM_BTREE_INTERNAL_H */