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

0001 /*
0002  * Copyright (C) 2011 Red Hat, Inc.
0003  *
0004  * This file is released under the GPL.
0005  */
0006
0007 #ifndef DM_BTREE_INTERNAL_H
0008 #define DM_BTREE_INTERNAL_H
0009
0010 #include "dm-btree.h"
0011
0012 /*----------------------------------------------------------------*/
0013
0014 /*
0015  * We'll need 2 accessor functions for n->csum and n->blocknr
0016  * to support dm-btree-spine.c in that case.
0017  */
0018
0019 enum node_flags {
0020     INTERNAL_NODE = 1,
0021     LEAF_NODE = 1 << 1
0022 };
0023
0024 /*
0025  * Every btree node begins with this structure.  Make sure it's a multiple
0026  * of 8-bytes in size, otherwise the 64bit keys will be mis-aligned.
0027  */
0028 struct node_header {
0029     __le32 csum;
0030     __le32 flags;
0031     __le64 blocknr; /* Block this node is supposed to live in. */
0032
0033     __le32 nr_entries;
0034     __le32 max_entries;
0035     __le32 value_size;
0036     __le32 padding;
0037 } __attribute__((packed, aligned(8)));
0038
0039 struct btree_node {
0040     struct node_header header;
0041     __le64 keys[];
0042 } __attribute__((packed, aligned(8)));
0043
0044
0045 /*
0046  * Locks a block using the btree node validator.
0047  */
0048 int bn_read_lock(struct dm_btree_info *info, dm_block_t b,
0049          struct dm_block **result);
0050
0051 void inc_children(struct dm_transaction_manager *tm, struct btree_node *n,
0052           struct dm_btree_value_type *vt);
0053
0054 int new_block(struct dm_btree_info *info, struct dm_block **result);
0055 void unlock_block(struct dm_btree_info *info, struct dm_block *b);
0056
0057 /*
0058  * Spines keep track of the rolling locks.  There are 2 variants, read-only
0059  * and one that uses shadowing.  These are separate structs to allow the
0060  * type checker to spot misuse, for example accidentally calling read_lock
0061  * on a shadow spine.
0062  */
0063 struct ro_spine {
0064     struct dm_btree_info *info;
0065
0066     int count;
0067     struct dm_block *nodes[2];
0068 };
0069
0070 void init_ro_spine(struct ro_spine *s, struct dm_btree_info *info);
0071 void exit_ro_spine(struct ro_spine *s);
0072 int ro_step(struct ro_spine *s, dm_block_t new_child);
0073 void ro_pop(struct ro_spine *s);
0074 struct btree_node *ro_node(struct ro_spine *s);
0075
0076 struct shadow_spine {
0077     struct dm_btree_info *info;
0078
0079     int count;
0080     struct dm_block *nodes[2];
0081
0082     dm_block_t root;
0083 };
0084
0085 void init_shadow_spine(struct shadow_spine *s, struct dm_btree_info *info);
0086 void exit_shadow_spine(struct shadow_spine *s);
0087
0088 int shadow_step(struct shadow_spine *s, dm_block_t b,
0089         struct dm_btree_value_type *vt);
0090
0091 /*
0092  * The spine must have at least one entry before calling this.
0093  */
0094 struct dm_block *shadow_current(struct shadow_spine *s);
0095
0096 /*
0097  * The spine must have at least two entries before calling this.
0098  */
0099 struct dm_block *shadow_parent(struct shadow_spine *s);
0100
0101 int shadow_has_parent(struct shadow_spine *s);
0102
0103 dm_block_t shadow_root(struct shadow_spine *s);
0104
0105 /*
0106  * Some inlines.
0107  */
0108 static inline __le64 *key_ptr(struct btree_node *n, uint32_t index)
0109 {
0110     return n->keys + index;
0111 }
0112
0113 static inline void *value_base(struct btree_node *n)
0114 {
0115     return &n->keys[le32_to_cpu(n->header.max_entries)];
0116 }
0117
0118 static inline void *value_ptr(struct btree_node *n, uint32_t index)
0119 {
0120     uint32_t value_size = le32_to_cpu(n->header.value_size);
0121     return value_base(n) + (value_size * index);
0122 }
0123
0124 /*
0125  * Assumes the values are suitably-aligned and converts to core format.
0126  */
0127 static inline uint64_t value64(struct btree_node *n, uint32_t index)
0128 {
0129     __le64 *values_le = value_base(n);
0130
0131     return le64_to_cpu(values_le[index]);
0132 }
0133
0134 /*
0135  * Searching for a key within a single node.
0136  */
0137 int lower_bound(struct btree_node *n, uint64_t key);
0138
0139 extern struct dm_block_validator btree_node_validator;
0140
0141 /*
0142  * Value type for upper levels of multi-level btrees.
0143  */
0144 extern void init_le64_type(struct dm_transaction_manager *tm,
0145                struct dm_btree_value_type *vt);
0146
0147 /*
0148  * This returns a shadowed btree leaf that you may modify.  In practise
0149  * this means overwrites only, since an insert could cause a node to
0150  * be split.  Useful if you need access to the old value to calculate the
0151  * new one.
0152  *
0153  * This only works with single level btrees.  The given key must be present in
0154  * the tree, otherwise -EINVAL will be returned.
0155  */
0156 int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root,
0157                  uint64_t key, int *index,
0158                  dm_block_t *new_root, struct dm_block **leaf);
0159
0160 #endif  /* DM_BTREE_INTERNAL_H */