lvm2-commits September 2018

lvm2-commits@lists.fedorahosted.org

4 participants
37 discussions

master - [radix-tree] alternative radix-tree implementation.
by Joe Thornber 11 Sep '18

11 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=4d964133e267b2b501a5d… Commit: 4d964133e267b2b501a5dcd40c30cfdcfaa5903a Parent: 22a13043683a5647e8cc4e3aead911e5269ffd2f Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Sep 11 11:11:35 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Tue Sep 11 13:12:07 2018 +0100 [radix-tree] alternative radix-tree implementation. Sacrifices performance for simplicity, meant only for verification of the real adaptive implementation. --- base/Makefile | 3 + base/data-struct/radix-tree-adaptive.c | 1262 ++++++++++++++++++++++++++++++++ base/data-struct/radix-tree-simple.c | 256 +++++++ base/data-struct/radix-tree.c | 1251 +------------------------------- 4 files changed, 1526 insertions(+), 1246 deletions(-) diff --git a/base/Makefile b/base/Makefile index 02c4236..1823c9b 100644 --- a/base/Makefile +++ b/base/Makefile @@ -10,6 +10,9 @@ # along with this program; if not, write to the Free Software Foundation, # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +# Uncomment this to build the simple radix tree. You'll need to make clean too. +# base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE + BASE_SOURCE=\ base/data-struct/radix-tree.c \ base/data-struct/hash.c \ diff --git a/base/data-struct/radix-tree-adaptive.c b/base/data-struct/radix-tree-adaptive.c new file mode 100644 index 0000000..1eef1f8 --- /dev/null +++ b/base/data-struct/radix-tree-adaptive.c @@ -0,0 +1,1262 @@ +// Copyright (C) 2018 Red Hat, Inc. All rights reserved. +// +// This file is part of LVM2. +// +// This copyrighted material is made available to anyone wishing to use, +// modify, copy, or redistribute it subject to the terms and conditions +// of the GNU Lesser General Public License v.2.1. +// +// You should have received a copy of the GNU Lesser General Public License +// along with this program; if not, write to the Free Software Foundation, +// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +#include "radix-tree.h" + +#include "base/memory/container_of.h" +#include "base/memory/zalloc.h" + +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> + +//---------------------------------------------------------------- + +enum node_type { + UNSET = 0, + VALUE, + VALUE_CHAIN, + PREFIX_CHAIN, + NODE4, + NODE16, + NODE48, + NODE256 +}; + +struct value { + enum node_type type; + union radix_value value; +}; + +// This is used for entries that have a key which is a prefix of another key. +struct value_chain { + union radix_value value; + struct value child; +}; + +struct prefix_chain { + struct value child; + unsigned len; + uint8_t prefix[0]; +}; + +struct node4 { + uint32_t nr_entries; + uint8_t keys[4]; + struct value values[4]; +}; + +struct node16 { + uint32_t nr_entries; + uint8_t keys[16]; + struct value values[16]; +}; + +struct node48 { + uint32_t nr_entries; + uint8_t keys[256]; + struct value values[48]; +}; + +struct node256 { + uint32_t nr_entries; + struct value values[256]; +}; + +struct radix_tree { + unsigned nr_entries; + struct value root; + radix_value_dtr dtr; + void *dtr_context; +}; + +//---------------------------------------------------------------- + +struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context) +{ + struct radix_tree *rt = malloc(sizeof(*rt)); + + if (rt) { + rt->nr_entries = 0; + rt->root.type = UNSET; + rt->dtr = dtr; + rt->dtr_context = dtr_context; + } + + return rt; +} + +static inline void _dtr(struct radix_tree *rt, union radix_value v) +{ + if (rt->dtr) + rt->dtr(rt->dtr_context, v); +} + +// Returns the number of values removed +static unsigned _free_node(struct radix_tree *rt, struct value v) +{ + unsigned i, nr = 0; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + switch (v.type) { + case UNSET: + break; + + case VALUE: + _dtr(rt, v.value); + nr = 1; + break; + + case VALUE_CHAIN: + vc = v.value.ptr; + _dtr(rt, vc->value); + nr = 1 + _free_node(rt, vc->child); + free(vc); + break; + + case PREFIX_CHAIN: + pc = v.value.ptr; + nr = _free_node(rt, pc->child); + free(pc); + break; + + case NODE4: + n4 = (struct node4 *) v.value.ptr; + for (i = 0; i < n4->nr_entries; i++) + nr += _free_node(rt, n4->values[i]); + free(n4); + break; + + case NODE16: + n16 = (struct node16 *) v.value.ptr; + for (i = 0; i < n16->nr_entries; i++) + nr += _free_node(rt, n16->values[i]); + free(n16); + break; + + case NODE48: + n48 = (struct node48 *) v.value.ptr; + for (i = 0; i < n48->nr_entries; i++) + nr += _free_node(rt, n48->values[i]); + free(n48); + break; + + case NODE256: + n256 = (struct node256 *) v.value.ptr; + for (i = 0; i < 256; i++) + nr += _free_node(rt, n256->values[i]); + free(n256); + break; + } + + return nr; +} + +void radix_tree_destroy(struct radix_tree *rt) +{ + _free_node(rt, rt->root); + free(rt); +} + +unsigned radix_tree_size(struct radix_tree *rt) +{ + return rt->nr_entries; +} + +static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv); + +static bool _insert_unset(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + unsigned len = ke - kb; + + if (!len) { + // value + v->type = VALUE; + v->value = rv; + rt->nr_entries++; + } else { + // prefix -> value + struct prefix_chain *pc = zalloc(sizeof(*pc) + len); + if (!pc) + return false; + + pc->child.type = VALUE; + pc->child.value = rv; + pc->len = len; + memcpy(pc->prefix, kb, len); + v->type = PREFIX_CHAIN; + v->value.ptr = pc; + rt->nr_entries++; + } + + return true; +} + +static bool _insert_value(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + unsigned len = ke - kb; + + if (!len) + // overwrite + v->value = rv; + + else { + // value_chain -> value + struct value_chain *vc = zalloc(sizeof(*vc)); + if (!vc) + return false; + + vc->value = v->value; + if (!_insert(rt, &vc->child, kb, ke, rv)) { + free(vc); + return false; + } + + v->type = VALUE_CHAIN; + v->value.ptr = vc; + } + + return true; +} + +static bool _insert_value_chain(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct value_chain *vc = v->value.ptr; + return _insert(rt, &vc->child, kb, ke, rv); +} + +static unsigned min(unsigned lhs, unsigned rhs) +{ + if (lhs <= rhs) + return lhs; + else + return rhs; +} + +static bool _insert_prefix_chain(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct prefix_chain *pc = v->value.ptr; + + if (!pc->len) { + v->type = VALUE; + v->value = rv; + + } else if (*kb == pc->prefix[0]) { + // There's a common prefix let's split the chain into two and + // recurse. + struct prefix_chain *pc2; + unsigned i, len = min(pc->len, ke - kb); + + for (i = 0; i < len; i++) + if (kb[i] != pc->prefix[i]) + break; + + pc2 = zalloc(sizeof(*pc2) + pc->len - i); + pc2->len = pc->len - i; + memmove(pc2->prefix, pc->prefix + i, pc2->len); + pc2->child = pc->child; + + // FIXME: this trashes pc so we can't back out + pc->child.type = PREFIX_CHAIN; + pc->child.value.ptr = pc2; + pc->len = i; + + if (!_insert(rt, &pc->child, kb + i, ke, rv)) { + free(pc2); + return false; + } + + } else { + // Stick an n4 in front. + struct node4 *n4 = zalloc(sizeof(*n4)); + if (!n4) + return false; + + n4->keys[0] = pc->prefix[0]; + if (pc->len == 1) { + n4->values[0] = pc->child; + free(pc); + } else { + memmove(pc->prefix, pc->prefix + 1, pc->len - 1); + pc->len--; + n4->values[0] = *v; + } + + n4->keys[1] = *kb; + if (!_insert(rt, n4->values + 1, kb + 1, ke, rv)) { + free(n4); + return false; + } + + n4->nr_entries = 2; + + v->type = NODE4; + v->value.ptr = n4; + } + + return true; +} + +static bool _insert_node4(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node4 *n4 = v->value.ptr; + if (n4->nr_entries == 4) { + struct node16 *n16 = zalloc(sizeof(*n16)); + if (!n16) + return false; + + n16->nr_entries = 5; + memcpy(n16->keys, n4->keys, sizeof(n4->keys)); + memcpy(n16->values, n4->values, sizeof(n4->values)); + + n16->keys[4] = *kb; + if (!_insert(rt, n16->values + 4, kb + 1, ke, rv)) { + free(n16); + return false; + } + free(n4); + v->type = NODE16; + v->value.ptr = n16; + } else { + if (!_insert(rt, n4->values + n4->nr_entries, kb + 1, ke, rv)) + return false; + + n4->keys[n4->nr_entries] = *kb; + n4->nr_entries++; + } + return true; +} + +static bool _insert_node16(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node16 *n16 = v->value.ptr; + + if (n16->nr_entries == 16) { + unsigned i; + struct node48 *n48 = zalloc(sizeof(*n48)); + + if (!n48) + return false; + + n48->nr_entries = 17; + memset(n48->keys, 48, sizeof(n48->keys)); + + for (i = 0; i < 16; i++) { + n48->keys[n16->keys[i]] = i; + n48->values[i] = n16->values[i]; + } + + n48->keys[*kb] = 16; + if (!_insert(rt, n48->values + 16, kb + 1, ke, rv)) { + free(n48); + return false; + } + + free(n16); + v->type = NODE48; + v->value.ptr = n48; + } else { + if (!_insert(rt, n16->values + n16->nr_entries, kb + 1, ke, rv)) + return false; + n16->keys[n16->nr_entries] = *kb; + n16->nr_entries++; + } + + return true; +} + +static bool _insert_node48(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node48 *n48 = v->value.ptr; + if (n48->nr_entries == 48) { + unsigned i; + struct node256 *n256 = zalloc(sizeof(*n256)); + if (!n256) + return false; + + n256->nr_entries = 49; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) + n256->values[i] = n48->values[n48->keys[i]]; + } + + if (!_insert(rt, n256->values + *kb, kb + 1, ke, rv)) { + free(n256); + return false; + } + + free(n48); + v->type = NODE256; + v->value.ptr = n256; + + } else { + if (!_insert(rt, n48->values + n48->nr_entries, kb + 1, ke, rv)) + return false; + + n48->keys[*kb] = n48->nr_entries; + n48->nr_entries++; + } + + return true; +} + +static bool _insert_node256(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node256 *n256 = v->value.ptr; + bool r, was_unset = n256->values[*kb].type == UNSET; + + r = _insert(rt, n256->values + *kb, kb + 1, ke, rv); + if (r && was_unset) + n256->nr_entries++; + + return r; +} + +// FIXME: the tree should not be touched if insert fails (eg, OOM) +static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + if (kb == ke) { + if (v->type == UNSET) { + v->type = VALUE; + v->value = rv; + rt->nr_entries++; + + } else if (v->type == VALUE) { + v->value = rv; + + } else { + struct value_chain *vc = zalloc(sizeof(*vc)); + if (!vc) + return false; + + vc->value = rv; + vc->child = *v; + v->type = VALUE_CHAIN; + v->value.ptr = vc; + rt->nr_entries++; + } + return true; + } + + switch (v->type) { + case UNSET: + return _insert_unset(rt, v, kb, ke, rv); + + case VALUE: + return _insert_value(rt, v, kb, ke, rv); + + case VALUE_CHAIN: + return _insert_value_chain(rt, v, kb, ke, rv); + + case PREFIX_CHAIN: + return _insert_prefix_chain(rt, v, kb, ke, rv); + + case NODE4: + return _insert_node4(rt, v, kb, ke, rv); + + case NODE16: + return _insert_node16(rt, v, kb, ke, rv); + + case NODE48: + return _insert_node48(rt, v, kb, ke, rv); + + case NODE256: + return _insert_node256(rt, v, kb, ke, rv); + } + + // can't get here + return false; +} + +struct lookup_result { + struct value *v; + uint8_t *kb; +}; + +static struct lookup_result _lookup_prefix(struct value *v, uint8_t *kb, uint8_t *ke) +{ + unsigned i; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (kb == ke) + return (struct lookup_result) {.v = v, .kb = kb}; + + switch (v->type) { + case UNSET: + case VALUE: + break; + + case VALUE_CHAIN: + vc = v->value.ptr; + return _lookup_prefix(&vc->child, kb, ke); + + case PREFIX_CHAIN: + pc = v->value.ptr; + if (ke - kb < pc->len) + return (struct lookup_result) {.v = v, .kb = kb}; + + for (i = 0; i < pc->len; i++) + if (kb[i] != pc->prefix[i]) + return (struct lookup_result) {.v = v, .kb = kb}; + + return _lookup_prefix(&pc->child, kb + pc->len, ke); + + case NODE4: + n4 = v->value.ptr; + for (i = 0; i < n4->nr_entries; i++) + if (n4->keys[i] == *kb) + return _lookup_prefix(n4->values + i, kb + 1, ke); + break; + + case NODE16: + // FIXME: use binary search or simd? + n16 = v->value.ptr; + for (i = 0; i < n16->nr_entries; i++) + if (n16->keys[i] == *kb) + return _lookup_prefix(n16->values + i, kb + 1, ke); + break; + + case NODE48: + n48 = v->value.ptr; + i = n48->keys[*kb]; + if (i < 48) + return _lookup_prefix(n48->values + i, kb + 1, ke); + break; + + case NODE256: + n256 = v->value.ptr; + if (n256->values[*kb].type != UNSET) + return _lookup_prefix(n256->values + *kb, kb + 1, ke); + break; + } + + return (struct lookup_result) {.v = v, .kb = kb}; +} + +bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); + return _insert(rt, lr.v, lr.kb, ke, rv); +} + +// Note the degrade functions also free the original node. +static void _degrade_to_n4(struct node16 *n16, struct value *result) +{ + struct node4 *n4 = zalloc(sizeof(*n4)); + + n4->nr_entries = n16->nr_entries; + memcpy(n4->keys, n16->keys, n16->nr_entries * sizeof(*n4->keys)); + memcpy(n4->values, n16->values, n16->nr_entries * sizeof(*n4->values)); + free(n16); + + result->type = NODE4; + result->value.ptr = n4; +} + +static void _degrade_to_n16(struct node48 *n48, struct value *result) +{ + unsigned i, count = 0; + struct node16 *n16 = zalloc(sizeof(*n16)); + + n16->nr_entries = n48->nr_entries; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) { + n16->keys[count] = i; + count++; + } + } + + memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values)); + + free(n48); + + result->type = NODE16; + result->value.ptr = n16; +} + +static void _degrade_to_n48(struct node256 *n256, struct value *result) +{ + unsigned i, count = 0; + struct node48 *n48 = zalloc(sizeof(*n48)); + + memset(n48->keys, 48, sizeof(n48->keys)); + + n48->nr_entries = n256->nr_entries; + for (i = 0; i < 256; i++) { + if (n256->values[i].type == UNSET) + continue; + + n48->keys[i] = count; + n48->values[count] = n256->values[i]; + count++; + } + + free(n256); + + result->type = NODE48; + result->value.ptr = n48; +} + +// Removes an entry in an array by sliding the values above it down. +static void _erase_elt(void *array, unsigned obj_size, unsigned count, unsigned index) +{ + if (index == (count - 1)) + // The simple case + return; + + memmove(((uint8_t *) array) + (obj_size * index), + ((uint8_t *) array) + (obj_size * (index + 1)), + obj_size * (count - index - 1)); + + // Zero the now unused last elt (set's v.type to UNSET) + memset(((uint8_t *) array) + (count - 1) * obj_size, 0, obj_size); +} + +static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke) +{ + bool r; + unsigned i, j; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (kb == ke) { + if (root->type == VALUE) { + root->type = UNSET; + _dtr(rt, root->value); + return true; + + } else if (root->type == VALUE_CHAIN) { + vc = root->value.ptr; + _dtr(rt, vc->value); + memcpy(root, &vc->child, sizeof(*root)); + free(vc); + return true; + + } else + return false; + } + + switch (root->type) { + case UNSET: + case VALUE: + // this is a value for a prefix of the key + return false; + + case VALUE_CHAIN: + vc = root->value.ptr; + r = _remove(rt, &vc->child, kb, ke); + if (r && (vc->child.type == UNSET)) { + root->type = VALUE; + root->value = vc->value; + free(vc); + } + return r; + + case PREFIX_CHAIN: + pc = root->value.ptr; + if (ke - kb < pc->len) + return false; + + for (i = 0; i < pc->len; i++) + if (kb[i] != pc->prefix[i]) + return false; + + r = _remove(rt, &pc->child, kb + pc->len, ke); + if (r && pc->child.type == UNSET) { + root->type = UNSET; + free(pc); + } + return r; + + case NODE4: + n4 = root->value.ptr; + for (i = 0; i < n4->nr_entries; i++) { + if (n4->keys[i] == *kb) { + r = _remove(rt, n4->values + i, kb + 1, ke); + if (r && n4->values[i].type == UNSET) { + if (i < n4->nr_entries) { + _erase_elt(n4->keys, sizeof(*n4->keys), n4->nr_entries, i); + _erase_elt(n4->values, sizeof(*n4->values), n4->nr_entries, i); + } + + n4->nr_entries--; + if (!n4->nr_entries) { + free(n4); + root->type = UNSET; + } + } + return r; + } + } + return false; + + case NODE16: + n16 = root->value.ptr; + for (i = 0; i < n16->nr_entries; i++) { + if (n16->keys[i] == *kb) { + r = _remove(rt, n16->values + i, kb + 1, ke); + if (r && n16->values[i].type == UNSET) { + if (i < n16->nr_entries) { + _erase_elt(n16->keys, sizeof(*n16->keys), n16->nr_entries, i); + _erase_elt(n16->values, sizeof(*n16->values), n16->nr_entries, i); + } + + n16->nr_entries--; + if (n16->nr_entries <= 4) { + _degrade_to_n4(n16, root); + } + } + return r; + } + } + return false; + + case NODE48: + n48 = root->value.ptr; + i = n48->keys[*kb]; + if (i < 48) { + r = _remove(rt, n48->values + i, kb + 1, ke); + if (r && n48->values[i].type == UNSET) { + n48->keys[*kb] = 48; + for (j = 0; j < 256; j++) + if (n48->keys[j] < 48 && n48->keys[j] > i) + n48->keys[j]--; + _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); + n48->nr_entries--; + if (n48->nr_entries <= 16) + _degrade_to_n16(n48, root); + } + return r; + } + return false; + + case NODE256: + n256 = root->value.ptr; + r = _remove(rt, n256->values + (*kb), kb + 1, ke); + if (r && n256->values[*kb].type == UNSET) { + n256->nr_entries--; + if (n256->nr_entries <= 48) + _degrade_to_n48(n256, root); + } + return r; + } + + return false; +} + +bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_end) +{ + if (_remove(rt, &rt->root, key_begin, key_end)) { + rt->nr_entries--; + return true; + } + + return false; +} + +//---------------------------------------------------------------- + +static bool _prefix_chain_matches(struct lookup_result *lr, uint8_t *ke) +{ + // It's possible the top node is a prefix chain, and + // the remaining key matches part of it. + if (lr->v->type == PREFIX_CHAIN) { + unsigned i, rlen = ke - lr->kb; + struct prefix_chain *pc = lr->v->value.ptr; + if (rlen < pc->len) { + for (i = 0; i < rlen; i++) + if (pc->prefix[i] != lr->kb[i]) + return false; + return true; + } + } + + return false; +} + +static bool _remove_subtree(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke, unsigned *count) +{ + bool r; + unsigned i, j, len; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (kb == ke) { + *count += _free_node(rt, *root); + root->type = UNSET; + return true; + } + + switch (root->type) { + case UNSET: + case VALUE: + // No entries with the given prefix + return true; + + case VALUE_CHAIN: + vc = root->value.ptr; + r = _remove_subtree(rt, &vc->child, kb, ke, count); + if (r && (vc->child.type == UNSET)) { + root->type = VALUE; + root->value = vc->value; + free(vc); + } + return r; + + case PREFIX_CHAIN: + pc = root->value.ptr; + len = min(pc->len, ke - kb); + for (i = 0; i < len; i++) + if (kb[i] != pc->prefix[i]) + return true; + + r = _remove_subtree(rt, &pc->child, len < pc->len ? ke : (kb + pc->len), ke, count); + if (r && pc->child.type == UNSET) { + root->type = UNSET; + free(pc); + } + return r; + + case NODE4: + n4 = root->value.ptr; + for (i = 0; i < n4->nr_entries; i++) { + if (n4->keys[i] == *kb) { + r = _remove_subtree(rt, n4->values + i, kb + 1, ke, count); + if (r && n4->values[i].type == UNSET) { + if (i < n4->nr_entries) { + _erase_elt(n4->keys, sizeof(*n4->keys), n4->nr_entries, i); + _erase_elt(n4->values, sizeof(*n4->values), n4->nr_entries, i); + } + + n4->nr_entries--; + if (!n4->nr_entries) { + free(n4); + root->type = UNSET; + } + } + return r; + } + } + return true; + + case NODE16: + n16 = root->value.ptr; + for (i = 0; i < n16->nr_entries; i++) { + if (n16->keys[i] == *kb) { + r = _remove_subtree(rt, n16->values + i, kb + 1, ke, count); + if (r && n16->values[i].type == UNSET) { + if (i < n16->nr_entries) { + _erase_elt(n16->keys, sizeof(*n16->keys), n16->nr_entries, i); + _erase_elt(n16->values, sizeof(*n16->values), n16->nr_entries, i); + } + + n16->nr_entries--; + if (n16->nr_entries <= 4) + _degrade_to_n4(n16, root); + } + return r; + } + } + return true; + + case NODE48: + n48 = root->value.ptr; + i = n48->keys[*kb]; + if (i < 48) { + r = _remove_subtree(rt, n48->values + i, kb + 1, ke, count); + if (r && n48->values[i].type == UNSET) { + n48->keys[*kb] = 48; + for (j = 0; j < 256; j++) + if (n48->keys[j] < 48 && n48->keys[j] > i) + n48->keys[j]--; + _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); + n48->nr_entries--; + if (n48->nr_entries <= 16) + _degrade_to_n16(n48, root); + } + return r; + } + return true; + + case NODE256: + n256 = root->value.ptr; + if (n256->values[*kb].type == UNSET) + return true; // No entries + + r = _remove_subtree(rt, n256->values + (*kb), kb + 1, ke, count); + if (r && n256->values[*kb].type == UNSET) { + n256->nr_entries--; + if (n256->nr_entries <= 48) + _degrade_to_n48(n256, root); + } + return r; + } + + // Shouldn't get here + return false; +} + +unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) +{ + unsigned count = 0; + + if (_remove_subtree(rt, &rt->root, kb, ke, &count)) + rt->nr_entries -= count; + + return count; +} + +//---------------------------------------------------------------- + +bool radix_tree_lookup(struct radix_tree *rt, + uint8_t *kb, uint8_t *ke, union radix_value *result) +{ + struct value_chain *vc; + struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); + if (lr.kb == ke) { + switch (lr.v->type) { + case VALUE: + *result = lr.v->value; + return true; + + case VALUE_CHAIN: + vc = lr.v->value.ptr; + *result = vc->value; + return true; + + default: + return false; + } + } + + return false; +} + +// FIXME: build up the keys too +static bool _iterate(struct value *v, struct radix_tree_iterator *it) +{ + unsigned i; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + switch (v->type) { + case UNSET: + // can't happen + break; + + case VALUE: + return it->visit(it, NULL, NULL, v->value); + + case VALUE_CHAIN: + vc = v->value.ptr; + return it->visit(it, NULL, NULL, vc->value) && _iterate(&vc->child, it); + + case PREFIX_CHAIN: + pc = v->value.ptr; + return _iterate(&pc->child, it); + + case NODE4: + n4 = (struct node4 *) v->value.ptr; + for (i = 0; i < n4->nr_entries; i++) + if (!_iterate(n4->values + i, it)) + return false; + return true; + + case NODE16: + n16 = (struct node16 *) v->value.ptr; + for (i = 0; i < n16->nr_entries; i++) + if (!_iterate(n16->values + i, it)) + return false; + return true; + + case NODE48: + n48 = (struct node48 *) v->value.ptr; + for (i = 0; i < n48->nr_entries; i++) + if (!_iterate(n48->values + i, it)) + return false; + return true; + + case NODE256: + n256 = (struct node256 *) v->value.ptr; + for (i = 0; i < 256; i++) + if (n256->values[i].type != UNSET && !_iterate(n256->values + i, it)) + return false; + return true; + } + + // can't get here + return false; +} + +void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, + struct radix_tree_iterator *it) +{ + struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); + if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) + _iterate(lr.v, it); +} + +//---------------------------------------------------------------- +// Checks: +// 1) The number of entries matches rt->nr_entries +// 2) The number of entries is correct in each node +// 3) prefix chain len > 0 +// 4) all unused values are UNSET + +static bool _check_nodes(struct value *v, unsigned *count) +{ + unsigned i, ncount; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + switch (v->type) { + case UNSET: + return true; + + case VALUE: + (*count)++; + return true; + + case VALUE_CHAIN: + (*count)++; + vc = v->value.ptr; + return _check_nodes(&vc->child, count); + + case PREFIX_CHAIN: + pc = v->value.ptr; + return _check_nodes(&pc->child, count); + + case NODE4: + n4 = v->value.ptr; + for (i = 0; i < n4->nr_entries; i++) + if (!_check_nodes(n4->values + i, count)) + return false; + + for (i = n4->nr_entries; i < 4; i++) + if (n4->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET (n4)\n"); + return false; + } + + return true; + + case NODE16: + n16 = v->value.ptr; + for (i = 0; i < n16->nr_entries; i++) + if (!_check_nodes(n16->values + i, count)) + return false; + + for (i = n16->nr_entries; i < 16; i++) + if (n16->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET (n16)\n"); + return false; + } + + return true; + + case NODE48: + n48 = v->value.ptr; + ncount = 0; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) { + ncount++; + if (!_check_nodes(n48->values + n48->keys[i], count)) + return false; + } + } + + if (ncount != n48->nr_entries) { + fprintf(stderr, "incorrect number of entries in n48, n48->nr_entries = %u, actual = %u\n", + n48->nr_entries, ncount); + return false; + } + + for (i = n48->nr_entries; i < 48; i++) + if (n48->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET (n48)\n"); + return false; + } + + return true; + + case NODE256: + n256 = v->value.ptr; + + ncount = 0; + for (i = 0; i < 256; i++) { + struct value *v2 = n256->values + i; + + if (v2->type == UNSET) + continue; + + if (!_check_nodes(v2, count)) + return false; + + ncount++; + } + + if (ncount != n256->nr_entries) { + fprintf(stderr, "incorrect number of entries in n256, n256->nr_entries = %u, actual = %u\n", + n256->nr_entries, ncount); + return false; + } + + return true; + + default: + fprintf(stderr, "unknown value type: %u\n", v->type); + } + + fprintf(stderr, "shouldn't get here\n"); + return false; +} + +bool radix_tree_is_well_formed(struct radix_tree *rt) +{ + unsigned count = 0; + + if (!_check_nodes(&rt->root, &count)) + return false; + + if (rt->nr_entries != count) { + fprintf(stderr, "incorrect entry count: rt->nr_entries = %u, actual = %u\n", + rt->nr_entries, count); + return false; + } + + return true; +} + +//---------------------------------------------------------------- + +static void _dump(FILE *out, struct value v, unsigned indent) +{ + unsigned i; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (v.type == UNSET) + return; + + for (i = 0; i < 2 * indent; i++) + fprintf(out, " "); + + switch (v.type) { + case UNSET: + // can't happen + break; + + case VALUE: + fprintf(out, "<val: %llu>\n", (unsigned long long) v.value.n); + break; + + case VALUE_CHAIN: + vc = v.value.ptr; + fprintf(out, "<val_chain: %llu>\n", (unsigned long long) vc->value.n); + _dump(out, vc->child, indent + 1); + break; + + case PREFIX_CHAIN: + pc = v.value.ptr; + fprintf(out, "<prefix: "); + for (i = 0; i < pc->len; i++) + fprintf(out, "%x.", (unsigned) *(pc->prefix + i)); + fprintf(out, ">\n"); + _dump(out, pc->child, indent + 1); + break; + + case NODE4: + n4 = v.value.ptr; + fprintf(out, "<n4: "); + for (i = 0; i < n4->nr_entries; i++) + fprintf(out, "%x ", (unsigned) n4->keys[i]); + fprintf(out, ">\n"); + + for (i = 0; i < n4->nr_entries; i++) + _dump(out, n4->values[i], indent + 1); + break; + + case NODE16: + n16 = v.value.ptr; + fprintf(out, "<n16: "); + for (i = 0; i < n16->nr_entries; i++) + fprintf(out, "%x ", (unsigned) n16->keys[i]); + fprintf(out, ">\n"); + + for (i = 0; i < n16->nr_entries; i++) + _dump(out, n16->values[i], indent + 1); + break; + + case NODE48: + n48 = v.value.ptr; + fprintf(out, "<n48: "); + for (i = 0; i < 256; i++) + if (n48->keys[i] < 48) + fprintf(out, "%x ", i); + fprintf(out, ">\n"); + + for (i = 0; i < 256; i++) + if (n48->keys[i] < 48) + _dump(out, n48->values[i], indent + 1); + break; + + case NODE256: + n256 = v.value.ptr; + fprintf(out, "<n256: "); + for (i = 0; i < 256; i++) + if (n256->values[i].type != UNSET) + fprintf(out, "%x ", i); + fprintf(out, ">\n"); + + for (i = 0; i < 256; i++) + if (n256->values[i].type != UNSET) + _dump(out, n256->values[i], indent + 1); + break; + } +} + +void radix_tree_dump(struct radix_tree *rt, FILE *out) +{ + _dump(out, rt->root, 0); +} + +//---------------------------------------------------------------- diff --git a/base/data-struct/radix-tree-simple.c b/base/data-struct/radix-tree-simple.c new file mode 100644 index 0000000..e8a2fdd --- /dev/null +++ b/base/data-struct/radix-tree-simple.c @@ -0,0 +1,256 @@ +// Copyright (C) 2018 Red Hat, Inc. All rights reserved. +// +// This file is part of LVM2. +// +// This copyrighted material is made available to anyone wishing to use, +// modify, copy, or redistribute it subject to the terms and conditions +// of the GNU Lesser General Public License v.2.1. +// +// You should have received a copy of the GNU Lesser General Public License +// along with this program; if not, write to the Free Software Foundation, +// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA + +#include "radix-tree.h" + +#include "base/memory/container_of.h" +#include "base/memory/zalloc.h" + +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> + +//---------------------------------------------------------------- +// This implementation is based around nested binary trees. Very +// simple (and hopefully correct). + +struct node { + struct node *left; + struct node *right; + + uint8_t key; + struct node *center; + + bool has_value; + union radix_value value; +}; + +struct radix_tree { + radix_value_dtr dtr; + void *dtr_context; + + struct node *root; +}; + +struct radix_tree * +radix_tree_create(radix_value_dtr dtr, void *dtr_context) +{ + struct radix_tree *rt = zalloc(sizeof(*rt)); + + if (rt) { + rt->dtr = dtr; + rt->dtr_context = dtr_context; + } + + return rt; +} + +// Returns the number of entries in the tree +static unsigned _destroy_tree(struct node *n, radix_value_dtr dtr, void *context) +{ + unsigned r; + + if (!n) + return 0; + + r = _destroy_tree(n->left, dtr, context); + r += _destroy_tree(n->right, dtr, context); + r += _destroy_tree(n->center, dtr, context); + + if (n->has_value) { + if (dtr) + dtr(context, n->value); + r++; + } + + free(n); + + return r; +} + +void radix_tree_destroy(struct radix_tree *rt) +{ + _destroy_tree(rt->root, rt->dtr, rt->dtr_context); + free(rt); +} + +static unsigned _count(struct node *n) +{ + unsigned r; + + if (!n) + return 0; + + r = _count(n->left); + r += _count(n->right); + r += _count(n->center); + + if (n->has_value) + r++; + + return r; +} + +unsigned radix_tree_size(struct radix_tree *rt) +{ + return _count(rt->root); +} + +static struct node **_lookup(struct node **pn, uint8_t *kb, uint8_t *ke) +{ + struct node *n = *pn; + + if (!n || (kb == ke)) + return pn; + + if (*kb < n->key) + return _lookup(&n->left, kb, ke); + + else if (*kb > n->key) + return _lookup(&n->right, kb, ke); + + else + return _lookup(&n->center, kb + 1, ke); +} + +static bool _insert(struct node **pn, uint8_t *kb, uint8_t *ke, union radix_value v) +{ + struct node *n = *pn; + + if (!n) { + n = zalloc(sizeof(*n)); + if (!n) + return false; + + n->key = *kb; + *pn = n; + } + + if (kb == ke) { + n->has_value = true; + n->value = v; + return true; + } + + if (*kb < n->key) + return _insert(&n->left, kb, ke, v); + + else if (*kb > n->key) + return _insert(&n->right, kb, ke, v); + + else + return _insert(&n->center, kb + 1, ke, v); +} + +bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value v) +{ + return _insert(&rt->root, kb, ke, v); +} + +bool radix_tree_remove(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) +{ + struct node **pn = _lookup(&rt->root, kb, ke); + struct node *n = *pn; + + if (!n || !n->has_value) + return false; + + else { + if (rt->dtr) + rt->dtr(rt->dtr_context, n->value); + + if (n->left || n->center || n->right) { + n->has_value = false; + return true; + + } else { + // FIXME: delete parent if this was the last entry + free(n); + *pn = NULL; + } + + return true; + } +} + +unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) +{ + struct node **pn; + unsigned count; + + pn = _lookup(&rt->root, kb, ke); + + if (*pn) { + count = _destroy_tree(*pn, rt->dtr, rt->dtr_context); + *pn = NULL; + } + + return count; +} + +bool +radix_tree_lookup(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value *result) +{ + struct node **pn = _lookup(&rt->root, kb, ke); + struct node *n = *pn; + + if (n && n->has_value) { + *result = n->value; + return true; + } else + return false; +} + +static void _iterate(struct node *n, struct radix_tree_iterator *it) +{ + if (!n) + return; + + _iterate(n->left, it); + + if (n->has_value) + // FIXME: fill out the key + it->visit(it, NULL, NULL, n->value); + + _iterate(n->center, it); + _iterate(n->right, it); +} + +void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, + struct radix_tree_iterator *it) +{ + if (kb == ke) + _iterate(rt->root, it); + + else { + struct node **pn = _lookup(&rt->root, kb, ke); + struct node *n = *pn; + + if (n) { + if (n->has_value) + it->visit(it, NULL, NULL, n->value); + _iterate(n->center, it); + } + } +} + +bool radix_tree_is_well_formed(struct radix_tree *rt) +{ + return true; +} + +void radix_tree_dump(struct radix_tree *rt, FILE *out) +{ +} + +//---------------------------------------------------------------- + diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index 1eef1f8..52a1a05 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -10,1253 +10,12 @@ // along with this program; if not, write to the Free Software Foundation, // Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA -#include "radix-tree.h" - -#include "base/memory/container_of.h" -#include "base/memory/zalloc.h" - -#include <assert.h> -#include <stdlib.h> -#include <stdio.h> - //---------------------------------------------------------------- -enum node_type { - UNSET = 0, - VALUE, - VALUE_CHAIN, - PREFIX_CHAIN, - NODE4, - NODE16, - NODE48, - NODE256 -}; - -struct value { - enum node_type type; - union radix_value value; -}; - -// This is used for entries that have a key which is a prefix of another key. -struct value_chain { - union radix_value value; - struct value child; -}; - -struct prefix_chain { - struct value child; - unsigned len; - uint8_t prefix[0]; -}; - -struct node4 { - uint32_t nr_entries; - uint8_t keys[4]; - struct value values[4]; -}; - -struct node16 { - uint32_t nr_entries; - uint8_t keys[16]; - struct value values[16]; -}; - -struct node48 { - uint32_t nr_entries; - uint8_t keys[256]; - struct value values[48]; -}; - -struct node256 { - uint32_t nr_entries; - struct value values[256]; -}; - -struct radix_tree { - unsigned nr_entries; - struct value root; - radix_value_dtr dtr; - void *dtr_context; -}; - -//---------------------------------------------------------------- - -struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context) -{ - struct radix_tree *rt = malloc(sizeof(*rt)); - - if (rt) { - rt->nr_entries = 0; - rt->root.type = UNSET; - rt->dtr = dtr; - rt->dtr_context = dtr_context; - } - - return rt; -} - -static inline void _dtr(struct radix_tree *rt, union radix_value v) -{ - if (rt->dtr) - rt->dtr(rt->dtr_context, v); -} - -// Returns the number of values removed -static unsigned _free_node(struct radix_tree *rt, struct value v) -{ - unsigned i, nr = 0; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - switch (v.type) { - case UNSET: - break; - - case VALUE: - _dtr(rt, v.value); - nr = 1; - break; - - case VALUE_CHAIN: - vc = v.value.ptr; - _dtr(rt, vc->value); - nr = 1 + _free_node(rt, vc->child); - free(vc); - break; - - case PREFIX_CHAIN: - pc = v.value.ptr; - nr = _free_node(rt, pc->child); - free(pc); - break; - - case NODE4: - n4 = (struct node4 *) v.value.ptr; - for (i = 0; i < n4->nr_entries; i++) - nr += _free_node(rt, n4->values[i]); - free(n4); - break; - - case NODE16: - n16 = (struct node16 *) v.value.ptr; - for (i = 0; i < n16->nr_entries; i++) - nr += _free_node(rt, n16->values[i]); - free(n16); - break; - - case NODE48: - n48 = (struct node48 *) v.value.ptr; - for (i = 0; i < n48->nr_entries; i++) - nr += _free_node(rt, n48->values[i]); - free(n48); - break; - - case NODE256: - n256 = (struct node256 *) v.value.ptr; - for (i = 0; i < 256; i++) - nr += _free_node(rt, n256->values[i]); - free(n256); - break; - } - - return nr; -} - -void radix_tree_destroy(struct radix_tree *rt) -{ - _free_node(rt, rt->root); - free(rt); -} - -unsigned radix_tree_size(struct radix_tree *rt) -{ - return rt->nr_entries; -} - -static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv); - -static bool _insert_unset(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - unsigned len = ke - kb; - - if (!len) { - // value - v->type = VALUE; - v->value = rv; - rt->nr_entries++; - } else { - // prefix -> value - struct prefix_chain *pc = zalloc(sizeof(*pc) + len); - if (!pc) - return false; - - pc->child.type = VALUE; - pc->child.value = rv; - pc->len = len; - memcpy(pc->prefix, kb, len); - v->type = PREFIX_CHAIN; - v->value.ptr = pc; - rt->nr_entries++; - } - - return true; -} - -static bool _insert_value(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - unsigned len = ke - kb; - - if (!len) - // overwrite - v->value = rv; - - else { - // value_chain -> value - struct value_chain *vc = zalloc(sizeof(*vc)); - if (!vc) - return false; - - vc->value = v->value; - if (!_insert(rt, &vc->child, kb, ke, rv)) { - free(vc); - return false; - } - - v->type = VALUE_CHAIN; - v->value.ptr = vc; - } - - return true; -} - -static bool _insert_value_chain(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct value_chain *vc = v->value.ptr; - return _insert(rt, &vc->child, kb, ke, rv); -} - -static unsigned min(unsigned lhs, unsigned rhs) -{ - if (lhs <= rhs) - return lhs; - else - return rhs; -} - -static bool _insert_prefix_chain(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct prefix_chain *pc = v->value.ptr; - - if (!pc->len) { - v->type = VALUE; - v->value = rv; - - } else if (*kb == pc->prefix[0]) { - // There's a common prefix let's split the chain into two and - // recurse. - struct prefix_chain *pc2; - unsigned i, len = min(pc->len, ke - kb); - - for (i = 0; i < len; i++) - if (kb[i] != pc->prefix[i]) - break; - - pc2 = zalloc(sizeof(*pc2) + pc->len - i); - pc2->len = pc->len - i; - memmove(pc2->prefix, pc->prefix + i, pc2->len); - pc2->child = pc->child; - - // FIXME: this trashes pc so we can't back out - pc->child.type = PREFIX_CHAIN; - pc->child.value.ptr = pc2; - pc->len = i; - - if (!_insert(rt, &pc->child, kb + i, ke, rv)) { - free(pc2); - return false; - } - - } else { - // Stick an n4 in front. - struct node4 *n4 = zalloc(sizeof(*n4)); - if (!n4) - return false; - - n4->keys[0] = pc->prefix[0]; - if (pc->len == 1) { - n4->values[0] = pc->child; - free(pc); - } else { - memmove(pc->prefix, pc->prefix + 1, pc->len - 1); - pc->len--; - n4->values[0] = *v; - } - - n4->keys[1] = *kb; - if (!_insert(rt, n4->values + 1, kb + 1, ke, rv)) { - free(n4); - return false; - } - - n4->nr_entries = 2; - - v->type = NODE4; - v->value.ptr = n4; - } - - return true; -} - -static bool _insert_node4(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct node4 *n4 = v->value.ptr; - if (n4->nr_entries == 4) { - struct node16 *n16 = zalloc(sizeof(*n16)); - if (!n16) - return false; - - n16->nr_entries = 5; - memcpy(n16->keys, n4->keys, sizeof(n4->keys)); - memcpy(n16->values, n4->values, sizeof(n4->values)); - - n16->keys[4] = *kb; - if (!_insert(rt, n16->values + 4, kb + 1, ke, rv)) { - free(n16); - return false; - } - free(n4); - v->type = NODE16; - v->value.ptr = n16; - } else { - if (!_insert(rt, n4->values + n4->nr_entries, kb + 1, ke, rv)) - return false; - - n4->keys[n4->nr_entries] = *kb; - n4->nr_entries++; - } - return true; -} - -static bool _insert_node16(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct node16 *n16 = v->value.ptr; - - if (n16->nr_entries == 16) { - unsigned i; - struct node48 *n48 = zalloc(sizeof(*n48)); - - if (!n48) - return false; - - n48->nr_entries = 17; - memset(n48->keys, 48, sizeof(n48->keys)); - - for (i = 0; i < 16; i++) { - n48->keys[n16->keys[i]] = i; - n48->values[i] = n16->values[i]; - } - - n48->keys[*kb] = 16; - if (!_insert(rt, n48->values + 16, kb + 1, ke, rv)) { - free(n48); - return false; - } - - free(n16); - v->type = NODE48; - v->value.ptr = n48; - } else { - if (!_insert(rt, n16->values + n16->nr_entries, kb + 1, ke, rv)) - return false; - n16->keys[n16->nr_entries] = *kb; - n16->nr_entries++; - } - - return true; -} - -static bool _insert_node48(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct node48 *n48 = v->value.ptr; - if (n48->nr_entries == 48) { - unsigned i; - struct node256 *n256 = zalloc(sizeof(*n256)); - if (!n256) - return false; - - n256->nr_entries = 49; - for (i = 0; i < 256; i++) { - if (n48->keys[i] < 48) - n256->values[i] = n48->values[n48->keys[i]]; - } - - if (!_insert(rt, n256->values + *kb, kb + 1, ke, rv)) { - free(n256); - return false; - } - - free(n48); - v->type = NODE256; - v->value.ptr = n256; - - } else { - if (!_insert(rt, n48->values + n48->nr_entries, kb + 1, ke, rv)) - return false; - - n48->keys[*kb] = n48->nr_entries; - n48->nr_entries++; - } - - return true; -} - -static bool _insert_node256(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct node256 *n256 = v->value.ptr; - bool r, was_unset = n256->values[*kb].type == UNSET; - - r = _insert(rt, n256->values + *kb, kb + 1, ke, rv); - if (r && was_unset) - n256->nr_entries++; - - return r; -} - -// FIXME: the tree should not be touched if insert fails (eg, OOM) -static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - if (kb == ke) { - if (v->type == UNSET) { - v->type = VALUE; - v->value = rv; - rt->nr_entries++; - - } else if (v->type == VALUE) { - v->value = rv; - - } else { - struct value_chain *vc = zalloc(sizeof(*vc)); - if (!vc) - return false; - - vc->value = rv; - vc->child = *v; - v->type = VALUE_CHAIN; - v->value.ptr = vc; - rt->nr_entries++; - } - return true; - } - - switch (v->type) { - case UNSET: - return _insert_unset(rt, v, kb, ke, rv); - - case VALUE: - return _insert_value(rt, v, kb, ke, rv); - - case VALUE_CHAIN: - return _insert_value_chain(rt, v, kb, ke, rv); - - case PREFIX_CHAIN: - return _insert_prefix_chain(rt, v, kb, ke, rv); - - case NODE4: - return _insert_node4(rt, v, kb, ke, rv); - - case NODE16: - return _insert_node16(rt, v, kb, ke, rv); - - case NODE48: - return _insert_node48(rt, v, kb, ke, rv); - - case NODE256: - return _insert_node256(rt, v, kb, ke, rv); - } - - // can't get here - return false; -} - -struct lookup_result { - struct value *v; - uint8_t *kb; -}; - -static struct lookup_result _lookup_prefix(struct value *v, uint8_t *kb, uint8_t *ke) -{ - unsigned i; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - if (kb == ke) - return (struct lookup_result) {.v = v, .kb = kb}; - - switch (v->type) { - case UNSET: - case VALUE: - break; - - case VALUE_CHAIN: - vc = v->value.ptr; - return _lookup_prefix(&vc->child, kb, ke); - - case PREFIX_CHAIN: - pc = v->value.ptr; - if (ke - kb < pc->len) - return (struct lookup_result) {.v = v, .kb = kb}; - - for (i = 0; i < pc->len; i++) - if (kb[i] != pc->prefix[i]) - return (struct lookup_result) {.v = v, .kb = kb}; - - return _lookup_prefix(&pc->child, kb + pc->len, ke); - - case NODE4: - n4 = v->value.ptr; - for (i = 0; i < n4->nr_entries; i++) - if (n4->keys[i] == *kb) - return _lookup_prefix(n4->values + i, kb + 1, ke); - break; - - case NODE16: - // FIXME: use binary search or simd? - n16 = v->value.ptr; - for (i = 0; i < n16->nr_entries; i++) - if (n16->keys[i] == *kb) - return _lookup_prefix(n16->values + i, kb + 1, ke); - break; - - case NODE48: - n48 = v->value.ptr; - i = n48->keys[*kb]; - if (i < 48) - return _lookup_prefix(n48->values + i, kb + 1, ke); - break; - - case NODE256: - n256 = v->value.ptr; - if (n256->values[*kb].type != UNSET) - return _lookup_prefix(n256->values + *kb, kb + 1, ke); - break; - } - - return (struct lookup_result) {.v = v, .kb = kb}; -} - -bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); - return _insert(rt, lr.v, lr.kb, ke, rv); -} - -// Note the degrade functions also free the original node. -static void _degrade_to_n4(struct node16 *n16, struct value *result) -{ - struct node4 *n4 = zalloc(sizeof(*n4)); - - n4->nr_entries = n16->nr_entries; - memcpy(n4->keys, n16->keys, n16->nr_entries * sizeof(*n4->keys)); - memcpy(n4->values, n16->values, n16->nr_entries * sizeof(*n4->values)); - free(n16); - - result->type = NODE4; - result->value.ptr = n4; -} - -static void _degrade_to_n16(struct node48 *n48, struct value *result) -{ - unsigned i, count = 0; - struct node16 *n16 = zalloc(sizeof(*n16)); - - n16->nr_entries = n48->nr_entries; - for (i = 0; i < 256; i++) { - if (n48->keys[i] < 48) { - n16->keys[count] = i; - count++; - } - } - - memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values)); - - free(n48); - - result->type = NODE16; - result->value.ptr = n16; -} - -static void _degrade_to_n48(struct node256 *n256, struct value *result) -{ - unsigned i, count = 0; - struct node48 *n48 = zalloc(sizeof(*n48)); - - memset(n48->keys, 48, sizeof(n48->keys)); - - n48->nr_entries = n256->nr_entries; - for (i = 0; i < 256; i++) { - if (n256->values[i].type == UNSET) - continue; - - n48->keys[i] = count; - n48->values[count] = n256->values[i]; - count++; - } - - free(n256); - - result->type = NODE48; - result->value.ptr = n48; -} - -// Removes an entry in an array by sliding the values above it down. -static void _erase_elt(void *array, unsigned obj_size, unsigned count, unsigned index) -{ - if (index == (count - 1)) - // The simple case - return; - - memmove(((uint8_t *) array) + (obj_size * index), - ((uint8_t *) array) + (obj_size * (index + 1)), - obj_size * (count - index - 1)); - - // Zero the now unused last elt (set's v.type to UNSET) - memset(((uint8_t *) array) + (count - 1) * obj_size, 0, obj_size); -} - -static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke) -{ - bool r; - unsigned i, j; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - if (kb == ke) { - if (root->type == VALUE) { - root->type = UNSET; - _dtr(rt, root->value); - return true; - - } else if (root->type == VALUE_CHAIN) { - vc = root->value.ptr; - _dtr(rt, vc->value); - memcpy(root, &vc->child, sizeof(*root)); - free(vc); - return true; - - } else - return false; - } - - switch (root->type) { - case UNSET: - case VALUE: - // this is a value for a prefix of the key - return false; - - case VALUE_CHAIN: - vc = root->value.ptr; - r = _remove(rt, &vc->child, kb, ke); - if (r && (vc->child.type == UNSET)) { - root->type = VALUE; - root->value = vc->value; - free(vc); - } - return r; - - case PREFIX_CHAIN: - pc = root->value.ptr; - if (ke - kb < pc->len) - return false; - - for (i = 0; i < pc->len; i++) - if (kb[i] != pc->prefix[i]) - return false; - - r = _remove(rt, &pc->child, kb + pc->len, ke); - if (r && pc->child.type == UNSET) { - root->type = UNSET; - free(pc); - } - return r; - - case NODE4: - n4 = root->value.ptr; - for (i = 0; i < n4->nr_entries; i++) { - if (n4->keys[i] == *kb) { - r = _remove(rt, n4->values + i, kb + 1, ke); - if (r && n4->values[i].type == UNSET) { - if (i < n4->nr_entries) { - _erase_elt(n4->keys, sizeof(*n4->keys), n4->nr_entries, i); - _erase_elt(n4->values, sizeof(*n4->values), n4->nr_entries, i); - } - - n4->nr_entries--; - if (!n4->nr_entries) { - free(n4); - root->type = UNSET; - } - } - return r; - } - } - return false; - - case NODE16: - n16 = root->value.ptr; - for (i = 0; i < n16->nr_entries; i++) { - if (n16->keys[i] == *kb) { - r = _remove(rt, n16->values + i, kb + 1, ke); - if (r && n16->values[i].type == UNSET) { - if (i < n16->nr_entries) { - _erase_elt(n16->keys, sizeof(*n16->keys), n16->nr_entries, i); - _erase_elt(n16->values, sizeof(*n16->values), n16->nr_entries, i); - } - - n16->nr_entries--; - if (n16->nr_entries <= 4) { - _degrade_to_n4(n16, root); - } - } - return r; - } - } - return false; - - case NODE48: - n48 = root->value.ptr; - i = n48->keys[*kb]; - if (i < 48) { - r = _remove(rt, n48->values + i, kb + 1, ke); - if (r && n48->values[i].type == UNSET) { - n48->keys[*kb] = 48; - for (j = 0; j < 256; j++) - if (n48->keys[j] < 48 && n48->keys[j] > i) - n48->keys[j]--; - _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); - n48->nr_entries--; - if (n48->nr_entries <= 16) - _degrade_to_n16(n48, root); - } - return r; - } - return false; - - case NODE256: - n256 = root->value.ptr; - r = _remove(rt, n256->values + (*kb), kb + 1, ke); - if (r && n256->values[*kb].type == UNSET) { - n256->nr_entries--; - if (n256->nr_entries <= 48) - _degrade_to_n48(n256, root); - } - return r; - } - - return false; -} - -bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_end) -{ - if (_remove(rt, &rt->root, key_begin, key_end)) { - rt->nr_entries--; - return true; - } - - return false; -} - -//---------------------------------------------------------------- - -static bool _prefix_chain_matches(struct lookup_result *lr, uint8_t *ke) -{ - // It's possible the top node is a prefix chain, and - // the remaining key matches part of it. - if (lr->v->type == PREFIX_CHAIN) { - unsigned i, rlen = ke - lr->kb; - struct prefix_chain *pc = lr->v->value.ptr; - if (rlen < pc->len) { - for (i = 0; i < rlen; i++) - if (pc->prefix[i] != lr->kb[i]) - return false; - return true; - } - } - - return false; -} - -static bool _remove_subtree(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke, unsigned *count) -{ - bool r; - unsigned i, j, len; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - if (kb == ke) { - *count += _free_node(rt, *root); - root->type = UNSET; - return true; - } - - switch (root->type) { - case UNSET: - case VALUE: - // No entries with the given prefix - return true; - - case VALUE_CHAIN: - vc = root->value.ptr; - r = _remove_subtree(rt, &vc->child, kb, ke, count); - if (r && (vc->child.type == UNSET)) { - root->type = VALUE; - root->value = vc->value; - free(vc); - } - return r; - - case PREFIX_CHAIN: - pc = root->value.ptr; - len = min(pc->len, ke - kb); - for (i = 0; i < len; i++) - if (kb[i] != pc->prefix[i]) - return true; - - r = _remove_subtree(rt, &pc->child, len < pc->len ? ke : (kb + pc->len), ke, count); - if (r && pc->child.type == UNSET) { - root->type = UNSET; - free(pc); - } - return r; - - case NODE4: - n4 = root->value.ptr; - for (i = 0; i < n4->nr_entries; i++) { - if (n4->keys[i] == *kb) { - r = _remove_subtree(rt, n4->values + i, kb + 1, ke, count); - if (r && n4->values[i].type == UNSET) { - if (i < n4->nr_entries) { - _erase_elt(n4->keys, sizeof(*n4->keys), n4->nr_entries, i); - _erase_elt(n4->values, sizeof(*n4->values), n4->nr_entries, i); - } - - n4->nr_entries--; - if (!n4->nr_entries) { - free(n4); - root->type = UNSET; - } - } - return r; - } - } - return true; - - case NODE16: - n16 = root->value.ptr; - for (i = 0; i < n16->nr_entries; i++) { - if (n16->keys[i] == *kb) { - r = _remove_subtree(rt, n16->values + i, kb + 1, ke, count); - if (r && n16->values[i].type == UNSET) { - if (i < n16->nr_entries) { - _erase_elt(n16->keys, sizeof(*n16->keys), n16->nr_entries, i); - _erase_elt(n16->values, sizeof(*n16->values), n16->nr_entries, i); - } - - n16->nr_entries--; - if (n16->nr_entries <= 4) - _degrade_to_n4(n16, root); - } - return r; - } - } - return true; - - case NODE48: - n48 = root->value.ptr; - i = n48->keys[*kb]; - if (i < 48) { - r = _remove_subtree(rt, n48->values + i, kb + 1, ke, count); - if (r && n48->values[i].type == UNSET) { - n48->keys[*kb] = 48; - for (j = 0; j < 256; j++) - if (n48->keys[j] < 48 && n48->keys[j] > i) - n48->keys[j]--; - _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); - n48->nr_entries--; - if (n48->nr_entries <= 16) - _degrade_to_n16(n48, root); - } - return r; - } - return true; - - case NODE256: - n256 = root->value.ptr; - if (n256->values[*kb].type == UNSET) - return true; // No entries - - r = _remove_subtree(rt, n256->values + (*kb), kb + 1, ke, count); - if (r && n256->values[*kb].type == UNSET) { - n256->nr_entries--; - if (n256->nr_entries <= 48) - _degrade_to_n48(n256, root); - } - return r; - } - - // Shouldn't get here - return false; -} - -unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) -{ - unsigned count = 0; - - if (_remove_subtree(rt, &rt->root, kb, ke, &count)) - rt->nr_entries -= count; - - return count; -} - -//---------------------------------------------------------------- - -bool radix_tree_lookup(struct radix_tree *rt, - uint8_t *kb, uint8_t *ke, union radix_value *result) -{ - struct value_chain *vc; - struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); - if (lr.kb == ke) { - switch (lr.v->type) { - case VALUE: - *result = lr.v->value; - return true; - - case VALUE_CHAIN: - vc = lr.v->value.ptr; - *result = vc->value; - return true; - - default: - return false; - } - } - - return false; -} - -// FIXME: build up the keys too -static bool _iterate(struct value *v, struct radix_tree_iterator *it) -{ - unsigned i; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - switch (v->type) { - case UNSET: - // can't happen - break; - - case VALUE: - return it->visit(it, NULL, NULL, v->value); - - case VALUE_CHAIN: - vc = v->value.ptr; - return it->visit(it, NULL, NULL, vc->value) && _iterate(&vc->child, it); - - case PREFIX_CHAIN: - pc = v->value.ptr; - return _iterate(&pc->child, it); - - case NODE4: - n4 = (struct node4 *) v->value.ptr; - for (i = 0; i < n4->nr_entries; i++) - if (!_iterate(n4->values + i, it)) - return false; - return true; - - case NODE16: - n16 = (struct node16 *) v->value.ptr; - for (i = 0; i < n16->nr_entries; i++) - if (!_iterate(n16->values + i, it)) - return false; - return true; - - case NODE48: - n48 = (struct node48 *) v->value.ptr; - for (i = 0; i < n48->nr_entries; i++) - if (!_iterate(n48->values + i, it)) - return false; - return true; - - case NODE256: - n256 = (struct node256 *) v->value.ptr; - for (i = 0; i < 256; i++) - if (n256->values[i].type != UNSET && !_iterate(n256->values + i, it)) - return false; - return true; - } - - // can't get here - return false; -} - -void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, - struct radix_tree_iterator *it) -{ - struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); - if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) - _iterate(lr.v, it); -} - -//---------------------------------------------------------------- -// Checks: -// 1) The number of entries matches rt->nr_entries -// 2) The number of entries is correct in each node -// 3) prefix chain len > 0 -// 4) all unused values are UNSET - -static bool _check_nodes(struct value *v, unsigned *count) -{ - unsigned i, ncount; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - switch (v->type) { - case UNSET: - return true; - - case VALUE: - (*count)++; - return true; - - case VALUE_CHAIN: - (*count)++; - vc = v->value.ptr; - return _check_nodes(&vc->child, count); - - case PREFIX_CHAIN: - pc = v->value.ptr; - return _check_nodes(&pc->child, count); - - case NODE4: - n4 = v->value.ptr; - for (i = 0; i < n4->nr_entries; i++) - if (!_check_nodes(n4->values + i, count)) - return false; - - for (i = n4->nr_entries; i < 4; i++) - if (n4->values[i].type != UNSET) { - fprintf(stderr, "unused value is not UNSET (n4)\n"); - return false; - } - - return true; - - case NODE16: - n16 = v->value.ptr; - for (i = 0; i < n16->nr_entries; i++) - if (!_check_nodes(n16->values + i, count)) - return false; - - for (i = n16->nr_entries; i < 16; i++) - if (n16->values[i].type != UNSET) { - fprintf(stderr, "unused value is not UNSET (n16)\n"); - return false; - } - - return true; - - case NODE48: - n48 = v->value.ptr; - ncount = 0; - for (i = 0; i < 256; i++) { - if (n48->keys[i] < 48) { - ncount++; - if (!_check_nodes(n48->values + n48->keys[i], count)) - return false; - } - } - - if (ncount != n48->nr_entries) { - fprintf(stderr, "incorrect number of entries in n48, n48->nr_entries = %u, actual = %u\n", - n48->nr_entries, ncount); - return false; - } - - for (i = n48->nr_entries; i < 48; i++) - if (n48->values[i].type != UNSET) { - fprintf(stderr, "unused value is not UNSET (n48)\n"); - return false; - } - - return true; - - case NODE256: - n256 = v->value.ptr; - - ncount = 0; - for (i = 0; i < 256; i++) { - struct value *v2 = n256->values + i; - - if (v2->type == UNSET) - continue; - - if (!_check_nodes(v2, count)) - return false; - - ncount++; - } - - if (ncount != n256->nr_entries) { - fprintf(stderr, "incorrect number of entries in n256, n256->nr_entries = %u, actual = %u\n", - n256->nr_entries, ncount); - return false; - } - - return true; - - default: - fprintf(stderr, "unknown value type: %u\n", v->type); - } - - fprintf(stderr, "shouldn't get here\n"); - return false; -} - -bool radix_tree_is_well_formed(struct radix_tree *rt) -{ - unsigned count = 0; - - if (!_check_nodes(&rt->root, &count)) - return false; - - if (rt->nr_entries != count) { - fprintf(stderr, "incorrect entry count: rt->nr_entries = %u, actual = %u\n", - rt->nr_entries, count); - return false; - } - - return true; -} - -//---------------------------------------------------------------- - -static void _dump(FILE *out, struct value v, unsigned indent) -{ - unsigned i; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - if (v.type == UNSET) - return; - - for (i = 0; i < 2 * indent; i++) - fprintf(out, " "); - - switch (v.type) { - case UNSET: - // can't happen - break; - - case VALUE: - fprintf(out, "<val: %llu>\n", (unsigned long long) v.value.n); - break; - - case VALUE_CHAIN: - vc = v.value.ptr; - fprintf(out, "<val_chain: %llu>\n", (unsigned long long) vc->value.n); - _dump(out, vc->child, indent + 1); - break; - - case PREFIX_CHAIN: - pc = v.value.ptr; - fprintf(out, "<prefix: "); - for (i = 0; i < pc->len; i++) - fprintf(out, "%x.", (unsigned) *(pc->prefix + i)); - fprintf(out, ">\n"); - _dump(out, pc->child, indent + 1); - break; - - case NODE4: - n4 = v.value.ptr; - fprintf(out, "<n4: "); - for (i = 0; i < n4->nr_entries; i++) - fprintf(out, "%x ", (unsigned) n4->keys[i]); - fprintf(out, ">\n"); - - for (i = 0; i < n4->nr_entries; i++) - _dump(out, n4->values[i], indent + 1); - break; - - case NODE16: - n16 = v.value.ptr; - fprintf(out, "<n16: "); - for (i = 0; i < n16->nr_entries; i++) - fprintf(out, "%x ", (unsigned) n16->keys[i]); - fprintf(out, ">\n"); - - for (i = 0; i < n16->nr_entries; i++) - _dump(out, n16->values[i], indent + 1); - break; - - case NODE48: - n48 = v.value.ptr; - fprintf(out, "<n48: "); - for (i = 0; i < 256; i++) - if (n48->keys[i] < 48) - fprintf(out, "%x ", i); - fprintf(out, ">\n"); - - for (i = 0; i < 256; i++) - if (n48->keys[i] < 48) - _dump(out, n48->values[i], indent + 1); - break; - - case NODE256: - n256 = v.value.ptr; - fprintf(out, "<n256: "); - for (i = 0; i < 256; i++) - if (n256->values[i].type != UNSET) - fprintf(out, "%x ", i); - fprintf(out, ">\n"); - - for (i = 0; i < 256; i++) - if (n256->values[i].type != UNSET) - _dump(out, n256->values[i], indent + 1); - break; - } -} - -void radix_tree_dump(struct radix_tree *rt, FILE *out) -{ - _dump(out, rt->root, 0); -} +#ifdef SIMPLE_RADIX_TREE +#include "base/data-struct/radix-tree-simple.c" +#else +#include "base/data-struct/radix-tree-adaptive.c" +#endif //----------------------------------------------------------------

