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

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