lvm2-commits June 2018

lvm2-commits@lists.fedorahosted.org

6 participants
181 discussions

master - radix-tree: squash a pointer arithmetic warning
by Joe Thornber 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=254e5c5d119447bcb8b16… Commit: 254e5c5d119447bcb8b160a4b4e5b0c36e9af5ba Parent: 18528180d9f588e265747f4710a8767756454b4c Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Jun 21 17:41:56 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jun 21 17:41:56 2018 +0100 radix-tree: squash a pointer arithmetic warning --- base/data-struct/radix-tree.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index ffbf029..1d24dad 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -628,7 +628,7 @@ static void _erase_elt(void *array, unsigned obj_size, unsigned count, unsigned obj_size * (count - index - 1)); // Zero the now unused last elt (set's v.type to UNSET) - memset(array + (count - 1) * obj_size, 0, obj_size); + memset(((uint8_t *) array) + (count - 1) * obj_size, 0, obj_size); } static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke)

1 0

master - Merge branch 'master' of git+ssh://sourceware.org/git/lvm2
by Joe Thornber 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=18528180d9f588e265747… Commit: 18528180d9f588e265747f4710a8767756454b4c Parent: 72e2e92f4c23b75efdf08ee5a4019b6beb86b9f1 dd7ebec12028a65081f676b5f52215b012c75c88 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Jun 21 17:12:09 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jun 21 17:12:09 2018 +0100 Merge branch 'master' of git+ssh://sourceware.org/git/lvm2 lib/commands/toolcontext.c | 18 --------- lib/config/config_settings.h | 2 +- lib/device/dev-cache.c | 80 +++------------------------------------ lib/device/dev-cache.h | 2 - lib/filters/filter-persistent.c | 7 ++- lib/metadata/mirror.c | 2 +- 6 files changed, 13 insertions(+), 98 deletions(-)

1 0

