Index: rcorder.8 =================================================================== --- rcorder.8 +++ rcorder.8 @@ -41,6 +41,8 @@ .Nm .Op Fl k Ar keep .Op Fl s Ar skip +.Op Fl g +.Op Fl p .Ar .Sh DESCRIPTION The @@ -107,6 +109,12 @@ If any .Fl s option is given, files containing the matching keyword are not listed. +.It Fl g +Produce a GraphViz (.dot) of the complete dependency graph instead of +plaintext calling order list. +.It Fl p +Generate ordering suitable for parallel startup placing files that can be +executed in simultaneously on the same line. .El .Pp An example block follows: @@ -159,18 +167,42 @@ utility may print one of the following error messages and exit with a non-zero status if it encounters an error while processing the file list. .Bl -diag -.It "Requirement %s has no providers, aborting." +.It "Requirement %s in file %s has no providers." No file has a .Dq Li PROVIDE line corresponding to a condition present in a .Dq Li REQUIRE line in another file. -.It "Circular dependency on provision %s, aborting." +.It "Circular dependency on provision %s in file %s." A set of files has a circular dependency which was detected while -processing the stated condition. -.It "Circular dependency on file %s, aborting." +processing the stated condition. Loop visualization follows this message. +.It "Circular dependency on file %s." A set of files has a circular dependency which was detected while processing the stated file. +.It "%s was seen in circular dependencies for %d times." +Each node that was a part of circular dependency loops reports total number of +such encounters. Start with files having biggest counter when fighting with +broken dependencies. +.Sh DIAGNOSTICS WITH GRAPHVIZ +Direct dependency is drawn with solid line, +.Dq Li BEFORE +dependency is drawn as a dashed line. +Each node of a graph represents an item from +.Dq Li PROVIDE +lines. In case there +are more than one file providing an item, a list of filenames shortened with +.Xr basename 3 +is shown. Shortened filenames are also shown in case +.Dq Li PROVIDE +item does not match file name. +.Pp +Edges and nodes where circular dependencies were detected are drawn bold red. +If a file has an item in +.Dq Li REQUIRE +or in +.Dq Li BEFORE +that could not be provided, +this missing provirer and the requirement will be drawn bold red as well. .El .Sh SEE ALSO .Xr acpiconf 8 , Index: rcorder.c =================================================================== --- rcorder.c +++ rcorder.c @@ -48,6 +48,7 @@ #include #include #include +#include #include "ealloc.h" #include "sprite.h" @@ -75,6 +76,8 @@ #define KEYWORDS_STR "# KEYWORDS:" #define KEYWORDS_LEN (sizeof(KEYWORDS_STR) - 1) +#define FAKE_PROV_NAME "fake_prov_" + static int exit_code; static int file_count; static char **file_list; @@ -86,6 +89,9 @@ #define SET TRUE #define RESET FALSE +static flag do_graphviz = RESET; +static flag do_parallel = RESET; + static Hash_Table provide_hash_s, *provide_hash; typedef struct provnode provnode; @@ -97,12 +103,14 @@ struct provnode { flag head; flag in_progress; + int sequence; filenode *fnode; provnode *next, *last; }; struct f_provnode { provnode *pnode; + Hash_Entry *entry; f_provnode *next; }; @@ -124,9 +132,11 @@ f_reqnode *req_list; f_provnode *prov_list; strnodelist *keyword_list; + int issues_count; + int sequence; }; -static filenode fn_head_s, *fn_head; +static filenode fn_head_s, *fn_head, **fn_seqlist; static strnodelist *bl_list; static strnodelist *keep_list; @@ -136,7 +146,8 @@ static void strnode_add(strnodelist **, char *, filenode *); static int skip_ok(filenode *fnode); static int keep_ok(filenode *fnode); -static void satisfy_req(f_reqnode *rnode, char *filename); +static char *print_loop_for_req(strnodelist *, provnode *, filenode *); +static void satisfy_req(f_reqnode *rnode, filenode *fnode); static void crunch_file(char *); static void parse_require(filenode *, char *); static void parse_provide(filenode *, char *); @@ -151,6 +162,10 @@ static Hash_Entry *make_fake_provision(filenode *); static void crunch_all_files(void); static void initialize(void); +static void generate_graphvis_header(void); +static void generate_graphvis_footer(void); +static void generate_graphviz_file_links(Hash_Entry *, filenode *); +static void generate_graphviz_providers(void); static void generate_ordering(void); int @@ -158,7 +173,7 @@ { int ch; - while ((ch = getopt(argc, argv, "dk:s:")) != -1) + while ((ch = getopt(argc, argv, "dk:s:gp")) != -1) switch (ch) { case 'd': #ifdef DEBUG @@ -173,6 +188,12 @@ case 's': strnode_add(&skip_list, optarg, 0); break; + case 'g': + do_graphviz = SET; + break; + case 'p': + do_parallel = SET; + break; default: /* XXX should crunch it? */ break; @@ -186,10 +207,13 @@ DPRINTF((stderr, "parse_args\n")); initialize(); DPRINTF((stderr, "initialize\n")); + generate_graphvis_header(); crunch_all_files(); DPRINTF((stderr, "crunch_all_files\n")); + generate_graphviz_providers(); generate_ordering(); DPRINTF((stderr, "generate_ordering\n")); + generate_graphvis_footer(); exit(exit_code); } @@ -295,6 +319,7 @@ head->head = SET; head->in_progress = RESET; head->fnode = NULL; + head->sequence = 0; head->last = head->next = NULL; Hash_SetValue(entry, head); } @@ -350,6 +375,7 @@ f_pnode = emalloc(sizeof(*f_pnode)); f_pnode->pnode = pnode; + f_pnode->entry = entry; f_pnode->next = fnode->prov_list; fnode->prov_list = f_pnode; } @@ -522,7 +548,7 @@ char buffer[30]; do { - snprintf(buffer, sizeof buffer, "fake_prov_%08d", i++); + snprintf(buffer, sizeof buffer, FAKE_PROV_NAME "%08d", i++); entry = Hash_CreateEntry(provide_hash, buffer, &new); } while (new == 0); head = emalloc(sizeof(*head)); @@ -543,6 +569,7 @@ pnode->next->last = pnode; f_pnode = emalloc(sizeof(*f_pnode)); + f_pnode->entry = entry; f_pnode->pnode = pnode; f_pnode->next = node->prov_list; node->prov_list = f_pnode; @@ -575,6 +602,11 @@ if (new == 1) warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s); + if (new == 1 && do_graphviz == SET) + generate_graphviz_file_links( + Hash_FindEntry(provide_hash, bl_list->s), + bl_list->node); + for (pnode = Hash_GetValue(entry); pnode; pnode = pnode->next) { if (pnode->head) continue; @@ -605,6 +637,113 @@ insert_before(); } +/* loop though povide list of vnode drawing all non-fake dependencies */ +static void +generate_graphviz_file_links(Hash_Entry *entry, filenode *fnode) +{ + char *dep_name, *fname; + provnode *head; + f_provnode *fpnode, *rfpnode; + int is_before = 0; + + dep_name = Hash_GetKey(entry); + if (dep_name == strstr(dep_name, FAKE_PROV_NAME)) + is_before = 1; + head = Hash_GetValue(entry); + + for (fpnode = fnode->prov_list; fpnode && fpnode->entry; + fpnode = fpnode->next) { + fname = Hash_GetKey(fpnode->entry); + if (fname == strstr(fname, FAKE_PROV_NAME)) + continue; + rfpnode = NULL; + do { + if (rfpnode) + dep_name = Hash_GetKey(rfpnode->entry); + else + dep_name = Hash_GetKey(entry); + + if (dep_name != strstr(dep_name, FAKE_PROV_NAME)) { + printf("\"%s\" -> \"%s\" [%s%s];\n", + fname, dep_name, + /* edge style */ + (is_before ? "style=dashed" : "style=solid"), + /* circular dep? */ + ((head == NULL || + (head->next && head->in_progress == SET)) ? + ", color=red, penwidth=4" : "")); + if (rfpnode == NULL) + break; + } + /* dependency is solved already */ + if (head == NULL || head->next == NULL) + break; + + if (rfpnode == NULL) + rfpnode = head->next->fnode->prov_list; + else + rfpnode = rfpnode->next; + } while(rfpnode); + } +} + +static char * +print_loop_for_req(strnodelist *stack_head, provnode *head, + filenode *fnode) +{ + provnode *pnode; + strnodelist *stack_ptr, *loop_entry; + char *buf; + size_t bufsize; + + loop_entry = NULL; + /* fast forward stack to the component that is required now */ + for (pnode = head->next; pnode; pnode = pnode->next) { + if (loop_entry) + break; + stack_ptr = stack_head->next; + while(stack_ptr) { + if (stack_ptr->node == pnode->fnode) { + loop_entry = stack_ptr; + break; + } + stack_ptr = stack_ptr->next; + } + } + + if (loop_entry == NULL) + return (NULL); + + /* estimate buffer size to allocate */ + stack_ptr = loop_entry; + bufsize = 0; + while(stack_ptr) { + bufsize += strlen(stack_ptr->node->filename); + bufsize += sizeof(" -> "); + stack_ptr = stack_ptr->next; + } + + bufsize += strlen(fnode->filename); + bufsize += sizeof(" -> "); + bufsize += strlen(loop_entry->node->filename); + + buf = emalloc(bufsize); + bzero(buf, bufsize); + stack_ptr = loop_entry; + while(stack_ptr) { + stack_ptr->node->issues_count++; + strlcat(buf, stack_ptr->node->filename, bufsize); + strlcat(buf, " -> ", bufsize); + stack_ptr = stack_ptr->next; + } + + strlcat(buf, fnode->filename, bufsize); + fnode->issues_count++; + strlcat(buf, " -> ", bufsize); + strlcat(buf, loop_entry->node->filename, bufsize); + + return (buf); +} /* * below are the functions that traverse the graphs we have built * finding out the desired ordering, printing each file in turn. @@ -621,17 +760,23 @@ * provision. */ static void -satisfy_req(f_reqnode *rnode, char *filename) +satisfy_req(f_reqnode *rnode, filenode *fnode) { Hash_Entry *entry; provnode *head; + static strnodelist req_stack_head = { NULL, NULL, "" /* unused */ }; + strnodelist *stack_ptr; + char *buf; entry = rnode->entry; head = Hash_GetValue(entry); + if (do_graphviz == SET) + generate_graphviz_file_links(entry, fnode); + if (head == NULL) { warnx("requirement `%s' in file `%s' has no providers.", - Hash_GetKey(entry), filename); + Hash_GetKey(entry), fnode->filename); exit_code = 1; return; } @@ -645,20 +790,43 @@ * print that there is a circular dependency on it and abort */ if (head->in_progress == SET) { - warnx("Circular dependency on provision `%s' in file `%s'.", - Hash_GetKey(entry), filename); exit_code = 1; + buf = print_loop_for_req(&req_stack_head, head, + fnode); + + if (buf == NULL) { + warnx("Circular dependency on provision `%s' in " + "file `%s' (tracing has failed).", + Hash_GetKey(entry), fnode->filename); + return; + } + + warnx("Circular dependency on provision `%s': %s.", + Hash_GetKey(entry), buf); + free(buf); return; } head->in_progress = SET; + + stack_ptr = &req_stack_head; + while(stack_ptr->next) + stack_ptr = stack_ptr->next; + stack_ptr->next = emalloc(sizeof(*stack_ptr)); + bzero(stack_ptr->next, sizeof(*stack_ptr)); + stack_ptr->next->node = fnode; + /* * while provision_list is not empty * do_file(first_member_of(provision_list)); */ while (head->next != NULL) do_file(head->next->fnode); + + stack_ptr->next->node = NULL; + free(stack_ptr->next); + stack_ptr->next = NULL; } static int @@ -707,6 +875,9 @@ f_provnode *p, *p_tmp; provnode *pnode; int was_set; + char *dep_name; + provnode *head; + static int max_sequence = 0; DPRINTF((stderr, "do_file on %s.\n", fnode->filename)); @@ -729,18 +900,43 @@ * satisfy_req(r, filename) */ r = fnode->req_list; + fnode->sequence = 0; while (r != NULL) { - satisfy_req(r, fnode->filename); + satisfy_req(r, fnode); + /* find sequence number where all requirements are satisfied */ + head = Hash_GetValue(r->entry); + if (head && head->sequence > fnode->sequence) + fnode->sequence = head->sequence; r = r->next; } fnode->req_list = NULL; + fnode->sequence++; + /* if we've seen issues with this file - put it to the tail */ + if (fnode->issues_count) + fnode->sequence = max_sequence + 1; + + if (max_sequence < fnode->sequence) + max_sequence = fnode->sequence; + /* * for each provision of fnode -> p * remove fnode from provision list for p in hash table */ p = fnode->prov_list; while (p != NULL) { + if (do_graphviz == SET && fnode->issues_count) { + dep_name = Hash_GetKey(p->entry); + if (dep_name != strstr(dep_name, FAKE_PROV_NAME)) + printf("\"%s\" [ color=red, penwidth=4 ];\n", + dep_name); + } + + /* update sequence when provided requirements are satisfied */ + head = Hash_GetValue(p->entry); + if (head->sequence < fnode->sequence) + head->sequence = fnode->sequence; + p_tmp = p; pnode = p->pnode; if (pnode->next != NULL) { @@ -759,8 +955,11 @@ DPRINTF((stderr, "next do: ")); /* if we were already in progress, don't print again */ - if (was_set == 0 && skip_ok(fnode) && keep_ok(fnode)) - printf("%s\n", fnode->filename); + if (do_graphviz != SET && was_set == 0 && skip_ok(fnode) && + keep_ok(fnode)) { + *fn_seqlist = fnode; + fn_seqlist++; + } if (fnode->next != NULL) { fnode->next->last = fnode->last; @@ -769,19 +968,102 @@ fnode->last->next = fnode->next; } + if (fnode->issues_count) + warnx("`%s' was seen in circular dependencies for %d times.", + fnode->filename, fnode->issues_count); + DPRINTF((stderr, "nuking %s\n", fnode->filename)); -#if 0 - if (was_set == 0) { - free(fnode->filename); - free(fnode); - } -#endif } static void +generate_graphvis_header() +{ + if (do_graphviz != SET) + return; + + printf("digraph rcorder {\n" + "rankdir=\"BT\";\n" + "node [style=rounded, shape=record];\n" + "graph [overlap = false];\n"); +} + +static void +generate_graphvis_footer() +{ + if (do_graphviz == SET) + printf("}\n"); +} + +static void +generate_graphviz_providers() +{ + Hash_Entry *entry; + Hash_Search pserarch; + provnode *head, *pnode; + char *dep_name; + + if (do_graphviz != SET) + return; + + entry = Hash_EnumFirst(provide_hash, &pserarch); + if (entry == NULL) + return; + + do { + dep_name = Hash_GetKey(entry); + if (dep_name == strstr(dep_name, FAKE_PROV_NAME)) + continue; + head = Hash_GetValue(entry); + /* no providers for this requirement */ + if (head == NULL || head->next == NULL) { + printf("\"%s\" [label=\"{ %s | ENOENT }\", " + "style=\"rounded,filled\", color=red];\n", + dep_name, dep_name); + continue; + } + /* one PROVIDE word for one file that matches */ + if (head->next->next == NULL && + strcmp(dep_name, + basename(head->next->fnode->filename)) == 0) { + continue; + } + printf("\"%s\" [label=\"{ %s | ", dep_name, dep_name); + for (pnode = head->next; pnode; pnode = pnode->next) + printf("%s\\n", basename(pnode->fnode->filename)); + + printf("}\"];\n"); + } while(NULL != (entry = Hash_EnumNext(&pserarch))); +} + +static int +sequence_cmp(const void *a, const void *b) +{ + filenode *fna = NULL, *fnb = NULL; + /* make compiler hapy with void * -> void ** conversion */ + memcpy(&fna, a, sizeof(filenode *)); + memcpy(&fnb, b, sizeof(filenode *)); + + /* push phantom files to the end */ + if (fna == NULL || fnb == NULL) + return (fna < fnb) - (fna > fnb); + + const int left = fna->sequence; + const int right = fnb->sequence; + + return (left > right) - (left < right); +} + +static void generate_ordering(void) { + filenode **seqlist, **psl; + int last_seq = 0; + /* Prepare order buffer */ + seqlist = emalloc(sizeof(filenode *) * (file_count + 1)); + bzero(seqlist, sizeof(filenode *) * (file_count + 1)); + fn_seqlist = seqlist; + /* * while there remain undone files{f}, * pick an arbitrary f, and do_file(f) @@ -800,4 +1082,22 @@ DPRINTF((stderr, "generate on %s\n", fn_head->next->filename)); do_file(fn_head->next); } + + /* Sort filenode list based on sequence */ + qsort(seqlist, file_count, sizeof(filenode *), sequence_cmp); + + for (psl = seqlist; *psl; psl++) { + printf("%s%s", + (last_seq == 0 ? "" : + (do_parallel != SET || last_seq != (*psl)->sequence) ? + "\n" : " "), + (*psl)->filename); + last_seq = (*psl)->sequence; + free((*psl)->filename); + free(*psl); + } + if (last_seq) + printf("\n"); + + free(seqlist); }