1 0

master - [bcache] Remove unused 'hash' field from blocks.
by Joe Thornber 11 Sep '18

11 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=3255e384dbd567a4d6dde… Commit: 3255e384dbd567a4d6ddec8dc3eaac2d16476d3c Parent: 4d964133e267b2b501a5dcd40c30cfdcfaa5903a Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Sep 11 13:17:29 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Tue Sep 11 13:17:29 2018 +0100 [bcache] Remove unused 'hash' field from blocks. We use a radix tree these days rather than a hash table. --- lib/device/bcache.c | 1 - lib/device/bcache.h | 1 - 2 files changed, 0 insertions(+), 2 deletions(-) diff --git a/lib/device/bcache.c b/lib/device/bcache.c index e759997..5e795c5 100644 --- a/lib/device/bcache.c +++ b/lib/device/bcache.c @@ -757,7 +757,6 @@ static struct block *_new_block(struct bcache *cache, int fd, block_address i, b if (b) { dm_list_init(&b->list); - dm_list_init(&b->hash); b->flags = 0; b->fd = fd; b->index = i; diff --git a/lib/device/bcache.h b/lib/device/bcache.h index ae5e69c..1d49af2 100644 --- a/lib/device/bcache.h +++ b/lib/device/bcache.h @@ -62,7 +62,6 @@ struct block { struct bcache *cache; struct dm_list list; - struct dm_list hash; unsigned flags; unsigned ref_count;

1 0

master - tests: remove lvmetad variation
by David Teigland 10 Sep '18

10 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=07d2794a1640f05a45165… Commit: 07d2794a1640f05a451657a2176ccea5308d3298 Parent: b070c14a8b70dd8b8f4f3393e22ea9f1c584de76 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Mon Sep 10 14:26:57 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Mon Sep 10 14:26:57 2018 -0500 tests: remove lvmetad variation --- test/shell/inconsistent-metadata.sh | 55 +++++++++++++++------------------- 1 files changed, 24 insertions(+), 31 deletions(-) diff --git a/test/shell/inconsistent-metadata.sh b/test/shell/inconsistent-metadata.sh index f5ccd13..b42715d 100644 --- a/test/shell/inconsistent-metadata.sh +++ b/test/shell/inconsistent-metadata.sh @@ -31,43 +31,36 @@ init() { aux restore_dev "$dev1" } -# vgscan fixes up metadata (needs --cache option for direct scan if lvmetad is used) -cache="" -test -e LOCAL_LVMETAD && cache="--cache" init -vgscan $cache 2>&1 | tee cmd.out +vgscan 2>&1 | tee cmd.out grep "Inconsistent metadata found for VG $vg" cmd.out -test -e LOCAL_LVMETAD && vgrename $vg foo && vgrename foo $vg # trigger a write -vgscan $cache 2>&1 | tee cmd.out +vgscan 2>&1 | tee cmd.out not grep "Inconsistent metadata found for VG $vg" cmd.out check lv_field $vg/resized lv_size "8.00m" -# only vgscan would have noticed metadata inconsistencies when lvmetad is active -if test ! -e LOCAL_LVMETAD; then - # vgdisplay fixes - init - vgdisplay $vg 2>&1 | tee cmd.out - grep "Inconsistent metadata found for VG $vg" cmd.out - vgdisplay $vg 2>&1 | tee cmd.out - not grep "Inconsistent metadata found for VG $vg" cmd.out - check lv_field $vg/resized lv_size "8.00m" +# vgdisplay fixes +init +vgdisplay $vg 2>&1 | tee cmd.out +grep "Inconsistent metadata found for VG $vg" cmd.out +vgdisplay $vg 2>&1 | tee cmd.out +not grep "Inconsistent metadata found for VG $vg" cmd.out +check lv_field $vg/resized lv_size "8.00m" - # lvs fixes up - init - lvs $vg 2>&1 | tee cmd.out - grep "Inconsistent metadata found for VG $vg" cmd.out - vgdisplay $vg 2>&1 | tee cmd.out - not grep "Inconsistent metadata found for VG $vg" cmd.out - check lv_field $vg/resized lv_size "8.00m" +# lvs fixes up +init +lvs $vg 2>&1 | tee cmd.out +grep "Inconsistent metadata found for VG $vg" cmd.out +vgdisplay $vg 2>&1 | tee cmd.out +not grep "Inconsistent metadata found for VG $vg" cmd.out +check lv_field $vg/resized lv_size "8.00m" - # vgs fixes up as well - init - vgs $vg 2>&1 | tee cmd.out - grep "Inconsistent metadata found for VG $vg" cmd.out - vgs $vg 2>&1 | tee cmd.out - not grep "Inconsistent metadata found for VG $vg" cmd.out - check lv_field $vg/resized lv_size "8.00m" -fi +# vgs fixes up as well +init +vgs $vg 2>&1 | tee cmd.out +grep "Inconsistent metadata found for VG $vg" cmd.out +vgs $vg 2>&1 | tee cmd.out +not grep "Inconsistent metadata found for VG $vg" cmd.out +check lv_field $vg/resized lv_size "8.00m" echo Check auto-repair of failed vgextend - metadata written to original pv but not new pv vgremove -f $vg @@ -77,7 +70,7 @@ aux backup_dev "$dev2" vgcreate $SHARED $vg "$dev1" vgextend $vg "$dev2" aux restore_dev "$dev2" -vgscan $cache +vgscan should check compare_fields vgs $vg vg_mda_count pvs "$dev2" vg_mda_count vgremove -ff $vg

1 0

master - tests: drop lvmetad parts of system_id test
by David Teigland 10 Sep '18

10 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=b070c14a8b70dd8b8f4f3… Commit: b070c14a8b70dd8b8f4f3393e22ea9f1c584de76 Parent: 3bcc6c7e6064bd9632557f9678d9d88526d9bbdc Author: David Teigland <teigland(a)redhat.com> AuthorDate: Mon Sep 10 14:08:27 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Mon Sep 10 14:08:27 2018 -0500 tests: drop lvmetad parts of system_id test --- test/shell/system_id.sh | 192 ----------------------------------------------- 1 files changed, 0 insertions(+), 192 deletions(-) diff --git a/test/shell/system_id.sh b/test/shell/system_id.sh index c3fc311..8814d54 100644 --- a/test/shell/system_id.sh +++ b/test/shell/system_id.sh @@ -27,22 +27,6 @@ aux prepare_devs 1 SIDFILE="etc/lvm_test.conf" LVMLOCAL="etc/lvmlocal.conf" -# with clvm enabled, vgcreate with no -c option creates a clustered vg, -# which should have no system id - -if [ -e LOCAL_CLVMD ]; then -SID1=sidfoolocal -SID2="" -print_lvmlocal " system_id = $SID1" -aux lvmconf "global/system_id_source = lvmlocal" -vgcreate $vg1 "$dev1" -vgs -o+systemid $vg1 -check vg_field $vg1 systemid "$SID2" -vgremove $vg1 -rm -f "$LVMLOCAL" -exit 0 -fi - # create vg with system_id using each source ## none @@ -596,179 +580,3 @@ check vg_field $vg1 systemid "$SID" grep "No system ID found from system_id_source" err vgremove $vg1 - -# When a foreign vg is newer on disk than in lvmetad, using --foreign -# should find the newer version. This simulates a foreign host changing -# foreign vg by turning off lvmetad when we create an lv in the vg. -SID1=sidfoofile1 -SID2=sidfoofile2 -echo "$SID1" > "$SIDFILE" -aux lvmconf "global/system_id_source = file" \ - "global/system_id_file = \"$SIDFILE\"" -# create a vg with an lv -vgcreate $vg1 "$dev1" -lvcreate -n $lv1 -l 2 -an $vg1 -# normal vgs sees the vg and lv -vgs >err -grep $vg1 err -check lv_exists $vg1 $lv1 -# go around lvmetad to create another lv in the vg, -# forcing the lvmetad copy to be older than on disk. -aux lvmconf 'global/use_lvmetad = 0' -lvcreate -n $lv2 -l 2 -an $vg1 -aux lvmconf 'global/use_lvmetad = 1' -# verify that the second lv is not in lvmetad -lvs $vg1 >err -grep $lv1 err -not grep $lv2 err -# change our system_id, making the vg foreign -echo "$SID2" > "$SIDFILE" -vgs >err -not grep $vg1 err -# using --foreign, we will get the latest vg from disk -lvs --foreign $vg1 >err -grep $vg1 err -grep $lv1 err -grep $lv2 err -# change our system_id back to match the vg so it's not foreign -echo "$SID1" > "$SIDFILE" -lvremove $vg1/$lv1 -lvremove $vg1/$lv2 -vgremove $vg1 - -# vgimport should find the exported vg on disk even though -# lvmetad's copy of the vg shows it's foreign. -SID1=sidfoofile1 -SID2=sidfoofile2 -echo "$SID1" > "$SIDFILE" -aux lvmconf "global/system_id_source = file" \ - "global/system_id_file = \"$SIDFILE\"" -# create a vg with an lv -vgcreate $vg1 "$dev1" -lvcreate -n $lv1 -l 2 -an $vg1 -# normal vgs sees the vg and lv -vgs >err -grep $vg1 err -check lv_exists $vg1 $lv1 -# go around lvmetad to export the vg so that lvmetad still -# has the original vg owned by SID1 in its cache -aux lvmconf 'global/use_lvmetad = 0' -vgexport $vg1 -aux lvmconf 'global/use_lvmetad = 1' -# change the local system_id so the lvmetad copy of the vg is foreign -echo "$SID2" > "$SIDFILE" -# verify that lvmetad thinks the vg is foreign -# (don't use --foreign to verify this because that will cause -# the lvmetad cache to be updated, which we don't want yet) -not vgs $vg1 -# attempt to import the vg that has been exported, but -# which lvmetad thinks is foreign -vgimport $vg1 -# verify that the imported vg has our system_id -vgs -o+systemid $vg1 >err -grep $vg1 err -grep $SID2 err -check lv_exists $vg1 $lv1 -lvremove $vg1/$lv1 -vgremove $vg1 -rm -f "$SIDFILE" - -# pvscan --cache should cause the latest version of a foreign VG to be -# cached in lvmetad. Without the --cache option, pvscan will see the old -# version of the VG. -SID1=sidfoofile1 -SID2=sidfoofile2 -echo "$SID1" > "$SIDFILE" -aux lvmconf "global/system_id_source = file" \ - "global/system_id_file = \"$SIDFILE\"" -# create a vg with an lv -vgcreate $vg1 "$dev1" -lvcreate -n $lv1 -l 2 -an $vg1 -# normal vgs sees the vg and lv -vgs >err -grep $vg1 err -check lv_exists $vg1 $lv1 -# go around lvmetad to create another lv in the vg, -# forcing the lvmetad copy to be older than on disk. -aux lvmconf 'global/use_lvmetad = 0' -lvcreate -n $lv2 -l 2 -an $vg1 -aux lvmconf 'global/use_lvmetad = 1' -# verify that the second lv is not in lvmetad -lvs $vg1 >err -grep $lv1 err -not grep $lv2 err -# verify that after pvscan without --cache, lvmetad still -# reports the old version -pvscan -lvs $vg1 >err -grep $lv1 err -not grep $lv2 err -# change our system_id, making the vg foreign -echo "$SID2" > "$SIDFILE" -not vgs $vg1 >err -not grep $vg1 err -# use pvscan --cache to update the foreign vg in lvmetad -pvscan --cache -not vgs $vg1 >err -not grep $vg1 err -# change our system_id back to SID1 so we can check that -# lvmetad has the latest copy of the vg (without having -# to use --foreign to check) -echo "$SID1" > "$SIDFILE" -vgs $vg1 >err -grep $vg1 err -lvs $vg1 >err -grep $lv1 err -grep $lv2 err -lvremove $vg1/$lv1 -lvremove $vg1/$lv2 -vgremove $vg1 - -# repeat the same test for vgscan instead of pvscan -SID1=sidfoofile1 -SID2=sidfoofile2 -echo "$SID1" > "$SIDFILE" -aux lvmconf "global/system_id_source = file" \ - "global/system_id_file = \"$SIDFILE\"" -# create a vg with an lv -vgcreate $vg1 "$dev1" -lvcreate -n $lv1 -l 2 -an $vg1 -# normal vgs sees the vg and lv -vgs >err -grep $vg1 err -check lv_exists $vg1 $lv1 -# go around lvmetad to create another lv in the vg, -# forcing the lvmetad copy to be older than on disk. -aux lvmconf 'global/use_lvmetad = 0' -lvcreate -n $lv2 -l 2 -an $vg1 -aux lvmconf 'global/use_lvmetad = 1' -# verify that the second lv is not in lvmetad -lvs $vg1 >err -grep $lv1 err -not grep $lv2 err -# verify that after vgscan without --cache, lvmetad still -# reports the old version -vgscan -lvs $vg1 >err -grep $lv1 err -not grep $lv2 err -# change our system_id, making the vg foreign -echo "$SID2" > "$SIDFILE" -not vgs $vg1 >err -not grep $vg1 err -# use vgscan --cache to update the foreign vg in lvmetad -vgscan --cache -not vgs $vg1 >err -not grep $vg1 err -# change our system_id back to SID1 so we can check that -# lvmetad has the latest copy of the vg (without having -# to use --foreign to check) -echo "$SID1" > "$SIDFILE" -vgs $vg1 >err -grep $vg1 err -lvs $vg1 >err -grep $lv1 err -grep $lv2 err -lvremove $vg1/$lv1 -lvremove $vg1/$lv2 -vgremove $vg1

1 0

master - tests: drop lvmetad bits
by David Teigland 10 Sep '18

10 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=3bcc6c7e6064bd9632557… Commit: 3bcc6c7e6064bd9632557f9678d9d88526d9bbdc Parent: 989626926c98cd00f0236c4fcac883107d76899d Author: David Teigland <teigland(a)redhat.com> AuthorDate: Mon Sep 10 11:10:55 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Mon Sep 10 11:49:11 2018 -0500 tests: drop lvmetad bits --- test/Makefile.in | 3 - test/lib/aux.sh | 83 ------------------------ test/lib/flavour-ndev-lvmetad-lvmpolld.sh | 3 - test/lib/flavour-ndev-lvmetad.sh | 2 - test/lib/flavour-udev-lvmetad-lvmpolld.sh | 4 - test/lib/flavour-udev-lvmetad.sh | 3 - test/lib/flavour-udev-lvmlockd-test-lvmetad.sh | 9 --- test/lib/inittest.sh | 18 +----- test/shell/dmsetup-integrity-keys.sh | 2 - test/shell/dmsetup-keyring.sh | 2 - test/shell/lvconvert-mirror-basic.sh | 3 - test/shell/lvconvert-mirror.sh | 3 - test/shell/lvconvert-raid-status-validation.sh | 2 - test/shell/lvconvert-raid.sh | 2 - test/shell/lvcreate-repair.sh | 1 - test/shell/mirror-vgreduce-removemissing.sh | 3 - test/shell/name-mangling.sh | 2 - test/shell/pool-labels.sh | 4 - test/shell/process-each-lv.sh | 3 - test/shell/pv-duplicate-uuid.sh | 8 +-- test/shell/pv-ext-update.sh | 3 - test/shell/pvmove-basic.sh | 3 - test/shell/pvmove-restart.sh | 2 - test/shell/pvmove-resume-1.sh | 2 - test/shell/pvmove-resume-2.sh | 2 - test/shell/pvmove-resume-multiseg.sh | 3 - test/shell/relative-sign-options.sh | 4 - test/shell/report-fields.sh | 2 - test/shell/report-hidden.sh | 2 - test/shell/snapshot-remove-dmsetup.sh | 2 - test/shell/system_id.sh | 5 -- test/shell/test-partition.sh | 1 - test/shell/thin-dmeventd-warns.sh | 2 - test/shell/vgchange-many.sh | 2 - test/shell/vgck.sh | 7 +-- test/shell/vgcreate-many-pvs.sh | 2 - test/shell/vgimportclone.sh | 12 ---- test/shell/vgremove-corrupt-vg.sh | 1 - test/shell/vgsplit-operation.sh | 3 - test/unit/Makefile | 2 +- test/unit/unit-test.sh | 2 - 41 files changed, 6 insertions(+), 218 deletions(-) diff --git a/test/Makefile.in b/test/Makefile.in index a9bb083..bb736a6 100644 --- a/test/Makefile.in +++ b/test/Makefile.in @@ -96,7 +96,6 @@ help: @echo " LVM_TEST_PREFER_BRD Prefer using brd (ramdisk) over loop for testing [1]." @echo " LVM_TEST_DIR Where to create test files [$(LVM_TEST_DIR)]." @echo " LVM_TEST_LOCKING Normal (1), Cluster (3)." - @echo " LVM_TEST_LVMETAD_DEBUG_OPTS Allows to override debug opts [-l all]." @echo " LVM_TEST_LVMPOLLD Start lvmpolld" @echo " LVM_TEST_NODEBUG Do not debug lvm commands." @echo " LVM_TEST_PARALLEL May skip agresive wipe of LVMTEST resources." @@ -252,7 +251,6 @@ lib/flavour-%: $(srcdir)/lib/flavour-%.sh .lib-dir-stamp lib/paths-common: $(srcdir)/Makefile.in .lib-dir-stamp Makefile echo 'DM_UDEV_SYNCHRONISATION=$(dm_udev_synchronisation)' >> $@-t - echo 'LVMETAD_PIDFILE="@LVMETAD_PIDFILE@"' >> $@-t echo 'LVMPOLLD_PIDFILE="@LVMPOLLD_PIDFILE@"' >> $@-t echo 'DMEVENTD_PIDFILE="@DMEVENTD_PIDFILE@"' >> $@-t echo 'LVM_TEST_THIN_CHECK_CMD=$${LVM_TEST_THIN_CHECK_CMD-@THIN_CHECK_CMD@}' >> $@-t @@ -264,7 +262,6 @@ lib/paths-common: $(srcdir)/Makefile.in .lib-dir-stamp Makefile echo 'LVM_TEST_CACHE_REPAIR_CMD=$${LVM_TEST_CACHE_REPAIR_CMD-@CACHE_REPAIR_CMD@}' >> $@-t echo 'LVM_TEST_CACHE_RESTORE_CMD=$${LVM_TEST_CACHE_RESTORE_CMD-@CACHE_RESTORE_CMD@}' >> $@-t echo 'export DM_UDEV_SYNCHRONISATION THIN RAID CACHE\' >> $@-t - echo ' LVMETAD_PIDFILE LVMPOLLD_PIDFILE DMEVENTD_PIDFILE \' >> $@-t echo ' LVM_TEST_THIN_CHECK_CMD LVM_TEST_THIN_DUMP_CMD LVM_TEST_THIN_REPAIR_CMD LVM_TEST_THIN_RESTORE_CMD\' >> $@-t echo ' LVM_TEST_CACHE_CHECK_CMD LVM_TEST_CACHE_DUMP_CMD LVM_TEST_CACHE_REPAIR_CMD LVM_TEST_CACHE_RESTORE_CMD' >> $@-t mv $@-t $@ diff --git a/test/lib/aux.sh b/test/lib/aux.sh index f72c851..c3aeb43 100644 --- a/test/lib/aux.sh +++ b/test/lib/aux.sh @@ -214,62 +214,7 @@ prepare_dmeventd() { echo ok } -prepare_lvmetad() { - check_daemon_in_builddir lvmetad - - local run_valgrind="" - test "${LVM_VALGRIND_LVMETAD:-0}" -eq 0 || run_valgrind="run_valgrind" - - kill_sleep_kill_ LOCAL_LVMETAD "${LVM_VALGRIND_LVMETAD:-0}" - - lvmconf "global/use_lvmetad = 1" "devices/md_component_detection = 0" - # Default debug is "-l all" and could be override - # by setting LVM_TEST_LVMETAD_DEBUG_OPTS before calling inittest. - echo -n "## preparing lvmetad..." - # shellcheck disable=SC2086 - $run_valgrind lvmetad -f "$@" -s "$TESTDIR/lvmetad.socket" \ - ${LVM_TEST_LVMETAD_DEBUG_OPTS--l all} & - echo $! > LOCAL_LVMETAD - for i in {200..0} ; do - test "$i" -eq 0 && die "Startup of lvmetad is too slow." - test -e "$TESTDIR/lvmetad.socket" && break - echo -n . - sleep .1; - done - echo ok -} - -lvmetad_talk() { - local use=nc - if type -p socat >& /dev/null; then - use=socat - elif echo | not nc -U "$TESTDIR/lvmetad.socket" ; then - echo "WARNING: Neither socat nor nc -U seems to be available." 1>&2 - echo "## failed to contact lvmetad." - return 1 - fi - - if test "$use" = nc ; then - nc -U "$TESTDIR/lvmetad.socket" - else - socat "unix-connect:$TESTDIR/lvmetad.socket" - - fi | tee -a lvmetad-talk.txt -} - -lvmetad_dump() { - (echo 'request="dump"'; echo '##') | lvmetad_talk "$@" -} - -notify_lvmetad() { - if test -e LOCAL_LVMETAD; then - # Ignore results here... - LVM_LOG_FILE_EPOCH="" pvscan --cache "$@" || true - rm -f debug.log - fi -} - prepare_lvmpolld() { - check_daemon_in_builddir lvmetad lvmconf "global/use_lvmpolld = 1" local run_valgrind="" @@ -583,8 +528,6 @@ teardown() { killall -9 lvmlockd || true fi - kill_sleep_kill_ LOCAL_LVMETAD "${LVM_VALGRIND_LVMETAD:-0}" - dm_table | not grep -E -q "$vg|$vg1|$vg2|$vg3|$vg4" || { # Avoid activation of dmeventd if there is no pid cfg=$(test -s LOCAL_DMEVENTD || echo "--config activation{monitoring=0}") @@ -802,11 +745,7 @@ prepare_md_dev() { echo "${mddevdir}${mdname}" > MD_DEV_PV ;; esac echo "$mddev" > MD_DEV - notify_lvmetad "$(< MD_DEV_PV)" printf "%s\n" "${@:4}" > MD_DEVICES - for mddev in "${@:4}"; do - notify_lvmetad "$mddev" - done } cleanup_md_dev() { @@ -820,12 +759,10 @@ cleanup_md_dev() { mddev_pv=$(< MD_DEV_PV) udev_wait mdadm --stop "$mddev" || true - notify_lvmetad "$mddev_pv" udev_wait # wait till events are process, not zeroing to early test "$DM_DEV_DIR" != "/dev" && rm -rf "${mddev_pv%/*}" for dev in $(< MD_DEVICES); do mdadm --zero-superblock "$dev" || true - notify_lvmetad "$dev" done udev_wait if [ -b "$mddev" ]; then @@ -929,12 +866,6 @@ prepare_devs() { printf "%s\\n" "${DEVICES[@]}" > DEVICES # ( IFS=$'\n'; echo "${DEVICES[*]}" ) >DEVICES echo "ok" - - if test -e LOCAL_LVMETAD; then - for dev in "${DEVICES[@]}"; do - notify_lvmetad "$dev" - done - fi } @@ -1041,10 +972,6 @@ disable_dev() { dmsetup remove -f "$dev" 2>/dev/null || true fi done - - test -n "$silent" || for num in $notify; do - notify_lvmetad --major "${num%%:*}" --minor "${num##*:}" - done } enable_dev() { @@ -1066,10 +993,6 @@ enable_dev() { dmsetup resume "$name" done finish_udev_transaction - - test -n "$silent" || for dev in "$@"; do - notify_lvmetad "$dev" - done } # Throttle down performance of kcopyd when mirroring i.e. disk image @@ -1108,10 +1031,6 @@ restore_from_devtable() { dmsetup resume "$name" done finish_udev_transaction - - test -n "$silent" || for dev in "$@"; do - notify_lvmetad "$dev" - done } # @@ -1215,7 +1134,6 @@ generate_config() { fi LVM_TEST_LOCKING=${LVM_TEST_LOCKING:-1} - LVM_TEST_LVMETAD=${LVM_TEST_LVMETAD:-0} LVM_TEST_LVMPOLLD=${LVM_TEST_LVMPOLLD:-0} LVM_TEST_LVMLOCKD=${LVM_TEST_LVMLOCKD:-0} # FIXME:dct: This is harmful! Variables are unused here and are tested not being empty elsewhere: @@ -1264,7 +1182,6 @@ global/si_unit_consistency = 1 global/thin_check_executable = "$LVM_TEST_THIN_CHECK_CMD" global/thin_dump_executable = "$LVM_TEST_THIN_DUMP_CMD" global/thin_repair_executable = "$LVM_TEST_THIN_REPAIR_CMD" -global/use_lvmetad = $LVM_TEST_LVMETAD global/use_lvmpolld = $LVM_TEST_LVMPOLLD global/use_lvmlockd = $LVM_TEST_LVMLOCKD log/activation = 1 diff --git a/test/lib/flavour-ndev-lvmetad-lvmpolld.sh b/test/lib/flavour-ndev-lvmetad-lvmpolld.sh deleted file mode 100644 index 496b3bc..0000000 --- a/test/lib/flavour-ndev-lvmetad-lvmpolld.sh +++ /dev/null @@ -1,3 +0,0 @@ -export LVM_TEST_LOCKING=1 -export LVM_TEST_LVMETAD=1 -export LVM_TEST_LVMPOLLD=1 diff --git a/test/lib/flavour-ndev-lvmetad.sh b/test/lib/flavour-ndev-lvmetad.sh deleted file mode 100644 index cb3c49e..0000000 --- a/test/lib/flavour-ndev-lvmetad.sh +++ /dev/null @@ -1,2 +0,0 @@ -export LVM_TEST_LOCKING=1 -export LVM_TEST_LVMETAD=1 diff --git a/test/lib/flavour-udev-lvmetad-lvmpolld.sh b/test/lib/flavour-udev-lvmetad-lvmpolld.sh deleted file mode 100644 index 64253d1..0000000 --- a/test/lib/flavour-udev-lvmetad-lvmpolld.sh +++ /dev/null @@ -1,4 +0,0 @@ -export LVM_TEST_LOCKING=1 -export LVM_TEST_LVMETAD=1 -export LVM_TEST_LVMPOLLD=1 -export LVM_TEST_DEVDIR=/dev diff --git a/test/lib/flavour-udev-lvmetad.sh b/test/lib/flavour-udev-lvmetad.sh deleted file mode 100644 index 13be32e..0000000 --- a/test/lib/flavour-udev-lvmetad.sh +++ /dev/null @@ -1,3 +0,0 @@ -export LVM_TEST_LOCKING=1 -export LVM_TEST_LVMETAD=1 -export LVM_TEST_DEVDIR=/dev diff --git a/test/lib/flavour-udev-lvmlockd-test-lvmetad.sh b/test/lib/flavour-udev-lvmlockd-test-lvmetad.sh deleted file mode 100644 index d2a7b4a..0000000 --- a/test/lib/flavour-udev-lvmlockd-test-lvmetad.sh +++ /dev/null @@ -1,9 +0,0 @@ -export LVM_TEST_LOCKING=1 -export LVM_TEST_LVMETAD=1 -export LVM_TEST_LVMPOLLD=1 -export LVM_TEST_LVMLOCKD=1 -export LVM_TEST_LVMLOCKD_TEST=1 -export LVM_TEST_DEVDIR=/dev - -# FIXME:dct: add option to allow --test with sanlock -export LVM_TEST_LVMLOCKD_TEST_DLM=1 diff --git a/test/lib/inittest.sh b/test/lib/inittest.sh index 967fc1f..a6cefa8 100644 --- a/test/lib/inittest.sh +++ b/test/lib/inittest.sh @@ -34,7 +34,6 @@ LVM_TEST_LVM1=${LVM_TEST_LVM1-} # TODO: LVM_TEST_SHARED SHARED=${SHARED-} -LVM_TEST_LVMETAD=${LVM_TEST_LVMETAD-} LVM_TEST_LVMLOCKD=${LVM_TEST_LVMLOCKD-} LVM_TEST_LVMLOCKD_TEST=${LVM_TEST_LVMLOCKD_TEST-} LVM_TEST_LVMPOLLD=${LVM_TEST_LVMPOLLD-} @@ -44,9 +43,6 @@ LVM_TEST_LOCK_TYPE_SANLOCK=${LVM_TEST_LOCK_TYPE_SANLOCK-} SKIP_WITHOUT_CLVMD=${SKIP_WITHOUT_CLVMD-} SKIP_WITH_CLVMD=${SKIP_WITH_CLVMD-} -SKIP_WITHOUT_LVMETAD=${SKIP_WITHOUT_LVMETAD-} -SKIP_WITH_LVMETAD=${SKIP_WITH_LVMETAD-} - SKIP_WITH_LVMPOLLD=${SKIP_WITH_LVMPOLLD-} SKIP_WITH_LVMLOCKD=${SKIP_WITH_LVMLOCKD-} SKIP_ROOT_DM_CHECK=${SKIP_ROOT_DM_CHECK-} @@ -58,9 +54,6 @@ test -f "lib/flavour-$LVM_TEST_FLAVOUR" || { echo "NOTE: Flavour '$LVM_TEST_FLAV test -n "$SKIP_WITHOUT_CLVMD" && test "$LVM_TEST_LOCKING" -ne 3 && initskip test -n "$SKIP_WITH_CLVMD" && test "$LVM_TEST_LOCKING" = 3 && initskip -test -n "$SKIP_WITHOUT_LVMETAD" && test -z "$LVM_TEST_LVMETAD" && initskip -test -n "$SKIP_WITH_LVMETAD" && test -n "$LVM_TEST_LVMETAD" && initskip - test -n "$SKIP_WITH_LVMPOLLD" && test -n "$LVM_TEST_LVMPOLLD" && test -z "$LVM_TEST_LVMLOCKD" && initskip test -n "$SKIP_WITH_LVMLOCKD" && test -n "$LVM_TEST_LVMLOCKD" && initskip @@ -68,7 +61,7 @@ test -n "$SKIP_WITH_LVMLOCKD" && test -n "$LVM_TEST_LVMLOCKD" && initskip unset CDPATH export LVM_TEST_BACKING_DEVICE LVM_TEST_DEVDIR LVM_TEST_NODEBUG -export LVM_TEST_LVMETAD LVM_TEST_LVMLOCKD LVM_TEST_LVMLOCKD_TEST +export LVM_TEST_LVMLOCKD LVM_TEST_LVMLOCKD_TEST export LVM_TEST_LVMPOLLD LVM_TEST_LOCK_TYPE_DLM LVM_TEST_LOCK_TYPE_SANLOCK # grab some common utilities . lib/utils @@ -157,15 +150,8 @@ test -n "$BASH" && set -euE -o pipefail echo "@TESTDIR=$TESTDIR" echo "@PREFIX=$PREFIX" -if test -n "$LVM_TEST_LVMETAD" ; then - export LVM_LVMETAD_SOCKET="$TESTDIR/lvmetad.socket" - export LVM_LVMETAD_PIDFILE="$TESTDIR/lvmetad.pid" - aux prepare_lvmetad -elif test -z "$SKIP_ROOT_DM_CHECK" ; then - # lvmetad prepares its own lvmconf - export LVM_LVMETAD_PIDFILE="$TESTDIR/non-existing-file" +if test -z "$SKIP_ROOT_DM_CHECK" ; then aux lvmconf - aux prepare_clvmd fi test -n "$LVM_TEST_LVMPOLLD" && { diff --git a/test/shell/dmsetup-integrity-keys.sh b/test/shell/dmsetup-integrity-keys.sh index 6a7172f..cd98ead 100644 --- a/test/shell/dmsetup-integrity-keys.sh +++ b/test/shell/dmsetup-integrity-keys.sh @@ -13,8 +13,6 @@ # unrelated to lvm2 daemons SKIP_WITH_LVMLOCKD=1 SKIP_WITH_LVMPOLLD=1 -SKIP_WITH_CLVMD=1 -SKIP_WITH_LVMETAD=1 . lib/inittest diff --git a/test/shell/dmsetup-keyring.sh b/test/shell/dmsetup-keyring.sh index 0f730a9..3c0b867 100644 --- a/test/shell/dmsetup-keyring.sh +++ b/test/shell/dmsetup-keyring.sh @@ -13,8 +13,6 @@ # unrelated to lvm2 daemons SKIP_WITH_LVMLOCKD=1 SKIP_WITH_LVMPOLLD=1 -SKIP_WITH_CLVMD=1 -SKIP_WITH_LVMETAD=1 . lib/inittest diff --git a/test/shell/lvconvert-mirror-basic.sh b/test/shell/lvconvert-mirror-basic.sh index 2378d48..8166613 100644 --- a/test/shell/lvconvert-mirror-basic.sh +++ b/test/shell/lvconvert-mirror-basic.sh @@ -12,9 +12,6 @@ -# disable lvmetad logging as it bogs down test systems -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest log_name_to_count() { diff --git a/test/shell/lvconvert-mirror.sh b/test/shell/lvconvert-mirror.sh index 87993da..8f37645 100644 --- a/test/shell/lvconvert-mirror.sh +++ b/test/shell/lvconvert-mirror.sh @@ -12,9 +12,6 @@ -# disable lvmetad logging as it bogs down test systems -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest aux prepare_pvs 5 diff --git a/test/shell/lvconvert-raid-status-validation.sh b/test/shell/lvconvert-raid-status-validation.sh index c5396d7..2d3b5b9 100644 --- a/test/shell/lvconvert-raid-status-validation.sh +++ b/test/shell/lvconvert-raid-status-validation.sh @@ -18,8 +18,6 @@ SKIP_WITH_LVMPOLLD=1 -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest # check for version 1.9.0 diff --git a/test/shell/lvconvert-raid.sh b/test/shell/lvconvert-raid.sh index ce60b6b..3b7af97 100644 --- a/test/shell/lvconvert-raid.sh +++ b/test/shell/lvconvert-raid.sh @@ -14,8 +14,6 @@ SKIP_WITH_LVMPOLLD=1 -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest get_image_pvs() { diff --git a/test/shell/lvcreate-repair.sh b/test/shell/lvcreate-repair.sh index cff0018..07263a3 100644 --- a/test/shell/lvcreate-repair.sh +++ b/test/shell/lvcreate-repair.sh @@ -88,7 +88,6 @@ dd if=backup_i of="$dev1" bs=256K count=1 # dirty game dd if=/dev/zero of="$dev3" bs=256K count=1 -aux notify_lvmetad "$dev3" # udev be watching you vgreduce --removemissing --force $vg diff --git a/test/shell/mirror-vgreduce-removemissing.sh b/test/shell/mirror-vgreduce-removemissing.sh index 69d9fe8..d95a0ac 100644 --- a/test/shell/mirror-vgreduce-removemissing.sh +++ b/test/shell/mirror-vgreduce-removemissing.sh @@ -15,9 +15,6 @@ test_description="ensure that 'vgreduce --removemissing' works on mirrored LV" SKIP_WITH_LVMPOLLD=1 -# disable lvmetad logging as it bogs down test systems -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest list_pvs=() diff --git a/test/shell/name-mangling.sh b/test/shell/name-mangling.sh index 8382ad1..4287939 100644 --- a/test/shell/name-mangling.sh +++ b/test/shell/name-mangling.sh @@ -13,8 +13,6 @@ # This test is not using any lvm command # so skip duplicate CLMVD and lvmetad test -SKIP_WITH_CLVMD=1 -SKIP_WITH_LVMETAD=1 SKIP_WITH_LVMPOLLD=1 . lib/inittest diff --git a/test/shell/pool-labels.sh b/test/shell/pool-labels.sh index 3f9b942..88978e8 100644 --- a/test/shell/pool-labels.sh +++ b/test/shell/pool-labels.sh @@ -10,9 +10,6 @@ # along with this program; if not, write to the Free Software Foundation, # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA -# lvmetad does not handle pool labels so skip test. - -SKIP_WITH_LVMETAD=1 SKIP_WITH_LVMPOLLD=1 . lib/inittest @@ -27,7 +24,6 @@ create_pool_label_() # printf comes from coreutils, and is probably not posix either env printf "\x01\x16\x70\x06\x5f\xcf\xff\xb9\xf8\x24\x8apool1" | dd of="$2" bs=5 seek=1 conv=notrunc env printf "\x04\x01\x03\x00\x00\x00\x01\x00\x00\x00\x00\x00\x00\x00\x02\x00\x00\x00\x0$1\x68\x01\x16\x70\x00\x00\x00\x00\x00\x06\x5f\xd0" | dd of=$2 bs=273 seek=1 conv=notrunc - aux notify_lvmetad "$2" } diff --git a/test/shell/process-each-lv.sh b/test/shell/process-each-lv.sh index 9482a08..f28988c 100644 --- a/test/shell/process-each-lv.sh +++ b/test/shell/process-each-lv.sh @@ -14,9 +14,6 @@ test_description='Exercise toollib process_each_lv' SKIP_WITH_LVMPOLLD=1 -# disable lvmetad logging as it bogs down test systems -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest diff --git a/test/shell/pv-duplicate-uuid.sh b/test/shell/pv-duplicate-uuid.sh index a076812..37d8514 100644 --- a/test/shell/pv-duplicate-uuid.sh +++ b/test/shell/pv-duplicate-uuid.sh @@ -20,15 +20,11 @@ aux prepare_devs 3 pvcreate "$dev1" UUID1=$(get pv_field "$dev1" uuid) -pvcreate --config "devices{filter=[\"a|$dev2|\",\"r|.*|\"]} global/use_lvmetad=0" -u "$UUID1" --norestorefile "$dev2" -pvcreate --config "devices{filter=[\"a|$dev3|\",\"r|.*|\"]} global/use_lvmetad=0" -u "$UUID1" --norestorefile "$dev3" +pvcreate --config "devices{filter=[\"a|$dev2|\",\"r|.*|\"]}" -u "$UUID1" --norestorefile "$dev2" +pvcreate --config "devices{filter=[\"a|$dev3|\",\"r|.*|\"]}" -u "$UUID1" --norestorefile "$dev3" pvscan --cache 2>&1 | tee out -if test -e LOCAL_LVMETAD; then - grep "WARNING: Disabling lvmetad cache which does not support duplicate PVs." out -fi - pvs -o+uuid 2>&1 | tee out grep WARNING out > warn || true diff --git a/test/shell/pv-ext-update.sh b/test/shell/pv-ext-update.sh index 9059a22..bd66c02 100644 --- a/test/shell/pv-ext-update.sh +++ b/test/shell/pv-ext-update.sh @@ -10,7 +10,6 @@ # along with this program; if not, write to the Free Software Foundation, # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA -# lvmetad does not handle pool labels so skip test. SKIP_WITH_LVMPOLLD=1 @@ -166,8 +165,6 @@ create_pv_with_ext_vsn1_and_vg() "\x75\x6c\x20\x32\x37\x20\x31\x31\x3a\x32\x35\x3a\x31\x30\x20\x32"\ "\x30\x31\x36\x0a\x0a\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00"\ "\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00" | dd of="$1" bs=5632 seek=1 conv=notrunc - - aux notify_lvmetad "$1" } aux prepare_devs 1 8 diff --git a/test/shell/pvmove-basic.sh b/test/shell/pvmove-basic.sh index 2fc71e2..c02354d 100644 --- a/test/shell/pvmove-basic.sh +++ b/test/shell/pvmove-basic.sh @@ -15,9 +15,6 @@ test_description="ensure that pvmove works with basic options" SKIP_WITH_LVMLOCKD=1 -# disable lvmetad logging as it bogs down test systems -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest which md5sum || skip diff --git a/test/shell/pvmove-restart.sh b/test/shell/pvmove-restart.sh index dcf4c37..115ce14 100644 --- a/test/shell/pvmove-restart.sh +++ b/test/shell/pvmove-restart.sh @@ -81,8 +81,6 @@ if test -e LOCAL_CLVMD ; then aux prepare_clvmd fi -aux notify_lvmetad "$dev1" "$dev2" "$dev3" - # Only PVs should be left in table... dmsetup table diff --git a/test/shell/pvmove-resume-1.sh b/test/shell/pvmove-resume-1.sh index ddebcb9..6b4cbe5 100644 --- a/test/shell/pvmove-resume-1.sh +++ b/test/shell/pvmove-resume-1.sh @@ -86,8 +86,6 @@ test_pvmove_resume() { aux prepare_clvmd fi - aux notify_lvmetad "$dev1" "$dev2" "$dev3" "$dev4" - # call resume function (see below) # with expected number of spawned # bg polling as parameter diff --git a/test/shell/pvmove-resume-2.sh b/test/shell/pvmove-resume-2.sh index 5e9ad81..803e6ef 100644 --- a/test/shell/pvmove-resume-2.sh +++ b/test/shell/pvmove-resume-2.sh @@ -75,8 +75,6 @@ test_pvmove_resume() { aux prepare_clvmd fi - aux notify_lvmetad "$dev1" "$dev2" - # call resume function (see below) # with expected number of spawned # bg polling as parameter diff --git a/test/shell/pvmove-resume-multiseg.sh b/test/shell/pvmove-resume-multiseg.sh index ce54061..89c2f74 100644 --- a/test/shell/pvmove-resume-multiseg.sh +++ b/test/shell/pvmove-resume-multiseg.sh @@ -16,7 +16,6 @@ # Multisegment variant w/ 2 pvmoves LVs per VG SKIP_WITH_LVMLOCKD=1 -SKIP_WITH_CLVMD=1 . lib/inittest @@ -79,8 +78,6 @@ test_pvmove_resume() { aux prepare_clvmd fi - aux notify_lvmetad "$dev1" "$dev2" "$dev3" "$dev4" "$dev5" - # call resume function (see below) # with expected number of spawned # bg polling as parameter diff --git a/test/shell/relative-sign-options.sh b/test/shell/relative-sign-options.sh index 82a5ed2..8333998 100644 --- a/test/shell/relative-sign-options.sh +++ b/test/shell/relative-sign-options.sh @@ -13,10 +13,6 @@ test_description='Exercise toollib process_each_lv' SKIP_WITH_LVMPOLLD=1 - -# disable lvmetad logging as it bogs down test systems -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest aux prepare_vg 1 256 diff --git a/test/shell/report-fields.sh b/test/shell/report-fields.sh index 8260610..949e5a5 100644 --- a/test/shell/report-fields.sh +++ b/test/shell/report-fields.sh @@ -11,9 +11,7 @@ # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA -SKIP_WITH_LVMETAD=1 SKIP_WITH_LVMPOLLD=1 -SKIP_WITH_CLVMD=1 . lib/inittest diff --git a/test/shell/report-hidden.sh b/test/shell/report-hidden.sh index 24a11c8..621eefc 100644 --- a/test/shell/report-hidden.sh +++ b/test/shell/report-hidden.sh @@ -11,8 +11,6 @@ # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA -SKIP_WITH_LVMETAD=1 -SKIP_WITH_CLVMD=1 SKIP_WITH_LVMPOLLD=1 . lib/inittest diff --git a/test/shell/snapshot-remove-dmsetup.sh b/test/shell/snapshot-remove-dmsetup.sh index a7925d5..19411ce 100644 --- a/test/shell/snapshot-remove-dmsetup.sh +++ b/test/shell/snapshot-remove-dmsetup.sh @@ -13,8 +13,6 @@ # check if 'dmsetup --noflush' will work properly for mounted snapshot SKIP_WITH_LVMLOCKD=1 -SKIP_WITH_CLVMD=1 -SKIP_WITH_LVMETAD=1 SKIP_WITH_LVMPOLLD=1 . lib/inittest diff --git a/test/shell/system_id.sh b/test/shell/system_id.sh index ec7953d..c3fc311 100644 --- a/test/shell/system_id.sh +++ b/test/shell/system_id.sh @@ -597,11 +597,6 @@ grep "No system ID found from system_id_source" err vgremove $vg1 -# Test cases where lvmetad cache of a foreign VG are out of date -# because the foreign owner has changed the VG. - -test ! -e LOCAL_LVMETAD && exit 0 - # When a foreign vg is newer on disk than in lvmetad, using --foreign # should find the newer version. This simulates a foreign host changing # foreign vg by turning off lvmetad when we create an lv in the vg. diff --git a/test/shell/test-partition.sh b/test/shell/test-partition.sh index 083cd98..0e92f00 100644 --- a/test/shell/test-partition.sh +++ b/test/shell/test-partition.sh @@ -32,5 +32,4 @@ pvs "$dev1" # create small partition table echo "1 2" | sfdisk --force "$dev1" -aux notify_lvmetad "$dev1" not pvs "$dev1" diff --git a/test/shell/thin-dmeventd-warns.sh b/test/shell/thin-dmeventd-warns.sh index a8002ae..2e97fb1 100644 --- a/test/shell/thin-dmeventd-warns.sh +++ b/test/shell/thin-dmeventd-warns.sh @@ -14,8 +14,6 @@ SKIP_WITH_LVMPOLLD=1 -SKIP_WITH_CLVMD=1 -SKIP_WITH_LVMETAD=1 . lib/inittest diff --git a/test/shell/vgchange-many.sh b/test/shell/vgchange-many.sh index debfdc4..389877a 100644 --- a/test/shell/vgchange-many.sh +++ b/test/shell/vgchange-many.sh @@ -16,8 +16,6 @@ SKIP_WITH_LVMPOLLD=1 . lib/inittest -# FIXME: lvmetad fails with i.e. 1500 device on memory failure... - # Number of LVs to create TEST_DEVS=1000 # On low-memory boxes let's not stress too much diff --git a/test/shell/vgck.sh b/test/shell/vgck.sh index c9d29bb..3288d1b 100644 --- a/test/shell/vgck.sh +++ b/test/shell/vgck.sh @@ -24,14 +24,9 @@ dd if=/dev/urandom bs=512 seek=2 count=32 of="$dev2" vgscan 2>&1 | tee vgscan.out || true -if test -e LOCAL_LVMETAD; then - not grep "Failed" vgscan.out -else - grep "Failed" vgscan.out -fi +grep "Failed" vgscan.out dd if=/dev/urandom bs=512 seek=2 count=32 of="$dev2" -aux notify_lvmetad "$dev2" vgck $vg 2>&1 | tee vgck.out || true grep Incorrect vgck.out diff --git a/test/shell/vgcreate-many-pvs.sh b/test/shell/vgcreate-many-pvs.sh index 9598f91..c68afeb 100644 --- a/test/shell/vgcreate-many-pvs.sh +++ b/test/shell/vgcreate-many-pvs.sh @@ -26,12 +26,10 @@ SKIP_WITH_LVMPOLLD=1 # export LVM_TEST_PVS=300 # # make check_local ~52sec (U:29s, S:13s) -# make check_lvmetad ~20sec (U: 4s, S: 5s) # # With patch from 2015-03-06: # # make check_local ~30sec (U:10s, S:12s) -# make check_lvmetad ~20sec (U: 4s, S: 5s) # # TODO: extend test suite to monitor performance and report regressions... diff --git a/test/shell/vgimportclone.sh b/test/shell/vgimportclone.sh index 48a666e..2245d65 100644 --- a/test/shell/vgimportclone.sh +++ b/test/shell/vgimportclone.sh @@ -45,7 +45,6 @@ vgchange -ay $vg1 # Clone the LUN dd if="$dev1" of="$dev2" bs=256K count=1 -aux notify_lvmetad "$dev2" # Verify pvs works on each device to give us vgname aux hide_dev "$dev2" @@ -59,14 +58,6 @@ aux unhide_dev "$dev1" # Import the cloned PV to a new VG vgimportclone --basevgname $vg2 "$dev2" -# We need to re-scan *both* $dev1 and $dev2 since a PV, as far as lvmetad is -# concerned, can only live on a single device. With the last pvscan, we told it -# that PV from $dev1 now lives on $dev2, but in fact this is not true anymore, -# since we wrote a different PV over $dev2. -rm -f "$TESTDIR/etc/.cache" -aux notify_lvmetad "$dev2" -aux notify_lvmetad "$dev1" - # Verify we can activate / deactivate the LV from both VGs lvchange -ay $vg1/$lv1 $vg2/$lv1 vgchange -an $vg1 $vg2 @@ -79,19 +70,16 @@ vgcreate $SHARED --metadatasize 128k A${vg1}B "$dev1" # vg1B is not the same as Avg1B - we don't need number suffix dd if="$dev1" of="$dev2" bs=256K count=1 -aux notify_lvmetad "$dev2" vgimportclone -n ${vg1}B "$dev2" check pv_field "$dev2" vg_name ${vg1}B # Avg1 is not the same as Avg1B - we don't need number suffix dd if="$dev1" of="$dev2" bs=256K count=1 -aux notify_lvmetad "$dev2" vgimportclone -n A${vg1} "$dev2" check pv_field "$dev2" vg_name A${vg1} # Avg1B is the same as Avg1B - we need to add the number suffix dd if="$dev1" of="$dev2" bs=256K count=1 -aux notify_lvmetad "$dev2" vgimportclone -n A${vg1}B "$dev2" aux vgs check pv_field "$dev2" vg_name A${vg1}B1 diff --git a/test/shell/vgremove-corrupt-vg.sh b/test/shell/vgremove-corrupt-vg.sh index 1de77e4..3b17746 100644 --- a/test/shell/vgremove-corrupt-vg.sh +++ b/test/shell/vgremove-corrupt-vg.sh @@ -19,6 +19,5 @@ aux prepare_vg 3 lvcreate -n blabla -L 1 $vg -an --zero n dd if=/dev/urandom bs=512 seek=2 count=32 of="$dev2" -aux notify_lvmetad "$dev2" vgremove -f $vg diff --git a/test/shell/vgsplit-operation.sh b/test/shell/vgsplit-operation.sh index 2ec140b..ab88866 100644 --- a/test/shell/vgsplit-operation.sh +++ b/test/shell/vgsplit-operation.sh @@ -12,12 +12,9 @@ # Test vgsplit operation, including different LV types -# disable lvmetad logging as it bogs down test systems SKIP_WITH_LVMLOCKD=1 SKIP_WITH_LVMPOLLD=1 -export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-} - . lib/inittest COMM() { diff --git a/test/unit/Makefile b/test/unit/Makefile index c2f992b..bf85354 100644 --- a/test/unit/Makefile +++ b/test/unit/Makefile @@ -45,7 +45,7 @@ run-unit-test: test/unit/unit-test ifeq ("$(USE_TRACKING)","yes") ifeq (,$(findstring $(MAKECMDGOALS),cscope.out cflow clean distclean lcov \ - help check check_local check_cluster check_lvmetad check_lvmpolld run-unit-test)) + help check check_local check_lvmpolld run-unit-test)) -include $(UNIT_DEPENDS) endif endif diff --git a/test/unit/unit-test.sh b/test/unit/unit-test.sh index e8332d6..f545f14 100644 --- a/test/unit/unit-test.sh +++ b/test/unit/unit-test.sh @@ -13,8 +13,6 @@ SKIP_WITH_LVMLOCKD=1 SKIP_WITH_LVMPOLLD=1 -SKIP_WITH_LVMETAD=1 -SKIP_WITH_CLVMD=1 SKIP_ROOT_DM_CHECK=1

1 0

master - lvconvert: allow raid4 -> linear conversion request
by Heinz Mauelshagen 10 Sep '18

10 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=989626926c98cd00f0236… Commit: 989626926c98cd00f0236c4fcac883107d76899d Parent: e2e30a64ab10602951443dfbd3481bd6b32f5459 Author: Heinz Mauelshagen <heinzm(a)redhat.com> AuthorDate: Mon Sep 10 18:36:52 2018 +0200 Committer: Heinz Mauelshagen <heinzm(a)redhat.com> CommitterDate: Mon Sep 10 18:43:21 2018 +0200 lvconvert: allow raid4 -> linear conversion request Allow "lvconvert --type linear RaidLV" on a raid4 LV providing convenient interim steps to convert to linear. Add respective new test lvconvert-raid-takeover-raid4_to_linear.sh and lvconvert-raid-takeover-linear_to_raid4.sh for linear to raid4 once on it. --- WHATS_NEW | 1 + lib/metadata/raid_manip.c | 22 +++-- .../lvconvert-raid-takeover-linear_to_raid4.sh | 71 +++++++++++++++++ .../lvconvert-raid-takeover-raid4_to_linear.sh | 82 ++++++++++++++++++++ 4 files changed, 167 insertions(+), 9 deletions(-) diff --git a/WHATS_NEW b/WHATS_NEW index 6575887..a065a17 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,5 +1,6 @@ Version 3.0.0 ============= + Allow raid4 -> linear conversion request. Fix lvconvert striped/raid0/raid0_meta -> raid6 regression. Add 'lvm2-activation-generator:' prefix for kmsg messages logged by generator. Add After=rbdmap.service to {lvm2-activation-net,blk-availability}.service. diff --git a/lib/metadata/raid_manip.c b/lib/metadata/raid_manip.c index 130cd34..1af3729 100644 --- a/lib/metadata/raid_manip.c +++ b/lib/metadata/raid_manip.c @@ -6149,9 +6149,17 @@ static int _set_convenient_raid145610_segtype_to(const struct lv_segment *seg_fr else if (!segtype_is_raid4(*segtype) && !segtype_is_any_raid5(*segtype)) seg_flag = SEG_RAID5_LS; - /* raid5* -> */ - } else if (seg_is_any_raid5(seg_from)) { - if (segtype_is_raid1(*segtype) || segtype_is_linear(*segtype)) { + /* raid4/raid5* -> */ + } else if (seg_is_raid4(seg_from) || seg_is_any_raid5(seg_from)) { + if (seg_is_raid4(seg_from) && segtype_is_any_raid5(*segtype)) { + if (!segtype_is_raid5_n(*segtype)) + seg_flag = SEG_RAID5_N; + + } else if (seg_is_any_raid5(seg_from) && segtype_is_raid4(*segtype)) { + if (!seg_is_raid5_n(seg_from)) + seg_flag = SEG_RAID5_N; + + } else if (segtype_is_raid1(*segtype) || segtype_is_linear(*segtype)) { if (seg_from->area_count != 2) { log_error("Converting %s LV %s to 2 stripes first.", lvseg_name(seg_from), display_lvname(seg_from->lv)); @@ -6173,12 +6181,12 @@ static int _set_convenient_raid145610_segtype_to(const struct lv_segment *seg_fr lvseg_name(seg_from), display_lvname(seg_from->lv), *new_image_count); } else - seg_flag = _raid_seg_flag_5_to_6(seg_from); + seg_flag = seg_is_raid4(seg_from) ? SEG_RAID6_N_6 :_raid_seg_flag_5_to_6(seg_from); } else if (segtype_is_striped(*segtype) || segtype_is_raid10(*segtype)) { int change = 0; - if (!seg_is_raid5_n(seg_from)) { + if (!seg_is_raid4(seg_from) && !seg_is_raid5_n(seg_from)) { seg_flag = SEG_RAID5_N; } else if (*stripes > 2 && *stripes != seg_from->area_count - seg_from->segtype->parity_devs) { @@ -6199,10 +6207,6 @@ static int _set_convenient_raid145610_segtype_to(const struct lv_segment *seg_fr lvseg_name(seg_from), display_lvname(seg_from->lv), *new_image_count); } - /* raid4 -> * */ - } else if (seg_is_raid4(seg_from) && !segtype_is_raid4(*segtype) && !segtype_is_striped(*segtype)) { - seg_flag = segtype_is_any_raid6(*segtype) ? SEG_RAID6_N_6 : SEG_RAID5_N; - /* raid6 -> striped/raid0/raid5/raid10 */ } else if (seg_is_any_raid6(seg_from)) { if (segtype_is_raid1(*segtype)) { diff --git a/test/shell/lvconvert-raid-takeover-linear_to_raid4.sh b/test/shell/lvconvert-raid-takeover-linear_to_raid4.sh new file mode 100644 index 0000000..0360fa0 --- /dev/null +++ b/test/shell/lvconvert-raid-takeover-linear_to_raid4.sh @@ -0,0 +1,71 @@ +#!/usr/bin/env bash + +# Copyright (C) 2018 Red Hat, Inc. All rights reserved. +# +# This copyrighted material is made available to anyone wishing to use, +# modify, copy, or redistribute it subject to the terms and conditions +# of the GNU General Public License v.2. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software Foundation, +# Inc., 51 Franklin Street, Fifth Floor, Boston, MA2110-1301 USA + + +SKIP_WITH_LVMPOLLD=1 + +. lib/inittest + +which mkfs.ext4 || skip +aux have_raid 1 9 1 || skip + +aux prepare_vg 4 32 + +# FIXME: lvconvert leaks 'error' devices +detect_error_leak_() +{ + local err="" + + for i in $(dmsetup info -c -o name --noheadings) ; do + case "$i" in + "$vg*") (dmsetup table "$i" | grep "error ") && err="$err $i" ;; + esac + done + + test -z "$err" || { + dmsetup table | grep $vg + dmsetup ls --tree + die "Device(s) $err should not be here." + } +} + +# Create linear LV +lvcreate -y -L 9M -n $lv $vg +check lv_field $vg/$lv segtype "linear" +check lv_field $vg/$lv data_stripes 1 +check lv_field $vg/$lv stripes 1 +mkfs.ext4 "$DM_DEV_DIR/$vg/$lv" +fsck -fn "$DM_DEV_DIR/$vg/$lv" + +# Step 1: convert linear -> raid4 (convert to 2-legged raid1) +lvconvert -y --stripes 3 --ty raid4 $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "raid1" +check lv_field $vg/$lv data_stripes 2 +check lv_field $vg/$lv stripes 2 +aux wait_for_sync $vg $lv + +# Step 2: convert linear ->raid4 (convert to raid4) +lvconvert -y --stripes 3 --ty raid4 $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "raid4" +check lv_field $vg/$lv data_stripes 1 +check lv_field $vg/$lv stripes 2 + +# Step 3: convert linear ->raid4 (reshape to add stripes) +lvconvert -y --stripes 3 --ty raid4 $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "raid4" +check lv_field $vg/$lv data_stripes 3 +check lv_field $vg/$lv stripes 4 + +vgremove -ff $vg diff --git a/test/shell/lvconvert-raid-takeover-raid4_to_linear.sh b/test/shell/lvconvert-raid-takeover-raid4_to_linear.sh new file mode 100644 index 0000000..e571b82 --- /dev/null +++ b/test/shell/lvconvert-raid-takeover-raid4_to_linear.sh @@ -0,0 +1,82 @@ +#!/usr/bin/env bash + +# Copyright (C) 2018 Red Hat, Inc. All rights reserved. +# +# This copyrighted material is made available to anyone wishing to use, +# modify, copy, or redistribute it subject to the terms and conditions +# of the GNU General Public License v.2. +# +# You should have received a copy of the GNU General Public License +# along with this program; if not, write to the Free Software Foundation, +# Inc., 51 Franklin Street, Fifth Floor, Boston, MA2110-1301 USA + + +SKIP_WITH_LVMPOLLD=1 + +. lib/inittest + +which mkfs.ext4 || skip +aux have_raid 1 9 1 || skip + +aux prepare_vg 4 32 + +# FIXME: lvconvert leaks 'error' devices +detect_error_leak_() +{ + local err="" + + for i in $(dmsetup info -c -o name --noheadings) ; do + case "$i" in + "$vg*") (dmsetup table "$i" | grep "error ") && err="$err $i" ;; + esac + done + + test -z "$err" || { + dmsetup table | grep $vg + dmsetup ls --tree + die "Device(s) $err should not be here." + } +} + +# Create 3-way striped raid4 (4 legs total) +lvcreate -y --ty raid4 --stripes 3 -L 9M -n $lv $vg +check lv_field $vg/$lv segtype "raid4" +check lv_field $vg/$lv data_stripes 3 +check lv_field $vg/$lv stripes 4 +mkfs.ext4 "$DM_DEV_DIR/$vg/$lv" +fsck -fn "$DM_DEV_DIR/$vg/$lv" + +# Step 1: grow before removing stripes +lvextend -y -L27M $vg/$lv +aux wait_for_sync $vg $lv + +# Step 2: convert raid4 -> linear (reshape to remove stripes) +lvconvert -y -f --ty linear $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "raid4" +check lv_field $vg/$lv data_stripes 1 +check lv_field $vg/$lv stripes 4 +aux wait_for_sync $vg $lv 1 + +# Step 2: convert raid4 -> linear (remove freed stripes) +lvconvert -y --ty linear $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "raid4" +check lv_field $vg/$lv data_stripes 1 +check lv_field $vg/$lv stripes 2 + +# Step 3: convert raid4 -> linear (convert to raid1) +lvconvert -y --ty linear $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "raid1" +check lv_field $vg/$lv data_stripes 2 +check lv_field $vg/$lv stripes 2 + +# Step 4: convert raid4 -> linear (convert to linear) +lvconvert -y --ty linear $vg/$lv +detect_error_leak_ +check lv_field $vg/$lv segtype "linear" +check lv_field $vg/$lv data_stripes 1 +check lv_field $vg/$lv stripes 1 + +vgremove -ff $vg

1 0

master - lvconvert: fix interim segtype regression on raid6 conversions
by Heinz Mauelshagen 07 Sep '18

07 Sep '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=e2e30a64ab10602951443… Commit: e2e30a64ab10602951443dfbd3481bd6b32f5459 Parent: 22a13043683a5647e8cc4e3aead911e5269ffd2f Author: Heinz Mauelshagen <heinzm(a)redhat.com> AuthorDate: Fri Sep 7 13:48:13 2018 +0200 Committer: Heinz Mauelshagen <heinzm(a)redhat.com> CommitterDate: Fri Sep 7 13:48:19 2018 +0200 lvconvert: fix interim segtype regression on raid6 conversions When converting from striped/raid0/raid0_meta to raid6 with > 2 stripes, allow possible direct conversion (to raid6_n_6). In case of 2 stripes, first convert to raid5_n to restripe to at least 3 data stripes (the raid6 minimum in lvm2) in a second conversion before finally converting to raid6_n_6. As before, raid6_n_6 then can be converted to any other raid6 layout. Enhance lvconvert-raid-takeover.sh to test the 2 stripes conversions to raid6. Resolves: rhbz1624038 --- WHATS_NEW | 1 + lib/metadata/raid_manip.c | 6 +++--- test/shell/lvconvert-raid-takeover.sh | 16 ++++++++++++---- 3 files changed, 16 insertions(+), 7 deletions(-) diff --git a/WHATS_NEW b/WHATS_NEW index 6003f0a..6575887 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,5 +1,6 @@ Version 3.0.0 ============= + Fix lvconvert striped/raid0/raid0_meta -> raid6 regression. Add 'lvm2-activation-generator:' prefix for kmsg messages logged by generator. Add After=rbdmap.service to {lvm2-activation-net,blk-availability}.service. Reduce max concurrent aios to avoid EMFILE with many devices. diff --git a/lib/metadata/raid_manip.c b/lib/metadata/raid_manip.c index 2bc179a..130cd34 100644 --- a/lib/metadata/raid_manip.c +++ b/lib/metadata/raid_manip.c @@ -6127,10 +6127,10 @@ static int _set_convenient_raid145610_segtype_to(const struct lv_segment *seg_fr /* striped/raid0 -> */ } else if (seg_is_striped(seg_from) || seg_is_any_raid0(seg_from)) { if (segtype_is_any_raid6(*segtype)) - seg_flag = SEG_RAID6_N_6; + seg_flag = seg_from->area_count < 3 ? SEG_RAID5_N : SEG_RAID6_N_6; - if (segtype_is_linear(*segtype) || - (!segtype_is_raid4(*segtype) && !segtype_is_raid10(*segtype) && !segtype_is_striped(*segtype))) + else if (segtype_is_linear(*segtype) || + (!segtype_is_raid4(*segtype) && !segtype_is_raid10(*segtype) && !segtype_is_striped(*segtype))) seg_flag = SEG_RAID5_N; /* raid1 -> */ diff --git a/test/shell/lvconvert-raid-takeover.sh b/test/shell/lvconvert-raid-takeover.sh index d1c5d30..d22c11b 100644 --- a/test/shell/lvconvert-raid-takeover.sh +++ b/test/shell/lvconvert-raid-takeover.sh @@ -108,11 +108,19 @@ function _invalid_raid5_conversions not _lvconvert raid6 raid6_n_6 4 6 $vg $lv1 } -# Check raid6 conversion constrainst of minimum 3 stripes -_lvcreate striped 2 2 4m $vg $lv1 -not _lvconvert raid6 raid6_n_6 2 4 $vg $lv1 -lvremove -y $vg +# Check raid6 conversion constrainst for 2 stripes +for type in striped raid0 raid0_meta +do + _lvcreate $type 2 2 4m $vg $lv1 + not _lvconvert raid6 raid6_n_6 2 4 $vg $lv1 + _lvconvert raid6 raid5_n 2 3 $vg $lv1 + _lvconvert raid6 raid5_n 3 4 $vg $lv1 + _lvconvert raid6 raid6_n_6 3 5 $vg $lv1 + lvremove -y $vg +done + +# Check raid6 conversion constrainst of minimum 3 stripes _lvcreate raid0 3 3 4m $vg $lv1 _lvconvert raid6 raid6_n_6 3 5 $vg $lv1 lvremove -y $vg

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

lvm2-commits September 2018