LXR linux/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
  19enum 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 */
  28struct 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
  39struct btree_node {
  40        struct node_header header;
  41        __le64 keys[];
  42} __attribute__((packed, aligned(8)));
  43
  44
  45/*
  46 * Locks a block using the btree node validator.
  47 */
  48int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
  49                 struct dm_block **result);
  50
  51void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
  52                  struct dm_btree_value_type *vt);
  53
  54int new_block(struct dm_btree_info *info, struct dm_block **result);
  55void 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 */
  63struct ro_spine {
  64        struct dm_btree_info *info;
  65
  66        int count;
  67        struct dm_block *nodes[2];
  68};
  69
  70void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
  71void exit_ro_spine(struct ro_spine *s);
  72int ro_step(struct ro_spine *s, dm_block_t new_child);
  73void ro_pop(struct ro_spine *s);
  74struct btree_node *ro_node(struct ro_spine *s);
  75
  76struct 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
  85void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
  86void exit_shadow_spine(struct shadow_spine *s);
  87
  88int 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 */
  94struct dm_block *shadow_current(struct shadow_spine *s);
  95
  96/*
  97 * The spine must have at least two entries before calling this.
  98 */
  99struct dm_block *shadow_parent(struct shadow_spine *s);
 100
 101int shadow_has_parent(struct shadow_spine *s);
 102
 103dm_block_t shadow_root(struct shadow_spine *s);
 104
 105/*
 106 * Some inlines.
 107 */
 108static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
 109{
 110        return n->keys + index;
 111}
 112
 113static inline void *value_base(struct btree_node *n)
 114{
 115        return &n->keys[le32_to_cpu(n->header.max_entries)];
 116}
 117
 118static 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 */
 127static 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 */
 137int lower_bound(struct btree_node *n, uint64_t key);
 138
 139extern struct dm_block_validator btree_node_validator;
 140
 141/*
 142 * Value type for upper levels of multi-level btrees.
 143 */
 144extern void init_le64_type(struct dm_transaction_manager *tm,
 145                           struct dm_btree_value_type *vt);
 146
 147/*
 148 * This returns a shadowed btree leaf that you may modify.  In practise
 149 * this means overwrites only, since an insert could cause a node to
 150 * be split.  Useful if you need access to the old value to calculate the
 151 * new one.
 152 *
 153 * This only works with single level btrees.  The given key must be present in
 154 * the tree, otherwise -EINVAL will be returned.
 155 */
 156int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root,
 157                             uint64_t key, int *index,
 158                             dm_block_t *new_root, struct dm_block **leaf);
 159
 160#endif  /* DM_BTREE_INTERNAL_H */
 161