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

   1 /*
   2  * Copyright (C) 2011 Red Hat, Inc. All rights reserved.
   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 node {
  40         struct node_header header;
  41         __le64 keys[0];
  42 } __packed;
  43
  44
  45 void inc_children(struct dm_transaction_manager *tm, struct 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 struct node *ro_node(struct ro_spine *s);
  68
  69 struct shadow_spine {
  70         struct dm_btree_info *info;
  71
  72         int count;
  73         struct dm_block *nodes[2];
  74
  75         dm_block_t root;
  76 };
  77
  78 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
  79 int exit_shadow_spine(struct shadow_spine *s);
  80
  81 int shadow_step(struct shadow_spine *s, dm_block_t b,
  82                 struct dm_btree_value_type *vt, int *inc);
  83
  84 /*
  85  * The spine must have at least one entry before calling this.
  86  */
  87 struct dm_block *shadow_current(struct shadow_spine *s);
  88
  89 /*
  90  * The spine must have at least two entries before calling this.
  91  */
  92 struct dm_block *shadow_parent(struct shadow_spine *s);
  93
  94 int shadow_has_parent(struct shadow_spine *s);
  95
  96 int shadow_root(struct shadow_spine *s);
  97
  98 /*
  99  * Some inlines.
 100  */
 101 static inline __le64 *key_ptr(struct node *n, uint32_t index)
 102 {
 103         return n->keys + index;
 104 }
 105
 106 static inline void *value_base(struct node *n)
 107 {
 108         return &n->keys[le32_to_cpu(n->header.max_entries)];
 109 }
 110
 111 static inline void *value_ptr(struct node *n, uint32_t index, size_t value_size)
 112 {
 113         return value_base(n) + (value_size * index);
 114 }
 115
 116 /*
 117  * Assumes the values are suitably-aligned and converts to core format.
 118  */
 119 static inline uint64_t value64(struct node *n, uint32_t index)
 120 {
 121         __le64 *values_le = value_base(n);
 122
 123         return le64_to_cpu(values_le[index]);
 124 }
 125
 126 /*
 127  * Searching for a key within a single node.
 128  */
 129 int lower_bound(struct node *n, uint64_t key);
 130
 131 extern struct dm_block_validator btree_node_validator;
 132
 133 #endif  /* DM_BTREE_INTERNAL_H */