From c380b84d8b88ca61371d8fdb77d5719c778700fc Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Mon, 17 Dec 2018 18:42:09 +0100 Subject: hashmap: rework hashmap_clear() to be more defensive Let's first remove an item from the hashmap and only then destroy it. This makes sure that destructor functions can mdoify the hashtables in their own codee and we won't be confused by that. --- src/basic/hashmap.c | 24 ++++++++++++++---------- src/basic/hashmap.h | 6 +++++- 2 files changed, 19 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c index d0bdbe3d1..0dd9f8ddd 100644 --- a/src/basic/hashmap.c +++ b/src/basic/hashmap.c @@ -882,17 +882,21 @@ void internal_hashmap_clear(HashmapBase *h, free_func_t default_free_key, free_f free_value = h->hash_ops->free_value ?: default_free_value; if (free_key || free_value) { - unsigned idx; - for (idx = skip_free_buckets(h, 0); idx != IDX_NIL; - idx = skip_free_buckets(h, idx + 1)) { - struct hashmap_base_entry *e = bucket_at(h, idx); + /* If destructor calls are defined, let's destroy things defensively: let's take the item out of the + * hash table, and only then call the destructor functions. If these destructors then try to unregister + * themselves from our hash table a second time, the entry is already gone. */ + + while (internal_hashmap_size(h) > 0) { + void *v, *k; + + v = internal_hashmap_first_key_and_value(h, true, &k); if (free_key) - free_key((void *) e->key); + free_key(k); if (free_value) - free_value(entry_value(h, e)); + free_value(v); } } @@ -1475,8 +1479,8 @@ int hashmap_remove_and_replace(Hashmap *h, const void *old_key, const void *new_ return 0; } -void *hashmap_remove_value(Hashmap *h, const void *key, void *value) { - struct plain_hashmap_entry *e; +void *internal_hashmap_remove_value(HashmapBase *h, const void *key, void *value) { + struct hashmap_base_entry *e; unsigned hash, idx; if (!h) @@ -1487,8 +1491,8 @@ void *hashmap_remove_value(Hashmap *h, const void *key, void *value) { if (idx == IDX_NIL) return NULL; - e = plain_bucket_at(h, idx); - if (e->value != value) + e = bucket_at(h, idx); + if (entry_value(h, e) != value) return NULL; remove_entry(h, idx); diff --git a/src/basic/hashmap.h b/src/basic/hashmap.h index a330a1d49..5bf807a76 100644 --- a/src/basic/hashmap.h +++ b/src/basic/hashmap.h @@ -191,7 +191,11 @@ static inline void *ordered_hashmap_remove2(OrderedHashmap *h, const void *key, return hashmap_remove2(PLAIN_HASHMAP(h), key, rkey); } -void *hashmap_remove_value(Hashmap *h, const void *key, void *value); +void *internal_hashmap_remove_value(HashmapBase *h, const void *key, void *value); +static inline void *hashmap_remove_value(Hashmap *h, const void *key, void *value) { + return internal_hashmap_remove_value(HASHMAP_BASE(h), key, value); +} + static inline void *ordered_hashmap_remove_value(OrderedHashmap *h, const void *key, void *value) { return hashmap_remove_value(PLAIN_HASHMAP(h), key, value); } -- cgit v1.2.3-65-gdbad From 8ae1a821b36683fae6514dcd317a2049d0824779 Mon Sep 17 00:00:00 2001 From: Lennart Poettering Date: Mon, 17 Dec 2018 18:43:11 +0100 Subject: sd-lldp: accept if a neighbor is already removed from the hashtable --- src/libsystemd-network/lldp-neighbor.c | 7 ++++++- 1 file changed, 6 insertions(+), 1 deletion(-) (limited to 'src') diff --git a/src/libsystemd-network/lldp-neighbor.c b/src/libsystemd-network/lldp-neighbor.c index 199d8aee0..43fc8e03c 100644 --- a/src/libsystemd-network/lldp-neighbor.c +++ b/src/libsystemd-network/lldp-neighbor.c @@ -82,7 +82,12 @@ sd_lldp_neighbor *lldp_neighbor_unlink(sd_lldp_neighbor *n) { if (!n->lldp) return NULL; - assert_se(hashmap_remove(n->lldp->neighbor_by_id, &n->id) == n); + /* Only remove the neighbor object from the hash table if it's in there, don't complain if it isn't. This is + * because we are used as destructor call for hashmap_clear() and thus sometimes are called to de-register + * ourselves from the hashtable and sometimes are called after we already are de-registered. */ + + (void) hashmap_remove_value(n->lldp->neighbor_by_id, &n->id, n); + assert_se(prioq_remove(n->lldp->neighbor_by_expiry, n, &n->prioq_idx) >= 0); n->lldp = NULL; -- cgit v1.2.3-65-gdbad From 7f09920585f65c62e042af77b47b2a217e46d779 Mon Sep 17 00:00:00 2001 From: Filipe Brandenburger Date: Wed, 5 Dec 2018 23:58:58 -0800 Subject: lldp: add test coverage for sd_lldp_get_neighbors() with multiple neighbors In particular, check that the order of the results is consistent. This test coverage will be useful in order to refactor the compare_func used while sorting the results. When introduced, this test also uncovered a memory leak in sd_lldp_stop(), which was then fixed by a separate commit using a specialized function as destructor of the LLDP Hashmap. Tested: $ ninja -C build/ test $ valgrind --leak-check=full build/test-lldp --- src/libsystemd-network/test-lldp.c | 130 +++++++++++++++++++++++++++++++++++++ 1 file changed, 130 insertions(+) (limited to 'src') diff --git a/src/libsystemd-network/test-lldp.c b/src/libsystemd-network/test-lldp.c index e0d4d9a85..cb4545d90 100644 --- a/src/libsystemd-network/test-lldp.c +++ b/src/libsystemd-network/test-lldp.c @@ -229,6 +229,135 @@ static void test_receive_oui_packet(sd_event *e) { assert_se(stop_lldp(lldp) == 0); } +static void test_multiple_neighbors_sorted(sd_event *e) { + + static const uint8_t frame1[] = { + /* Ethernet header */ + 0x01, 0x80, 0xc2, 0x00, 0x00, 0x03, /* Destination MAC */ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, /* Source MAC */ + 0x88, 0xcc, /* Ethertype */ + /* LLDP mandatory TLVs */ + 0x02, 0x04, 0x01, '1', '/', '2', /* Chassis component: "1/2" */ + 0x04, 0x04, 0x02, '2', '/', '3', /* Port component: "2/3" */ + 0x06, 0x02, 0x00, 0x78, /* TTL: 120 seconds */ + 0x00, 0x00 /* End Of LLDPDU */ + }; + static const uint8_t frame2[] = { + /* Ethernet header */ + 0x01, 0x80, 0xc2, 0x00, 0x00, 0x03, /* Destination MAC */ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, /* Source MAC */ + 0x88, 0xcc, /* Ethertype */ + /* LLDP mandatory TLVs */ + 0x02, 0x04, 0x01, '2', '/', '1', /* Chassis component: "2/1" */ + 0x04, 0x04, 0x02, '1', '/', '3', /* Port component: "1/3" */ + 0x06, 0x02, 0x00, 0x78, /* TTL: 120 seconds */ + 0x00, 0x00 /* End Of LLDPDU */ + }; + static const uint8_t frame3[] = { + /* Ethernet header */ + 0x01, 0x80, 0xc2, 0x00, 0x00, 0x03, /* Destination MAC */ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, /* Source MAC */ + 0x88, 0xcc, /* Ethertype */ + /* LLDP mandatory TLVs */ + 0x02, 0x05, 0x01, '2', '/', '1', '0', /* Chassis component: "2/10" */ + 0x04, 0x04, 0x02, '1', '/', '0', /* Port component: "1/0" */ + 0x06, 0x02, 0x00, 0x78, /* TTL: 120 seconds */ + 0x00, 0x00 /* End Of LLDPDU */ + }; + static const uint8_t frame4[] = { + /* Ethernet header */ + 0x01, 0x80, 0xc2, 0x00, 0x00, 0x03, /* Destination MAC */ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, /* Source MAC */ + 0x88, 0xcc, /* Ethertype */ + /* LLDP mandatory TLVs */ + 0x02, 0x05, 0x01, '2', '/', '1', '9', /* Chassis component: "2/19" */ + 0x04, 0x04, 0x02, '1', '/', '0', /* Port component: "1/0" */ + 0x06, 0x02, 0x00, 0x78, /* TTL: 120 seconds */ + 0x00, 0x00 /* End Of LLDPDU */ + }; + static const uint8_t frame5[] = { + /* Ethernet header */ + 0x01, 0x80, 0xc2, 0x00, 0x00, 0x03, /* Destination MAC */ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, /* Source MAC */ + 0x88, 0xcc, /* Ethertype */ + /* LLDP mandatory TLVs */ + 0x02, 0x04, 0x01, '1', '/', '2', /* Chassis component: "1/2" */ + 0x04, 0x05, 0x02, '2', '/', '1', '0', /* Port component: "2/10" */ + 0x06, 0x02, 0x00, 0x78, /* TTL: 120 seconds */ + 0x00, 0x00 /* End Of LLDPDU */ + }; + static const uint8_t frame6[] = { + /* Ethernet header */ + 0x01, 0x80, 0xc2, 0x00, 0x00, 0x03, /* Destination MAC */ + 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, /* Source MAC */ + 0x88, 0xcc, /* Ethertype */ + /* LLDP mandatory TLVs */ + 0x02, 0x04, 0x01, '1', '/', '2', /* Chassis component: "1/2" */ + 0x04, 0x05, 0x02, '2', '/', '3', '9', /* Port component: "2/10" */ + 0x06, 0x02, 0x00, 0x78, /* TTL: 120 seconds */ + 0x00, 0x00 /* End Of LLDPDU */ + }; + static const char* expected[] = { + /* ordered pairs of Chassis+Port */ + "1/2", "2/10", + "1/2", "2/3", + "1/2", "2/39", + "2/1", "1/3", + "2/10", "1/0", + "2/19", "1/0", + }; + + sd_lldp *lldp; + sd_lldp_neighbor **neighbors; + int i; + uint8_t type; + const void *data; + size_t length, expected_length; + uint16_t ttl; + + lldp_handler_calls = 0; + assert_se(start_lldp(&lldp, e, lldp_handler, NULL) == 0); + + assert_se(write(test_fd[1], frame1, sizeof(frame1)) == sizeof(frame1)); + sd_event_run(e, 0); + assert_se(write(test_fd[1], frame2, sizeof(frame2)) == sizeof(frame2)); + sd_event_run(e, 0); + assert_se(write(test_fd[1], frame3, sizeof(frame3)) == sizeof(frame3)); + sd_event_run(e, 0); + assert_se(write(test_fd[1], frame4, sizeof(frame4)) == sizeof(frame4)); + sd_event_run(e, 0); + assert_se(write(test_fd[1], frame5, sizeof(frame5)) == sizeof(frame5)); + sd_event_run(e, 0); + assert_se(write(test_fd[1], frame6, sizeof(frame6)) == sizeof(frame6)); + sd_event_run(e, 0); + assert_se(lldp_handler_calls == 6); + + assert_se(sd_lldp_get_neighbors(lldp, &neighbors) == 6); + + for (i = 0; i < 6; i++) { + assert_se(sd_lldp_neighbor_get_chassis_id(neighbors[i], &type, &data, &length) == 0); + assert_se(type == SD_LLDP_CHASSIS_SUBTYPE_CHASSIS_COMPONENT); + expected_length = strlen(expected[2 * i]); + assert_se(length == expected_length); + assert_se(memcmp(data, expected[2 * i], expected_length) == 0); + + assert_se(sd_lldp_neighbor_get_port_id(neighbors[i], &type, &data, &length) == 0); + assert_se(type == SD_LLDP_PORT_SUBTYPE_PORT_COMPONENT); + expected_length = strlen(expected[2 * i + 1]); + assert_se(length == expected_length); + assert_se(memcmp(data, expected[2 * i + 1], expected_length) == 0); + + assert_se(sd_lldp_neighbor_get_ttl(neighbors[i], &ttl) == 0); + assert_se(ttl == 120); + } + + for (i = 0; i < 6; i++) + sd_lldp_neighbor_unref(neighbors[i]); + free(neighbors); + + assert_se(stop_lldp(lldp) == 0); +} + int main(int argc, char *argv[]) { _cleanup_(sd_event_unrefp) sd_event *e = NULL; @@ -239,6 +368,7 @@ int main(int argc, char *argv[]) { test_receive_basic_packet(e); test_receive_incomplete_packet(e); test_receive_oui_packet(e); + test_multiple_neighbors_sorted(e); return 0; } -- cgit v1.2.3-65-gdbad From 70b400d9c2322d9a6982514c951f1b2da85fe462 Mon Sep 17 00:00:00 2001 From: Zbigniew Jędrzejewski-Szmek Date: Tue, 18 Dec 2018 09:50:01 +0100 Subject: hashmap: use ternary op to shorten code --- src/basic/hash-funcs.c | 2 +- src/basic/hashmap.c | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/basic/hash-funcs.c b/src/basic/hash-funcs.c index d6dc34e60..1be43d41a 100644 --- a/src/basic/hash-funcs.c +++ b/src/basic/hash-funcs.c @@ -65,7 +65,7 @@ int trivial_compare_func(const void *a, const void *b) { const struct hash_ops trivial_hash_ops = { .hash = trivial_hash_func, - .compare = trivial_compare_func + .compare = trivial_compare_func, }; void uint64_hash_func(const uint64_t *p, struct siphash *state) { diff --git a/src/basic/hashmap.c b/src/basic/hashmap.c index 0dd9f8ddd..5a4bb37b8 100644 --- a/src/basic/hashmap.c +++ b/src/basic/hashmap.c @@ -779,7 +779,7 @@ static struct HashmapBase *hashmap_base_new(const struct hash_ops *hash_ops, enu h->type = type; h->from_pool = up; - h->hash_ops = hash_ops ? hash_ops : &trivial_hash_ops; + h->hash_ops = hash_ops ?: &trivial_hash_ops; if (type == HASHMAP_TYPE_ORDERED) { OrderedHashmap *lh = (OrderedHashmap*)h; -- cgit v1.2.3-65-gdbad From 32ca29115e20c9ec772570bda3b326cacafacc52 Mon Sep 17 00:00:00 2001 From: Zbigniew Jędrzejewski-Szmek Date: Tue, 18 Dec 2018 11:33:52 +0100 Subject: test-hashmap: use the usual function headers and print timing stats This makes it slightly easier to watch for performance changes. --- src/test/test-hashmap-plain.c | 72 ++++++++++++++++++++++++------------------- src/test/test-hashmap.c | 8 +++++ 2 files changed, 48 insertions(+), 32 deletions(-) (limited to 'src') diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index c04ef0b1f..039c0e0e5 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -14,7 +14,7 @@ static void test_hashmap_replace(void) { Hashmap *m; char *val1, *val2, *val3, *val4, *val5, *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); @@ -54,7 +54,7 @@ static void test_hashmap_copy(void) { Hashmap *m, *copy; char *val1, *val2, *val3, *val4, *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("val1"); assert_se(val1); @@ -92,7 +92,7 @@ static void test_hashmap_get_strv(void) { char **strv; char *val1, *val2, *val3, *val4; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("val1"); assert_se(val1); @@ -130,7 +130,7 @@ static void test_hashmap_move_one(void) { Hashmap *m, *n; char *val1, *val2, *val3, *val4, *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("val1"); assert_se(val1); @@ -171,7 +171,7 @@ static void test_hashmap_move(void) { Hashmap *m, *n; char *val1, *val2, *val3, *val4, *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("val1"); assert_se(val1); @@ -215,7 +215,7 @@ static void test_hashmap_update(void) { Hashmap *m; char *val1, *val2, *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); val1 = strdup("old_value"); @@ -247,7 +247,7 @@ static void test_hashmap_put(void) { void *val2 = (void*) "val 2"; _cleanup_free_ char* key1 = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); assert_se(hashmap_ensure_allocated(&m, &string_hash_ops) >= 0); assert_se(m); @@ -267,7 +267,7 @@ static void test_hashmap_remove(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; char *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); r = hashmap_remove(NULL, "key 1"); assert_se(r == NULL); @@ -297,7 +297,7 @@ static void test_hashmap_remove2(void) { char val2[] = "val 2"; void *r, *r2; - log_info("%s", __func__); + log_info("/* %s */", __func__); r = hashmap_remove2(NULL, "key 1", &r2); assert_se(r == NULL); @@ -329,7 +329,7 @@ static void test_hashmap_remove_value(void) { char val1[] = "val 1"; char val2[] = "val 2"; - log_info("%s", __func__); + log_info("/* %s */", __func__); r = hashmap_remove_value(NULL, "key 1", val1); assert_se(r == NULL); @@ -363,7 +363,7 @@ static void test_hashmap_remove_and_put(void) { int valid; char *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); assert_se(m); @@ -399,7 +399,7 @@ static void test_hashmap_remove_and_replace(void) { void *r; int i, j; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&trivial_hash_ops); assert_se(m); @@ -452,7 +452,7 @@ static void test_hashmap_ensure_allocated(void) { Hashmap *m; int valid_hashmap; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); @@ -475,7 +475,7 @@ static void test_hashmap_foreach_key(void) { "key 3\0" "key 4\0"; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); @@ -507,7 +507,7 @@ static void test_hashmap_foreach(void) { char *val1, *val2, *val3, *val4, *s; unsigned count; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("my val1"); assert_se(val1); @@ -559,7 +559,7 @@ static void test_hashmap_merge(void) { Hashmap *n; char *val1, *val2, *val3, *val4, *r; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("my val1"); assert_se(val1); @@ -594,7 +594,7 @@ static void test_hashmap_contains(void) { Hashmap *m; char *val1; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("my val"); assert_se(val1); @@ -616,7 +616,7 @@ static void test_hashmap_isempty(void) { Hashmap *m; char *val1; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("my val"); assert_se(val1); @@ -635,7 +635,7 @@ static void test_hashmap_size(void) { Hashmap *m; char *val1, *val2, *val3, *val4; - log_info("%s", __func__); + log_info("/* %s */", __func__); val1 = strdup("my val"); assert_se(val1); @@ -667,7 +667,7 @@ static void test_hashmap_get(void) { char *r; char *val; - log_info("%s", __func__); + log_info("/* %s */", __func__); val = strdup("my val"); assert_se(val); @@ -696,7 +696,7 @@ static void test_hashmap_get2(void) { char key_orig[] = "Key 1"; void *key_copy; - log_info("%s", __func__); + log_info("/* %s */", __func__); val = strdup("my val"); assert_se(val); @@ -739,16 +739,20 @@ static void test_hashmap_many(void) { void *v, *k; bool slow = slow_tests_enabled(); const struct { + const char *title; const struct hash_ops *ops; unsigned n_entries; } tests[] = { - { .ops = NULL, .n_entries = slow ? 1 << 20 : 240 }, - { .ops = &crippled_hashmap_ops, .n_entries = slow ? 1 << 14 : 140 }, + { "trivial_hashmap_ops", NULL, slow ? 1 << 20 : 240 }, + { "crippled_hashmap_ops", &crippled_hashmap_ops, slow ? 1 << 14 : 140 }, }; - log_info("%s (%s)", __func__, slow ? "slow" : "fast"); + log_info("/* %s (%s) */", __func__, slow ? "slow" : "fast"); for (j = 0; j < ELEMENTSOF(tests); j++) { + usec_t ts = now(CLOCK_MONOTONIC), n; + char b[FORMAT_TIMESPAN_MAX]; + assert_se(h = hashmap_new(tests[j].ops)); for (i = 1; i < tests[j].n_entries*3; i+=3) { @@ -759,7 +763,8 @@ static void test_hashmap_many(void) { for (i = 1; i < tests[j].n_entries*3; i++) assert_se(hashmap_contains(h, UINT_TO_PTR(i)) == (i % 3 == 1)); - log_info("%u <= %u * 0.8 = %g", hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.8); + log_info("%s %u <= %u * 0.8 = %g", + tests[j].title, hashmap_size(h), hashmap_buckets(h), hashmap_buckets(h) * 0.8); assert_se(hashmap_size(h) <= hashmap_buckets(h) * 0.8); assert_se(hashmap_size(h) == tests[j].n_entries); @@ -771,13 +776,16 @@ static void test_hashmap_many(void) { } hashmap_free(h); + + n = now(CLOCK_MONOTONIC); + log_info("test took %s", format_timespan(b, sizeof b, n - ts, 0)); } } static void test_hashmap_first(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); assert_se(m); @@ -796,7 +804,7 @@ static void test_hashmap_first(void) { static void test_hashmap_first_key(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); assert_se(m); @@ -815,7 +823,7 @@ static void test_hashmap_first_key(void) { static void test_hashmap_steal_first_key(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); assert_se(m); @@ -832,7 +840,7 @@ static void test_hashmap_steal_first(void) { int seen[3] = {}; char *val; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); assert_se(m); @@ -852,7 +860,7 @@ static void test_hashmap_steal_first(void) { static void test_hashmap_clear_free_free(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); assert_se(m); @@ -878,7 +886,7 @@ DEFINE_PRIVATE_HASH_OPS_FULL(test_hash_ops_full, char, string_hash_func, string_ static void test_hashmap_clear_free_with_destructor(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&test_hash_ops_key); assert_se(m); @@ -905,7 +913,7 @@ static void test_hashmap_clear_free_with_destructor(void) { static void test_hashmap_reserve(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; - log_info("%s", __func__); + log_info("/* %s */", __func__); m = hashmap_new(&string_hash_ops); diff --git a/src/test/test-hashmap.c b/src/test/test-hashmap.c index d525ba770..6f29266d6 100644 --- a/src/test/test-hashmap.c +++ b/src/test/test-hashmap.c @@ -10,6 +10,8 @@ static void test_ordered_hashmap_next(void) { _cleanup_ordered_hashmap_free_ OrderedHashmap *m = NULL; int i; + log_info("/* %s */", __func__); + assert_se(m = ordered_hashmap_new(NULL)); for (i = -2; i <= 2; i++) assert_se(ordered_hashmap_put(m, INT_TO_PTR(i), INT_TO_PTR(i+10)) == 1); @@ -32,6 +34,8 @@ static void test_hashmap_free_with_destructor(void) { struct Item items[4] = {}; unsigned i; + log_info("/* %s */", __func__); + assert_se(m = hashmap_new(NULL)); for (i = 0; i < ELEMENTSOF(items) - 1; i++) assert_se(hashmap_put(m, INT_TO_PTR(i), items + i) == 1); @@ -87,6 +91,8 @@ static void test_iterated_cache(void) { Hashmap *m; IteratedCache *c; + log_info("/* %s */", __func__); + assert_se(m = hashmap_new(NULL)); assert_se(c = hashmap_iterated_cache_new(m)); compare_cache(m, c); @@ -122,6 +128,8 @@ static void test_iterated_cache(void) { static void test_path_hashmap(void) { _cleanup_hashmap_free_ Hashmap *h = NULL; + log_info("/* %s */", __func__); + assert_se(h = hashmap_new(&path_hash_ops)); assert_se(hashmap_put(h, "foo", INT_TO_PTR(1)) >= 0); -- cgit v1.2.3-65-gdbad From 8872c3a3910dbf4e6470e8a6f86e4c645712805b Mon Sep 17 00:00:00 2001 From: Zbigniew Jędrzejewski-Szmek Date: Tue, 18 Dec 2018 11:35:48 +0100 Subject: test-hashmap: add test to compare hashmap_free performance The point here is to compare speed of hashmap_destroy with free and a different freeing function, to the implementation details of hashmap_clear can be evaluated. Results: current code: /* test_hashmap_free (slow, 1048576 entries) */ string_hash_ops test took 2.494499s custom_free_hash_ops test took 2.640449s string_hash_ops test took 2.287734s custom_free_hash_ops test took 2.557632s string_hash_ops test took 2.299791s custom_free_hash_ops test took 2.586975s string_hash_ops test took 2.314099s custom_free_hash_ops test took 2.589327s string_hash_ops test took 2.319137s custom_free_hash_ops test took 2.584038s code with a patch which restores the "fast path" using: for (idx = skip_free_buckets(h, 0); idx != IDX_NIL; idx = skip_free_buckets(h, idx + 1)) in the case where both free_key and free_value are either free or NULL: /* test_hashmap_free (slow, 1048576 entries) */ string_hash_ops test took 2.347013s custom_free_hash_ops test took 2.585104s string_hash_ops test took 2.311583s custom_free_hash_ops test took 2.578388s string_hash_ops test took 2.283658s custom_free_hash_ops test took 2.621675s string_hash_ops test took 2.334675s custom_free_hash_ops test took 2.601568s So the test is noisy, but there clearly is no significant difference with the "fast path" restored. I'm surprised by this, but it shows that the current "safe" implementation does not cause a performance loss. When the code is compiled with optimization, those times are significantly lower (e.g. 1.1s and 1.4s), but again, there is no difference with the "fast path" restored. The difference between string_hash_ops and custom_free_hash_ops is the additional cost of global modification and the extra function call. --- src/test/test-hashmap-plain.c | 49 +++++++++++++++++++++++++++++++++++++++++++ src/test/test-hashmap.c | 9 ++++++++ 2 files changed, 58 insertions(+) (limited to 'src') diff --git a/src/test/test-hashmap-plain.c b/src/test/test-hashmap-plain.c index 039c0e0e5..5376aa84c 100644 --- a/src/test/test-hashmap-plain.c +++ b/src/test/test-hashmap-plain.c @@ -3,6 +3,7 @@ #include "alloc-util.h" #include "hashmap.h" #include "log.h" +#include "stdio-util.h" #include "string-util.h" #include "strv.h" #include "tests.h" @@ -782,6 +783,53 @@ static void test_hashmap_many(void) { } } +extern unsigned custom_counter; +extern const struct hash_ops boring_hash_ops, custom_hash_ops; + +static void test_hashmap_free(void) { + Hashmap *h; + bool slow = slow_tests_enabled(); + usec_t ts, n; + char b[FORMAT_TIMESPAN_MAX]; + unsigned n_entries = slow ? 1 << 20 : 240; + + const struct { + const char *title; + const struct hash_ops *ops; + unsigned expect_counter; + } tests[] = { + { "string_hash_ops", &boring_hash_ops, 2 * n_entries}, + { "custom_free_hash_ops", &custom_hash_ops, 0 }, + }; + + log_info("/* %s (%s, %u entries) */", __func__, slow ? "slow" : "fast", n_entries); + + for (unsigned j = 0; j < ELEMENTSOF(tests); j++) { + ts = now(CLOCK_MONOTONIC); + assert_se(h = hashmap_new(tests[j].ops)); + + custom_counter = 0; + for (unsigned i = 0; i < n_entries; i++) { + char s[DECIMAL_STR_MAX(unsigned)]; + char *k, *v; + + xsprintf(s, "%u", i); + assert_se(k = strdup(s)); + assert_se(v = strdup(s)); + custom_counter += 2; + + assert_se(hashmap_put(h, k, v) >= 0); + } + + hashmap_free(h); + + n = now(CLOCK_MONOTONIC); + log_info("%s test took %s", tests[j].title, format_timespan(b, sizeof b, n - ts, 0)); + + assert_se(custom_counter == tests[j].expect_counter); + } +} + static void test_hashmap_first(void) { _cleanup_hashmap_free_ Hashmap *m = NULL; @@ -955,6 +1003,7 @@ void test_hashmap_funcs(void) { test_hashmap_get2(); test_hashmap_size(); test_hashmap_many(); + test_hashmap_free(); test_hashmap_first(); test_hashmap_first_key(); test_hashmap_steal_first_key(); diff --git a/src/test/test-hashmap.c b/src/test/test-hashmap.c index 6f29266d6..ee4c0e66d 100644 --- a/src/test/test-hashmap.c +++ b/src/test/test-hashmap.c @@ -3,6 +3,15 @@ #include "hashmap.h" #include "util.h" +unsigned custom_counter = 0; +static void custom_destruct(void* p) { + custom_counter--; + free(p); +} + +DEFINE_HASH_OPS_FULL(boring_hash_ops, char, string_hash_func, string_compare_func, free, char, free); +DEFINE_HASH_OPS_FULL(custom_hash_ops, char, string_hash_func, string_compare_func, custom_destruct, char, custom_destruct); + void test_hashmap_funcs(void); void test_ordered_hashmap_funcs(void); -- cgit v1.2.3-65-gdbad