From c0d3d1808dd63d83560f5c28095644a4af651e32 Mon Sep 17 00:00:00 2001 From: Alberto Leiva Popper Date: Tue, 19 Sep 2023 18:08:15 -0600 Subject: [PATCH] Testing on the local cache code - Recover from more errors - Test more error paths --- src/cache/local_cache.c | 240 ++++++++++++++++++++++------------ test/cache/local_cache_test.c | 187 ++++++++++++++++++++++++-- 2 files changed, 327 insertions(+), 100 deletions(-) diff --git a/src/cache/local_cache.c b/src/cache/local_cache.c index bdf08f74..c879e93c 100644 --- a/src/cache/local_cache.c +++ b/src/cache/local_cache.c @@ -484,50 +484,6 @@ end: return error; } -static struct cache_node * -find_next(struct cache_node *sibling, struct cache_node *parent) -{ - if (sibling != NULL) - return sibling; - - while (parent != NULL) { - while (!parent->children) { - sibling = parent; - parent = sibling->parent; - delete_node(sibling); - if (parent == NULL) - return NULL; - } - - sibling = parent->hh.next; - if (sibling) - return sibling; - - parent = parent->parent; - } - - return NULL; -} - -static void cleanup_nodes(struct cache_node *node) -{ - struct cache_node *parent, *next; - - while (node != NULL) { - if (was_recently_downloaded(node) && !node->error) { - drop_children(node); - node = find_next(node->hh.next, node->parent); - } else if (node->children) { - node = node->children; - } else { - parent = node->parent; - next = node->hh.next; - delete_node(node); - node = find_next(next, parent); - } - } -} - /* * @force: ignore nonexistent files */ @@ -541,39 +497,149 @@ pb_rm_r(struct path_builder *pb, char const *filename, bool force) pr_op_err("Cannot delete %s: %s", pb->string, strerror(error)); } -/* Safe removal, Postorder */ +enum ctt_status { + CTTS_STILL, + CTTS_UP, + CTTS_DOWN, +}; + struct cache_tree_traverser { - struct path_builder *pb; + struct cache_node **root; struct cache_node *next; - bool next_sibling; + struct path_builder *pb; + enum ctt_status status; }; static void -ctt_init(struct cache_tree_traverser *ctt, struct cache_node *node, +ctt_init(struct cache_tree_traverser *ctt, struct cache_node **root, struct path_builder *pb) { - if (node == NULL) { - ctt->next = NULL; - return; - } + struct cache_node *node; - /* FIXME test these error paths */ - while (node->children != NULL) { - if (pb_append(pb, node->basename) != 0) { - node = node->parent; - goto end; - } - node = node->children; - } - if (pb_append(pb, "a") != 0) + node = *root; + if (node != NULL && (pb_append(pb, "a") != 0)) node = node->parent; -end: - ctt->pb = pb; + ctt->root = root; ctt->next = node; - ctt->next_sibling = true; + ctt->pb = pb; + ctt->status = CTTS_DOWN; +} + +static bool +is_node_fresh(struct cache_node *node) +{ + return was_recently_downloaded(node) && !node->error; +} + +/* + * Assumes @node has not been added to the pb. + */ +static struct cache_node * +ctt_delete(struct cache_tree_traverser *ctt, struct cache_node *node) +{ + struct cache_node *parent, *sibling; + + sibling = node->hh.next; + parent = node->parent; + + delete_node(node); + + if (sibling != NULL) { + ctt->status = CTTS_DOWN; + return sibling; + } + + if (parent != NULL) { + ctt->status = CTTS_UP; + return parent; + } + + *ctt->root = NULL; + return NULL; +} + +/* + * Assumes @node is not NULL, has yet to be traversed, and is already included + * in the pb. + */ +static struct cache_node * +go_up(struct cache_tree_traverser *ctt, struct cache_node *node) +{ + if (node->children == NULL && !is_node_fresh(node)) { + pb_pop(ctt->pb, true); + return ctt_delete(ctt, node); + } + + ctt->status = CTTS_STILL; + return node; +} + +static struct cache_node * +find_first_viable_child(struct cache_tree_traverser *ctt, + struct cache_node *node) +{ + struct cache_node *child, *tmp; + + HASH_ITER(hh, node->children, child, tmp) { + if (pb_append(ctt->pb, child->basename) == 0) + return child; + delete_node(child); /* Unviable */ + } + + return NULL; +} + +/* + * Assumes @node is not NULL, has yet to be traversed, and has not yet been + * added to the pb. + */ +static struct cache_node * +go_down(struct cache_tree_traverser *ctt, struct cache_node *node) +{ + struct cache_node *child; + + if (pb_append(ctt->pb, node->basename) != 0) + return ctt_delete(ctt, node); + + do { + if (is_node_fresh(node)) { + drop_children(node); + ctt->status = CTTS_STILL; + return node; + } + + child = find_first_viable_child(ctt, node); + if (child == NULL) { + /* Welp; stale and no children. */ + ctt->status = CTTS_UP; + return node; + } + + node = child; + } while (true); } +/* + * - Depth-first, post-order, non-recursive, safe [1] traversal. + * - However, deletion is the only allowed modification during the traversal. + * - If the node is fresh [2], it will have no children. + * (Because they would be redundant.) + * (Childless nodes do not imply corresponding childless directories.) + * - If the node is not fresh, it WILL have children. + * (Stale [3] nodes are always sustained by fresh descendant nodes.) + * - The ctt will automatically clean up unviable [4] and unsustained stale + * nodes during the traversal, caller doesn't have to worry about them. + * - The ctt's pb will be updated at all times, caller should not modify the + * string. + * + * [1] Safe = caller can delete the returned node via delete_node(), during + * iteration. + * [2] Fresh = Mapped to a file or directory that was downloaded/updated + * successfully at some point since the beginning of the iteration. + * [3] Stale = Not fresh + * [4] Unviable = Node's path is too long, ie. cannot be mapped to a cache file. + */ static struct cache_node * ctt_next(struct cache_tree_traverser *ctt) { @@ -583,44 +649,45 @@ ctt_next(struct cache_tree_traverser *ctt) return NULL; pb_pop(ctt->pb, true); - if (ctt->next_sibling) - pb_append(ctt->pb, next->basename); /* FIXME */ + + do { + if (ctt->status == CTTS_DOWN) + next = go_down(ctt, next); + else if (ctt->status == CTTS_UP) + next = go_up(ctt, next); + + if (next == NULL) { + ctt->next = NULL; + return NULL; + } + } while (ctt->status != CTTS_STILL); if (next->hh.next != NULL) { ctt->next = next->hh.next; - ctt->next_sibling = true; + ctt->status = CTTS_DOWN; } else { ctt->next = next->parent; - ctt->next_sibling = false; + ctt->status = CTTS_UP; } return next; } -static void cleanup_files(struct cache_node *node, char const *name) +static void cleanup_tree(struct cache_node **root, char const *treename) { struct cache_tree_traverser ctt; struct path_builder pb; struct stat meta; DIR *dir; struct dirent *file; - struct cache_node *child, *tmp; + struct cache_node *node, *child, *tmp; int error; pb_init(&pb); if (pb_append(&pb, config_get_local_repository()) != 0) goto end; - if (node == NULL) { - /* File might exist but node doesn't: Delete file */ - if (pb_append(&pb, name) != 0) - goto end; - pb_rm_r(&pb, name, true); - pb_cleanup(&pb); - return; - } - - ctt_init(&ctt, node, &pb); + ctt_init(&ctt, root, &pb); while ((node = ctt_next(&ctt)) != NULL) { if (stat(pb.string, &meta) != 0) { @@ -633,7 +700,7 @@ static void cleanup_files(struct cache_node *node, char const *name) pr_op_err("Cannot clean up '%s'; stat() returned errno %d: %s", pb.string, error, strerror(error)); - break; + continue; } if (!node->children) @@ -644,6 +711,7 @@ static void cleanup_files(struct cache_node *node, char const *name) /* File is not a directory; welp. */ remove(pb.string); delete_node(node); + continue; } dir = opendir(pb.string); @@ -701,6 +769,8 @@ static void cleanup_files(struct cache_node *node, char const *name) } } + if ((*root) == NULL && pb_append(&pb, treename) == 0) + pb_rm_r(&pb, treename, true); end: pb_cleanup(&pb); } @@ -869,12 +939,8 @@ write_metadata_json(void) void cache_cleanup(void) { - cleanup_nodes(rsync); - cleanup_files(rsync, "rsync"); - - cleanup_nodes(https); - cleanup_files(https, "https"); - + cleanup_tree(&rsync, "rsync"); + cleanup_tree(&https, "https"); write_metadata_json(); } diff --git a/test/cache/local_cache_test.c b/test/cache/local_cache_test.c index 9a6c67d0..84aa132d 100644 --- a/test/cache/local_cache_test.c +++ b/test/cache/local_cache_test.c @@ -233,7 +233,8 @@ search_dir(DIR *parent, char const *path, char const *name) } static void -validate_file(struct cache_node *expected, struct path_builder *pb) +validate_file(struct cache_node *expected, struct path_builder *pb, + char const *tree) { struct stat meta; DIR *dir; @@ -241,8 +242,16 @@ validate_file(struct cache_node *expected, struct path_builder *pb) struct cache_node *child, *tmp; int error; - if (expected == NULL) - return; + if (expected == NULL) { + pb_append(pb, tree); + if (stat(pb->string, &meta) != 0) { + error = errno; + ck_assert_int_eq(ENOENT, error); + pb_pop(pb, true); + return; + } + ck_abort_msg("'%s' exists, but it shouldn't.", pb->string); + } ck_assert_int_eq(0, pb_append(pb, expected->basename)); @@ -285,7 +294,7 @@ must_be_dir: pb->string, file->d_name); } - validate_file(child, pb); + validate_file(child, pb, tree); } error = errno; ck_assert_int_eq(0, error); @@ -309,20 +318,18 @@ validate_trees(struct cache_node *actual, struct cache_node *nodes, print_tree(nodes, 1); printf("Actual nodes:\n"); print_tree(actual, 1); - if (files != NULL) { - if (nodes != files) { - printf("Expected files:\n"); - print_tree(files, 0); - } - printf("Actual files:\n"); - file_ls_R("tmp"); + if (nodes != files) { + printf("Expected files:\n"); + print_tree(files, 0); } + printf("Actual files:\n"); + file_ls_R("tmp"); pb_init(&pb); ck_assert_int_eq(0, pb_append(&pb, "tmp")); validate_node(nodes, NULL, actual, &pb); - validate_file(files, &pb); + validate_file(files, &pb, (actual == rsync) ? "rsync" : "https"); pb_cleanup(&pb); @@ -602,9 +609,12 @@ START_TEST(test_cache_cleanup_rsync) validate_tree(rsync, NULL); /* Node exists, but file doesn't */ + printf("Tmp files:\n"); + file_ls_R("tmp"); __cache_prepare(); download_rsync("rsync://a.b.c/e", 0, 1); download_rsync("rsync://a.b.c/f/g/h", 0, 1); + validate_tree(rsync, NODE("rsync", 0, 0, NODE("a.b.c", 0, 0, @@ -957,6 +967,9 @@ START_TEST(test_metadata_json) json_t *json; char *str; + ck_assert_int_eq(0, system("rm -rf tmp/")); + ck_assert_int_eq(0, system("mkdir tmp/")); + rsync = TNODE("rsync", 0, NOW + 0, NOW + 1, 0, TNODE("a.b.c", 0, NOW + 2, NOW + 3, 0, TNODE("d", SUCCESS, NOW + 4, NOW + 5, 0), @@ -1010,12 +1023,156 @@ START_TEST(test_metadata_json) } END_TEST +#define INIT(_root) \ + pb_init(&pb); \ + root = _root; \ + ctt_init(&ctt, &root, &pb) +#define DONE \ + delete_node(root); \ + pb_cleanup(&pb) + +#define ASSERT_NEXT_NODE(_basename, _path) \ + node = ctt_next(&ctt); \ + ck_assert_ptr_ne(NULL, node); \ + ck_assert_str_eq(_basename, node->basename); \ + ck_assert_str_eq(_path, pb.string) +#define ASSERT_NEXT_NULL ck_assert_ptr_eq(NULL, ctt_next(&ctt)) +#define ASSERT_TREE(_root) validate_trees(root, _root, NULL) + +#define BRANCH(bn, ...) __NODE(bn, 0, 0, 0, 0, __VA_ARGS__, NULL) +#define LEAF(bn) __NODE(bn, CNF_DIRECT, now, now, 0, NULL) + +START_TEST(test_ctt_traversal) +{ + struct cache_tree_traverser ctt; + struct path_builder pb; + struct cache_node *root; + struct cache_node *node; + time_t now; + + ck_assert_int_eq(0, system("rm -rf tmp/")); + + cache_prepare(); + now = time(NULL); + if (now == ((time_t) -1)) + ck_abort_msg("time(NULL) returned -1"); + + INIT(LEAF("a")); + ASSERT_NEXT_NODE("a", "a"); + ASSERT_NEXT_NULL; + ASSERT_TREE(LEAF("a")); + DONE; + + INIT(BRANCH("a", LEAF("b"))); + ASSERT_NEXT_NODE("b", "a/b"); + ASSERT_NEXT_NODE("a", "a"); + ASSERT_NEXT_NULL; + ASSERT_TREE(BRANCH("a", LEAF("b"))); + DONE; + + INIT(BRANCH("a", + BRANCH("b", + BRANCH("c", + LEAF("d"))))); + ASSERT_NEXT_NODE("d", "a/b/c/d"); + ASSERT_NEXT_NODE("c", "a/b/c"); + ASSERT_NEXT_NODE("b", "a/b"); + ASSERT_NEXT_NODE("a", "a"); + ASSERT_NEXT_NULL; + ASSERT_TREE(BRANCH("a", + BRANCH("b", + BRANCH("c", + LEAF("d"))))); + DONE; + + INIT(BRANCH("a", + LEAF("b"), + BRANCH("c", + LEAF("d")), + LEAF("e"))); + ASSERT_NEXT_NODE("b", "a/b"); + ASSERT_NEXT_NODE("d", "a/c/d"); + ASSERT_NEXT_NODE("c", "a/c"); + ASSERT_NEXT_NODE("e", "a/e"); + ASSERT_NEXT_NODE("a", "a"); + ASSERT_NEXT_NULL; + ASSERT_TREE(BRANCH("a", + LEAF("b"), + BRANCH("c", + LEAF("d")), + LEAF("e"))); + DONE; + + INIT(BRANCH("a", + BRANCH("b", + LEAF("c")), + BRANCH("d", + LEAF("e")), + BRANCH("f", + LEAF("g")))); + ASSERT_NEXT_NODE("c", "a/b/c"); + ASSERT_NEXT_NODE("b", "a/b"); + ASSERT_NEXT_NODE("e", "a/d/e"); + ASSERT_NEXT_NODE("d", "a/d"); + ASSERT_NEXT_NODE("g", "a/f/g"); + ASSERT_NEXT_NODE("f", "a/f"); + ASSERT_NEXT_NODE("a", "a"); + ASSERT_NEXT_NULL; + ASSERT_TREE(BRANCH("a", + BRANCH("b", + LEAF("c")), + BRANCH("d", + LEAF("e")), + BRANCH("f", + LEAF("g")))); + DONE; + + INIT(BRANCH("a", + BRANCH("b", + LEAF("c")), + BRANCH("d", + LEAF("e")), + BRANCH("f", + BRANCH("g", NULL)))); + ASSERT_NEXT_NODE("c", "a/b/c"); + ASSERT_NEXT_NODE("b", "a/b"); + ASSERT_NEXT_NODE("e", "a/d/e"); + ASSERT_NEXT_NODE("d", "a/d"); + ASSERT_NEXT_NODE("a", "a"); + ASSERT_NEXT_NULL; + ASSERT_TREE(BRANCH("a", + BRANCH("b", + LEAF("c")), + BRANCH("d", + LEAF("e")))); + DONE; + + INIT(NULL); + ASSERT_NEXT_NULL; + ck_assert_ptr_eq(NULL, root); + DONE; + + INIT(BRANCH("a", NULL)); + ASSERT_NEXT_NULL; + ck_assert_ptr_eq(NULL, root); + DONE; + + INIT(BRANCH("a", + BRANCH("b", NULL), + BRANCH("c", NULL), + BRANCH("d", NULL))); + ASSERT_NEXT_NULL; + ck_assert_ptr_eq(NULL, root); + DONE; +} +END_TEST + /* Boilerplate */ Suite *thread_pool_suite(void) { Suite *suite; - TCase *rsync , *https, *dot, *meta; + TCase *rsync , *https, *dot, *meta, *ctt; rsync = tcase_create("rsync"); tcase_add_test(rsync, test_cache_download_rsync); @@ -1035,11 +1192,15 @@ Suite *thread_pool_suite(void) meta = tcase_create("metadata.json"); tcase_add_test(meta, test_metadata_json); + ctt = tcase_create("ctt"); + tcase_add_test(ctt, test_ctt_traversal); + suite = suite_create("local-cache"); suite_add_tcase(suite, rsync); suite_add_tcase(suite, https); suite_add_tcase(suite, dot); suite_add_tcase(suite, meta); + suite_add_tcase(suite, ctt); return suite; } -- 2.47.3