master - radix-tree: fix bug when erasing elts in remove_prefix
by Joe Thornber 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=72e2e92f4c23b75efdf08… Commit: 72e2e92f4c23b75efdf08ee5a4019b6beb86b9f1 Parent: 40c1f7889fd88ce4a2f2b42c594db3deb8f84593 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Jun 21 17:10:05 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jun 21 17:10:05 2018 +0100 radix-tree: fix bug when erasing elts in remove_prefix _erase_elt() now zeroes the last element of the array (ie. sets to UNSET). Previously remove() was doing this, but not remove_prefix(). --- base/data-struct/radix-tree.c | 12 ++++++------ 1 files changed, 6 insertions(+), 6 deletions(-) diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index 202d463..ffbf029 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -626,6 +626,9 @@ static void _erase_elt(void *array, unsigned obj_size, unsigned count, unsigned memmove(((uint8_t *) array) + (obj_size * index), ((uint8_t *) array) + (obj_size * (index + 1)), obj_size * (count - index - 1)); + + // Zero the now unused last elt (set's v.type to UNSET) + memset(array + (count - 1) * obj_size, 0, obj_size); } static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke) @@ -700,7 +703,6 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint } n4->nr_entries--; - n4->values[n4->nr_entries].type = UNSET; if (!n4->nr_entries) { free(n4); root->type = UNSET; @@ -723,7 +725,6 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint } n16->nr_entries--; - n16->values[n16->nr_entries].type = UNSET; if (n16->nr_entries <= 4) { _degrade_to_n4(n16, root); } @@ -745,7 +746,6 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint n48->keys[j]--; _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); n48->nr_entries--; - n48->values[n48->nr_entries].type = UNSET; if (n48->nr_entries <= 16) _degrade_to_n16(n48, root); } @@ -1066,7 +1066,7 @@ static bool _check_nodes(struct value *v, unsigned *count) for (i = n4->nr_entries; i < 4; i++) if (n4->values[i].type != UNSET) { - fprintf(stderr, "unused value is not UNSET\n"); + fprintf(stderr, "unused value is not UNSET (n4)\n"); return false; } @@ -1080,7 +1080,7 @@ static bool _check_nodes(struct value *v, unsigned *count) for (i = n16->nr_entries; i < 16; i++) if (n16->values[i].type != UNSET) { - fprintf(stderr, "unused value is not UNSET\n"); + fprintf(stderr, "unused value is not UNSET (n16)\n"); return false; } @@ -1105,7 +1105,7 @@ static bool _check_nodes(struct value *v, unsigned *count) for (i = n48->nr_entries; i < 48; i++) if (n48->values[i].type != UNSET) { - fprintf(stderr, "unused value is not UNSET\n"); + fprintf(stderr, "unused value is not UNSET (n48)\n"); return false; }

1 0

master - filter: use pointers to real addresses
by David Teigland 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=dd7ebec12028a65081f67… Commit: dd7ebec12028a65081f676b5f52215b012c75c88 Parent: 15826214f94da5a447f34ae9d237f1f018d3bac3 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Jun 21 10:52:35 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Jun 21 10:54:43 2018 -0500 filter: use pointers to real addresses instead of casting values 1 and 2 to pointers which gcc optimization can have problems with. --- lib/filters/filter-persistent.c | 7 +++++-- 1 files changed, 5 insertions(+), 2 deletions(-) diff --git a/lib/filters/filter-persistent.c b/lib/filters/filter-persistent.c index 1782bfa..130b1e5 100644 --- a/lib/filters/filter-persistent.c +++ b/lib/filters/filter-persistent.c @@ -43,12 +43,15 @@ struct pfilter { * do this. */ +static int _good_device; +static int _bad_device; + /* * The hash table holds one of these two states * against each entry. */ -#define PF_BAD_DEVICE ((void *) 1) -#define PF_GOOD_DEVICE ((void *) 2) +#define PF_BAD_DEVICE ((void *) &_good_device) +#define PF_GOOD_DEVICE ((void *) &_bad_device) static int _init_hash(struct pfilter *pf) {

1 0

master - Remove code for using files as devices
by David Teigland 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=15826214f94da5a447f34… Commit: 15826214f94da5a447f34ae9d237f1f018d3bac3 Parent: e166d2b14ca22ead559a5898cc229ecbcc261007 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Jun 21 09:33:21 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Jun 21 09:33:21 2018 -0500 Remove code for using files as devices It appears this has not been used in a long time, and it seems to have no point since loop devices exist. --- lib/commands/toolcontext.c | 18 --------- lib/config/config_settings.h | 2 +- lib/device/dev-cache.c | 80 +++-------------------------------------- lib/device/dev-cache.h | 2 - 4 files changed, 7 insertions(+), 95 deletions(-) diff --git a/lib/commands/toolcontext.c b/lib/commands/toolcontext.c index 50474c1..eb15581 100644 --- a/lib/commands/toolcontext.c +++ b/lib/commands/toolcontext.c @@ -1030,24 +1030,6 @@ static int _init_dev_cache(struct cmd_context *cmd) } } - if (!(cn = find_config_tree_array(cmd, devices_loopfiles_CFG, NULL))) - return 1; - - for (cv = cn->v; cv; cv = cv->next) { - if (cv->type != DM_CFG_STRING) { - log_error("Invalid string in config file: " - "devices/loopfiles"); - return 0; - } - - if (!dev_cache_add_loopfile(cv->v.str)) { - log_error("Failed to add loopfile %s to internal " - "device cache", cv->v.str); - return 0; - } - } - - return 1; } diff --git a/lib/config/config_settings.h b/lib/config/config_settings.h index ac0f0ff..7cb266c 100644 --- a/lib/config/config_settings.h +++ b/lib/config/config_settings.h @@ -226,7 +226,7 @@ cfg(devices_dir_CFG, "dir", devices_CFG_SECTION, CFG_ADVANCED, CFG_TYPE_STRING, cfg_array(devices_scan_CFG, "scan", devices_CFG_SECTION, CFG_ADVANCED, CFG_TYPE_STRING, "#S/dev", vsn(1, 0, 0), NULL, 0, NULL, "Directories containing device nodes to use with LVM.\n") -cfg_array(devices_loopfiles_CFG, "loopfiles", devices_CFG_SECTION, CFG_DEFAULT_UNDEFINED | CFG_UNSUPPORTED, CFG_TYPE_STRING, NULL, vsn(1, 2, 0), NULL, 0, NULL, NULL) +cfg_array(devices_loopfiles_CFG, "loopfiles", devices_CFG_SECTION, CFG_DEFAULT_UNDEFINED | CFG_UNSUPPORTED, CFG_TYPE_STRING, NULL, vsn(1, 2, 0), NULL, vsn(3, 0, 0), NULL, NULL) cfg(devices_obtain_device_list_from_udev_CFG, "obtain_device_list_from_udev", devices_CFG_SECTION, 0, CFG_TYPE_BOOL, DEFAULT_OBTAIN_DEVICE_LIST_FROM_UDEV, vsn(2, 2, 85), NULL, 0, NULL, "Obtain the list of available devices from udev.\n" diff --git a/lib/device/dev-cache.c b/lib/device/dev-cache.c index a0d98a3..59e00ae 100644 --- a/lib/device/dev-cache.c +++ b/lib/device/dev-cache.c @@ -690,18 +690,8 @@ 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; - /* Generate pretend device numbers for loopfiles */ - if (!d) { - if (dm_hash_lookup(_cache.names, path)) - return 1; - d = ++loopfile_count; - loopfile = 1; - } - 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; @@ -724,10 +714,7 @@ static int _insert_dev(const char *path, dev_t d) 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))) + if (!(dev = _dev_create(d))) return_0; } @@ -742,7 +729,7 @@ static int _insert_dev(const char *path, dev_t d) return 0; } - if (!loopfile && !_add_alias(dev, path_copy)) { + if (!_add_alias(dev, path_copy)) { log_error("Couldn't add alias to dev cache."); return 0; } @@ -767,7 +754,7 @@ static int _insert_dev(const char *path, dev_t d) return 0; } - if (!loopfile && !_add_alias(dev, path_copy)) { + if (!_add_alias(dev, path_copy)) { log_error("Couldn't add alias to dev cache."); return 0; } @@ -791,10 +778,7 @@ static int _insert_dev(const char *path, dev_t d) 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))) + if (!(dev = _dev_create(d))) return_0; } @@ -809,7 +793,7 @@ static int _insert_dev(const char *path, dev_t d) return 0; } - if (!loopfile && !_add_alias(dev, path_copy)) { + if (!_add_alias(dev, path_copy)) { log_error("Couldn't add alias to dev cache."); return 0; } @@ -839,7 +823,7 @@ static int _insert_dev(const char *path, dev_t d) return 0; } - if (!loopfile && !_add_alias(dev, path_copy)) { + if (!_add_alias(dev, path_copy)) { log_error("Couldn't add alias to dev cache."); return 0; } @@ -919,26 +903,6 @@ static int _insert_dir(const char *dir) return r; } -static int _insert_file(const char *path) -{ - struct stat info; - - if (stat(path, &info) < 0) { - log_sys_very_verbose("stat", path); - return 0; - } - - if (!S_ISREG(info.st_mode)) { - log_debug_devs("%s: Not a regular file", path); - return 0; - } - - if (!_insert_dev(path, 0)) - return_0; - - return 1; -} - static int _dev_cache_iterate_devs_for_index(void) { struct btree_iter *iter = btree_first(_cache.devices); @@ -1207,8 +1171,6 @@ static int _insert(const char *path, const struct stat *info, void dev_cache_scan(void) { - struct dir_list *dl; - log_debug_devs("Creating list of system devices."); _cache.has_scanned = 1; @@ -1216,9 +1178,6 @@ void dev_cache_scan(void) _insert_dirs(&_cache.dirs); (void) dev_cache_index_devs(); - - dm_list_iterate_items(dl, &_cache.files) - _insert_file(dl->dir); } int dev_cache_has_scanned(void) @@ -1317,7 +1276,6 @@ int dev_cache_init(struct cmd_context *cmd) } dm_list_init(&_cache.dirs); - dm_list_init(&_cache.files); if (!_init_preferred_names(cmd)) goto_bad; @@ -1411,32 +1369,6 @@ int dev_cache_add_dir(const char *path) return 1; } -int dev_cache_add_loopfile(const char *path) -{ - struct dir_list *dl; - struct stat st; - - if (stat(path, &st)) { - log_warn("Ignoring %s: %s.", path, strerror(errno)); - /* But don't fail */ - return 1; - } - - if (!S_ISREG(st.st_mode)) { - log_warn("Ignoring %s: Not a regular file.", path); - return 1; - } - - if (!(dl = _zalloc(sizeof(*dl) + strlen(path) + 1))) { - log_error("dir_list allocation failed for file"); - return 0; - } - - strcpy(dl->dir, path); - dm_list_add(&_cache.files, &dl->list); - return 1; -} - /* Check cached device name is still valid before returning it */ /* This should be a rare occurrence */ /* set quiet if the cache is expected to be out-of-date */ diff --git a/lib/device/dev-cache.h b/lib/device/dev-cache.h index 6386ba9..41c4a9c 100644 --- a/lib/device/dev-cache.h +++ b/lib/device/dev-cache.h @@ -51,8 +51,6 @@ void dev_cache_scan(void); int dev_cache_has_scanned(void); int dev_cache_add_dir(const char *path); -int dev_cache_add_loopfile(const char *path); -__attribute__((nonnull(1))) struct device *dev_cache_get(struct cmd_context *cmd, const char *name, struct dev_filter *f); const char *dev_cache_filtered_reason(const char *name);

1 0

