lvm2-commits May 2018

lvm2-commits@lists.fedorahosted.org

6 participants
217 discussions

master - tests: some missed skip with lvmlockd
by David Teigland 31 May '18

31 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6a44dceb4895fc3e1b89c… 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

1 0

master - tests: fix skipping logic for lvmpolld and lvmlockd
by David Teigland 31 May '18

31 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=5ac9f8d631cc6b340f4d3… 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'

1 0

master - scan: removed failed paths for devices
by David Teigland 30 May '18

30 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6d14d5d16b92c520b5f4e… 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

1 0

master - radix-tree: fix some bugs in remove_prefix and iterate
by Joe Thornber 30 May '18

30 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=06c789eda19445d5e59a9… 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); }

1 0

master - radix-tree: radix_tree_iterate()
by Joe Thornber 29 May '18

29 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=1924426ad1e8a569c168e… 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); }

1 0

master - radix-tree: radix_tree_remove_prefix()
by Joe Thornber 29 May '18

29 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c2a8bbed3bc8c5c4f505a… 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); }

1 0

master - radix-tree: call the value dtr when removing an entry.
by Joe Thornber 29 May '18

29 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=9b41efae826257ecfd940… 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; }

1 0

master - Merge branch '2018-05-29-radix-tree-iterate' into 2018-05-23-radix-tree-remove
by Joe Thornber 29 May '18

29 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=0181c77e3fe0fd4c82b10… 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(-)

1 0

master - data-struct/radix-tree: pass the value dtr into create.
by Joe Thornber 29 May '18

29 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=033df741e2e771b3abda3… 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)

1 0

master - radix_tree_t: knock out some debug
by Joe Thornber 29 May '18

29 May '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6cd798f556b34c4c4171d… 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));

1 0

← Newer
1
2
3
4
5
6
7
...
22
Older →

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

lvm2-commits May 2018