LXR linux/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
  11struct 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 */
  40struct 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 */
  81struct 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 */
  94int 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 */
 100int 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 */
 109int 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 */
 116int 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 */
 122int 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 */
 131int 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 */
 141int 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 */
 150int 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 */
 159int 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 */
 167int 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 */
 175int 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#endif  /* _LINUX_DM_BTREE_H */
 180