dm-btree-remove.c | Explore in Territory

// SPDX-License-Identifier: GPL-2.0-only
/*
 * Copyright (C) 2011 Red Hat, Inc.
 *
 * This file is released under the GPL.
 */

#include "dm-btree.h"
#include "dm-btree-internal.h"
#include "dm-transaction-manager.h"

#include <linux/export.h>
#include <linux/device-mapper.h>

#define DM_MSG_PREFIX …

/*
 * Removing an entry from a btree
 * ==============================
 *
 * A very important constraint for our btree is that no node, except the
 * root, may have fewer than a certain number of entries.
 * (MIN_ENTRIES <= nr_entries <= MAX_ENTRIES).
 *
 * Ensuring this is complicated by the way we want to only ever hold the
 * locks on 2 nodes concurrently, and only change nodes in a top to bottom
 * fashion.
 *
 * Each node may have a left or right sibling.  When decending the spine,
 * if a node contains only MIN_ENTRIES then we try and increase this to at
 * least MIN_ENTRIES + 1.  We do this in the following ways:
 *
 * [A] No siblings => this can only happen if the node is the root, in which
 *     case we copy the childs contents over the root.
 *
 * [B] No left sibling
 *     ==> rebalance(node, right sibling)
 *
 * [C] No right sibling
 *     ==> rebalance(left sibling, node)
 *
 * [D] Both siblings, total_entries(left, node, right) <= DEL_THRESHOLD
 *     ==> delete node adding it's contents to left and right
 *
 * [E] Both siblings, total_entries(left, node, right) > DEL_THRESHOLD
 *     ==> rebalance(left, node, right)
 *
 * After these operations it's possible that the our original node no
 * longer contains the desired sub tree.  For this reason this rebalancing
 * is performed on the children of the current node.  This also avoids
 * having a special case for the root.
 *
 * Once this rebalancing has occurred we can then step into the child node
 * for internal nodes.  Or delete the entry for leaf nodes.
 */

/*
 * Some little utilities for moving node data around.
 */
static void node_shift(struct btree_node *n, int shift)
{ … }

static int node_copy(struct btree_node *left, struct btree_node *right, int shift)
{ … }

/*
 * Delete a specific entry from a leaf node.
 */
static void delete_at(struct btree_node *n, unsigned int index)
{ … }

static unsigned int merge_threshold(struct btree_node *n)
{ … }

struct child { … };

static int init_child(struct dm_btree_info *info, struct dm_btree_value_type *vt,
		      struct btree_node *parent,
		      unsigned int index, struct child *result)
{ … }

static void exit_child(struct dm_btree_info *info, struct child *c)
{ … }

static int shift(struct btree_node *left, struct btree_node *right, int count)
{ … }

static int __rebalance2(struct dm_btree_info *info, struct btree_node *parent,
			struct child *l, struct child *r)
{ … }

static int rebalance2(struct shadow_spine *s, struct dm_btree_info *info,
		      struct dm_btree_value_type *vt, unsigned int left_index)
{ … }

/*
 * We dump as many entries from center as possible into left, then the rest
 * in right, then rebalance2.  This wastes some cpu, but I want something
 * simple atm.
 */
static int delete_center_node(struct dm_btree_info *info, struct btree_node *parent,
			      struct child *l, struct child *c, struct child *r,
			      struct btree_node *left, struct btree_node *center, struct btree_node *right,
			      uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)
{ … }

/*
 * Redistributes entries among 3 sibling nodes.
 */
static int redistribute3(struct dm_btree_info *info, struct btree_node *parent,
			 struct child *l, struct child *c, struct child *r,
			 struct btree_node *left, struct btree_node *center, struct btree_node *right,
			 uint32_t nr_left, uint32_t nr_center, uint32_t nr_right)
{ … }

static int __rebalance3(struct dm_btree_info *info, struct btree_node *parent,
			struct child *l, struct child *c, struct child *r)
{ … }

static int rebalance3(struct shadow_spine *s, struct dm_btree_info *info,
		      struct dm_btree_value_type *vt, unsigned int left_index)
{ … }

static int rebalance_children(struct shadow_spine *s,
			      struct dm_btree_info *info,
			      struct dm_btree_value_type *vt, uint64_t key)
{ … }

static int do_leaf(struct btree_node *n, uint64_t key, unsigned int *index)
{ … }

/*
 * Prepares for removal from one level of the hierarchy.  The caller must
 * call delete_at() to remove the entry at index.
 */
static int remove_raw(struct shadow_spine *s, struct dm_btree_info *info,
		      struct dm_btree_value_type *vt, dm_block_t root,
		      uint64_t key, unsigned int *index)
{ … }

int dm_btree_remove(struct dm_btree_info *info, dm_block_t root,
		    uint64_t *keys, dm_block_t *new_root)
{ … }
EXPORT_SYMBOL_GPL(…);

/*----------------------------------------------------------------*/

static int remove_nearest(struct shadow_spine *s, struct dm_btree_info *info,
			  struct dm_btree_value_type *vt, dm_block_t root,
			  uint64_t key, int *index)
{ … }

static int remove_one(struct dm_btree_info *info, dm_block_t root,
		      uint64_t *keys, uint64_t end_key,
		      dm_block_t *new_root, unsigned int *nr_removed)
{ … }

int dm_btree_remove_leaves(struct dm_btree_info *info, dm_block_t root,
			   uint64_t *first_key, uint64_t end_key,
			   dm_block_t *new_root, unsigned int *nr_removed)
{ … }
EXPORT_SYMBOL_GPL(…);
linux/drivers/md/persistent-data/dm-btree-remove.c
