master - radix-tree: squash a pointer arithmetic warning
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=254e5c5d119447bcb8b...
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)
5 years, 10 months
master - radix-tree: fix bug when erasing elts in remove_prefix
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=72e2e92f4c23b75efdf...
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;
}
5 years, 10 months
master - filter: use pointers to real addresses
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=dd7ebec12028a65081f...
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)
{
5 years, 10 months
master - Remove code for using files as devices
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=15826214f94da5a447f...
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);
5 years, 10 months
master - lvmlockd: fix another missing lock_type null check
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=e166d2b14ca22ead559...
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)) {
5 years, 10 months
master - radix-tree: FIx various bugs to do with removal
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=20b9746c5d22de385e3...
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);
}
5 years, 10 months
master - radix-tree: More debugging of remove
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=40c1f7889fd88ce4a2f...
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);
}
5 years, 10 months
master - radix_tree: add new test case
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c8cfbfa605ce6577c39...
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);
}
5 years, 10 months
master - scan: work around udev problems by avoiding open RDWR
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=42f7caf1c267a5b75ee...
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);
5 years, 10 months