diff options
-rw-r--r-- | src/comp.c | 113 | ||||
-rw-r--r-- | src/depmap.c | 40 | ||||
-rw-r--r-- | src/pies.h | 6 | ||||
-rw-r--r-- | tests/Makefile.am | 1 | ||||
-rw-r--r-- | tests/atlocal.in | 6 | ||||
-rw-r--r-- | tests/cyclic.at | 114 | ||||
-rw-r--r-- | tests/testsuite.at | 2 |
7 files changed, 222 insertions, 60 deletions
@@ -116,25 +116,25 @@ component_lookup_tag (int idx, const char *tag) if (strcmp (comp->tag, tag) == 0) break; return comp; } ssize_t component_lookup_index (const char *tag) { size_t i; for (i = 0; i < comp_count; i++) - if (comp_array[i] && strcmp (comp_array[i]->tag, tag) == 0) + if (strcmp (comp_array[i]->tag, tag) == 0) return i; return -1; } struct component * component_create (const char *name) { struct component *comp = component_lookup_tag (cur, name); if (!comp) { comp = grecs_zalloc (sizeof (*comp)); comp->listidx = cur; @@ -379,104 +379,140 @@ mark_prog (struct prog *prog, void *data) if (prog->v.p.status == status_listener) progman_stop_component (&prog); } return 0; } static int list_str_cmp (const void *a, const void *b) { return safe_strcmp (a, b); } +/* Report cyclic dependency starting at IDX. Mark each element with + CF_REMOVE for subsequent removal. + DP is a transitive closure of depmap. +*/ static void -component_log_dep (size_t idx) +report_cyclic_dependency (pies_depmap_t dp, size_t idx) { - pies_depmap_pos_t pos; - size_t n; + size_t i; - logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[idx]->tag); - for (n = depmap_first (depmap, depmap_col, idx, &pos); - n != (size_t)-1; - n = depmap_next (depmap, pos)) + i = idx; + do { - logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[n]->tag); + size_t n; + pies_depmap_pos_t pos; + + logmsg_printf (LOG_NOTICE, "%s -> ", comp_array[i]->tag); + comp_array[i]->flags |= CF_REMOVE; + for (n = depmap_first (depmap, depmap_col, i, &pos); + n != (size_t)-1; + n = depmap_next (depmap, pos)) + { + if (n == i) + continue; + if (depmap_isset (dp, n, i) && depmap_isset (dp, n, n)) + break; + } + depmap_end (pos); + + if (n == (size_t)-1) + break; + i = n; } - depmap_end (pos); + while (i != idx); logmsg_printf (LOG_NOTICE, "%s\n", comp_array[idx]->tag); } void +comp_array_remove (size_t i) +{ + struct component *comp = comp_array[i]; + if (i < comp_count - 1) + memmove (&comp_array[i], &comp_array[i+1], + (comp_count - i - 1) * sizeof comp_array[0]); + component_free (comp); + comp_count--; +} + +void component_build_depmap (void) { size_t i; pies_depmap_t dp; free (depmap); depmap = depmap_alloc (comp_count); - for (i = 0; i < comp_count; i++) + for (i = 0; i < comp_count; ) { struct component *comp = comp_array[i]; struct grecs_list_entry *ep; if (comp->prereq) for (ep = comp->prereq->head; ep; ep = ep->next) { char const *tag = ep->data; ssize_t tgt = component_lookup_index (tag); if (tgt < 0) { logmsg (LOG_ERR, _("component %s depends on %s, " "which is not declared"), comp->tag, tag); - component_free (comp); - comp_array[i] = NULL; - depmap_clear_all (depmap, depmap_row, i); - depmap_clear_all (depmap, depmap_col, i); + comp_array_remove (i); + depmap_remove (depmap, i); continue; } depmap_set (depmap, i, tgt); } if (comp->depend) for (ep = comp->depend->head; ep; ep = ep->next) { char const *tag = ep->data; ssize_t tgt = component_lookup_index (tag); if (tgt < 0) { logmsg (LOG_ERR, _("undefined component %s depends on %s"), tag, comp->tag); continue; } depmap_set (depmap, tgt, i); } + + i++; } dp = depmap_copy (depmap); depmap_tc (dp); for (i = 0; i < comp_count; i++) - if (depmap_isset (dp, i, i)) + if (!(comp_array[i]->flags & CF_REMOVE) && depmap_isset (dp, i, i)) { logmsg (LOG_ERR, _("component %s depends on itself"), comp_array[i]->tag); - component_log_dep (i); - component_free (comp_array[i]); - comp_array[i] = NULL; - depmap_clear_all (depmap, depmap_row, i); - depmap_clear_all (depmap, depmap_col, i); - continue; + report_cyclic_dependency (dp, i); + } + + + for (i = 0; i < comp_count;) + if (comp_array[i]->flags & CF_REMOVE) + { + comp_array_remove (i); + depmap_remove (depmap, i); } + else + i++; + free (dp); } void component_config_commit (void) { struct complist *list = &comp_list[cur]; struct component *comp, *match; int prev = prev_index (); size_t i; /* Count available components and allocate array for them */ @@ -739,55 +775,52 @@ component_finish (struct component *comp, grecs_locus_t *locus) } } struct component * component_get (size_t n) { if (n >= comp_count) return NULL; return comp_array[n]; } void -components_dump_depmap (void) +depmap_dump (pies_depmap_t dpm) { - size_t i, j, k; + size_t i, j; printf ("%s:\n", _("Dependency map")); printf (" "); - for (i = k = 0; i < comp_count; i++) - if (comp_array[i]) - { - printf (" %2lu", (unsigned long)k); - k++; - } + for (i = 0; i < comp_count; i++) + printf (" %2lu", (unsigned long)i); printf ("\n"); - for (i = k = 0; i < comp_count; i++) + for (i = 0; i < comp_count; i++) { - if (comp_array[i]) - { - printf ("%2lu ", (unsigned long)k); - for (j = 0; j < comp_count; j++) - if (comp_array[j]) - printf (" %c ", depmap_isset (depmap, i, j) ? 'X' : ' '); - printf ("\n"); - k++; - } + printf ("%2lu", (unsigned long)i); + for (j = 0; j < comp_count; j++) + printf (" %c", depmap_isset (dpm, i, j) ? 'X' : ' '); + printf ("\n"); } printf ("\n%s:\n", _("Legend")); for (i = 0; i < comp_count; i++) printf ("%2lu: %s\n", (unsigned long)i, comp_array[i]->tag); } void +components_dump_depmap (void) +{ + depmap_dump (depmap); +} + +void component_trace (size_t idx, enum pies_depmap_direction dir) { pies_depmap_pos_t pos; size_t n; int delim = ':'; logmsg_printf (LOG_NOTICE, "%s", comp_array[idx]->tag); for (n = depmap_first (depmap, dir, idx, &pos); n != (size_t)-1; n = depmap_next (depmap, pos)) { logmsg_printf (LOG_NOTICE, "%c %s", delim, comp_array[n]->tag); diff --git a/src/depmap.c b/src/depmap.c index 3ea5722..cb50548 100644 --- a/src/depmap.c +++ b/src/depmap.c @@ -72,45 +72,52 @@ TC (unsigned *R, int n) mask <<= 1; if (mask == 0) { mask = 1; cword++; } rowi = (unsigned *) ((char *) rowi + rowsize); } } struct pies_depmap { - size_t nrows; - size_t rowlen; - unsigned r[1]; + size_t nrows; /* Number of rows (== number of mapped elements) */ + size_t rowlen; /* Length of a row in words */ + unsigned r[1]; /* Data rows */ }; pies_depmap_t depmap_alloc (size_t count) { size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD; pies_depmap_t dmap = grecs_zalloc (sizeof (*dmap) - 1 + count * size * sizeof (unsigned)); dmap->nrows = count; dmap->rowlen = size; return dmap; } +/* Return size of a depmap row in bytes */ +static inline size_t +depmap_row_size (pies_depmap_t dpm) +{ + return dpm->rowlen * sizeof (unsigned); +} + pies_depmap_t depmap_copy (pies_depmap_t dpm) { pies_depmap_t copy = depmap_alloc (dpm->nrows); - memcpy (copy->r, dpm->r, dpm->nrows * dpm->rowlen * sizeof (unsigned)); + memcpy (copy->r, dpm->r, dpm->nrows * depmap_row_size (dpm)); return copy; } static unsigned * depmap_rowptr (pies_depmap_t dmap, size_t row) { return dmap->r + dmap->rowlen * row; } void depmap_set (pies_depmap_t dmap, size_t row, size_t col) { @@ -165,30 +172,31 @@ depmap_first (pies_depmap_t dmap, enum pies_depmap_direction dir, pos->dir = dir; pos->coord[!pos->dir] = coord; pos->coord[pos->dir] = -1; return depmap_next (dmap, pos); } void depmap_end (pies_depmap_pos_t pos) { grecs_free (pos); } +/* Remove nth row and column from the map */ void -depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, - size_t coord) +depmap_remove (pies_depmap_t dmap, size_t n) { - size_t i; - - switch (dir) + if (n < dmap->nrows - 1) { - case depmap_row: - for (i = 0; i < dmap->nrows; i++) - depmap_clear (dmap, coord, i); - break; - - case depmap_col: + size_t i, j; + + /* Remove nth row */ + memmove (depmap_rowptr (dmap, n), depmap_rowptr (dmap, n + 1), + (dmap->nrows - n - 1) * depmap_row_size (dmap)); + /* Renumber all columns j >= n: j = j - 1 */ for (i = 0; i < dmap->nrows; i++) - depmap_clear (dmap, i, coord); + for (j = n; j < dmap->nrows - 1; j++) + (depmap_isset (dmap, i, j + 1) ? depmap_set : depmap_clear) + (dmap, i, j); } + dmap->nrows--; } @@ -190,24 +190,26 @@ enum pies_comp_mode #define CF_TCPMUX 0x008 /* A plain TCPMUX service */ #define CF_TCPMUXPLUS 0x010 /* A TCPMUX-plus service, i.e. pies must emit a '+' response before starting it */ #define CF_INTERNAL 0x020 /* An internal inetd service */ #define CF_SOCKENV 0x040 /* Component wants socket information in the environment */ #define CF_RESOLVE 0x080 /* Resolve IP addresses */ #define CF_SIGGROUP 0x100 /* Send signals to the process group */ #define CF_NULLINPUT 0x200 /* Provide null input stream */ +#define CF_REMOVE 0x400 /* Marked for removal */ + #define ISCF_TCPMUX(f) ((f) & (CF_TCPMUX | CF_TCPMUXPLUS)) struct prog; struct component { struct component *prev, *next; /* Components form doubly-linked list. */ int listidx; /* Index of the list. */ size_t arridx; /* Index of this component. */ size_t ref_count; /* Reference count. */ struct prog *prog; /* Prog associated with this component. */ @@ -365,27 +367,25 @@ typedef struct pies_depmap *pies_depmap_t; typedef struct pies_depmap_pos *pies_depmap_pos_t; enum pies_depmap_direction { depmap_row = 0, depmap_col = !depmap_row }; pies_depmap_t depmap_alloc (size_t count); pies_depmap_t depmap_copy (pies_depmap_t dpm); void depmap_set (pies_depmap_t dmap, size_t row, size_t col); int depmap_isset (pies_depmap_t dmap, size_t row, size_t col); void depmap_clear (pies_depmap_t dmap, size_t row, size_t col); - -void depmap_clear_all (pies_depmap_t dmap, enum pies_depmap_direction dir, - size_t coord); +void depmap_remove (pies_depmap_t dmap, size_t n); void depmap_tc (pies_depmap_t dmap); size_t depmap_first (pies_depmap_t dmap, enum pies_depmap_direction dir, size_t coord, pies_depmap_pos_t *ppos); size_t depmap_next (pies_depmap_t dmap, pies_depmap_pos_t pos); void depmap_end (pies_depmap_pos_t pos); int assert_grecs_value_type (grecs_locus_t *locus, const grecs_value_t *value, int type); int str_to_socket_type (const char *str, int *pret); int socket_type_to_str (int socket_type, const char **pres); diff --git a/tests/Makefile.am b/tests/Makefile.am index 5ef3796..6c387cb 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -32,24 +32,25 @@ $(srcdir)/package.m4: $(top_srcdir)/configure.ac echo 'm4_define([AT_PACKAGE_BUGREPORT], [@PACKAGE_BUGREPORT@])'; \ } >$(srcdir)/package.m4 # ## ------------ ## ## Test suite. ## ## ------------ ## TESTSUITE_AT = \ testsuite.at\ control.at\ + cyclic.at\ respawn.at\ redirect.at\ ret-exec.at\ ret-notify.at\ version.at TESTSUITE = $(srcdir)/testsuite M4=m4 AUTOTEST = $(AUTOM4TE) --language=autotest $(TESTSUITE): package.m4 $(TESTSUITE_AT) $(AM_V_GEN)$(AUTOTEST) -I $(srcdir) testsuite.at -o $@.tmp diff --git a/tests/atlocal.in b/tests/atlocal.in index 2ba1462..9069bbd 100644 --- a/tests/atlocal.in +++ b/tests/atlocal.in @@ -1,6 +1,10 @@ # @configure_input@ -*- shell-script -*- # Configurable variable values for GNU Pies test suite. -# Copyright (C) 2016-2017 Sergey Poznyakoff +# Copyright (C) 2016-2019 Sergey Poznyakoff PATH=@abs_builddir@:@abs_top_builddir@/src:$srcdir:$PATH XFAILFILE=$abs_builddir/.badversion + +trimws() { + sed 's/[ ][ ]*$//' +} diff --git a/tests/cyclic.at b/tests/cyclic.at new file mode 100644 index 0000000..27da22e --- /dev/null +++ b/tests/cyclic.at @@ -0,0 +1,114 @@ +# This file is part of GNU pies testsuite. -*- Autotest -*- +# Copyright (C) 2019 Sergey Poznyakoff +# +# GNU pies is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3, or (at your option) +# any later version. +# +# GNU pies is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with GNU pies. If not, see <http://www.gnu.org/licenses/>. + +AT_SETUP([Detecting cyclic dependencies]) +AT_CHECK([ +PIES_XFAIL_CHECK +# The following matrices describe the test.conf configuration file below. +# +# Dependency matrix: +# 0 1 2 3 4 5 6 7 +# 0 X X +# 1 X +# 2 X +# 3 X +# 4 X +# 5 +# 6 X +# 7 +# +# Transitive closure: +# 0 1 2 3 4 5 6 7 +# 0 X X X X X +# 1 X +# 2 X X X X X +# 3 X X X X X +# 4 X X X X X +# 5 +# 6 X +# 7 +# +# Legend: +# 0: a +# 1: b +# 2: c +# 3: d +# 4: e +# 5: f +# 6: g +# 7: h + +AT_DATA([test.conf], +[component a { + command "a"; + prerequisites (b,d); +} + +component b { + command "b"; + prerequisites (b); +} + +component c { + command "c"; + prerequisites (e); +} + +component d { + command "d"; + prerequisites (c); +} + +component e { + command "e"; + prerequisites (a); +} + +component f { + command "f"; +} + +component g { + command "g"; + prerequisites (h); +} + +component h { + command "h"; +} +]) + +pies --config-file test.conf --dump-depmap | trimws +], +[0], +[Dependency map: + 0 1 2 + 0 + 1 X + 2 + +Legend: + 0: f + 1: g + 2: h +], +[pies: component a depends on itself +pies: a -> d -> c -> e -> a +pies: component b depends on itself +pies: b -> b +]) + +AT_CLEANUP diff --git a/tests/testsuite.at b/tests/testsuite.at index 152b77f..7f4e7b8 100644 --- a/tests/testsuite.at +++ b/tests/testsuite.at @@ -49,17 +49,19 @@ do kill `cat $pidfile` echo >&2 "timed out waiting for shutdown" fi done]) AT_INIT AT_TESTED([pies]) AT_BANNER([Initial]) m4_include([version.at]) m4_include([control.at]) +AT_BANNER([Dependencies]) +m4_include([cyclic.at]) AT_BANNER([Components]) m4_include([respawn.at]) m4_include([redirect.at]) m4_include([ret-exec.at]) m4_include([ret-notify.at]) |