January 2020 - lvm2-commits - Fedora mailing-lists

master - writecache: report status fields
by David Teigland 01 Feb '20

01 Feb '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=bddbbcb98ca135b91aa68… Commit: bddbbcb98ca135b91aa688c04c1c8be7d76a2bd1 Parent: 2444e830a90fe84721bd61f950946eedcbce0af7 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Fri Jan 31 11:52:49 2020 -0600 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Fri Jan 31 11:52:49 2020 -0600 writecache: report status fields reporting fields (-o) directly from kernel: writecache_total_blocks writecache_free_blocks writecache_writeback_blocks writecache_error The data_percent field shows used cache blocks / total cache blocks. --- device_mapper/all.h | 2 +- device_mapper/libdm-targets.c | 4 ++-- lib/metadata/lv.c | 8 ++++++++ lib/report/columns.h | 4 ++++ lib/report/properties.c | 9 +++++++++ lib/report/report.c | 21 +++++++++++++++++++++ 6 files changed, 45 insertions(+), 3 deletions(-) diff --git a/device_mapper/all.h b/device_mapper/all.h index 57673b4..b23485f 100644 --- a/device_mapper/all.h +++ b/device_mapper/all.h @@ -383,7 +383,7 @@ int dm_get_status_cache(struct dm_pool *mem, const char *params, struct dm_status_cache **status); struct dm_status_writecache { - uint32_t error; + uint64_t error; uint64_t total_blocks; uint64_t free_blocks; uint64_t writeback_blocks; diff --git a/device_mapper/libdm-targets.c b/device_mapper/libdm-targets.c index d82e28b..86cb847 100644 --- a/device_mapper/libdm-targets.c +++ b/device_mapper/libdm-targets.c @@ -366,8 +366,8 @@ int dm_get_status_writecache(struct dm_pool *mem, const char *params, if (!(s = dm_pool_zalloc(mem, sizeof(struct dm_status_writecache)))) return_0; - if (sscanf(params, "%u %llu %llu %llu", - &s->error, + if (sscanf(params, "%llu %llu %llu %llu", + (unsigned long long *)&s->error, (unsigned long long *)&s->total_blocks, (unsigned long long *)&s->free_blocks, (unsigned long long *)&s->writeback_blocks) != 4) { diff --git a/lib/metadata/lv.c b/lib/metadata/lv.c index 4c2ab2b..ab26b8d 100644 --- a/lib/metadata/lv.c +++ b/lib/metadata/lv.c @@ -405,6 +405,14 @@ dm_percent_t lvseg_percent_with_info_and_seg_status(const struct lv_with_info_an } } break; + case SEG_STATUS_WRITECACHE: + if (type != PERCENT_GET_DATA) + p = DM_PERCENT_INVALID; + else { + uint64_t used = s->writecache->total_blocks - s->writecache->free_blocks; + p = dm_make_percent(used, s->writecache->total_blocks); + } + break; case SEG_STATUS_RAID: switch (type) { case PERCENT_GET_DIRTY: diff --git a/lib/report/columns.h b/lib/report/columns.h index 0a89451..31a1d17 100644 --- a/lib/report/columns.h +++ b/lib/report/columns.h @@ -151,6 +151,10 @@ FIELD(LVSSTATUS, lv, STR, "VDOCompressionState", lvid, 0, vdo_compression_state, FIELD(LVSSTATUS, lv, STR, "VDOIndexState", lvid, 0, vdo_index_state, vdo_index_state, "For vdo pools, state of index for deduplication.", 0) FIELD(LVSSTATUS, lv, NUM, "VDOUsedSize", lvid, 0, vdo_used_size, vdo_used_size, "For vdo pools, currently used space.", 0) FIELD(LVSSTATUS, lv, NUM, "VDOSaving%", lvid, 0, vdo_saving_percent, vdo_saving_percent, "For vdo pools, percentage of saved space.", 0) +FIELD(LVSSTATUS, lv, NUM, "WCacheTotalBlocks", lvid, 0, writecache_total_blocks, writecache_total_blocks, "Total writecache blocks.", 0) +FIELD(LVSSTATUS, lv, NUM, "WCacheFreeBlocks", lvid, 0, writecache_free_blocks, writecache_free_blocks, "Total writecache free blocks.", 0) +FIELD(LVSSTATUS, lv, NUM, "WCacheWritebackBlocks", lvid, 0, writecache_writeback_blocks, writecache_writeback_blocks, "Total writecache writeback blocks.", 0) +FIELD(LVSSTATUS, lv, NUM, "WCacheErrors", lvid, 0, writecache_error, writecache_error, "Total writecache errors.", 0) /* * End of LVSSTATUS type fields */ diff --git a/lib/report/properties.c b/lib/report/properties.c index 25e263f..3257505 100644 --- a/lib/report/properties.c +++ b/lib/report/properties.c @@ -279,6 +279,15 @@ GET_PV_NUM_PROPERTY_FN(pv_ba_size, SECTOR_SIZE * pv->ba_size) #define _cache_write_misses_set prop_not_implemented_set #define _cache_write_misses_get prop_not_implemented_get +#define _writecache_total_blocks_set prop_not_implemented_set +#define _writecache_total_blocks_get prop_not_implemented_get +#define _writecache_free_blocks_set prop_not_implemented_set +#define _writecache_free_blocks_get prop_not_implemented_get +#define _writecache_writeback_blocks_set prop_not_implemented_set +#define _writecache_writeback_blocks_get prop_not_implemented_get +#define _writecache_error_set prop_not_implemented_set +#define _writecache_error_get prop_not_implemented_get + #define _vdo_operating_mode_set prop_not_implemented_set #define _vdo_operating_mode_get prop_not_implemented_get #define _vdo_compression_state_set prop_not_implemented_set diff --git a/lib/report/report.c b/lib/report/report.c index 70ee514..d379e2a 100644 --- a/lib/report/report.c +++ b/lib/report/report.c @@ -3875,6 +3875,27 @@ GENERATE_CACHE_STATUS_DISP_FN(read_misses) GENERATE_CACHE_STATUS_DISP_FN(write_hits) GENERATE_CACHE_STATUS_DISP_FN(write_misses) +/* + * Macro to generate '_writecache_<cache_status_field_name>_disp' reporting function. + * The 'writecache_status_field_name' is field name from struct dm_writecache_status. + */ +#define GENERATE_WRITECACHE_STATUS_DISP_FN(writecache_status_field_name) \ +static int _writecache_ ## writecache_status_field_name ## _disp (struct dm_report *rh, \ + struct dm_pool *mem, \ + struct dm_report_field *field, \ + const void *data, \ + void *private) \ +{ \ + const struct lv_with_info_and_seg_status *lvdm = (const struct lv_with_info_and_seg_status *) data; \ + if (lvdm->seg_status.type != SEG_STATUS_WRITECACHE) \ + return _field_set_value(field, "", &GET_TYPE_RESERVED_VALUE(num_undef_64)); \ + return dm_report_field_uint64(rh, field, &lvdm->seg_status.writecache->writecache_status_field_name); \ +} + +GENERATE_WRITECACHE_STATUS_DISP_FN(total_blocks) +GENERATE_WRITECACHE_STATUS_DISP_FN(free_blocks) +GENERATE_WRITECACHE_STATUS_DISP_FN(writeback_blocks) +GENERATE_WRITECACHE_STATUS_DISP_FN(error) /* * Macro to generate '_vdo_<vdo_field_name>_disp' reporting function.

1 0

master - man: updates to lvmcache
by David Teigland 31 Jan '20

31 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=2444e830a90fe84721bd6… Commit: 2444e830a90fe84721bd61f950946eedcbce0af7 Parent: 8810c11bc924e8871f97aa25c61e73b3b3f1fa87 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Thu Jan 30 14:09:21 2020 -0600 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Thu Jan 30 14:09:21 2020 -0600 man: updates to lvmcache --- man/lvmcache.7_main | 99 +++++++++++++++++++++++++++++------------------------ 1 file changed, 54 insertions(+), 45 deletions(-) diff --git a/man/lvmcache.7_main b/man/lvmcache.7_main index 985b79a..fb91be8 100644 --- a/man/lvmcache.7_main +++ b/man/lvmcache.7_main @@ -5,24 +5,32 @@ lvmcache \(em LVM caching .SH DESCRIPTION \fBlvm\fP(8) includes two kinds of caching that can be used to improve the -performance of a Logical Volume (LV). Typically, a smaller, faster device -is used to improve i/o performance of a larger, slower LV. To do this, a -separate LV is created from the faster device, and then the original LV is -converted to start using the fast LV. +performance of a Logical Volume (LV). When caching, varying subsets of an +LV's data are temporarily stored on a smaller, faster device (e.g. an SSD) +to improve the performance of the LV. + +To do this with lvm, a new special LV is first created from the faster +device. This LV will hold the cache. Then, the new fast LV is attached to +the main LV by way of an lvconvert command. lvconvert inserts one of the +device mapper caching targets into the main LV's i/o path. The device +mapper target combines the main LV and fast LV into a hybrid device that looks +like the main LV, but has better performance. While the main LV is being +used, portions of its data will be temporarily and transparently stored on +the special fast LV. The two kinds of caching are: .IP \[bu] 2 -A read and write hot-spot cache, using the dm-cache kernel module. This -cache is slow moving, and adjusts the cache content over time so that the -most used parts of the LV are kept on the faster device. Both reads and -writes use the cache. LVM refers to this using the LV type \fBcache\fP. +A read and write hot-spot cache, using the dm-cache kernel module. +This cache tracks access patterns and adjusts its content deliberately so +that commonly used parts of the main LV are likely to be found on the fast +storage. LVM refers to this using the LV type \fBcache\fP. .IP \[bu] 2 -A streaming write cache, using the dm-writecache kernel module. This -cache is intended to be used with SSD or PMEM devices to speed up all -writes to an LV. Reads do not use this cache. LVM refers to this using -the LV type \fBwritecache\fP. +A write cache, using the dm-writecache kernel module. This cache can be +used with SSD or PMEM devices to speed up all writes to the main LV. Data +read from the main LV is not stored in the cache, only newly written data. +LVM refers to this using the LV type \fBwritecache\fP. .SH USAGE @@ -30,30 +38,31 @@ Both kinds of caching use similar lvm commands: .B 1. Identify main LV that needs caching -A main LV exists on slower devices. +The main LV may already exist, and is located on larger, slower devices. +A main LV would be created with a command like: .nf - $ lvcreate -n main -L Size vg /dev/slow + $ lvcreate -n main -L Size vg /dev/slow_hhd .fi .B 2. Identify fast LV to use as the cache -A fast LV exists on faster devices. This LV will be used to hold the -cache. +A fast LV is created using one or more fast devices, like an SSD. This +special LV will be used to hold the cache: .nf - $ lvcreate -n fast -L Size vg /dev/fast + $ lvcreate -n fast -L Size vg /dev/fast_ssd $ lvs -a LV Attr Type Devices - fast -wi------- linear /dev/fast - main -wi------- linear /dev/slow + fast -wi------- linear /dev/fast_ssd + main -wi------- linear /dev/slow_hhd .fi .B 3. Start caching the main LV -To start caching the main LV using the fast LV, convert the main LV to the -desired caching type, and specify the fast LV to use: +To start caching the main LV, convert the main LV to the desired caching +type, and specify the fast LV to use as the cache: .nf using dm-cache: @@ -83,16 +92,16 @@ using dm-cache: $ lvs -a LV Pool Type Devices main [fast_cvol] cache main_corig(0) - [fast_cvol] linear /dev/fast - [main_corig] linear /dev/slow + [fast_cvol] linear /dev/fast_ssd + [main_corig] linear /dev/slow_hhd using dm-writecache: $ lvs -a LV Pool Type Devices main [fast_cvol] writecache main_wcorig(0) - [fast_cvol] linear /dev/fast - [main_wcorig] linear /dev/slow + [fast_cvol] linear /dev/fast_ssd + [main_wcorig] linear /dev/slow_hhd using dm-cache (with cachepool): @@ -100,9 +109,9 @@ using dm-cache (with cachepool): LV Pool Type Devices main [fast_cpool] cache main_corig(0) [fast_cpool] cache-pool fast_pool_cdata(0) - [fast_cpool_cdata] linear /dev/fast - [fast_cpool_cmeta] linear /dev/fast - [main_corig] linear /dev/slow + [fast_cpool_cdata] linear /dev/fast_ssd + [fast_cpool_cmeta] linear /dev/fast_ssd + [main_corig] linear /dev/slow_hhd .fi .B 5. Use the main LV @@ -120,8 +129,8 @@ attached. $ lvs -a LV VG Attr Type Devices - fast vg -wi------- linear /dev/fast - main vg -wi------- linear /dev/slow + fast vg -wi------- linear /dev/fast_ssd + main vg -wi------- linear /dev/slow_hhd .fi @@ -137,21 +146,21 @@ attached. .I LV .br -Pass this option a standard LV. With a cachevol, cache data and metadata -are contained within the single LV. This is used with dm-writecache or -dm-cache. +Pass this option a fast LV that should be used to hold the cache. With a +cachevol, cache data and metadata are stored in different parts of the +same fast LV. This option can be used with dm-writecache or dm-cache. .B --cachepool .IR CachePoolLV | LV .br -Pass this option a cache pool object. With a cache pool, lvm places cache -data and cache metadata on different LVs. The two LVs together are called -a cache pool. This permits specific placement of data and metadata. A -cache pool is represented as a special type of LV that cannot be used -directly. (If a standard LV is passed to this option, lvm will first -convert it to a cache pool by combining it with another LV to use for -metadata.) This can be used with dm-cache. +Pass this option a cachepool LV or a standard LV. When using a cache +pool, lvm places cache data and cache metadata on different LVs. The two +LVs together are called a cache pool. This permits specific placement of +data and metadata. A cache pool is represented as a special type of LV +that cannot be used directly. If a standard LV is passed with this +option, lvm will first convert it to a cache pool by combining it with +another LV to use for metadata. This option can be used with dm-cache. \& @@ -267,8 +276,8 @@ LV that references two sub LVs, one for data and one for metadata. To create a cache pool from two separate LVs: .nf -$ lvcreate -n fast -L DataSize vg /dev/fast1 -$ lvcreate -n fastmeta -L MetadataSize vg /dev/fast2 +$ lvcreate -n fast -L DataSize vg /dev/fast_ssd1 +$ lvcreate -n fastmeta -L MetadataSize vg /dev/fast_ssd2 $ lvconvert --type cache-pool --poolmetadata fastmeta vg/fast .fi @@ -286,8 +295,8 @@ cache pool LV from the two specified LVs, and use the cache pool to start caching the main LV. .nf -$ lvcreate -n fast -L DataSize vg /dev/fast1 -$ lvcreate -n fastmeta -L MetadataSize vg /dev/fast2 +$ lvcreate -n fast -L DataSize vg /dev/fast_ssd1 +$ lvcreate -n fastmeta -L MetadataSize vg /dev/fast_ssd2 $ lvconvert --type cache --cachepool fast --poolmetadata fastmeta vg/main .fi @@ -418,7 +427,7 @@ and metadata LVs, each of the sub-LVs can use raid1.) .nf $ lvcreate -n main -L Size vg /dev/slow -$ lvcreate --type raid1 -m 1 -n fast -L Size vg /dev/fast1 /dev/fast2 +$ lvcreate --type raid1 -m 1 -n fast -L Size vg /dev/ssd1 /dev/ssd2 $ lvconvert --type cache --cachevol fast vg/main .fi

1 0

master - lvmlockd: use ret value in query function
by David Teigland 30 Jan '20

30 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=8810c11bc924e8871f97a… Commit: 8810c11bc924e8871f97aa25c61e73b3b3f1fa87 Parent: 7404216241827d903dcb3ff441bae0c8819309d2 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Wed Jan 29 10:37:28 2020 -0600 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Wed Jan 29 10:37:28 2020 -0600 lvmlockd: use ret value in query function --- lib/locking/lvmlockd.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/lib/locking/lvmlockd.c b/lib/locking/lvmlockd.c index f396478..cbe2121 100644 --- a/lib/locking/lvmlockd.c +++ b/lib/locking/lvmlockd.c @@ -2114,7 +2114,7 @@ static int _query_lock_lv(struct cmd_context *cmd, struct volume_group *vg, if (result == -ENOENT) return 1; - return 1; + return ret; } /*

1 0

master - WHATS_NEW: update
by Zdenek Kabelac 23 Jan '20

23 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=7404216241827d903dcb3… Commit: 7404216241827d903dcb3ff441bae0c8819309d2 Parent: bab3b70e3ae253da39da6fb9146ccf428cdb6ab3 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Thu Jan 23 10:25:35 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Thu Jan 23 10:32:15 2020 +0100 WHATS_NEW: update --- WHATS_NEW | 2 ++ 1 file changed, 2 insertions(+) diff --git a/WHATS_NEW b/WHATS_NEW index b7aa4e9..66ea748 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,5 +1,7 @@ Version 2.03.08 - ==================================== + Accept more output lines from vdo_format. + Prohibit reshaping of stacked raid LVs. Avoid running cache input arg validation when creating vdo pool. Prevent raid reshaping of stacked volumes. Added VDO lvmdbusd methods for enable/disable compression & dedupe.

1 0

master - tests: add corruption write on PV test
by Zdenek Kabelac 23 Jan '20

23 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=bab3b70e3ae253da39da6… Commit: bab3b70e3ae253da39da6fb9146ccf428cdb6ab3 Parent: ecb77e9db31c88ed1a53e3194366e642f9b04e5a Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 20 14:16:13 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Thu Jan 23 10:32:15 2020 +0100 tests: add corruption write on PV test Test a case where PV is readable, but fails on write updating. Check the failure is reported only for a single PV. --- test/shell/pv-corruption.sh | 56 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) diff --git a/test/shell/pv-corruption.sh b/test/shell/pv-corruption.sh new file mode 100644 index 0000000..b3c5059 --- /dev/null +++ b/test/shell/pv-corruption.sh @@ -0,0 +1,56 @@ +#!/usr/bin/env bash + +# Copyright (C) 2020 Red Hat, Inc. All rights reserved. +# +# 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 General Public License v.2. +# +# You should have received a copy of the GNU 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 + +# tests, write failer on PV1 is not reporting errors on PV2 or PV3... + +SKIP_WITH_LVMLOCKD=1 +SKIP_WITH_LVMPOLLD=1 + +. lib/inittest + +# skip test early if there is no 'delay' target available +aux target_at_least dm-delay 1 1 0 || skip "missing dm-delay target" +touch HAVE_DM_DELAY + +# +# Main +# +aux prepare_devs 3 20 + +pvcreate -y --setphysicalvolumesize 10m "$dev1" +pvcreate "$dev2" +pvcreate "$dev3" + +vgcreate $vg "$dev1" "$dev2" "$dev3" + +pvs -o +uuid + +# Keep device readable, but any write fails +aux writeerror_dev "$dev1" 0:100 + +# Suppose to fail, size PV1 is not writable +not pvresize "$dev1" 2>&1 | tee out + +# Output should not complain about any error on pv2 nor pv3 +not grep pv2 out +not grep pv3 out + +# Restore working PV1 back +aux enable_dev "$dev1" + +# FIXME: Takes a lot of time ATM.... +pvck "$dev2" + +pvs -o +uuid +vgdisplay + +vgremove $vg

1 0

master - tests: writeerror_dev
by Zdenek Kabelac 23 Jan '20

23 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=ecb77e9db31c88ed1a53e… Commit: ecb77e9db31c88ed1a53e3194366e642f9b04e5a Parent: cf844941d4f0939a78a9e0d0e0ef932172e55bfb Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 20 13:15:46 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Thu Jan 23 10:32:15 2020 +0100 tests: writeerror_dev Intruduce aux function for easy simulation of disk areas, that are 'normally' readable, but will fail on write. --- test/lib/aux.sh | 27 +++++++++++++++++++++++++++ 1 file changed, 27 insertions(+) diff --git a/test/lib/aux.sh b/test/lib/aux.sh index ea126de..a9d1fe4 100644 --- a/test/lib/aux.sh +++ b/test/lib/aux.sh @@ -516,6 +516,8 @@ teardown() { echo -n "## teardown..." unset LVM_LOG_FILE_EPOCH + test ! -f ERR_DEV || should dmsetup remove $(cat ERR_DEV_NAME) + if test -f TESTNAME ; then if test ! -f SKIP_THIS_TEST ; then @@ -954,6 +956,8 @@ common_dev_() { case "$tgtype" in delay) echo "$from $len delay $pvdev $(( pos + offset )) $read_ms $pvdev $(( pos + offset )) $write_ms" ;; + writeerror) + echo "$from $len delay $pvdev $(( pos + offset )) 0 $(cat ERR_DEV) 0 0" ;; error|zero) echo "$from $len $tgtype" ;; esac @@ -1082,6 +1086,29 @@ error_dev() { } # +# Convert device to device with write errors but normal reads. +# For this 'delay' dev is used and reroutes 'reads' back to original device +# and for writes it will use extra new TEST-errordev (huge error target) +# i.e. writeerror_dev "$dev1" 8:32 +writeerror_dev() { + local name=${PREFIX}-errordev + + if test ! -e ERR_DEV; then + # delay target is used for error mapping + if test ! -f HAVE_DM_DELAY ; then + target_at_least dm-delay 1 1 0 || return 0 + touch HAVE_DM_DELAY + fi + dmsetup create -u "TEST-$name" "$name" --table "0 4611686018427387904 error" + # Take major:minor of our error device + echo "$name" > ERR_DEV_NAME + dmsetup info -c --noheadings -o major,minor "$name" > ERR_DEV + fi + + common_dev_ writeerror "$@" +} + +# # Convert existing device to a device with zero segments # Takes the list of pairs of zero segment from:len # Combination with error or delay is unsupported

1 0

master - vdo: adapt for multi line vdo_format output
by Zdenek Kabelac 23 Jan '20

23 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=cf844941d4f0939a78a9e… Commit: cf844941d4f0939a78a9e0d0e0ef932172e55bfb Parent: d7bf7091c35d3d34aae0d118fa4b78cd30cd4778 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Wed Jan 22 12:57:23 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Thu Jan 23 10:32:15 2020 +0100 vdo: adapt for multi line vdo_format output Do not close pipeline after 1st. line parsed from vdo_format. Also reprint the output for a user so new messages from vdo_format can be seen by users. --- lib/metadata/vdo_manip.c | 15 +++++++++++---- 1 file changed, 11 insertions(+), 4 deletions(-) diff --git a/lib/metadata/vdo_manip.c b/lib/metadata/vdo_manip.c index 26694cc..b690e73 100644 --- a/lib/metadata/vdo_manip.c +++ b/lib/metadata/vdo_manip.c @@ -317,15 +317,17 @@ static int _format_vdo_pool_data_lv(struct logical_volume *data_lv, } if (!*logical_size) - while (fgets(buf, sizeof(buf), f)) { + while (!feof(f) && fgets(buf, sizeof(buf), f)) { /* TODO: Watch out for locales */ if (sscanf(buf, "Logical blocks defaulted to " FMTu64 " blocks", &lb) == 1) { *logical_size = lb * DM_VDO_BLOCK_SIZE; log_verbose("Available VDO logical blocks " FMTu64 " (%s).", lb, display_size(data_lv->vg->cmd, *logical_size)); - break; - } else - log_warn("WARNING: Cannot parse output '%s' from %s.", buf, argv[0]); + } + if ((dpath = strchr(buf, '\n'))) + *dpath = 0; /* cut last '\n' away */ + if (buf[0]) + log_print(" %s", buf); /* Print vdo_format messages */ } if (!pipe_close(&pdata)) { @@ -333,6 +335,11 @@ static int _format_vdo_pool_data_lv(struct logical_volume *data_lv, return 0; } + if (!*logical_size) { + log_error("Number of VDO logical blocks was not provided by vdo_format output."); + return 0; + } + return 1; }

1 0

master - raid: more limitted prohibition of stacked raid usage
by Zdenek Kabelac 23 Jan '20

