217 lines · c
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_H8#define _LINUX_DM_BTREE_H9 10#include "dm-block-manager.h"11 12struct 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#else25# 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#endif30 31/*----------------------------------------------------------------*/32 33/*34 * Manipulates hierarchical B+ trees with 64-bit keys and arbitrary-sized35 * values.36 */37 38/*39 * Information about the values stored within the btree.40 */41struct 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 not51 * need the corresponding feature.52 */53 54 /*55 * The btree is making a duplicate of a run of values, for instance56 * 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 count59 * somewhere.) This method is _not_ called for insertion of a new60 * 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 freeing66 * the memory pointed to by @value. Often the del function just67 * 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 is73 * overwritten with a new one, the old one has the dec method74 * 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 */82struct 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 */95int 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, so99 * please don't call it on an IO path.100 */101int 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 */110int 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 that115 * given. Useful for skipping empty sections of the btree.116 */117int 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 */123int 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 just129 * overwrote. Useful if you're keeping track of the number of entries in a130 * tree.131 */132int 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. Normally139 * subtrees represent a separate entity, like a snapshot map, so this is140 * correct behaviour. O(ln(n)).141 */142int 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 not147 * reaching keys2 (where keys2 is keys with the final key replaced with148 * 'end_key'). 'end_key' is the one-past-the-end value. 'keys' may be149 * altered.150 */151int 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 have157 * been filled out. Remember trees can have zero entries, and as such have158 * no lowest key.159 */160int 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 have165 * been filled out. Remember trees can have zero entries, and as such have166 * no highest key.167 */168int 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, so174 * monitor stack usage carefully.175 */176int 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 we185 * know the order that values are required we can issue prefetches to speed186 * up iteration. Use on a single level btree only.187 */188#define DM_BTREE_CURSOR_MAX_DEPTH 16189 190struct cursor_node {191 struct dm_block *b;192 unsigned int index;193};194 195struct 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 assumed206 * the btree contains block indexes that will be prefetched. The cursor is207 * quite large, so you probably don't want to put it on the stack.208 */209int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root,210 bool prefetch_leaves, struct dm_btree_cursor *c);211void dm_btree_cursor_end(struct dm_btree_cursor *c);212int dm_btree_cursor_next(struct dm_btree_cursor *c);213int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count);214int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le);215 216#endif /* _LINUX_DM_BTREE_H */217