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} __packed;
  38
  39struct btree_node {
  40        struct node_header header;
  41        __le64 keys[0];
  42} __packed;
  43
  44
  45void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
  46                  struct dm_btree_value_type *vt);
  47
  48int new_block(struct dm_btree_info *info, struct dm_block **result);
  49int 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 */
  57struct ro_spine {
  58        struct dm_btree_info *info;
  59
  60        int count;
  61        struct dm_block *nodes[2];
  62};
  63
  64void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
  65int exit_ro_spine(struct ro_spine *s);
  66int ro_step(struct ro_spine *s, dm_block_t new_child);
  67void ro_pop(struct ro_spine *s);
  68struct btree_node *ro_node(struct ro_spine *s);
  69
  70struct 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
  79void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
  80int exit_shadow_spine(struct shadow_spine *s);
  81
  82int 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 */
  88struct dm_block *shadow_current(struct shadow_spine *s);
  89
  90/*
  91 * The spine must have at least two entries before calling this.
  92 */
  93struct dm_block *shadow_parent(struct shadow_spine *s);
  94
  95int shadow_has_parent(struct shadow_spine *s);
  96
  97int shadow_root(struct shadow_spine *s);
  98
  99/*
 100 * Some inlines.
 101 */
 102static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
 103{
 104        return n->keys + index;
 105}
 106
 107static inline void *value_base(struct btree_node *n)
 108{
 109        return &n->keys[le32_to_cpu(n->header.max_entries)];
 110}
 111
 112static 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 */
 121static 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 */
 131int lower_bound(struct btree_node *n, uint64_t key);
 132
 133extern struct dm_block_validator btree_node_validator;
 134
 135#endif  /* DM_BTREE_INTERNAL_H */
 136