svn commit: r365449 - head/sbin/rcorder
Mitchell Horne
mhorne at freebsd.org
Tue Sep 8 14:20:33 UTC 2020
Hi,
I think this change warrants an entry in RELNOTES.
Cheers,
Mitchell
On Tue, Sep 8, 2020 at 7:36 AM Andrey V. Elsukov <ae at freebsd.org> wrote:
>
> Author: ae
> Date: Tue Sep 8 10:36:11 2020
> New Revision: 365449
> URL: https://svnweb.freebsd.org/changeset/base/365449
>
> Log:
> Add a few features to rcorder:
>
> o Enhance dependency loop logging: print full chain instead of the
> last link competing the loop;
> o Add -g option to generate dependency graph suitable for GraphViz
> visualization, loops and other graph generation issues are highlighted
> automatically;
> o Add -p option that enables grouping items that can be processed in
> parallel.
>
> Submitted by: Boris Lytochkin <lytboris at gmail>
> Reviewed by: melifaro
> MFC after: 1 week
> Differential Revision: https://reviews.freebsd.org/D25389
>
> Modified:
> head/sbin/rcorder/rcorder.8
> head/sbin/rcorder/rcorder.c
>
> Modified: head/sbin/rcorder/rcorder.8
> ==============================================================================
> --- head/sbin/rcorder/rcorder.8 Tue Sep 8 07:37:45 2020 (r365448)
> +++ head/sbin/rcorder/rcorder.8 Tue Sep 8 10:36:11 2020 (r365449)
> @@ -31,7 +31,7 @@
> .\"
> .\" $FreeBSD$
> .\"
> -.Dd June 22, 2020
> +.Dd September 8, 2020
> .Dt RCORDER 8
> .Os
> .Sh NAME
> @@ -39,6 +39,7 @@
> .Nd print a dependency ordering of interdependent files
> .Sh SYNOPSIS
> .Nm
> +.Op Fl gp
> .Op Fl k Ar keep
> .Op Fl s Ar skip
> .Ar
> @@ -95,6 +96,9 @@ is reached, parsing stops.
> .Pp
> The options are as follows:
> .Bl -tag -width "-k keep"
> +.It Fl g
> +Produce a GraphViz (.dot) of the complete dependency graph instead of
> +plaintext calling order list.
> .It Fl k Ar keep
> Add the specified keyword to the
> .Dq "keep list" .
> @@ -102,6 +106,9 @@ If any
> .Fl k
> option is given, only those files containing the matching keyword are listed.
> This option can be specified multiple times.
> +.It Fl p
> +Generate ordering suitable for parallel startup, placing files that can be
> +executed simultaneously on the same line.
> .It Fl s Ar skip
> Add the specified keyword to the
> .Dq "skip list" .
> @@ -178,19 +185,46 @@ The
> 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
> .Ql PROVIDE
> line corresponding to a condition present in a
> .Ql 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."
> +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.
> .El
> +.Sh DIAGNOSTICS WITH GRAPHVIZ
> +Direct dependency is drawn with solid line,
> +.Ql BEFORE
> +dependency is drawn as a dashed line.
> +Each node of a graph represents an item from
> +.Ql 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
> +.Ql 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
> +.Ql REQUIRE
> +or in
> +.Ql BEFORE
> +that could not be provided,
> +this missing provider and the requirement will be drawn bold red as well.
> .Sh SEE ALSO
> .Xr acpiconf 8 ,
> .Xr rc 8 ,
>
> Modified: head/sbin/rcorder/rcorder.c
> ==============================================================================
> --- head/sbin/rcorder/rcorder.c Tue Sep 8 07:37:45 2020 (r365448)
> +++ head/sbin/rcorder/rcorder.c Tue Sep 8 10:36:11 2020 (r365449)
> @@ -9,6 +9,8 @@
> * All rights reserved.
> * Copyright (c) 1998
> * Perry E. Metzger. All rights reserved.
> + * Copyright (c) 2020
> + * Boris N. Lytochkin. All rights reserved.
> *
> * Redistribution and use in source and binary forms, with or without
> * modification, are permitted provided that the following conditions
> @@ -48,6 +50,8 @@ __FBSDID("$FreeBSD$");
> #include <stdlib.h>
> #include <string.h>
> #include <unistd.h>
> +#include <libgen.h>
> +#include <stdbool.h>
>
> #include "ealloc.h"
> #include "sprite.h"
> @@ -75,17 +79,21 @@ static int debug = 0;
> #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;
>
> -typedef int bool;
> #define TRUE 1
> #define FALSE 0
> typedef bool flag;
> #define SET TRUE
> #define RESET FALSE
>
> +static flag do_graphviz = false;
> +static flag do_parallel = false;
> +
> static Hash_Table provide_hash_s, *provide_hash;
>
> typedef struct provnode provnode;
> @@ -97,12 +105,14 @@ typedef struct strnodelist strnodelist;
> 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,19 +134,23 @@ struct filenode {
> 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 int max_sequence = 0;
>
> static strnodelist *bl_list;
> static strnodelist *keep_list;
> static strnodelist *skip_list;
>
> -static void do_file(filenode *fnode);
> +static void do_file(filenode *fnode, strnodelist *);
> 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 *generate_loop_for_req(strnodelist *, provnode *, filenode *);
> +static void satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *);
> static void crunch_file(char *);
> static void parse_require(filenode *, char *);
> static void parse_provide(filenode *, char *);
> @@ -151,6 +165,12 @@ static void insert_before(void);
> static Hash_Entry *make_fake_provision(filenode *);
> static void crunch_all_files(void);
> static void initialize(void);
> +static void generate_graphviz_header(void);
> +static void generate_graphviz_footer(void);
> +static void generate_graphviz_file_links(Hash_Entry *, filenode *);
> +static void generate_graphviz_providers(void);
> +static inline int is_fake_prov(const char *);
> +static int sequence_cmp(const void *, const void *);
> static void generate_ordering(void);
>
> int
> @@ -158,7 +178,7 @@ main(int argc, char *argv[])
> {
> int ch;
>
> - while ((ch = getopt(argc, argv, "dk:s:")) != -1)
> + while ((ch = getopt(argc, argv, "dgk:ps:")) != -1)
> switch (ch) {
> case 'd':
> #ifdef DEBUG
> @@ -167,9 +187,15 @@ main(int argc, char *argv[])
> warnx("debugging not compiled in, -d ignored");
> #endif
> break;
> + case 'g':
> + do_graphviz = true;
> + break;
> case 'k':
> strnode_add(&keep_list, optarg, 0);
> break;
> + case 'p':
> + do_parallel = true;
> + break;
> case 's':
> strnode_add(&skip_list, optarg, 0);
> break;
> @@ -186,10 +212,13 @@ main(int argc, char *argv[])
> DPRINTF((stderr, "parse_args\n"));
> initialize();
> DPRINTF((stderr, "initialize\n"));
> + generate_graphviz_header();
> crunch_all_files();
> DPRINTF((stderr, "crunch_all_files\n"));
> + generate_graphviz_providers();
> generate_ordering();
> DPRINTF((stderr, "generate_ordering\n"));
> + generate_graphviz_footer();
>
> exit(exit_code);
> }
> @@ -295,6 +324,7 @@ add_provide(filenode *fnode, char *s)
> head->head = SET;
> head->in_progress = RESET;
> head->fnode = NULL;
> + head->sequence = 0;
> head->last = head->next = NULL;
> Hash_SetValue(entry, head);
> }
> @@ -350,6 +380,7 @@ add_provide(filenode *fnode, char *s)
>
> 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 +553,7 @@ make_fake_provision(filenode *node)
> 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 +574,7 @@ make_fake_provision(filenode *node)
> 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 +607,11 @@ insert_before(void)
> if (new == 1)
> warnx("file `%s' is before unknown provision `%s'", bl_list->node->filename, bl_list->s);
>
> + if (new == 1 && do_graphviz == true)
> + 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,7 +642,134 @@ crunch_all_files(void)
> insert_before();
> }
>
> +static inline int
> +is_fake_prov(const char *name)
> +{
> +
> + return (name == strstr(name, FAKE_PROV_NAME));
> +}
> +
> +/* loop though provide 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 (is_fake_prov(dep_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 (is_fake_prov(fname))
> + continue;
> + rfpnode = NULL;
> + do {
> + if (rfpnode)
> + dep_name = Hash_GetKey(rfpnode->entry);
> + else
> + dep_name = Hash_GetKey(entry);
> +
> + if (!is_fake_prov(dep_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);
> + }
> +}
> +
> /*
> + * Walk the stack, find the looping point and generate traceback.
> + * NULL is returned on failure, otherwize pointer to a buffer holding
> + * text representation is returned, caller must run free(3) for the
> + * pointer.
> + */
> +static char *
> +generate_loop_for_req(strnodelist *stack_tail, provnode *head,
> + filenode *fnode)
> +{
> + provnode *pnode;
> + strnodelist *stack_ptr, *loop_entry;
> + char *buf, **revstack;
> + size_t bufsize;
> + int i, stack_depth;
> +
> + 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_depth = 0;
> + for (stack_ptr = stack_tail; stack_ptr;
> + stack_ptr = stack_ptr->next) {
> + stack_depth++;
> + if (stack_ptr->node == pnode->fnode) {
> + loop_entry = stack_ptr;
> + break;
> + }
> + }
> + }
> +
> + if (loop_entry == NULL)
> + return (NULL);
> +
> + stack_depth += 2; /* fnode + loop_entry */
> + revstack = emalloc(sizeof(char *) * stack_depth);
> + bzero(revstack, (sizeof(char *) * stack_depth));
> +
> + /* reverse stack and estimate buffer size to allocate */
> + bufsize = 1; /* tralining \0 */
> +
> + revstack[stack_depth - 1] = loop_entry->node->filename;
> + bufsize += strlen(revstack[stack_depth - 1]);
> +
> + revstack[stack_depth - 2] = fnode->filename;
> + bufsize += strlen(revstack[stack_depth - 2]);
> + fnode->issues_count++;
> +
> + stack_ptr = stack_tail;
> + for (i = stack_depth - 3; i >= 0; i--) {
> + revstack[i] = stack_ptr->node->filename;
> + stack_ptr->node->issues_count++;
> + stack_ptr = stack_ptr->next;
> + bufsize += strlen(revstack[i]);
> + }
> + bufsize += strlen(" -> ") * (stack_depth - 1);
> +
> + buf = emalloc(bufsize);
> + bzero(buf, bufsize);
> +
> + for (i = 0; i < stack_depth; i++) {
> + strlcat(buf, revstack[i], bufsize);
> + if (i < stack_depth - 1)
> + strlcat(buf, " -> ", bufsize);
> + }
> +
> + free(revstack);
> + return (buf);
> +}
> +/*
> * below are the functions that traverse the graphs we have built
> * finding out the desired ordering, printing each file in turn.
> * if missing requirements, or cyclic graphs are detected, a
> @@ -621,17 +785,22 @@ crunch_all_files(void)
> * provision.
> */
> static void
> -satisfy_req(f_reqnode *rnode, char *filename)
> +satisfy_req(f_reqnode *rnode, filenode *fnode, strnodelist *stack_ptr)
> {
> Hash_Entry *entry;
> provnode *head;
> + strnodelist stack_item;
> + char *buf;
>
> entry = rnode->entry;
> head = Hash_GetValue(entry);
>
> + if (do_graphviz == true)
> + 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 +814,34 @@ satisfy_req(f_reqnode *rnode, char *filename)
> * 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 = generate_loop_for_req(stack_ptr, 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_item.next = stack_ptr;
> + stack_item.node = fnode;
> +
> /*
> * while provision_list is not empty
> * do_file(first_member_of(provision_list));
> */
> while (head->next != NULL)
> - do_file(head->next->fnode);
> + do_file(head->next->fnode, &stack_item);
> }
>
> static int
> @@ -701,12 +884,13 @@ keep_ok(filenode *fnode)
> * Circular dependencies will cause problems if we do.
> */
> static void
> -do_file(filenode *fnode)
> +do_file(filenode *fnode, strnodelist *stack_ptr)
> {
> f_reqnode *r;
> f_provnode *p, *p_tmp;
> - provnode *pnode;
> + provnode *pnode, *head;
> int was_set;
> + char *dep_name;
>
> DPRINTF((stderr, "do_file on %s.\n", fnode->filename));
>
> @@ -729,18 +913,44 @@ do_file(filenode *fnode)
> * satisfy_req(r, filename)
> */
> r = fnode->req_list;
> + fnode->sequence = 0;
> while (r != NULL) {
> - satisfy_req(r, fnode->filename);
> + satisfy_req(r, fnode, stack_ptr);
> + /* 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) {
> + /* mark all troublemakers on graphviz */
> + if (do_graphviz == true && fnode->issues_count) {
> + dep_name = Hash_GetKey(p->entry);
> + if (!is_fake_prov(dep_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 +969,11 @@ do_file(filenode *fnode)
> 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 != true && 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 +982,103 @@ do_file(filenode *fnode)
> 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_graphviz_header()
> +{
> +
> + if (do_graphviz != true)
> + return;
> +
> + printf("digraph rcorder {\n"
> + "rankdir=\"BT\";\n"
> + "node [style=rounded, shape=record];\n"
> + "graph [overlap = false];\n");
> +}
> +
> +static void
> +generate_graphviz_footer()
> +{
> +
> + if (do_graphviz == true)
> + printf("}\n");
> +}
> +
> +static void
> +generate_graphviz_providers()
> +{
> + Hash_Entry *entry;
> + Hash_Search psearch;
> + provnode *head, *pnode;
> + char *dep_name;
> +
> + if (do_graphviz != true)
> + return;
> +
> + entry = Hash_EnumFirst(provide_hash, &psearch);
> + if (entry == NULL)
> + return;
> +
> + do {
> + dep_name = Hash_GetKey(entry);
> + if (is_fake_prov(dep_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(&psearch)));
> +}
> +
> +static int
> +sequence_cmp(const void *a, const void *b)
> +{
> + const filenode *fna = *((const filenode * const *)a);
> + const filenode *fnb = *((const filenode * const *)b);
> + int left, right;
> +
> + /* push phantom files to the end */
> + if (fna == NULL || fnb == NULL)
> + return ((fna < fnb) - (fna > fnb));
> +
> + left = fna->sequence;
> + right = fnb->sequence;
> +
> + return ((left > right) - (left < right));
> +}
> +
> +static void
> generate_ordering(void)
> {
> + filenode **seqlist, **psl;
> + int last_seq = 0;
>
> + /* Prepare order buffer, use an additional one as a list terminator */
> + 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)
> @@ -798,6 +1095,24 @@ generate_ordering(void)
> */
> while (fn_head->next != NULL) {
> DPRINTF((stderr, "generate on %s\n", fn_head->next->filename));
> - do_file(fn_head->next);
> + do_file(fn_head->next, NULL);
> }
> +
> + /* 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 != true || last_seq != (*psl)->sequence) ?
> + "\n" : " "),
> + (*psl)->filename);
> + last_seq = (*psl)->sequence;
> + free((*psl)->filename);
> + free(*psl);
> + }
> + if (last_seq)
> + printf("\n");
> +
> + free(seqlist);
> }
More information about the svn-src-all
mailing list