master - lvmlockd: fix another missing lock_type null check
by David Teigland 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=e166d2b14ca22ead559a5… Commit: e166d2b14ca22ead559a5898cc229ecbcc261007 Parent: 40c1f7889fd88ce4a2f2b42c594db3deb8f84593 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Jun 21 09:00:23 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Jun 21 09:24:51 2018 -0500 lvmlockd: fix another missing lock_type null check Same as 347c807f8. --- lib/metadata/mirror.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-) diff --git a/lib/metadata/mirror.c b/lib/metadata/mirror.c index 11f2a8f..58615d8 100644 --- a/lib/metadata/mirror.c +++ b/lib/metadata/mirror.c @@ -698,7 +698,7 @@ static int _split_mirror_images(struct logical_volume *lv, return 0; } - if (!strcmp(lv->vg->lock_type, "dlm")) + if (lv->vg->lock_type && !strcmp(lv->vg->lock_type, "dlm")) new_lv->lock_args = lv->lock_args; if (!dm_list_empty(&split_images)) {

1 0

master - radix-tree: FIx various bugs to do with removal
by Joe Thornber 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=20b9746c5d22de385e32f… Commit: 20b9746c5d22de385e32f5be9a8f04754be2c706 Parent: 42f7caf1c267a5b75ee38ea77a7e2fd7c582e704 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Jun 19 10:19:06 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jun 21 09:49:08 2018 +0100 radix-tree: FIx various bugs to do with removal Add radix_tree_is_well_formed() which does some sanity checking of the tree. Call the above a lot in the unit tests. Fix revealed bugs. --- base/data-struct/radix-tree.c | 342 +++++++++++++++++++++++++++++++++++++---- base/data-struct/radix-tree.h | 4 + test/unit/Makefile | 1 - test/unit/radix_tree_t.c | 146 +++++++++++++++++- 4 files changed, 457 insertions(+), 36 deletions(-) diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index 222b350..24455e1 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -387,11 +387,10 @@ static bool _insert_node48(struct radix_tree *rt, struct value *v, uint8_t *kb, if (!n256) return false; + n256->nr_entries = 49; for (i = 0; i < 256; i++) { - if (n48->keys[i] >= 48) - continue; - - n256->values[i] = n48->values[n48->keys[i]]; + if (n48->keys[i] < 48) + n256->values[i] = n48->values[n48->keys[i]]; } if (!_insert(rt, n256->values + *kb, kb + 1, ke, rv)) { @@ -417,15 +416,13 @@ static bool _insert_node48(struct radix_tree *rt, struct value *v, uint8_t *kb, 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(rt, n256->values + *kb, kb + 1, ke, rv)) - return false; + bool r, was_unset = n256->values[*kb].type == UNSET; - if (was_unset) + r = _insert(rt, n256->values + *kb, kb + 1, ke, rv); + if (r && was_unset) n256->nr_entries++; - return true; + return r; } // FIXME: the tree should not be touched if insert fails (eg, OOM) @@ -546,7 +543,9 @@ static struct lookup_result _lookup_prefix(struct value *v, uint8_t *kb, uint8_t case NODE256: n256 = v->value.ptr; - return _lookup_prefix(n256->values + *kb, kb + 1, ke); + if (n256->values[*kb].type != UNSET) + return _lookup_prefix(n256->values + *kb, kb + 1, ke); + break; } return (struct lookup_result) {.v = v, .kb = kb}; @@ -574,11 +573,19 @@ static void _degrade_to_n4(struct node16 *n16, struct value *result) static void _degrade_to_n16(struct node48 *n48, struct value *result) { - struct node4 *n16 = zalloc(sizeof(*n16)); + unsigned i, count = 0; + struct node16 *n16 = zalloc(sizeof(*n16)); n16->nr_entries = n48->nr_entries; - memcpy(n16->keys, n48->keys, n48->nr_entries * sizeof(*n16->keys)); + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) { + n16->keys[count] = i; + count++; + } + } + memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values)); + free(n48); result->type = NODE16; @@ -588,27 +595,42 @@ static void _degrade_to_n16(struct node48 *n48, struct value *result) static void _degrade_to_n48(struct node256 *n256, struct value *result) { unsigned i, count = 0; - struct node4 *n48 = zalloc(sizeof(*n48)); + struct node48 *n48 = zalloc(sizeof(*n48)); + + memset(n48->keys, 48, sizeof(n48->keys)); n48->nr_entries = n256->nr_entries; for (i = 0; i < 256; i++) { if (n256->values[i].type == UNSET) continue; - n48->keys[count] = i; + n48->keys[i] = count; n48->values[count] = n256->values[i]; count++; } + free(n256); result->type = NODE48; result->value.ptr = n48; } +// Removes an entry in an array by sliding the values above it down. +static void _erase_elt(void *array, unsigned obj_size, unsigned count, unsigned index) +{ + if (index == (count - 1)) + // The simple case + return; + + memmove(((uint8_t *) array) + (obj_size * index), + ((uint8_t *) array) + (obj_size * (index + 1)), + obj_size * (count - index - 1)); +} + static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke) { bool r; - unsigned i; + unsigned i, j; struct value_chain *vc; struct prefix_chain *pc; struct node4 *n4; @@ -643,7 +665,8 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint vc = root->value.ptr; r = _remove(rt, &vc->child, kb, ke); if (r && (vc->child.type == UNSET)) { - memcpy(root, &vc->child, sizeof(*root)); + root->type = VALUE; + root->value = vc->value; free(vc); } return r; @@ -657,7 +680,12 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint if (kb[i] != pc->prefix[i]) return false; - return _remove(rt, &pc->child, kb + pc->len, ke); + r = _remove(rt, &pc->child, kb + pc->len, ke); + if (r && pc->child.type == UNSET) { + root->type = UNSET; + free(pc); + } + return r; case NODE4: n4 = root->value.ptr; @@ -665,13 +693,16 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint if (n4->keys[i] == *kb) { r = _remove(rt, n4->values + i, kb + 1, ke); if (r && n4->values[i].type == UNSET) { + if (i < n4->nr_entries) { + _erase_elt(n4->keys, sizeof(*n4->keys), n4->nr_entries, i); + _erase_elt(n4->values, sizeof(*n4->values), n4->nr_entries, i); + } + n4->nr_entries--; - if (i < n4->nr_entries) - // slide the entries down - memmove(n4->keys + i, n4->keys + i + 1, - sizeof(*n4->keys) * (n4->nr_entries - i)); - if (!n4->nr_entries) + if (!n4->nr_entries) { + free(n4); root->type = UNSET; + } } return r; } @@ -684,13 +715,15 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint if (n16->keys[i] == *kb) { r = _remove(rt, n16->values + i, kb + 1, ke); if (r && n16->values[i].type == UNSET) { + if (i < n16->nr_entries) { + _erase_elt(n16->keys, sizeof(*n16->keys), n16->nr_entries, i); + _erase_elt(n16->values, sizeof(*n16->values), n16->nr_entries, i); + } + n16->nr_entries--; - if (i < n16->nr_entries) - // slide the entries down - memmove(n16->keys + i, n16->keys + i + 1, - sizeof(*n16->keys) * (n16->nr_entries - i)); - if (n16->nr_entries <= 4) + if (n16->nr_entries <= 4) { _degrade_to_n4(n16, root); + } } return r; } @@ -704,6 +737,10 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint r = _remove(rt, n48->values + i, kb + 1, ke); if (r && n48->values[i].type == UNSET) { n48->keys[*kb] = 48; + for (j = 0; j < 256; j++) + if (n48->keys[j] < 48 && n48->keys[j] > i) + n48->keys[j]--; + _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); n48->nr_entries--; if (n48->nr_entries <= 16) _degrade_to_n16(n48, root); @@ -736,6 +773,8 @@ 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 @@ -754,19 +793,141 @@ static bool _prefix_chain_matches(struct lookup_result *lr, uint8_t *ke) return false; } +static bool _remove_subtree(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke, unsigned *count) +{ + bool r; + unsigned i, j, len; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (kb == ke) { + *count += _free_node(rt, *root); + root->type = UNSET; + return true; + } + + switch (root->type) { + case UNSET: + case VALUE: + // No entries with the given prefix + return true; + + case VALUE_CHAIN: + vc = root->value.ptr; + r = _remove_subtree(rt, &vc->child, kb, ke, count); + if (r && (vc->child.type == UNSET)) { + root->type = VALUE; + root->value = vc->value; + free(vc); + } + return r; + + case PREFIX_CHAIN: + pc = root->value.ptr; + len = min(pc->len, ke - kb); + for (i = 0; i < len; i++) + if (kb[i] != pc->prefix[i]) + return true; + + r = _remove_subtree(rt, &pc->child, len < pc->len ? ke : (kb + pc->len), ke, count); + if (r && pc->child.type == UNSET) { + root->type = UNSET; + free(pc); + } + return r; + + case NODE4: + n4 = root->value.ptr; + for (i = 0; i < n4->nr_entries; i++) { + if (n4->keys[i] == *kb) { + r = _remove_subtree(rt, n4->values + i, kb + 1, ke, count); + if (r && n4->values[i].type == UNSET) { + if (i < n4->nr_entries) { + _erase_elt(n4->keys, sizeof(*n4->keys), n4->nr_entries, i); + _erase_elt(n4->values, sizeof(*n4->values), n4->nr_entries, i); + } + + n4->nr_entries--; + if (!n4->nr_entries) { + free(n4); + root->type = UNSET; + } + } + return r; + } + } + return true; + + case NODE16: + n16 = root->value.ptr; + for (i = 0; i < n16->nr_entries; i++) { + if (n16->keys[i] == *kb) { + r = _remove_subtree(rt, n16->values + i, kb + 1, ke, count); + if (r && n16->values[i].type == UNSET) { + if (i < n16->nr_entries) { + _erase_elt(n16->keys, sizeof(*n16->keys), n16->nr_entries, i); + _erase_elt(n16->values, sizeof(*n16->values), n16->nr_entries, i); + } + + n16->nr_entries--; + if (n16->nr_entries <= 4) + _degrade_to_n4(n16, root); + } + return r; + } + } + return true; + + case NODE48: + n48 = root->value.ptr; + i = n48->keys[*kb]; + if (i < 48) { + r = _remove_subtree(rt, n48->values + i, kb + 1, ke, count); + if (r && n48->values[i].type == UNSET) { + n48->keys[*kb] = 48; + for (j = 0; j < 256; j++) + if (n48->keys[j] < 48 && n48->keys[j] > i) + n48->keys[j]--; + _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); + n48->nr_entries--; + if (n48->nr_entries <= 16) + _degrade_to_n16(n48, root); + } + return r; + } + return true; + + case NODE256: + n256 = root->value.ptr; + r = _remove_subtree(rt, n256->values + (*kb), kb + 1, ke, count); + if (r && n256->values[*kb].type == UNSET) { + n256->nr_entries--; + if (n256->nr_entries <= 48) + _degrade_to_n48(n256, root); + } + return r; + } + + // Shouldn't get here + return false; +} + unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) { unsigned count = 0; - struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); - if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) { - count = _free_node(rt, *lr.v); - lr.v->type = UNSET; - } - rt->nr_entries -= count; + if (_remove_subtree(rt, &rt->root, kb, ke, &count)) + rt->nr_entries -= count; + return count; } +//---------------------------------------------------------------- + bool radix_tree_lookup(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value *result) { @@ -860,3 +1021,116 @@ void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, } //---------------------------------------------------------------- +// Checks: +// 1) The number of entries matches rt->nr_entries +// 2) The number of entries is correct in each node + +static bool _check_nodes(struct value *v, unsigned *count) +{ + unsigned i, ncount; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + switch (v->type) { + case UNSET: + return true; + + case VALUE: + (*count)++; + return true; + + case VALUE_CHAIN: + (*count)++; + vc = v->value.ptr; + return _check_nodes(&vc->child, count); + + case PREFIX_CHAIN: + pc = v->value.ptr; + return _check_nodes(&pc->child, count); + + case NODE4: + n4 = v->value.ptr; + for (i = 0; i < n4->nr_entries; i++) + if (!_check_nodes(n4->values + i, count)) + return false; + return true; + + case NODE16: + n16 = v->value.ptr; + for (i = 0; i < n16->nr_entries; i++) + if (!_check_nodes(n16->values + i, count)) + return false; + return true; + + case NODE48: + n48 = v->value.ptr; + ncount = 0; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) { + ncount++; + if (!_check_nodes(n48->values + n48->keys[i], count)) + return false; + } + } + + if (ncount != n48->nr_entries) { + fprintf(stderr, "incorrect number of entries in n48, n48->nr_entries = %u, actual = %u\n", + n48->nr_entries, ncount); + return false; + } + + return true; + + case NODE256: + n256 = v->value.ptr; + + ncount = 0; + for (i = 0; i < 256; i++) { + struct value *v2 = n256->values + i; + + if (v2->type == UNSET) + continue; + + if (!_check_nodes(v2, count)) + return false; + + ncount++; + } + + if (ncount != n256->nr_entries) { + fprintf(stderr, "incorrect number of entries in n256, n256->nr_entries = %u, actual = %u\n", + n256->nr_entries, ncount); + return false; + } + + return true; + + default: + fprintf(stderr, "unknown value type: %u\n", v->type); + } + + fprintf(stderr, "shouldn't get here\n"); + return false; +} + +bool radix_tree_is_well_formed(struct radix_tree *rt) +{ + unsigned count = 0; + + if (!_check_nodes(&rt->root, &count)) + return false; + + if (rt->nr_entries != count) { + fprintf(stderr, "incorrect entry count: rt->nr_entries = %u, actual = %u\n", + rt->nr_entries, count); + return false; + } + + return true; +} + +//---------------------------------------------------------------- diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h index 1b6aee8..2deaf9a 100644 --- a/base/data-struct/radix-tree.h +++ b/base/data-struct/radix-tree.h @@ -53,6 +53,10 @@ struct radix_tree_iterator { void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, struct radix_tree_iterator *it); +// Checks that some constraints on the shape of the tree are +// being held. For debug only. +bool radix_tree_is_well_formed(struct radix_tree *rt); + //---------------------------------------------------------------- #endif diff --git a/test/unit/Makefile b/test/unit/Makefile index e7cc852..9155c47 100644 --- a/test/unit/Makefile +++ b/test/unit/Makefile @@ -11,7 +11,6 @@ # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA UNIT_SOURCE=\ - base/data-struct/radix-tree.c \ device_mapper/vdo/status.c \ \ test/unit/activation-generator_t.c \ diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c index 7266a8a..e2d11e8 100644 --- a/test/unit/radix_tree_t.c +++ b/test/unit/radix_tree_t.c @@ -44,6 +44,7 @@ static void test_insert_one(void *fixture) unsigned char k = 'a'; v.n = 65; T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v)); + T_ASSERT(radix_tree_is_well_formed(rt)); v.n = 0; T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v)); T_ASSERT_EQUAL(v.n, 65); @@ -62,6 +63,8 @@ static void test_single_byte_keys(void *fixture) T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); + for (i = 0; i < count; i++) { k = i; T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v)); @@ -82,12 +85,16 @@ static void test_overwrite_single_byte_keys(void *fixture) T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); + for (i = 0; i < count; i++) { k = i; v.n = 1000 + i; T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); + for (i = 0; i < count; i++) { k = i; T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v)); @@ -109,6 +116,8 @@ static void test_16_bit_keys(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); + for (i = 0; i < count; i++) { k[0] = i / 256; k[1] = i % 256; @@ -127,8 +136,10 @@ static void test_prefix_keys(void *fixture) k[1] = 200; v.n = 1024; T_ASSERT(radix_tree_insert(rt, k, k + 1, v)); + T_ASSERT(radix_tree_is_well_formed(rt)); v.n = 2345; T_ASSERT(radix_tree_insert(rt, k, k + 2, v)); + T_ASSERT(radix_tree_is_well_formed(rt)); T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v)); T_ASSERT_EQUAL(v.n, 1024); T_ASSERT(radix_tree_lookup(rt, k, k + 2, &v)); @@ -145,8 +156,10 @@ static void test_prefix_keys_reversed(void *fixture) k[1] = 200; v.n = 1024; T_ASSERT(radix_tree_insert(rt, k, k + 2, v)); + T_ASSERT(radix_tree_is_well_formed(rt)); v.n = 2345; T_ASSERT(radix_tree_insert(rt, k, k + 1, v)); + T_ASSERT(radix_tree_is_well_formed(rt)); T_ASSERT(radix_tree_lookup(rt, k, k + 2, &v)); T_ASSERT_EQUAL(v.n, 1024); T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v)); @@ -170,7 +183,10 @@ static void test_sparse_keys(void *fixture) _gen_key(k, k + sizeof(k)); v.n = 1234; T_ASSERT(radix_tree_insert(rt, k, k + 32, v)); + // FIXME: remove + //T_ASSERT(radix_tree_is_well_formed(rt)); } + T_ASSERT(radix_tree_is_well_formed(rt)); } static void test_remove_one(void *fixture) @@ -182,7 +198,9 @@ static void test_remove_one(void *fixture) _gen_key(k, k + sizeof(k)); v.n = 1234; T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + T_ASSERT(radix_tree_is_well_formed(rt)); T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k))); + T_ASSERT(radix_tree_is_well_formed(rt)); T_ASSERT(!radix_tree_lookup(rt, k, k + sizeof(k), &v)); } @@ -199,14 +217,19 @@ static void test_remove_one_byte_keys(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + 1, v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); for (i = 0; i < 256; i++) { k[0] = i; T_ASSERT(radix_tree_remove(rt, k, k + 1)); + T_ASSERT(radix_tree_is_well_formed(rt)); for (j = i + 1; j < 256; j++) { k[0] = j; T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v)); - T_ASSERT_EQUAL(v.n, j + 1000); + if (v.n != j + 1000) + test_fail("v.n (%u) != j + 1000 (%u)\n", + (unsigned) v.n, + (unsigned) j + 1000); } } @@ -216,6 +239,40 @@ static void test_remove_one_byte_keys(void *fixture) } } +static void test_remove_one_byte_keys_reversed(void *fixture) +{ + struct radix_tree *rt = fixture; + unsigned i, j; + uint8_t k[1]; + union radix_value v; + + for (i = 0; i < 256; i++) { + k[0] = i; + v.n = i + 1000; + T_ASSERT(radix_tree_insert(rt, k, k + 1, v)); + } + + T_ASSERT(radix_tree_is_well_formed(rt)); + for (i = 256; i; i--) { + k[0] = i - 1; + T_ASSERT(radix_tree_remove(rt, k, k + 1)); + T_ASSERT(radix_tree_is_well_formed(rt)); + + for (j = 0; j < i - 1; j++) { + k[0] = j; + T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v)); + if (v.n != j + 1000) + test_fail("v.n (%u) != j + 1000 (%u)\n", + (unsigned) v.n, + (unsigned) j + 1000); + } + } + + for (i = 0; i < 256; i++) { + k[0] = i; + T_ASSERT(!radix_tree_lookup(rt, k, k + 1, &v)); + } +} static void test_remove_prefix_keys(void *fixture) { struct radix_tree *rt = fixture; @@ -230,8 +287,10 @@ static void test_remove_prefix_keys(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + i, v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); for (i = 0; i < 32; i++) { T_ASSERT(radix_tree_remove(rt, k, k + i)); + T_ASSERT(radix_tree_is_well_formed(rt)); for (j = i + 1; j < 32; j++) { T_ASSERT(radix_tree_lookup(rt, k, k + j, &v)); T_ASSERT_EQUAL(v.n, j); @@ -256,8 +315,10 @@ static void test_remove_prefix_keys_reversed(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + i, v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); for (i = 0; i < 32; i++) { T_ASSERT(radix_tree_remove(rt, k, k + (31 - i))); + T_ASSERT(radix_tree_is_well_formed(rt)); for (j = 0; j < 31 - i; j++) { T_ASSERT(radix_tree_lookup(rt, k, k + j, &v)); T_ASSERT_EQUAL(v.n, j); @@ -284,9 +345,12 @@ static void test_remove_prefix(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); + // remove keys in a sub range k[0] = 21; T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 1), count); + T_ASSERT(radix_tree_is_well_formed(rt)); } static void test_remove_prefix_single(void *fixture) @@ -298,7 +362,9 @@ static void test_remove_prefix_single(void *fixture) _gen_key(k, k + sizeof(k)); v.n = 1234; T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + T_ASSERT(radix_tree_is_well_formed(rt)); T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 2), 1); + T_ASSERT(radix_tree_is_well_formed(rt)); } static void test_size(void *fixture) @@ -318,6 +384,7 @@ static void test_size(void *fixture) } T_ASSERT_EQUAL(radix_tree_size(rt), 10000 - dup_count); + T_ASSERT(radix_tree_is_well_formed(rt)); } struct visitor { @@ -348,6 +415,7 @@ static void test_iterate_all(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); vt.count = 0; vt.it.visit = _visit; radix_tree_iterate(rt, NULL, NULL, &vt.it); @@ -371,6 +439,7 @@ static void test_iterate_subset(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); vt.count = 0; vt.it.visit = _visit; k[0] = 21; @@ -390,6 +459,7 @@ static void test_iterate_single(void *fixture) v.n = 1234; T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + T_ASSERT(radix_tree_is_well_formed(rt)); vt.count = 0; vt.it.visit = _visit; radix_tree_iterate(rt, k, k + 3, &vt.it); @@ -411,6 +481,7 @@ static void test_iterate_vary_middle(void *fixture) T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); } + T_ASSERT(radix_tree_is_well_formed(rt)); vt.it.visit = _visit; for (i = 0; i < 16; i++) { vt.count = 0; @@ -422,6 +493,77 @@ static void test_iterate_vary_middle(void *fixture) //---------------------------------------------------------------- +#define DTR_COUNT 100 + +struct counter { + unsigned c; + uint8_t present[DTR_COUNT]; +}; + +static void _counting_dtr(void *context, union radix_value v) +{ + struct counter *c = context; + c->c++; + T_ASSERT(v.n < DTR_COUNT); + c->present[v.n] = 0; +} + +static void test_remove_calls_dtr(void *fixture) +{ + struct counter c; + struct radix_tree *rt = radix_tree_create(_counting_dtr, &c); + T_ASSERT(rt); + + // Bug hunting, so I need the keys to be deterministic + srand(0); + + c.c = 0; + memset(c.present, 1, sizeof(c.present)); + + { + unsigned i; + uint8_t keys[DTR_COUNT * 3]; + union radix_value v; + + // generate and insert a lot of keys + for (i = 0; i < DTR_COUNT; i++) { + bool found = false; + do { + v.n = i; + uint8_t *k = keys + (i * 3); + _gen_key(k, k + 3); + if (!radix_tree_lookup(rt, k, k + 3, &v)) { + T_ASSERT(radix_tree_insert(rt, k, k + 3, v)); + found = true; + } + + } while (!found); + } + + T_ASSERT(radix_tree_is_well_formed(rt)); + + // double check + for (i = 0; i < DTR_COUNT; i++) { + uint8_t *k = keys + (i * 3); + T_ASSERT(radix_tree_lookup(rt, k, k + 3, &v)); + } + + for (i = 0; i < DTR_COUNT; i++) { + uint8_t *k = keys + (i * 3); + // FIXME: check the values get passed to the dtr + T_ASSERT(radix_tree_remove(rt, k, k + 3)); + } + + T_ASSERT(c.c == DTR_COUNT); + for (i = 0; i < DTR_COUNT; i++) + T_ASSERT(!c.present[i]); + } + + radix_tree_destroy(rt); +} + +//---------------------------------------------------------------- + #define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn) void radix_tree_tests(struct dm_list *all_tests) @@ -442,6 +584,7 @@ void radix_tree_tests(struct dm_list *all_tests) T("sparse-keys", "see what the memory usage is for sparsely distributed keys", test_sparse_keys); T("remove-one", "remove one entry", test_remove_one); T("remove-one-byte-keys", "remove many one byte keys", test_remove_one_byte_keys); + T("remove-one-byte-keys-reversed", "remove many one byte keys reversed", test_remove_one_byte_keys_reversed); 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); @@ -451,6 +594,7 @@ void radix_tree_tests(struct dm_list *all_tests) 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); + T("remove-calls-dtr", "remove should call the dtr for the value", test_remove_calls_dtr); dm_list_add(all_tests, &ts->list); }

1 0

master - radix-tree: More debugging of remove
by Joe Thornber 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=40c1f7889fd88ce4a2f2b… Commit: 40c1f7889fd88ce4a2f2b42c594db3deb8f84593 Parent: c8cfbfa605ce6577c390cf940d51d872b3556c64 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Wed Jun 20 10:04:59 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jun 21 09:49:43 2018 +0100 radix-tree: More debugging of remove There's now a pretty printer called radix_tree_dump() n4, n16, and n48 weren't UNSETting the last entry after sliding values down. --- base/data-struct/radix-tree.c | 157 ++++++++++++++++++++++++++++++++++++----- base/data-struct/radix-tree.h | 2 + test/unit/radix_tree_t.c | 32 ++++++++ 3 files changed, 174 insertions(+), 17 deletions(-) diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index 24455e1..202d463 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -251,7 +251,11 @@ static bool _insert_prefix_chain(struct radix_tree *rt, struct value *v, uint8_t { struct prefix_chain *pc = v->value.ptr; - if (*kb == pc->prefix[0]) { + if (!pc->len) { + v->type = VALUE; + v->value = rv; + + } else if (*kb == pc->prefix[0]) { // There's a common prefix let's split the chain into two and // recurse. struct prefix_chain *pc2; @@ -282,25 +286,23 @@ static bool _insert_prefix_chain(struct radix_tree *rt, struct value *v, uint8_t if (!n4) return false; - n4->keys[0] = *kb; - if (!_insert(rt, n4->values, kb + 1, ke, rv)) { + n4->keys[0] = pc->prefix[0]; + if (pc->len == 1) { + n4->values[0] = pc->child; + free(pc); + } else { + memmove(pc->prefix, pc->prefix + 1, pc->len - 1); + pc->len--; + n4->values[0] = *v; + } + + n4->keys[1] = *kb; + if (!_insert(rt, n4->values + 1, kb + 1, ke, rv)) { free(n4); return false; } - if (pc->len) { - n4->keys[1] = pc->prefix[0]; - if (pc->len == 1) { - n4->values[1] = pc->child; - free(pc); - } else { - memmove(pc->prefix, pc->prefix + 1, pc->len - 1); - pc->len--; - n4->values[1] = *v; - } - n4->nr_entries = 2; - } else - n4->nr_entries = 1; + n4->nr_entries = 2; v->type = NODE4; v->value.ptr = n4; @@ -330,7 +332,6 @@ static bool _insert_node4(struct radix_tree *rt, struct value *v, uint8_t *kb, u v->type = NODE16; v->value.ptr = n16; } else { - n4 = v->value.ptr; if (!_insert(rt, n4->values + n4->nr_entries, kb + 1, ke, rv)) return false; @@ -699,6 +700,7 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint } n4->nr_entries--; + n4->values[n4->nr_entries].type = UNSET; if (!n4->nr_entries) { free(n4); root->type = UNSET; @@ -721,6 +723,7 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint } n16->nr_entries--; + n16->values[n16->nr_entries].type = UNSET; if (n16->nr_entries <= 4) { _degrade_to_n4(n16, root); } @@ -742,6 +745,7 @@ static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint n48->keys[j]--; _erase_elt(n48->values, sizeof(*n48->values), n48->nr_entries, i); n48->nr_entries--; + n48->values[n48->nr_entries].type = UNSET; if (n48->nr_entries <= 16) _degrade_to_n16(n48, root); } @@ -1024,6 +1028,8 @@ void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, // Checks: // 1) The number of entries matches rt->nr_entries // 2) The number of entries is correct in each node +// 3) prefix chain len > 0 +// 4) all unused values are UNSET static bool _check_nodes(struct value *v, unsigned *count) { @@ -1057,6 +1063,13 @@ static bool _check_nodes(struct value *v, unsigned *count) for (i = 0; i < n4->nr_entries; i++) if (!_check_nodes(n4->values + i, count)) return false; + + for (i = n4->nr_entries; i < 4; i++) + if (n4->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET\n"); + return false; + } + return true; case NODE16: @@ -1064,6 +1077,13 @@ static bool _check_nodes(struct value *v, unsigned *count) for (i = 0; i < n16->nr_entries; i++) if (!_check_nodes(n16->values + i, count)) return false; + + for (i = n16->nr_entries; i < 16; i++) + if (n16->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET\n"); + return false; + } + return true; case NODE48: @@ -1083,6 +1103,12 @@ static bool _check_nodes(struct value *v, unsigned *count) return false; } + for (i = n48->nr_entries; i < 48; i++) + if (n48->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET\n"); + return false; + } + return true; case NODE256: @@ -1134,3 +1160,100 @@ bool radix_tree_is_well_formed(struct radix_tree *rt) } //---------------------------------------------------------------- + +static void _dump(FILE *out, struct value v, unsigned indent) +{ + unsigned i; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (v.type == UNSET) + return; + + for (i = 0; i < 2 * indent; i++) + fprintf(out, " "); + + switch (v.type) { + case UNSET: + // can't happen + break; + + case VALUE: + fprintf(out, "<val: %llu>\n", (unsigned long long) v.value.n); + break; + + case VALUE_CHAIN: + vc = v.value.ptr; + fprintf(out, "<val_chain: %llu>\n", (unsigned long long) vc->value.n); + _dump(out, vc->child, indent + 1); + break; + + case PREFIX_CHAIN: + pc = v.value.ptr; + fprintf(out, "<prefix: "); + for (i = 0; i < pc->len; i++) + fprintf(out, "%x.", (unsigned) *(pc->prefix + i)); + fprintf(out, ">\n"); + _dump(out, pc->child, indent + 1); + break; + + case NODE4: + n4 = v.value.ptr; + fprintf(out, "<n4: "); + for (i = 0; i < n4->nr_entries; i++) + fprintf(out, "%x ", (unsigned) n4->keys[i]); + fprintf(out, ">\n"); + + for (i = 0; i < n4->nr_entries; i++) + _dump(out, n4->values[i], indent + 1); + break; + + case NODE16: + n16 = v.value.ptr; + fprintf(out, "<n16: "); + for (i = 0; i < n16->nr_entries; i++) + fprintf(out, "%x ", (unsigned) n16->keys[i]); + fprintf(out, ">\n"); + + for (i = 0; i < n16->nr_entries; i++) + _dump(out, n16->values[i], indent + 1); + break; + + case NODE48: + n48 = v.value.ptr; + fprintf(out, "<n48: "); + for (i = 0; i < 256; i++) + if (n48->keys[i] < 48) + fprintf(out, "%x ", i); + fprintf(out, ">\n"); + + for (i = 0; i < 256; i++) + if (n48->keys[i] < 48) + _dump(out, n48->values[i], indent + 1); + break; + + case NODE256: + n256 = v.value.ptr; + fprintf(out, "<n256: "); + for (i = 0; i < 256; i++) + if (n256->values[i].type != UNSET) + fprintf(out, "%x ", i); + fprintf(out, ">\n"); + + for (i = 0; i < 256; i++) + if (n256->values[i].type != UNSET) + _dump(out, n256->values[i], indent + 1); + break; + } +} + +void radix_tree_dump(struct radix_tree *rt, FILE *out) +{ + _dump(out, rt->root, 0); +} + +//---------------------------------------------------------------- diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h index 2deaf9a..5d4d04c 100644 --- a/base/data-struct/radix-tree.h +++ b/base/data-struct/radix-tree.h @@ -15,6 +15,7 @@ #include <stdbool.h> #include <stdint.h> +#include <stdio.h> //---------------------------------------------------------------- @@ -56,6 +57,7 @@ void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, // Checks that some constraints on the shape of the tree are // being held. For debug only. bool radix_tree_is_well_formed(struct radix_tree *rt); +void radix_tree_dump(struct radix_tree *rt, FILE *out); //---------------------------------------------------------------- diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c index 4ee22c1..2fba15f 100644 --- a/test/unit/radix_tree_t.c +++ b/test/unit/radix_tree_t.c @@ -605,6 +605,37 @@ static void test_destroy_calls_dtr(void *fixture) //---------------------------------------------------------------- +static void test_bcache_scenario(void *fixture) +{ + struct radix_tree *rt = fixture; + + unsigned i; + uint8_t k[6]; + union radix_value v; + + memset(k, 0, sizeof(k)); + + for (i = 0; i < 3; i++) { + // it has to be the 4th byte that varies to + // trigger the bug. + k[4] = i; + v.n = i; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + } + T_ASSERT(radix_tree_is_well_formed(rt)); + + k[4] = 0; + T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k))); + T_ASSERT(radix_tree_is_well_formed(rt)); + + k[4] = i; + v.n = i; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + T_ASSERT(radix_tree_is_well_formed(rt)); +} + +//---------------------------------------------------------------- + #define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn) void radix_tree_tests(struct dm_list *all_tests) @@ -637,6 +668,7 @@ void radix_tree_tests(struct dm_list *all_tests) T("iterate-vary-middle", "iterate keys that vary in the middle", test_iterate_vary_middle); T("remove-calls-dtr", "remove should call the dtr for the value", test_remove_calls_dtr); T("destroy-calls-dtr", "destroy should call the dtr for all values", test_destroy_calls_dtr); + T("bcache-scenario", "A specific series of keys from a bcache scenario", test_bcache_scenario); dm_list_add(all_tests, &ts->list); }

1 0

master - radix_tree: add new test case
by Joe Thornber 21 Jun '18

21 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c8cfbfa605ce6577c390c… Commit: c8cfbfa605ce6577c390cf940d51d872b3556c64 Parent: 20b9746c5d22de385e32f5be9a8f04754be2c706 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Jun 19 13:38:13 2018 +0100 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jun 21 09:49:25 2018 +0100 radix_tree: add new test case Check that value destructors are called by radix_tree_destroy() --- test/unit/radix_tree_t.c | 42 ++++++++++++++++++++++++++++++++++++++++++ 1 files changed, 42 insertions(+), 0 deletions(-) diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c index e2d11e8..4ee22c1 100644 --- a/test/unit/radix_tree_t.c +++ b/test/unit/radix_tree_t.c @@ -562,6 +562,47 @@ static void test_remove_calls_dtr(void *fixture) radix_tree_destroy(rt); } +static void test_destroy_calls_dtr(void *fixture) +{ + unsigned i; + struct counter c; + struct radix_tree *rt = radix_tree_create(_counting_dtr, &c); + T_ASSERT(rt); + + // Bug hunting, so I need the keys to be deterministic + srand(0); + + c.c = 0; + memset(c.present, 1, sizeof(c.present)); + + { + uint8_t keys[DTR_COUNT * 3]; + union radix_value v; + + // generate and insert a lot of keys + for (i = 0; i < DTR_COUNT; i++) { + bool found = false; + do { + v.n = i; + uint8_t *k = keys + (i * 3); + _gen_key(k, k + 3); + if (!radix_tree_lookup(rt, k, k + 3, &v)) { + T_ASSERT(radix_tree_insert(rt, k, k + 3, v)); + found = true; + } + + } while (!found); + } + + T_ASSERT(radix_tree_is_well_formed(rt)); + } + + radix_tree_destroy(rt); + T_ASSERT(c.c == DTR_COUNT); + for (i = 0; i < DTR_COUNT; i++) + T_ASSERT(!c.present[i]); +} + //---------------------------------------------------------------- #define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn) @@ -595,6 +636,7 @@ void radix_tree_tests(struct dm_list *all_tests) 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); T("remove-calls-dtr", "remove should call the dtr for the value", test_remove_calls_dtr); + T("destroy-calls-dtr", "destroy should call the dtr for all values", test_destroy_calls_dtr); dm_list_add(all_tests, &ts->list); }

1 0

master - scan: work around udev problems by avoiding open RDWR
by David Teigland 20 Jun '18

20 Jun '18

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=42f7caf1c267a5b75ee38… Commit: 42f7caf1c267a5b75ee38ea77a7e2fd7c582e704 Parent: f85a010a6bc9dc0414ccdf9c6b195c78231f1914 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Wed Jun 20 11:32:45 2018 -0500 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Wed Jun 20 14:08:12 2018 -0500 scan: work around udev problems by avoiding open RDWR udev creates a train wreck of events if we open devices with RDWR. Until we can fix/disable/scrap udev, work around this by opening RDONLY and then closing/reopening RDWR when a write is needed. This invalidates the bcache blocks for the device before writing so it can trigger unnecessary rereading. --- lib/device/device.h | 1 + lib/label/label.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 55 insertions(+), 2 deletions(-) diff --git a/lib/device/device.h b/lib/device/device.h index 00e398a..e879dbb 100644 --- a/lib/device/device.h +++ b/lib/device/device.h @@ -35,6 +35,7 @@ #define DEV_BCACHE_EXCL 0x00001000 /* bcache_fd should be open EXCL */ #define DEV_FILTER_AFTER_SCAN 0x00002000 /* apply filter after bcache has data */ #define DEV_FILTER_OUT_SCAN 0x00004000 /* filtered out during label scan */ +#define DEV_BCACHE_WRITE 0x00008000 /* bcache_fd is open with RDWR */ /* * Support for external device info. diff --git a/lib/label/label.c b/lib/label/label.c index 065c01f..d2c8685 100644 --- a/lib/label/label.c +++ b/lib/label/label.c @@ -467,12 +467,24 @@ static int _scan_dev_open(struct device *dev) name_sl = dm_list_item(name_list, struct dm_str_list); name = name_sl->str; - flags |= O_RDWR; flags |= O_DIRECT; flags |= O_NOATIME; - if (dev->flags & DEV_BCACHE_EXCL) + /* + * FIXME: udev is a train wreck when we open RDWR and close, so we + * need to only use RDWR when we actually need to write, and use + * RDONLY otherwise. Fix, disable or scrap udev nonsense so we can + * just open with RDWR by default. + */ + + if (dev->flags & DEV_BCACHE_EXCL) { flags |= O_EXCL; + flags |= O_RDWR; + } else if (dev->flags & DEV_BCACHE_WRITE) { + flags |= O_RDWR; + } else { + flags |= O_RDONLY; + } retry_open: @@ -1124,7 +1136,14 @@ int label_scan_open(struct device *dev) int label_scan_open_excl(struct device *dev) { + if (_in_bcache(dev) && !(dev->flags & DEV_BCACHE_EXCL)) { + /* FIXME: avoid tossing out bcache blocks just to replace fd. */ + log_debug("Close and reopen excl %s", dev_name(dev)); + bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _scan_dev_close(dev); + } dev->flags |= DEV_BCACHE_EXCL; + dev->flags |= DEV_BCACHE_WRITE; return label_scan_open(dev); } @@ -1166,8 +1185,19 @@ bool dev_write_bytes(struct device *dev, uint64_t start, size_t len, void *data) return false; } + if (!(dev->flags & DEV_BCACHE_WRITE)) { + /* FIXME: avoid tossing out bcache blocks just to replace fd. */ + log_debug("Close and reopen to write %s", dev_name(dev)); + bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _scan_dev_close(dev); + + dev->flags |= DEV_BCACHE_WRITE; + label_scan_open(dev); + } + if (dev->bcache_fd <= 0) { /* This is not often needed, perhaps only with lvmetad. */ + dev->flags |= DEV_BCACHE_WRITE; if (!label_scan_open(dev)) { log_error("Error opening device %s for writing at %llu length %u.", dev_name(dev), (unsigned long long)start, (uint32_t)len); @@ -1201,8 +1231,19 @@ bool dev_write_zeros(struct device *dev, uint64_t start, size_t len) return false; } + if (!(dev->flags & DEV_BCACHE_WRITE)) { + /* FIXME: avoid tossing out bcache blocks just to replace fd. */ + log_debug("Close and reopen to write %s", dev_name(dev)); + bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _scan_dev_close(dev); + + dev->flags |= DEV_BCACHE_WRITE; + label_scan_open(dev); + } + if (dev->bcache_fd <= 0) { /* This is not often needed, perhaps only with lvmetad. */ + dev->flags |= DEV_BCACHE_WRITE; if (!label_scan_open(dev)) { log_error("Error opening device %s for writing at %llu length %u.", dev_name(dev), (unsigned long long)start, (uint32_t)len); @@ -1236,8 +1277,19 @@ bool dev_set_bytes(struct device *dev, uint64_t start, size_t len, uint8_t val) return false; } + if (!(dev->flags & DEV_BCACHE_WRITE)) { + /* FIXME: avoid tossing out bcache blocks just to replace fd. */ + log_debug("Close and reopen to write %s", dev_name(dev)); + bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _scan_dev_close(dev); + + dev->flags |= DEV_BCACHE_WRITE; + label_scan_open(dev); + } + if (dev->bcache_fd <= 0) { /* This is not often needed, perhaps only with lvmetad. */ + dev->flags |= DEV_BCACHE_WRITE; if (!label_scan_open(dev)) { log_error("Error opening device %s for writing at %llu length %u.", dev_name(dev), (unsigned long long)start, (uint32_t)len);

1 0

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

lvm2-commits June 2018