master - [radix-tree] alternative radix-tree implementation.
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=4d964133e267b2b501a...
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
//----------------------------------------------------------------
5 years, 6 months
master - [bcache] Remove unused 'hash' field from blocks.
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=3255e384dbd567a4d6d...
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;
5 years, 6 months
master - tests: remove lvmetad variation
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=07d2794a1640f05a451...
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
5 years, 6 months
master - tests: drop lvmetad parts of system_id test
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=b070c14a8b70dd8b8f4...
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
5 years, 6 months
master - tests: drop lvmetad bits
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=3bcc6c7e6064bd96325...
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
5 years, 6 months
master - lvconvert: allow raid4 -> linear conversion request
by Heinz Mauelshagen
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=989626926c98cd00f02...
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
5 years, 6 months
master - lvconvert: fix interim segtype regression on raid6 conversions
by Heinz Mauelshagen
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=e2e30a64ab106029514...
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
5 years, 6 months