lvm2-commits January 2020

lvm2-commits@lists.fedorahosted.org

5 participants
37 discussions

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

16 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 16 Jan '20

16 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 16 Jan '20

16 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 16 Jan '20

16 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 16 Jan '20

16 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 15 Jan '20

15 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 15 Jan '20

15 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 13 Jan '20

13 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 13 Jan '20

13 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 13 Jan '20

13 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

2026

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

lvm2-commits January 2020