aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/comp.c113
-rw-r--r--src/depmap.c40
-rw-r--r--src/pies.h6
-rw-r--r--tests/Makefile.am1
-rw-r--r--tests/atlocal.in6
-rw-r--r--tests/cyclic.at114
-rw-r--r--tests/testsuite.at2
7 files changed, 222 insertions, 60 deletions
diff --git a/src/comp.c b/src/comp.c
index 17832ad..fcd0a14 100644
--- a/src/comp.c
+++ b/src/comp.c
@@ -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--;
}
diff --git a/src/pies.h b/src/pies.h
index 70d972a..e7e5d71 100644
--- a/src/pies.h
+++ b/src/pies.h
@@ -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])

Return to:

Send suggestions and report system problems to the System administrator.