From 4b31caa9cdaef67c70bc7fb43963ba68b7bf5bb1 Mon Sep 17 00:00:00 2001 From: Laurent Bercot Date: Thu, 4 Jun 2015 20:48:10 +0000 Subject: Initial commit --- src/libs6rc/deps-lib/s6rc | 6 ++ src/libs6rc/s6rc_db_check_depcycles.c | 50 ++++++++++ src/libs6rc/s6rc_db_check_revdeps.c | 30 ++++++ src/libs6rc/s6rc_db_read.c | 176 ++++++++++++++++++++++++++++++++++ src/libs6rc/s6rc_db_read_sizes.c | 53 ++++++++++ src/libs6rc/s6rc_db_read_uint32.c | 14 +++ src/libs6rc/s6rc_graph_closure.c | 39 ++++++++ 7 files changed, 368 insertions(+) create mode 100644 src/libs6rc/deps-lib/s6rc create mode 100644 src/libs6rc/s6rc_db_check_depcycles.c create mode 100644 src/libs6rc/s6rc_db_check_revdeps.c create mode 100644 src/libs6rc/s6rc_db_read.c create mode 100644 src/libs6rc/s6rc_db_read_sizes.c create mode 100644 src/libs6rc/s6rc_db_read_uint32.c create mode 100644 src/libs6rc/s6rc_graph_closure.c (limited to 'src/libs6rc') diff --git a/src/libs6rc/deps-lib/s6rc b/src/libs6rc/deps-lib/s6rc new file mode 100644 index 0000000..65b562e --- /dev/null +++ b/src/libs6rc/deps-lib/s6rc @@ -0,0 +1,6 @@ +s6rc_db_check_depcycles.o +s6rc_db_read.o +s6rc_db_read_sizes.o +s6rc_db_read_uint32.o +s6rc_db_check_revdeps.o +s6rc_graph_closure.o diff --git a/src/libs6rc/s6rc_db_check_depcycles.c b/src/libs6rc/s6rc_db_check_depcycles.c new file mode 100644 index 0000000..13dcf7b --- /dev/null +++ b/src/libs6rc/s6rc_db_check_depcycles.c @@ -0,0 +1,50 @@ +/* ISC license. */ + +#include +#include +#include +#include + +typedef struct recinfo_s recinfo_t, *recinfo_t_ref ; +struct recinfo_s +{ + s6rc_db_t const *db ; + unsigned int n ; + unsigned char *gray ; + unsigned char *black ; + unsigned char h : 1 ; +} ; + +static unsigned int s6rc_db_checknocycle_rec (recinfo_t *recinfo, unsigned int i) +{ + if (!bitarray_peek(recinfo->black, i)) + { + unsigned int j = recinfo->db->services[i].ndeps[recinfo->h] ; + if (bitarray_peek(recinfo->gray, i)) return i ; + bitarray_set(recinfo->gray, i) ; + while (j--) + { + register unsigned int r = s6rc_db_checknocycle_rec(recinfo, recinfo->db->deps[recinfo->h * recinfo->db->ndeps + recinfo->db->services[i].deps[recinfo->h] + j]) ; + if (r < recinfo->n) return r ; + } + bitarray_set(recinfo->black, i) ; + } + return recinfo->n ; +} + +unsigned int s6rc_db_check_depcycles (s6rc_db_t const *db, int h, unsigned int *problem) +{ + unsigned int n = db->nshort + db->nlong ; + unsigned char gray[bitarray_div8(n)] ; + unsigned char black[bitarray_div8(n)] ; + recinfo_t info = { .db = db, .n = n, .gray = gray, .black = black, .h = !!h } ; + unsigned int i = n ; + byte_zero(gray, bitarray_div8(n)) ; + byte_zero(black, bitarray_div8(n)) ; + while (i--) + { + register unsigned int r = s6rc_db_checknocycle_rec(&info, i) ; + if (r < n) return (*problem = r, i) ; + } + return n ; +} diff --git a/src/libs6rc/s6rc_db_check_revdeps.c b/src/libs6rc/s6rc_db_check_revdeps.c new file mode 100644 index 0000000..0cb2845 --- /dev/null +++ b/src/libs6rc/s6rc_db_check_revdeps.c @@ -0,0 +1,30 @@ +/* ISC license. */ + +#include +#include +#include +#include + +int s6rc_db_check_revdeps (s6rc_db_t const *db) +{ + unsigned int n = db->nshort + db->nlong ; + unsigned int m = bitarray_div8(n) ; + unsigned char matrix[n * m] ; + register unsigned int i = n ; + register unsigned char const *p = matrix ; + byte_zero(matrix, n * m) ; + while (i--) + { + register unsigned int j = db->services[i].ndeps[1] ; + while (j--) bitarray_not(matrix + m * i, db->deps[db->ndeps + db->services[i].deps[1] + j], 1) ; + } + i = n ; + while (i--) + { + register unsigned int j = db->services[i].ndeps[0] ; + while (j--) bitarray_not(matrix + m * db->deps[db->services[i].deps[0] + j], i, 1) ; + } + i = n * m ; + while (i--) if (*p++) return 0 ; + return 1 ; +} diff --git a/src/libs6rc/s6rc_db_read.c b/src/libs6rc/s6rc_db_read.c new file mode 100644 index 0000000..f0c7909 --- /dev/null +++ b/src/libs6rc/s6rc_db_read.c @@ -0,0 +1,176 @@ +/* ISC license. */ + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#ifdef DEBUG +#include +#define DBG(...) do { bprintf(buffer_2, "debug: ") ; bprintf(buffer_2, __VA_ARGS__) ; bprintf(buffer_2, "\n") ; buffer_flush(buffer_2) ; } while(0) +#else +#define DBG(...) +#endif + +static int s6rc_db_check_valid_string (char const *string, unsigned int stringlen, unsigned int pos) +{ + if (pos >= stringlen) return 0 ; + if (str_nlen(string + pos, stringlen - pos) == stringlen - pos) return 0 ; + return 1 ; +} + +static inline int s6rc_db_check_valid_strings (char const *string, unsigned int stringlen, unsigned int pos, unsigned int n) +{ + while (n--) + { + if (!s6rc_db_check_valid_string(string, stringlen, pos)) return 0 ; + pos += str_len(string + pos) + 1 ; + } + return 1 ; +} + +static inline int s6rc_db_read_deps (buffer *b, unsigned int max, uint32 *deps, unsigned int ndeps) +{ + uint32 x ; + ndeps <<= 1 ; + while (ndeps--) + { + if (!s6rc_db_read_uint32(b, &x)) return -1 ; + if (x >= max) return 0 ; + *deps++ = x ; + } + return 1 ; +} + +static inline int s6rc_db_read_services (buffer *b, s6rc_db_t *db) +{ + unsigned int n = db->nshort + db->nlong ; + s6rc_service_t *sv = db->services ; + unsigned int nargvs = db->nargvs ; + char **argvs = db->argvs ; + char type ; +#ifdef DEBUG + register unsigned int i = 0 ; +#endif + while (n--) + { + DBG("iteration %u - %u remaining", i++, n) ; + if (!s6rc_db_read_uint32(b, &sv->name)) return -1 ; + DBG(" name is %u: %s", sv->name, db->string + sv->name) ; + if (sv->name >= db->stringlen) return 0 ; + if (!s6rc_db_check_valid_string(db->string, db->stringlen, sv->name)) return 0 ; + if (!s6rc_db_read_uint32(b, &sv->flags)) return -1 ; + DBG(" flags is %x", sv->flags) ; + if (!s6rc_db_read_uint32(b, &sv->timeout[0])) return -1 ; + DBG(" timeout0 is %u", sv->timeout[0]) ; + if (!s6rc_db_read_uint32(b, &sv->timeout[1])) return -1 ; + DBG(" timeout1 is %u", sv->timeout[1]) ; + if (!s6rc_db_read_uint32(b, &sv->ndeps[0])) return -1 ; + DBG(" ndeps0 is %u", sv->ndeps[0]) ; + if (!s6rc_db_read_uint32(b, &sv->ndeps[1])) return -1 ; + DBG(" ndeps1 is %u", sv->ndeps[1]) ; + if (!s6rc_db_read_uint32(b, &sv->deps[0])) return -1 ; + DBG(" deps0 is %u", sv->deps[0]) ; + if (sv->deps[0] > db->ndeps || sv->deps[0] + sv->ndeps[0] > db->ndeps) + return 0 ; + if (!s6rc_db_read_uint32(b, &sv->deps[1])) return -1 ; + DBG(" deps1 is %u", sv->deps[1]) ; + if (sv->deps[1] > db->ndeps || sv->deps[1] + sv->ndeps[1] > db->ndeps) + return 0 ; +#ifdef DEBUG + { + unsigned int k = 0 ; + for (; k < sv->ndeps[0] ; k++) + DBG(" rev dep on %u", db->deps[sv->deps[0] + k]) ; + for (k = 0 ; k < sv->ndeps[1] ; k++) + DBG(" dep on %u", db->deps[db->ndeps + sv->deps[1] + k]) ; + } +#endif + if (buffer_get(b, &type, 1) < 1) return -1 ; + if (type) + { + sv->type = 1 ; + if (!s6rc_db_read_uint32(b, &sv->x.longrun.servicedir)) return -1 ; + DBG(" longrun - servicedir is %u: %s", sv->x.longrun.servicedir, db->string + sv->x.longrun.servicedir) ; + if (!s6rc_db_check_valid_string(db->string, db->stringlen, sv->x.longrun.servicedir)) return 0 ; + } + else + { + unsigned int i = 0 ; + DBG(" oneshot") ; + sv->type = 0 ; + for (; i < 2 ; i++) + { + uint32 argvpos, argc ; + if (!s6rc_db_read_uint32(b, &argc)) return -1 ; + DBG(" argc[%u] is %u, nargvs is %u", i, argc, nargvs) ; + if (argc > nargvs) return 0 ; + if (!s6rc_db_read_uint32(b, &argvpos)) return -1 ; + DBG(" argvpos[%u] is %u", i, argvpos) ; + if (!s6rc_db_check_valid_strings(db->string, db->stringlen, argvpos, argc)) return 0 ; + if (!env_make((char const **)argvs, argc, db->string + argvpos, db->stringlen - argvpos)) return -1 ; + DBG(" first arg is %s", argvs[0]) ; + sv->x.oneshot.argv[i] = argvpos ; + sv->x.oneshot.argc[i] = argc ; + argvs += argc ; nargvs -= argc ; + if (!nargvs--) return 0 ; *argvs++ = 0 ; + } + } + if (buffer_get(b, &type, 1) < 1) return -1 ; + if (type != '\376') return 0 ; + sv++ ; + } + if (nargvs) return 0 ; + return 1 ; +} + +static inline int s6rc_db_read_string (buffer *b, char *string, unsigned int len) +{ + if (buffer_get(b, string, len) < (int)len) return -1 ; + return 1 ; +} + +static inline int s6rc_db_read_buffer (buffer *b, s6rc_db_t *db) +{ + { + char banner[S6RC_DB_BANNER_START_LEN] ; + if (buffer_get(b, banner, S6RC_DB_BANNER_START_LEN) < S6RC_DB_BANNER_START_LEN) return -1 ; + if (byte_diff(banner, S6RC_DB_BANNER_START_LEN, S6RC_DB_BANNER_START)) return 0 ; + } + + { + register int r = s6rc_db_read_string(b, db->string, db->stringlen) ; + if (r < 1) return r ; + r = s6rc_db_read_deps(b, db->nshort + db->nlong, db->deps, db->ndeps) ; + if (r < 1) return r ; + r = s6rc_db_read_services(b, db) ; + if (r < 1) return r ; + } + + { + char banner[S6RC_DB_BANNER_END_LEN] ; + if (buffer_get(b, banner, S6RC_DB_BANNER_END_LEN) < S6RC_DB_BANNER_END_LEN) return -1 ; + if (byte_diff(banner, S6RC_DB_BANNER_END_LEN, S6RC_DB_BANNER_END)) return 0 ; + } + return 1 ; +} + +int s6rc_db_read (int fdcompiled, s6rc_db_t *db) +{ + int r, e ; + buffer b ; + char buf[BUFFER_INSIZE] ; + int fd = open_readatb(fdcompiled, "db") ; + if (fd < 0) return -1 ; + buffer_init(&b, &fd_readsv, fd, buf, BUFFER_INSIZE) ; + r = s6rc_db_read_buffer(&b, db) ; + e = errno ; + fd_close(fd) ; + errno = e ; + return r ; +} diff --git a/src/libs6rc/s6rc_db_read_sizes.c b/src/libs6rc/s6rc_db_read_sizes.c new file mode 100644 index 0000000..4d1537f --- /dev/null +++ b/src/libs6rc/s6rc_db_read_sizes.c @@ -0,0 +1,53 @@ +/* ISC license. */ + +#include +#include +#include +#include +#include +#include +#include + +static inline int s6rc_db_read_sizes_buffer (buffer *b, s6rc_db_t *db) +{ + uint32 x ; + if (!s6rc_db_read_uint32(b, &x)) return 0 ; + db->nshort = x ; + if (!s6rc_db_read_uint32(b, &x)) return 0 ; + db->nlong = x ; + if (!s6rc_db_read_uint32(b, &x)) return 0 ; + db->stringlen = x ; + if (!s6rc_db_read_uint32(b, &x)) return 0 ; + db->nargvs = x ; + if (!s6rc_db_read_uint32(b, &x)) return 0 ; + db->ndeps = x ; + return 1 ; +} + +int s6rc_db_read_sizes (int fdcompiled, s6rc_db_t *db) +{ + char buf[64] ; + buffer b ; + int fd = open_readatb(fdcompiled, "n") ; + if (fd < 0) return 0 ; + buffer_init(&b, &fd_readsv, fd, buf, 64) ; + if (!s6rc_db_read_sizes_buffer(&b, db)) + { + fd_close(fd) ; + return 0 ; + } + { + char c ; + register int r = buffer_get(&b, &c, 1) ; + if (r < 0) + { + r = errno ; + fd_close(fd) ; + errno = r ; + return 0 ; + } + fd_close(fd) ; + if (r) return 0 ; + } + return 1 ; +} diff --git a/src/libs6rc/s6rc_db_read_uint32.c b/src/libs6rc/s6rc_db_read_uint32.c new file mode 100644 index 0000000..05d1f9e --- /dev/null +++ b/src/libs6rc/s6rc_db_read_uint32.c @@ -0,0 +1,14 @@ +/* ISC license. */ + +#include +#include +#include + +int s6rc_db_read_uint32 (buffer *b, uint32 *x) +{ + unsigned int w = 0 ; + char pack[4] ; + if (buffer_getall(b, pack, 4, &w) <= 0) return 0 ; + uint32_unpack_big(pack, x) ; + return 1 ; +} diff --git a/src/libs6rc/s6rc_graph_closure.c b/src/libs6rc/s6rc_graph_closure.c new file mode 100644 index 0000000..0ec2def --- /dev/null +++ b/src/libs6rc/s6rc_graph_closure.c @@ -0,0 +1,39 @@ +/* ISC license. */ + +#include +#include +#include + +typedef struct recinfo_s recinfo_t, *recinfo_t_ref ; +struct recinfo_s +{ + s6rc_db_t const *db ; + unsigned int n ; + unsigned char *bits ; + unsigned char *mark ; + unsigned char mask ; + unsigned char h : 1 ; +} ; + +static void s6rc_graph_closure_rec (recinfo_t *recinfo, unsigned int i) +{ + if (!bitarray_peek(recinfo->mark, i)) + { + unsigned int j = recinfo->db->services[i].ndeps[recinfo->h] ; + bitarray_set(recinfo->mark, i) ; + while (j--) s6rc_graph_closure_rec(recinfo, recinfo->db->deps[recinfo->h * recinfo->db->ndeps + recinfo->db->services[i].deps[recinfo->h] + j]) ; + recinfo->bits[i] |= recinfo->mask ; + } +} + +void s6rc_graph_closure (s6rc_db_t const *db, unsigned char *bits, unsigned int bitno, int h) +{ + unsigned int n = db->nshort + db->nlong ; + unsigned int m = bitarray_div8(n) ; + unsigned char mark[m] ; + recinfo_t info = { .db = db, .n = n, .bits = bits, .mark = mark, .mask = 1 << (bitno & 7), .h = !!h } ; + register unsigned int i = n ; + byte_zero(mark, m) ; + while (i--) + if (bits[i] & info.mask) s6rc_graph_closure_rec(&info, i) ; +} -- cgit v1.2.3