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

   1 /*
   2  * Copyright (C) 2011 Red Hat, Inc.
   3  *
   4  * This file is released under the GPL.
   5  */
   6 #ifndef _LINUX_DM_BTREE_H
   7 #define _LINUX_DM_BTREE_H
   8
   9 #include "dm-block-manager.h"
  10
  11 struct dm_transaction_manager;
  12
  13 /*----------------------------------------------------------------*/
  14
  15 /*
  16  * Annotations used to check on-disk metadata is handled as little-endian.
  17  */
  18 #ifdef __CHECKER__
  19 #  define __dm_written_to_disk(x) __releases(x)
  20 #  define __dm_reads_from_disk(x) __acquires(x)
  21 #  define __dm_bless_for_disk(x) __acquire(x)
  22 #  define __dm_unbless_for_disk(x) __release(x)
  23 #else
  24 #  define __dm_written_to_disk(x)
  25 #  define __dm_reads_from_disk(x)
  26 #  define __dm_bless_for_disk(x)
  27 #  define __dm_unbless_for_disk(x)
  28 #endif
  29
  30 /*----------------------------------------------------------------*/
  31
  32 /*
  33  * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
  34  * values.
  35  */
  36
  37 /*
  38  * Information about the values stored within the btree.
  39  */
  40 struct dm_btree_value_type {
  41         void *context;
  42
  43         /*
  44          * The size in bytes of each value.
  45          */
  46         uint32_t size;
  47
  48         /*
  49          * Any of these methods can be safely set to NULL if you do not
  50          * need the corresponding feature.
  51          */
  52
  53         /*
  54          * The btree is making a duplicate of the value, for instance
  55          * because previously-shared btree nodes have now diverged.
  56          * @value argument is the new copy that the copy function may modify.
  57          * (Probably it just wants to increment a reference count
  58          * somewhere.) This method is _not_ called for insertion of a new
  59          * value: It is assumed the ref count is already 1.
  60          */
  61         void (*inc)(void *context, const void *value);
  62
  63         /*
  64          * This value is being deleted.  The btree takes care of freeing
  65          * the memory pointed to by @value.  Often the del function just
  66          * needs to decrement a reference count somewhere.
  67          */
  68         void (*dec)(void *context, const void *value);
  69
  70         /*
  71          * A test for equality between two values.  When a value is
  72          * overwritten with a new one, the old one has the dec method
  73          * called _unless_ the new and old value are deemed equal.
  74          */
  75         int (*equal)(void *context, const void *value1, const void *value2);
  76 };
  77
  78 /*
  79  * The shape and contents of a btree.
  80  */
  81 struct dm_btree_info {
  82         struct dm_transaction_manager *tm;
  83
  84         /*
  85          * Number of nested btrees. (Not the depth of a single tree.)
  86          */
  87         unsigned levels;
  88         struct dm_btree_value_type value_type;
  89 };
  90
  91 /*
  92  * Set up an empty tree.  O(1).
  93  */
  94 int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root);
  95
  96 /*
  97  * Delete a tree.  O(n) - this is the slow one!  It can also block, so
  98  * please don't call it on an IO path.
  99  */
 100 int dm_btree_del(struct dm_btree_info *info, dm_block_t root);
 101
 102 /*
 103  * All the lookup functions return -ENODATA if the key cannot be found.
 104  */
 105
 106 /*
 107  * Tries to find a key that matches exactly.  O(ln(n))
 108  */
 109 int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
 110                     uint64_t *keys, void *value_le);
 111
 112 /*
 113  * Tries to find the first key where the bottom level key is >= to that
 114  * given.  Useful for skipping empty sections of the btree.
 115  */
 116 int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
 117                          uint64_t *keys, uint64_t *rkey, void *value_le);
 118
 119 /*
 120  * Insertion (or overwrite an existing value).  O(ln(n))
 121  */
 122 int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
 123                     uint64_t *keys, void *value, dm_block_t *new_root)
 124                     __dm_written_to_disk(value);
 125
 126 /*
 127  * A variant of insert that indicates whether it actually inserted or just
 128  * overwrote.  Useful if you're keeping track of the number of entries in a
 129  * tree.
 130  */
 131 int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
 132                            uint64_t *keys, void *value, dm_block_t *new_root,
 133                            int *inserted)
 134                            __dm_written_to_disk(value);
 135
 136 /*
 137  * Remove a key if present.  This doesn't remove empty sub trees.  Normally
 138  * subtrees represent a separate entity, like a snapshot map, so this is
 139  * correct behaviour.  O(ln(n)).
 140  */
 141 int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
 142                     uint64_t *keys, dm_block_t *new_root);
 143
 144 /*
 145  * Removes a _contiguous_ run of values starting from 'keys' and not
 146  * reaching keys2 (where keys2 is keys with the final key replaced with
 147  * 'end_key').  'end_key' is the one-past-the-end value.  'keys' may be
 148  * altered.
 149  */
 150 int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
 151                            uint64_t *keys, uint64_t end_key,
 152                            dm_block_t *new_root, unsigned *nr_removed);
 153
 154 /*
 155  * Returns < 0 on failure.  Otherwise the number of key entries that have
 156  * been filled out.  Remember trees can have zero entries, and as such have
 157  * no lowest key.
 158  */
 159 int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
 160                              uint64_t *result_keys);
 161
 162 /*
 163  * Returns < 0 on failure.  Otherwise the number of key entries that have
 164  * been filled out.  Remember trees can have zero entries, and as such have
 165  * no highest key.
 166  */
 167 int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
 168                               uint64_t *result_keys);
 169
 170 /*
 171  * Iterate through the a btree, calling fn() on each entry.
 172  * It only works for single level trees and is internally recursive, so
 173  * monitor stack usage carefully.
 174  */
 175 int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
 176                   int (*fn)(void *context, uint64_t *keys, void *leaf),
 177                   void *context);
 178
 179
 180 /*----------------------------------------------------------------*/
 181
 182 /*
 183  * Cursor API.  This does not follow the rolling lock convention.  Since we
 184  * know the order that values are required we can issue prefetches to speed
 185  * up iteration.  Use on a single level btree only.
 186  */
 187 #define DM_BTREE_CURSOR_MAX_DEPTH 16
 188
 189 struct cursor_node {
 190         struct dm_block *b;
 191         unsigned index;
 192 };
 193
 194 struct dm_btree_cursor {
 195         struct dm_btree_info *info;
 196         dm_block_t root;
 197
 198         bool prefetch_leaves;
 199         unsigned depth;
 200         struct cursor_node nodes[DM_BTREE_CURSOR_MAX_DEPTH];
 201 };
 202
 203 /*
 204  * Creates a fresh cursor.  If prefetch_leaves is set then it is assumed
 205  * the btree contains block indexes that will be prefetched.  The cursor is
 206  * quite large, so you probably don't want to put it on the stack.
 207  */
 208 int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,
 209                           bool prefetch_leaves, struct dm_btree_cursor *c);
 210 void dm_btree_cursor_end(struct dm_btree_cursor *c);
 211 int dm_btree_cursor_next(struct dm_btree_cursor *c);
 212 int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count);
 213 int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le);
 214
 215 #endif  /* _LINUX_DM_BTREE_H */