// 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 "btree" /* *-------------------------------------------------------------- * Array manipulation *-------------------------------------------------------------- */static void memcpy_disk(void *dest, const void *src, size_t len) __dm_written_to_disk(src){ memcpy(dest, src, len); __dm_unbless_for_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){ if (index < nr_elts) memmove(base + (elt_size * (index + 1)), base + (elt_size * index), (nr_elts - index) * elt_size); memcpy_disk(base + (elt_size * index), elt, elt_size);} /*----------------------------------------------------------------*/ /* makes the assumption that no two keys are the same. */static int bsearch(struct btree_node *n, uint64_t key, int want_hi){ int lo = -1, hi = le32_to_cpu(n->header.nr_entries); while (hi - lo > 1) { int mid = lo + ((hi - lo) / 2); uint64_t mid_key = le64_to_cpu(n->keys[mid]); if (mid_key == key) return mid; if (mid_key < key) lo = mid; else hi = mid; } return want_hi ? hi : lo;} int lower_bound(struct btree_node *n, uint64_t key){ return bsearch(n, key, 0);} static int upper_bound(struct btree_node *n, uint64_t key){ return bsearch(n, key, 1);} void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, struct dm_btree_value_type *vt){ uint32_t nr_entries = le32_to_cpu(n->header.nr_entries); if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) dm_tm_with_runs(tm, value_ptr(n, 0), nr_entries, dm_tm_inc_range); else if (vt->inc) vt->inc(vt->context, value_ptr(n, 0), nr_entries);} 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){ uint32_t nr_entries = le32_to_cpu(node->header.nr_entries); uint32_t max_entries = le32_to_cpu(node->header.max_entries); __le64 key_le = cpu_to_le64(key); if (index > nr_entries || index >= max_entries || nr_entries >= max_entries) { DMERR("too many entries in btree node for insert"); __dm_unbless_for_disk(value); return -ENOMEM; } __dm_bless_for_disk(&key_le); array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); array_insert(value_base(node), value_size, nr_entries, index, value); node->header.nr_entries = cpu_to_le32(nr_entries + 1); return 0;} /*----------------------------------------------------------------*/ /* * 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){ uint32_t total, n; size_t elt_size = sizeof(uint64_t) + value_size; /* key + value */ block_size -= sizeof(struct node_header); total = block_size / elt_size; n = total / 3; /* rounds down */ return 3 * n;} int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root){ int r; struct dm_block *b; struct btree_node *n; size_t block_size; uint32_t max_entries; r = new_block(info, &b); if (r < 0) return r; block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); max_entries = calc_max_entries(info->value_type.size, block_size); n = dm_block_data(b); memset(n, 0, block_size); n->header.flags = cpu_to_le32(LEAF_NODE); n->header.nr_entries = cpu_to_le32(0); n->header.max_entries = cpu_to_le32(max_entries); n->header.value_size = cpu_to_le32(info->value_type.size); *root = dm_block_location(b); unlock_block(info, b); return 0;}EXPORT_SYMBOL_GPL(dm_btree_empty); /*----------------------------------------------------------------*/ /* * Deletion uses a recursive algorithm, since we have limited stack space * we explicitly manage our own stack on the heap. */#define MAX_SPINE_DEPTH 64struct frame { struct dm_block *b; struct btree_node *n; unsigned int level; unsigned int nr_children; unsigned int current_child;}; struct del_stack { struct dm_btree_info *info; struct dm_transaction_manager *tm; int top; struct frame spine[MAX_SPINE_DEPTH];}; static int top_frame(struct del_stack *s, struct frame **f){ if (s->top < 0) { DMERR("btree deletion stack empty"); return -EINVAL; } *f = s->spine + s->top; return 0;} static int unprocessed_frames(struct del_stack *s){ return s->top >= 0;} static void prefetch_children(struct del_stack *s, struct frame *f){ unsigned int i; struct dm_block_manager *bm = dm_tm_get_bm(s->tm); for (i = 0; i < f->nr_children; i++) dm_bm_prefetch(bm, value64(f->n, i));} static bool is_internal_level(struct dm_btree_info *info, struct frame *f){ return f->level < (info->levels - 1);} static int push_frame(struct del_stack *s, dm_block_t b, unsigned int level){ int r; uint32_t ref_count; if (s->top >= MAX_SPINE_DEPTH - 1) { DMERR("btree deletion stack out of memory"); return -ENOMEM; } r = dm_tm_ref(s->tm, b, &ref_count); if (r) return r; if (ref_count > 1) /* * This is a shared node, so we can just decrement it's * reference counter and leave the children. */ dm_tm_dec(s->tm, b); else { uint32_t flags; struct frame *f = s->spine + ++s->top; r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); if (r) { s->top--; return r; } f->n = dm_block_data(f->b); f->level = level; f->nr_children = le32_to_cpu(f->n->header.nr_entries); f->current_child = 0; flags = le32_to_cpu(f->n->header.flags); if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) prefetch_children(s, f); } return 0;} static void pop_frame(struct del_stack *s){ struct frame *f = s->spine + s->top--; dm_tm_dec(s->tm, dm_block_location(f->b)); dm_tm_unlock(s->tm, f->b);} static void unlock_all_frames(struct del_stack *s){ struct frame *f; while (unprocessed_frames(s)) { f = s->spine + s->top--; dm_tm_unlock(s->tm, f->b); }} int dm_btree_del(struct dm_btree_info *info, dm_block_t root){ int r; struct del_stack *s; /* * dm_btree_del() is called via an ioctl, as such should be * considered an FS op. We can't recurse back into the FS, so we * allocate GFP_NOFS. */ s = kmalloc_obj(*s, GFP_NOFS); if (!s) return -ENOMEM; s->info = info; s->tm = info->tm; s->top = -1; r = push_frame(s, root, 0); if (r) goto out; while (unprocessed_frames(s)) { uint32_t flags; struct frame *f; dm_block_t b; r = top_frame(s, &f); if (r) goto out; if (f->current_child >= f->nr_children) { pop_frame(s); continue; } flags = le32_to_cpu(f->n->header.flags); if (flags & INTERNAL_NODE) { b = value64(f->n, f->current_child); f->current_child++; r = push_frame(s, b, f->level); if (r) goto out; } else if (is_internal_level(info, f)) { b = value64(f->n, f->current_child); f->current_child++; r = push_frame(s, b, f->level + 1); if (r) goto out; } else { if (info->value_type.dec) info->value_type.dec(info->value_type.context, value_ptr(f->n, 0), f->nr_children); pop_frame(s); } }out: if (r) { /* cleanup all frames of del_stack */ unlock_all_frames(s); } kfree(s); return r;}EXPORT_SYMBOL_GPL(dm_btree_del); /*----------------------------------------------------------------*/ 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 i, r; uint32_t flags, nr_entries; do { r = ro_step(s, block); if (r < 0) return r; i = search_fn(ro_node(s), key); flags = le32_to_cpu(ro_node(s)->header.flags); nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); if (i < 0 || i >= nr_entries) return -ENODATA; if (flags & INTERNAL_NODE) block = value64(ro_node(s), i); } while (!(flags & LEAF_NODE)); *result_key = le64_to_cpu(ro_node(s)->keys[i]); if (v) memcpy(v, value_ptr(ro_node(s), i), value_size); return 0;} int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value_le){ unsigned int level, last_level = info->levels - 1; int r = -ENODATA; uint64_t rkey; __le64 internal_value_le; struct ro_spine spine; init_ro_spine(&spine, info); for (level = 0; level < info->levels; level++) { size_t size; void *value_p; if (level == last_level) { value_p = value_le; size = info->value_type.size; } else { value_p = &internal_value_le; size = sizeof(uint64_t); } r = btree_lookup_raw(&spine, root, keys[level], lower_bound, &rkey, value_p, size); if (!r) { if (rkey != keys[level]) { exit_ro_spine(&spine); return -ENODATA; } } else { exit_ro_spine(&spine); return r; } root = le64_to_cpu(internal_value_le); } exit_ro_spine(&spine); return r;}EXPORT_SYMBOL_GPL(dm_btree_lookup); 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 r, i; uint32_t flags, nr_entries; struct dm_block *node; struct btree_node *n; r = bn_read_lock(info, root, &node); if (r) return r; n = dm_block_data(node); flags = le32_to_cpu(n->header.flags); nr_entries = le32_to_cpu(n->header.nr_entries); if (flags & INTERNAL_NODE) { i = lower_bound(n, key); if (i < 0) { /* * avoid early -ENODATA return when all entries are * higher than the search @key. */ i = 0; } if (i >= nr_entries) { r = -ENODATA; goto out; } r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le); if (r == -ENODATA && i < (nr_entries - 1)) { i++; r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le); } } else { i = upper_bound(n, key); if (i < 0 || i >= nr_entries) { r = -ENODATA; goto out; } *rkey = le64_to_cpu(n->keys[i]); memcpy(value_le, value_ptr(n, i), info->value_type.size); }out: dm_tm_unlock(info->tm, node); return r;} int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, uint64_t *rkey, void *value_le){ unsigned int level; int r = -ENODATA; __le64 internal_value_le; struct ro_spine spine; init_ro_spine(&spine, info); for (level = 0; level < info->levels - 1u; level++) { r = btree_lookup_raw(&spine, root, keys[level], lower_bound, rkey, &internal_value_le, sizeof(uint64_t)); if (r) goto out; if (*rkey != keys[level]) { r = -ENODATA; goto out; } root = le64_to_cpu(internal_value_le); } r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le);out: exit_ro_spine(&spine); return r;}EXPORT_SYMBOL_GPL(dm_btree_lookup_next); Lines 1–500 of 1637. Load more
// 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 "btree" /* *-------------------------------------------------------------- * Array manipulation *-------------------------------------------------------------- */ static void memcpy_disk(void *dest, const void *src, size_t len) __dm_written_to_disk(src) { memcpy(dest, src, len); __dm_unbless_for_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) { if (index < nr_elts) memmove(base + (elt_size * (index + 1)), base + (elt_size * index), (nr_elts - index) * elt_size); memcpy_disk(base + (elt_size * index), elt, elt_size); } /*----------------------------------------------------------------*/ /* makes the assumption that no two keys are the same. */ static int bsearch(struct btree_node *n, uint64_t key, int want_hi) { int lo = -1, hi = le32_to_cpu(n->header.nr_entries); while (hi - lo > 1) { int mid = lo + ((hi - lo) / 2); uint64_t mid_key = le64_to_cpu(n->keys[mid]); if (mid_key == key) return mid; if (mid_key < key) lo = mid; else hi = mid; } return want_hi ? hi : lo; } int lower_bound(struct btree_node *n, uint64_t key) { return bsearch(n, key, 0); } static int upper_bound(struct btree_node *n, uint64_t key) { return bsearch(n, key, 1); } void inc_children(struct dm_transaction_manager *tm, struct btree_node *n, struct dm_btree_value_type *vt) { uint32_t nr_entries = le32_to_cpu(n->header.nr_entries); if (le32_to_cpu(n->header.flags) & INTERNAL_NODE) dm_tm_with_runs(tm, value_ptr(n, 0), nr_entries, dm_tm_inc_range); else if (vt->inc) vt->inc(vt->context, value_ptr(n, 0), nr_entries); } 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) { uint32_t nr_entries = le32_to_cpu(node->header.nr_entries); uint32_t max_entries = le32_to_cpu(node->header.max_entries); __le64 key_le = cpu_to_le64(key); if (index > nr_entries || index >= max_entries || nr_entries >= max_entries) { DMERR("too many entries in btree node for insert"); __dm_unbless_for_disk(value); return -ENOMEM; } __dm_bless_for_disk(&key_le); array_insert(node->keys, sizeof(*node->keys), nr_entries, index, &key_le); array_insert(value_base(node), value_size, nr_entries, index, value); node->header.nr_entries = cpu_to_le32(nr_entries + 1); return 0; } /*----------------------------------------------------------------*/ /* * 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) { uint32_t total, n; size_t elt_size = sizeof(uint64_t) + value_size; /* key + value */ block_size -= sizeof(struct node_header); total = block_size / elt_size; n = total / 3; /* rounds down */ return 3 * n; } int dm_btree_empty(struct dm_btree_info *info, dm_block_t *root) { int r; struct dm_block *b; struct btree_node *n; size_t block_size; uint32_t max_entries; r = new_block(info, &b); if (r < 0) return r; block_size = dm_bm_block_size(dm_tm_get_bm(info->tm)); max_entries = calc_max_entries(info->value_type.size, block_size); n = dm_block_data(b); memset(n, 0, block_size); n->header.flags = cpu_to_le32(LEAF_NODE); n->header.nr_entries = cpu_to_le32(0); n->header.max_entries = cpu_to_le32(max_entries); n->header.value_size = cpu_to_le32(info->value_type.size); *root = dm_block_location(b); unlock_block(info, b); return 0; } EXPORT_SYMBOL_GPL(dm_btree_empty); /*----------------------------------------------------------------*/ /* * Deletion uses a recursive algorithm, since we have limited stack space * we explicitly manage our own stack on the heap. */ #define MAX_SPINE_DEPTH 64 struct frame { struct dm_block *b; struct btree_node *n; unsigned int level; unsigned int nr_children; unsigned int current_child; }; struct del_stack { struct dm_btree_info *info; struct dm_transaction_manager *tm; int top; struct frame spine[MAX_SPINE_DEPTH]; }; static int top_frame(struct del_stack *s, struct frame **f) { if (s->top < 0) { DMERR("btree deletion stack empty"); return -EINVAL; } *f = s->spine + s->top; return 0; } static int unprocessed_frames(struct del_stack *s) { return s->top >= 0; } static void prefetch_children(struct del_stack *s, struct frame *f) { unsigned int i; struct dm_block_manager *bm = dm_tm_get_bm(s->tm); for (i = 0; i < f->nr_children; i++) dm_bm_prefetch(bm, value64(f->n, i)); } static bool is_internal_level(struct dm_btree_info *info, struct frame *f) { return f->level < (info->levels - 1); } static int push_frame(struct del_stack *s, dm_block_t b, unsigned int level) { int r; uint32_t ref_count; if (s->top >= MAX_SPINE_DEPTH - 1) { DMERR("btree deletion stack out of memory"); return -ENOMEM; } r = dm_tm_ref(s->tm, b, &ref_count); if (r) return r; if (ref_count > 1) /* * This is a shared node, so we can just decrement it's * reference counter and leave the children. */ dm_tm_dec(s->tm, b); else { uint32_t flags; struct frame *f = s->spine + ++s->top; r = dm_tm_read_lock(s->tm, b, &btree_node_validator, &f->b); if (r) { s->top--; return r; } f->n = dm_block_data(f->b); f->level = level; f->nr_children = le32_to_cpu(f->n->header.nr_entries); f->current_child = 0; flags = le32_to_cpu(f->n->header.flags); if (flags & INTERNAL_NODE || is_internal_level(s->info, f)) prefetch_children(s, f); } return 0; } static void pop_frame(struct del_stack *s) { struct frame *f = s->spine + s->top--; dm_tm_dec(s->tm, dm_block_location(f->b)); dm_tm_unlock(s->tm, f->b); } static void unlock_all_frames(struct del_stack *s) { struct frame *f; while (unprocessed_frames(s)) { f = s->spine + s->top--; dm_tm_unlock(s->tm, f->b); } } int dm_btree_del(struct dm_btree_info *info, dm_block_t root) { int r; struct del_stack *s; /* * dm_btree_del() is called via an ioctl, as such should be * considered an FS op. We can't recurse back into the FS, so we * allocate GFP_NOFS. */ s = kmalloc_obj(*s, GFP_NOFS); if (!s) return -ENOMEM; s->info = info; s->tm = info->tm; s->top = -1; r = push_frame(s, root, 0); if (r) goto out; while (unprocessed_frames(s)) { uint32_t flags; struct frame *f; dm_block_t b; r = top_frame(s, &f); if (r) goto out; if (f->current_child >= f->nr_children) { pop_frame(s); continue; } flags = le32_to_cpu(f->n->header.flags); if (flags & INTERNAL_NODE) { b = value64(f->n, f->current_child); f->current_child++; r = push_frame(s, b, f->level); if (r) goto out; } else if (is_internal_level(info, f)) { b = value64(f->n, f->current_child); f->current_child++; r = push_frame(s, b, f->level + 1); if (r) goto out; } else { if (info->value_type.dec) info->value_type.dec(info->value_type.context, value_ptr(f->n, 0), f->nr_children); pop_frame(s); } } out: if (r) { /* cleanup all frames of del_stack */ unlock_all_frames(s); } kfree(s); return r; } EXPORT_SYMBOL_GPL(dm_btree_del); /*----------------------------------------------------------------*/ 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 i, r; uint32_t flags, nr_entries; do { r = ro_step(s, block); if (r < 0) return r; i = search_fn(ro_node(s), key); flags = le32_to_cpu(ro_node(s)->header.flags); nr_entries = le32_to_cpu(ro_node(s)->header.nr_entries); if (i < 0 || i >= nr_entries) return -ENODATA; if (flags & INTERNAL_NODE) block = value64(ro_node(s), i); } while (!(flags & LEAF_NODE)); *result_key = le64_to_cpu(ro_node(s)->keys[i]); if (v) memcpy(v, value_ptr(ro_node(s), i), value_size); return 0; } int dm_btree_lookup(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, void *value_le) { unsigned int level, last_level = info->levels - 1; int r = -ENODATA; uint64_t rkey; __le64 internal_value_le; struct ro_spine spine; init_ro_spine(&spine, info); for (level = 0; level < info->levels; level++) { size_t size; void *value_p; if (level == last_level) { value_p = value_le; size = info->value_type.size; } else { value_p = &internal_value_le; size = sizeof(uint64_t); } r = btree_lookup_raw(&spine, root, keys[level], lower_bound, &rkey, value_p, size); if (!r) { if (rkey != keys[level]) { exit_ro_spine(&spine); return -ENODATA; } } else { exit_ro_spine(&spine); return r; } root = le64_to_cpu(internal_value_le); } exit_ro_spine(&spine); return r; } EXPORT_SYMBOL_GPL(dm_btree_lookup); 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 r, i; uint32_t flags, nr_entries; struct dm_block *node; struct btree_node *n; r = bn_read_lock(info, root, &node); if (r) return r; n = dm_block_data(node); flags = le32_to_cpu(n->header.flags); nr_entries = le32_to_cpu(n->header.nr_entries); if (flags & INTERNAL_NODE) { i = lower_bound(n, key); if (i < 0) { /* * avoid early -ENODATA return when all entries are * higher than the search @key. */ i = 0; } if (i >= nr_entries) { r = -ENODATA; goto out; } r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le); if (r == -ENODATA && i < (nr_entries - 1)) { i++; r = dm_btree_lookup_next_single(info, value64(n, i), key, rkey, value_le); } } else { i = upper_bound(n, key); if (i < 0 || i >= nr_entries) { r = -ENODATA; goto out; } *rkey = le64_to_cpu(n->keys[i]); memcpy(value_le, value_ptr(n, i), info->value_type.size); } out: dm_tm_unlock(info->tm, node); return r; } int dm_btree_lookup_next(struct dm_btree_info *info, dm_block_t root, uint64_t *keys, uint64_t *rkey, void *value_le) { unsigned int level; int r = -ENODATA; __le64 internal_value_le; struct ro_spine spine; init_ro_spine(&spine, info); for (level = 0; level < info->levels - 1u; level++) { r = btree_lookup_raw(&spine, root, keys[level], lower_bound, rkey, &internal_value_le, sizeof(uint64_t)); if (r) goto out; if (*rkey != keys[level]) { r = -ENODATA; goto out; } root = le64_to_cpu(internal_value_le); } r = dm_btree_lookup_next_single(info, root, keys[level], rkey, value_le); out: exit_ro_spine(&spine); return r; } EXPORT_SYMBOL_GPL(dm_btree_lookup_next);