// SPDX-License-Identifier: GPL-2.0-only /* * Copyright (C) 2012 Red Hat, Inc. * * This file is released under the GPL. */ #include "dm-array.h" #include "dm-space-map.h" #include "dm-transaction-manager.h" #include <linux/export.h> #include <linux/device-mapper.h> #define DM_MSG_PREFIX … /*----------------------------------------------------------------*/ /* * The array is implemented as a fully populated btree, which points to * blocks that contain the packed values. This is more space efficient * than just using a btree since we don't store 1 key per value. */ struct array_block { … } __packed; /*----------------------------------------------------------------*/ /* * Validator methods. As usual we calculate a checksum, and also write the * block location into the header (paranoia about ssds remapping areas by * mistake). */ #define CSUM_XOR … static void array_block_prepare_for_write(const struct dm_block_validator *v, struct dm_block *b, size_t size_of_block) { … } static int array_block_check(const struct dm_block_validator *v, struct dm_block *b, size_t size_of_block) { … } static const struct dm_block_validator array_validator = …; /*----------------------------------------------------------------*/ /* * Functions for manipulating the array blocks. */ /* * Returns a pointer to a value within an array block. * * index - The index into _this_ specific block. */ static void *element_at(struct dm_array_info *info, struct array_block *ab, unsigned int index) { … } /* * Utility function that calls one of the value_type methods on every value * in an array block. */ static void on_entries(struct dm_array_info *info, struct array_block *ab, void (*fn)(void *, const void *, unsigned int)) { … } /* * Increment every value in an array block. */ static void inc_ablock_entries(struct dm_array_info *info, struct array_block *ab) { … } /* * Decrement every value in an array block. */ static void dec_ablock_entries(struct dm_array_info *info, struct array_block *ab) { … } /* * Each array block can hold this many values. */ static uint32_t calc_max_entries(size_t value_size, size_t size_of_block) { … } /* * Allocate a new array block. The caller will need to unlock block. */ static int alloc_ablock(struct dm_array_info *info, size_t size_of_block, uint32_t max_entries, struct dm_block **block, struct array_block **ab) { … } /* * Pad an array block out with a particular value. Every instance will * cause an increment of the value_type. new_nr must always be more than * the current number of entries. */ static void fill_ablock(struct dm_array_info *info, struct array_block *ab, const void *value, unsigned int new_nr) { … } /* * Remove some entries from the back of an array block. Every value * removed will be decremented. new_nr must be <= the current number of * entries. */ static void trim_ablock(struct dm_array_info *info, struct array_block *ab, unsigned int new_nr) { … } /* * Read locks a block, and coerces it to an array block. The caller must * unlock 'block' when finished. */ static int get_ablock(struct dm_array_info *info, dm_block_t b, struct dm_block **block, struct array_block **ab) { … } /* * Unlocks an array block. */ static void unlock_ablock(struct dm_array_info *info, struct dm_block *block) { … } /*----------------------------------------------------------------*/ /* * Btree manipulation. */ /* * Looks up an array block in the btree, and then read locks it. * * index is the index of the index of the array_block, (ie. the array index * / max_entries). */ static int lookup_ablock(struct dm_array_info *info, dm_block_t root, unsigned int index, struct dm_block **block, struct array_block **ab) { … } /* * Insert an array block into the btree. The block is _not_ unlocked. */ static int insert_ablock(struct dm_array_info *info, uint64_t index, struct dm_block *block, dm_block_t *root) { … } /*----------------------------------------------------------------*/ static int __shadow_ablock(struct dm_array_info *info, dm_block_t b, struct dm_block **block, struct array_block **ab) { … } /* * The shadow op will often be a noop. Only insert if it really * copied data. */ static int __reinsert_ablock(struct dm_array_info *info, unsigned int index, struct dm_block *block, dm_block_t b, dm_block_t *root) { … } /* * Looks up an array block in the btree. Then shadows it, and updates the * btree to point to this new shadow. 'root' is an input/output parameter * for both the current root block, and the new one. */ static int shadow_ablock(struct dm_array_info *info, dm_block_t *root, unsigned int index, struct dm_block **block, struct array_block **ab) { … } /* * Allocate an new array block, and fill it with some values. */ static int insert_new_ablock(struct dm_array_info *info, size_t size_of_block, uint32_t max_entries, unsigned int block_index, uint32_t nr, const void *value, dm_block_t *root) { … } static int insert_full_ablocks(struct dm_array_info *info, size_t size_of_block, unsigned int begin_block, unsigned int end_block, unsigned int max_entries, const void *value, dm_block_t *root) { … } /* * There are a bunch of functions involved with resizing an array. This * structure holds information that commonly needed by them. Purely here * to reduce parameter count. */ struct resize { … }; /* * Removes a consecutive set of array blocks from the btree. The values * in block are decremented as a side effect of the btree remove. * * begin_index - the index of the first array block to remove. * end_index - the one-past-the-end value. ie. this block is not removed. */ static int drop_blocks(struct resize *resize, unsigned int begin_index, unsigned int end_index) { … } /* * Calculates how many blocks are needed for the array. */ static unsigned int total_nr_blocks_needed(unsigned int nr_full_blocks, unsigned int nr_entries_in_last_block) { … } /* * Shrink an array. */ static int shrink(struct resize *resize) { … } /* * Grow an array. */ static int grow_extend_tail_block(struct resize *resize, uint32_t new_nr_entries) { … } static int grow_add_tail_block(struct resize *resize) { … } static int grow_needs_more_blocks(struct resize *resize) { … } static int grow(struct resize *resize) { … } /*----------------------------------------------------------------*/ /* * These are the value_type functions for the btree elements, which point * to array blocks. */ static void block_inc(void *context, const void *value, unsigned int count) { … } static void __block_dec(void *context, const void *value) { … } static void block_dec(void *context, const void *value, unsigned int count) { … } static int block_equal(void *context, const void *value1, const void *value2) { … } /*----------------------------------------------------------------*/ void dm_array_info_init(struct dm_array_info *info, struct dm_transaction_manager *tm, struct dm_btree_value_type *vt) { … } EXPORT_SYMBOL_GPL(…); int dm_array_empty(struct dm_array_info *info, dm_block_t *root) { … } EXPORT_SYMBOL_GPL(…); static int array_resize(struct dm_array_info *info, dm_block_t root, uint32_t old_size, uint32_t new_size, const void *value, dm_block_t *new_root) { … } int dm_array_resize(struct dm_array_info *info, dm_block_t root, uint32_t old_size, uint32_t new_size, const void *value, dm_block_t *new_root) __dm_written_to_disk(value) { … } EXPORT_SYMBOL_GPL(…); static int populate_ablock_with_values(struct dm_array_info *info, struct array_block *ab, value_fn fn, void *context, unsigned int base, unsigned int new_nr) { … } int dm_array_new(struct dm_array_info *info, dm_block_t *root, uint32_t size, value_fn fn, void *context) { … } EXPORT_SYMBOL_GPL(…); int dm_array_del(struct dm_array_info *info, dm_block_t root) { … } EXPORT_SYMBOL_GPL(…); int dm_array_get_value(struct dm_array_info *info, dm_block_t root, uint32_t index, void *value_le) { … } EXPORT_SYMBOL_GPL(…); static int array_set_value(struct dm_array_info *info, dm_block_t root, uint32_t index, const void *value, dm_block_t *new_root) { … } int dm_array_set_value(struct dm_array_info *info, dm_block_t root, uint32_t index, const void *value, dm_block_t *new_root) __dm_written_to_disk(value) { … } EXPORT_SYMBOL_GPL(…); struct walk_info { … }; static int walk_ablock(void *context, uint64_t *keys, void *leaf) { … } int dm_array_walk(struct dm_array_info *info, dm_block_t root, int (*fn)(void *, uint64_t key, void *leaf), void *context) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/ static int load_ablock(struct dm_array_cursor *c) { … } int dm_array_cursor_begin(struct dm_array_info *info, dm_block_t root, struct dm_array_cursor *c) { … } EXPORT_SYMBOL_GPL(…); void dm_array_cursor_end(struct dm_array_cursor *c) { … } EXPORT_SYMBOL_GPL(…); int dm_array_cursor_next(struct dm_array_cursor *c) { … } EXPORT_SYMBOL_GPL(…); int dm_array_cursor_skip(struct dm_array_cursor *c, uint32_t count) { … } EXPORT_SYMBOL_GPL(…); void dm_array_cursor_get_value(struct dm_array_cursor *c, void **value_le) { … } EXPORT_SYMBOL_GPL(…); /*----------------------------------------------------------------*/
Codebase Browser
linux