md/persistent-data/dm-btree.h

0001 /*
0002  * Copyright (C) 2011 Red Hat, Inc.
0003  *
0004  * This file is released under the GPL.
0005  */
0006 #ifndef _LINUX_DM_BTREE_H
0007 #define _LINUX_DM_BTREE_H
0008
0009 #include "dm-block-manager.h"
0010
0011 struct dm_transaction_manager;
0012
0013 /*----------------------------------------------------------------*/
0014
0015 /*
0016  * Annotations used to check on-disk metadata is handled as little-endian.
0017  */
0018 #ifdef __CHECKER__
0019 #  define __dm_written_to_disk(x) __releases(x)
0020 #  define __dm_reads_from_disk(x) __acquires(x)
0021 #  define __dm_bless_for_disk(x) __acquire(x)
0022 #  define __dm_unbless_for_disk(x) __release(x)
0023 #else
0024 #  define __dm_written_to_disk(x)
0025 #  define __dm_reads_from_disk(x)
0026 #  define __dm_bless_for_disk(x)
0027 #  define __dm_unbless_for_disk(x)
0028 #endif
0029
0030 /*----------------------------------------------------------------*/
0031
0032 /*
0033  * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized
0034  * values.
0035  */
0036
0037 /*
0038  * Information about the values stored within the btree.
0039  */
0040 struct dm_btree_value_type {
0041     void *context;
0042
0043     /*
0044      * The size in bytes of each value.
0045      */
0046     uint32_t size;
0047
0048     /*
0049      * Any of these methods can be safely set to NULL if you do not
0050      * need the corresponding feature.
0051      */
0052
0053     /*
0054      * The btree is making a duplicate of a run of values, for instance
0055      * because previously-shared btree nodes have now diverged.
0056      * @value argument is the new copy that the copy function may modify.
0057      * (Probably it just wants to increment a reference count
0058      * somewhere.) This method is _not_ called for insertion of a new
0059      * value: It is assumed the ref count is already 1.
0060      */
0061     void (*inc)(void *context, const void *value, unsigned count);
0062
0063     /*
0064      * These values are being deleted.  The btree takes care of freeing
0065      * the memory pointed to by @value.  Often the del function just
0066      * needs to decrement a reference counts somewhere.
0067      */
0068     void (*dec)(void *context, const void *value, unsigned count);
0069
0070     /*
0071      * A test for equality between two values.  When a value is
0072      * overwritten with a new one, the old one has the dec method
0073      * called _unless_ the new and old value are deemed equal.
0074      */
0075     int (*equal)(void *context, const void *value1, const void *value2);
0076 };
0077
0078 /*
0079  * The shape and contents of a btree.
0080  */
0081 struct dm_btree_info {
0082     struct dm_transaction_manager *tm;
0083
0084     /*
0085      * Number of nested btrees. (Not the depth of a single tree.)
0086      */
0087     unsigned levels;
0088     struct dm_btree_value_type value_type;
0089 };
0090
0091 /*
0092  * Set up an empty tree.  O(1).
0093  */
0094 int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root);
0095
0096 /*
0097  * Delete a tree.  O(n) - this is the slow one!  It can also block, so
0098  * please don't call it on an IO path.
0099  */
0100 int dm_btree_del(struct dm_btree_info *info, dm_block_t root);
0101
0102 /*
0103  * All the lookup functions return -ENODATA if the key cannot be found.
0104  */
0105
0106 /*
0107  * Tries to find a key that matches exactly.  O(ln(n))
0108  */
0109 int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root,
0110             uint64_t *keys, void *value_le);
0111
0112 /*
0113  * Tries to find the first key where the bottom level key is >= to that
0114  * given.  Useful for skipping empty sections of the btree.
0115  */
0116 int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root,
0117              uint64_t *keys, uint64_t *rkey, void *value_le);
0118
0119 /*
0120  * Insertion (or overwrite an existing value).  O(ln(n))
0121  */
0122 int dm_btree_insert(struct dm_btree_info *info, dm_block_t root,
0123             uint64_t *keys, void *value, dm_block_t *new_root)
0124             __dm_written_to_disk(value);
0125
0126 /*
0127  * A variant of insert that indicates whether it actually inserted or just
0128  * overwrote.  Useful if you're keeping track of the number of entries in a
0129  * tree.
0130  */
0131 int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root,
0132                uint64_t *keys, void *value, dm_block_t *new_root,
0133                int *inserted)
0134                __dm_written_to_disk(value);
0135
0136 /*
0137  * Remove a key if present.  This doesn't remove empty sub trees.  Normally
0138  * subtrees represent a separate entity, like a snapshot map, so this is
0139  * correct behaviour.  O(ln(n)).
0140  */
0141 int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
0142             uint64_t *keys, dm_block_t *new_root);
0143
0144 /*
0145  * Removes a _contiguous_ run of values starting from 'keys' and not
0146  * reaching keys2 (where keys2 is keys with the final key replaced with
0147  * 'end_key').  'end_key' is the one-past-the-end value.  'keys' may be
0148  * altered.
0149  */
0150 int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
0151                uint64_t *keys, uint64_t end_key,
0152                dm_block_t *new_root, unsigned *nr_removed);
0153
0154 /*
0155  * Returns < 0 on failure.  Otherwise the number of key entries that have
0156  * been filled out.  Remember trees can have zero entries, and as such have
0157  * no lowest key.
0158  */
0159 int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root,
0160                  uint64_t *result_keys);
0161
0162 /*
0163  * Returns < 0 on failure.  Otherwise the number of key entries that have
0164  * been filled out.  Remember trees can have zero entries, and as such have
0165  * no highest key.
0166  */
0167 int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root,
0168                   uint64_t *result_keys);
0169
0170 /*
0171  * Iterate through the a btree, calling fn() on each entry.
0172  * It only works for single level trees and is internally recursive, so
0173  * monitor stack usage carefully.
0174  */
0175 int dm_btree_walk(struct dm_btree_info *info, dm_block_t root,
0176           int (*fn)(void *context, uint64_t *keys, void *leaf),
0177           void *context);
0178
0179
0180 /*----------------------------------------------------------------*/
0181
0182 /*
0183  * Cursor API.  This does not follow the rolling lock convention.  Since we
0184  * know the order that values are required we can issue prefetches to speed
0185  * up iteration.  Use on a single level btree only.
0186  */
0187 #define DM_BTREE_CURSOR_MAX_DEPTH 16
0188
0189 struct cursor_node {
0190     struct dm_block *b;
0191     unsigned index;
0192 };
0193
0194 struct dm_btree_cursor {
0195     struct dm_btree_info *info;
0196     dm_block_t root;
0197
0198     bool prefetch_leaves;
0199     unsigned depth;
0200     struct cursor_node nodes[DM_BTREE_CURSOR_MAX_DEPTH];
0201 };
0202
0203 /*
0204  * Creates a fresh cursor.  If prefetch_leaves is set then it is assumed
0205  * the btree contains block indexes that will be prefetched.  The cursor is
0206  * quite large, so you probably don't want to put it on the stack.
0207  */
0208 int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,
0209               bool prefetch_leaves, struct dm_btree_cursor *c);
0210 void dm_btree_cursor_end(struct dm_btree_cursor *c);
0211 int dm_btree_cursor_next(struct dm_btree_cursor *c);
0212 int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count);
0213 int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le);
0214
0215 #endif  /* _LINUX_DM_BTREE_H */