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);
}
_______________________________________________
svn-src-head@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/svn-src-head
To unsubscribe, send any mail to "svn-src-head-unsubscr...@freebsd.org"
