// SPDX-License-Identifier: GPL-2.0-only /* * Copyright (C) 2011 Red Hat, Inc. * * This file is released under the GPL. */ #include "dm-btree-internal.h" #include "dm-space-map.h" #include "dm-transaction-manager.h" #include <linux/export.h> #include <linux/device-mapper.h> #define DM_MSG_PREFIX … /* *-------------------------------------------------------------- * Array manipulation *-------------------------------------------------------------- */ static void memcpy_disk(void *dest, const void *src, size_t len) __dm_written_to_disk(src) { … } static void array_insert(void *base, size_t elt_size, unsigned int nr_elts, unsigned int index, void *elt) __dm_written_to_disk(elt) { … } /*----------------------------------------------------------------*/ /* makes the assumption that no two keys are the same. */ static int bsearch(struct btree_node *n, uint64_t key, int want_hi) { … } int lower_bound(struct btree_node *n, uint64_t key) { … } static int upper_bound(struct btree_node *n, uint64_t key) { … } void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, struct dm_btree_value_type *vt) { … } static int insert_at(size_t value_size, struct btree_node *node, unsigned int index, uint64_t key, void *value) __dm_written_to_disk(value) { … } /*----------------------------------------------------------------*/ /* * We want 3n entries (for some n). This works more nicely for repeated * insert remove loops than (2n + 1). */ static uint32_t calc_max_entries(size_t value_size, size_t block_size) { … } int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ /* * Deletion uses a recursive algorithm, since we have limited stack space * we explicitly manage our own stack on the heap. */ #define MAX_SPINE_DEPTH … struct frame { … }; struct del_stack { … }; static int top_frame(struct del_stack *s, struct frame **f) { … } static int unprocessed_frames(struct del_stack *s) { … } static void prefetch_children(struct del_stack *s, struct frame *f) { … } static bool is_internal_level(struct dm_btree_info *info, struct frame *f) { … } static int push_frame(struct del_stack *s, dm_block_t b, unsigned int level) { … } static void pop_frame(struct del_stack *s) { … } static void unlock_all_frames(struct del_stack *s) { … } int dm_btree_del(struct dm_btree_info *info, dm_block_t root) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ static int btree_lookup_raw(struct ro_spine *s, dm_block_t block, uint64_t key, int (*search_fn)(struct btree_node *, uint64_t), uint64_t *result_key, void *v, size_t value_size) { … } int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value_le) { … } EXPORT_SYMBOL_GPL(…); static int dm_btree_lookup_next_single(struct dm_btree_info *info, dm_block_t root, uint64_t key, uint64_t *rkey, void *value_le) { … } int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, uint64_t *rkey, void *value_le) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ /* * Copies entries from one region of a btree node to another. The regions * must not overlap. */ static void copy_entries(struct btree_node *dest, unsigned int dest_offset, struct btree_node *src, unsigned int src_offset, unsigned int count) { … } /* * Moves entries from one region fo a btree node to another. The regions * may overlap. */ static void move_entries(struct btree_node *dest, unsigned int dest_offset, struct btree_node *src, unsigned int src_offset, unsigned int count) { … } /* * Erases the first 'count' entries of a btree node, shifting following * entries down into their place. */ static void shift_down(struct btree_node *n, unsigned int count) { … } /* * Moves entries in a btree node up 'count' places, making space for * new entries at the start of the node. */ static void shift_up(struct btree_node *n, unsigned int count) { … } /* * Redistributes entries between two btree nodes to make them * have similar numbers of entries. */ static void redistribute2(struct btree_node *left, struct btree_node *right) { … } /* * Redistribute entries between three nodes. Assumes the central * node is empty. */ static void redistribute3(struct btree_node *left, struct btree_node *center, struct btree_node *right) { … } /* * Splits a node by creating a sibling node and shifting half the nodes * contents across. Assumes there is a parent node, and it has room for * another child. * * Before: * +--------+ * | Parent | * +--------+ * | * v * +----------+ * | A ++++++ | * +----------+ * * * After: * +--------+ * | Parent | * +--------+ * | | * v +------+ * +---------+ | * | A* +++ | v * +---------+ +-------+ * | B +++ | * +-------+ * * Where A* is a shadow of A. */ static int split_one_into_two(struct shadow_spine *s, unsigned int parent_index, struct dm_btree_value_type *vt, uint64_t key) { … } /* * We often need to modify a sibling node. This function shadows a particular * child of the given parent node. Making sure to update the parent to point * to the new shadow. */ static int shadow_child(struct dm_btree_info *info, struct dm_btree_value_type *vt, struct btree_node *parent, unsigned int index, struct dm_block **result) { … } /* * Splits two nodes into three. This is more work, but results in fuller * nodes, so saves metadata space. */ static int split_two_into_three(struct shadow_spine *s, unsigned int parent_index, struct dm_btree_value_type *vt, uint64_t key) { … } /*----------------------------------------------------------------*/ /* * Splits a node by creating two new children beneath the given node. * * Before: * +----------+ * | A ++++++ | * +----------+ * * * After: * +------------+ * | A (shadow) | * +------------+ * | | * +------+ +----+ * | | * v v * +-------+ +-------+ * | B +++ | | C +++ | * +-------+ +-------+ */ static int btree_split_beneath(struct shadow_spine *s, uint64_t key) { … } /*----------------------------------------------------------------*/ /* * Redistributes a node's entries with its left sibling. */ static int rebalance_left(struct shadow_spine *s, struct dm_btree_value_type *vt, unsigned int parent_index, uint64_t key) { … } /* * Redistributes a nodes entries with its right sibling. */ static int rebalance_right(struct shadow_spine *s, struct dm_btree_value_type *vt, unsigned int parent_index, uint64_t key) { … } /* * Returns the number of spare entries in a node. */ static int get_node_free_space(struct dm_btree_info *info, dm_block_t b, unsigned int *space) { … } /* * Make space in a node, either by moving some entries to a sibling, * or creating a new sibling node. SPACE_THRESHOLD defines the minimum * number of free entries that must be in the sibling to make the move * worth while. If the siblings are shared (eg, part of a snapshot), * then they are not touched, since this break sharing and so consume * more space than we save. */ #define SPACE_THRESHOLD … static int rebalance_or_split(struct shadow_spine *s, struct dm_btree_value_type *vt, unsigned int parent_index, uint64_t key) { … } /* * Does the node contain a particular key? */ static bool contains_key(struct btree_node *node, uint64_t key) { … } /* * In general we preemptively make sure there's a free entry in every * node on the spine when doing an insert. But we can avoid that with * leaf nodes if we know it's an overwrite. */ static bool has_space_for_insert(struct btree_node *node, uint64_t key) { … } static int btree_insert_raw(struct shadow_spine *s, dm_block_t root, struct dm_btree_value_type *vt, uint64_t key, unsigned int *index) { … } static int __btree_get_overwrite_leaf(struct shadow_spine *s, dm_block_t root, uint64_t key, int *index) { … } int btree_get_overwrite_leaf(struct dm_btree_info *info, dm_block_t root, uint64_t key, int *index, dm_block_t *new_root, struct dm_block **leaf) { … } static bool need_insert(struct btree_node *node, uint64_t *keys, unsigned int level, unsigned int index) { … } static int insert(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value, dm_block_t *new_root, int *inserted) __dm_written_to_disk(value) { … } int dm_btree_insert(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value, dm_block_t *new_root) __dm_written_to_disk(value) { … } EXPORT_SYMBOL_GPL(…); int dm_btree_insert_notify(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value, dm_block_t *new_root, int *inserted) __dm_written_to_disk(value) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ static int find_key(struct ro_spine *s, dm_block_t block, bool find_highest, uint64_t *result_key, dm_block_t *next_block) { … } static int dm_btree_find_key(struct dm_btree_info *info, dm_block_t root, bool find_highest, uint64_t *result_keys) { … } int dm_btree_find_highest_key(struct dm_btree_info *info, dm_block_t root, uint64_t *result_keys) { … } EXPORT_SYMBOL_GPL(…); int dm_btree_find_lowest_key(struct dm_btree_info *info, dm_block_t root, uint64_t *result_keys) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ /* * FIXME: We shouldn't use a recursive algorithm when we have limited stack * space. Also this only works for single level trees. */ static int walk_node(struct dm_btree_info *info, dm_block_t block, int (*fn)(void *context, uint64_t *keys, void *leaf), void *context) { … } int dm_btree_walk(struct dm_btree_info *info, dm_block_t root, int (*fn)(void *context, uint64_t *keys, void *leaf), void *context) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ static void prefetch_values(struct dm_btree_cursor *c) { … } static bool leaf_node(struct dm_btree_cursor *c) { … } static int push_node(struct dm_btree_cursor *c, dm_block_t b) { … } static void pop_node(struct dm_btree_cursor *c) { … } static int inc_or_backtrack(struct dm_btree_cursor *c) { … } static int find_leaf(struct dm_btree_cursor *c) { … } int dm_btree_cursor_begin(struct dm_btree_info *info, dm_block_t root, bool prefetch_leaves, struct dm_btree_cursor *c) { … } EXPORT_SYMBOL_GPL(…); void dm_btree_cursor_end(struct dm_btree_cursor *c) { … } EXPORT_SYMBOL_GPL(…); int dm_btree_cursor_next(struct dm_btree_cursor *c) { … } EXPORT_SYMBOL_GPL(…); int dm_btree_cursor_skip(struct dm_btree_cursor *c, uint32_t count) { … } EXPORT_SYMBOL_GPL(…); int dm_btree_cursor_get_value(struct dm_btree_cursor *c, uint64_t *key, void *value_le) { … } EXPORT_SYMBOL_GPL(…);
Codebase Browser
linux