Page MenuHomeFreeBSD
Files F149177672

D25389.id73439.diff
No OneTemporary
Actions

D25389.id73439.diff
View Options

Index: rcorder.8
===================================================================
--- rcorder.8
+++ rcorder.8
@@ -31,7 +31,7 @@
.\"
.\" $FreeBSD$
.\"
-.Dd October 27, 2018
+.Dd June 21, 2020
.Dt RCORDER 8
.Os
.Sh NAME
@@ -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
@@ -72,11 +74,11 @@
Each line must begin with a single
.Ql # ,
followed by a single space, followed by
-.Dq Li PROVIDE: ,
-.Dq Li REQUIRE: ,
-.Dq Li BEFORE: ,
+.Dq Li PROVIDE\&: ,
+.Dq Li REQUIRE\&: ,
+.Dq Li BEFORE\&:
or
-.Dq Li KEYWORD: .
+.Dq Li KEYWORD\&: .
No deviation is permitted.
Each dependency line is then followed by a series of conditions,
separated by whitespace.
@@ -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 simultaneously on the same line.
.El
.Pp
An example block follows:
@@ -159,19 +167,46 @@
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."
+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,
+.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 provider and the requirement will be drawn bold red as well.
.Sh SEE ALSO
.Xr acpiconf 8 ,
.Xr rc 8 ,
Index: rcorder.c
===================================================================
--- rcorder.c
+++ rcorder.c
@@ -48,6 +48,7 @@
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
+#include <libgen.h>
#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);
}

File Metadata

Mime Type
text/plain
Expires
Mon, Mar 23, 7:13 PM (11 h, 40 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
30201209
Default Alt Text
D25389.id73439.diff (16 KB)

Event Timeline