23 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=d7bf7091c35d3d34aae0d… Commit: d7bf7091c35d3d34aae0d118fa4b78cd30cd4778 Parent: 7078dd01e86b176aa5bcb964f57db4ba108eeb4e Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Thu Jan 16 16:43:55 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Thu Jan 23 10:32:15 2020 +0100 raid: more limitted prohibition of stacked raid usage We actually need to prohibit only reshaping cases which are running over multiple commands. --- lib/metadata/raid_manip.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/lib/metadata/raid_manip.c b/lib/metadata/raid_manip.c index 4855039..486dea1 100644 --- a/lib/metadata/raid_manip.c +++ b/lib/metadata/raid_manip.c @@ -6210,6 +6210,13 @@ static int _set_convenient_raid145610_segtype_to(const struct lv_segment *seg_fr if (seg_flag) { if (!(*segtype = get_segtype_from_flag(cmd, seg_flag))) return_0; + + /* FIXME Can't reshape volume in use - aka not toplevel devices */ + if (!dm_list_empty(&seg_from->lv->segs_using_this_lv)) { + log_error("Can't reshape stacked volume %s.", display_lvname(seg_from->lv)); + return 0; + } + if (segtype_sav != *segtype) { log_warn("Replaced LV type %s%s with possible type %s.", segtype_sav->name, _get_segtype_alias_str(seg_from->lv, segtype_sav), @@ -6438,12 +6445,6 @@ int lv_raid_convert(struct logical_volume *lv, uint32_t available_slvs, removed_slvs; takeover_fn_t takeover_fn; - /* FIXME Can't reshape volume in use - aka not toplevel devices */ - if (!dm_list_empty(&lv->segs_using_this_lv)) { - log_error("Can't reshape stacked volume %s.", display_lvname(lv)); - return 0; - } - /* FIXME If not active, prompt and activate */ /* FIXME Some operations do not require the LV to be active */ /* LV must be active to perform raid conversion operations */

1 0

master - man: pvck dump description improvements
by David Teigland 23 Jan '20

23 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=7078dd01e86b176aa5bcb… Commit: 7078dd01e86b176aa5bcb964f57db4ba108eeb4e Parent: d53bfae273677975bd805bfaa3d7e7cd995aaa52 Author: David Teigland <teigland(a)redhat.com> AuthorDate: Wed Jan 22 15:01:00 2020 -0600 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Wed Jan 22 15:01:00 2020 -0600 man: pvck dump description improvements --- man/pvck.8_des | 60 +++++++++++++++++++++++++++++++++------------------------- 1 file changed, 34 insertions(+), 26 deletions(-) diff --git a/man/pvck.8_des b/man/pvck.8_des index 8e81493..b87345e 100644 --- a/man/pvck.8_des +++ b/man/pvck.8_des @@ -1,43 +1,49 @@ pvck checks and repairs LVM metadata on PVs. -.SS Dump +.SS Dump options .B headers .br -Print header values and warn if any values are incorrect. Checks the -label_header, pv_header, mda_header(s), and metadata text. +Print LVM on-disk headers and structures: label_header, pv_header, +mda_header(s), and metadata text. Warnings are printed if any values are +incorrect. The label_header and pv_header both exist in a 512 byte +sector, usually the second sector of the device. An mda_header exists in +a 512 byte sector at offset 4096 bytes. A second mda_header can +optionally exist near the end of the device. The metadata text exists in +an area (about 1MiB by default) immediately following the mda_header +sector. The metadata text is checked but not printed (see other options). .B metadata .br -Print or save the current metadata text, using headers to locate the -metadata. If headers are damaged, the metadata may not be found. Use ---settings "mda_num=2" to look in mda2 (the second mda at the end of the -device (if used). The metadata text is printed to stdout. With --file, -the metadata text is saved to a file. +Print the current LVM VG metadata text (or save to a file), using headers +to locate the latest copy of metadata. If headers are damaged, metadata +may not be found (see metadata_search). Use --settings "mda_num=2" to +look in mda2 (the second mda at the end of the device, if used). The +metadata text is printed to stdout or saved to a file with --file. .B metadata_all .br -List or save all versions of metadata found in the metadata area, using -headers to locate the metadata. If headers are damaged, the metadata may -not be found. Use --settings "mda_num=2" as above. All metadata versions -are listed (add -v to include descriptions and dates in the listing.) -With -file, all versions are written to a file. +List all versions of VG metadata found in the metadata area, using headers +to locate metadata. Full copies of all metadata are saved to a file with +the --file option. If headers are damaged, metadata may not be found (see +metadata_search). Use --settings "mda_num=2" as above. Use -v to include +descriptions and dates when listing metadata versions. .B metadata_search .br -Search for all versions of metadata in the common locations. This does -not use headers, so it can find metadata even when headers are damaged. -Use --settings "mda_num=2" as above. All metadata versions are listed -(add -v to include descriptions and dates in the listing.) With --file, -all versions are written to a file. To save one copy of metadata, use ---settings "metadata_offset=<offset>", where the offset is taken from the -dump listing. +List all versions of VG metadata found in the metadata area, searching +common locations so metadata can be found if headers are damaged. Full +copies of all metadata are saved to a file with the --file option. To +save one specific version of metadata, use --settings +"metadata_offset=<offset>", where the offset is taken from the list of +versions found. Use -v to include descriptions and dates when listing +metadata versions. .B metadata_area .br Save the entire text metadata area to a file without processing. -.SS Repair +.SS Repair options .B --repair .br @@ -55,14 +61,15 @@ VG, it is important for the user to determine the correct PV UUID and specify it in --settings. Otherwise, the wrong PV UUID could be used if device names have been swapped since the metadata was last written. -If a PV had no metadata areas and the pv_header is damaged, then the +If a PV has no metadata areas and the pv_header is damaged, then the repair will not know to create no metadata areas during repair. It will by default repair metadata in mda1. To repair with no metadata areas, use --settings "mda_offset=0 mda_size=0". There are cases where repair should be run on all PVs in the VG (using the same metadata file): if all PVs in the VG are damaged, if using an old -metadata version, or if a backup file is used instead of raw metadata. +metadata version, or if a backup file is used instead of raw metadata +(taken from pvck dump.) Using --repair is equivalent to running --repairtype pv_header followed by --repairtype metadata. @@ -102,9 +109,10 @@ print/save one instance of metadata text. \fBmda_offset=\fP\fIbytes\fP \fBmda_size=\fP\fIbytes\fP .br Refers to a metadata area (mda) location and size. An mda includes an -mda_header and circular text buffer. Setting this forces metadata_search -look for metadata in the given area instead of the normal locations. When -set to zero with repair, it indicates no metadata areas should exist. +mda_header and circular metadata text buffer. Setting this forces +metadata_search look for metadata in the given area instead of the +standard locations. When set to zero with repair, it indicates no +metadata areas should exist. \fBmda2_offset=\fP\fIbytes\fP \fBmda2_size=\fP\fIbytes\fP .br

1 0

stable-2.02 - tests: partial revert of test change of b6e6ea2d65785f03f3cee7938be635bcb8ad4944
by Zdenek Kabelac 22 Jan '20

22 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=a1f06e2faebfbc091b4bb… Commit: a1f06e2faebfbc091b4bbb900398cda05264c753 Parent: 62888e9c7692443066e90494764791753277f02e Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Tue Jan 21 17:07:20 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Tue Jan 21 17:07:20 2020 +0100 tests: partial revert of test change of b6e6ea2d65785f03f3cee7938be635bcb8ad4944 With the update with commit b6e6ea2d65785f03f3cee7938be635bcb8ad4944 the test file has been updated - however stable branch still has clvmd & lvmetad so we want to omit runnig unit tests for these runs. --- test/unit/unit-test.sh | 2 ++ 1 file changed, 2 insertions(+) diff --git a/test/unit/unit-test.sh b/test/unit/unit-test.sh index f545f14..e8332d6 100644 --- a/test/unit/unit-test.sh +++ b/test/unit/unit-test.sh @@ -13,6 +13,8 @@ SKIP_WITH_LVMLOCKD=1 SKIP_WITH_LVMPOLLD=1 +SKIP_WITH_LVMETAD=1 +SKIP_WITH_CLVMD=1 SKIP_ROOT_DM_CHECK=1

1 0

stable-2.02 - tests: skip test when dm-delay is not available
by Zdenek Kabelac 22 Jan '20

22 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=62888e9c7692443066e90… Commit: 62888e9c7692443066e90494764791753277f02e Parent: 5ab4d44a3b05cf77836b3be2c812a738131367ae Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Tue Jan 21 16:49:53 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Tue Jan 21 16:49:53 2020 +0100 tests: skip test when dm-delay is not available --- test/shell/pv-corruption.sh | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/test/shell/pv-corruption.sh b/test/shell/pv-corruption.sh index 3958ee1..b3c5059 100644 --- a/test/shell/pv-corruption.sh +++ b/test/shell/pv-corruption.sh @@ -17,6 +17,10 @@ SKIP_WITH_LVMPOLLD=1 . lib/inittest +# skip test early if there is no 'delay' target available +aux target_at_least dm-delay 1 1 0 || skip "missing dm-delay target" +touch HAVE_DM_DELAY + # # Main #

1 0

stable-2.02 - aux: writeerror_dev checks for delay target
by Zdenek Kabelac 22 Jan '20

22 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=5ab4d44a3b05cf77836b3… Commit: 5ab4d44a3b05cf77836b3be2c812a738131367ae Parent: f8ef0307372f13e1a5e74bd5741898f343c520bd Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Tue Jan 21 16:49:34 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Tue Jan 21 16:49:34 2020 +0100 aux: writeerror_dev checks for delay target --- test/lib/aux.sh | 5 +++++ 1 file changed, 5 insertions(+) diff --git a/test/lib/aux.sh b/test/lib/aux.sh index b90063d..7a8d054 100644 --- a/test/lib/aux.sh +++ b/test/lib/aux.sh @@ -1137,6 +1137,11 @@ writeerror_dev() { local name=${PREFIX}-errordev if test ! -e ERR_DEV; then + # delay target is used for error mapping + if test ! -f HAVE_DM_DELAY ; then + target_at_least dm-delay 1 1 0 || return 0 + touch HAVE_DM_DELAY + fi dmsetup create -u "TEST-$name" "$name" --table "0 4611686018427387904 error" # Take major:minor of our error device echo "$name" > ERR_DEV_NAME

1 0

stable-2.02 - tests: add corruption write on PV test
by Zdenek Kabelac 20 Jan '20

20 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c66e01569862a421d137e… Commit: c66e01569862a421d137eedbf9e6abe4e1152853 Parent: 9b41118b9c8fed755eaabb1b0833f2518ddf1c36 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 20 14:16:13 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 20 15:21:38 2020 +0100 tests: add corruption write on PV test Test a case where PV is readable, but fails on write updating. Check the failure is reported only for a single PV. --- test/shell/pv-corruption.sh | 52 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) diff --git a/test/shell/pv-corruption.sh b/test/shell/pv-corruption.sh new file mode 100644 index 0000000..3958ee1 --- /dev/null +++ b/test/shell/pv-corruption.sh @@ -0,0 +1,52 @@ +#!/usr/bin/env bash + +# Copyright (C) 2020 Red Hat, Inc. All rights reserved. +# +# 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 General Public License v.2. +# +# You should have received a copy of the GNU 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 + +# tests, write failer on PV1 is not reporting errors on PV2 or PV3... + +SKIP_WITH_LVMLOCKD=1 +SKIP_WITH_LVMPOLLD=1 + +. lib/inittest + +# +# Main +# +aux prepare_devs 3 20 + +pvcreate -y --setphysicalvolumesize 10m "$dev1" +pvcreate "$dev2" +pvcreate "$dev3" + +vgcreate $vg "$dev1" "$dev2" "$dev3" + +pvs -o +uuid + +# Keep device readable, but any write fails +aux writeerror_dev "$dev1" 0:100 + +# Suppose to fail, size PV1 is not writable +not pvresize "$dev1" 2>&1 | tee out + +# Output should not complain about any error on pv2 nor pv3 +not grep pv2 out +not grep pv3 out + +# Restore working PV1 back +aux enable_dev "$dev1" + +# FIXME: Takes a lot of time ATM.... +pvck "$dev2" + +pvs -o +uuid +vgdisplay + +vgremove $vg

1 0

stable-2.02 - raid: more limitted prohibition of stacked raid usage
by Zdenek Kabelac 20 Jan '20

20 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=f8ef0307372f13e1a5e74… Commit: f8ef0307372f13e1a5e74bd5741898f343c520bd Parent: c66e01569862a421d137eedbf9e6abe4e1152853 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Thu Jan 16 16:43:55 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 20 15:21:38 2020 +0100 raid: more limitted prohibition of stacked raid usage We actually need to prohibit only reshaping cases which are running over multiple commands. --- lib/metadata/raid_manip.c | 13 +++++++------ 1 file changed, 7 insertions(+), 6 deletions(-) diff --git a/lib/metadata/raid_manip.c b/lib/metadata/raid_manip.c index 548faf1..0b0c091 100644 --- a/lib/metadata/raid_manip.c +++ b/lib/metadata/raid_manip.c @@ -6216,6 +6216,13 @@ static int _set_convenient_raid145610_segtype_to(const struct lv_segment *seg_fr if (seg_flag) { if (!(*segtype = get_segtype_from_flag(cmd, seg_flag))) return_0; + + /* FIXME Can't reshape volume in use - aka not toplevel devices */ + if (!dm_list_empty(&seg_from->lv->segs_using_this_lv)) { + log_error("Can't reshape stacked volume %s.", display_lvname(seg_from->lv)); + return 0; + } + if (segtype_sav != *segtype) { log_warn("Replaced LV type %s%s with possible type %s.", segtype_sav->name, _get_segtype_alias_str(seg_from->lv, segtype_sav), @@ -6444,12 +6451,6 @@ int lv_raid_convert(struct logical_volume *lv, uint32_t available_slvs, removed_slvs; takeover_fn_t takeover_fn; - /* FIXME Can't reshape volume in use - aka not toplevel devices */ - if (!dm_list_empty(&lv->segs_using_this_lv)) { - log_error("Can't reshape stacked volume %s.", display_lvname(lv)); - return 0; - } - /* FIXME If not active, prompt and activate */ /* FIXME Some operations do not require the LV to be active */ /* LV must be active to perform raid conversion operations */

1 0

stable-2.02 - tests: writeerror_dev
by Zdenek Kabelac 20 Jan '20

20 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=9b41118b9c8fed755eaab… Commit: 9b41118b9c8fed755eaabb1b0833f2518ddf1c36 Parent: 440ced192a5ae6d5fa7c191981abcdf59926e90b Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 20 13:15:46 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 20 15:21:38 2020 +0100 tests: writeerror_dev Intruduce aux function for easy simulation of disk areas, that are 'normally' readable, but will fail on write. --- test/lib/aux.sh | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/test/lib/aux.sh b/test/lib/aux.sh index ec0699f..b90063d 100644 --- a/test/lib/aux.sh +++ b/test/lib/aux.sh @@ -564,6 +564,8 @@ teardown() { echo -n "## teardown..." unset LVM_LOG_FILE_EPOCH + test ! -f ERR_DEV || should dmsetup remove $(cat ERR_DEV_NAME) + if test -f TESTNAME ; then if test ! -f SKIP_THIS_TEST ; then @@ -985,6 +987,8 @@ common_dev_() { case "$tgtype" in delay) echo "$from $len delay $pvdev $(( pos + offset )) $read_ms $pvdev $(( pos + offset )) $write_ms" ;; + writeerror) + echo "$from $len delay $pvdev $(( pos + offset )) 0 $(cat ERR_DEV) 0 0" ;; error|zero) echo "$from $len $tgtype" ;; esac @@ -1125,6 +1129,24 @@ error_dev() { } # +# Convert device to device with write errors but normal reads. +# For this 'delay' dev is used and reroutes 'reads' back to original device +# and for writes it will use extra new TEST-errordev (huge error target) +# i.e. writeerror_dev "$dev1" 8:32 +writeerror_dev() { + local name=${PREFIX}-errordev + + if test ! -e ERR_DEV; then + dmsetup create -u "TEST-$name" "$name" --table "0 4611686018427387904 error" + # Take major:minor of our error device + echo "$name" > ERR_DEV_NAME + dmsetup info -c --noheadings -o major,minor "$name" > ERR_DEV + fi + + common_dev_ writeerror "$@" +} + +# # Convert existing device to a device with zero segments # Takes the list of pairs of zero segment from:len # Combination with error or delay is unsupported

1 0

stable-2.02 - base: Get Makefile from master
by Marian Csontos 20 Jan '20

20 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=440ced192a5ae6d5fa7c1… Commit: 440ced192a5ae6d5fa7c191981abcdf59926e90b Parent: d20490f76dd5a82b5fe61adc1c4e8044593e1c98 Author: Marian Csontos <mcsontos(a)redhat.com> AuthorDate: Mon Jan 20 14:36:16 2020 +0100 Committer: Marian Csontos <mcsontos(a)redhat.com> CommitterDate: Mon Jan 20 14:48:58 2020 +0100 base: Get Makefile from master --- base/Makefile | 38 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 38 insertions(+) diff --git a/base/Makefile b/base/Makefile new file mode 100644 index 000000000..056ea5910 --- /dev/null +++ b/base/Makefile @@ -0,0 +1,38 @@ +# Copyright (C) 2018 Red Hat, Inc. All rights reserved. +# +# This file is part of the device-mapper userspace tools. +# +# 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 + +# Uncomment this to build the simple radix tree. You'll need to make clean too. +# Comment to build the advanced radix tree. +#base/data-struct/radix-tree.o: CFLAGS += -DSIMPLE_RADIX_TREE + +# NOTE: this Makefile only works as 'include' for toplevel Makefile +# which defined all top_* variables + +BASE_SOURCE=\ + base/data-struct/radix-tree.c + +BASE_TARGET = base/libbase.a +BASE_DEPENDS = $(BASE_SOURCE:%.c=%.d) +BASE_OBJECTS = $(BASE_SOURCE:%.c=%.o) +CLEAN_TARGETS += $(BASE_DEPENDS) $(BASE_OBJECTS) \ + $(BASE_SOURCE:%.c=%.gcda) \ + $(BASE_SOURCE:%.c=%.gcno) \ + $(BASE_TARGET) + +$(BASE_TARGET): $(BASE_OBJECTS) + @echo " [AR] $@" + $(Q) $(RM) $@ + $(Q) $(AR) rsv $@ $(BASE_OBJECTS) > /dev/null + +ifeq ("$(DEPENDS)","yes") +-include $(BASE_DEPENDS) +endif

1 0

stable-2.02 - [radix-tree] Add missing test case
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=d20490f76dd5a82b5fe61… Commit: d20490f76dd5a82b5fe61adc1c4e8044593e1c98 Parent: 019fa6f8eec799ebc7a9b9c5b31354ff1717db12 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Jan 16 15:25:18 2020 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 15:25:18 2020 +0000 [radix-tree] Add missing test case --- test/unit/rt_case1.c | 1669 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1669 insertions(+) diff --git a/test/unit/rt_case1.c b/test/unit/rt_case1.c new file mode 100644 index 000000000..c1677d185 --- /dev/null +++ b/test/unit/rt_case1.c @@ -0,0 +1,1669 @@ + __lookup_fails(rt, 6, 0); + __insert(rt, 6, 0, 0); + __lookup_fails(rt, 7, 0); + __insert(rt, 7, 0, 1); + __lookup_fails(rt, 8, 0); + __insert(rt, 8, 0, 2); + __lookup_fails(rt, 9, 0); + __insert(rt, 9, 0, 3); + __lookup_fails(rt, 10, 0); + __insert(rt, 10, 0, 4); + __lookup_fails(rt, 11, 0); + __insert(rt, 11, 0, 5); + __lookup_fails(rt, 12, 0); + __insert(rt, 12, 0, 6); + __lookup_fails(rt, 13, 0); + __insert(rt, 13, 0, 7); + __lookup_fails(rt, 14, 0); + __insert(rt, 14, 0, 8); + __lookup_fails(rt, 15, 0); + __insert(rt, 15, 0, 9); + __lookup_fails(rt, 16, 0); + __insert(rt, 16, 0, 10); + __lookup_fails(rt, 17, 0); + __insert(rt, 17, 0, 11); + __lookup_fails(rt, 18, 0); + __insert(rt, 18, 0, 12); + __lookup_fails(rt, 19, 0); + __insert(rt, 19, 0, 13); + __lookup_fails(rt, 20, 0); + __insert(rt, 20, 0, 14); + __lookup_fails(rt, 21, 0); + __insert(rt, 21, 0, 15); + __lookup_fails(rt, 22, 0); + __insert(rt, 22, 0, 16); + __lookup_fails(rt, 23, 0); + __insert(rt, 23, 0, 17); + __lookup_fails(rt, 24, 0); + __insert(rt, 24, 0, 18); + __lookup_fails(rt, 25, 0); + __insert(rt, 25, 0, 19); + __lookup_fails(rt, 26, 0); + __insert(rt, 26, 0, 20); + __lookup_fails(rt, 27, 0); + __insert(rt, 27, 0, 21); + __lookup_fails(rt, 28, 0); + __insert(rt, 28, 0, 22); + __lookup_fails(rt, 29, 0); + __insert(rt, 29, 0, 23); + __lookup_fails(rt, 30, 0); + __insert(rt, 30, 0, 24); + __lookup_fails(rt, 31, 0); + __insert(rt, 31, 0, 25); + __lookup_fails(rt, 32, 0); + __insert(rt, 32, 0, 26); + __lookup_fails(rt, 33, 0); + __insert(rt, 33, 0, 27); + __lookup_fails(rt, 34, 0); + __insert(rt, 34, 0, 28); + __lookup_fails(rt, 35, 0); + __insert(rt, 35, 0, 29); + __lookup_fails(rt, 36, 0); + __insert(rt, 36, 0, 30); + __lookup_fails(rt, 37, 0); + __insert(rt, 37, 0, 31); + __lookup_fails(rt, 38, 0); + __insert(rt, 38, 0, 32); + __lookup_fails(rt, 39, 0); + __insert(rt, 39, 0, 33); + __lookup_fails(rt, 40, 0); + __insert(rt, 40, 0, 34); + __lookup_fails(rt, 41, 0); + __insert(rt, 41, 0, 35); + __lookup_fails(rt, 42, 0); + __insert(rt, 42, 0, 36); + __lookup_fails(rt, 43, 0); + __insert(rt, 43, 0, 37); + __lookup_fails(rt, 44, 0); + __insert(rt, 44, 0, 38); + __lookup_fails(rt, 45, 0); + __insert(rt, 45, 0, 39); + __lookup_fails(rt, 46, 0); + __insert(rt, 46, 0, 40); + __lookup_fails(rt, 47, 0); + __insert(rt, 47, 0, 41); + __lookup_fails(rt, 48, 0); + __insert(rt, 48, 0, 42); + __lookup_fails(rt, 49, 0); + __insert(rt, 49, 0, 43); + __lookup_fails(rt, 50, 0); + __insert(rt, 50, 0, 44); + __lookup_fails(rt, 51, 0); + __insert(rt, 51, 0, 45); + __lookup_fails(rt, 52, 0); + __insert(rt, 52, 0, 46); + __lookup_fails(rt, 53, 0); + __insert(rt, 53, 0, 47); + __lookup_fails(rt, 54, 0); + __insert(rt, 54, 0, 48); + __lookup_fails(rt, 55, 0); + __insert(rt, 55, 0, 49); + __lookup_fails(rt, 56, 0); + __insert(rt, 56, 0, 50); + __lookup_fails(rt, 57, 0); + __insert(rt, 57, 0, 51); + __lookup_fails(rt, 58, 0); + __insert(rt, 58, 0, 52); + __lookup_fails(rt, 59, 0); + __insert(rt, 59, 0, 53); + __lookup_fails(rt, 60, 0); + __insert(rt, 60, 0, 54); + __lookup_fails(rt, 61, 0); + __insert(rt, 61, 0, 55); + __lookup_fails(rt, 62, 0); + __insert(rt, 62, 0, 56); + __lookup_fails(rt, 63, 0); + __insert(rt, 63, 0, 57); + __lookup_fails(rt, 64, 0); + __insert(rt, 64, 0, 58); + __lookup_fails(rt, 65, 0); + __insert(rt, 65, 0, 59); + __lookup_fails(rt, 66, 0); + __insert(rt, 66, 0, 60); + __lookup_fails(rt, 67, 0); + __insert(rt, 67, 0, 61); + __lookup_fails(rt, 68, 0); + __insert(rt, 68, 0, 62); + __lookup_fails(rt, 69, 0); + __insert(rt, 69, 0, 63); + __lookup_fails(rt, 70, 0); + __insert(rt, 70, 0, 64); + __lookup_fails(rt, 71, 0); + __insert(rt, 71, 0, 65); + __lookup_fails(rt, 72, 0); + __insert(rt, 72, 0, 66); + __lookup_fails(rt, 73, 0); + __insert(rt, 73, 0, 67); + __lookup_fails(rt, 74, 0); + __insert(rt, 74, 0, 68); + __lookup_fails(rt, 75, 0); + __insert(rt, 75, 0, 69); + __lookup_fails(rt, 76, 0); + __insert(rt, 76, 0, 70); + __lookup_fails(rt, 77, 0); + __insert(rt, 77, 0, 71); + __lookup_fails(rt, 78, 0); + __insert(rt, 78, 0, 72); + __lookup_fails(rt, 79, 0); + __insert(rt, 79, 0, 73); + __lookup_fails(rt, 80, 0); + __insert(rt, 80, 0, 74); + __lookup_fails(rt, 81, 0); + __insert(rt, 81, 0, 75); + __lookup_fails(rt, 82, 0); + __insert(rt, 82, 0, 76); + __lookup_fails(rt, 83, 0); + __insert(rt, 83, 0, 77); + __lookup_fails(rt, 84, 0); + __insert(rt, 84, 0, 78); + __lookup_fails(rt, 85, 0); + __insert(rt, 85, 0, 79); + __lookup_fails(rt, 86, 0); + __insert(rt, 86, 0, 80); + __lookup_fails(rt, 87, 0); + __insert(rt, 87, 0, 81); + __lookup_fails(rt, 88, 0); + __insert(rt, 88, 0, 82); + __lookup_fails(rt, 89, 0); + __insert(rt, 89, 0, 83); + __lookup_fails(rt, 90, 0); + __insert(rt, 90, 0, 84); + __lookup_fails(rt, 91, 0); + __insert(rt, 91, 0, 85); + __lookup_fails(rt, 92, 0); + __insert(rt, 92, 0, 86); + __lookup_fails(rt, 93, 0); + __insert(rt, 93, 0, 87); + __lookup_fails(rt, 94, 0); + __insert(rt, 94, 0, 88); + __lookup_fails(rt, 95, 0); + __insert(rt, 95, 0, 89); + __lookup_fails(rt, 96, 0); + __insert(rt, 96, 0, 90); + __lookup_fails(rt, 97, 0); + __insert(rt, 97, 0, 91); + __lookup_fails(rt, 98, 0); + __insert(rt, 98, 0, 92); + __lookup_fails(rt, 99, 0); + __insert(rt, 99, 0, 93); + __lookup_fails(rt, 100, 0); + __insert(rt, 100, 0, 94); + __lookup_fails(rt, 101, 0); + __insert(rt, 101, 0, 95); + __lookup_fails(rt, 102, 0); + __insert(rt, 102, 0, 96); + __lookup_fails(rt, 103, 0); + __insert(rt, 103, 0, 97); + __lookup_fails(rt, 104, 0); + __insert(rt, 104, 0, 98); + __lookup_fails(rt, 105, 0); + __insert(rt, 105, 0, 99); + __lookup_fails(rt, 106, 0); + __insert(rt, 106, 0, 100); + __lookup_fails(rt, 107, 0); + __insert(rt, 107, 0, 101); + __lookup_fails(rt, 108, 0); + __insert(rt, 108, 0, 102); + __lookup_fails(rt, 109, 0); + __insert(rt, 109, 0, 103); + __lookup_fails(rt, 110, 0); + __insert(rt, 110, 0, 104); + __lookup_fails(rt, 111, 0); + __insert(rt, 111, 0, 105); + __lookup_fails(rt, 112, 0); + __insert(rt, 112, 0, 106); + __lookup_fails(rt, 113, 0); + __insert(rt, 113, 0, 107); + __lookup_fails(rt, 114, 0); + __insert(rt, 114, 0, 108); + __lookup_fails(rt, 115, 0); + __insert(rt, 115, 0, 109); + __lookup_fails(rt, 116, 0); + __insert(rt, 116, 0, 110); + __lookup_fails(rt, 117, 0); + __insert(rt, 117, 0, 111); + __lookup_fails(rt, 118, 0); + __insert(rt, 118, 0, 112); + __lookup_fails(rt, 119, 0); + __insert(rt, 119, 0, 113); + __lookup_fails(rt, 120, 0); + __insert(rt, 120, 0, 114); + __lookup_fails(rt, 121, 0); + __insert(rt, 121, 0, 115); + __lookup_fails(rt, 122, 0); + __insert(rt, 122, 0, 116); + __lookup_fails(rt, 123, 0); + __insert(rt, 123, 0, 117); + __lookup_fails(rt, 124, 0); + __insert(rt, 124, 0, 118); + __lookup_fails(rt, 125, 0); + __insert(rt, 125, 0, 119); + __lookup_fails(rt, 126, 0); + __insert(rt, 126, 0, 120); + __lookup_fails(rt, 127, 0); + __insert(rt, 127, 0, 121); + __lookup_fails(rt, 128, 0); + __insert(rt, 128, 0, 122); + __lookup_fails(rt, 129, 0); + __insert(rt, 129, 0, 123); + __lookup_fails(rt, 130, 0); + __insert(rt, 130, 0, 124); + __lookup_fails(rt, 131, 0); + __insert(rt, 131, 0, 125); + __lookup_fails(rt, 132, 0); + __insert(rt, 132, 0, 126); + __lookup_fails(rt, 133, 0); + __insert(rt, 133, 0, 127); + __lookup_fails(rt, 134, 0); + __insert(rt, 134, 0, 128); + __lookup_fails(rt, 135, 0); + __insert(rt, 135, 0, 129); + __lookup_fails(rt, 136, 0); + __insert(rt, 136, 0, 130); + __lookup_fails(rt, 137, 0); + __insert(rt, 137, 0, 131); + __lookup_fails(rt, 138, 0); + __insert(rt, 138, 0, 132); + __lookup_fails(rt, 139, 0); + __insert(rt, 139, 0, 133); + __lookup_fails(rt, 140, 0); + __insert(rt, 140, 0, 134); + __lookup_fails(rt, 141, 0); + __insert(rt, 141, 0, 135); + __lookup_fails(rt, 142, 0); + __insert(rt, 142, 0, 136); + __lookup_fails(rt, 143, 0); + __insert(rt, 143, 0, 137); + __lookup_fails(rt, 144, 0); + __insert(rt, 144, 0, 138); + __lookup_fails(rt, 145, 0); + __insert(rt, 145, 0, 139); + __lookup_fails(rt, 146, 0); + __insert(rt, 146, 0, 140); + __lookup_fails(rt, 147, 0); + __insert(rt, 147, 0, 141); + __lookup_fails(rt, 148, 0); + __insert(rt, 148, 0, 142); + __lookup_fails(rt, 149, 0); + __insert(rt, 149, 0, 143); + __lookup_fails(rt, 150, 0); + __insert(rt, 150, 0, 144); + __lookup_fails(rt, 151, 0); + __insert(rt, 151, 0, 145); + __lookup_fails(rt, 152, 0); + __insert(rt, 152, 0, 146); + __lookup_fails(rt, 153, 0); + __insert(rt, 153, 0, 147); + __lookup_fails(rt, 154, 0); + __insert(rt, 154, 0, 148); + __lookup_fails(rt, 155, 0); + __insert(rt, 155, 0, 149); + __lookup_fails(rt, 156, 0); + __insert(rt, 156, 0, 150); + __lookup_fails(rt, 157, 0); + __insert(rt, 157, 0, 151); + __lookup_fails(rt, 158, 0); + __insert(rt, 158, 0, 152); + __lookup_fails(rt, 159, 0); + __insert(rt, 159, 0, 153); + __lookup_fails(rt, 160, 0); + __insert(rt, 160, 0, 154); + __lookup_fails(rt, 161, 0); + __insert(rt, 161, 0, 155); + __lookup_fails(rt, 162, 0); + __insert(rt, 162, 0, 156); + __lookup_fails(rt, 163, 0); + __insert(rt, 163, 0, 157); + __lookup_fails(rt, 164, 0); + __insert(rt, 164, 0, 158); + __lookup_fails(rt, 165, 0); + __insert(rt, 165, 0, 159); + __lookup_fails(rt, 166, 0); + __insert(rt, 166, 0, 160); + __lookup_fails(rt, 167, 0); + __insert(rt, 167, 0, 161); + __lookup_fails(rt, 168, 0); + __insert(rt, 168, 0, 162); + __lookup_fails(rt, 169, 0); + __insert(rt, 169, 0, 163); + __lookup_fails(rt, 170, 0); + __insert(rt, 170, 0, 164); + __lookup_fails(rt, 171, 0); + __insert(rt, 171, 0, 165); + __lookup_fails(rt, 172, 0); + __insert(rt, 172, 0, 166); + __lookup_fails(rt, 173, 0); + __insert(rt, 173, 0, 167); + __lookup_fails(rt, 174, 0); + __insert(rt, 174, 0, 168); + __lookup_fails(rt, 175, 0); + __insert(rt, 175, 0, 169); + __lookup_fails(rt, 176, 0); + __insert(rt, 176, 0, 170); + __lookup_fails(rt, 177, 0); + __insert(rt, 177, 0, 171); + __lookup_fails(rt, 178, 0); + __insert(rt, 178, 0, 172); + __lookup_fails(rt, 179, 0); + __insert(rt, 179, 0, 173); + __lookup_fails(rt, 180, 0); + __insert(rt, 180, 0, 174); + __lookup_fails(rt, 181, 0); + __insert(rt, 181, 0, 175); + __lookup_fails(rt, 182, 0); + __insert(rt, 182, 0, 176); + __lookup_fails(rt, 183, 0); + __insert(rt, 183, 0, 177); + __lookup_fails(rt, 184, 0); + __insert(rt, 184, 0, 178); + __lookup_fails(rt, 185, 0); + __insert(rt, 185, 0, 179); + __lookup_fails(rt, 186, 0); + __insert(rt, 186, 0, 180); + __lookup_fails(rt, 187, 0); + __insert(rt, 187, 0, 181); + __lookup_fails(rt, 188, 0); + __insert(rt, 188, 0, 182); + __lookup_fails(rt, 189, 0); + __insert(rt, 189, 0, 183); + __lookup_fails(rt, 190, 0); + __insert(rt, 190, 0, 184); + __lookup_fails(rt, 191, 0); + __insert(rt, 191, 0, 185); + __lookup_fails(rt, 192, 0); + __insert(rt, 192, 0, 186); + __lookup_fails(rt, 193, 0); + __insert(rt, 193, 0, 187); + __lookup_fails(rt, 194, 0); + __insert(rt, 194, 0, 188); + __lookup_fails(rt, 195, 0); + __insert(rt, 195, 0, 189); + __lookup_fails(rt, 196, 0); + __insert(rt, 196, 0, 190); + __lookup_fails(rt, 197, 0); + __insert(rt, 197, 0, 191); + __lookup_fails(rt, 198, 0); + __insert(rt, 198, 0, 192); + __lookup_fails(rt, 199, 0); + __insert(rt, 199, 0, 193); + __lookup_fails(rt, 200, 0); + __insert(rt, 200, 0, 194); + __lookup_fails(rt, 201, 0); + __insert(rt, 201, 0, 195); + __lookup_fails(rt, 202, 0); + __insert(rt, 202, 0, 196); + __lookup_fails(rt, 203, 0); + __insert(rt, 203, 0, 197); + __lookup_fails(rt, 204, 0); + __insert(rt, 204, 0, 198); + __lookup_fails(rt, 205, 0); + __insert(rt, 205, 0, 199); + __lookup_matches(rt, 6, 0, 0); + __invalidate(rt, 6); + __lookup_matches(rt, 7, 0, 1); + __invalidate(rt, 7); + __lookup_matches(rt, 8, 0, 2); + __invalidate(rt, 8); + __lookup_matches(rt, 9, 0, 3); + __invalidate(rt, 9); + __lookup_matches(rt, 10, 0, 4); + __invalidate(rt, 10); + __lookup_matches(rt, 11, 0, 5); + __invalidate(rt, 11); + __lookup_matches(rt, 12, 0, 6); + __lookup_matches(rt, 13, 0, 7); + __invalidate(rt, 13); + __lookup_matches(rt, 14, 0, 8); + __invalidate(rt, 14); + __lookup_matches(rt, 15, 0, 9); + __invalidate(rt, 15); + __lookup_matches(rt, 16, 0, 10); + __invalidate(rt, 16); + __lookup_matches(rt, 17, 0, 11); + __invalidate(rt, 17); + __lookup_matches(rt, 18, 0, 12); + __invalidate(rt, 18); + __lookup_matches(rt, 19, 0, 13); + __invalidate(rt, 19); + __lookup_matches(rt, 20, 0, 14); + __invalidate(rt, 20); + __lookup_matches(rt, 21, 0, 15); + __invalidate(rt, 21); + __lookup_matches(rt, 22, 0, 16); + __invalidate(rt, 22); + __lookup_matches(rt, 23, 0, 17); + __invalidate(rt, 23); + __lookup_matches(rt, 24, 0, 18); + __invalidate(rt, 24); + __lookup_matches(rt, 25, 0, 19); + __invalidate(rt, 25); + __lookup_matches(rt, 26, 0, 20); + __invalidate(rt, 26); + __lookup_matches(rt, 27, 0, 21); + __invalidate(rt, 27); + __lookup_matches(rt, 28, 0, 22); + __invalidate(rt, 28); + __lookup_matches(rt, 29, 0, 23); + __invalidate(rt, 29); + __lookup_matches(rt, 30, 0, 24); + __invalidate(rt, 30); + __lookup_matches(rt, 31, 0, 25); + __invalidate(rt, 31); + __lookup_matches(rt, 32, 0, 26); + __invalidate(rt, 32); + __lookup_matches(rt, 33, 0, 27); + __invalidate(rt, 33); + __lookup_matches(rt, 34, 0, 28); + __invalidate(rt, 34); + __lookup_matches(rt, 35, 0, 29); + __invalidate(rt, 35); + __lookup_matches(rt, 36, 0, 30); + __invalidate(rt, 36); + __lookup_matches(rt, 37, 0, 31); + __invalidate(rt, 37); + __lookup_matches(rt, 38, 0, 32); + __invalidate(rt, 38); + __lookup_matches(rt, 39, 0, 33); + __invalidate(rt, 39); + __lookup_matches(rt, 40, 0, 34); + __invalidate(rt, 40); + __lookup_matches(rt, 41, 0, 35); + __invalidate(rt, 41); + __lookup_matches(rt, 42, 0, 36); + __invalidate(rt, 42); + __lookup_matches(rt, 43, 0, 37); + __invalidate(rt, 43); + __lookup_matches(rt, 44, 0, 38); + __invalidate(rt, 44); + __lookup_matches(rt, 45, 0, 39); + __invalidate(rt, 45); + __lookup_matches(rt, 46, 0, 40); + __lookup_fails(rt, 46, 5); + __insert(rt, 46, 5, 200); + __lookup_matches(rt, 46, 5, 200); + __lookup_fails(rt, 46, 6); + __insert(rt, 46, 6, 201); + __lookup_fails(rt, 46, 7); + __insert(rt, 46, 7, 202); + __lookup_fails(rt, 46, 8); + __insert(rt, 46, 8, 203); + __lookup_matches(rt, 46, 5, 200); + __lookup_matches(rt, 46, 6, 201); + __lookup_matches(rt, 46, 7, 202); + __lookup_matches(rt, 46, 8, 203); + __lookup_matches(rt, 47, 0, 41); + __invalidate(rt, 47); + __lookup_matches(rt, 48, 0, 42); + __invalidate(rt, 48); + __lookup_matches(rt, 49, 0, 43); + __invalidate(rt, 49); + __lookup_matches(rt, 50, 0, 44); + __invalidate(rt, 50); + __lookup_matches(rt, 51, 0, 45); + __invalidate(rt, 51); + __lookup_matches(rt, 52, 0, 46); + __invalidate(rt, 52); + __lookup_matches(rt, 53, 0, 47); + __invalidate(rt, 53); + __lookup_matches(rt, 54, 0, 48); + __invalidate(rt, 54); + __lookup_matches(rt, 55, 0, 49); + __invalidate(rt, 55); + __lookup_matches(rt, 56, 0, 50); + __invalidate(rt, 56); + __lookup_matches(rt, 57, 0, 51); + __invalidate(rt, 57); + __lookup_matches(rt, 58, 0, 52); + __invalidate(rt, 58); + __lookup_matches(rt, 59, 0, 53); + __invalidate(rt, 59); + __lookup_matches(rt, 60, 0, 54); + __invalidate(rt, 60); + __lookup_matches(rt, 61, 0, 55); + __invalidate(rt, 61); + __lookup_matches(rt, 62, 0, 56); + __invalidate(rt, 62); + __lookup_matches(rt, 63, 0, 57); + __invalidate(rt, 63); + __lookup_matches(rt, 64, 0, 58); + __invalidate(rt, 64); + __lookup_matches(rt, 65, 0, 59); + __lookup_fails(rt, 65, 1); + __insert(rt, 65, 1, 204); + __lookup_fails(rt, 65, 2); + __insert(rt, 65, 2, 205); + __lookup_fails(rt, 65, 3); + __insert(rt, 65, 3, 206); + __lookup_fails(rt, 65, 4); + __insert(rt, 65, 4, 207); + __lookup_matches(rt, 65, 0, 59); + __lookup_matches(rt, 65, 1, 204); + __lookup_matches(rt, 65, 2, 205); + __lookup_matches(rt, 65, 3, 206); + __lookup_matches(rt, 65, 4, 207); + __lookup_matches(rt, 66, 0, 60); + __invalidate(rt, 66); + __lookup_matches(rt, 67, 0, 61); + __invalidate(rt, 67); + __lookup_matches(rt, 68, 0, 62); + __invalidate(rt, 68); + __lookup_matches(rt, 69, 0, 63); + __invalidate(rt, 69); + __lookup_matches(rt, 70, 0, 64); + __invalidate(rt, 70); + __lookup_matches(rt, 71, 0, 65); + __invalidate(rt, 71); + __lookup_matches(rt, 72, 0, 66); + __invalidate(rt, 72); + __lookup_matches(rt, 73, 0, 67); + __invalidate(rt, 73); + __lookup_matches(rt, 74, 0, 68); + __invalidate(rt, 74); + __lookup_matches(rt, 75, 0, 69); + __invalidate(rt, 75); + __lookup_matches(rt, 76, 0, 70); + __invalidate(rt, 76); + __lookup_matches(rt, 77, 0, 71); + __invalidate(rt, 77); + __lookup_matches(rt, 78, 0, 72); + __invalidate(rt, 78); + __lookup_matches(rt, 79, 0, 73); + __invalidate(rt, 79); + __lookup_matches(rt, 80, 0, 74); + __invalidate(rt, 80); + __lookup_matches(rt, 81, 0, 75); + __invalidate(rt, 81); + __lookup_matches(rt, 82, 0, 76); + __invalidate(rt, 82); + __lookup_matches(rt, 83, 0, 77); + __invalidate(rt, 83); + __lookup_matches(rt, 84, 0, 78); + __invalidate(rt, 84); + __lookup_matches(rt, 85, 0, 79); + __invalidate(rt, 85); + __lookup_matches(rt, 86, 0, 80); + __invalidate(rt, 86); + __lookup_matches(rt, 87, 0, 81); + __invalidate(rt, 87); + __lookup_matches(rt, 88, 0, 82); + __invalidate(rt, 88); + __lookup_matches(rt, 89, 0, 83); + __invalidate(rt, 89); + __lookup_matches(rt, 90, 0, 84); + __invalidate(rt, 90); + __lookup_matches(rt, 91, 0, 85); + __invalidate(rt, 91); + __lookup_matches(rt, 92, 0, 86); + __invalidate(rt, 92); + __lookup_matches(rt, 93, 0, 87); + __invalidate(rt, 93); + __lookup_matches(rt, 94, 0, 88); + __invalidate(rt, 94); + __lookup_matches(rt, 95, 0, 89); + __invalidate(rt, 95); + __lookup_matches(rt, 96, 0, 90); + __lookup_matches(rt, 97, 0, 91); + __invalidate(rt, 97); + __lookup_matches(rt, 98, 0, 92); + __invalidate(rt, 98); + __lookup_matches(rt, 99, 0, 93); + __invalidate(rt, 99); + __lookup_matches(rt, 100, 0, 94); + __invalidate(rt, 100); + __lookup_matches(rt, 101, 0, 95); + __invalidate(rt, 101); + __lookup_matches(rt, 102, 0, 96); + __invalidate(rt, 102); + __lookup_matches(rt, 103, 0, 97); + __invalidate(rt, 103); + __lookup_matches(rt, 104, 0, 98); + __invalidate(rt, 104); + __lookup_matches(rt, 105, 0, 99); + __invalidate(rt, 105); + __lookup_matches(rt, 106, 0, 100); + __invalidate(rt, 106); + __lookup_matches(rt, 107, 0, 101); + __invalidate(rt, 107); + __lookup_matches(rt, 108, 0, 102); + __invalidate(rt, 108); + __lookup_matches(rt, 109, 0, 103); + __invalidate(rt, 109); + __lookup_matches(rt, 110, 0, 104); + __invalidate(rt, 110); + __lookup_matches(rt, 111, 0, 105); + __invalidate(rt, 111); + __lookup_matches(rt, 112, 0, 106); + __invalidate(rt, 112); + __lookup_matches(rt, 113, 0, 107); + __invalidate(rt, 113); + __lookup_matches(rt, 114, 0, 108); + __invalidate(rt, 114); + __lookup_matches(rt, 115, 0, 109); + __invalidate(rt, 115); + __lookup_matches(rt, 116, 0, 110); + __invalidate(rt, 116); + __lookup_matches(rt, 117, 0, 111); + __invalidate(rt, 117); + __lookup_matches(rt, 118, 0, 112); + __invalidate(rt, 118); + __lookup_matches(rt, 119, 0, 113); + __invalidate(rt, 119); + __lookup_matches(rt, 120, 0, 114); + __invalidate(rt, 120); + __lookup_matches(rt, 121, 0, 115); + __invalidate(rt, 121); + __lookup_matches(rt, 122, 0, 116); + __invalidate(rt, 122); + __lookup_matches(rt, 123, 0, 117); + __invalidate(rt, 123); + __lookup_matches(rt, 124, 0, 118); + __invalidate(rt, 124); + __lookup_matches(rt, 125, 0, 119); + __invalidate(rt, 125); + __lookup_matches(rt, 126, 0, 120); + __invalidate(rt, 126); + __lookup_matches(rt, 127, 0, 121); + __invalidate(rt, 127); + __lookup_matches(rt, 128, 0, 122); + __invalidate(rt, 128); + __lookup_matches(rt, 129, 0, 123); + __invalidate(rt, 129); + __lookup_matches(rt, 130, 0, 124); + __invalidate(rt, 130); + __lookup_matches(rt, 131, 0, 125); + __invalidate(rt, 131); + __lookup_matches(rt, 132, 0, 126); + __invalidate(rt, 132); + __lookup_matches(rt, 133, 0, 127); + __invalidate(rt, 133); + __lookup_matches(rt, 134, 0, 128); + __invalidate(rt, 134); + __lookup_matches(rt, 135, 0, 129); + __invalidate(rt, 135); + __lookup_matches(rt, 136, 0, 130); + __invalidate(rt, 136); + __lookup_matches(rt, 137, 0, 131); + __invalidate(rt, 137); + __lookup_matches(rt, 138, 0, 132); + __invalidate(rt, 138); + __lookup_matches(rt, 139, 0, 133); + __invalidate(rt, 139); + __lookup_matches(rt, 140, 0, 134); + __invalidate(rt, 140); + __lookup_matches(rt, 141, 0, 135); + __invalidate(rt, 141); + __lookup_matches(rt, 142, 0, 136); + __invalidate(rt, 142); + __lookup_matches(rt, 143, 0, 137); + __invalidate(rt, 143); + __lookup_matches(rt, 144, 0, 138); + __invalidate(rt, 144); + __lookup_matches(rt, 145, 0, 139); + __invalidate(rt, 145); + __lookup_matches(rt, 146, 0, 140); + __invalidate(rt, 146); + __lookup_matches(rt, 147, 0, 141); + __invalidate(rt, 147); + __lookup_matches(rt, 148, 0, 142); + __invalidate(rt, 148); + __lookup_matches(rt, 149, 0, 143); + __invalidate(rt, 149); + __lookup_matches(rt, 150, 0, 144); + __invalidate(rt, 150); + __lookup_matches(rt, 151, 0, 145); + __invalidate(rt, 151); + __lookup_matches(rt, 152, 0, 146); + __invalidate(rt, 152); + __lookup_matches(rt, 153, 0, 147); + __invalidate(rt, 153); + __lookup_matches(rt, 154, 0, 148); + __invalidate(rt, 154); + __lookup_matches(rt, 155, 0, 149); + __invalidate(rt, 155); + __lookup_matches(rt, 156, 0, 150); + __invalidate(rt, 156); + __lookup_matches(rt, 157, 0, 151); + __invalidate(rt, 157); + __lookup_matches(rt, 158, 0, 152); + __invalidate(rt, 158); + __lookup_matches(rt, 159, 0, 153); + __invalidate(rt, 159); + __lookup_matches(rt, 160, 0, 154); + __invalidate(rt, 160); + __lookup_matches(rt, 161, 0, 155); + __invalidate(rt, 161); + __lookup_matches(rt, 162, 0, 156); + __invalidate(rt, 162); + __lookup_matches(rt, 163, 0, 157); + __lookup_matches(rt, 164, 0, 158); + __invalidate(rt, 164); + __lookup_matches(rt, 165, 0, 159); + __invalidate(rt, 165); + __lookup_matches(rt, 166, 0, 160); + __invalidate(rt, 166); + __lookup_matches(rt, 167, 0, 161); + __invalidate(rt, 167); + __lookup_matches(rt, 168, 0, 162); + __invalidate(rt, 168); + __lookup_matches(rt, 169, 0, 163); + __invalidate(rt, 169); + __lookup_matches(rt, 170, 0, 164); + __invalidate(rt, 170); + __lookup_matches(rt, 171, 0, 165); + __invalidate(rt, 171); + __lookup_matches(rt, 172, 0, 166); + __invalidate(rt, 172); + __lookup_matches(rt, 173, 0, 167); + __invalidate(rt, 173); + __lookup_matches(rt, 174, 0, 168); + __invalidate(rt, 174); + __lookup_matches(rt, 175, 0, 169); + __invalidate(rt, 175); + __lookup_matches(rt, 176, 0, 170); + __invalidate(rt, 176); + __lookup_matches(rt, 177, 0, 171); + __invalidate(rt, 177); + __lookup_matches(rt, 178, 0, 172); + __invalidate(rt, 178); + __lookup_matches(rt, 179, 0, 173); + __invalidate(rt, 179); + __lookup_matches(rt, 180, 0, 174); + __invalidate(rt, 180); + __lookup_matches(rt, 181, 0, 175); + __invalidate(rt, 181); + __lookup_matches(rt, 182, 0, 176); + __invalidate(rt, 182); + __lookup_matches(rt, 183, 0, 177); + __invalidate(rt, 183); + __lookup_matches(rt, 184, 0, 178); + __invalidate(rt, 184); + __lookup_matches(rt, 185, 0, 179); + __invalidate(rt, 185); + __lookup_matches(rt, 186, 0, 180); + __invalidate(rt, 186); + __lookup_matches(rt, 187, 0, 181); + __invalidate(rt, 187); + __lookup_matches(rt, 188, 0, 182); + __invalidate(rt, 188); + __lookup_matches(rt, 189, 0, 183); + __invalidate(rt, 189); + __lookup_matches(rt, 190, 0, 184); + __invalidate(rt, 190); + __lookup_matches(rt, 191, 0, 185); + __invalidate(rt, 191); + __lookup_matches(rt, 192, 0, 186); + __invalidate(rt, 192); + __lookup_matches(rt, 193, 0, 187); + __invalidate(rt, 193); + __lookup_matches(rt, 194, 0, 188); + __invalidate(rt, 194); + __lookup_matches(rt, 195, 0, 189); + __invalidate(rt, 195); + __lookup_matches(rt, 196, 0, 190); + __invalidate(rt, 196); + __lookup_matches(rt, 197, 0, 191); + __invalidate(rt, 197); + __lookup_matches(rt, 198, 0, 192); + __invalidate(rt, 198); + __lookup_matches(rt, 199, 0, 193); + __invalidate(rt, 199); + __lookup_matches(rt, 200, 0, 194); + __invalidate(rt, 200); + __lookup_matches(rt, 201, 0, 195); + __invalidate(rt, 201); + __lookup_matches(rt, 202, 0, 196); + __invalidate(rt, 202); + __lookup_matches(rt, 203, 0, 197); + __invalidate(rt, 203); + __lookup_matches(rt, 204, 0, 198); + __invalidate(rt, 204); + __lookup_matches(rt, 205, 0, 199); + __invalidate(rt, 205); + __lookup_fails(rt, 6, 0); + __insert(rt, 6, 0, 208); + __lookup_fails(rt, 7, 0); + __insert(rt, 7, 0, 209); + __lookup_fails(rt, 8, 0); + __insert(rt, 8, 0, 210); + __lookup_fails(rt, 9, 0); + __insert(rt, 9, 0, 211); + __lookup_fails(rt, 10, 0); + __insert(rt, 10, 0, 212); + __lookup_fails(rt, 11, 0); + __insert(rt, 11, 0, 213); + __lookup_fails(rt, 13, 0); + __insert(rt, 13, 0, 214); + __lookup_fails(rt, 14, 0); + __insert(rt, 14, 0, 215); + __lookup_fails(rt, 15, 0); + __insert(rt, 15, 0, 216); + __lookup_fails(rt, 16, 0); + __insert(rt, 16, 0, 217); + __lookup_fails(rt, 17, 0); + __insert(rt, 17, 0, 218); + __lookup_fails(rt, 18, 0); + __insert(rt, 18, 0, 219); + __lookup_fails(rt, 19, 0); + __insert(rt, 19, 0, 220); + __lookup_fails(rt, 20, 0); + __insert(rt, 20, 0, 221); + __lookup_fails(rt, 21, 0); + __insert(rt, 21, 0, 222); + __lookup_fails(rt, 22, 0); + __insert(rt, 22, 0, 223); + __lookup_fails(rt, 23, 0); + __insert(rt, 23, 0, 224); + __lookup_fails(rt, 24, 0); + __insert(rt, 24, 0, 225); + __lookup_fails(rt, 25, 0); + __insert(rt, 25, 0, 226); + __lookup_fails(rt, 26, 0); + __insert(rt, 26, 0, 227); + __lookup_fails(rt, 27, 0); + __insert(rt, 27, 0, 228); + __lookup_fails(rt, 28, 0); + __insert(rt, 28, 0, 229); + __lookup_fails(rt, 29, 0); + __insert(rt, 29, 0, 230); + __lookup_fails(rt, 30, 0); + __insert(rt, 30, 0, 231); + __lookup_fails(rt, 31, 0); + __insert(rt, 31, 0, 232); + __lookup_fails(rt, 32, 0); + __insert(rt, 32, 0, 233); + __lookup_fails(rt, 33, 0); + __insert(rt, 33, 0, 234); + __lookup_fails(rt, 34, 0); + __insert(rt, 34, 0, 235); + __lookup_fails(rt, 35, 0); + __insert(rt, 35, 0, 236); + __lookup_fails(rt, 36, 0); + __insert(rt, 36, 0, 237); + __lookup_fails(rt, 37, 0); + __insert(rt, 37, 0, 238); + __lookup_fails(rt, 38, 0); + __insert(rt, 38, 0, 239); + __lookup_fails(rt, 39, 0); + __insert(rt, 39, 0, 240); + __lookup_fails(rt, 40, 0); + __insert(rt, 40, 0, 241); + __lookup_fails(rt, 41, 0); + __insert(rt, 41, 0, 242); + __lookup_fails(rt, 42, 0); + __insert(rt, 42, 0, 243); + __lookup_fails(rt, 43, 0); + __insert(rt, 43, 0, 244); + __lookup_fails(rt, 44, 0); + __insert(rt, 44, 0, 245); + __lookup_fails(rt, 45, 0); + __insert(rt, 45, 0, 246); + __lookup_fails(rt, 47, 0); + __insert(rt, 47, 0, 247); + __lookup_fails(rt, 48, 0); + __insert(rt, 48, 0, 248); + __lookup_fails(rt, 49, 0); + __insert(rt, 49, 0, 249); + __lookup_fails(rt, 50, 0); + __insert(rt, 50, 0, 250); + __lookup_fails(rt, 51, 0); + __insert(rt, 51, 0, 251); + __lookup_fails(rt, 52, 0); + __insert(rt, 52, 0, 252); + __lookup_fails(rt, 53, 0); + __insert(rt, 53, 0, 253); + __lookup_fails(rt, 54, 0); + __insert(rt, 54, 0, 254); + __lookup_fails(rt, 55, 0); + __insert(rt, 55, 0, 255); + __lookup_fails(rt, 56, 0); + __insert(rt, 56, 0, 256); + __lookup_fails(rt, 57, 0); + __insert(rt, 57, 0, 257); + __lookup_fails(rt, 58, 0); + __insert(rt, 58, 0, 258); + __lookup_fails(rt, 59, 0); + __insert(rt, 59, 0, 259); + __lookup_fails(rt, 60, 0); + __insert(rt, 60, 0, 260); + __lookup_fails(rt, 61, 0); + __insert(rt, 61, 0, 261); + __lookup_fails(rt, 62, 0); + __insert(rt, 62, 0, 262); + __lookup_fails(rt, 63, 0); + __insert(rt, 63, 0, 263); + __lookup_fails(rt, 64, 0); + __insert(rt, 64, 0, 264); + __lookup_fails(rt, 66, 0); + __insert(rt, 66, 0, 265); + __lookup_fails(rt, 67, 0); + __insert(rt, 67, 0, 266); + __lookup_fails(rt, 68, 0); + __insert(rt, 68, 0, 267); + __lookup_fails(rt, 69, 0); + __insert(rt, 69, 0, 268); + __lookup_fails(rt, 70, 0); + __insert(rt, 70, 0, 269); + __lookup_fails(rt, 71, 0); + __insert(rt, 71, 0, 270); + __lookup_fails(rt, 72, 0); + __insert(rt, 72, 0, 271); + __lookup_fails(rt, 73, 0); + __insert(rt, 73, 0, 272); + __lookup_fails(rt, 74, 0); + __insert(rt, 74, 0, 273); + __lookup_fails(rt, 75, 0); + __insert(rt, 75, 0, 274); + __lookup_fails(rt, 76, 0); + __insert(rt, 76, 0, 275); + __lookup_fails(rt, 77, 0); + __insert(rt, 77, 0, 276); + __lookup_fails(rt, 78, 0); + __insert(rt, 78, 0, 277); + __lookup_fails(rt, 79, 0); + __insert(rt, 79, 0, 278); + __lookup_fails(rt, 80, 0); + __insert(rt, 80, 0, 279); + __lookup_fails(rt, 81, 0); + __insert(rt, 81, 0, 280); + __lookup_fails(rt, 82, 0); + __insert(rt, 82, 0, 281); + __lookup_fails(rt, 83, 0); + __insert(rt, 83, 0, 282); + __lookup_fails(rt, 84, 0); + __insert(rt, 84, 0, 283); + __lookup_fails(rt, 85, 0); + __insert(rt, 85, 0, 284); + __lookup_fails(rt, 86, 0); + __insert(rt, 86, 0, 285); + __lookup_fails(rt, 87, 0); + __insert(rt, 87, 0, 286); + __lookup_fails(rt, 88, 0); + __insert(rt, 88, 0, 287); + __lookup_fails(rt, 89, 0); + __insert(rt, 89, 0, 288); + __lookup_fails(rt, 90, 0); + __insert(rt, 90, 0, 289); + __lookup_fails(rt, 91, 0); + __insert(rt, 91, 0, 290); + __lookup_fails(rt, 92, 0); + __insert(rt, 92, 0, 291); + __lookup_fails(rt, 93, 0); + __insert(rt, 93, 0, 292); + __lookup_fails(rt, 94, 0); + __insert(rt, 94, 0, 293); + __lookup_fails(rt, 95, 0); + __insert(rt, 95, 0, 294); + __lookup_fails(rt, 97, 0); + __insert(rt, 97, 0, 295); + __lookup_fails(rt, 98, 0); + __insert(rt, 98, 0, 296); + __lookup_fails(rt, 99, 0); + __insert(rt, 99, 0, 297); + __lookup_fails(rt, 100, 0); + __insert(rt, 100, 0, 298); + __lookup_fails(rt, 101, 0); + __insert(rt, 101, 0, 299); + __lookup_fails(rt, 102, 0); + __insert(rt, 102, 0, 300); + __lookup_fails(rt, 103, 0); + __insert(rt, 103, 0, 301); + __lookup_fails(rt, 104, 0); + __insert(rt, 104, 0, 302); + __lookup_fails(rt, 105, 0); + __insert(rt, 105, 0, 303); + __lookup_fails(rt, 106, 0); + __insert(rt, 106, 0, 304); + __lookup_fails(rt, 107, 0); + __insert(rt, 107, 0, 305); + __lookup_fails(rt, 108, 0); + __insert(rt, 108, 0, 306); + __lookup_fails(rt, 109, 0); + __insert(rt, 109, 0, 307); + __lookup_fails(rt, 110, 0); + __insert(rt, 110, 0, 308); + __lookup_fails(rt, 111, 0); + __insert(rt, 111, 0, 309); + __lookup_fails(rt, 112, 0); + __insert(rt, 112, 0, 310); + __lookup_fails(rt, 113, 0); + __insert(rt, 113, 0, 311); + __lookup_fails(rt, 114, 0); + __insert(rt, 114, 0, 312); + __lookup_fails(rt, 115, 0); + __insert(rt, 115, 0, 313); + __lookup_fails(rt, 116, 0); + __insert(rt, 116, 0, 314); + __lookup_fails(rt, 117, 0); + __insert(rt, 117, 0, 315); + __lookup_fails(rt, 118, 0); + __insert(rt, 118, 0, 316); + __lookup_fails(rt, 119, 0); + __insert(rt, 119, 0, 317); + __lookup_fails(rt, 120, 0); + __insert(rt, 120, 0, 318); + __lookup_fails(rt, 121, 0); + __insert(rt, 121, 0, 319); + __lookup_fails(rt, 122, 0); + __insert(rt, 122, 0, 320); + __lookup_fails(rt, 123, 0); + __insert(rt, 123, 0, 321); + __lookup_fails(rt, 124, 0); + __insert(rt, 124, 0, 322); + __lookup_fails(rt, 125, 0); + __insert(rt, 125, 0, 323); + __lookup_fails(rt, 126, 0); + __insert(rt, 126, 0, 324); + __lookup_fails(rt, 127, 0); + __insert(rt, 127, 0, 325); + __lookup_fails(rt, 128, 0); + __insert(rt, 128, 0, 326); + __lookup_fails(rt, 129, 0); + __insert(rt, 129, 0, 327); + __lookup_fails(rt, 130, 0); + __insert(rt, 130, 0, 328); + __lookup_fails(rt, 131, 0); + __insert(rt, 131, 0, 329); + __lookup_fails(rt, 132, 0); + __insert(rt, 132, 0, 330); + __lookup_fails(rt, 133, 0); + __insert(rt, 133, 0, 331); + __lookup_fails(rt, 134, 0); + __insert(rt, 134, 0, 332); + __lookup_fails(rt, 135, 0); + __insert(rt, 135, 0, 333); + __lookup_fails(rt, 136, 0); + __insert(rt, 136, 0, 334); + __lookup_fails(rt, 137, 0); + __insert(rt, 137, 0, 335); + __lookup_fails(rt, 138, 0); + __insert(rt, 138, 0, 336); + __lookup_fails(rt, 139, 0); + __insert(rt, 139, 0, 337); + __lookup_fails(rt, 140, 0); + __insert(rt, 140, 0, 338); + __lookup_fails(rt, 141, 0); + __insert(rt, 141, 0, 339); + __lookup_fails(rt, 142, 0); + __insert(rt, 142, 0, 340); + __lookup_fails(rt, 143, 0); + __insert(rt, 143, 0, 341); + __lookup_fails(rt, 144, 0); + __insert(rt, 144, 0, 342); + __lookup_fails(rt, 145, 0); + __insert(rt, 145, 0, 343); + __lookup_fails(rt, 146, 0); + __insert(rt, 146, 0, 344); + __lookup_fails(rt, 147, 0); + __insert(rt, 147, 0, 345); + __lookup_fails(rt, 148, 0); + __insert(rt, 148, 0, 346); + __lookup_fails(rt, 149, 0); + __insert(rt, 149, 0, 347); + __lookup_fails(rt, 150, 0); + __insert(rt, 150, 0, 348); + __lookup_fails(rt, 151, 0); + __insert(rt, 151, 0, 349); + __lookup_fails(rt, 152, 0); + __insert(rt, 152, 0, 350); + __lookup_fails(rt, 153, 0); + __insert(rt, 153, 0, 351); + __lookup_fails(rt, 154, 0); + __insert(rt, 154, 0, 352); + __lookup_fails(rt, 155, 0); + __insert(rt, 155, 0, 353); + __lookup_fails(rt, 156, 0); + __insert(rt, 156, 0, 354); + __lookup_fails(rt, 157, 0); + __insert(rt, 157, 0, 355); + __lookup_fails(rt, 158, 0); + __insert(rt, 158, 0, 356); + __lookup_fails(rt, 159, 0); + __insert(rt, 159, 0, 357); + __lookup_fails(rt, 160, 0); + __insert(rt, 160, 0, 358); + __lookup_fails(rt, 161, 0); + __insert(rt, 161, 0, 359); + __lookup_fails(rt, 162, 0); + __insert(rt, 162, 0, 360); + __lookup_fails(rt, 164, 0); + __insert(rt, 164, 0, 361); + __lookup_fails(rt, 165, 0); + __insert(rt, 165, 0, 362); + __lookup_fails(rt, 166, 0); + __insert(rt, 166, 0, 363); + __lookup_fails(rt, 167, 0); + __insert(rt, 167, 0, 364); + __lookup_fails(rt, 168, 0); + __insert(rt, 168, 0, 365); + __lookup_fails(rt, 169, 0); + __insert(rt, 169, 0, 366); + __lookup_fails(rt, 170, 0); + __insert(rt, 170, 0, 367); + __lookup_fails(rt, 171, 0); + __insert(rt, 171, 0, 368); + __lookup_fails(rt, 172, 0); + __insert(rt, 172, 0, 369); + __lookup_fails(rt, 173, 0); + __insert(rt, 173, 0, 370); + __lookup_fails(rt, 174, 0); + __insert(rt, 174, 0, 371); + __lookup_fails(rt, 175, 0); + __insert(rt, 175, 0, 372); + __lookup_fails(rt, 176, 0); + __insert(rt, 176, 0, 373); + __lookup_fails(rt, 177, 0); + __insert(rt, 177, 0, 374); + __lookup_fails(rt, 178, 0); + __insert(rt, 178, 0, 375); + __lookup_fails(rt, 179, 0); + __insert(rt, 179, 0, 376); + __lookup_fails(rt, 180, 0); + __insert(rt, 180, 0, 377); + __lookup_fails(rt, 181, 0); + __insert(rt, 181, 0, 378); + __lookup_fails(rt, 182, 0); + __insert(rt, 182, 0, 379); + __lookup_fails(rt, 183, 0); + __insert(rt, 183, 0, 380); + __lookup_fails(rt, 184, 0); + __insert(rt, 184, 0, 381); + __lookup_fails(rt, 185, 0); + __insert(rt, 185, 0, 382); + __lookup_fails(rt, 186, 0); + __insert(rt, 186, 0, 383); + __lookup_fails(rt, 187, 0); + __insert(rt, 187, 0, 384); + __lookup_fails(rt, 188, 0); + __insert(rt, 188, 0, 385); + __lookup_fails(rt, 189, 0); + __insert(rt, 189, 0, 386); + __lookup_fails(rt, 190, 0); + __insert(rt, 190, 0, 387); + __lookup_fails(rt, 191, 0); + __insert(rt, 191, 0, 388); + __lookup_fails(rt, 192, 0); + __insert(rt, 192, 0, 389); + __lookup_fails(rt, 193, 0); + __insert(rt, 193, 0, 390); + __lookup_fails(rt, 194, 0); + __insert(rt, 194, 0, 391); + __lookup_fails(rt, 195, 0); + __insert(rt, 195, 0, 392); + __lookup_fails(rt, 196, 0); + __insert(rt, 196, 0, 393); + __lookup_fails(rt, 197, 0); + __insert(rt, 197, 0, 394); + __lookup_fails(rt, 198, 0); + __insert(rt, 198, 0, 395); + __lookup_fails(rt, 199, 0); + __insert(rt, 199, 0, 396); + __lookup_fails(rt, 200, 0); + __insert(rt, 200, 0, 397); + __lookup_fails(rt, 201, 0); + __insert(rt, 201, 0, 398); + __lookup_fails(rt, 202, 0); + __insert(rt, 202, 0, 399); + __lookup_fails(rt, 203, 0); + __insert(rt, 203, 0, 400); + __lookup_fails(rt, 204, 0); + __insert(rt, 204, 0, 401); + __lookup_fails(rt, 205, 0); + __insert(rt, 205, 0, 402); + __lookup_fails(rt, 206, 0); + __insert(rt, 206, 0, 403); + __lookup_fails(rt, 207, 0); + __insert(rt, 207, 0, 404); + __lookup_fails(rt, 208, 0); + __insert(rt, 208, 0, 405); + __lookup_fails(rt, 209, 0); + __insert(rt, 209, 0, 406); + __lookup_fails(rt, 210, 0); + __insert(rt, 210, 0, 407); + __lookup_matches(rt, 6, 0, 208); + __invalidate(rt, 6); + __lookup_matches(rt, 7, 0, 209); + __invalidate(rt, 7); + __lookup_matches(rt, 8, 0, 210); + __invalidate(rt, 8); + __lookup_matches(rt, 9, 0, 211); + __invalidate(rt, 9); + __lookup_matches(rt, 10, 0, 212); + __invalidate(rt, 10); + __lookup_matches(rt, 11, 0, 213); + __invalidate(rt, 11); + __lookup_matches(rt, 13, 0, 214); + __invalidate(rt, 13); + __lookup_matches(rt, 14, 0, 215); + __invalidate(rt, 14); + __lookup_matches(rt, 15, 0, 216); + __invalidate(rt, 15); + __lookup_matches(rt, 16, 0, 217); + __invalidate(rt, 16); + __lookup_matches(rt, 17, 0, 218); + __invalidate(rt, 17); + __lookup_matches(rt, 18, 0, 219); + __invalidate(rt, 18); + __lookup_matches(rt, 19, 0, 220); + __invalidate(rt, 19); + __lookup_matches(rt, 20, 0, 221); + __invalidate(rt, 20); + __lookup_matches(rt, 21, 0, 222); + __invalidate(rt, 21); + __lookup_matches(rt, 22, 0, 223); + __invalidate(rt, 22); + __lookup_matches(rt, 23, 0, 224); + __invalidate(rt, 23); + __lookup_matches(rt, 24, 0, 225); + __invalidate(rt, 24); + __lookup_matches(rt, 25, 0, 226); + __invalidate(rt, 25); + __lookup_matches(rt, 26, 0, 227); + __invalidate(rt, 26); + __lookup_matches(rt, 27, 0, 228); + __invalidate(rt, 27); + __lookup_matches(rt, 28, 0, 229); + __invalidate(rt, 28); + __lookup_matches(rt, 29, 0, 230); + __invalidate(rt, 29); + __lookup_matches(rt, 30, 0, 231); + __invalidate(rt, 30); + __lookup_matches(rt, 31, 0, 232); + __invalidate(rt, 31); + __lookup_matches(rt, 32, 0, 233); + __invalidate(rt, 32); + __lookup_matches(rt, 33, 0, 234); + __invalidate(rt, 33); + __lookup_matches(rt, 34, 0, 235); + __invalidate(rt, 34); + __lookup_matches(rt, 35, 0, 236); + __invalidate(rt, 35); + __lookup_matches(rt, 36, 0, 237); + __invalidate(rt, 36); + __lookup_matches(rt, 37, 0, 238); + __invalidate(rt, 37); + __lookup_matches(rt, 38, 0, 239); + __invalidate(rt, 38); + __lookup_matches(rt, 39, 0, 240); + __invalidate(rt, 39); + __lookup_matches(rt, 40, 0, 241); + __invalidate(rt, 40); + __lookup_matches(rt, 41, 0, 242); + __invalidate(rt, 41); + __lookup_matches(rt, 42, 0, 243); + __invalidate(rt, 42); + __lookup_matches(rt, 43, 0, 244); + __invalidate(rt, 43); + __lookup_matches(rt, 44, 0, 245); + __invalidate(rt, 44); + __lookup_matches(rt, 45, 0, 246); + __invalidate(rt, 45); + __lookup_matches(rt, 47, 0, 247); + __invalidate(rt, 47); + __lookup_matches(rt, 48, 0, 248); + __invalidate(rt, 48); + __lookup_matches(rt, 49, 0, 249); + __invalidate(rt, 49); + __lookup_matches(rt, 50, 0, 250); + __invalidate(rt, 50); + __lookup_matches(rt, 51, 0, 251); + __invalidate(rt, 51); + __lookup_matches(rt, 52, 0, 252); + __invalidate(rt, 52); + __lookup_matches(rt, 53, 0, 253); + __invalidate(rt, 53); + __lookup_matches(rt, 54, 0, 254); + __invalidate(rt, 54); + __lookup_matches(rt, 55, 0, 255); + __invalidate(rt, 55); + __lookup_matches(rt, 56, 0, 256); + __invalidate(rt, 56); + __lookup_matches(rt, 57, 0, 257); + __invalidate(rt, 57); + __lookup_matches(rt, 58, 0, 258); + __invalidate(rt, 58); + __lookup_matches(rt, 59, 0, 259); + __invalidate(rt, 59); + __lookup_matches(rt, 60, 0, 260); + __invalidate(rt, 60); + __lookup_matches(rt, 61, 0, 261); + __invalidate(rt, 61); + __lookup_matches(rt, 62, 0, 262); + __invalidate(rt, 62); + __lookup_matches(rt, 63, 0, 263); + __invalidate(rt, 63); + __lookup_matches(rt, 64, 0, 264); + __invalidate(rt, 64); + __lookup_matches(rt, 66, 0, 265); + __invalidate(rt, 66); + __lookup_matches(rt, 67, 0, 266); + __invalidate(rt, 67); + __lookup_matches(rt, 68, 0, 267); + __invalidate(rt, 68); + __lookup_matches(rt, 69, 0, 268); + __invalidate(rt, 69); + __lookup_matches(rt, 70, 0, 269); + __invalidate(rt, 70); + __lookup_matches(rt, 71, 0, 270); + __invalidate(rt, 71); + __lookup_matches(rt, 72, 0, 271); + __invalidate(rt, 72); + __lookup_matches(rt, 73, 0, 272); + __lookup_matches(rt, 74, 0, 273); + __invalidate(rt, 74); + __lookup_matches(rt, 75, 0, 274); + __invalidate(rt, 75); + __lookup_matches(rt, 76, 0, 275); + __invalidate(rt, 76); + __lookup_matches(rt, 77, 0, 276); + __invalidate(rt, 77); + __lookup_matches(rt, 78, 0, 277); + __invalidate(rt, 78); + __lookup_matches(rt, 79, 0, 278); + __invalidate(rt, 79); + __lookup_matches(rt, 80, 0, 279); + __invalidate(rt, 80); + __lookup_matches(rt, 81, 0, 280); + __invalidate(rt, 81); + __lookup_matches(rt, 82, 0, 281); + __invalidate(rt, 82); + __lookup_matches(rt, 83, 0, 282); + __invalidate(rt, 83); + __lookup_matches(rt, 84, 0, 283); + __invalidate(rt, 84); + __lookup_matches(rt, 85, 0, 284); + __invalidate(rt, 85); + __lookup_matches(rt, 86, 0, 285); + __invalidate(rt, 86); + __lookup_matches(rt, 87, 0, 286); + __invalidate(rt, 87); + __lookup_matches(rt, 88, 0, 287); + __invalidate(rt, 88); + __lookup_matches(rt, 89, 0, 288); + __invalidate(rt, 89); + __lookup_matches(rt, 90, 0, 289); + __invalidate(rt, 90); + __lookup_matches(rt, 91, 0, 290); + __invalidate(rt, 91); + __lookup_matches(rt, 92, 0, 291); + __invalidate(rt, 92); + __lookup_matches(rt, 93, 0, 292); + __invalidate(rt, 93); + __lookup_matches(rt, 94, 0, 293); + __invalidate(rt, 94); + __lookup_matches(rt, 95, 0, 294); + __invalidate(rt, 95); + __lookup_matches(rt, 97, 0, 295); + __invalidate(rt, 97); + __lookup_matches(rt, 98, 0, 296); + __invalidate(rt, 98); + __lookup_matches(rt, 99, 0, 297); + __invalidate(rt, 99); + __lookup_matches(rt, 100, 0, 298); + __invalidate(rt, 100); + __lookup_matches(rt, 101, 0, 299); + __invalidate(rt, 101); + __lookup_matches(rt, 102, 0, 300); + __invalidate(rt, 102); + __lookup_matches(rt, 103, 0, 301); + __invalidate(rt, 103); + __lookup_matches(rt, 104, 0, 302); + __invalidate(rt, 104); + __lookup_matches(rt, 105, 0, 303); + __invalidate(rt, 105); + __lookup_matches(rt, 106, 0, 304); + __invalidate(rt, 106); + __lookup_matches(rt, 107, 0, 305); + __invalidate(rt, 107); + __lookup_matches(rt, 108, 0, 306); + __invalidate(rt, 108); + __lookup_matches(rt, 109, 0, 307); + __invalidate(rt, 109); + __lookup_matches(rt, 110, 0, 308); + __invalidate(rt, 110); + __lookup_matches(rt, 111, 0, 309); + __invalidate(rt, 111); + __lookup_matches(rt, 112, 0, 310); + __invalidate(rt, 112); + __lookup_matches(rt, 113, 0, 311); + __invalidate(rt, 113); + __lookup_matches(rt, 114, 0, 312); + __invalidate(rt, 114); + __lookup_matches(rt, 115, 0, 313); + __invalidate(rt, 115); + __lookup_matches(rt, 116, 0, 314); + __invalidate(rt, 116); + __lookup_matches(rt, 117, 0, 315); + __invalidate(rt, 117); + __lookup_matches(rt, 118, 0, 316); + __invalidate(rt, 118); + __lookup_matches(rt, 119, 0, 317); + __invalidate(rt, 119); + __lookup_matches(rt, 120, 0, 318); + __invalidate(rt, 120); + __lookup_matches(rt, 121, 0, 319); + __invalidate(rt, 121); + __lookup_matches(rt, 122, 0, 320); + __invalidate(rt, 122); + __lookup_matches(rt, 123, 0, 321); + __invalidate(rt, 123); + __lookup_matches(rt, 124, 0, 322); + __invalidate(rt, 124); + __lookup_matches(rt, 125, 0, 323); + __invalidate(rt, 125); + __lookup_matches(rt, 126, 0, 324); + __invalidate(rt, 126); + __lookup_matches(rt, 127, 0, 325); + __invalidate(rt, 127); + __lookup_matches(rt, 128, 0, 326); + __invalidate(rt, 128); + __lookup_matches(rt, 129, 0, 327); + __invalidate(rt, 129); + __lookup_matches(rt, 130, 0, 328); + __invalidate(rt, 130); + __lookup_matches(rt, 131, 0, 329); + __invalidate(rt, 131); + __lookup_matches(rt, 132, 0, 330); + __invalidate(rt, 132); + __lookup_matches(rt, 133, 0, 331); + __invalidate(rt, 133); + __lookup_matches(rt, 134, 0, 332); + __invalidate(rt, 134); + __lookup_matches(rt, 135, 0, 333); + __invalidate(rt, 135); + __lookup_matches(rt, 136, 0, 334); + __invalidate(rt, 136); + __lookup_matches(rt, 137, 0, 335); + __invalidate(rt, 137); + __lookup_matches(rt, 138, 0, 336); + __invalidate(rt, 138); + __lookup_matches(rt, 139, 0, 337); + __invalidate(rt, 139); + __lookup_matches(rt, 140, 0, 338); + __invalidate(rt, 140); + __lookup_matches(rt, 141, 0, 339); + __invalidate(rt, 141); + __lookup_matches(rt, 142, 0, 340); + __invalidate(rt, 142); + __lookup_matches(rt, 143, 0, 341); + __invalidate(rt, 143); + __lookup_matches(rt, 144, 0, 342); + __invalidate(rt, 144); + __lookup_matches(rt, 145, 0, 343); + __invalidate(rt, 145); + __lookup_matches(rt, 146, 0, 344); + __invalidate(rt, 146); + __lookup_matches(rt, 147, 0, 345); + __invalidate(rt, 147); + __lookup_matches(rt, 148, 0, 346); + __invalidate(rt, 148); + __lookup_matches(rt, 149, 0, 347); + __invalidate(rt, 149); + __lookup_matches(rt, 150, 0, 348); + __invalidate(rt, 150); + __lookup_matches(rt, 151, 0, 349); + __invalidate(rt, 151); + __lookup_matches(rt, 152, 0, 350); + __invalidate(rt, 152); + __lookup_matches(rt, 153, 0, 351); + __invalidate(rt, 153); + __lookup_matches(rt, 154, 0, 352); + __invalidate(rt, 154); + __lookup_matches(rt, 155, 0, 353); + __invalidate(rt, 155); + __lookup_matches(rt, 156, 0, 354); + __invalidate(rt, 156); + __lookup_matches(rt, 157, 0, 355); + __invalidate(rt, 157); + __lookup_matches(rt, 158, 0, 356); + __invalidate(rt, 158); + __lookup_matches(rt, 159, 0, 357); + __invalidate(rt, 159); + __lookup_matches(rt, 160, 0, 358); + __invalidate(rt, 160); + __lookup_matches(rt, 161, 0, 359); + __invalidate(rt, 161); + __lookup_matches(rt, 162, 0, 360); + __invalidate(rt, 162); + __lookup_matches(rt, 164, 0, 361); + __invalidate(rt, 164); + __lookup_matches(rt, 165, 0, 362); + __invalidate(rt, 165); + __lookup_matches(rt, 166, 0, 363); + __invalidate(rt, 166); + __lookup_matches(rt, 167, 0, 364); + __invalidate(rt, 167); + __lookup_matches(rt, 168, 0, 365); + __invalidate(rt, 168); + __lookup_matches(rt, 169, 0, 366); + __invalidate(rt, 169); + __lookup_matches(rt, 170, 0, 367); + __invalidate(rt, 170); + __lookup_matches(rt, 171, 0, 368); + __invalidate(rt, 171); + __lookup_matches(rt, 172, 0, 369); + __invalidate(rt, 172); + __lookup_matches(rt, 173, 0, 370); + __invalidate(rt, 173); + __lookup_matches(rt, 174, 0, 371); + __invalidate(rt, 174); + __lookup_matches(rt, 175, 0, 372); + __invalidate(rt, 175); + __lookup_matches(rt, 176, 0, 373); + __invalidate(rt, 176); + __lookup_matches(rt, 177, 0, 374); + __invalidate(rt, 177); + __lookup_matches(rt, 178, 0, 375); + __invalidate(rt, 178); + __lookup_matches(rt, 179, 0, 376); + __invalidate(rt, 179); + __lookup_matches(rt, 180, 0, 377); + __invalidate(rt, 180); + __lookup_matches(rt, 181, 0, 378); + __invalidate(rt, 181); + __lookup_matches(rt, 182, 0, 379); + __invalidate(rt, 182); + __lookup_matches(rt, 183, 0, 380); + __invalidate(rt, 183); + __lookup_matches(rt, 184, 0, 381); + __invalidate(rt, 184); + __lookup_matches(rt, 185, 0, 382); + __invalidate(rt, 185); + __lookup_matches(rt, 186, 0, 383); + __invalidate(rt, 186); + __lookup_matches(rt, 187, 0, 384); + __invalidate(rt, 187); + __lookup_matches(rt, 188, 0, 385); + __invalidate(rt, 188); + __lookup_matches(rt, 189, 0, 386); + __invalidate(rt, 189); + __lookup_matches(rt, 190, 0, 387); + __invalidate(rt, 190); + __lookup_matches(rt, 191, 0, 388); + __invalidate(rt, 191); + __lookup_matches(rt, 192, 0, 389); + __invalidate(rt, 192); + __lookup_matches(rt, 193, 0, 390); + __invalidate(rt, 193); + __lookup_matches(rt, 194, 0, 391); + __invalidate(rt, 194); + __lookup_matches(rt, 195, 0, 392); + __invalidate(rt, 195); + __lookup_matches(rt, 196, 0, 393); + __invalidate(rt, 196); + __lookup_matches(rt, 197, 0, 394); + __invalidate(rt, 197); + __lookup_matches(rt, 198, 0, 395); + __invalidate(rt, 198); + __lookup_matches(rt, 199, 0, 396); + __invalidate(rt, 199); + __lookup_matches(rt, 200, 0, 397); + __invalidate(rt, 200); + __lookup_matches(rt, 201, 0, 398); + __invalidate(rt, 201); + __lookup_matches(rt, 202, 0, 399); + __invalidate(rt, 202); + __lookup_matches(rt, 203, 0, 400); + __invalidate(rt, 203); + __lookup_matches(rt, 204, 0, 401); + __invalidate(rt, 204); + __lookup_matches(rt, 205, 0, 402); + __invalidate(rt, 205); + __lookup_matches(rt, 206, 0, 403); + __invalidate(rt, 206); + __lookup_matches(rt, 207, 0, 404); + __invalidate(rt, 207); + __lookup_matches(rt, 208, 0, 405); + __invalidate(rt, 208); + __lookup_matches(rt, 209, 0, 406); + __invalidate(rt, 209); + __lookup_matches(rt, 210, 0, 407); + __invalidate(rt, 210); + __lookup_fails(rt, 6, 0); + __insert(rt, 6, 0, 408); + __lookup_fails(rt, 7, 0); + __insert(rt, 7, 0, 409); + __lookup_fails(rt, 8, 0); + __insert(rt, 8, 0, 410); + __lookup_fails(rt, 9, 0); + __insert(rt, 9, 0, 411); + __lookup_fails(rt, 10, 0); + __insert(rt, 10, 0, 412); + __lookup_fails(rt, 11, 0); + __insert(rt, 11, 0, 413); + __lookup_fails(rt, 13, 0); + __insert(rt, 13, 0, 414); + __lookup_fails(rt, 14, 0); + __insert(rt, 14, 0, 415); + __lookup_fails(rt, 15, 0); + __insert(rt, 15, 0, 416); + __lookup_fails(rt, 16, 0); + __insert(rt, 16, 0, 417); + __lookup_fails(rt, 17, 0); + __insert(rt, 17, 0, 418); + __lookup_fails(rt, 18, 0); + __insert(rt, 18, 0, 419); + __lookup_fails(rt, 19, 0); + __insert(rt, 19, 0, 420); + __lookup_fails(rt, 20, 0); + __insert(rt, 20, 0, 421); + __lookup_fails(rt, 21, 0); + __insert(rt, 21, 0, 422); + __lookup_fails(rt, 22, 0); + __insert(rt, 22, 0, 423); + __lookup_fails(rt, 23, 0); + __insert(rt, 23, 0, 424); + __lookup_matches(rt, 6, 0, 408); + __invalidate(rt, 6); + __lookup_matches(rt, 7, 0, 409); + __invalidate(rt, 7); + __lookup_matches(rt, 8, 0, 410); + __invalidate(rt, 8); + __lookup_matches(rt, 9, 0, 411); + __invalidate(rt, 9); + __lookup_matches(rt, 10, 0, 412); + __invalidate(rt, 10); + __lookup_matches(rt, 11, 0, 413); + __invalidate(rt, 11); + __lookup_matches(rt, 13, 0, 414); + __invalidate(rt, 13); + __lookup_matches(rt, 14, 0, 415);

1 0

stable-2.02 - [bcache] bcache_invalidate_fd, only remove prefixes on success.
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=019fa6f8eec799ebc7a9b… Commit: 019fa6f8eec799ebc7a9b9c5b31354ff1717db12 Parent: 1e2e12f19c584c3568c255c5d89ed8aadbe61b9c Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Oct 29 15:21:11 2019 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:58:56 2020 +0000 [bcache] bcache_invalidate_fd, only remove prefixes on success. --- lib/device/bcache.c | 5 ++++- 1 file changed, 4 insertions(+), 1 deletion(-) diff --git a/lib/device/bcache.c b/lib/device/bcache.c index 72cc59929..b64707ecc 100644 --- a/lib/device/bcache.c +++ b/lib/device/bcache.c @@ -1291,7 +1291,10 @@ bool bcache_invalidate_fd(struct bcache *cache, int fd) it.success = true; it.it.visit = _invalidate_v; radix_tree_iterate(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd), &it.it); - radix_tree_remove_prefix(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd)); + + if (it.success) + radix_tree_remove_prefix(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd)); + return it.success; }

1 0

stable-2.02 - [bcache] reverse earlier patch.
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=1e2e12f19c584c3568c25… Commit: 1e2e12f19c584c3568c255c5d89ed8aadbe61b9c Parent: 6370c20d392fb6228273695cd9f1a2ae43ff1e77 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Oct 29 15:14:07 2019 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:58:43 2020 +0000 [bcache] reverse earlier patch. It broke some unit tests, for v. little benefit --- lib/device/bcache.c | 7 ++----- 1 file changed, 2 insertions(+), 5 deletions(-) diff --git a/lib/device/bcache.c b/lib/device/bcache.c index 56e3db33f..72cc59929 100644 --- a/lib/device/bcache.c +++ b/lib/device/bcache.c @@ -246,10 +246,6 @@ static bool _async_issue(struct io_engine *ioe, enum dir d, int fd, if (r < 0) { _cb_free(e->cbs, cb); - ((struct block *) context)->error = r; - log_warn("io_submit <%c> off %llu bytes %llu return %d:%s", - (d == DIR_READ) ? 'R' : 'W', (long long unsigned)offset, - (long long unsigned) nbytes, r, strerror(-r)); return false; } @@ -788,7 +784,8 @@ static void _issue_low_level(struct block *b, enum dir d) dm_list_move(&cache->io_pending, &b->list); if (!cache->engine->issue(cache->engine, d, b->fd, sb, se, b->data, b)) { - _complete_io(b, b->error); + /* FIXME: if io_submit() set an errno, return that instead of EIO? */ + _complete_io(b, -EIO); return; } }

1 0

stable-2.02 - [bcache] pass up the error from io_submit rather than using generic -EIO
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=6370c20d392fb62282736… Commit: 6370c20d392fb6228273695cd9f1a2ae43ff1e77 Parent: 056eb0a8809aee3ca888aff4fe8e22bf8884a0cc Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Oct 29 10:39:20 2019 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:58:28 2020 +0000 [bcache] pass up the error from io_submit rather than using generic -EIO Author: Heming Zhao --- lib/device/bcache.c | 7 +++++-- 1 file changed, 5 insertions(+), 2 deletions(-) diff --git a/lib/device/bcache.c b/lib/device/bcache.c index 72cc59929..56e3db33f 100644 --- a/lib/device/bcache.c +++ b/lib/device/bcache.c @@ -246,6 +246,10 @@ static bool _async_issue(struct io_engine *ioe, enum dir d, int fd, if (r < 0) { _cb_free(e->cbs, cb); + ((struct block *) context)->error = r; + log_warn("io_submit <%c> off %llu bytes %llu return %d:%s", + (d == DIR_READ) ? 'R' : 'W', (long long unsigned)offset, + (long long unsigned) nbytes, r, strerror(-r)); return false; } @@ -784,8 +788,7 @@ static void _issue_low_level(struct block *b, enum dir d) dm_list_move(&cache->io_pending, &b->list); if (!cache->engine->issue(cache->engine, d, b->fd, sb, se, b->data, b)) { - /* FIXME: if io_submit() set an errno, return that instead of EIO? */ - _complete_io(b, -EIO); + _complete_io(b, b->error); return; } }

1 0

stable-2.02 - [bcache] add unit test
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=056eb0a8809aee3ca888a… Commit: 056eb0a8809aee3ca888aff4fe8e22bf8884a0cc Parent: babde3da5530e4bbda5fb474fb5ea32a55adf16f Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Tue Oct 29 10:33:31 2019 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:58:12 2020 +0000 [bcache] add unit test abort-forces-read --- test/unit/bcache_t.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) diff --git a/test/unit/bcache_t.c b/test/unit/bcache_t.c index 668d24d77..2a8f931e4 100644 --- a/test/unit/bcache_t.c +++ b/test/unit/bcache_t.c @@ -837,6 +837,29 @@ static void test_abort_single_block(void *context) T_ASSERT(bcache_flush(cache)); } +static void test_abort_forces_reread(void *context) +{ + struct fixture *f = context; + struct mock_engine *me = f->me; + struct bcache *cache = f->cache; + struct block *b; + int fd = 17; + + _expect_read(me, fd, 0); + _expect(me, E_WAIT); + T_ASSERT(bcache_get(cache, fd, 0, GF_DIRTY, &b)); + bcache_put(b); + + bcache_abort_fd(cache, fd); + T_ASSERT(bcache_flush(cache)); + + // Check the block is re-read + _expect_read(me, fd, 0); + _expect(me, E_WAIT); + T_ASSERT(bcache_get(cache, fd, 0, 0, &b)); + bcache_put(b); +} + static void test_abort_only_specific_fd(void *context) { struct fixture *f = context; @@ -960,6 +983,7 @@ static struct test_suite *_small_tests(void) T("abort-with-no-blocks", "you can call abort, even if there are no blocks in the cache", test_abort_no_blocks); T("abort-single-block", "single block get silently discarded", test_abort_single_block); + T("abort-forces-read", "if a block has been discarded then another read is necc.", test_abort_forces_reread); T("abort-specific-fd", "abort doesn't effect other fds", test_abort_only_specific_fd); T("concurrent-reads-after-invalidate", "prefetch should still issue concurrent reads after invalidate",

1 0

stable-2.02 - [label] Use bcache_abort_fd() to ensure blocks are no longer in the cache.
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=babde3da5530e4bbda5fb… Commit: babde3da5530e4bbda5fb474fb5ea32a55adf16f Parent: 232f779db4a4cb3c9a1cc628f011f7b28fb6f158 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Mon Oct 28 15:01:47 2019 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:57:49 2020 +0000 [label] Use bcache_abort_fd() to ensure blocks are no longer in the cache. The return value from bcache_invalidate_fd() was not being checked. So I've introduced a little function, _invalidate_fd() that always calls bcache_abort_fd() if the write fails. --- lib/label/label.c | 42 +++++++++++++++++++++++++++++++----------- 1 file changed, 31 insertions(+), 11 deletions(-) diff --git a/lib/label/label.c b/lib/label/label.c index ae5c1427e..70b793441 100644 --- a/lib/label/label.c +++ b/lib/label/label.c @@ -594,6 +594,14 @@ static void _drop_bad_aliases(struct device *dev) } } +// Like bcache_invalidate, only it throws any dirty data away if the +// write fails. +static void _invalidate_fd(struct bcache *cache, int fd) +{ + if (!bcache_invalidate_fd(cache, fd)) + bcache_abort_fd(cache, fd); +} + /* * Read or reread label/metadata from selected devs. * @@ -704,7 +712,7 @@ static int _scan_list(struct cmd_context *cmd, struct dev_filter *f, * drop it from bcache. */ if (scan_failed || !is_lvm_device) { - bcache_invalidate_fd(scan_bcache, devl->dev->bcache_fd); + _invalidate_fd(scan_bcache, devl->dev->bcache_fd); _scan_dev_close(devl->dev); } @@ -881,7 +889,7 @@ int label_scan(struct cmd_context *cmd) * so this will usually not be true. */ if (_in_bcache(dev)) { - bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); } @@ -1066,7 +1074,7 @@ int label_scan_devs(struct cmd_context *cmd, struct dev_filter *f, struct dm_lis dm_list_iterate_items(devl, devs) { if (_in_bcache(devl->dev)) { - bcache_invalidate_fd(scan_bcache, devl->dev->bcache_fd); + _invalidate_fd(scan_bcache, devl->dev->bcache_fd); _scan_dev_close(devl->dev); } } @@ -1085,7 +1093,7 @@ int label_scan_devs_rw(struct cmd_context *cmd, struct dev_filter *f, struct dm_ dm_list_iterate_items(devl, devs) { if (_in_bcache(devl->dev)) { - bcache_invalidate_fd(scan_bcache, devl->dev->bcache_fd); + _invalidate_fd(scan_bcache, devl->dev->bcache_fd); _scan_dev_close(devl->dev); } @@ -1107,7 +1115,7 @@ int label_scan_devs_excl(struct dm_list *devs) dm_list_iterate_items(devl, devs) { if (_in_bcache(devl->dev)) { - bcache_invalidate_fd(scan_bcache, devl->dev->bcache_fd); + _invalidate_fd(scan_bcache, devl->dev->bcache_fd); _scan_dev_close(devl->dev); } /* @@ -1127,7 +1135,7 @@ int label_scan_devs_excl(struct dm_list *devs) void label_scan_invalidate(struct device *dev) { if (_in_bcache(dev)) { - bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); } } @@ -1208,7 +1216,7 @@ int label_read(struct device *dev) dm_list_add(&one_dev, &devl->list); if (_in_bcache(dev)) { - bcache_invalidate_fd(scan_bcache, dev->bcache_fd); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); } @@ -1314,7 +1322,7 @@ 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); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); } dev->flags |= DEV_BCACHE_EXCL; @@ -1322,6 +1330,18 @@ int label_scan_open_excl(struct device *dev) return label_scan_open(dev); } +int label_scan_open_rw(struct device *dev) +{ + if (_in_bcache(dev) && !(dev->flags & DEV_BCACHE_WRITE)) { + /* FIXME: avoid tossing out bcache blocks just to replace fd. */ + log_debug("Close and reopen rw %s", dev_name(dev)); + _invalidate_fd(scan_bcache, dev->bcache_fd); + _scan_dev_close(dev); + } + dev->flags |= DEV_BCACHE_WRITE; + return label_scan_open(dev); +} + bool dev_read_bytes(struct device *dev, uint64_t start, size_t len, void *data) { if (!scan_bcache) { @@ -1363,7 +1383,7 @@ bool dev_write_bytes(struct device *dev, uint64_t start, size_t len, void *data) if (_in_bcache(dev) && !(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); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); dev->flags |= DEV_BCACHE_WRITE; @@ -1411,7 +1431,7 @@ bool dev_write_zeros(struct device *dev, uint64_t start, size_t len) if (_in_bcache(dev) && !(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); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); dev->flags |= DEV_BCACHE_WRITE; @@ -1462,7 +1482,7 @@ bool dev_set_bytes(struct device *dev, uint64_t start, size_t len, uint8_t val) if (_in_bcache(dev) && !(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); + _invalidate_fd(scan_bcache, dev->bcache_fd); _scan_dev_close(dev); dev->flags |= DEV_BCACHE_WRITE;

1 0

stable-2.02 - [bcache] add bcache_abort()
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=232f779db4a4cb3c9a1cc… Commit: 232f779db4a4cb3c9a1cc628f011f7b28fb6f158 Parent: b6e6ea2d65785f03f3cee7938be635bcb8ad4944 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Mon Oct 28 14:29:47 2019 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:53:17 2020 +0000 [bcache] add bcache_abort() This gives us a way to cope with write failures. --- lib/device/bcache.c | 33 ++++++++++++++++++++++++++ lib/device/bcache.h | 7 ++++++ test/unit/bcache_t.c | 67 +++++++++++++++++++++++++++++++++++++++++++++++++++- 3 files changed, 106 insertions(+), 1 deletion(-) diff --git a/lib/device/bcache.c b/lib/device/bcache.c index 9f67a274e..72cc59929 100644 --- a/lib/device/bcache.c +++ b/lib/device/bcache.c @@ -1297,6 +1297,39 @@ bool bcache_invalidate_fd(struct bcache *cache, int fd) //---------------------------------------------------------------- +static bool _abort_v(struct radix_tree_iterator *it, + uint8_t *kb, uint8_t *ke, union radix_value v) +{ + struct block *b = v.ptr; + + if (b->ref_count) { + log_fatal("bcache_abort: block (%d, %llu) still held", + b->fd, (unsigned long long) b->index); + return true; + } + + _unlink_block(b); + _free_block(b); + + // We can't remove the block from the radix tree yet because + // we're in the middle of an iteration. + return true; +} + +void bcache_abort_fd(struct bcache *cache, int fd) +{ + union key k; + struct radix_tree_iterator it; + + k.parts.fd = fd; + + it.visit = _abort_v; + radix_tree_iterate(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd), &it); + radix_tree_remove_prefix(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd)); +} + +//---------------------------------------------------------------- + void bcache_set_last_byte(struct bcache *cache, int fd, uint64_t offset, int sector_size) { _last_byte_fd = fd; diff --git a/lib/device/bcache.h b/lib/device/bcache.h index 790d0fec3..f9067f70c 100644 --- a/lib/device/bcache.h +++ b/lib/device/bcache.h @@ -144,6 +144,13 @@ bool bcache_invalidate(struct bcache *cache, int fd, block_address index); */ bool bcache_invalidate_fd(struct bcache *cache, int fd); +/* + * Call this function if flush, or invalidate fail and you do not + * wish to retry the writes. This will throw away any dirty data + * not written. If any blocks for fd are held, then it will call + * abort(). + */ +void bcache_abort_fd(struct bcache *cache, int fd); //---------------------------------------------------------------- // The next four functions are utilities written in terms of the above api. diff --git a/test/unit/bcache_t.c b/test/unit/bcache_t.c index 92c2d57d4..668d24d77 100644 --- a/test/unit/bcache_t.c +++ b/test/unit/bcache_t.c @@ -793,7 +793,6 @@ static void test_invalidate_after_write_error(void *context) static void test_invalidate_held_block(void *context) { - struct fixture *f = context; struct mock_engine *me = f->me; struct bcache *cache = f->cache; @@ -809,6 +808,67 @@ static void test_invalidate_held_block(void *context) bcache_put(b); } +//---------------------------------------------------------------- +// abort tests + +static void test_abort_no_blocks(void *context) +{ + struct fixture *f = context; + struct bcache *cache = f->cache; + int fd = 17; + + // We have no expectations + bcache_abort_fd(cache, fd); +} + +static void test_abort_single_block(void *context) +{ + struct fixture *f = context; + struct bcache *cache = f->cache; + struct block *b; + int fd = 17; + + T_ASSERT(bcache_get(cache, fd, 0, GF_ZERO, &b)); + bcache_put(b); + + bcache_abort_fd(cache, fd); + + // no write should be issued + T_ASSERT(bcache_flush(cache)); +} + +static void test_abort_only_specific_fd(void *context) +{ + struct fixture *f = context; + struct mock_engine *me = f->me; + struct bcache *cache = f->cache; + struct block *b; + int fd1 = 17, fd2 = 18; + + T_ASSERT(bcache_get(cache, fd1, 0, GF_ZERO, &b)); + bcache_put(b); + + T_ASSERT(bcache_get(cache, fd1, 1, GF_ZERO, &b)); + bcache_put(b); + + T_ASSERT(bcache_get(cache, fd2, 0, GF_ZERO, &b)); + bcache_put(b); + + T_ASSERT(bcache_get(cache, fd2, 1, GF_ZERO, &b)); + bcache_put(b); + + bcache_abort_fd(cache, fd2); + + // writes for fd1 should still be issued + _expect_write(me, fd1, 0); + _expect_write(me, fd1, 1); + + _expect(me, E_WAIT); + _expect(me, E_WAIT); + + T_ASSERT(bcache_flush(cache)); +} + //---------------------------------------------------------------- // Chasing a bug reported by dct @@ -897,6 +957,11 @@ static struct test_suite *_small_tests(void) T("invalidate-read-error", "invalidate a block that errored", test_invalidate_after_read_error); T("invalidate-write-error", "invalidate a block that errored", test_invalidate_after_write_error); T("invalidate-fails-in-held", "invalidating a held block fails", test_invalidate_held_block); + + T("abort-with-no-blocks", "you can call abort, even if there are no blocks in the cache", test_abort_no_blocks); + T("abort-single-block", "single block get silently discarded", test_abort_single_block); + T("abort-specific-fd", "abort doesn't effect other fds", test_abort_only_specific_fd); + T("concurrent-reads-after-invalidate", "prefetch should still issue concurrent reads after invalidate", test_concurrent_reads_after_invalidate);

1 0

stable-2.02 - [bcache] Bring bcache into sync with master branch
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=b6e6ea2d65785f03f3cee… Commit: b6e6ea2d65785f03f3cee7938be635bcb8ad4944 Parent: e55210302787d063d3037835316ca06d5cd63bd5 Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Jan 16 14:20:35 2020 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:20:35 2020 +0000 [bcache] Bring bcache into sync with master branch --- lib/device/bcache.c | 350 ++++++++++++++++++--------------------------- lib/device/bcache.h | 1 - test/unit/bcache_t.c | 7 +- test/unit/bcache_utils_t.c | 3 +- test/unit/unit-test.sh | 2 - 5 files changed, 143 insertions(+), 220 deletions(-) diff --git a/lib/device/bcache.c b/lib/device/bcache.c index d487ca2a7..9f67a274e 100644 --- a/lib/device/bcache.c +++ b/lib/device/bcache.c @@ -12,9 +12,9 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ -#define _GNU_SOURCE - #include "bcache.h" + +#include "base/data-struct/radix-tree.h" #include "lvm-logging.h" #include "log.h" @@ -67,14 +67,14 @@ struct cb_set { static struct cb_set *_cb_set_create(unsigned nr) { int i; - struct cb_set *cbs = dm_malloc(sizeof(*cbs)); + struct cb_set *cbs = malloc(sizeof(*cbs)); if (!cbs) return NULL; - cbs->vec = dm_malloc(nr * sizeof(*cbs->vec)); + cbs->vec = malloc(nr * sizeof(*cbs->vec)); if (!cbs->vec) { - dm_free(cbs); + free(cbs); return NULL; } @@ -97,8 +97,8 @@ static void _cb_set_destroy(struct cb_set *cbs) return; } - dm_free(cbs->vec); - dm_free(cbs); + free(cbs->vec); + free(cbs); } static struct control_block *_cb_alloc(struct cb_set *cbs, void *context) @@ -152,7 +152,7 @@ static void _async_destroy(struct io_engine *ioe) if (r) log_sys_warn("io_destroy"); - dm_free(e); + free(e); } static int _last_byte_fd; @@ -169,7 +169,6 @@ static bool _async_issue(struct io_engine *ioe, enum dir d, int fd, sector_t offset; sector_t nbytes; sector_t limit_nbytes; - sector_t orig_nbytes; sector_t extra_nbytes = 0; if (((uintptr_t) data) & e->page_mask) { @@ -192,41 +191,11 @@ static bool _async_issue(struct io_engine *ioe, enum dir d, int fd, return false; } - /* - * If the bcache block offset+len goes beyond where lvm is - * intending to write, then reduce the len being written - * (which is the bcache block size) so we don't write past - * the limit set by lvm. If after applying the limit, the - * resulting size is not a multiple of the sector size (512 - * or 4096) then extend the reduced size to be a multiple of - * the sector size (we don't want to write partial sectors.) - */ if (offset + nbytes > _last_byte_offset) { limit_nbytes = _last_byte_offset - offset; - - if (limit_nbytes % _last_byte_sector_size) { + if (limit_nbytes % _last_byte_sector_size) extra_nbytes = _last_byte_sector_size - (limit_nbytes % _last_byte_sector_size); - /* - * adding extra_nbytes to the reduced nbytes (limit_nbytes) - * should make the final write size a multiple of the - * sector size. This should never result in a final size - * larger than the bcache block size (as long as the bcache - * block size is a multiple of the sector size). - */ - if (limit_nbytes + extra_nbytes > nbytes) { - log_warn("Skip extending write at %llu len %llu limit %llu extra %llu sector_size %llu", - (unsigned long long)offset, - (unsigned long long)nbytes, - (unsigned long long)limit_nbytes, - (unsigned long long)extra_nbytes, - (unsigned long long)_last_byte_sector_size); - extra_nbytes = 0; - } - } - - orig_nbytes = nbytes; - if (extra_nbytes) { log_debug("Limit write at %llu len %llu to len %llu rounded to %llu", (unsigned long long)offset, @@ -241,22 +210,6 @@ static bool _async_issue(struct io_engine *ioe, enum dir d, int fd, (unsigned long long)limit_nbytes); nbytes = limit_nbytes; } - - /* - * This shouldn't happen, the reduced+extended - * nbytes value should never be larger than the - * bcache block size. - */ - if (nbytes > orig_nbytes) { - log_error("Invalid adjusted write at %llu len %llu adjusted %llu limit %llu extra %llu sector_size %llu", - (unsigned long long)offset, - (unsigned long long)orig_nbytes, - (unsigned long long)nbytes, - (unsigned long long)limit_nbytes, - (unsigned long long)extra_nbytes, - (unsigned long long)_last_byte_sector_size); - return false; - } } } @@ -361,7 +314,7 @@ static unsigned _async_max_io(struct io_engine *e) struct io_engine *create_async_io_engine(void) { int r; - struct async_engine *e = dm_malloc(sizeof(*e)); + struct async_engine *e = malloc(sizeof(*e)); if (!e) return NULL; @@ -375,14 +328,14 @@ struct io_engine *create_async_io_engine(void) r = io_setup(MAX_IO, &e->aio_context); if (r < 0) { log_debug("io_setup failed %d", r); - dm_free(e); + free(e); return NULL; } e->cbs = _cb_set_create(MAX_IO); if (!e->cbs) { log_warn("couldn't create control block set"); - dm_free(e); + free(e); return NULL; } @@ -411,7 +364,7 @@ static struct sync_engine *_to_sync(struct io_engine *e) static void _sync_destroy(struct io_engine *ioe) { struct sync_engine *e = _to_sync(ioe); - dm_free(e); + free(e); } static bool _sync_issue(struct io_engine *ioe, enum dir d, int fd, @@ -430,7 +383,6 @@ static bool _sync_issue(struct io_engine *ioe, enum dir d, int fd, } where = sb * 512; - off = lseek(fd, where, SEEK_SET); if (off == (off_t) -1) { log_warn("Device seek error %d for offset %llu", errno, (unsigned long long)where); @@ -451,7 +403,6 @@ static bool _sync_issue(struct io_engine *ioe, enum dir d, int fd, uint64_t nbytes = len; sector_t limit_nbytes = 0; sector_t extra_nbytes = 0; - sector_t orig_nbytes = 0; if (offset > _last_byte_offset) { log_error("Limit write at %llu len %llu beyond last byte %llu", @@ -464,30 +415,9 @@ static bool _sync_issue(struct io_engine *ioe, enum dir d, int fd, if (offset + nbytes > _last_byte_offset) { limit_nbytes = _last_byte_offset - offset; - - if (limit_nbytes % _last_byte_sector_size) { + if (limit_nbytes % _last_byte_sector_size) extra_nbytes = _last_byte_sector_size - (limit_nbytes % _last_byte_sector_size); - /* - * adding extra_nbytes to the reduced nbytes (limit_nbytes) - * should make the final write size a multiple of the - * sector size. This should never result in a final size - * larger than the bcache block size (as long as the bcache - * block size is a multiple of the sector size). - */ - if (limit_nbytes + extra_nbytes > nbytes) { - log_warn("Skip extending write at %llu len %llu limit %llu extra %llu sector_size %llu", - (unsigned long long)offset, - (unsigned long long)nbytes, - (unsigned long long)limit_nbytes, - (unsigned long long)extra_nbytes, - (unsigned long long)_last_byte_sector_size); - extra_nbytes = 0; - } - } - - orig_nbytes = nbytes; - if (extra_nbytes) { log_debug("Limit write at %llu len %llu to len %llu rounded to %llu", (unsigned long long)offset, @@ -502,23 +432,6 @@ static bool _sync_issue(struct io_engine *ioe, enum dir d, int fd, (unsigned long long)limit_nbytes); nbytes = limit_nbytes; } - - /* - * This shouldn't happen, the reduced+extended - * nbytes value should never be larger than the - * bcache block size. - */ - if (nbytes > orig_nbytes) { - log_error("Invalid adjusted write at %llu len %llu adjusted %llu limit %llu extra %llu sector_size %llu", - (unsigned long long)offset, - (unsigned long long)orig_nbytes, - (unsigned long long)nbytes, - (unsigned long long)limit_nbytes, - (unsigned long long)extra_nbytes, - (unsigned long long)_last_byte_sector_size); - free(io); - return false; - } } where = offset; @@ -580,7 +493,7 @@ static bool _sync_wait(struct io_engine *ioe, io_complete_fn fn) dm_list_iterate_items_safe(io, tmp, &e->complete) { fn(io->context, 0); dm_list_del(&io->list); - dm_free(io); + free(io); } return true; @@ -593,7 +506,7 @@ static unsigned _sync_max_io(struct io_engine *e) struct io_engine *create_sync_io_engine(void) { - struct sync_engine *e = dm_malloc(sizeof(*e)); + struct sync_engine *e = malloc(sizeof(*e)); if (!e) return NULL; @@ -673,12 +586,7 @@ struct bcache { struct dm_list clean; struct dm_list io_pending; - /* - * Hash table. - */ - unsigned nr_buckets; - unsigned hash_mask; - struct dm_list *buckets; + struct radix_tree *rtree; /* * Statistics @@ -693,75 +601,50 @@ struct bcache { //---------------------------------------------------------------- -/* 2^63 + 2^61 - 2^57 + 2^54 - 2^51 - 2^18 + 1 */ -#define GOLDEN_RATIO_PRIME_64 0x9e37fffffffc0001ULL +struct key_parts { + uint32_t fd; + uint64_t b; +} __attribute__ ((packed)); -static unsigned _hash(struct bcache *cache, int fd, uint64_t i) -{ - uint64_t h = (i << 10) & fd; - h *= GOLDEN_RATIO_PRIME_64; - return h & cache->hash_mask; -} +union key { + struct key_parts parts; + uint8_t bytes[12]; +}; -static struct block *_hash_lookup(struct bcache *cache, int fd, uint64_t i) +static struct block *_block_lookup(struct bcache *cache, int fd, uint64_t i) { - struct block *b; - unsigned h = _hash(cache, fd, i); - - dm_list_iterate_items_gen (b, cache->buckets + h, hash) - if (b->fd == fd && b->index == i) - return b; + union key k; + union radix_value v; - return NULL; -} + k.parts.fd = fd; + k.parts.b = i; -static void _hash_insert(struct block *b) -{ - unsigned h = _hash(b->cache, b->fd, b->index); - dm_list_add_h(b->cache->buckets + h, &b->hash); -} + if (radix_tree_lookup(cache->rtree, k.bytes, k.bytes + sizeof(k.bytes), &v)) + return v.ptr; -static inline void _hash_remove(struct block *b) -{ - dm_list_del(&b->hash); + return NULL; } -/* - * Must return a power of 2. - */ -static unsigned _calc_nr_buckets(unsigned nr_blocks) +static bool _block_insert(struct block *b) { - unsigned r = 8; - unsigned n = nr_blocks / 4; + union key k; + union radix_value v; - if (n < 8) - n = 8; + k.parts.fd = b->fd; + k.parts.b = b->index; + v.ptr = b; - while (r < n) - r <<= 1; - - return r; + return radix_tree_insert(b->cache->rtree, k.bytes, k.bytes + sizeof(k.bytes), v); } -static bool _hash_table_init(struct bcache *cache, unsigned nr_entries) +static void _block_remove(struct block *b) { - unsigned i; + union key k; - cache->nr_buckets = _calc_nr_buckets(nr_entries); - cache->hash_mask = cache->nr_buckets - 1; - cache->buckets = dm_malloc(cache->nr_buckets * sizeof(*cache->buckets)); - if (!cache->buckets) - return false; + k.parts.fd = b->fd; + k.parts.b = b->index; - for (i = 0; i < cache->nr_buckets; i++) - dm_list_init(cache->buckets + i); - - return true; -} - -static void _hash_table_exit(struct bcache *cache) -{ - dm_free(cache->buckets); + radix_tree_remove(b->cache->rtree, k.bytes, k.bytes + sizeof(k.bytes)); } //---------------------------------------------------------------- @@ -777,7 +660,7 @@ static bool _init_free_list(struct bcache *cache, unsigned count, unsigned pgsiz if (!data) return false; - cache->raw_blocks = dm_malloc(count * sizeof(*cache->raw_blocks)); + cache->raw_blocks = malloc(count * sizeof(*cache->raw_blocks)); if (!cache->raw_blocks) { free(data); return false; @@ -797,8 +680,8 @@ static bool _init_free_list(struct bcache *cache, unsigned count, unsigned pgsiz static void _exit_free_list(struct bcache *cache) { - dm_free(cache->raw_data); - dm_free(cache->raw_blocks); + free(cache->raw_data); + free(cache->raw_blocks); } static struct block *_alloc_block(struct bcache *cache) @@ -809,6 +692,11 @@ static struct block *_alloc_block(struct bcache *cache) return dm_list_struct_base(_list_pop(&cache->free), struct block, list); } +static void _free_block(struct block *b) +{ + dm_list_add(&b->cache->free, &b->list); +} + /*---------------------------------------------------------------- * Clean/dirty list management. * Always use these methods to ensure nr_dirty_ is correct. @@ -963,7 +851,7 @@ static struct block *_find_unused_clean_block(struct bcache *cache) dm_list_iterate_items (b, &cache->clean) { if (!b->ref_count) { _unlink_block(b); - _hash_remove(b); + _block_remove(b); return b; } } @@ -993,29 +881,18 @@ static struct block *_new_block(struct bcache *cache, int fd, block_address i, b if (b) { dm_list_init(&b->list); - dm_list_init(&b->hash); b->flags = 0; b->fd = fd; b->index = i; b->ref_count = 0; b->error = 0; - _hash_insert(b); - } - -#if 0 - if (!b) { - log_error("bcache no new blocks for fd %d index %u " - "clean %u free %u dirty %u pending %u nr_data_blocks %u nr_cache_blocks %u", - fd, (uint32_t) i, - dm_list_size(&cache->clean), - dm_list_size(&cache->free), - dm_list_size(&cache->dirty), - dm_list_size(&cache->io_pending), - (uint32_t)cache->nr_data_blocks, - (uint32_t)cache->nr_cache_blocks); + if (!_block_insert(b)) { + log_error("bcache unable to insert block in radix tree (OOM?)"); + _free_block(b); + return NULL; + } } -#endif return b; } @@ -1054,7 +931,7 @@ static struct block *_lookup_or_read_block(struct bcache *cache, int fd, block_address i, unsigned flags) { - struct block *b = _hash_lookup(cache, fd, i); + struct block *b = _block_lookup(cache, fd, i); if (b) { // FIXME: this is insufficient. We need to also catch a read @@ -1125,8 +1002,8 @@ struct bcache *bcache_create(sector_t block_sectors, unsigned nr_cache_blocks, unsigned max_io = engine->max_io(engine); long pgsize = sysconf(_SC_PAGESIZE); - if ((pgsize = sysconf(_SC_PAGESIZE)) < 0) { - log_warn("bcache cannot read pagesize."); + if (pgsize < 0) { + log_warn("WARNING: _SC_PAGESIZE returns negative value."); return NULL; } @@ -1145,7 +1022,7 @@ struct bcache *bcache_create(sector_t block_sectors, unsigned nr_cache_blocks, return NULL; } - cache = dm_malloc(sizeof(*cache)); + cache = malloc(sizeof(*cache)); if (!cache) return NULL; @@ -1163,9 +1040,10 @@ struct bcache *bcache_create(sector_t block_sectors, unsigned nr_cache_blocks, dm_list_init(&cache->clean); dm_list_init(&cache->io_pending); - if (!_hash_table_init(cache, nr_cache_blocks)) { + cache->rtree = radix_tree_create(NULL, NULL); + if (!cache->rtree) { cache->engine->destroy(cache->engine); - dm_free(cache); + free(cache); return NULL; } @@ -1178,8 +1056,8 @@ struct bcache *bcache_create(sector_t block_sectors, unsigned nr_cache_blocks, if (!_init_free_list(cache, nr_cache_blocks, pgsize)) { cache->engine->destroy(cache->engine); - _hash_table_exit(cache); - dm_free(cache); + radix_tree_destroy(cache->rtree); + free(cache); return NULL; } @@ -1192,12 +1070,12 @@ void bcache_destroy(struct bcache *cache) log_warn("some blocks are still locked"); if (!bcache_flush(cache)) - log_warn("cache flushing failed."); + stack; _wait_all(cache); _exit_free_list(cache); - _hash_table_exit(cache); + radix_tree_destroy(cache->rtree); cache->engine->destroy(cache->engine); - dm_free(cache); + free(cache); } sector_t bcache_block_sectors(struct bcache *cache) @@ -1217,7 +1095,7 @@ unsigned bcache_max_prefetches(struct bcache *cache) void bcache_prefetch(struct bcache *cache, int fd, block_address i) { - struct block *b = _hash_lookup(cache, fd, i); + struct block *b = _block_lookup(cache, fd, i); if (!b) { if (cache->nr_io_pending < cache->max_io) { @@ -1230,11 +1108,13 @@ void bcache_prefetch(struct bcache *cache, int fd, block_address i) } } +//---------------------------------------------------------------- + static void _recycle_block(struct bcache *cache, struct block *b) { _unlink_block(b); - _hash_remove(b); - dm_list_add(&cache->free, &b->list); + _block_remove(b); + _free_block(b); } bool bcache_get(struct bcache *cache, int fd, block_address i, @@ -1268,6 +1148,8 @@ bool bcache_get(struct bcache *cache, int fd, block_address i, return false; } +//---------------------------------------------------------------- + static void _put_ref(struct block *b) { if (!b->ref_count) { @@ -1288,6 +1170,8 @@ void bcache_put(struct block *b) _preemptive_writeback(b->cache); } +//---------------------------------------------------------------- + bool bcache_flush(struct bcache *cache) { // Only dirty data is on the errored list, since bad read blocks get @@ -1310,6 +1194,7 @@ bool bcache_flush(struct bcache *cache) return dm_list_empty(&cache->errored); } +//---------------------------------------------------------------- /* * You can safely call this with a NULL block. */ @@ -1342,29 +1227,72 @@ static bool _invalidate_block(struct bcache *cache, struct block *b) bool bcache_invalidate(struct bcache *cache, int fd, block_address i) { - return _invalidate_block(cache, _hash_lookup(cache, fd, i)); + return _invalidate_block(cache, _block_lookup(cache, fd, i)); +} + +//---------------------------------------------------------------- + +struct invalidate_iterator { + bool success; + struct radix_tree_iterator it; +}; + +static bool _writeback_v(struct radix_tree_iterator *it, + uint8_t *kb, uint8_t *ke, union radix_value v) +{ + struct block *b = v.ptr; + + if (_test_flags(b, BF_DIRTY)) + _issue_write(b); + + return true; +} + +static bool _invalidate_v(struct radix_tree_iterator *it, + uint8_t *kb, uint8_t *ke, union radix_value v) +{ + struct block *b = v.ptr; + struct invalidate_iterator *iit = container_of(it, struct invalidate_iterator, it); + + if (b->error || _test_flags(b, BF_DIRTY)) { + log_warn("bcache_invalidate: block (%d, %llu) still dirty", + b->fd, (unsigned long long) b->index); + iit->success = false; + return true; + } + + if (b->ref_count) { + log_warn("bcache_invalidate: block (%d, %llu) still held", + b->fd, (unsigned long long) b->index); + iit->success = false; + return true; + } + + _unlink_block(b); + _free_block(b); + + // We can't remove the block from the radix tree yet because + // we're in the middle of an iteration. + return true; } -// FIXME: switch to a trie, or maybe 1 hash table per fd? To save iterating -// through the whole cache. bool bcache_invalidate_fd(struct bcache *cache, int fd) { - struct block *b, *tmp; - bool r = true; + union key k; + struct invalidate_iterator it; - // Start writing back any dirty blocks on this fd. - dm_list_iterate_items_safe (b, tmp, &cache->dirty) - if (b->fd == fd) - _issue_write(b); + k.parts.fd = fd; - _wait_all(cache); + it.it.visit = _writeback_v; + radix_tree_iterate(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd), &it.it); - // Everything should be in the clean list now. - dm_list_iterate_items_safe (b, tmp, &cache->clean) - if (b->fd == fd) - r = _invalidate_block(cache, b) && r; + _wait_all(cache); - return r; + it.success = true; + it.it.visit = _invalidate_v; + radix_tree_iterate(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd), &it.it); + radix_tree_remove_prefix(cache->rtree, k.bytes, k.bytes + sizeof(k.parts.fd)); + return it.success; } //---------------------------------------------------------------- diff --git a/lib/device/bcache.h b/lib/device/bcache.h index cb902ef36..790d0fec3 100644 --- a/lib/device/bcache.h +++ b/lib/device/bcache.h @@ -61,7 +61,6 @@ struct block { struct bcache *cache; struct dm_list list; - struct dm_list hash; unsigned flags; unsigned ref_count; diff --git a/test/unit/bcache_t.c b/test/unit/bcache_t.c index 925b95d3d..92c2d57d4 100644 --- a/test/unit/bcache_t.c +++ b/test/unit/bcache_t.c @@ -12,15 +12,14 @@ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ +#include "units.h" +#include "lib/device/bcache.h" + #include <errno.h> #include <stdio.h> #include <stdlib.h> #include <unistd.h> -#include "bcache.h" -#include "framework.h" -#include "units.h" - #define SHOW_MOCK_CALLS 0 /*---------------------------------------------------------------- diff --git a/test/unit/bcache_utils_t.c b/test/unit/bcache_utils_t.c index 9ddc19469..2e0832096 100644 --- a/test/unit/bcache_utils_t.c +++ b/test/unit/bcache_utils_t.c @@ -14,9 +14,8 @@ #define _GNU_SOURCE -#include "bcache.h" -#include "framework.h" #include "units.h" +#include "lib/device/bcache.h" #include <errno.h> #include <stdio.h> diff --git a/test/unit/unit-test.sh b/test/unit/unit-test.sh index e8332d62d..f545f1490 100644 --- a/test/unit/unit-test.sh +++ b/test/unit/unit-test.sh @@ -13,8 +13,6 @@ SKIP_WITH_LVMLOCKD=1 SKIP_WITH_LVMPOLLD=1 -SKIP_WITH_LVMETAD=1 -SKIP_WITH_CLVMD=1 SKIP_ROOT_DM_CHECK=1

1 0

stable-2.02 - [radix-tree] Bring radix-tree up to date with the master branch
by Joe Thornber 17 Jan '20

17 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=e55210302787d063d3037… Commit: e55210302787d063d3037835316ca06d5cd63bd5 Parent: 846ae8d49d74ac61c2caed84c9720aedbe9867ae Author: Joe Thornber <ejt(a)redhat.com> AuthorDate: Thu Jan 16 14:03:42 2020 +0000 Committer: Joe Thornber <ejt(a)redhat.com> CommitterDate: Thu Jan 16 14:03:42 2020 +0000 [radix-tree] Bring radix-tree up to date with the master branch --- Makefile.in | 18 +- base/data-struct/radix-tree-adaptive.c | 1297 ++++++++++++++++++++++++++++++++ base/data-struct/radix-tree-simple.c | 256 +++++++ base/data-struct/radix-tree.c | 851 +-------------------- base/data-struct/radix-tree.h | 6 + make.tmpl.in | 12 +- test/unit/radix_tree_t.c | 399 +++++++++- 7 files changed, 1980 insertions(+), 859 deletions(-) diff --git a/Makefile.in b/Makefile.in index 29d5bed3c..3c8f8c8cf 100644 --- a/Makefile.in +++ b/Makefile.in @@ -51,18 +51,20 @@ DISTCLEAN_TARGETS += config.cache config.log config.status make.tmpl include make.tmpl -libdm: include -libdaemon: include -lib: libdm libdaemon -liblvm: lib -daemons: lib libdaemon tools -tools: lib libdaemon device-mapper +include $(top_srcdir)/base/Makefile + +libdm: include $(top_builddir)/base/libbase.a +libdaemon: include $(top_builddir)/base/libbase.a +lib: libdm libdaemon $(top_builddir)/base/libbase.a +liblvm: lib $(top_builddir)/base/libbase.a +daemons: lib libdaemon tools $(top_builddir)/base/libbase.a +tools: lib libdaemon device-mapper $(top_builddir)/base/libbase.a po: tools daemons man: tools all_man: tools scripts: liblvm libdm -test: tools daemons -unit-test: lib +test: tools daemons $(top_builddir)/base/libbase.a +unit-test: lib $(top_builddir)/base/libbase.a run-unit-test: unit-test lib.device-mapper: include.device-mapper diff --git a/base/data-struct/radix-tree-adaptive.c b/base/data-struct/radix-tree-adaptive.c new file mode 100644 index 000000000..b9ba4179f --- /dev/null +++ b/base/data-struct/radix-tree-adaptive.c @@ -0,0 +1,1297 @@ +// 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 "base/memory/container_of.h" +#include "base/memory/zalloc.h" + +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> +#include <string.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 { + uint32_t nr_entries; + struct value values[256]; +}; + +struct radix_tree { + unsigned nr_entries; + struct value root; + radix_value_dtr dtr; + void *dtr_context; +}; + +//---------------------------------------------------------------- + +struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context) +{ + struct radix_tree *rt = malloc(sizeof(*rt)); + + if (rt) { + rt->nr_entries = 0; + rt->root.type = UNSET; + rt->dtr = dtr; + rt->dtr_context = dtr_context; + } + + return rt; +} + +static inline void _dtr(struct radix_tree *rt, union radix_value v) +{ + if (rt->dtr) + rt->dtr(rt->dtr_context, v); +} + +// Returns the number of values removed +static unsigned _free_node(struct radix_tree *rt, struct value v) +{ + unsigned i, nr = 0; + 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: + _dtr(rt, v.value); + nr = 1; + break; + + case VALUE_CHAIN: + vc = v.value.ptr; + _dtr(rt, vc->value); + nr = 1 + _free_node(rt, vc->child); + free(vc); + break; + + case PREFIX_CHAIN: + pc = v.value.ptr; + nr = _free_node(rt, pc->child); + free(pc); + break; + + case NODE4: + n4 = (struct node4 *) v.value.ptr; + for (i = 0; i < n4->nr_entries; i++) + nr += _free_node(rt, n4->values[i]); + free(n4); + break; + + case NODE16: + n16 = (struct node16 *) v.value.ptr; + for (i = 0; i < n16->nr_entries; i++) + nr += _free_node(rt, n16->values[i]); + free(n16); + break; + + case NODE48: + n48 = (struct node48 *) v.value.ptr; + for (i = 0; i < n48->nr_entries; i++) + nr += _free_node(rt, n48->values[i]); + free(n48); + break; + + case NODE256: + n256 = (struct node256 *) v.value.ptr; + for (i = 0; i < 256; i++) + nr += _free_node(rt, n256->values[i]); + free(n256); + break; + } + + return nr; +} + +void radix_tree_destroy(struct radix_tree *rt) +{ + _free_node(rt, rt->root); + free(rt); +} + +unsigned radix_tree_size(struct radix_tree *rt) +{ + return rt->nr_entries; +} + +static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv); + +static bool _insert_unset(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + unsigned len = ke - kb; + + if (!len) { + // value + v->type = VALUE; + v->value = rv; + rt->nr_entries++; + } 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; + rt->nr_entries++; + } + + return true; +} + +static bool _insert_value(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + unsigned len = ke - kb; + + 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(rt, &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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct value_chain *vc = v->value.ptr; + return _insert(rt, &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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct prefix_chain *pc = v->value.ptr; + + 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; + unsigned i, len = min(pc->len, ke - kb); + + for (i = 0; i < len; i++) + if (kb[i] != pc->prefix[i]) + break; + + if (!(pc2 = zalloc(sizeof(*pc2) + pc->len - i))) + return false; + 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(rt, &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] = 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; + } + + n4->nr_entries = 2; + + v->type = NODE4; + v->value.ptr = n4; + } + + return true; +} + +static bool _insert_node4(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node4 *n4 = v->value.ptr; + if (n4->nr_entries == 4) { + 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(rt, n16->values + 4, kb + 1, ke, rv)) { + free(n16); + return false; + } + free(n4); + v->type = NODE16; + v->value.ptr = n16; + } else { + if (!_insert(rt, 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 radix_tree *rt, 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; + /* coverity[bad_memset] intentional use of '0' */ + 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(rt, n48->values + 16, kb + 1, ke, rv)) { + free(n48); + return false; + } + + free(n16); + v->type = NODE48; + v->value.ptr = n48; + } else { + if (!_insert(rt, 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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node48 *n48 = v->value.ptr; + if (n48->nr_entries == 48) { + unsigned i; + struct node256 *n256 = zalloc(sizeof(*n256)); + if (!n256) + return false; + + n256->nr_entries = 49; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) + n256->values[i] = n48->values[n48->keys[i]]; + } + + if (!_insert(rt, n256->values + *kb, kb + 1, ke, rv)) { + free(n256); + return false; + } + + free(n48); + v->type = NODE256; + v->value.ptr = n256; + + } else { + if (!_insert(rt, 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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + struct node256 *n256 = v->value.ptr; + bool r, was_unset = n256->values[*kb].type == UNSET; + + r = _insert(rt, n256->values + *kb, kb + 1, ke, rv); + if (r && was_unset) + n256->nr_entries++; + + return r; +} + +// FIXME: the tree should not be touched if insert fails (eg, OOM) +static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) +{ + if (kb == ke) { + if (v->type == UNSET) { + v->type = VALUE; + v->value = rv; + rt->nr_entries++; + + } else if (v->type == VALUE) { + v->value = rv; + + } 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; + rt->nr_entries++; + } + return true; + } + + switch (v->type) { + case UNSET: + return _insert_unset(rt, v, kb, ke, rv); + + case VALUE: + return _insert_value(rt, v, kb, ke, rv); + + case VALUE_CHAIN: + return _insert_value_chain(rt, v, kb, ke, rv); + + case PREFIX_CHAIN: + return _insert_prefix_chain(rt, v, kb, ke, rv); + + case NODE4: + return _insert_node4(rt, v, kb, ke, rv); + + case NODE16: + return _insert_node16(rt, v, kb, ke, rv); + + case NODE48: + return _insert_node48(rt, v, kb, ke, rv); + + case NODE256: + return _insert_node256(rt, 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; + if (n256->values[*kb].type != UNSET) + return _lookup_prefix(n256->values + *kb, kb + 1, ke); + break; + } + + 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); + return _insert(rt, lr.v, lr.kb, ke, rv); +} + +// Note the degrade functions also free the original node. +static void _degrade_to_n4(struct node16 *n16, struct value *result) +{ + struct node4 *n4 = zalloc(sizeof(*n4)); + + assert(n4 != NULL); + + n4->nr_entries = n16->nr_entries; + memcpy(n4->keys, n16->keys, n16->nr_entries * sizeof(*n4->keys)); + memcpy(n4->values, n16->values, n16->nr_entries * sizeof(*n4->values)); + free(n16); + + result->type = NODE4; + result->value.ptr = n4; +} + +static void _degrade_to_n16(struct node48 *n48, struct value *result) +{ + unsigned i, count = 0; + struct node16 *n16 = zalloc(sizeof(*n16)); + + assert(n16 != NULL); + + n16->nr_entries = n48->nr_entries; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) { + n16->keys[count] = i; + n16->values[count] = n48->values[n48->keys[i]]; + count++; + } + } + + free(n48); + + result->type = NODE16; + result->value.ptr = n16; +} + +static void _degrade_to_n48(struct node256 *n256, struct value *result) +{ + unsigned i, count = 0; + struct node48 *n48 = zalloc(sizeof(*n48)); + + assert(n48 != NULL); + + n48->nr_entries = n256->nr_entries; + for (i = 0; i < 256; i++) { + if (n256->values[i].type == UNSET) + n48->keys[i] = 48; + + else { + 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, size_t obj_size, unsigned count, unsigned idx) +{ + if (idx == (count - 1)) + // The simple case + return; + + memmove(((uint8_t *) array) + (obj_size * idx), + ((uint8_t *) array) + (obj_size * (idx + 1)), + obj_size * (count - idx - 1)); + + // Zero the now unused last elt (set's v.type to UNSET) + 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) +{ + bool r; + unsigned i, j; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + if (kb == ke) { + if (root->type == VALUE) { + root->type = UNSET; + _dtr(rt, root->value); + return true; + + } else if (root->type == VALUE_CHAIN) { + vc = root->value.ptr; + _dtr(rt, vc->value); + memcpy(root, &vc->child, sizeof(*root)); + free(vc); + return true; + + } else + return false; + } + + switch (root->type) { + case UNSET: + case VALUE: + // this is a value for a prefix of the key + return false; + + case VALUE_CHAIN: + vc = root->value.ptr; + r = _remove(rt, &vc->child, kb, ke); + if (r && (vc->child.type == UNSET)) { + root->type = VALUE; + root->value = vc->value; + free(vc); + } + return r; + + case PREFIX_CHAIN: + pc = root->value.ptr; + if (ke - kb < pc->len) + return false; + + for (i = 0; i < pc->len; i++) + if (kb[i] != pc->prefix[i]) + return false; + + 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; + for (i = 0; i < n4->nr_entries; i++) { + 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 (!n4->nr_entries) { + free(n4); + root->type = UNSET; + } + } + return r; + } + } + return false; + + case NODE16: + n16 = root->value.ptr; + for (i = 0; i < n16->nr_entries; i++) { + 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 (n16->nr_entries <= 4) { + _degrade_to_n4(n16, root); + } + } + return r; + } + } + return false; + + case NODE48: + n48 = root->value.ptr; + i = n48->keys[*kb]; + if (i < 48) { + 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); + } + return r; + } + return false; + + case NODE256: + n256 = root->value.ptr; + r = _remove(rt, n256->values + (*kb), kb + 1, ke); + if (r && n256->values[*kb].type == UNSET) { + n256->nr_entries--; + if (n256->nr_entries <= 48) + _degrade_to_n48(n256, root); + } + return r; + } + + return false; +} + +bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_end) +{ + if (_remove(rt, &rt->root, key_begin, key_end)) { + rt->nr_entries--; + return true; + } + + return false; +} + +//---------------------------------------------------------------- + +static bool _prefix_chain_matches(struct lookup_result *lr, uint8_t *ke) +{ + // It's possible the top node is a prefix chain, and + // the remaining key matches part of it. + if (lr->v->type == PREFIX_CHAIN) { + unsigned i, rlen = ke - lr->kb; + struct prefix_chain *pc = lr->v->value.ptr; + if (rlen < pc->len) { + for (i = 0; i < rlen; i++) + if (pc->prefix[i] != lr->kb[i]) + return false; + return true; + } + } + + return false; +} + +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; + if (n256->values[*kb].type == UNSET) + return true; // No entries + + 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; + + 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) +{ + 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; +} + +// FIXME: build up the keys too +static bool _iterate(struct value *v, struct radix_tree_iterator *it) +{ + unsigned i; + struct value_chain *vc; + struct prefix_chain *pc; + struct node4 *n4; + struct node16 *n16; + struct node48 *n48; + struct node256 *n256; + + switch (v->type) { + case UNSET: + // can't happen + break; + + case VALUE: + return it->visit(it, NULL, NULL, v->value); + + case VALUE_CHAIN: + vc = v->value.ptr; + return it->visit(it, NULL, NULL, vc->value) && _iterate(&vc->child, it); + + case PREFIX_CHAIN: + pc = v->value.ptr; + return _iterate(&pc->child, it); + + case NODE4: + n4 = (struct node4 *) v->value.ptr; + for (i = 0; i < n4->nr_entries; i++) + if (!_iterate(n4->values + i, it)) + return false; + return true; + + case NODE16: + n16 = (struct node16 *) v->value.ptr; + for (i = 0; i < n16->nr_entries; i++) + if (!_iterate(n16->values + i, it)) + return false; + return true; + + case NODE48: + n48 = (struct node48 *) v->value.ptr; + for (i = 0; i < n48->nr_entries; i++) + if (!_iterate(n48->values + i, it)) + return false; + return true; + + case NODE256: + n256 = (struct node256 *) v->value.ptr; + for (i = 0; i < 256; i++) + if (n256->values[i].type != UNSET && !_iterate(n256->values + i, it)) + return false; + return true; + } + + // can't get here + return false; +} + +void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, + struct radix_tree_iterator *it) +{ + struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); + if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) + _iterate(lr.v, it); +} + +//---------------------------------------------------------------- +// 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) +{ + uint64_t bits; + 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; + + for (i = n4->nr_entries; i < 4; i++) + if (n4->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET (n4)\n"); + 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; + + for (i = n16->nr_entries; i < 16; i++) + if (n16->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET (n16)\n"); + return false; + } + + return true; + + case NODE48: + bits = 0; + n48 = v->value.ptr; + ncount = 0; + for (i = 0; i < 256; i++) { + if (n48->keys[i] < 48) { + if (n48->keys[i] >= n48->nr_entries) { + fprintf(stderr, "referencing value past nr_entries (n48)\n"); + return false; + } + + if (bits & (1ull << n48->keys[i])) { + fprintf(stderr, "duplicate entry (n48) %u\n", (unsigned) n48->keys[i]); + return false; + } + bits = bits | (1ull << n48->keys[i]); + ncount++; + + if (!_check_nodes(n48->values + n48->keys[i], count)) + return false; + } + } + + for (i = 0; i < n48->nr_entries; i++) { + if (!(bits & (1ull << i))) { + fprintf(stderr, "not all values are referenced (n48)\n"); + 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; + } + + for (i = 0; i < n48->nr_entries; i++) + if (n48->values[i].type == UNSET) { + fprintf(stderr, "value in UNSET (n48)\n"); + return false; + } + + for (i = n48->nr_entries; i < 48; i++) + if (n48->values[i].type != UNSET) { + fprintf(stderr, "unused value is not UNSET (n48)\n"); + 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; +} + +//---------------------------------------------------------------- + +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 < n48->nr_entries; i++) { + assert(n48->values[i].type != UNSET); + _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-simple.c b/base/data-struct/radix-tree-simple.c new file mode 100644 index 000000000..e8a2fddfa --- /dev/null +++ b/base/data-struct/radix-tree-simple.c @@ -0,0 +1,256 @@ +// 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 "base/memory/container_of.h" +#include "base/memory/zalloc.h" + +#include <assert.h> +#include <stdlib.h> +#include <stdio.h> + +//---------------------------------------------------------------- +// This implementation is based around nested binary trees. Very +// simple (and hopefully correct). + +struct node { + struct node *left; + struct node *right; + + uint8_t key; + struct node *center; + + bool has_value; + union radix_value value; +}; + +struct radix_tree { + radix_value_dtr dtr; + void *dtr_context; + + struct node *root; +}; + +struct radix_tree * +radix_tree_create(radix_value_dtr dtr, void *dtr_context) +{ + struct radix_tree *rt = zalloc(sizeof(*rt)); + + if (rt) { + rt->dtr = dtr; + rt->dtr_context = dtr_context; + } + + return rt; +} + +// Returns the number of entries in the tree +static unsigned _destroy_tree(struct node *n, radix_value_dtr dtr, void *context) +{ + unsigned r; + + if (!n) + return 0; + + r = _destroy_tree(n->left, dtr, context); + r += _destroy_tree(n->right, dtr, context); + r += _destroy_tree(n->center, dtr, context); + + if (n->has_value) { + if (dtr) + dtr(context, n->value); + r++; + } + + free(n); + + return r; +} + +void radix_tree_destroy(struct radix_tree *rt) +{ + _destroy_tree(rt->root, rt->dtr, rt->dtr_context); + free(rt); +} + +static unsigned _count(struct node *n) +{ + unsigned r; + + if (!n) + return 0; + + r = _count(n->left); + r += _count(n->right); + r += _count(n->center); + + if (n->has_value) + r++; + + return r; +} + +unsigned radix_tree_size(struct radix_tree *rt) +{ + return _count(rt->root); +} + +static struct node **_lookup(struct node **pn, uint8_t *kb, uint8_t *ke) +{ + struct node *n = *pn; + + if (!n || (kb == ke)) + return pn; + + if (*kb < n->key) + return _lookup(&n->left, kb, ke); + + else if (*kb > n->key) + return _lookup(&n->right, kb, ke); + + else + return _lookup(&n->center, kb + 1, ke); +} + +static bool _insert(struct node **pn, uint8_t *kb, uint8_t *ke, union radix_value v) +{ + struct node *n = *pn; + + if (!n) { + n = zalloc(sizeof(*n)); + if (!n) + return false; + + n->key = *kb; + *pn = n; + } + + if (kb == ke) { + n->has_value = true; + n->value = v; + return true; + } + + if (*kb < n->key) + return _insert(&n->left, kb, ke, v); + + else if (*kb > n->key) + return _insert(&n->right, kb, ke, v); + + else + return _insert(&n->center, kb + 1, ke, v); +} + +bool radix_tree_insert(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value v) +{ + return _insert(&rt->root, kb, ke, v); +} + +bool radix_tree_remove(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) +{ + struct node **pn = _lookup(&rt->root, kb, ke); + struct node *n = *pn; + + if (!n || !n->has_value) + return false; + + else { + if (rt->dtr) + rt->dtr(rt->dtr_context, n->value); + + if (n->left || n->center || n->right) { + n->has_value = false; + return true; + + } else { + // FIXME: delete parent if this was the last entry + free(n); + *pn = NULL; + } + + return true; + } +} + +unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) +{ + struct node **pn; + unsigned count; + + pn = _lookup(&rt->root, kb, ke); + + if (*pn) { + count = _destroy_tree(*pn, rt->dtr, rt->dtr_context); + *pn = NULL; + } + + return count; +} + +bool +radix_tree_lookup(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, union radix_value *result) +{ + struct node **pn = _lookup(&rt->root, kb, ke); + struct node *n = *pn; + + if (n && n->has_value) { + *result = n->value; + return true; + } else + return false; +} + +static void _iterate(struct node *n, struct radix_tree_iterator *it) +{ + if (!n) + return; + + _iterate(n->left, it); + + if (n->has_value) + // FIXME: fill out the key + it->visit(it, NULL, NULL, n->value); + + _iterate(n->center, it); + _iterate(n->right, it); +} + +void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, + struct radix_tree_iterator *it) +{ + if (kb == ke) + _iterate(rt->root, it); + + else { + struct node **pn = _lookup(&rt->root, kb, ke); + struct node *n = *pn; + + if (n) { + if (n->has_value) + it->visit(it, NULL, NULL, n->value); + _iterate(n->center, it); + } + } +} + +bool radix_tree_is_well_formed(struct radix_tree *rt) +{ + return true; +} + +void radix_tree_dump(struct radix_tree *rt, FILE *out) +{ +} + +//---------------------------------------------------------------- + diff --git a/base/data-struct/radix-tree.c b/base/data-struct/radix-tree.c index 222b35047..52a1a0540 100644 --- a/base/data-struct/radix-tree.c +++ b/base/data-struct/radix-tree.c @@ -10,853 +10,12 @@ // 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 "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 { - uint32_t nr_entries; - struct value values[256]; -}; - -struct radix_tree { - unsigned nr_entries; - struct value root; - radix_value_dtr dtr; - void *dtr_context; -}; - -//---------------------------------------------------------------- - -struct radix_tree *radix_tree_create(radix_value_dtr dtr, void *dtr_context) -{ - struct radix_tree *rt = malloc(sizeof(*rt)); - - if (rt) { - rt->nr_entries = 0; - rt->root.type = UNSET; - rt->dtr = dtr; - rt->dtr_context = dtr_context; - } - - return rt; -} - -static inline void _dtr(struct radix_tree *rt, union radix_value v) -{ - if (rt->dtr) - rt->dtr(rt->dtr_context, v); -} - -// Returns the number of values removed -static unsigned _free_node(struct radix_tree *rt, struct value v) -{ - unsigned i, nr = 0; - 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: - _dtr(rt, v.value); - nr = 1; - break; - - case VALUE_CHAIN: - vc = v.value.ptr; - _dtr(rt, vc->value); - nr = 1 + _free_node(rt, vc->child); - free(vc); - break; - - case PREFIX_CHAIN: - pc = v.value.ptr; - nr = _free_node(rt, pc->child); - free(pc); - break; - - case NODE4: - n4 = (struct node4 *) v.value.ptr; - for (i = 0; i < n4->nr_entries; i++) - nr += _free_node(rt, n4->values[i]); - free(n4); - break; - - case NODE16: - n16 = (struct node16 *) v.value.ptr; - for (i = 0; i < n16->nr_entries; i++) - nr += _free_node(rt, n16->values[i]); - free(n16); - break; - - case NODE48: - n48 = (struct node48 *) v.value.ptr; - for (i = 0; i < n48->nr_entries; i++) - nr += _free_node(rt, n48->values[i]); - free(n48); - break; - - case NODE256: - n256 = (struct node256 *) v.value.ptr; - for (i = 0; i < 256; i++) - nr += _free_node(rt, n256->values[i]); - free(n256); - break; - } - - return nr; -} - -void radix_tree_destroy(struct radix_tree *rt) -{ - _free_node(rt, rt->root); - free(rt); -} - -unsigned radix_tree_size(struct radix_tree *rt) -{ - return rt->nr_entries; -} - -static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv); - -static bool _insert_unset(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - unsigned len = ke - kb; - - if (!len) { - // value - v->type = VALUE; - v->value = rv; - rt->nr_entries++; - } 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; - rt->nr_entries++; - } - - return true; -} - -static bool _insert_value(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - unsigned len = ke - kb; - - 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(rt, &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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct value_chain *vc = v->value.ptr; - return _insert(rt, &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 radix_tree *rt, 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(rt, &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(rt, 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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct node4 *n4 = v->value.ptr; - if (n4->nr_entries == 4) { - 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(rt, 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(rt, 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 radix_tree *rt, 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(rt, n48->values + 16, kb + 1, ke, rv)) { - free(n48); - return false; - } - - free(n16); - v->type = NODE48; - v->value.ptr = n48; - } else { - if (!_insert(rt, 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 radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - struct node48 *n48 = v->value.ptr; - if (n48->nr_entries == 48) { - 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(rt, n256->values + *kb, kb + 1, ke, rv)) { - free(n256); - return false; - } - - free(n48); - v->type = NODE256; - v->value.ptr = n256; - - } else { - if (!_insert(rt, 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 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; - - if (was_unset) - n256->nr_entries++; - - return true; -} - -// FIXME: the tree should not be touched if insert fails (eg, OOM) -static bool _insert(struct radix_tree *rt, struct value *v, uint8_t *kb, uint8_t *ke, union radix_value rv) -{ - if (kb == ke) { - if (v->type == UNSET) { - v->type = VALUE; - v->value = rv; - rt->nr_entries++; - - } else if (v->type == VALUE) { - v->value = rv; - - } 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; - rt->nr_entries++; - } - return true; - } - - switch (v->type) { - case UNSET: - return _insert_unset(rt, v, kb, ke, rv); - - case VALUE: - return _insert_value(rt, v, kb, ke, rv); - - case VALUE_CHAIN: - return _insert_value_chain(rt, v, kb, ke, rv); - - case PREFIX_CHAIN: - return _insert_prefix_chain(rt, v, kb, ke, rv); - - case NODE4: - return _insert_node4(rt, v, kb, ke, rv); - - case NODE16: - return _insert_node16(rt, v, kb, ke, rv); - - case NODE48: - return _insert_node48(rt, v, kb, ke, rv); - - case NODE256: - return _insert_node256(rt, 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); - return _insert(rt, lr.v, lr.kb, ke, rv); -} - -// Note the degrade functions also free the original node. -static void _degrade_to_n4(struct node16 *n16, struct value *result) -{ - struct node4 *n4 = zalloc(sizeof(*n4)); - - n4->nr_entries = n16->nr_entries; - memcpy(n4->keys, n16->keys, n16->nr_entries * sizeof(*n4->keys)); - memcpy(n4->values, n16->values, n16->nr_entries * sizeof(*n4->values)); - free(n16); - - result->type = NODE4; - result->value.ptr = n4; -} - -static void _degrade_to_n16(struct node48 *n48, struct value *result) -{ - struct node4 *n16 = zalloc(sizeof(*n16)); - - n16->nr_entries = n48->nr_entries; - memcpy(n16->keys, n48->keys, n48->nr_entries * sizeof(*n16->keys)); - memcpy(n16->values, n48->values, n48->nr_entries * sizeof(*n16->values)); - free(n48); - - result->type = NODE16; - result->value.ptr = n16; -} - -static void _degrade_to_n48(struct node256 *n256, struct value *result) -{ - unsigned i, count = 0; - struct node4 *n48 = zalloc(sizeof(*n48)); - - n48->nr_entries = n256->nr_entries; - for (i = 0; i < 256; i++) { - if (n256->values[i].type == UNSET) - continue; - - n48->keys[count] = i; - n48->values[count] = n256->values[i]; - count++; - } - free(n256); - - result->type = NODE48; - result->value.ptr = n48; -} - -static bool _remove(struct radix_tree *rt, struct value *root, uint8_t *kb, uint8_t *ke) -{ - bool r; - 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) { - if (root->type == VALUE) { - root->type = UNSET; - _dtr(rt, root->value); - return true; - - } else if (root->type == VALUE_CHAIN) { - vc = root->value.ptr; - _dtr(rt, vc->value); - memcpy(root, &vc->child, sizeof(*root)); - free(vc); - return true; - - } else - return false; - } - - switch (root->type) { - case UNSET: - case VALUE: - // this is a value for a prefix of the key - return false; - - case VALUE_CHAIN: - vc = root->value.ptr; - r = _remove(rt, &vc->child, kb, ke); - if (r && (vc->child.type == UNSET)) { - memcpy(root, &vc->child, sizeof(*root)); - free(vc); - } - return r; - - case PREFIX_CHAIN: - pc = root->value.ptr; - if (ke - kb < pc->len) - return false; - - for (i = 0; i < pc->len; i++) - if (kb[i] != pc->prefix[i]) - return false; - - return _remove(rt, &pc->child, kb + pc->len, ke); - - case NODE4: - n4 = root->value.ptr; - for (i = 0; i < n4->nr_entries; i++) { - if (n4->keys[i] == *kb) { - r = _remove(rt, n4->values + i, kb + 1, ke); - if (r && n4->values[i].type == UNSET) { - 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) - root->type = UNSET; - } - return r; - } - } - return false; - - case NODE16: - n16 = root->value.ptr; - for (i = 0; i < n16->nr_entries; i++) { - if (n16->keys[i] == *kb) { - r = _remove(rt, n16->values + i, kb + 1, ke); - if (r && n16->values[i].type == UNSET) { - 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) - _degrade_to_n4(n16, root); - } - return r; - } - } - return false; - - case NODE48: - n48 = root->value.ptr; - i = n48->keys[*kb]; - if (i < 48) { - r = _remove(rt, n48->values + i, kb + 1, ke); - if (r && n48->values[i].type == UNSET) { - n48->keys[*kb] = 48; - n48->nr_entries--; - if (n48->nr_entries <= 16) - _degrade_to_n16(n48, root); - } - return r; - } - return false; - - case NODE256: - n256 = root->value.ptr; - r = _remove(rt, n256->values + (*kb), kb + 1, ke); - if (r && n256->values[*kb].type == UNSET) { - n256->nr_entries--; - if (n256->nr_entries <= 48) - _degrade_to_n48(n256, root); - } - return r; - } - - return false; -} - -bool radix_tree_remove(struct radix_tree *rt, uint8_t *key_begin, uint8_t *key_end) -{ - if (_remove(rt, &rt->root, key_begin, key_end)) { - rt->nr_entries--; - return true; - } - - return false; -} - -static bool _prefix_chain_matches(struct lookup_result *lr, uint8_t *ke) -{ - // It's possible the top node is a prefix chain, and - // the remaining key matches part of it. - if (lr->v->type == PREFIX_CHAIN) { - unsigned i, rlen = ke - lr->kb; - struct prefix_chain *pc = lr->v->value.ptr; - if (rlen < pc->len) { - for (i = 0; i < rlen; i++) - if (pc->prefix[i] != lr->kb[i]) - return false; - return true; - } - } - - return false; -} - -unsigned radix_tree_remove_prefix(struct radix_tree *rt, uint8_t *kb, uint8_t *ke) -{ - unsigned count = 0; - struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); - if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) { - count = _free_node(rt, *lr.v); - lr.v->type = UNSET; - } - - rt->nr_entries -= count; - return count; -} - -bool radix_tree_lookup(struct radix_tree *rt, - uint8_t *kb, uint8_t *ke, union radix_value *result) -{ - 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; -} - -// FIXME: build up the keys too -static bool _iterate(struct value *v, struct radix_tree_iterator *it) -{ - unsigned i; - struct value_chain *vc; - struct prefix_chain *pc; - struct node4 *n4; - struct node16 *n16; - struct node48 *n48; - struct node256 *n256; - - switch (v->type) { - case UNSET: - // can't happen - break; - - case VALUE: - return it->visit(it, NULL, NULL, v->value); - - case VALUE_CHAIN: - vc = v->value.ptr; - return it->visit(it, NULL, NULL, vc->value) && _iterate(&vc->child, it); - - case PREFIX_CHAIN: - pc = v->value.ptr; - return _iterate(&pc->child, it); - - case NODE4: - n4 = (struct node4 *) v->value.ptr; - for (i = 0; i < n4->nr_entries; i++) - if (!_iterate(n4->values + i, it)) - return false; - return true; - - case NODE16: - n16 = (struct node16 *) v->value.ptr; - for (i = 0; i < n16->nr_entries; i++) - if (!_iterate(n16->values + i, it)) - return false; - return true; - - case NODE48: - n48 = (struct node48 *) v->value.ptr; - for (i = 0; i < n48->nr_entries; i++) - if (!_iterate(n48->values + i, it)) - return false; - return true; - - case NODE256: - n256 = (struct node256 *) v->value.ptr; - for (i = 0; i < 256; i++) - if (n256->values[i].type != UNSET && !_iterate(n256->values + i, it)) - return false; - return true; - } - - // can't get here - return false; -} - -void radix_tree_iterate(struct radix_tree *rt, uint8_t *kb, uint8_t *ke, - struct radix_tree_iterator *it) -{ - struct lookup_result lr = _lookup_prefix(&rt->root, kb, ke); - if (lr.kb == ke || _prefix_chain_matches(&lr, ke)) - _iterate(lr.v, it); -} +#ifdef SIMPLE_RADIX_TREE +#include "base/data-struct/radix-tree-simple.c" +#else +#include "base/data-struct/radix-tree-adaptive.c" +#endif //---------------------------------------------------------------- diff --git a/base/data-struct/radix-tree.h b/base/data-struct/radix-tree.h index 1b6aee8f0..5d4d04c63 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> //---------------------------------------------------------------- @@ -53,6 +54,11 @@ 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); +void radix_tree_dump(struct radix_tree *rt, FILE *out); + //---------------------------------------------------------------- #endif diff --git a/make.tmpl.in b/make.tmpl.in index c8e4f1440..e7780e8d4 100644 --- a/make.tmpl.in +++ b/make.tmpl.in @@ -68,7 +68,15 @@ CLDFLAGS += @CLDFLAGS@ ELDFLAGS += @ELDFLAGS@ LDDEPS += @LDDEPS@ LIB_SUFFIX = @LIB_SUFFIX@ -LVMINTERNAL_LIBS = -llvm-internal $(DMEVENT_LIBS) $(DAEMON_LIBS) $(SYSTEMD_LIBS) $(UDEV_LIBS) $(DL_LIBS) $(BLKID_LIBS) +LVMINTERNAL_LIBS =\ + -llvm-internal \ + $(top_builddir)/base/libbase.a \ + $(DMEVENT_LIBS) \ + $(DAEMON_LIBS) \ + $(SYSTEMD_LIBS) \ + $(UDEV_LIBS) \ + $(DL_LIBS) \ + $(BLKID_LIBS) DL_LIBS = @DL_LIBS@ RT_LIBS = @RT_LIBS@ M_LIBS = @M_LIBS@ @@ -306,7 +314,7 @@ LIB_VERSION_DM := $(shell $(AWK) -F '.' '{printf "%s.%s",$$1,$$2}' $(top_srcdir) LIB_VERSION_APP := $(shell $(AWK) -F '[(). ]' '{printf "%s.%s",$$1,$$4}' $(top_srcdir)/VERSION) -INCLUDES += -I$(srcdir) -I$(top_builddir)/include +INCLUDES += -I$(top_srcdir) -I$(srcdir) -I$(top_builddir)/include INC_LNS = $(top_builddir)/include/.symlinks_created diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c index 7266a8a46..54bc40670 100644 --- a/test/unit/radix_tree_t.c +++ b/test/unit/radix_tree_t.c @@ -10,11 +10,10 @@ // along with this program; if not, write to the Free Software Foundation, // Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA +#include "units.h" #include "base/data-struct/radix-tree.h" #include "base/memory/container_of.h" -#include "units.h" - #include <stdio.h> #include <stdlib.h> @@ -44,6 +43,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 +62,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 +84,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 +115,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 +135,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 +155,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 +182,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 +197,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 +216,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 +238,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 +286,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 +314,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 +344,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 +361,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 +383,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 +414,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 +438,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 +458,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 +480,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 +492,323 @@ 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); +} + +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]); +} + +//---------------------------------------------------------------- + +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)); +} + +//---------------------------------------------------------------- + +static void _bcs2_step1(struct radix_tree *rt) +{ + unsigned i; + uint8_t k[12]; + union radix_value v; + + memset(k, 0, sizeof(k)); + for (i = 0x6; i < 0x69; i++) { + k[0] = i; + v.n = i; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + } + T_ASSERT(radix_tree_is_well_formed(rt)); +} + +static void _bcs2_step2(struct radix_tree *rt) +{ + unsigned i; + uint8_t k[12]; + + memset(k, 0, sizeof(k)); + for (i = 0x6; i < 0x69; i++) { + k[0] = i; + radix_tree_remove_prefix(rt, k, k + 4); + } + T_ASSERT(radix_tree_is_well_formed(rt)); +} + +static void test_bcache_scenario2(void *fixture) +{ + unsigned i; + struct radix_tree *rt = fixture; + uint8_t k[12]; + union radix_value v; + + _bcs2_step1(rt); + _bcs2_step2(rt); + + memset(k, 0, sizeof(k)); + for (i = 0; i < 50; i++) { + k[0] = 0x6; + v.n = 0x6; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + radix_tree_remove_prefix(rt, k, k + 4); + } + T_ASSERT(radix_tree_is_well_formed(rt)); + + _bcs2_step1(rt); + _bcs2_step2(rt); + _bcs2_step1(rt); + _bcs2_step2(rt); + + memset(k, 0, sizeof(k)); + for(i = 0x6; i < 0x37; i++) { + k[0] = i; + k[4] = 0xf; + k[5] = 0x1; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + k[4] = 0; + k[5] = 0; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + } + T_ASSERT(radix_tree_is_well_formed(rt)); + + memset(k, 0, sizeof(k)); + for (i = 0x38; i < 0x69; i++) { + k[0] = i - 0x32; + k[4] = 0xf; + k[5] = 1; + T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k))); + + k[0] = i; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + + k[0] = i - 0x32; + k[4] = 0; + k[5] = 0; + T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k))); + + k[0] = i; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + } + T_ASSERT(radix_tree_is_well_formed(rt)); + + memset(k, 0, sizeof(k)); + k[0] = 0x6; + radix_tree_remove_prefix(rt, k, k + 4); + T_ASSERT(radix_tree_is_well_formed(rt)); + + k[0] = 0x38; + k[4] = 0xf; + k[5] = 0x1; + T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k))); + T_ASSERT(radix_tree_is_well_formed(rt)); + + memset(k, 0, sizeof(k)); + k[0] = 0x6; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + T_ASSERT(radix_tree_is_well_formed(rt)); + + k[0] = 0x7; + radix_tree_remove_prefix(rt, k, k + 4); + T_ASSERT(radix_tree_is_well_formed(rt)); + + k[0] = 0x38; + T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k))); + T_ASSERT(radix_tree_is_well_formed(rt)); + + k[0] = 7; + T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v)); + T_ASSERT(radix_tree_is_well_formed(rt)); +} + +//---------------------------------------------------------------- + +struct key_parts { + uint32_t fd; + uint64_t b; +} __attribute__ ((packed)); + +union key { + struct key_parts parts; + uint8_t bytes[12]; +}; + +static void __lookup_matches(struct radix_tree *rt, int fd, uint64_t b, uint64_t expected) +{ + union key k; + union radix_value v; + + k.parts.fd = fd; + k.parts.b = b; + T_ASSERT(radix_tree_lookup(rt, k.bytes, k.bytes + sizeof(k.bytes), &v)); + T_ASSERT(v.n == expected); +} + +static void __lookup_fails(struct radix_tree *rt, int fd, uint64_t b) +{ + union key k; + union radix_value v; + + k.parts.fd = fd; + k.parts.b = b; + T_ASSERT(!radix_tree_lookup(rt, k.bytes, k.bytes + sizeof(k.bytes), &v)); +} + +static void __insert(struct radix_tree *rt, int fd, uint64_t b, uint64_t n) +{ + union key k; + union radix_value v; + + k.parts.fd = fd; + k.parts.b = b; + v.n = n; + T_ASSERT(radix_tree_insert(rt, k.bytes, k.bytes + sizeof(k.bytes), v)); +} + +static void __invalidate(struct radix_tree *rt, int fd) +{ + union key k; + + k.parts.fd = fd; + radix_tree_remove_prefix(rt, k.bytes, k.bytes + sizeof(k.parts.fd)); + radix_tree_is_well_formed(rt); +} + +static void test_bcache_scenario3(void *fixture) +{ + struct radix_tree *rt = fixture; + + #include "test/unit/rt_case1.c" +} + +//---------------------------------------------------------------- #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 +829,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 +839,11 @@ 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); + 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); + T("bcache-scenario-2", "A second series of keys from a bcache scenario", test_bcache_scenario2); + T("bcache-scenario-3", "A third series of keys from a bcache scenario", test_bcache_scenario3); dm_list_add(all_tests, &ts->list); }

1 0

master - add suggestion message for mirror LVs
by David Teigland 16 Jan '20

16 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=d53bfae273677975bd805… Commit: d53bfae273677975bd805bfaa3d7e7cd995aaa52 Parent: 2f6d0a6408220a1f6a96a9f39779846578d88b8c Author: Heming Zhao <heming.zhao(a)suse.com> AuthorDate: Wed Jan 15 02:44:30 2020 +0000 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Wed Jan 15 09:46:54 2020 -0600 add suggestion message for mirror LVs Currently the error messages are not clear. This very easy to guide user to execute "--removemissing --force", it is dangerous and will make the LVs to be destroied. Signed-off-by: Zhao Heming <heming.zhao(a)suse.com> --- tools/vgreduce.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/tools/vgreduce.c b/tools/vgreduce.c index b001ccb..4a4202e 100644 --- a/tools/vgreduce.c +++ b/tools/vgreduce.c @@ -67,6 +67,8 @@ static int _consolidate_vg(struct cmd_context *cmd, struct volume_group *vg) cmd->handles_missing_pvs = 1; log_error("There are still partial LVs in VG %s.", vg->name); log_error("To remove them unconditionally use: vgreduce --removemissing --force."); + log_error("To remove them unconditionally from mirror LVs use: vgreduce" + " --removemissing --mirrorsonly --force."); log_warn("WARNING: Proceeding to remove empty missing PVs."); }

1 0

master - fix corosync.conf: no interface error
by David Teigland 16 Jan '20

16 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=2f6d0a6408220a1f6a96a… Commit: 2f6d0a6408220a1f6a96a9f39779846578d88b8c Parent: 151bf52649ba7a5a6731693e5af8560f6cf1742a Author: Heming Zhao <heming.zhao(a)suse.com> AuthorDate: Wed Jan 15 02:17:47 2020 +0000 Committer: David Teigland <teigland(a)redhat.com> CommitterDate: Wed Jan 15 09:46:54 2020 -0600 fix corosync.conf: no interface error systemctl status corosync (version: 2.4.5) report error: parse error in config: No interfaces defined Signed-off-by: Zhao Heming <heming.zhao(a)suse.com> --- test/lib/test-corosync-conf | 9 +++++++++ 1 file changed, 9 insertions(+) diff --git a/test/lib/test-corosync-conf b/test/lib/test-corosync-conf index ccc958f..e04be73 100644 --- a/test/lib/test-corosync-conf +++ b/test/lib/test-corosync-conf @@ -3,6 +3,13 @@ totem { version: 2 secauth: off cluster_name: test + interface { + ingnumber: 0 + bindnetaddr: 127.0.0.1 + mcastaddr: 239.255.255.100 + mcastport: 5405 + ttl: 1 + } } nodelist { node { @@ -12,6 +19,8 @@ nodelist { } quorum { provider: corosync_votequorum + expected_votes: 1 + two_node: 0 } logging { to_syslog: yes

1 0

master - WHATS_NEW: update
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=151bf52649ba7a5a67316… Commit: 151bf52649ba7a5a6731693e5af8560f6cf1742a Parent: 30f4d0fcd497338be5eb994a9b5b1ccee993f62c Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 13 17:37:29 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:42:53 2020 +0100 WHATS_NEW: update --- WHATS_NEW | 2 ++ 1 file changed, 2 insertions(+) diff --git a/WHATS_NEW b/WHATS_NEW index b3c6102..b7aa4e9 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,5 +1,7 @@ Version 2.03.08 - ==================================== + Avoid running cache input arg validation when creating vdo pool. + Prevent raid reshaping of stacked volumes. Added VDO lvmdbusd methods for enable/disable compression & dedupe. Added VDO lvmdbusd method for converting LV to VDO pool.

1 0

master - tests: update for readahead
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=30f4d0fcd497338be5eb9… Commit: 30f4d0fcd497338be5eb994a9b5b1ccee993f62c Parent: 5ccf3e6f30479331b9b47e0165ed191fbaa38f44 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Thu Dec 12 15:54:17 2019 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:42:31 2020 +0100 tests: update for readahead --- test/shell/lvcreate-usage.sh | 14 +++++++------- test/shell/read-ahead.sh | 9 ++++----- 2 files changed, 11 insertions(+), 12 deletions(-) diff --git a/test/shell/lvcreate-usage.sh b/test/shell/lvcreate-usage.sh index b1cd515..6d46939 100644 --- a/test/shell/lvcreate-usage.sh +++ b/test/shell/lvcreate-usage.sh @@ -180,16 +180,16 @@ check lv_field $vg/$lv4 lv_read_ahead "auto" # figure RA value of a PV origin device DEVICE=$(dmsetup deps -o blkdevname "$dev1" | sed -e "s,.*:\ ($.*$),/dev/\1,") RASZ=$(( $(blockdev --getra "$DEVICE" ) / 2 )) -SZ="$RASZ.00k" -test "$RASZ" -ge 128 || SZ="128.00k" -check lv_field $vg/$lv4 lv_kernel_read_ahead "$SZ" --units k -lvcreate -L 8 -n $lv5 -i2 --stripesize 16k --readahead auto $vg +test "$RASZ" -ge 128 || RASZ="128" +check lv_field $vg/$lv4 lv_kernel_read_ahead "${RASZ}.00k" --units k +lvcreate -vvvvv -L 8 -n $lv5 -i2 --stripesize 16k --readahead auto $vg check lv_field $vg/$lv5 lv_read_ahead "auto" -check lv_field $vg/$lv5 lv_kernel_read_ahead "$SZ" --units k +# For 16k stripe we set '128k' as the is the minimum size we get when creating DM device +check lv_field $vg/$lv5 lv_kernel_read_ahead "128.00k" --units k lvcreate -L 8 -n $lv6 -i2 --stripesize 128k --readahead auto $vg check lv_field $vg/$lv6 lv_read_ahead "auto" -test "$RASZ" -ge 512 || SZ="512.00k" -check lv_field $vg/$lv6 lv_kernel_read_ahead "$SZ" --units k +# For striped device we set double of strip size unrelated to underlaying dev RA size +check lv_field $vg/$lv6 lv_kernel_read_ahead "512.00k" --units k lvremove -ff $vg # diff --git a/test/shell/read-ahead.sh b/test/shell/read-ahead.sh index 53cc572..2f061fa 100644 --- a/test/shell/read-ahead.sh +++ b/test/shell/read-ahead.sh @@ -35,12 +35,11 @@ lvremove -ff $vg #COMM "read ahead is properly inherited from underlying PV" blockdev --setra 768 "$dev1" vgscan -DEVICE=$(dmsetup deps -o blkdevname "$dev1" | sed -e "s,.*:\ ($.*$),/dev/\1,") -RASZ=$(blockdev --getra "$DEVICE") -SZ=$RASZ -test "$RASZ" -ge 768 || SZ=768 +# is there something in the system changing readahead settings behind the scene... +RASZ=$(blockdev --getra "$dev1") +test "$RASZ" -ge 768 || RASZ=768 lvcreate -n $lv -L4m $vg "$dev1" -test "$(blockdev --getra "$DM_DEV_DIR/$vg/$lv")" -eq "$SZ" +test "$(blockdev --getra "$DM_DEV_DIR/$vg/$lv")" -eq "$RASZ" lvremove -ff $vg # Check default, active/inactive values for read_ahead / kernel_read_ahead

1 0

master - vdo: avoid running initialization of cache pool vars
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=5ccf3e6f30479331b9b47… Commit: 5ccf3e6f30479331b9b47e0165ed191fbaa38f44 Parent: 7737ffb11ceba0f4220e1dfb79b8e97f20e7b8e9 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 6 15:57:08 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:42:31 2020 +0100 vdo: avoid running initialization of cache pool vars Since VDO is also pool, the old if() case missed to know about this, and executed unnecesserily initialization of cache pool variables. This was usually harmless when using 'smaller' sizes of VDO pools, but for big VDO pool size, we were reporting senseless messages about big cache chunk sizes. --- tools/lvcreate.c | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) diff --git a/tools/lvcreate.c b/tools/lvcreate.c index 4a1534c..448f125 100644 --- a/tools/lvcreate.c +++ b/tools/lvcreate.c @@ -396,13 +396,15 @@ static int _update_extents_params(struct volume_group *vg, &lp->discards, &lp->zero_new_blocks)) return_0; - } else if (!update_cache_pool_params(vg->cmd, vg->profile, vg->extent_size, - lp->segtype, lp->target_attr, - lp->extents, - &lp->pool_metadata_extents, - &lp->thin_chunk_size_calc_policy, - &lp->chunk_size)) - return_0; + } else if (segtype_is_cache_pool(lp->segtype) || segtype_is_cache(lp->segtype)) { + if (!update_cache_pool_params(vg->cmd, vg->profile, vg->extent_size, + lp->segtype, lp->target_attr, + lp->extents, + &lp->pool_metadata_extents, + &lp->thin_chunk_size_calc_policy, + &lp->chunk_size)) + return_0; + } if (lcp->percent == PERCENT_FREE || lcp->percent == PERCENT_PVS) { if (lp->extents <= (2 * lp->pool_metadata_extents)) {

1 0

master - raid: disallow reshape of stacked LVs
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=7737ffb11ceba0f4220e1… Commit: 7737ffb11ceba0f4220e1dfb79b8e97f20e7b8e9 Parent: dad2660a387ed32dc8146b497d279089c1ce48ed Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 13 17:27:24 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:42:31 2020 +0100 raid: disallow reshape of stacked LVs Until we resolve reshape for 'stacked' devices, we need to disable it. So users can no longer reshape i.e. thin-pool data volumes, causing ATM bad thin-pool problems. --- lib/metadata/raid_manip.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/lib/metadata/raid_manip.c b/lib/metadata/raid_manip.c index a1c51aa..4855039 100644 --- a/lib/metadata/raid_manip.c +++ b/lib/metadata/raid_manip.c @@ -6438,6 +6438,12 @@ int lv_raid_convert(struct logical_volume *lv, uint32_t available_slvs, removed_slvs; takeover_fn_t takeover_fn; + /* FIXME Can't reshape volume in use - aka not toplevel devices */ + if (!dm_list_empty(&lv->segs_using_this_lv)) { + log_error("Can't reshape stacked volume %s.", display_lvname(lv)); + return 0; + } + /* FIXME If not active, prompt and activate */ /* FIXME Some operations do not require the LV to be active */ /* LV must be active to perform raid conversion operations */

1 0

stable-2.02 - WHATS_NEW: update
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=846ae8d49d74ac61c2cae… Commit: 846ae8d49d74ac61c2caed84c9720aedbe9867ae Parent: c575c1c9ff71d95b6af0ec75798dd597491ca0b8 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 13 17:37:29 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:41:44 2020 +0100 WHATS_NEW: update --- WHATS_NEW | 2 ++ 1 file changed, 2 insertions(+) diff --git a/WHATS_NEW b/WHATS_NEW index 047479b..c885a21 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,5 +1,7 @@ Version 2.02.187 - =================================== + Avoid running cache input arg validation when creating vdo pool. + Prevent raid reshaping of stacked volumes. Ensure minimum required region size on striped RaidLV creation. Fix resize of thin-pool with data and metadata of different segtype. Fix splitting mirror leg in cluster.

1 0

stable-2.02 - vdo: avoid running initialization of cache pool vars
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c575c1c9ff71d95b6af0e… Commit: c575c1c9ff71d95b6af0ec75798dd597491ca0b8 Parent: 36210c2b491424d7a0ab27d0a65effd6fc6ecc4c Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 6 15:57:08 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:41:22 2020 +0100 vdo: avoid running initialization of cache pool vars Since VDO is also pool, the old if() case missed to know about this, and executed unnecesserily initialization of cache pool variables. This was usually harmless when using 'smaller' sizes of VDO pools, but for big VDO pool size, we were reporting senseless messages about big cache chunk sizes. --- tools/lvcreate.c | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) diff --git a/tools/lvcreate.c b/tools/lvcreate.c index c27b798..4be8e03 100644 --- a/tools/lvcreate.c +++ b/tools/lvcreate.c @@ -395,13 +395,15 @@ static int _update_extents_params(struct volume_group *vg, &lp->discards, &lp->zero_new_blocks)) return_0; - } else if (!update_cache_pool_params(vg->cmd, vg->profile, vg->extent_size, - lp->segtype, lp->target_attr, - lp->extents, - &lp->pool_metadata_extents, - &lp->thin_chunk_size_calc_policy, - &lp->chunk_size)) - return_0; + } else if (segtype_is_cache_pool(lp->segtype) || segtype_is_cache(lp->segtype)) { + if (!update_cache_pool_params(vg->cmd, vg->profile, vg->extent_size, + lp->segtype, lp->target_attr, + lp->extents, + &lp->pool_metadata_extents, + &lp->thin_chunk_size_calc_policy, + &lp->chunk_size)) + return_0; + } if (lcp->percent == PERCENT_FREE || lcp->percent == PERCENT_PVS) { if (lp->extents <= (2 * lp->pool_metadata_extents)) {

1 0

stable-2.02 - raid: disallow reshape of stacked LVs
by Zdenek Kabelac 14 Jan '20

14 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=36210c2b491424d7a0ab2… Commit: 36210c2b491424d7a0ab27d0a65effd6fc6ecc4c Parent: 50c56ade2a7a89f751091669fb8b31854f93eff1 Author: Zdenek Kabelac <zkabelac(a)redhat.com> AuthorDate: Mon Jan 13 17:27:24 2020 +0100 Committer: Zdenek Kabelac <zkabelac(a)redhat.com> CommitterDate: Mon Jan 13 17:41:22 2020 +0100 raid: disallow reshape of stacked LVs Until we resolve reshape for 'stacked' devices, we need to disable it. So users can no longer reshape i.e. thin-pool data volumes, causing ATM bad thin-pool problems. --- lib/metadata/raid_manip.c | 6 ++++++ 1 file changed, 6 insertions(+) diff --git a/lib/metadata/raid_manip.c b/lib/metadata/raid_manip.c index 9030261..548faf1 100644 --- a/lib/metadata/raid_manip.c +++ b/lib/metadata/raid_manip.c @@ -6444,6 +6444,12 @@ int lv_raid_convert(struct logical_volume *lv, uint32_t available_slvs, removed_slvs; takeover_fn_t takeover_fn; + /* FIXME Can't reshape volume in use - aka not toplevel devices */ + if (!dm_list_empty(&lv->segs_using_this_lv)) { + log_error("Can't reshape stacked volume %s.", display_lvname(lv)); + return 0; + } + /* FIXME If not active, prompt and activate */ /* FIXME Some operations do not require the LV to be active */ /* LV must be active to perform raid conversion operations */

1 0

master - WHATS_NEW: VDO lvmdbusd adds
by Tony Asleson 10 Jan '20

10 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=dad2660a387ed32dc8146… Commit: dad2660a387ed32dc8146b497d279089c1ce48ed Parent: c496ba6505dda29bb1fb48b326cfd959ab0facd4 Author: Tony Asleson <tasleson(a)redhat.com> AuthorDate: Thu Jan 9 13:11:41 2020 -0600 Committer: Tony Asleson <tasleson(a)redhat.com> CommitterDate: Thu Jan 9 13:11:41 2020 -0600 WHATS_NEW: VDO lvmdbusd adds --- WHATS_NEW | 2 ++ 1 files changed, 2 insertions(+), 0 deletions(-) diff --git a/WHATS_NEW b/WHATS_NEW index ec41e54..b3c6102 100644 --- a/WHATS_NEW +++ b/WHATS_NEW @@ -1,5 +1,7 @@ Version 2.03.08 - ==================================== + Added VDO lvmdbusd methods for enable/disable compression & dedupe. + Added VDO lvmdbusd method for converting LV to VDO pool. Version 2.03.07 - 30th November 2019 ====================================

1 0

master - lvmdbusd: Add function to convert LV into a VDO pool
by Tony Asleson 10 Jan '20

10 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c496ba6505dda29bb1fb4… Commit: c496ba6505dda29bb1fb48b326cfd959ab0facd4 Parent: c3ef41f620418bc9d5932fc6f7284a600e6cebec Author: Vojtech Trefny <vtrefny(a)redhat.com> AuthorDate: Mon Jan 6 11:28:41 2020 +0100 Committer: Tony Asleson <tasleson(a)redhat.com> CommitterDate: Thu Jan 9 13:07:55 2020 -0600 lvmdbusd: Add function to convert LV into a VDO pool --- daemons/lvmdbusd/cmdhandler.py | 8 ++++++++ daemons/lvmdbusd/vg.py | 32 ++++++++++++++++++++++++++++++++ test/dbus/lvmdbustest.py | 38 ++++++++++++++++++++++++++++++++++++++ 3 files changed, 78 insertions(+), 0 deletions(-) diff --git a/daemons/lvmdbusd/cmdhandler.py b/daemons/lvmdbusd/cmdhandler.py index aa5199f..7d2f4c4 100644 --- a/daemons/lvmdbusd/cmdhandler.py +++ b/daemons/lvmdbusd/cmdhandler.py @@ -398,6 +398,14 @@ def vg_create_vdo_pool_lv_and_lv(vg_name, pool_name, lv_name, data_size, return call(cmd) +def vg_create_vdo_pool(pool_full_name, lv_name, virtual_size, create_options): + cmd = ['lvconvert'] + cmd.extend(options_to_cli_args(create_options)) + cmd.extend(['--type', 'vdo-pool', '-n', lv_name, '--force', '-y', + '-V', '%dB' % virtual_size, pool_full_name]) + return call(cmd) + + def lv_remove(lv_path, remove_options): cmd = ['lvremove'] cmd.extend(options_to_cli_args(remove_options)) diff --git a/daemons/lvmdbusd/vg.py b/daemons/lvmdbusd/vg.py index 789626c..51fd07e 100644 --- a/daemons/lvmdbusd/vg.py +++ b/daemons/lvmdbusd/vg.py @@ -813,3 +813,35 @@ class VgVdo(Vg): round_size(virtual_size), create_options), cb, cbe) cfg.worker_q.put(r) + + @staticmethod + def _vdo_pool_create(uuid, vg_name, pool_lv, name, virtual_size, create_options): + Vg.validate_dbus_object(uuid, vg_name) + + # Retrieve the full name of the pool lv + pool = cfg.om.get_object_by_path(pool_lv) + if not pool: + msg = 'LV with object path %s not present!' % \ + (pool_lv) + raise dbus.exceptions.DBusException(VG_VDO_INTERFACE, msg) + + Vg.handle_execute(*cmdhandler.vg_create_vdo_pool( + pool.lv_full_name(), name, virtual_size, + create_options)) + return Vg.fetch_new_lv(vg_name, pool.Name) + + @dbus.service.method( + dbus_interface=VG_VDO_INTERFACE, + in_signature='ostia{sv}', + out_signature='(oo)', + async_callbacks=('cb', 'cbe')) + def CreateVdoPool(self, pool_lv, name, virtual_size, + tmo, create_options, cb, cbe): + utils.validate_lv_name(VG_VDO_INTERFACE, self.Name, name) + + r = RequestEntry(tmo, VgVdo._vdo_pool_create, + (self.state.Uuid, self.state.lvm_id, + pool_lv, name, + round_size(virtual_size), + create_options), cb, cbe) + cfg.worker_q.put(r) diff --git a/test/dbus/lvmdbustest.py b/test/dbus/lvmdbustest.py index b819a04..8753e65 100755 --- a/test/dbus/lvmdbustest.py +++ b/test/dbus/lvmdbustest.py @@ -1903,6 +1903,44 @@ class TestDbusService(unittest.TestCase): vg, _, _ = self._create_vdo_pool_and_lv() self.handle_return(vg.Vg.Remove(dbus.Int32(g_tmo), EOD)) + def _create_vdo_pool(self): + pool_name = lv_n('_vdo_pool') + lv_name = lv_n('_vdo_data') + vg_proxy = self._vg_create(vg_prefix="vdo_conv_") + lv = self._test_lv_create( + vg_proxy.Vg.LvCreate, + (dbus.String(pool_name), dbus.UInt64(mib(4096)), + dbus.Array([], signature='(ott)'), dbus.Int32(g_tmo), + EOD), vg_proxy.Vg, LV_BASE_INT) + lv_obj_path = self._lookup("%s/%s" % (vg_proxy.Vg.Name, pool_name)) + self.assertNotEqual(lv_obj_path, "/") + + vdo_pool_path = self.handle_return( + vg_proxy.VgVdo.CreateVdoPool( + dbus.ObjectPath(lv.object_path), lv_name, + dbus.UInt64(mib(8192)), + dbus.Int32(g_tmo), + EOD)) + + self.assertNotEqual(vdo_pool_path, "/") + self.assertEqual( + vdo_pool_path, + self._lookup("%s/%s" % (vg_proxy.Vg.Name, pool_name))) + intf = [LV_COMMON_INT, LV_INT] + vdo_lv_obj_path = self._lookup("%s/%s" % (vg_proxy.Vg.Name, lv_name)) + vdo_lv = ClientProxy(self.bus, vdo_lv_obj_path, interfaces=intf) + intf.append(VDOPOOL_INT) + vdo_pool_lv = ClientProxy(self.bus, vdo_pool_path, interfaces=intf) + return vg_proxy, vdo_pool_lv, vdo_lv + + def test_vdo_pool_convert(self): + # Basic vdo sanity testing + if not self.vdo: + raise unittest.SkipTest('vdo not supported') + + vg, _pool, _lv = self._create_vdo_pool() + self.handle_return(vg.Vg.Remove(dbus.Int32(g_tmo), EOD)) + def test_vdo_pool_compression_deduplication(self): if not self.vdo: raise unittest.SkipTest('vdo not supported')

1 0

master - lvmdbusd: Add VDO enable/disable compress & dedup
by Tony Asleson 10 Jan '20

10 Jan '20

Gitweb: https://sourceware.org/git/?p=lvm2.git;a=commitdiff;h=c3ef41f620418bc9d5932… Commit: c3ef41f620418bc9d5932fc6f7284a600e6cebec Parent: 87e88078c993a149af6d2f104998c508b7aee9be Author: Vojtech Trefny <vtrefny(a)redhat.com> AuthorDate: Fri Dec 27 15:29:15 2019 +0100 Committer: Tony Asleson <tasleson(a)redhat.com> CommitterDate: Thu Jan 9 13:07:47 2020 -0600 lvmdbusd: Add VDO enable/disable compress & dedup Added methods to vdo pool interface to allow enabling and disabling of VDO: * Compression * Deduplication --- daemons/lvmdbusd/cmdhandler.py | 22 +++++++++++++ daemons/lvmdbusd/lv.py | 66 ++++++++++++++++++++++++++++++++++++++++ test/dbus/lvmdbustest.py | 32 ++++++++++++++++++- 3 files changed, 118 insertions(+), 2 deletions(-) diff --git a/daemons/lvmdbusd/cmdhandler.py b/daemons/lvmdbusd/cmdhandler.py index e0bb105..aa5199f 100644 --- a/daemons/lvmdbusd/cmdhandler.py +++ b/daemons/lvmdbusd/cmdhandler.py @@ -460,6 +460,28 @@ def lv_detach_cache(lv_full_name, detach_options, destroy_cache): return call(cmd) +def lv_vdo_compression(lv_path, enable, comp_options): + cmd = ['lvchange', '--compression'] + if enable: + cmd.append('y') + else: + cmd.append('n') + cmd.extend(options_to_cli_args(comp_options)) + cmd.append(lv_path) + return call(cmd) + + +def lv_vdo_deduplication(lv_path, enable, dedup_options): + cmd = ['lvchange', '--deduplication'] + if enable: + cmd.append('y') + else: + cmd.append('n') + cmd.extend(options_to_cli_args(dedup_options)) + cmd.append(lv_path) + return call(cmd) + + def supports_json(): cmd = ['help'] rc, out, err = call(cmd) diff --git a/daemons/lvmdbusd/lv.py b/daemons/lvmdbusd/lv.py index 3018749..fd46f34 100644 --- a/daemons/lvmdbusd/lv.py +++ b/daemons/lvmdbusd/lv.py @@ -780,6 +780,72 @@ class LvVdoPool(Lv): def DataLv(self): return dbus.ObjectPath(self._data_lv) + @staticmethod + def _enable_disable_compression(pool_uuid, pool_name, enable, comp_options): + # Make sure we have a dbus object representing it + LvCommon.validate_dbus_object(pool_uuid, pool_name) + # Rename the logical volume + LvCommon.handle_execute(*cmdhandler.lv_vdo_compression( + pool_name, enable, comp_options)) + return '/' + + @dbus.service.method( + dbus_interface=VDO_POOL_INTERFACE, + in_signature='ia{sv}', + out_signature='o', + async_callbacks=('cb', 'cbe')) + def EnableCompression(self, tmo, comp_options, cb, cbe): + r = RequestEntry( + tmo, LvVdoPool._enable_disable_compression, + (self.Uuid, self.lvm_id, True, comp_options), + cb, cbe, False) + cfg.worker_q.put(r) + + @dbus.service.method( + dbus_interface=VDO_POOL_INTERFACE, + in_signature='ia{sv}', + out_signature='o', + async_callbacks=('cb', 'cbe')) + def DisableCompression(self, tmo, comp_options, cb, cbe): + r = RequestEntry( + tmo, LvVdoPool._enable_disable_compression, + (self.Uuid, self.lvm_id, False, comp_options), + cb, cbe, False) + cfg.worker_q.put(r) + + @staticmethod + def _enable_disable_deduplication(pool_uuid, pool_name, enable, dedup_options): + # Make sure we have a dbus object representing it + LvCommon.validate_dbus_object(pool_uuid, pool_name) + # Rename the logical volume + LvCommon.handle_execute(*cmdhandler.lv_vdo_deduplication( + pool_name, enable, dedup_options)) + return '/' + + @dbus.service.method( + dbus_interface=VDO_POOL_INTERFACE, + in_signature='ia{sv}', + out_signature='o', + async_callbacks=('cb', 'cbe')) + def EnableDeduplication(self, tmo, dedup_options, cb, cbe): + r = RequestEntry( + tmo, LvVdoPool._enable_disable_deduplication, + (self.Uuid, self.lvm_id, True, dedup_options), + cb, cbe, False) + cfg.worker_q.put(r) + + @dbus.service.method( + dbus_interface=VDO_POOL_INTERFACE, + in_signature='ia{sv}', + out_signature='o', + async_callbacks=('cb', 'cbe')) + def DisableDeduplication(self, tmo, dedup_options, cb, cbe): + r = RequestEntry( + tmo, LvVdoPool._enable_disable_deduplication, + (self.Uuid, self.lvm_id, False, dedup_options), + cb, cbe, False) + cfg.worker_q.put(r) + # noinspection PyPep8Naming class LvThinPool(Lv): diff --git a/test/dbus/lvmdbustest.py b/test/dbus/lvmdbustest.py index 8215968..b819a04 100755 --- a/test/dbus/lvmdbustest.py +++ b/test/dbus/lvmdbustest.py @@ -1858,11 +1858,11 @@ class TestDbusService(unittest.TestCase): self.assertEqual(pv_object_path, self._lookup(symlink)) self.assertEqual(pv_object_path, self._lookup(pv_device_path)) - def _create_vdo_pool_and_lv(self): + def _create_vdo_pool_and_lv(self, vg_prefix="vdo_"): pool_name = lv_n("_vdo_pool") lv_name = lv_n() - vg_proxy = self._vg_create(vg_prefix="vdo_") + vg_proxy = self._vg_create(vg_prefix=vg_prefix) vdo_pool_object_path = self.handle_return( vg_proxy.VgVdo.CreateVdoPoolandLv( pool_name, lv_name, @@ -1903,6 +1903,34 @@ class TestDbusService(unittest.TestCase): vg, _, _ = self._create_vdo_pool_and_lv() self.handle_return(vg.Vg.Remove(dbus.Int32(g_tmo), EOD)) + def test_vdo_pool_compression_deduplication(self): + if not self.vdo: + raise unittest.SkipTest('vdo not supported') + + vg, pool, _lv = self._create_vdo_pool_and_lv(vg_prefix="vdo2_") + + # compression and deduplication should be enabled by default + self.assertEqual(pool.VdoPool.Compression, "enabled") + self.assertEqual(pool.VdoPool.Deduplication, "enabled") + + self.handle_return( + pool.VdoPool.DisableCompression(dbus.Int32(g_tmo), EOD)) + self.handle_return( + pool.VdoPool.DisableDeduplication(dbus.Int32(g_tmo), EOD)) + pool.update() + self.assertEqual(pool.VdoPool.Compression, "") + self.assertEqual(pool.VdoPool.Deduplication, "") + + self.handle_return( + pool.VdoPool.EnableCompression(dbus.Int32(g_tmo), EOD)) + self.handle_return( + pool.VdoPool.EnableDeduplication(dbus.Int32(g_tmo), EOD)) + pool.update() + self.assertEqual(pool.VdoPool.Compression, "enabled") + self.assertEqual(pool.VdoPool.Deduplication, "enabled") + + self.handle_return(vg.Vg.Remove(dbus.Int32(g_tmo), EOD)) + def _test_lv_method_interface(self, lv): self._rename_lv_test(lv) self._test_activate_deactivate(lv)

1 0

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

lvm2-commits January 2020