master - tests: some missed skip with lvmlockd
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6a44dceb4895fc3e1b8...
Commit: 6a44dceb4895fc3e1b89cad0050bc766250d91a4
Parent: 5ac9f8d631cc6b340f4d3ad2cc35021e42d36ef6
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Wed May 23 13:04:47 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Wed May 30 09:25:45 2018 -0500
tests: some missed skip with lvmlockd
---
test/shell/dmstats-create.sh | 1 +
test/shell/dmstats-report.sh | 1 +
test/shell/lv-ancestry.sh | 1 +
test/shell/lvconvert-repair-cache.sh | 1 +
test/shell/process-each-lv.sh | 2 ++
test/shell/pv-ext-update.sh | 1 +
test/shell/relative-sign-options.sh | 1 +
test/shell/vg-check-devs-used.sh | 1 +
8 files changed, 9 insertions(+), 0 deletions(-)
diff --git a/test/shell/dmstats-create.sh b/test/shell/dmstats-create.sh
index c16f26f..03406ae 100644
--- a/test/shell/dmstats-create.sh
+++ b/test/shell/dmstats-create.sh
@@ -11,6 +11,7 @@
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
. lib/inittest
diff --git a/test/shell/dmstats-report.sh b/test/shell/dmstats-report.sh
index 0312149..bd72f1a 100644
--- a/test/shell/dmstats-report.sh
+++ b/test/shell/dmstats-report.sh
@@ -11,6 +11,7 @@
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
. lib/inittest
diff --git a/test/shell/lv-ancestry.sh b/test/shell/lv-ancestry.sh
index 732499f..c36f366 100644
--- a/test/shell/lv-ancestry.sh
+++ b/test/shell/lv-ancestry.sh
@@ -11,6 +11,7 @@
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
. lib/inittest
diff --git a/test/shell/lvconvert-repair-cache.sh b/test/shell/lvconvert-repair-cache.sh
index 4b9d8b8..6afb7ea 100644
--- a/test/shell/lvconvert-repair-cache.sh
+++ b/test/shell/lvconvert-repair-cache.sh
@@ -13,6 +13,7 @@
# Test repairing of broken cached LV
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
. lib/inittest
diff --git a/test/shell/process-each-lv.sh b/test/shell/process-each-lv.sh
index e9cea81..9482a08 100644
--- a/test/shell/process-each-lv.sh
+++ b/test/shell/process-each-lv.sh
@@ -11,6 +11,7 @@
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
test_description='Exercise toollib process_each_lv'
+
SKIP_WITH_LVMPOLLD=1
# disable lvmetad logging as it bogs down test systems
@@ -18,6 +19,7 @@ export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-}
. lib/inittest
+
aux prepare_devs 10
#
diff --git a/test/shell/pv-ext-update.sh b/test/shell/pv-ext-update.sh
index cfaece7..44f301e 100644
--- a/test/shell/pv-ext-update.sh
+++ b/test/shell/pv-ext-update.sh
@@ -12,6 +12,7 @@
# lvmetad does not handle pool labels so skip test.
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
. lib/inittest
diff --git a/test/shell/relative-sign-options.sh b/test/shell/relative-sign-options.sh
index 2db281a..2a36f1f 100644
--- a/test/shell/relative-sign-options.sh
+++ b/test/shell/relative-sign-options.sh
@@ -12,6 +12,7 @@
test_description='Exercise toollib process_each_lv'
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
# disable lvmetad logging as it bogs down test systems
export LVM_TEST_LVMETAD_DEBUG_OPTS=${LVM_TEST_LVMETAD_DEBUG_OPTS-}
diff --git a/test/shell/vg-check-devs-used.sh b/test/shell/vg-check-devs-used.sh
index 7d44812..9b99ef7 100644
--- a/test/shell/vg-check-devs-used.sh
+++ b/test/shell/vg-check-devs-used.sh
@@ -11,6 +11,7 @@
# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
SKIP_WITH_LVMPOLLD=1
+SKIP_WITH_LVMLOCKD=1
. lib/inittest
5 years, 10 months
master - tests: fix skipping logic for lvmpolld and lvmlockd
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=5ac9f8d631cc6b340f4...
Commit: 5ac9f8d631cc6b340f4d3ad2cc35021e42d36ef6
Parent: 6d14d5d16b92c520b5f4ee464f171684cac40735
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Wed May 23 12:56:33 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Wed May 30 09:25:45 2018 -0500
tests: fix skipping logic for lvmpolld and lvmlockd
---
test/lib/inittest.sh | 4 +++-
1 files changed, 3 insertions(+), 1 deletions(-)
diff --git a/test/lib/inittest.sh b/test/lib/inittest.sh
index 5e900c0..c48ea13 100644
--- a/test/lib/inittest.sh
+++ b/test/lib/inittest.sh
@@ -59,7 +59,7 @@ 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" && 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
@@ -172,6 +172,8 @@ test -n "$LVM_TEST_LVMPOLLD" && {
aux prepare_lvmpolld
}
+export SHARED=""
+
if test -n "$LVM_TEST_LVMLOCKD" ; then
if test -n "$LVM_TEST_LOCK_TYPE_SANLOCK" ; then
aux lvmconf 'local/host_id = 1'
5 years, 10 months
master - scan: removed failed paths for devices
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6d14d5d16b92c520b5f...
Commit: 6d14d5d16b92c520b5f4ee464f171684cac40735
Parent: 06c789eda19445d5e59a9c8044d91300fa1d2000
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Tue May 29 17:02:27 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Wed May 30 09:05:18 2018 -0500
scan: removed failed paths for devices
Drop a device path when the scan fails to open it.
---
lib/device/dev-cache.c | 187 +++++++++++++++++++++++++++++++++------
lib/device/dev-cache.h | 2 +
lib/filters/filter-persistent.c | 10 ++-
lib/label/label.c | 65 +++++++++++---
4 files changed, 219 insertions(+), 45 deletions(-)
diff --git a/lib/device/dev-cache.c b/lib/device/dev-cache.c
index dd01558..c866ff9 100644
--- a/lib/device/dev-cache.c
+++ b/lib/device/dev-cache.c
@@ -333,10 +333,8 @@ static int _add_alias(struct device *dev, const char *path)
/* Is name already there? */
dm_list_iterate_items(strl, &dev->aliases) {
- if (!strcmp(strl->str, path)) {
- log_debug_devs("%s: Already in device cache", path);
+ if (!strcmp(strl->str, path))
return 1;
- }
}
sl->str = path;
@@ -344,13 +342,7 @@ static int _add_alias(struct device *dev, const char *path)
if (!dm_list_empty(&dev->aliases)) {
oldpath = dm_list_item(dev->aliases.n, struct dm_str_list)->str;
prefer_old = _compare_paths(path, oldpath);
- log_debug_devs("%s: Aliased to %s in device cache%s (%d:%d)",
- path, oldpath, prefer_old ? "" : " (preferred name)",
- (int) MAJOR(dev->dev), (int) MINOR(dev->dev));
-
- } else
- log_debug_devs("%s: Added to device cache (%d:%d)", path,
- (int) MAJOR(dev->dev), (int) MINOR(dev->dev));
+ }
if (prefer_old)
dm_list_add(&dev->aliases, &sl->list);
@@ -667,12 +659,37 @@ struct dm_list *dev_cache_get_dev_list_for_lvid(const char *lvid)
}
/*
+ * Scanning code calls this when it fails to open a device using
+ * this path. The path is dropped from dev-cache. In the next
+ * dev_cache_scan it may be added again, but it could be for a
+ * different device.
+ */
+
+void dev_cache_failed_path(struct device *dev, const char *path)
+{
+ struct device *dev_by_path;
+ struct dm_str_list *strl;
+
+ if ((dev_by_path = (struct device *) dm_hash_lookup(_cache.names, path)))
+ dm_hash_remove(_cache.names, path);
+
+ dm_list_iterate_items(strl, &dev->aliases) {
+ if (!strcmp(strl->str, path)) {
+ dm_list_del(&strl->list);
+ break;
+ }
+ }
+}
+
+/*
* Either creates a new dev, or adds an alias to
* an existing dev.
*/
static int _insert_dev(const char *path, dev_t d)
{
struct device *dev;
+ struct device *dev_by_devt;
+ struct device *dev_by_path;
static dev_t loopfile_count = 0;
int loopfile = 0;
char *path_copy;
@@ -685,8 +702,26 @@ static int _insert_dev(const char *path, dev_t d)
loopfile = 1;
}
- /* is this device already registered ? */
- if (!(dev = (struct device *) btree_lookup(_cache.devices, (uint32_t) d))) {
+ dev_by_devt = (struct device *) btree_lookup(_cache.devices, (uint32_t) d);
+ dev_by_path = (struct device *) dm_hash_lookup(_cache.names, path);
+ dev = dev_by_devt;
+
+ /*
+ * Existing device, existing path points to the same device.
+ */
+ if (dev_by_devt && dev_by_path && (dev_by_devt == dev_by_path)) {
+ log_debug_devs("Found dev %d:%d %s - exists. %.8s",
+ (int)MAJOR(d), (int)MINOR(d), path, dev->pvid);
+ return 1;
+ }
+
+ /*
+ * No device or path found, add devt to cache.devices, add name to cache.names.
+ */
+ if (!dev_by_devt && !dev_by_path) {
+ log_debug_devs("Found dev %d:%d %s - new.",
+ (int)MAJOR(d), (int)MINOR(d), path);
+
if (!(dev = (struct device *) btree_lookup(_cache.sysfs_only_devices, (uint32_t) d))) {
/* create new device */
if (loopfile) {
@@ -701,30 +736,126 @@ static int _insert_dev(const char *path, dev_t d)
_free(dev);
return 0;
}
- }
- if (dm_hash_lookup(_cache.names, path) == dev) {
- /* Hash already has matching entry present */
- log_debug("%s: Path already cached.", path);
+ if (!(path_copy = dm_pool_strdup(_cache.mem, path))) {
+ log_error("Failed to duplicate path string.");
+ return 0;
+ }
+
+ if (!loopfile && !_add_alias(dev, path_copy)) {
+ log_error("Couldn't add alias to dev cache.");
+ return 0;
+ }
+
+ if (!dm_hash_insert(_cache.names, path_copy, dev)) {
+ log_error("Couldn't add name to hash in dev cache.");
+ return 0;
+ }
+
return 1;
}
- if (!(path_copy = dm_pool_strdup(_cache.mem, path))) {
- log_error("Failed to duplicate path string.");
- return 0;
+ /*
+ * Existing device, path is new, add path as a new alias for the device.
+ */
+ if (dev_by_devt && !dev_by_path) {
+ log_debug_devs("Found dev %d:%d %s - new alias.",
+ (int)MAJOR(d), (int)MINOR(d), path);
+
+ if (!(path_copy = dm_pool_strdup(_cache.mem, path))) {
+ log_error("Failed to duplicate path string.");
+ return 0;
+ }
+
+ if (!loopfile && !_add_alias(dev, path_copy)) {
+ log_error("Couldn't add alias to dev cache.");
+ return 0;
+ }
+
+ if (!dm_hash_insert(_cache.names, path_copy, dev)) {
+ log_error("Couldn't add name to hash in dev cache.");
+ return 0;
+ }
+
+ return 1;
}
- if (!loopfile && !_add_alias(dev, path_copy)) {
- log_error("Couldn't add alias to dev cache.");
- return 0;
+ /*
+ * No existing device, but path exists and previously pointed
+ * to a different device.
+ */
+ if (!dev_by_devt && dev_by_path) {
+ log_debug_devs("Found dev %d:%d %s - new device, path was previously %d:%d.",
+ (int)MAJOR(d), (int)MINOR(d), path,
+ (int)MAJOR(dev_by_path->dev), (int)MINOR(dev_by_path->dev));
+
+ if (!(dev = (struct device *) btree_lookup(_cache.sysfs_only_devices, (uint32_t) d))) {
+ /* create new device */
+ if (loopfile) {
+ if (!(dev = dev_create_file(path, NULL, NULL, 0)))
+ return_0;
+ } else if (!(dev = _dev_create(d)))
+ return_0;
+ }
+
+ if (!(btree_insert(_cache.devices, (uint32_t) d, dev))) {
+ log_error("Couldn't insert device into binary tree.");
+ _free(dev);
+ return 0;
+ }
+
+ if (!(path_copy = dm_pool_strdup(_cache.mem, path))) {
+ log_error("Failed to duplicate path string.");
+ return 0;
+ }
+
+ if (!loopfile && !_add_alias(dev, path_copy)) {
+ log_error("Couldn't add alias to dev cache.");
+ return 0;
+ }
+
+ dm_hash_remove(_cache.names, path);
+
+ if (!dm_hash_insert(_cache.names, path_copy, dev)) {
+ log_error("Couldn't add name to hash in dev cache.");
+ return 0;
+ }
+
+ return 1;
+
}
- if (!dm_hash_insert(_cache.names, path_copy, dev)) {
- log_error("Couldn't add name to hash in dev cache.");
- return 0;
+ /*
+ * Existing device, and path exists and previously pointed to
+ * a different device.
+ */
+ if (dev_by_devt && dev_by_path) {
+ log_debug_devs("Found dev %d:%d %s - existing device, path was previously %d:%d.",
+ (int)MAJOR(d), (int)MINOR(d), path,
+ (int)MAJOR(dev_by_path->dev), (int)MINOR(dev_by_path->dev));
+
+ if (!(path_copy = dm_pool_strdup(_cache.mem, path))) {
+ log_error("Failed to duplicate path string.");
+ return 0;
+ }
+
+ if (!loopfile && !_add_alias(dev, path_copy)) {
+ log_error("Couldn't add alias to dev cache.");
+ return 0;
+ }
+
+ dm_hash_remove(_cache.names, path);
+
+ if (!dm_hash_insert(_cache.names, path_copy, dev)) {
+ log_error("Couldn't add name to hash in dev cache.");
+ return 0;
+ }
+
+ return 1;
}
- return 1;
+ log_error("Found dev %d:%d %s - failed to use.", (int)MAJOR(d), (int)MINOR(d), path);
+ return 0;
}
static char *_join(const char *dir, const char *name)
@@ -1064,10 +1195,8 @@ static int _insert(const char *path, const struct stat *info,
if (rec && !_insert_dir(path))
return_0;
} else { /* add a device */
- if (!S_ISBLK(info->st_mode)) {
- log_debug_devs("%s: Not a block device", path);
+ if (!S_ISBLK(info->st_mode))
return 1;
- }
if (!_insert_dev(path, info->st_rdev))
return_0;
diff --git a/lib/device/dev-cache.h b/lib/device/dev-cache.h
index 4797274..df6ba0e 100644
--- a/lib/device/dev-cache.h
+++ b/lib/device/dev-cache.h
@@ -70,4 +70,6 @@ struct device *dev_iter_get(struct dev_iter *iter);
void dev_reset_error_count(struct cmd_context *cmd);
+void dev_cache_failed_path(struct device *dev, const char *path);
+
#endif
diff --git a/lib/filters/filter-persistent.c b/lib/filters/filter-persistent.c
index 3fa57f1..e4659aa 100644
--- a/lib/filters/filter-persistent.c
+++ b/lib/filters/filter-persistent.c
@@ -286,10 +286,18 @@ out:
static int _lookup_p(struct dev_filter *f, struct device *dev)
{
struct pfilter *pf = (struct pfilter *) f->private;
- void *l = dm_hash_lookup(pf->devices, dev_name(dev));
+ void *l;
struct dm_str_list *sl;
int pass = 1;
+ if (dm_list_empty(&dev->aliases)) {
+ log_debug_devs("%d:%d: filter cache skipping (no name)",
+ (int)MAJOR(dev->dev), (int)MINOR(dev->dev));
+ return 0;
+ }
+
+ l = dm_hash_lookup(pf->devices, dev_name(dev));
+
/* Cached bad, skip dev */
if (l == PF_BAD_DEVICE) {
log_debug_devs("%s: filter cache skipping (cached bad)", dev_name(dev));
diff --git a/lib/label/label.c b/lib/label/label.c
index 8ecaa61..97a4359 100644
--- a/lib/label/label.c
+++ b/lib/label/label.c
@@ -501,15 +501,6 @@ retry_open:
(int)MAJOR(sbuf.st_rdev), (int)MINOR(sbuf.st_rdev));
}
- /*
- * FIXME: do we want to try opening this device using
- * one of the other path aliases for the same
- * major:minor from dev->aliases? We could iterate
- * through those aliases to try opening each of them to
- * find one that works. What are the consequences of
- * using a different, non-preferred alias to a device?
- */
-
if (!retried) {
/*
* FIXME: remove this, the theory for this retry is that
@@ -550,6 +541,37 @@ static int _scan_dev_close(struct device *dev)
return 1;
}
+static void _drop_bad_aliases(struct device *dev)
+{
+ struct dm_str_list *strl, *strl2;
+ const char *name;
+ struct stat sbuf;
+ int major = (int)MAJOR(dev->dev);
+ int minor = (int)MINOR(dev->dev);
+ int bad;
+
+ dm_list_iterate_items_safe(strl, strl2, &dev->aliases) {
+ name = strl->str;
+ bad = 0;
+
+ if (stat(name, &sbuf)) {
+ bad = 1;
+ log_debug_devs("Device path check %d:%d %s stat failed errno %d",
+ major, minor, name, errno);
+ } else if (sbuf.st_rdev != dev->dev) {
+ bad = 1;
+ log_debug_devs("Device path check %d:%d %s stat %d:%d does not match.",
+ major, minor, name,
+ (int)MAJOR(sbuf.st_rdev), (int)MINOR(sbuf.st_rdev));
+ }
+
+ if (bad) {
+ log_debug_devs("Device path check %d:%d dropping path %s.", major, minor, name);
+ dev_cache_failed_path(dev, name);
+ }
+ }
+}
+
/*
* Read or reread label/metadata from selected devs.
*
@@ -635,7 +657,11 @@ static int _scan_list(struct cmd_context *cmd, struct dev_filter *f,
scan_failed_count++;
lvmcache_del_dev(devl->dev);
} else {
- log_debug_devs("Processing data from device %s fd %d block %p", dev_name(devl->dev), devl->dev->bcache_fd, bb);
+ log_debug_devs("Processing data from device %s %d:%d fd %d block %p",
+ dev_name(devl->dev),
+ (int)MAJOR(devl->dev->dev),
+ (int)MINOR(devl->dev->dev),
+ devl->dev->bcache_fd, bb);
ret = _process_block(cmd, f, devl->dev, bb, 0, 0, &is_lvm_device);
@@ -675,11 +701,6 @@ static int _scan_list(struct cmd_context *cmd, struct dev_filter *f,
* to open the devs on the reopen_devs list.
*
* FIXME: it's not clear if or why this helps.
- *
- * FIXME: should we delete the first path name from dev->aliases that
- * we failed to open the first time before retrying? If that path
- * still exists on the system, dev_cache_scan should put it back, but
- * if it doesn't exist we don't want to try using it again.
*/
if (!dm_list_empty(&reopen_devs)) {
if (retried_open) {
@@ -690,6 +711,20 @@ static int _scan_list(struct cmd_context *cmd, struct dev_filter *f,
}
retried_open = 1;
+ dm_list_iterate_items_safe(devl, devl2, &reopen_devs) {
+ _drop_bad_aliases(devl->dev);
+
+ if (dm_list_empty(&devl->dev->aliases)) {
+ log_warn("WARNING: Scan ignoring device %d:%d with no paths.",
+ (int)MAJOR(devl->dev->dev),
+ (int)MINOR(devl->dev->dev));
+
+ dm_list_del(&devl->list);
+ lvmcache_del_dev(devl->dev);
+ scan_failed_count++;
+ }
+ }
+
/*
* This will search the system's /dev for new path names and
* could help us reopen the device if it finds a new preferred
5 years, 11 months
master - radix-tree: fix some bugs in remove_prefix and iterate
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=06c789eda19445d5e59...
Commit: 06c789eda19445d5e59a9c8044d91300fa1d2000
Parent: 1924426ad1e8a569c168e3d85c368ed531f382fe
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Wed May 30 14:14:59 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Wed May 30 14:21:27 2018 +0100
radix-tree: fix some bugs in remove_prefix and iterate
These weren't working if the prefix key was part of a prefix_chain.
---
base/data-struct/radix-tree.c | 22 ++++++++++++++-
test/unit/radix_tree_t.c | 56 +++++++++++++++++++++++++++++++++++++++++
2 files changed, 76 insertions(+), 2 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
index 8e8ac90..222b350 100644
--- a/base/data-struct/radix-tree.c
+++ b/base/data-struct/radix-tree.c
@@ -736,11 +736,29 @@ bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_e
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;
+}
+
unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke)
{
unsigned count = 0;
struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke);
- if (lr.kb == ke) {
+ if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) {
count = _free_node(rt, *lr.v);
lr.v->type = UNSET;
}
@@ -837,7 +855,7 @@ 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)
+ if (lr.kb == ke || _prefix_chain_matches(&lr, ke))
_iterate(lr.v, it);
}
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
index ba0d5e1..7266a8a 100644
--- a/test/unit/radix_tree_t.c
+++ b/test/unit/radix_tree_t.c
@@ -289,6 +289,18 @@ static void test_remove_prefix(void *fixture)
T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 1), count);
}
+static void test_remove_prefix_single(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ uint8_t k[4];
+ union radix_value v;
+
+ _gen_key(k, k + sizeof(k));
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 2), 1);
+}
+
static void test_size(void *fixture)
{
struct radix_tree *rt = fixture;
@@ -367,6 +379,47 @@ static void test_iterate_subset(void *fixture)
T_ASSERT_EQUAL(vt.count, subset_count);
}
+static void test_iterate_single(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ uint8_t k[6];
+ union radix_value v;
+ struct visitor vt;
+
+ _gen_key(k, k + sizeof(k));
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+
+ vt.count = 0;
+ vt.it.visit = _visit;
+ radix_tree_iterate(rt, k, k + 3, &vt.it);
+ T_ASSERT_EQUAL(vt.count, 1);
+}
+
+static void test_iterate_vary_middle(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i;
+ uint8_t k[6];
+ union radix_value v;
+ struct visitor vt;
+
+ _gen_key(k, k + sizeof(k));
+ for (i = 0; i < 16; i++) {
+ k[3] = i;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ vt.it.visit = _visit;
+ for (i = 0; i < 16; i++) {
+ vt.count = 0;
+ k[3] = i;
+ radix_tree_iterate(rt, k, k + 4, &vt.it);
+ T_ASSERT_EQUAL(vt.count, 1);
+ }
+}
+
//----------------------------------------------------------------
#define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn)
@@ -392,9 +445,12 @@ void radix_tree_tests(struct dm_list *all_tests)
T("remove-prefix-keys", "remove a set of keys that have common prefixes", test_remove_prefix_keys);
T("remove-prefix-keys-reversed", "remove a set of keys that have common prefixes (reversed)", test_remove_prefix_keys_reversed);
T("remove-prefix", "remove a subrange", test_remove_prefix);
+ T("remove-prefix-single", "remove a subrange with a single entry", test_remove_prefix_single);
T("size-spots-duplicates", "duplicate entries aren't counted twice", test_size);
T("iterate-all", "iterate all entries in tree", test_iterate_all);
T("iterate-subset", "iterate a subset of entries in tree", test_iterate_subset);
+ T("iterate-single", "iterate a subset that contains a single entry", test_iterate_single);
+ T("iterate-vary-middle", "iterate keys that vary in the middle", test_iterate_vary_middle);
dm_list_add(all_tests, &ts->list);
}
5 years, 11 months
master - radix-tree: radix_tree_iterate()
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=1924426ad1e8a569c16...
Commit: 1924426ad1e8a569c168e3d85c368ed531f382fe
Parent: c2a8bbed3bc8c5c4f505a7cecc4db0b94e7243bc
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Tue May 29 17:58:58 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Tue May 29 17:58:58 2018 +0100
radix-tree: radix_tree_iterate()
---
base/data-struct/radix-tree.c | 142 +++++++++++++++++++++++++++++++----------
base/data-struct/radix-tree.h | 12 ++++
test/unit/radix_tree_t.c | 82 +++++++++++++++++++++++
3 files changed, 201 insertions(+), 35 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
index 5688dec..8e8ac90 100644
--- a/base/data-struct/radix-tree.c
+++ b/base/data-struct/radix-tree.c
@@ -172,9 +172,14 @@ void radix_tree_destroy(struct radix_tree *rt)
free(rt);
}
-static bool _insert(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv);
+unsigned radix_tree_size(struct radix_tree *rt)
+{
+ return rt->nr_entries;
+}
-static bool _insert_unset(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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;
@@ -182,6 +187,7 @@ static bool _insert_unset(struct value *v, uint8_t *kb, uint8_t *ke, union radix
// value
v->type = VALUE;
v->value = rv;
+ rt->nr_entries++;
} else {
// prefix -> value
struct prefix_chain *pc = zalloc(sizeof(*pc) + len);
@@ -194,12 +200,13 @@ static bool _insert_unset(struct value *v, uint8_t *kb, uint8_t *ke, union radix
memcpy(pc->prefix, kb, len);
v->type = PREFIX_CHAIN;
v->value.ptr = pc;
+ rt->nr_entries++;
}
return true;
}
-static bool _insert_value(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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;
@@ -214,7 +221,7 @@ static bool _insert_value(struct value *v, uint8_t *kb, uint8_t *ke, union radix
return false;
vc->value = v->value;
- if (!_insert(&vc->child, kb, ke, rv)) {
+ if (!_insert(rt, &vc->child, kb, ke, rv)) {
free(vc);
return false;
}
@@ -226,10 +233,10 @@ static bool _insert_value(struct value *v, uint8_t *kb, uint8_t *ke, union radix
return true;
}
-static bool _insert_value_chain(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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(&vc->child, kb, ke, rv);
+ return _insert(rt, &vc->child, kb, ke, rv);
}
static unsigned min(unsigned lhs, unsigned rhs)
@@ -240,7 +247,7 @@ static unsigned min(unsigned lhs, unsigned rhs)
return rhs;
}
-static bool _insert_prefix_chain(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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;
@@ -264,7 +271,7 @@ static bool _insert_prefix_chain(struct value *v, uint8_t *kb, uint8_t *ke, unio
pc->child.value.ptr = pc2;
pc->len = i;
- if (!_insert(&pc->child, kb + i, ke, rv)) {
+ if (!_insert(rt, &pc->child, kb + i, ke, rv)) {
free(pc2);
return false;
}
@@ -276,7 +283,7 @@ static bool _insert_prefix_chain(struct value *v, uint8_t *kb, uint8_t *ke, unio
return false;
n4->keys[0] = *kb;
- if (!_insert(n4->values, kb + 1, ke, rv)) {
+ if (!_insert(rt, n4->values, kb + 1, ke, rv)) {
free(n4);
return false;
}
@@ -302,7 +309,7 @@ static bool _insert_prefix_chain(struct value *v, uint8_t *kb, uint8_t *ke, unio
return true;
}
-static bool _insert_node4(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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) {
@@ -315,7 +322,7 @@ static bool _insert_node4(struct value *v, uint8_t *kb, uint8_t *ke, union radix
memcpy(n16->values, n4->values, sizeof(n4->values));
n16->keys[4] = *kb;
- if (!_insert(n16->values + 4, kb + 1, ke, rv)) {
+ if (!_insert(rt, n16->values + 4, kb + 1, ke, rv)) {
free(n16);
return false;
}
@@ -324,7 +331,7 @@ static bool _insert_node4(struct value *v, uint8_t *kb, uint8_t *ke, union radix
v->value.ptr = n16;
} else {
n4 = v->value.ptr;
- if (!_insert(n4->values + n4->nr_entries, kb + 1, ke, rv))
+ if (!_insert(rt, n4->values + n4->nr_entries, kb + 1, ke, rv))
return false;
n4->keys[n4->nr_entries] = *kb;
@@ -333,7 +340,7 @@ static bool _insert_node4(struct value *v, uint8_t *kb, uint8_t *ke, union radix
return true;
}
-static bool _insert_node16(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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;
@@ -353,7 +360,7 @@ static bool _insert_node16(struct value *v, uint8_t *kb, uint8_t *ke, union radi
}
n48->keys[*kb] = 16;
- if (!_insert(n48->values + 16, kb + 1, ke, rv)) {
+ if (!_insert(rt, n48->values + 16, kb + 1, ke, rv)) {
free(n48);
return false;
}
@@ -362,7 +369,7 @@ static bool _insert_node16(struct value *v, uint8_t *kb, uint8_t *ke, union radi
v->type = NODE48;
v->value.ptr = n48;
} else {
- if (!_insert(n16->values + n16->nr_entries, kb + 1, ke, rv))
+ if (!_insert(rt, n16->values + n16->nr_entries, kb + 1, ke, rv))
return false;
n16->keys[n16->nr_entries] = *kb;
n16->nr_entries++;
@@ -371,7 +378,7 @@ static bool _insert_node16(struct value *v, uint8_t *kb, uint8_t *ke, union radi
return true;
}
-static bool _insert_node48(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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) {
@@ -387,7 +394,7 @@ static bool _insert_node48(struct value *v, uint8_t *kb, uint8_t *ke, union radi
n256->values[i] = n48->values[n48->keys[i]];
}
- if (!_insert(n256->values + *kb, kb + 1, ke, rv)) {
+ if (!_insert(rt, n256->values + *kb, kb + 1, ke, rv)) {
free(n256);
return false;
}
@@ -397,7 +404,7 @@ static bool _insert_node48(struct value *v, uint8_t *kb, uint8_t *ke, union radi
v->value.ptr = n256;
} else {
- if (!_insert(n48->values + n48->nr_entries, kb + 1, ke, rv))
+ if (!_insert(rt, n48->values + n48->nr_entries, kb + 1, ke, rv))
return false;
n48->keys[*kb] = n48->nr_entries;
@@ -407,12 +414,12 @@ static bool _insert_node48(struct value *v, uint8_t *kb, uint8_t *ke, union radi
return true;
}
-static bool _insert_node256(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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 was_unset = n256->values[*kb].type == UNSET;
- if (!_insert(n256->values + *kb, kb + 1, ke, rv))
+ if (!_insert(rt, n256->values + *kb, kb + 1, ke, rv))
return false;
if (was_unset)
@@ -422,12 +429,13 @@ static bool _insert_node256(struct value *v, uint8_t *kb, uint8_t *ke, union rad
}
// FIXME: the tree should not be touched if insert fails (eg, OOM)
-static bool _insert(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+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;
@@ -441,34 +449,35 @@ static bool _insert(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value
vc->child = *v;
v->type = VALUE_CHAIN;
v->value.ptr = vc;
+ rt->nr_entries++;
}
return true;
}
switch (v->type) {
case UNSET:
- return _insert_unset(v, kb, ke, rv);
+ return _insert_unset(rt, v, kb, ke, rv);
case VALUE:
- return _insert_value(v, kb, ke, rv);
+ return _insert_value(rt, v, kb, ke, rv);
case VALUE_CHAIN:
- return _insert_value_chain(v, kb, ke, rv);
+ return _insert_value_chain(rt, v, kb, ke, rv);
case PREFIX_CHAIN:
- return _insert_prefix_chain(v, kb, ke, rv);
+ return _insert_prefix_chain(rt, v, kb, ke, rv);
case NODE4:
- return _insert_node4(v, kb, ke, rv);
+ return _insert_node4(rt, v, kb, ke, rv);
case NODE16:
- return _insert_node16(v, kb, ke, rv);
+ return _insert_node16(rt, v, kb, ke, rv);
case NODE48:
- return _insert_node48(v, kb, ke, rv);
+ return _insert_node48(rt, v, kb, ke, rv);
case NODE256:
- return _insert_node256(v, kb, ke, rv);
+ return _insert_node256(rt, v, kb, ke, rv);
}
// can't get here
@@ -546,12 +555,7 @@ static struct lookup_result _lookup_prefix(struct value *v, uint8_t *kb, uint8_t
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);
- if (_insert(lr.v, lr.kb, ke, rv)) {
- rt->nr_entries++;
- return true;
- }
-
- return false;
+ return _insert(rt, lr.v, lr.kb, ke, rv);
}
// Note the degrade functions also free the original node.
@@ -769,4 +773,72 @@ bool radix_tree_lookup(struct radix_tree *rt,
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)
+ _iterate(lr.v, it);
+}
+
//----------------------------------------------------------------
diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h
index ad8a952..1b6aee8 100644
--- a/base/data-struct/radix-tree.h
+++ b/base/data-struct/radix-tree.h
@@ -41,6 +41,18 @@ unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *prefix_b, uint
bool radix_tree_lookup(struct radix_tree *rt,
uint8_t *kb, uint8_t *ke, union radix_value *result);
+// The radix tree stores entries in lexicographical order. Which means
+// we can iterate entries, in order. Or iterate entries with a particular
+// prefix.
+struct radix_tree_iterator {
+ // Returns false if the iteration should end.
+ bool (*visit)(struct radix_tree_iterator *it,
+ uint8_t *kb, uint8_t *ke, union radix_value v);
+};
+
+void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke,
+ struct radix_tree_iterator *it);
+
//----------------------------------------------------------------
#endif
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
index eb35773..ba0d5e1 100644
--- a/test/unit/radix_tree_t.c
+++ b/test/unit/radix_tree_t.c
@@ -11,6 +11,7 @@
// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
#include "base/data-struct/radix-tree.h"
+#include "base/memory/container_of.h"
#include "units.h"
@@ -288,6 +289,84 @@ static void test_remove_prefix(void *fixture)
T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 1), count);
}
+static void test_size(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, dup_count = 0;
+ uint8_t k[2];
+ union radix_value v;
+
+ // populate some random 16bit keys
+ for (i = 0; i < 10000; i++) {
+ _gen_key(k, k + sizeof(k));
+ if (radix_tree_lookup(rt, k, k + sizeof(k), &v))
+ dup_count++;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT_EQUAL(radix_tree_size(rt), 10000 - dup_count);
+}
+
+struct visitor {
+ struct radix_tree_iterator it;
+ unsigned count;
+};
+
+static bool _visit(struct radix_tree_iterator *it,
+ uint8_t *kb, uint8_t *ke, union radix_value v)
+{
+ struct visitor *vt = container_of(it, struct visitor, it);
+ vt->count++;
+ return true;
+}
+
+static void test_iterate_all(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i;
+ uint8_t k[4];
+ union radix_value v;
+ struct visitor vt;
+
+ // populate some random 32bit keys
+ for (i = 0; i < 100000; i++) {
+ _gen_key(k, k + sizeof(k));
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ vt.count = 0;
+ vt.it.visit = _visit;
+ radix_tree_iterate(rt, NULL, NULL, &vt.it);
+ T_ASSERT_EQUAL(vt.count, radix_tree_size(rt));
+}
+
+static void test_iterate_subset(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, subset_count = 0;
+ uint8_t k[3];
+ union radix_value v;
+ struct visitor vt;
+
+ // populate some random 32bit keys
+ for (i = 0; i < 100000; i++) {
+ _gen_key(k, k + sizeof(k));
+ if (k[0] == 21 && k[1] == 12)
+ subset_count++;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ vt.count = 0;
+ vt.it.visit = _visit;
+ k[0] = 21;
+ k[1] = 12;
+ radix_tree_iterate(rt, k, k + 2, &vt.it);
+ T_ASSERT_EQUAL(vt.count, subset_count);
+}
+
//----------------------------------------------------------------
#define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn)
@@ -313,6 +392,9 @@ void radix_tree_tests(struct dm_list *all_tests)
T("remove-prefix-keys", "remove a set of keys that have common prefixes", test_remove_prefix_keys);
T("remove-prefix-keys-reversed", "remove a set of keys that have common prefixes (reversed)", test_remove_prefix_keys_reversed);
T("remove-prefix", "remove a subrange", test_remove_prefix);
+ T("size-spots-duplicates", "duplicate entries aren't counted twice", test_size);
+ T("iterate-all", "iterate all entries in tree", test_iterate_all);
+ T("iterate-subset", "iterate a subset of entries in tree", test_iterate_subset);
dm_list_add(all_tests, &ts->list);
}
5 years, 11 months
master - radix-tree: radix_tree_remove_prefix()
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c2a8bbed3bc8c5c4f50...
Commit: c2a8bbed3bc8c5c4f505a7cecc4db0b94e7243bc
Parent: 9b41efae826257ecfd9400d6a9d17d7e98e822dc
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Tue May 29 13:25:59 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Tue May 29 13:25:59 2018 +0100
radix-tree: radix_tree_remove_prefix()
---
base/data-struct/radix-tree.c | 33 +++++++++++++++++++++++++--------
base/data-struct/radix-tree.h | 4 ++++
test/unit/radix_tree_t.c | 22 ++++++++++++++++++++++
3 files changed, 51 insertions(+), 8 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
index 26748e3..5688dec 100644
--- a/base/data-struct/radix-tree.c
+++ b/base/data-struct/radix-tree.c
@@ -101,9 +101,10 @@ static inline void _dtr(struct radix_tree *rt, union radix_value v)
rt->dtr(rt->dtr_context, v);
}
-static void _free_node(struct radix_tree *rt, struct value v)
+// Returns the number of values removed
+static unsigned _free_node(struct radix_tree *rt, struct value v)
{
- unsigned i;
+ unsigned i, nr = 0;
struct value_chain *vc;
struct prefix_chain *pc;
struct node4 *n4;
@@ -117,49 +118,52 @@ static void _free_node(struct radix_tree *rt, struct value v)
case VALUE:
_dtr(rt, v.value);
+ nr = 1;
break;
case VALUE_CHAIN:
vc = v.value.ptr;
_dtr(rt, vc->value);
- _free_node(rt, vc->child);
+ nr = 1 + _free_node(rt, vc->child);
free(vc);
break;
case PREFIX_CHAIN:
pc = v.value.ptr;
- _free_node(rt, pc->child);
+ 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++)
- _free_node(rt, n4->values[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++)
- _free_node(rt, n16->values[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++)
- _free_node(rt, n48->values[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++)
- _free_node(rt, n256->values[i]);
+ nr += _free_node(rt, n256->values[i]);
free(n256);
break;
}
+
+ return nr;
}
void radix_tree_destroy(struct radix_tree *rt)
@@ -728,6 +732,19 @@ bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_e
return false;
}
+unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke)
+{
+ unsigned count = 0;
+ struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke);
+ if (lr.kb == ke) {
+ count = _free_node(rt, *lr.v);
+ lr.v->type = UNSET;
+ }
+
+ rt->nr_entries -= count;
+ return count;
+}
+
bool radix_tree_lookup(struct radix_tree *rt,
uint8_t *kb, uint8_t *ke, union radix_value *result)
{
diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h
index 8560b34..ad8a952 100644
--- a/base/data-struct/radix-tree.h
+++ b/base/data-struct/radix-tree.h
@@ -34,6 +34,10 @@ void radix_tree_destroy(struct radix_tree *rt);
unsigned radix_tree_size(struct radix_tree *rt);
bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value v);
bool radix_tree_remove(struct radix_tree *rt, uint8_t *kb, uint8_t *ke);
+
+// Returns the number of values removed
+unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *prefix_b, uint8_t *prefix_e);
+
bool radix_tree_lookup(struct radix_tree *rt,
uint8_t *kb, uint8_t *ke, union radix_value *result);
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
index d2b0adc..eb35773 100644
--- a/test/unit/radix_tree_t.c
+++ b/test/unit/radix_tree_t.c
@@ -267,6 +267,27 @@ static void test_remove_prefix_keys_reversed(void *fixture)
T_ASSERT(!radix_tree_lookup(rt, k, k + i, &v));
}
+static void test_remove_prefix(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, count = 0;
+ uint8_t k[4];
+ union radix_value v;
+
+ // populate some random 32bit keys
+ for (i = 0; i < 100000; i++) {
+ _gen_key(k, k + sizeof(k));
+ if (k[0] == 21)
+ count++;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ // remove keys in a sub range
+ k[0] = 21;
+ T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 1), count);
+}
+
//----------------------------------------------------------------
#define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn)
@@ -291,6 +312,7 @@ void radix_tree_tests(struct dm_list *all_tests)
T("remove-one-byte-keys", "remove many one byte keys", test_remove_one_byte_keys);
T("remove-prefix-keys", "remove a set of keys that have common prefixes", test_remove_prefix_keys);
T("remove-prefix-keys-reversed", "remove a set of keys that have common prefixes (reversed)", test_remove_prefix_keys_reversed);
+ T("remove-prefix", "remove a subrange", test_remove_prefix);
dm_list_add(all_tests, &ts->list);
}
5 years, 11 months
master - radix-tree: call the value dtr when removing an entry.
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=9b41efae826257ecfd9...
Commit: 9b41efae826257ecfd9400d6a9d17d7e98e822dc
Parent: 0181c77e3fe0fd4c82b10e283d4852a09ff78452
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Tue May 29 11:23:36 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Tue May 29 11:23:36 2018 +0100
radix-tree: call the value dtr when removing an entry.
---
base/data-struct/radix-tree.c | 46 +++++++++++++++++++++++-----------------
1 files changed, 26 insertions(+), 20 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
index 3df85e7..26748e3 100644
--- a/base/data-struct/radix-tree.c
+++ b/base/data-struct/radix-tree.c
@@ -95,7 +95,13 @@ struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context)
return rt;
}
-static void _free_node(struct value v, radix_value_dtr dtr, void *context)
+static inline void _dtr(struct radix_tree *rt, union radix_value v)
+{
+ if (rt->dtr)
+ rt->dtr(rt->dtr_context, v);
+}
+
+static void _free_node(struct radix_tree *rt, struct value v)
{
unsigned i;
struct value_chain *vc;
@@ -110,49 +116,47 @@ static void _free_node(struct value v, radix_value_dtr dtr, void *context)
break;
case VALUE:
- if (dtr)
- dtr(context, v.value);
+ _dtr(rt, v.value);
break;
case VALUE_CHAIN:
vc = v.value.ptr;
- if (dtr)
- dtr(context, vc->value);
- _free_node(vc->child, dtr, context);
+ _dtr(rt, vc->value);
+ _free_node(rt, vc->child);
free(vc);
break;
case PREFIX_CHAIN:
pc = v.value.ptr;
- _free_node(pc->child, dtr, context);
+ _free_node(rt, pc->child);
free(pc);
break;
case NODE4:
n4 = (struct node4 *) v.value.ptr;
for (i = 0; i < n4->nr_entries; i++)
- _free_node(n4->values[i], dtr, context);
+ _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++)
- _free_node(n16->values[i], dtr, context);
+ _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++)
- _free_node(n48->values[i], dtr, context);
+ _free_node(rt, n48->values[i]);
free(n48);
break;
case NODE256:
n256 = (struct node256 *) v.value.ptr;
for (i = 0; i < 256; i++)
- _free_node(n256->values[i], dtr, context);
+ _free_node(rt, n256->values[i]);
free(n256);
break;
}
@@ -160,7 +164,7 @@ static void _free_node(struct value v, radix_value_dtr dtr, void *context)
void radix_tree_destroy(struct radix_tree *rt)
{
- _free_node(rt->root, rt->dtr, rt->dtr_context);
+ _free_node(rt, rt->root);
free(rt);
}
@@ -593,7 +597,7 @@ static void _degrade_to_n48(struct node256 *n256, struct value *result)
result->value.ptr = n48;
}
-static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
+static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke)
{
bool r;
unsigned i;
@@ -607,10 +611,12 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
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;
@@ -627,7 +633,7 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
case VALUE_CHAIN:
vc = root->value.ptr;
- r = _remove(&vc->child, kb, ke);
+ r = _remove(rt, &vc->child, kb, ke);
if (r && (vc->child.type == UNSET)) {
memcpy(root, &vc->child, sizeof(*root));
free(vc);
@@ -643,13 +649,13 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
if (kb[i] != pc->prefix[i])
return false;
- return _remove(&pc->child, kb + pc->len, ke);
+ return _remove(rt, &pc->child, kb + pc->len, ke);
case NODE4:
n4 = root->value.ptr;
for (i = 0; i < n4->nr_entries; i++) {
if (n4->keys[i] == *kb) {
- r = _remove(n4->values + i, kb + 1, ke);
+ r = _remove(rt, n4->values + i, kb + 1, ke);
if (r && n4->values[i].type == UNSET) {
n4->nr_entries--;
if (i < n4->nr_entries)
@@ -668,7 +674,7 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
n16 = root->value.ptr;
for (i = 0; i < n16->nr_entries; i++) {
if (n16->keys[i] == *kb) {
- r = _remove(n16->values + i, kb + 1, ke);
+ r = _remove(rt, n16->values + i, kb + 1, ke);
if (r && n16->values[i].type == UNSET) {
n16->nr_entries--;
if (i < n16->nr_entries)
@@ -687,7 +693,7 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
n48 = root->value.ptr;
i = n48->keys[*kb];
if (i < 48) {
- r = _remove(n48->values + i, kb + 1, ke);
+ r = _remove(rt, n48->values + i, kb + 1, ke);
if (r && n48->values[i].type == UNSET) {
n48->keys[*kb] = 48;
n48->nr_entries--;
@@ -700,7 +706,7 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
case NODE256:
n256 = root->value.ptr;
- r = _remove(n256->values + (*kb), kb + 1, ke);
+ r = _remove(rt, n256->values + (*kb), kb + 1, ke);
if (r && n256->values[*kb].type == UNSET) {
n256->nr_entries--;
if (n256->nr_entries <= 48)
@@ -714,7 +720,7 @@ static bool _remove(struct value *root, uint8_t *kb, uint8_t *ke)
bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_end)
{
- if (_remove(&rt->root, key_begin, key_end)) {
+ if (_remove(rt, &rt->root, key_begin, key_end)) {
rt->nr_entries--;
return true;
}
5 years, 11 months
master - Merge branch '2018-05-29-radix-tree-iterate' into 2018-05-23-radix-tree-remove
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=0181c77e3fe0fd4c82b...
Commit: 0181c77e3fe0fd4c82b10e283d4852a09ff78452
Parent: 6cd798f556b34c4c4171d536298d8f718f8aef62 033df741e2e771b3abda3e190ed9c359d579ce4a
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Tue May 29 11:04:32 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Tue May 29 11:04:32 2018 +0100
Merge branch '2018-05-29-radix-tree-iterate' into 2018-05-23-radix-tree-remove
.gitignore | 52 +++++++++++++++-
VERSION | 2 +-
VERSION_DM | 2 +-
WHATS_NEW | 25 ++++----
WHATS_NEW_DM | 7 ++-
base/data-struct/radix-tree.c | 10 ++-
base/data-struct/radix-tree.h | 7 +-
doc/release-notes/2.02.178 | 53 ++++++++++++++++
lib/device/dev-cache.c | 2 +
lib/format_text/archive.c | 4 +-
lib/label/label.c | 115 +++++++++++++++++++++++++++++++---
man/dmeventd.8_main | 4 +-
man/vgexport.8_pregen | 19 +++++-
test/lib/aux.sh | 30 ++++++---
test/shell/lvmetad-pvscan-md.sh | 3 +-
test/shell/pvcreate-md-fake-hdr.sh | 94 ++++++++++++++++++++++++++++
test/shell/pvcreate-operation-md.sh | 17 ++++-
test/unit/radix_tree_t.c | 4 +-
18 files changed, 388 insertions(+), 62 deletions(-)
5 years, 11 months
master - data-struct/radix-tree: pass the value dtr into create.
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=033df741e2e771b3abd...
Commit: 033df741e2e771b3abda3e190ed9c359d579ce4a
Parent: 28c8e95d197bf512a39b561281162ff4d93a598e
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Tue May 29 11:03:10 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Tue May 29 11:03:10 2018 +0100
data-struct/radix-tree: pass the value dtr into create.
Rather than having to pass it into every method that removes items.
---
base/data-struct/radix-tree.c | 10 +++++++---
base/data-struct/radix-tree.h | 7 +++----
test/unit/radix_tree_t.c | 4 ++--
3 files changed, 12 insertions(+), 9 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
index b4b6791..c50bd43 100644
--- a/base/data-struct/radix-tree.c
+++ b/base/data-struct/radix-tree.c
@@ -74,17 +74,21 @@ struct node256 {
struct radix_tree {
unsigned nr_entries;
struct value root;
+ radix_value_dtr dtr;
+ void *dtr_context;
};
//----------------------------------------------------------------
-struct radix_tree *radix_tree_create(void)
+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;
@@ -153,9 +157,9 @@ static void _free_node(struct value v, radix_value_dtr dtr, void *context)
}
}
-void radix_tree_destroy(struct radix_tree *rt, radix_value_dtr dtr, void *context)
+void radix_tree_destroy(struct radix_tree *rt)
{
- _free_node(rt->root, dtr, context);
+ _free_node(rt->root, rt->dtr, rt->dtr_context);
free(rt);
}
diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h
index d84e3c5..13ab4cd 100644
--- a/base/data-struct/radix-tree.h
+++ b/base/data-struct/radix-tree.h
@@ -25,12 +25,11 @@ union radix_value {
uint64_t n;
};
-struct radix_tree *radix_tree_create(void);
-
typedef void (*radix_value_dtr)(void *context, union radix_value v);
-// dtr may be NULL
-void radix_tree_destroy(struct radix_tree *rt, radix_value_dtr dtr, void *context);
+// dtr will be called on any deleted entries. dtr may be NULL.
+struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context);
+void radix_tree_destroy(struct radix_tree *rt);
unsigned radix_tree_size(struct radix_tree *rt);
bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value v);
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
index 4455f2b..245ec8d 100644
--- a/test/unit/radix_tree_t.c
+++ b/test/unit/radix_tree_t.c
@@ -21,14 +21,14 @@
static void *rt_init(void)
{
- struct radix_tree *rt = radix_tree_create();
+ struct radix_tree *rt = radix_tree_create(NULL, NULL);
T_ASSERT(rt);
return rt;
}
static void rt_exit(void *fixture)
{
- radix_tree_destroy(fixture, NULL, NULL);
+ radix_tree_destroy(fixture);
}
static void test_create_destroy(void *fixture)
5 years, 11 months
master - radix_tree_t: knock out some debug
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6cd798f556b34c4c417...
Commit: 6cd798f556b34c4c4171d536298d8f718f8aef62
Parent: b7fd8ac8ebf07f7a8119aae723f40ef6f85273ce
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Wed May 23 12:54:02 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Wed May 23 12:54:02 2018 +0100
radix_tree_t: knock out some debug
---
test/unit/radix_tree_t.c | 1 -
1 files changed, 0 insertions(+), 1 deletions(-)
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
index 9f2ba07..4cf394f 100644
--- a/test/unit/radix_tree_t.c
+++ b/test/unit/radix_tree_t.c
@@ -256,7 +256,6 @@ static void test_remove_prefix_keys_reversed(void *fixture)
}
for (i = 0; i < 32; i++) {
- fprintf(stderr, "removing %u\n", i);
T_ASSERT(radix_tree_remove(rt, k, k + (31 - i)));
for (j = 0; j < 31 - i; j++) {
T_ASSERT(radix_tree_lookup(rt, k, k + j, &v));
5 years, 11 months