master - devs: recognize md devices in subsystem check
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=b5d99146282d2747b96...
Commit: b5d99146282d2747b96d37efb5d2a7dc02fa6327
Parent: ccab54677c9f92cf1bd11895251799c043a57602
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Fri May 11 14:00:19 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Fri May 11 14:00:19 2018 -0500
devs: recognize md devices in subsystem check
If md components appear as duplicate PVs, let the
existing subsystem check recognize the md device.
---
lib/device/dev-type.c | 3 +++
1 files changed, 3 insertions(+), 0 deletions(-)
diff --git a/lib/device/dev-type.c b/lib/device/dev-type.c
index 8d4a403..af4b407 100644
--- a/lib/device/dev-type.c
+++ b/lib/device/dev-type.c
@@ -215,6 +215,9 @@ int dev_subsystem_part_major(struct dev_types *dt, struct device *dev)
if (MAJOR(dev->dev) == dt->device_mapper_major)
return 1;
+ if (MAJOR(dev->dev) == dt->md_major)
+ return 1;
+
if (MAJOR(dev->dev) == dt->drbd_major)
return 1;
6 years
master - dev_cache: fix close in dev_get_block_size
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=ccab54677c9f92cf1bd...
Commit: ccab54677c9f92cf1bd11895251799c043a57602
Parent: bbb8040456a07a0c9076d45a8eee5e5f7fcde0ec
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Fri May 11 13:53:19 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Fri May 11 13:53:19 2018 -0500
dev_cache: fix close in dev_get_block_size
---
lib/device/dev-io.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/lib/device/dev-io.c b/lib/device/dev-io.c
index 903c582..8028306 100644
--- a/lib/device/dev-io.c
+++ b/lib/device/dev-io.c
@@ -198,7 +198,7 @@ int dev_get_block_size(struct device *dev, unsigned int *physical_block_size, un
*physical_block_size = (unsigned int) dev->phys_block_size;
*block_size = (unsigned int) dev->block_size;
out:
- if (needs_open && !dev_close(dev))
+ if (needs_open && !dev_close_immediate(dev))
stack;
return r;
6 years
master - dev_cache: drop open_list
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=bbb8040456a07a0c907...
Commit: bbb8040456a07a0c9076d45a8eee5e5f7fcde0ec
Parent: 43620138726da124f5eb58c9347cba8b582271ed
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Fri May 11 11:59:44 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Fri May 11 12:47:56 2018 -0500
dev_cache: drop open_list
devices are now held open only in bcache,
so drop the dev_cache list of open devices
which is unused.
---
lib/cache/lvmcache.c | 1 -
lib/device/dev-cache.c | 1 -
lib/device/dev-io.c | 16 ----------------
lib/device/device.h | 2 --
lib/label/label.c | 4 ----
lib/metadata/metadata.c | 2 --
lib/misc/lvm-exec.c | 1 -
tools/polldaemon.c | 8 --------
tools/toollib.c | 1 -
9 files changed, 0 insertions(+), 36 deletions(-)
diff --git a/lib/cache/lvmcache.c b/lib/cache/lvmcache.c
index 290d733..3f9e6fd 100644
--- a/lib/cache/lvmcache.c
+++ b/lib/cache/lvmcache.c
@@ -643,7 +643,6 @@ void lvmcache_unlock_vgname(const char *vgname)
/* FIXME Do this per-VG */
if (strcmp(vgname, VG_GLOBAL) && !--_vgs_locked) {
- dev_close_all();
dev_size_seqno_inc(); /* invalidate all cached dev sizes */
}
}
diff --git a/lib/device/dev-cache.c b/lib/device/dev-cache.c
index 15d4cdf..975fc12 100644
--- a/lib/device/dev-cache.c
+++ b/lib/device/dev-cache.c
@@ -73,7 +73,6 @@ static void _dev_init(struct device *dev, int max_error_count)
dev->ext.src = DEV_EXT_NONE;
dm_list_init(&dev->aliases);
- dm_list_init(&dev->open_list);
}
void dev_destroy_file(struct device *dev)
diff --git a/lib/device/dev-io.c b/lib/device/dev-io.c
index cce5a94..903c582 100644
--- a/lib/device/dev-io.c
+++ b/lib/device/dev-io.c
@@ -53,7 +53,6 @@
# endif
#endif
-static DM_LIST_INIT(_open_devices);
static unsigned _dev_size_seqno = 1;
static const char *_reasons[] = {
@@ -597,8 +596,6 @@ int dev_open_flags(struct device *dev, int flags, int direct, int quiet)
if ((flags & O_CREAT) && !(flags & O_TRUNC))
dev->end = lseek(dev->fd, (off_t) 0, SEEK_END);
- dm_list_add(&_open_devices, &dev->open_list);
-
log_debug_devs("Opened %s %s%s%s", dev_name(dev),
dev->flags & DEV_OPENED_RW ? "RW" : "RO",
dev->flags & DEV_OPENED_EXCL ? " O_EXCL" : "",
@@ -650,7 +647,6 @@ static void _close(struct device *dev)
dev->fd = -1;
dev->phys_block_size = -1;
dev->block_size = -1;
- dm_list_del(&dev->open_list);
log_debug_devs("Closed %s", dev_name(dev));
@@ -696,18 +692,6 @@ int dev_close_immediate(struct device *dev)
return _dev_close(dev, 1);
}
-void dev_close_all(void)
-{
- struct dm_list *doh, *doht;
- struct device *dev;
-
- dm_list_iterate_safe(doh, doht, &_open_devices) {
- dev = dm_list_struct_base(doh, struct device, open_list);
- if (dev->open_count < 1)
- _close(dev);
- }
-}
-
static inline int _dev_is_valid(struct device *dev)
{
return (dev->max_error_count == NO_DEV_ERROR_COUNT_LIMIT ||
diff --git a/lib/device/device.h b/lib/device/device.h
index fd8cbb7..42659cd 100644
--- a/lib/device/device.h
+++ b/lib/device/device.h
@@ -74,7 +74,6 @@ struct device {
unsigned size_seqno;
uint64_t size;
uint64_t end;
- struct dm_list open_list;
struct dev_ext ext;
const char *vgid; /* if device is an LV */
@@ -144,7 +143,6 @@ int dev_open_readonly_buffered(struct device *dev);
int dev_open_readonly_quiet(struct device *dev);
int dev_close(struct device *dev);
int dev_close_immediate(struct device *dev);
-void dev_close_all(void);
int dev_test_excl(struct device *dev);
int dev_fd(struct device *dev);
diff --git a/lib/label/label.c b/lib/label/label.c
index 45acd73..ab040e1 100644
--- a/lib/label/label.c
+++ b/lib/label/label.c
@@ -975,8 +975,6 @@ int label_scan_open(struct device *dev)
bool dev_read_bytes(struct device *dev, uint64_t start, size_t len, void *data)
{
- int ret;
-
if (!scan_bcache) {
/* Should not happen */
log_error("dev_read bcache not set up %s", dev_name(dev));
@@ -1003,8 +1001,6 @@ bool dev_read_bytes(struct device *dev, uint64_t start, size_t len, void *data)
bool dev_write_bytes(struct device *dev, uint64_t start, size_t len, void *data)
{
- int ret;
-
if (test_mode())
return true;
diff --git a/lib/metadata/metadata.c b/lib/metadata/metadata.c
index b8f1b97..bfdc4cf 100644
--- a/lib/metadata/metadata.c
+++ b/lib/metadata/metadata.c
@@ -5192,8 +5192,6 @@ static struct volume_group *_recover_vg(struct cmd_context *cmd,
unlock_vg(cmd, NULL, vg_name);
- dev_close_all();
-
if (!lock_vol(cmd, vg_name, LCK_VG_WRITE, NULL))
return_NULL;
diff --git a/lib/misc/lvm-exec.c b/lib/misc/lvm-exec.c
index 190d426..c3858c4 100644
--- a/lib/misc/lvm-exec.c
+++ b/lib/misc/lvm-exec.c
@@ -78,7 +78,6 @@ int exec_cmd(struct cmd_context *cmd, const char *const argv[],
if (!pid) {
/* Child */
reset_locking();
- dev_close_all();
/* FIXME Fix effect of reset_locking on cache then include this */
/* destroy_toolcontext(cmd); */
/* FIXME Use execve directly */
diff --git a/tools/polldaemon.c b/tools/polldaemon.c
index 5b5f57f..020be21 100644
--- a/tools/polldaemon.c
+++ b/tools/polldaemon.c
@@ -134,7 +134,6 @@ static void _sleep_and_rescan_devices(struct cmd_context *cmd, struct daemon_par
*/
lvmcache_destroy(cmd, 1, 0);
label_scan_destroy(cmd);
- dev_close_all();
_nanosleep(parms->interval, 1);
lvmcache_label_scan(cmd);
}
@@ -530,9 +529,6 @@ static void _lvmpolld_poll_for_all_vgs(struct cmd_context *cmd,
_report_progress(cmd, idl->id, lpdp.parms);
}
- if (lpdp.parms->interval)
- dev_close_all();
-
_nanosleep(lpdp.parms->interval, 0);
}
@@ -559,9 +555,6 @@ static int _lvmpoll_daemon(struct cmd_context *cmd, struct poll_operation_id *id
(!parms->aborting && !(r = _report_progress(cmd, id, parms))))
break;
- if (parms->interval)
- dev_close_all();
-
_nanosleep(parms->interval, 0);
}
}
@@ -620,7 +613,6 @@ static int _poll_daemon(struct cmd_context *cmd, struct poll_operation_id *id,
/* clear lvmcache/bcache/fds from the parent */
lvmcache_destroy(cmd, 1, 0);
label_scan_destroy(cmd);
- dev_close_all();
if (id) {
if (!wait_for_single_lv(cmd, id, parms)) {
diff --git a/tools/toollib.c b/tools/toollib.c
index e633cdd..5e5cc51 100644
--- a/tools/toollib.c
+++ b/tools/toollib.c
@@ -115,7 +115,6 @@ int become_daemon(struct cmd_context *cmd, int skip_lvm)
/* FIXME Clean up properly here */
_exit(ECMD_FAILED);
}
- dev_close_all();
return 1;
}
6 years
master - bcache: disable fallback to old io
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=43620138726da124f5e...
Commit: 43620138726da124f5eb58c9347cba8b582271ed
Parent: 228ed56455b9510ed7943997987ae28459efc1b4
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Fri May 11 09:50:25 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Fri May 11 11:35:56 2018 -0500
bcache: disable fallback to old io
All io has been converted to bcache.
---
lib/label/label.c | 28 ++++++++--------------------
1 files changed, 8 insertions(+), 20 deletions(-)
diff --git a/lib/label/label.c b/lib/label/label.c
index f5f30c6..45acd73 100644
--- a/lib/label/label.c
+++ b/lib/label/label.c
@@ -978,15 +978,9 @@ bool dev_read_bytes(struct device *dev, uint64_t start, size_t len, void *data)
int ret;
if (!scan_bcache) {
- if (!dev_open_readonly(dev))
- return false;
-
- ret = dev_read(dev, start, len, 0, data);
-
- if (!dev_close(dev))
- stack;
-
- return ret ? true : false;
+ /* Should not happen */
+ log_error("dev_read bcache not set up %s", dev_name(dev));
+ return false;
}
if (dev->bcache_fd <= 0) {
@@ -1015,15 +1009,9 @@ bool dev_write_bytes(struct device *dev, uint64_t start, size_t len, void *data)
return true;
if (!scan_bcache) {
- if (!dev_open(dev))
- return false;
-
- ret = dev_write(dev, start, len, 0, data);
-
- if (!dev_close(dev))
- stack;
-
- return ret ? true : false;
+ /* Should not happen */
+ log_error("dev_write bcache not set up %s", dev_name(dev));
+ return false;
}
if (dev->bcache_fd <= 0) {
@@ -1056,7 +1044,7 @@ bool dev_write_zeros(struct device *dev, uint64_t start, size_t len)
return true;
if (!scan_bcache) {
- log_error("dev_write_zeros %s bcache not set up", dev_name(dev));
+ log_error("dev_write_zeros bcache not set up %s", dev_name(dev));
return false;
}
@@ -1090,7 +1078,7 @@ bool dev_set_bytes(struct device *dev, uint64_t start, size_t len, uint8_t val)
return true;
if (!scan_bcache) {
- log_error("dev_set_bytes %s bcache not set up", dev_name(dev));
+ log_error("dev_set_bytes bcache not set up %s", dev_name(dev));
return false;
}
6 years
master - pvck: allow checking at user specified offsets
by David Teigland
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=228ed56455b9510ed79...
Commit: 228ed56455b9510ed7943997987ae28459efc1b4
Parent: 413488edc6dd077e79517e44a8d3b9a51c5138e5
Author: David Teigland <teigland(a)redhat.com>
AuthorDate: Thu May 10 16:27:34 2018 -0500
Committer: David Teigland <teigland(a)redhat.com>
CommitterDate: Fri May 11 11:23:51 2018 -0500
pvck: allow checking at user specified offsets
with the --labelsector option. We probably don't
need all this code to support any value for this
option; it's unclear how, when, why it would be
used.
---
lib/label/label.c | 105 ++++++++++++++++++++++++++++++++++++++++-------------
lib/label/label.h | 2 +-
tools/pvck.c | 28 ++++++++++-----
3 files changed, 99 insertions(+), 36 deletions(-)
diff --git a/lib/label/label.c b/lib/label/label.c
index 071c2e7..f5f30c6 100644
--- a/lib/label/label.c
+++ b/lib/label/label.c
@@ -251,9 +251,11 @@ static bool _in_bcache(struct device *dev)
static struct labeller *_find_lvm_header(struct device *dev,
char *scan_buf,
+ uint32_t scan_buf_sectors,
char *label_buf,
uint64_t *label_sector,
- uint64_t scan_sector)
+ uint64_t block_sector,
+ uint64_t start_sector)
{
struct labeller_i *li;
struct labeller *labeller_ret = NULL;
@@ -266,25 +268,34 @@ static struct labeller *_find_lvm_header(struct device *dev,
* and copy it into label_buf.
*/
- for (sector = 0; sector < LABEL_SCAN_SECTORS;
+ for (sector = start_sector; sector < start_sector + LABEL_SCAN_SECTORS;
sector += LABEL_SIZE >> SECTOR_SHIFT) {
+
+ /*
+ * The scan_buf passed in is a bcache block, which is
+ * BCACHE_BLOCK_SIZE_IN_SECTORS large. So if start_sector is
+ * one of the last couple sectors in that buffer, we need to
+ * break early.
+ */
+ if (sector >= scan_buf_sectors)
+ break;
+
lh = (struct label_header *) (scan_buf + (sector << SECTOR_SHIFT));
if (!strncmp((char *)lh->id, LABEL_ID, sizeof(lh->id))) {
if (found) {
log_error("Ignoring additional label on %s at sector %llu",
- dev_name(dev), (unsigned long long)(sector + scan_sector));
+ dev_name(dev), (unsigned long long)(block_sector + sector));
}
- if (xlate64(lh->sector_xl) != sector + scan_sector) {
- log_very_verbose("%s: Label for sector %llu found at sector %llu - ignoring.",
- dev_name(dev),
- (unsigned long long)xlate64(lh->sector_xl),
- (unsigned long long)(sector + scan_sector));
+ if (xlate64(lh->sector_xl) != sector) {
+ log_warn("%s: Label for sector %llu found at sector %llu - ignoring.",
+ dev_name(dev),
+ (unsigned long long)xlate64(lh->sector_xl),
+ (unsigned long long)(block_sector + sector));
continue;
}
- if (calc_crc(INITIAL_CRC, (uint8_t *)&lh->offset_xl, LABEL_SIZE -
- ((uint8_t *) &lh->offset_xl - (uint8_t *) lh)) !=
- xlate32(lh->crc_xl)) {
+ if (calc_crc(INITIAL_CRC, (uint8_t *)&lh->offset_xl,
+ LABEL_SIZE - ((uint8_t *) &lh->offset_xl - (uint8_t *) lh)) != xlate32(lh->crc_xl)) {
log_very_verbose("Label checksum incorrect on %s - ignoring", dev_name(dev));
continue;
}
@@ -293,14 +304,14 @@ static struct labeller *_find_lvm_header(struct device *dev,
}
dm_list_iterate_items(li, &_labellers) {
- if (li->l->ops->can_handle(li->l, (char *) lh, sector + scan_sector)) {
+ if (li->l->ops->can_handle(li->l, (char *) lh, block_sector + sector)) {
log_very_verbose("%s: %s label detected at sector %llu",
dev_name(dev), li->name,
- (unsigned long long)(sector + scan_sector));
+ (unsigned long long)(block_sector + sector));
if (found) {
log_error("Ignoring additional label on %s at sector %llu",
dev_name(dev),
- (unsigned long long)(sector + scan_sector));
+ (unsigned long long)(block_sector + sector));
continue;
}
@@ -309,7 +320,7 @@ static struct labeller *_find_lvm_header(struct device *dev,
memcpy(label_buf, lh, LABEL_SIZE);
if (label_sector)
- *label_sector = sector + scan_sector;
+ *label_sector = block_sector + sector;
break;
}
}
@@ -329,7 +340,9 @@ static struct labeller *_find_lvm_header(struct device *dev,
* are performed in the processing functions to get that data.
*/
static int _process_block(struct cmd_context *cmd, struct dev_filter *f,
- struct device *dev, struct block *bb, int *is_lvm_device)
+ struct device *dev, struct block *bb,
+ uint64_t block_sector, uint64_t start_sector,
+ int *is_lvm_device)
{
char label_buf[LABEL_SIZE] __attribute__((aligned(8)));
struct label *label = NULL;
@@ -345,7 +358,7 @@ static int _process_block(struct cmd_context *cmd, struct dev_filter *f,
* data had been read (here). They set this flag to indicate that the
* filters should be retested now that data from the device is ready.
*/
- if (cmd && (dev->flags & DEV_FILTER_AFTER_SCAN)) {
+ if (f && (dev->flags & DEV_FILTER_AFTER_SCAN)) {
dev->flags &= ~DEV_FILTER_AFTER_SCAN;
log_debug_devs("Scan filtering %s", dev_name(dev));
@@ -374,7 +387,7 @@ static int _process_block(struct cmd_context *cmd, struct dev_filter *f,
* FIXME: we don't need to copy one sector from bb->data into label_buf,
* we can just point label_buf at one sector in ld->buf.
*/
- if (!(labeller = _find_lvm_header(dev, bb->data, label_buf, §or, 0))) {
+ if (!(labeller = _find_lvm_header(dev, bb->data, BCACHE_BLOCK_SIZE_IN_SECTORS, label_buf, §or, block_sector, start_sector))) {
/*
* Non-PVs exit here
@@ -567,7 +580,7 @@ static int _scan_list(struct cmd_context *cmd, struct dev_filter *f,
} else {
log_debug_devs("Processing data from device %s fd %d block %p", dev_name(devl->dev), devl->dev->bcache_fd, bb);
- ret = _process_block(cmd, f, devl->dev, bb, &is_lvm_device);
+ ret = _process_block(cmd, f, devl->dev, bb, 0, 0, &is_lvm_device);
if (!ret && is_lvm_device) {
log_debug_devs("Scan failed to process %s", dev_name(devl->dev));
@@ -875,18 +888,58 @@ int label_read(struct device *dev, struct label **labelp, uint64_t unused_sector
/*
* Read a label from a specfic, non-zero sector. This is used in only
- * one place: pvck -> pv_analyze.
+ * one place: pvck/pv_analyze.
*/
-int label_read_sector(struct device *dev, struct label **labelp, uint64_t scan_sector)
+int label_read_sector(struct device *dev, uint64_t read_sector)
{
- if (scan_sector) {
- /* TODO: not yet implemented */
- /* When is this done? When does it make sense? Is it actually possible? */
- return 0;
+ struct block *bb = NULL;
+ uint64_t block_num;
+ uint64_t block_sector;
+ uint64_t start_sector;
+ int is_lvm_device = 0;
+ int result;
+ int ret;
+
+ block_num = read_sector / BCACHE_BLOCK_SIZE_IN_SECTORS;
+ block_sector = block_num * BCACHE_BLOCK_SIZE_IN_SECTORS;
+ start_sector = read_sector % BCACHE_BLOCK_SIZE_IN_SECTORS;
+
+ label_scan_open(dev);
+
+ bcache_prefetch(scan_bcache, dev->bcache_fd, block_num);
+
+ if (!bcache_get(scan_bcache, dev->bcache_fd, block_num, 0, &bb)) {
+ log_error("Scan failed to read %s at %llu",
+ dev_name(dev), (unsigned long long)block_num);
+ ret = 0;
+ goto out;
+ }
+
+ /*
+ * TODO: check if scan_sector is larger than the bcache block size.
+ * If it is, we need to fetch a later block from bcache.
+ */
+
+ result = _process_block(NULL, NULL, dev, bb, block_sector, start_sector, &is_lvm_device);
+
+ if (!result && is_lvm_device) {
+ log_error("Scan failed to process %s", dev_name(dev));
+ ret = 0;
+ goto out;
}
- return label_read(dev, labelp, 0);
+ if (!result || !is_lvm_device) {
+ log_error("Could not find LVM label on %s", dev_name(dev));
+ ret = 0;
+ goto out;
+ }
+
+ ret = 1;
+out:
+ if (bb)
+ bcache_put(bb);
+ return ret;
}
/*
diff --git a/lib/label/label.h b/lib/label/label.h
index 3483321..508cb6f 100644
--- a/lib/label/label.h
+++ b/lib/label/label.h
@@ -110,7 +110,7 @@ void label_scan_invalidate_lv(struct cmd_context *cmd, struct logical_volume *lv
void label_scan_drop(struct cmd_context *cmd);
void label_scan_destroy(struct cmd_context *cmd);
int label_read(struct device *dev, struct label **labelp, uint64_t unused_sector);
-int label_read_sector(struct device *dev, struct label **labelp, uint64_t scan_sector);
+int label_read_sector(struct device *dev, uint64_t scan_sector);
void label_scan_confirm(struct device *dev);
int label_scan_setup_bcache(void);
int label_scan_open(struct device *dev);
diff --git a/tools/pvck.c b/tools/pvck.c
index 5d3c7d1..9030496 100644
--- a/tools/pvck.c
+++ b/tools/pvck.c
@@ -25,17 +25,8 @@ int pvck(struct cmd_context *cmd, int argc, char **argv)
int i;
int ret_max = ECMD_PROCESSED;
- /* FIXME: validate cmdline options */
- /* FIXME: what does the cmdline look like? */
-
labelsector = arg_uint64_value(cmd, labelsector_ARG, UINT64_C(0));
- if (labelsector) {
- /* FIXME: see label_read_sector */
- log_error("TODO: reading label from non-zero sector");
- return ECMD_FAILED;
- }
-
dm_list_init(&devs);
for (i = 0; i < argc; i++) {
@@ -61,6 +52,25 @@ int pvck(struct cmd_context *cmd, int argc, char **argv)
label_scan_devs(cmd, cmd->filter, &devs);
dm_list_iterate_items(devl, &devs) {
+
+ /*
+ * The scan above will populate lvmcache with any info from the
+ * standard locations at the start of the device. Now populate
+ * lvmcache with any info from non-standard offsets.
+ *
+ * FIXME: is it possible for a real lvm label sector to be
+ * anywhere other than the first four sectors of the disk?
+ * If not, drop the code in label_read_sector/find_lvm_header
+ * that supports searching at any sector.
+ */
+ if (labelsector) {
+ if (!label_read_sector(devl->dev, labelsector)) {
+ stack;
+ ret_max = ECMD_FAILED;
+ continue;
+ }
+ }
+
if (!pv_analyze(cmd, devl->dev, labelsector)) {
stack;
ret_max = ECMD_FAILED;
6 years
master - radix-tree: fix a function decl
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=413488edc6dd077e795...
Commit: 413488edc6dd077e79517e44a8d3b9a51c5138e5
Parent: 30a4c7988e790c16cea043b6b6743f0576c80c1e
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Fri May 11 11:40:47 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Fri May 11 11:40:47 2018 +0100
radix-tree: fix a function decl
---
test/unit/radix_tree_t.c | 2 +-
1 files changed, 1 insertions(+), 1 deletions(-)
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
index 6a7ecac..4455f2b 100644
--- a/test/unit/radix_tree_t.c
+++ b/test/unit/radix_tree_t.c
@@ -19,7 +19,7 @@
//----------------------------------------------------------------
-static void *rt_init()
+static void *rt_init(void)
{
struct radix_tree *rt = radix_tree_create();
T_ASSERT(rt);
6 years
master - radix-tree: remove some unneccessary includes
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=30a4c7988e790c16cea...
Commit: 30a4c7988e790c16cea043b6b6743f0576c80c1e
Parent: 0a31fb4aa323e0e8636d9c0b9332d14df86afda5
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Fri May 11 09:46:34 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Fri May 11 09:46:34 2018 +0100
radix-tree: remove some unneccessary includes
---
base/data-struct/radix-tree.c | 3 ---
1 files changed, 0 insertions(+), 3 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
index f2f53e9..b4b6791 100644
--- a/base/data-struct/radix-tree.c
+++ b/base/data-struct/radix-tree.c
@@ -12,9 +12,6 @@
#include "radix-tree.h"
-#include "dm-logging.h"
-#include "log.h"
-
#include "base/memory/container_of.h"
#include "base/memory/zalloc.h"
6 years
master - doc: add a little document describing new directory structure.
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=0a31fb4aa323e0e8636...
Commit: 0a31fb4aa323e0e8636d9c0b9332d14df86afda5
Parent: 576dd1fc41259a9ed3d95b2385305fc035058618
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Fri May 11 06:46:25 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Fri May 11 06:46:25 2018 +0100
doc: add a little document describing new directory structure.
---
doc/refactoring.txt | 158 +++++++++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 158 insertions(+), 0 deletions(-)
diff --git a/doc/refactoring.txt b/doc/refactoring.txt
new file mode 100644
index 0000000..2e9df21
--- /dev/null
+++ b/doc/refactoring.txt
@@ -0,0 +1,158 @@
+Over time, I'd like to refactor the LVM code into these high level modules.
+
+
+ +-------------------------------------------+
+ | |
+ | User Interface |
+ | |
+ | |
+ +-------------------+-----------------------+
+ |
+ +--------------------v-----------------------+
+ | |
+ | LVM Core |
+ | |
+ | |
+ +----+----------------+-----------------+----+
+ | | |
+ +-----v-----+ +-----v------+ +------v----+
+ | | | | | |
+ | Device | | Metadata | | System |
+ | Mapper | | | | |
+ | | | | | |
+ | | | | | |
+ | | | | | |
+ +-----------+ +------------+ +-----------+
+
++---------------------------------------------------------+
+
+
+ +------------------------------------+
+ | |
+ | Base |
+ | |
+ | |
+ | |
+ | |
+ +------------------------------------+
+
+Going from the bottom up we have:
+
+Base
+----
+
+This holds all our general purpose code such as data structures, regex engine,
+memory allocators. In fact pretty much everything in libdevmapper apart from
+the dm code and config.
+
+This can be used by any code in the system, which is why I've drawn a line
+between it and the code above rather than using arrows.
+
+If anyone can come up with a better name please do. I'm trying to stay away
+from 'utils'.
+
+
+Device mapper
+-------------
+
+As well as the low level dm-ioctl driving code we need to have all our dm 'best
+practise' stuff in here. For instance this is the code that decides to use the
+mirror target to move some data around; that knows to suspend a thin volume
+before taking a snapshot of it. This module is going to have a lot more code
+in it than the current libdevmapper.
+
+It should not know anything about the LVM abstractions or metadata (no PVs, LVs
+or VGs). It just knows about the dm world.
+
+Code in here is only allowed to use base.
+
+
+Metadata model
+--------------
+
+Here we have all the format handling, labelling, config parsing etc. We try
+and put *everything* to do with LVM in here that doesn't actually require dm.
+
+
+System
+------
+
+Code that interfaces with the system (udev etc).
+
+
+LVM Core
+--------
+
+[terrible name]
+
+This ties together the last 3 units. It should just be glue. We need to be
+strict about pushing code down from here to keep this as small as possible.
+
+
+User interface
+--------------
+
+Self explanatory.
+
+
+Headers
+-------
+
+Headers will be included using sub directories to make it clearer where they
+are in the tree.
+
+eg,
+ #include "base/mm/pool.h"
+ #include "base/data-struct/list.h"
+ #include "dm/thin-provisioning.h"
+ #include "core/pvmove.h"
+
+
+Getting there
+=============
+
++-------------------------------------------+
+| |
+| |
+| Tools |
+| |
+| |
+| |
++---------+------------------------------+--+
+ | |
+ | +---------------v---------------------------+
+ | | |
+ | | |
+ | | Lib |
+ | | |
+ | | |
+ | | |
+ | | |
+ | +----------------+--------------------------+
+ | |
+ | |
+ +-----v-------------------------------v-----+
+ | |
+ | |
+ | libdevmapper |
+ | |
+ | |
+ | |
+ | |
+ +-------------------------------------------+
+
+This is where I see us now.
+
+'base' should be easy to factor out, it's just the non-dm part of libdevmapper
+(ie. the bulk of it). But we have the problem that libdevmapper is a public
+interface to get round.
+
+'lib' is where the bulk of our code currently is. Dependency-wise the code is
+a bit like a ball of string. So splitting it up is going to take time. We can
+probably pull code pretty quickly into the 'metadata model' dir. But factoring
+out the dm best practises stuff is going to require splitting at least
+files, and probably functions. Certainly not something that can be done in one
+go. System should just be a question of cherry picking functions.
+
+I'm not too familiar with the tools dir. Hopefully it just corresponds with
+the User Interface module and doesn't contain any business logic.
6 years
master - radix-tree: First drop of radix tree.
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=576dd1fc41259a9ed3d...
Commit: 576dd1fc41259a9ed3d95b2385305fc035058618
Parent: 3b02b35c3eef04ddc62302328323d7874f6b9daa
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Fri May 11 06:10:01 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Fri May 11 06:10:01 2018 +0100
radix-tree: First drop of radix tree.
An implementation of an adaptive radix tree. Has the following nice
properties:
- At least as fast as the hash table
- Uses less memory
- You don't need to give an expected size when you create
- It scales nicely (ie. no large reallocations like the hash table).
- You can iterate the keys in lexicographical order.
Only insert and lookup are implemented so far. Plus there's a lot
more performance to come.
---
base/data-struct/radix-tree.c | 573 +++++++++++++++++++++++++++++++++++++++++
base/data-struct/radix-tree.h | 43 +++
base/memory/container_of.h | 23 ++
base/memory/zalloc.h | 31 +++
test/unit/Makefile.in | 2 +
test/unit/radix_tree_t.c | 194 ++++++++++++++
test/unit/units.h | 7 +-
7 files changed, 871 insertions(+), 2 deletions(-)
diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c
new file mode 100644
index 0000000..f2f53e9
--- /dev/null
+++ b/base/data-struct/radix-tree.c
@@ -0,0 +1,573 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+//
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#include "radix-tree.h"
+
+#include "dm-logging.h"
+#include "log.h"
+
+#include "base/memory/container_of.h"
+#include "base/memory/zalloc.h"
+
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+//----------------------------------------------------------------
+
+enum node_type {
+ UNSET = 0,
+ VALUE,
+ VALUE_CHAIN,
+ PREFIX_CHAIN,
+ NODE4,
+ NODE16,
+ NODE48,
+ NODE256
+};
+
+struct value {
+ enum node_type type;
+ union radix_value value;
+};
+
+// This is used for entries that have a key which is a prefix of another key.
+struct value_chain {
+ union radix_value value;
+ struct value child;
+};
+
+struct prefix_chain {
+ struct value child;
+ unsigned len;
+ uint8_t prefix[0];
+};
+
+struct node4 {
+ uint32_t nr_entries;
+ uint8_t keys[4];
+ struct value values[4];
+};
+
+struct node16 {
+ uint32_t nr_entries;
+ uint8_t keys[16];
+ struct value values[16];
+};
+
+struct node48 {
+ uint32_t nr_entries;
+ uint8_t keys[256];
+ struct value values[48];
+};
+
+struct node256 {
+ struct value values[256];
+};
+
+struct radix_tree {
+ unsigned nr_entries;
+ struct value root;
+};
+
+//----------------------------------------------------------------
+
+struct radix_tree *radix_tree_create(void)
+{
+ struct radix_tree *rt = malloc(sizeof(*rt));
+
+ if (rt) {
+ rt->nr_entries = 0;
+ rt->root.type = UNSET;
+ }
+
+ return rt;
+}
+
+static void _free_node(struct value v, radix_value_dtr dtr, void *context)
+{
+ unsigned i;
+ struct value_chain *vc;
+ struct prefix_chain *pc;
+ struct node4 *n4;
+ struct node16 *n16;
+ struct node48 *n48;
+ struct node256 *n256;
+
+ switch (v.type) {
+ case UNSET:
+ break;
+
+ case VALUE:
+ if (dtr)
+ dtr(context, v.value);
+ break;
+
+ case VALUE_CHAIN:
+ vc = v.value.ptr;
+ if (dtr)
+ dtr(context, vc->value);
+ _free_node(vc->child, dtr, context);
+ free(vc);
+ break;
+
+ case PREFIX_CHAIN:
+ pc = v.value.ptr;
+ _free_node(pc->child, dtr, context);
+ free(pc);
+ break;
+
+ case NODE4:
+ n4 = (struct node4 *) v.value.ptr;
+ for (i = 0; i < n4->nr_entries; i++)
+ _free_node(n4->values[i], dtr, context);
+ free(n4);
+ break;
+
+ case NODE16:
+ n16 = (struct node16 *) v.value.ptr;
+ for (i = 0; i < n16->nr_entries; i++)
+ _free_node(n16->values[i], dtr, context);
+ free(n16);
+ break;
+
+ case NODE48:
+ n48 = (struct node48 *) v.value.ptr;
+ for (i = 0; i < n48->nr_entries; i++)
+ _free_node(n48->values[i], dtr, context);
+ free(n48);
+ break;
+
+ case NODE256:
+ n256 = (struct node256 *) v.value.ptr;
+ for (i = 0; i < 256; i++)
+ _free_node(n256->values[i], dtr, context);
+ free(n256);
+ break;
+ }
+}
+
+void radix_tree_destroy(struct radix_tree *rt, radix_value_dtr dtr, void *context)
+{
+ _free_node(rt->root, dtr, context);
+ free(rt);
+}
+
+static bool _insert(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv);
+
+static bool _insert_unset(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ unsigned len = ke - kb;
+
+ if (!len) {
+ // value
+ v->type = VALUE;
+ v->value = rv;
+ } else {
+ // prefix -> value
+ struct prefix_chain *pc = zalloc(sizeof(*pc) + len);
+ if (!pc)
+ return false;
+
+ pc->child.type = VALUE;
+ pc->child.value = rv;
+ pc->len = len;
+ memcpy(pc->prefix, kb, len);
+ v->type = PREFIX_CHAIN;
+ v->value.ptr = pc;
+ }
+
+ return true;
+}
+
+static bool _insert_value(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ unsigned len = ke - kb;
+
+ if (!len)
+ // overwrite
+ v->value = rv;
+
+ else {
+ // value_chain -> value
+ struct value_chain *vc = zalloc(sizeof(*vc));
+ if (!vc)
+ return false;
+
+ vc->value = v->value;
+ if (!_insert(&vc->child, kb, ke, rv)) {
+ free(vc);
+ return false;
+ }
+
+ v->type = VALUE_CHAIN;
+ v->value.ptr = vc;
+ }
+
+ return true;
+}
+
+static bool _insert_value_chain(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct value_chain *vc = v->value.ptr;
+ return _insert(&vc->child, kb, ke, rv);
+}
+
+static unsigned min(unsigned lhs, unsigned rhs)
+{
+ if (lhs <= rhs)
+ return lhs;
+ else
+ return rhs;
+}
+
+static bool _insert_prefix_chain(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct prefix_chain *pc = v->value.ptr;
+
+ if (*kb == pc->prefix[0]) {
+ // There's a common prefix let's split the chain into two and
+ // recurse.
+ struct prefix_chain *pc2;
+ unsigned i, len = min(pc->len, ke - kb);
+
+ for (i = 0; i < len; i++)
+ if (kb[i] != pc->prefix[i])
+ break;
+
+ pc2 = zalloc(sizeof(*pc2) + pc->len - i);
+ pc2->len = pc->len - i;
+ memmove(pc2->prefix, pc->prefix + i, pc2->len);
+ pc2->child = pc->child;
+
+ // FIXME: this trashes pc so we can't back out
+ pc->child.type = PREFIX_CHAIN;
+ pc->child.value.ptr = pc2;
+ pc->len = i;
+
+ if (!_insert(&pc->child, kb + i, ke, rv)) {
+ free(pc2);
+ return false;
+ }
+
+ } else {
+ // Stick an n4 in front.
+ struct node4 *n4 = zalloc(sizeof(*n4));
+ if (!n4)
+ return false;
+
+ n4->keys[0] = *kb;
+ if (!_insert(n4->values, 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;
+
+ v->type = NODE4;
+ v->value.ptr = n4;
+ }
+
+ return true;
+}
+
+static bool _insert_node4(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct node4 *n4 = v->value.ptr;
+ if (n4->nr_entries == 4) {
+ struct node16 *n16 = zalloc(sizeof(*n16));
+ if (!n16)
+ return false;
+
+ n16->nr_entries = 5;
+ memcpy(n16->keys, n4->keys, sizeof(n4->keys));
+ memcpy(n16->values, n4->values, sizeof(n4->values));
+
+ n16->keys[4] = *kb;
+ if (!_insert(n16->values + 4, kb + 1, ke, rv)) {
+ free(n16);
+ return false;
+ }
+ free(n4);
+ v->type = NODE16;
+ v->value.ptr = n16;
+ } else {
+ n4 = v->value.ptr;
+ if (!_insert(n4->values + n4->nr_entries, kb + 1, ke, rv))
+ return false;
+
+ n4->keys[n4->nr_entries] = *kb;
+ n4->nr_entries++;
+ }
+ return true;
+}
+
+static bool _insert_node16(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct node16 *n16 = v->value.ptr;
+
+ if (n16->nr_entries == 16) {
+ unsigned i;
+ struct node48 *n48 = zalloc(sizeof(*n48));
+
+ if (!n48)
+ return false;
+
+ n48->nr_entries = 17;
+ memset(n48->keys, 48, sizeof(n48->keys));
+
+ for (i = 0; i < 16; i++) {
+ n48->keys[n16->keys[i]] = i;
+ n48->values[i] = n16->values[i];
+ }
+
+ n48->keys[*kb] = 16;
+ if (!_insert(n48->values + 16, kb + 1, ke, rv)) {
+ free(n48);
+ return false;
+ }
+
+ free(n16);
+ v->type = NODE48;
+ v->value.ptr = n48;
+ } else {
+ if (!_insert(n16->values + n16->nr_entries, kb + 1, ke, rv))
+ return false;
+ n16->keys[n16->nr_entries] = *kb;
+ n16->nr_entries++;
+ }
+
+ return true;
+}
+
+static bool _insert_node48(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct node48 *n48 = v->value.ptr;
+ if (n48->nr_entries == 48) {
+ unsigned i;
+ struct node256 *n256 = zalloc(sizeof(*n256));
+ if (!n256)
+ return false;
+
+ for (i = 0; i < 256; i++) {
+ if (n48->keys[i] >= 48)
+ continue;
+
+ n256->values[i] = n48->values[n48->keys[i]];
+ }
+
+ if (!_insert(n256->values + *kb, kb + 1, ke, rv)) {
+ free(n256);
+ return false;
+ }
+
+ free(n48);
+ v->type = NODE256;
+ v->value.ptr = n256;
+
+ } else {
+ if (!_insert(n48->values + n48->nr_entries, kb + 1, ke, rv))
+ return false;
+
+ n48->keys[*kb] = n48->nr_entries;
+ n48->nr_entries++;
+ }
+
+ return true;
+}
+
+static bool _insert_node256(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct node256 *n256 = v->value.ptr;
+ if (!_insert(n256->values + *kb, kb + 1, ke, rv)) {
+ n256->values[*kb].type = UNSET;
+ return false;
+ }
+
+ return true;
+}
+
+// FIXME: the tree should not be touched if insert fails (eg, OOM)
+static bool _insert(struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ if (kb == ke) {
+ if (v->type == UNSET) {
+ v->type = VALUE;
+ v->value = rv;
+
+ } else if (v->type == VALUE) {
+ v->value = rv;
+
+ } else {
+ struct value_chain *vc = zalloc(sizeof(*vc));
+ if (!vc)
+ return false;
+
+ vc->value = rv;
+ vc->child = *v;
+ v->type = VALUE_CHAIN;
+ v->value.ptr = vc;
+ }
+ return true;
+ }
+
+ switch (v->type) {
+ case UNSET:
+ return _insert_unset(v, kb, ke, rv);
+
+ case VALUE:
+ return _insert_value(v, kb, ke, rv);
+
+ case VALUE_CHAIN:
+ return _insert_value_chain(v, kb, ke, rv);
+
+ case PREFIX_CHAIN:
+ return _insert_prefix_chain(v, kb, ke, rv);
+
+ case NODE4:
+ return _insert_node4(v, kb, ke, rv);
+
+ case NODE16:
+ return _insert_node16(v, kb, ke, rv);
+
+ case NODE48:
+ return _insert_node48(v, kb, ke, rv);
+
+ case NODE256:
+ return _insert_node256(v, kb, ke, rv);
+ }
+
+ // can't get here
+ return false;
+}
+
+struct lookup_result {
+ struct value *v;
+ uint8_t *kb;
+};
+
+static struct lookup_result _lookup_prefix(struct value *v, uint8_t *kb, uint8_t *ke)
+{
+ unsigned i;
+ struct value_chain *vc;
+ struct prefix_chain *pc;
+ struct node4 *n4;
+ struct node16 *n16;
+ struct node48 *n48;
+ struct node256 *n256;
+
+ if (kb == ke)
+ return (struct lookup_result) {.v = v, .kb = kb};
+
+ switch (v->type) {
+ case UNSET:
+ case VALUE:
+ break;
+
+ case VALUE_CHAIN:
+ vc = v->value.ptr;
+ return _lookup_prefix(&vc->child, kb, ke);
+
+ case PREFIX_CHAIN:
+ pc = v->value.ptr;
+ if (ke - kb < pc->len)
+ return (struct lookup_result) {.v = v, .kb = kb};
+
+ for (i = 0; i < pc->len; i++)
+ if (kb[i] != pc->prefix[i])
+ return (struct lookup_result) {.v = v, .kb = kb};
+
+ return _lookup_prefix(&pc->child, kb + pc->len, ke);
+
+ case NODE4:
+ n4 = v->value.ptr;
+ for (i = 0; i < n4->nr_entries; i++)
+ if (n4->keys[i] == *kb)
+ return _lookup_prefix(n4->values + i, kb + 1, ke);
+ break;
+
+ case NODE16:
+ // FIXME: use binary search or simd?
+ n16 = v->value.ptr;
+ for (i = 0; i < n16->nr_entries; i++)
+ if (n16->keys[i] == *kb)
+ return _lookup_prefix(n16->values + i, kb + 1, ke);
+ break;
+
+ case NODE48:
+ n48 = v->value.ptr;
+ i = n48->keys[*kb];
+ if (i < 48)
+ return _lookup_prefix(n48->values + i, kb + 1, ke);
+ break;
+
+ case NODE256:
+ n256 = v->value.ptr;
+ return _lookup_prefix(n256->values + *kb, kb + 1, ke);
+ }
+
+ return (struct lookup_result) {.v = v, .kb = kb};
+}
+
+bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value rv)
+{
+ struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke);
+ if (_insert(lr.v, lr.kb, ke, rv)) {
+ rt->nr_entries++;
+ return true;
+ }
+
+ return false;
+}
+
+void radix_tree_delete(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_end)
+{
+ assert(0);
+}
+
+bool radix_tree_lookup(struct radix_tree *rt,
+ uint8_t *kb, uint8_t *ke, union radix_value *result)
+{
+ struct value_chain *vc;
+ struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke);
+ if (lr.kb == ke) {
+ switch (lr.v->type) {
+ case VALUE:
+ *result = lr.v->value;
+ return true;
+
+ case VALUE_CHAIN:
+ vc = lr.v->value.ptr;
+ *result = vc->value;
+ return true;
+
+ default:
+ return false;
+ }
+ }
+
+ return false;
+}
+
+//----------------------------------------------------------------
diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h
new file mode 100644
index 0000000..d84e3c5
--- /dev/null
+++ b/base/data-struct/radix-tree.h
@@ -0,0 +1,43 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+//
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#ifndef BASE_DATA_STRUCT_RADIX_TREE_H
+#define BASE_DATA_STRUCT_RADIX_TREE_H
+
+#include <stdbool.h>
+#include <stdint.h>
+
+//----------------------------------------------------------------
+
+struct radix_tree;
+
+union radix_value {
+ void *ptr;
+ uint64_t n;
+};
+
+struct radix_tree *radix_tree_create(void);
+
+typedef void (*radix_value_dtr)(void *context, union radix_value v);
+
+// dtr may be NULL
+void radix_tree_destroy(struct radix_tree *rt, radix_value_dtr dtr, void *context);
+
+unsigned radix_tree_size(struct radix_tree *rt);
+bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value v);
+void radix_tree_delete(struct radix_tree *rt, uint8_t *kb, uint8_t *ke);
+bool radix_tree_lookup(struct radix_tree *rt,
+ uint8_t *kb, uint8_t *ke, union radix_value *result);
+
+//----------------------------------------------------------------
+
+#endif
diff --git a/base/memory/container_of.h b/base/memory/container_of.h
new file mode 100644
index 0000000..4e4c662
--- /dev/null
+++ b/base/memory/container_of.h
@@ -0,0 +1,23 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+//
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#ifndef BASE_MEMORY_CONTAINER_OF_H
+#define BASE_MEMORY_CONTAINER_OF_H
+
+//----------------------------------------------------------------
+
+#define container_of(v, t, head) \
+ ((t *)((const char *)(v) - (const char *)&((t *) 0)->head))
+
+//----------------------------------------------------------------
+
+#endif
diff --git a/base/memory/zalloc.h b/base/memory/zalloc.h
new file mode 100644
index 0000000..d2ef827
--- /dev/null
+++ b/base/memory/zalloc.h
@@ -0,0 +1,31 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+//
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#ifndef BASE_MEMORY_ZALLOC_H
+#define BASE_MEMORY_ZALLOC_H
+
+#include <stdlib.h>
+#include <string.h>
+
+//----------------------------------------------------------------
+
+static inline void *zalloc(size_t len)
+{
+ void *ptr = malloc(len);
+ if (ptr)
+ memset(ptr, 0, len);
+ return ptr;
+}
+
+//----------------------------------------------------------------
+
+#endif
diff --git a/test/unit/Makefile.in b/test/unit/Makefile.in
index 0e1015c..9d18608 100644
--- a/test/unit/Makefile.in
+++ b/test/unit/Makefile.in
@@ -11,6 +11,7 @@
# 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/bcache_t.c \
@@ -20,6 +21,7 @@ UNIT_SOURCE=\
test/unit/dmlist_t.c \
test/unit/dmstatus_t.c \
test/unit/io_engine_t.c \
+ test/unit/radix_tree_t.c \
test/unit/matcher_t.c \
test/unit/framework.c \
test/unit/percent_t.c \
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
new file mode 100644
index 0000000..6a7ecac
--- /dev/null
+++ b/test/unit/radix_tree_t.c
@@ -0,0 +1,194 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+//
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#include "base/data-struct/radix-tree.h"
+
+#include "units.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+//----------------------------------------------------------------
+
+static void *rt_init()
+{
+ struct radix_tree *rt = radix_tree_create();
+ T_ASSERT(rt);
+ return rt;
+}
+
+static void rt_exit(void *fixture)
+{
+ radix_tree_destroy(fixture, NULL, NULL);
+}
+
+static void test_create_destroy(void *fixture)
+{
+ T_ASSERT(fixture);
+}
+
+static void test_insert_one(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ unsigned char k = 'a';
+ v.n = 65;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ v.n = 0;
+ T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 65);
+}
+
+static void test_single_byte_keys(void *fixture)
+{
+ unsigned i, count = 256;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k;
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ v.n = 100 + i;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ }
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 100 + i);
+ }
+}
+
+static void test_overwrite_single_byte_keys(void *fixture)
+{
+ unsigned i, count = 256;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k;
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ v.n = 100 + i;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ }
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ v.n = 1000 + i;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ }
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 1000 + i);
+ }
+}
+
+static void test_16_bit_keys(void *fixture)
+{
+ unsigned i, count = 1 << 16;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[2];
+
+ for (i = 0; i < count; i++) {
+ k[0] = i / 256;
+ k[1] = i % 256;
+ v.n = 100 + i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ for (i = 0; i < count; i++) {
+ k[0] = i / 256;
+ k[1] = i % 256;
+ T_ASSERT(radix_tree_lookup(rt, k, k + sizeof(k), &v));
+ T_ASSERT_EQUAL(v.n, 100 + i);
+ }
+}
+
+static void test_prefix_keys(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[2];
+
+ k[0] = 100;
+ k[1] = 200;
+ v.n = 1024;
+ T_ASSERT(radix_tree_insert(rt, k, k + 1, v));
+ v.n = 2345;
+ T_ASSERT(radix_tree_insert(rt, k, k + 2, v));
+ 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));
+ T_ASSERT_EQUAL(v.n, 2345);
+}
+
+static void test_prefix_keys_reversed(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[2];
+
+ k[0] = 100;
+ k[1] = 200;
+ v.n = 1024;
+ T_ASSERT(radix_tree_insert(rt, k, k + 2, v));
+ v.n = 2345;
+ T_ASSERT(radix_tree_insert(rt, k, k + 1, v));
+ 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));
+ T_ASSERT_EQUAL(v.n, 2345);
+}
+
+static void test_sparse_keys(void *fixture)
+{
+ unsigned i, n;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[32];
+
+ for (n = 0; n < 100000; n++) {
+ for (i = 0; i < 32; i++)
+ k[i] = rand() % 256;
+
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + 32, v));
+ }
+}
+
+//----------------------------------------------------------------
+
+#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)
+{
+ struct test_suite *ts = test_suite_create(rt_init, rt_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("create-destroy", "create and destroy an empty tree", test_create_destroy);
+ T("insert-one", "insert one trivial trivial key", test_insert_one);
+ T("insert-single-byte-keys", "inserts many single byte keys", test_single_byte_keys);
+ T("overwrite-single-byte-keys", "overwrite many single byte keys", test_overwrite_single_byte_keys);
+ T("insert-16-bit-keys", "insert many 16bit keys", test_16_bit_keys);
+ T("prefix-keys", "prefixes of other keys are valid keys", test_prefix_keys);
+ T("prefix-keys-reversed", "prefixes of other keys are valid keys", test_prefix_keys_reversed);
+ T("sparse-keys", "see what the memory usage is for sparsely distributed keys", test_sparse_keys);
+
+ dm_list_add(all_tests, &ts->list);
+}
+//----------------------------------------------------------------
diff --git a/test/unit/units.h b/test/unit/units.h
index ec0cbbf..d7ac6ad 100644
--- a/test/unit/units.h
+++ b/test/unit/units.h
@@ -27,8 +27,9 @@ void config_tests(struct dm_list *suites);
void dm_list_tests(struct dm_list *suites);
void dm_status_tests(struct dm_list *suites);
void io_engine_tests(struct dm_list *suites);
-void regex_tests(struct dm_list *suites);
void percent_tests(struct dm_list *suites);
+void radix_tree_tests(struct dm_list *suites);
+void regex_tests(struct dm_list *suites);
void string_tests(struct dm_list *suites);
void vdo_tests(struct dm_list *suites);
@@ -42,11 +43,13 @@ static inline void register_all_tests(struct dm_list *suites)
dm_list_tests(suites);
dm_status_tests(suites);
io_engine_tests(suites);
- regex_tests(suites);
percent_tests(suites);
+ radix_tree_tests(suites);
+ regex_tests(suites);
string_tests(suites);
vdo_tests(suites);
}
//-----------------------------------------------------------------
+
#endif
6 years
master - Merge branch 'master' of git+ssh://sourceware.org/git/lvm2
by Joe Thornber
Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=3b02b35c3eef04ddc62...
Commit: 3b02b35c3eef04ddc62302328323d7874f6b9daa
Parent: 5f780813f295cd927d92d669ab086063adb1534e 9ad42e5f068ec9c712724631696afb9eb96bc24b
Author: Joe Thornber <ejt(a)redhat.com>
AuthorDate: Fri May 11 05:39:27 2018 +0100
Committer: Joe Thornber <ejt(a)redhat.com>
CommitterDate: Fri May 11 05:39:27 2018 +0100
Merge branch 'master' of git+ssh://sourceware.org/git/lvm2
lib/cache/lvmcache.c | 2 +-
lib/cache/lvmetad.c | 2 +-
lib/commands/toolcontext.c | 2 +-
lib/commands/toolcontext.h | 1 +
lib/device/dev-cache.c | 70 +++++++++++++++++++++++++++++-----
lib/device/dev-io.c | 4 +-
lib/device/dev-luks.c | 13 ++----
lib/device/dev-md.c | 67 +++++++++++++++++++++++++--------
lib/device/dev-swap.c | 16 ++-----
lib/device/dev-type.c | 18 +++------
lib/device/dev-type.h | 7 ++-
lib/device/device.h | 2 +
lib/filters/filter-composite.c | 9 +++-
lib/filters/filter-md.c | 39 ++++++++++++++++--
lib/filters/filter-partitioned.c | 12 +++++-
lib/filters/filter-persistent.c | 78 ++++++++++++++++++++++++++++++-------
lib/filters/filter-signature.c | 12 +++---
lib/filters/filter-usable.c | 9 ----
lib/filters/filter.h | 2 +-
lib/label/label.c | 58 +++++++++++++++++++++++-----
lib/label/label.h | 2 +-
lib/metadata/metadata-exported.h | 2 +-
lib/metadata/metadata.c | 19 ++-------
lib/metadata/mirror.c | 9 ++--
tools/lvmdiskscan.c | 5 +-
tools/pvck.c | 48 +++++++++++++++++------
tools/pvcreate.c | 3 +
tools/pvscan.c | 49 ++++++++++++++++++++---
tools/vgcreate.c | 3 +
tools/vgextend.c | 3 +
30 files changed, 408 insertions(+), 158 deletions(-)
6 years