X-Git-Url: https://git.lttng.org/?a=blobdiff_plain;f=tests%2Ftest_urcu_ja.c;h=05725275cffaa0781e8bf8636c206e833b7db6bd;hb=5bcf8326b6e13ca93429925bc38fb81c73155c54;hp=c85d20610c566aacd596aa0157528e4e169fb474;hpb=5b62a42a6295b4a30b5e82ebe54e8f40b8a0b3a3;p=userspace-rcu.git diff --git a/tests/test_urcu_ja.c b/tests/test_urcu_ja.c index c85d206..0572527 100644 --- a/tests/test_urcu_ja.c +++ b/tests/test_urcu_ja.c @@ -223,13 +223,40 @@ printf(" [not -u nor -s] Add entries (supports redundant keys).\n"); printf("\n\n"); } +static +int test_free_all_nodes(struct cds_ja *ja) +{ + uint64_t key; + struct cds_ja_node *ja_node; + int ret = 0; + + rcu_read_lock(); + cds_ja_for_each_key_rcu(test_ja, key, ja_node) { + struct cds_ja_node *tmp_node; + + cds_ja_for_each_duplicate_safe_rcu(ja_node, tmp_node) { + ret = cds_ja_del(test_ja, key, ja_node); + if (ret) { + fprintf(stderr, "Error (%d) removing node %" PRIu64 "\n", ret, key); + goto end; + } + /* Alone using Judy array, OK to free now */ + free_node(ja_node); + } + } +end: + rcu_read_unlock(); + return ret; +} + static int test_8bit_key(void) { int ret, i; uint64_t key; - uint64_t ka[] = { 4, 17, 100, 222 }; + uint64_t ka[] = { 5, 17, 100, 222 }; uint64_t ka_test_offset = 5; + struct cds_ja_node *ja_node; /* Test with 8-bit key */ test_ja = cds_ja_new(8); @@ -257,11 +284,9 @@ int test_8bit_key(void) printf("Test #2: successful key lookup (8-bit).\n"); for (key = 0; key < 200; key++) { - struct cds_ja_node *node; - rcu_read_lock(); - node = cds_ja_lookup(test_ja, key); - if (!node) { + ja_node = cds_ja_lookup(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } @@ -270,11 +295,9 @@ int test_8bit_key(void) printf("OK\n"); printf("Test #3: unsuccessful key lookup (8-bit).\n"); for (key = 200; key < 240; key++) { - struct cds_ja_node *node; - rcu_read_lock(); - node = cds_ja_lookup(test_ja, key); - if (node) { + ja_node = cds_ja_lookup(test_ja, key); + if (ja_node) { fprintf(stderr, "Error unexpected lookup node %" PRIu64 "\n", key); @@ -285,7 +308,6 @@ int test_8bit_key(void) printf("OK\n"); printf("Test #4: remove keys (8-bit).\n"); for (key = 0; key < 200; key++) { - struct cds_ja_node *ja_node; struct ja_test_node *node; rcu_read_lock(); @@ -310,7 +332,7 @@ int test_8bit_key(void) } printf("OK\n"); - printf("Test #5: lookup lower equal (8-bit).\n"); + printf("Test #5: lookup below/above equal (8-bit).\n"); for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct ja_test_node *node = node_alloc(); @@ -328,42 +350,76 @@ int test_8bit_key(void) } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i] + ka_test_offset; rcu_read_lock(); - ja_node = cds_ja_lookup_lower_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { - fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", + fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); + assert(0); + } + rcu_read_unlock(); + } + + for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { + struct ja_test_node *node; + uint64_t result_key; + + key = ka[i] - ka_test_offset; + rcu_read_lock(); + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); + if (!ja_node) { + fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", + ka[i], key); + assert(0); + } + node = caa_container_of(ja_node, struct ja_test_node, node); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i]; /* without offset */ rcu_read_lock(); - ja_node = cds_ja_lookup_lower_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { - fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", + fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); + assert(0); + } + + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); + if (!ja_node) { + fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", + ka[i], key); + assert(0); + } + node = caa_container_of(ja_node, struct ja_test_node, node); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -371,7 +427,13 @@ int test_8bit_key(void) printf("OK\n"); - ret = cds_ja_destroy(test_ja, free_node); + ret = test_free_all_nodes(test_ja); + if (ret) { + fprintf(stderr, "Error freeing all nodes\n"); + return -1; + } + + ret = cds_ja_destroy(test_ja); if (ret) { fprintf(stderr, "Error destroying judy array\n"); return -1; @@ -384,8 +446,9 @@ int test_16bit_key(void) { int ret, i; uint64_t key; - uint64_t ka[] = { 4, 105, 222, 4000, 4111, 59990, 65435 }; + uint64_t ka[] = { 105, 206, 4000, 4111, 59990, 65435 }; uint64_t ka_test_offset = 100; + struct cds_ja_node *ja_node; /* Test with 16-bit key */ test_ja = cds_ja_new(16); @@ -415,11 +478,11 @@ int test_16bit_key(void) printf("Test #2: successful key lookup (16-bit).\n"); for (key = 0; key < 10000; key++) { //for (key = 0; key < 65536; key+=256) { - struct cds_ja_node *node; + struct cds_ja_node *ja_node; rcu_read_lock(); - node = cds_ja_lookup(test_ja, key); - if (!node) { + ja_node = cds_ja_lookup(test_ja, key); + if (!ja_node) { fprintf(stderr, "Error lookup node %" PRIu64 "\n", key); assert(0); } @@ -428,11 +491,11 @@ int test_16bit_key(void) printf("OK\n"); printf("Test #3: unsuccessful key lookup (16-bit).\n"); for (key = 11000; key <= 11002; key++) { - struct cds_ja_node *node; + struct cds_ja_node *ja_node; rcu_read_lock(); - node = cds_ja_lookup(test_ja, key); - if (node) { + ja_node = cds_ja_lookup(test_ja, key); + if (ja_node) { fprintf(stderr, "Error unexpected lookup node %" PRIu64 "\n", key); @@ -444,7 +507,6 @@ int test_16bit_key(void) printf("Test #4: remove keys (16-bit).\n"); for (key = 0; key < 10000; key++) { //for (key = 0; key < 65536; key+=256) { - struct cds_ja_node *ja_node; struct ja_test_node *node; rcu_read_lock(); @@ -469,7 +531,7 @@ int test_16bit_key(void) } printf("OK\n"); - printf("Test #5: lookup lower equal (16-bit).\n"); + printf("Test #5: lookup below/above equal (16-bit).\n"); for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { struct ja_test_node *node = node_alloc(); @@ -487,42 +549,76 @@ int test_16bit_key(void) } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i] + ka_test_offset; rcu_read_lock(); - ja_node = cds_ja_lookup_lower_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { - fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", + fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); + assert(0); + } + rcu_read_unlock(); + } + + for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { + struct ja_test_node *node; + uint64_t result_key; + + key = ka[i] - ka_test_offset; + rcu_read_lock(); + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); + if (!ja_node) { + fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n", + ka[i], key); + assert(0); + } + node = caa_container_of(ja_node, struct ja_test_node, node); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); } for (i = 0; i < CAA_ARRAY_SIZE(ka); i++) { - struct cds_ja_node *ja_node; struct ja_test_node *node; + uint64_t result_key; key = ka[i]; /* without offset */ rcu_read_lock(); - ja_node = cds_ja_lookup_lower_equal(test_ja, key); + ja_node = cds_ja_lookup_below_equal(test_ja, key, &result_key); if (!ja_node) { - fprintf(stderr, "Error lookup lower equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", + fprintf(stderr, "Error lookup below equal. Cannot find expected key %" PRIu64" below or equal to %" PRIu64 ".\n", ka[i], key); assert(0); } node = caa_container_of(ja_node, struct ja_test_node, node); - if (node->key != ka[i]) { - fprintf(stderr, "Error lookup lower equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 " instead.\n", - ka[i], key, node->key); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup below equal. Expecting key %" PRIu64 " below or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); + assert(0); + } + + ja_node = cds_ja_lookup_above_equal(test_ja, key, &result_key); + if (!ja_node) { + fprintf(stderr, "Error lookup above equal. Cannot find expected key %" PRIu64" above or equal to %" PRIu64 ".\n", + ka[i], key); + assert(0); + } + node = caa_container_of(ja_node, struct ja_test_node, node); + if (node->key != ka[i] || result_key != ka[i]) { + fprintf(stderr, "Error lookup above equal. Expecting key %" PRIu64 " above or equal to %" PRIu64 ", but found %" PRIu64 "/%" PRIu64" instead.\n", + ka[i], key, node->key, result_key); assert(0); } rcu_read_unlock(); @@ -530,7 +626,13 @@ int test_16bit_key(void) printf("OK\n"); - ret = cds_ja_destroy(test_ja, free_node); + ret = test_free_all_nodes(test_ja); + if (ret) { + fprintf(stderr, "Error freeing all nodes\n"); + return -1; + } + + ret = cds_ja_destroy(test_ja); if (ret) { fprintf(stderr, "Error destroying judy array\n"); return -1; @@ -546,6 +648,7 @@ int test_sparse_key(unsigned int bits, int nr_dup) { uint64_t key, max_key; int zerocount, i, ret; + struct cds_ja_node *ja_node; if (bits == 64) max_key = UINT64_MAX; @@ -585,7 +688,6 @@ int test_sparse_key(unsigned int bits, int nr_dup) printf("Test #2: successful key lookup (%u-bit).\n", bits); zerocount = 0; for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) { - struct cds_ja_node *ja_node; struct ja_test_node *node; int count = 0; @@ -610,8 +712,6 @@ int test_sparse_key(unsigned int bits, int nr_dup) printf("Test #3: unsuccessful key lookup (%u-bit).\n", bits); zerocount = 0; for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) { - struct cds_ja_node *ja_node; - rcu_read_lock(); ja_node = cds_ja_lookup(test_ja, key + 42); if (ja_node) { @@ -629,7 +729,6 @@ int test_sparse_key(unsigned int bits, int nr_dup) printf("Test #4: remove keys (%u-bit).\n", bits); zerocount = 0; for (key = 0; key <= max_key && (key != 0 || zerocount < 1); key += 1ULL << (bits - 8)) { - struct cds_ja_node *ja_node; int count = 0; rcu_read_lock(); @@ -665,7 +764,13 @@ int test_sparse_key(unsigned int bits, int nr_dup) } printf("OK\n"); - ret = cds_ja_destroy(test_ja, free_node); + ret = test_free_all_nodes(test_ja); + if (ret) { + fprintf(stderr, "Error freeing all nodes\n"); + return -1; + } + + ret = cds_ja_destroy(test_ja); if (ret) { fprintf(stderr, "Error destroying judy array\n"); return -1; @@ -745,8 +850,10 @@ void *test_ja_rw_thr_reader(void *_count) struct cds_ja_node *ja_node; uint64_t key; - printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", - "reader", pthread_self(), (unsigned long) gettid()); + printf_verbose("thread_begin %s, tid %lu\n", + "reader", urcu_get_thread_id()); + + URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL); set_affinity(); @@ -787,8 +894,8 @@ void *test_ja_rw_thr_reader(void *_count) rcu_unregister_thread(); *count = URCU_TLS(nr_reads); - printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", - "reader", pthread_self(), (unsigned long) gettid()); + printf_verbose("thread_end %s, tid %lu\n", + "reader", urcu_get_thread_id()); printf_verbose("readid : %lx, lookupfail %lu, lookupok %lu\n", pthread_self(), URCU_TLS(lookup_fail), URCU_TLS(lookup_ok)); @@ -808,8 +915,10 @@ void *test_ja_rw_thr_writer(void *_count) uint64_t key; int ret; - printf_verbose("thread_begin %s, thread id : %lx, tid %lu\n", - "writer", pthread_self(), (unsigned long) gettid()); + printf_verbose("thread_begin %s, tid %lu\n", + "writer", urcu_get_thread_id()); + + URCU_TLS(rand_lookup) = urcu_get_thread_id() ^ time(NULL); set_affinity(); @@ -891,8 +1000,8 @@ void *test_ja_rw_thr_writer(void *_count) rcu_unregister_thread(); - printf_verbose("thread_end %s, thread id : %lx, tid %lu\n", - "writer", pthread_self(), (unsigned long) gettid()); + printf_verbose("thread_end %s, tid %lu\n", + "writer", urcu_get_thread_id()); printf_verbose("info id %lx: nr_add %lu, nr_addexist %lu, nr_del %lu, " "nr_delnoent %lu\n", pthread_self(), URCU_TLS(nr_add), URCU_TLS(nr_addexist), URCU_TLS(nr_del), @@ -928,6 +1037,9 @@ int do_mt_populate_ja(void) URCU_TLS(nr_add)++; URCU_TLS(nr_writes)++; rcu_read_unlock(); + /* Hash table resize only occurs in call_rcu thread */ + if (!(iter % 100)) + rcu_quiescent_state(); if (ret) { fprintf(stderr, "Error (%d) adding node %" PRIu64 "\n", ret, key); @@ -1011,7 +1123,13 @@ int do_mt_test(void) } rcu_thread_online_qsbr(); - ret = cds_ja_destroy(test_ja, free_node); + ret = test_free_all_nodes(test_ja); + if (ret) { + fprintf(stderr, "Error freeing all nodes\n"); + return -1; + } + + ret = cds_ja_destroy(test_ja); if (ret) { fprintf(stderr, "Error destroying judy array\n"); goto end; @@ -1176,8 +1294,8 @@ int main(int argc, char **argv) printf_verbose("Validating lookups.\n"); if (leak_detection) printf_verbose("Memory leak dection activated.\n"); - printf_verbose("thread %-6s, thread id : %lx, tid %lu\n", - "main", pthread_self(), (unsigned long)gettid()); + printf_verbose("thread %-6s, tid %lu\n", + "main", urcu_get_thread_id()); memset(&act, 0, sizeof(act)); ret = sigemptyset(&act.sa_mask);