From b99749f6d13a59ce0b6ff35ce0aea5a9e50b63bf Mon Sep 17 00:00:00 2001 From: Christian Neukirchen Date: Tue, 1 Sep 2015 11:55:59 +0200 Subject: Initial import of redo-c --- redo.c | 710 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 710 insertions(+) create mode 100644 redo.c (limited to 'redo.c') diff --git a/redo.c b/redo.c new file mode 100644 index 0000000..db300a8 --- /dev/null +++ b/redo.c @@ -0,0 +1,710 @@ +/* +##% cc -g -Os -Wall -Wextra -o $STEM $FILE +*/ + +/* +current bugs: + dependency-loop: unlimited recursion + need locks + + exts: prepend ./? --- execl should be good enough + + no directory handling at all + - fiddle .dep file lookup + - chdir to basename for each argument + + test job server properly +*/ + +// XXX drop asprintf +#define _GNU_SOURCE + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +// --------------------------------------------------------------------------- +// from musl/src/crypt/crypt_sha256.c + +/* public domain sha256 implementation based on fips180-3 */ + +struct sha256 { + uint64_t len; /* processed message length */ + uint32_t h[8]; /* hash state */ + uint8_t buf[64]; /* message block buffer */ +}; + +static uint32_t ror(uint32_t n, int k) { return (n >> k) | (n << (32-k)); } +#define Ch(x,y,z) (z ^ (x & (y ^ z))) +#define Maj(x,y,z) ((x & y) | (z & (x | y))) +#define S0(x) (ror(x,2) ^ ror(x,13) ^ ror(x,22)) +#define S1(x) (ror(x,6) ^ ror(x,11) ^ ror(x,25)) +#define R0(x) (ror(x,7) ^ ror(x,18) ^ (x>>3)) +#define R1(x) (ror(x,17) ^ ror(x,19) ^ (x>>10)) + +static const uint32_t K[64] = { +0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5, +0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174, +0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da, +0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967, +0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85, +0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070, +0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3, +0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2 +}; + +static void processblock(struct sha256 *s, const uint8_t *buf) +{ + uint32_t W[64], t1, t2, a, b, c, d, e, f, g, h; + int i; + + for (i = 0; i < 16; i++) { + W[i] = (uint32_t)buf[4*i]<<24; + W[i] |= (uint32_t)buf[4*i+1]<<16; + W[i] |= (uint32_t)buf[4*i+2]<<8; + W[i] |= buf[4*i+3]; + } + for (; i < 64; i++) + W[i] = R1(W[i-2]) + W[i-7] + R0(W[i-15]) + W[i-16]; + a = s->h[0]; + b = s->h[1]; + c = s->h[2]; + d = s->h[3]; + e = s->h[4]; + f = s->h[5]; + g = s->h[6]; + h = s->h[7]; + for (i = 0; i < 64; i++) { + t1 = h + S1(e) + Ch(e,f,g) + K[i] + W[i]; + t2 = S0(a) + Maj(a,b,c); + h = g; + g = f; + f = e; + e = d + t1; + d = c; + c = b; + b = a; + a = t1 + t2; + } + s->h[0] += a; + s->h[1] += b; + s->h[2] += c; + s->h[3] += d; + s->h[4] += e; + s->h[5] += f; + s->h[6] += g; + s->h[7] += h; +} + +static void pad(struct sha256 *s) +{ + unsigned r = s->len % 64; + + s->buf[r++] = 0x80; + if (r > 56) { + memset(s->buf + r, 0, 64 - r); + r = 0; + processblock(s, s->buf); + } + memset(s->buf + r, 0, 56 - r); + s->len *= 8; + s->buf[56] = s->len >> 56; + s->buf[57] = s->len >> 48; + s->buf[58] = s->len >> 40; + s->buf[59] = s->len >> 32; + s->buf[60] = s->len >> 24; + s->buf[61] = s->len >> 16; + s->buf[62] = s->len >> 8; + s->buf[63] = s->len; + processblock(s, s->buf); +} + +static void sha256_init(struct sha256 *s) +{ + s->len = 0; + s->h[0] = 0x6a09e667; + s->h[1] = 0xbb67ae85; + s->h[2] = 0x3c6ef372; + s->h[3] = 0xa54ff53a; + s->h[4] = 0x510e527f; + s->h[5] = 0x9b05688c; + s->h[6] = 0x1f83d9ab; + s->h[7] = 0x5be0cd19; +} + +static void sha256_sum(struct sha256 *s, uint8_t *md) +{ + int i; + + pad(s); + for (i = 0; i < 8; i++) { + md[4*i] = s->h[i] >> 24; + md[4*i+1] = s->h[i] >> 16; + md[4*i+2] = s->h[i] >> 8; + md[4*i+3] = s->h[i]; + } +} + +static void sha256_update(struct sha256 *s, const void *m, unsigned long len) +{ + const uint8_t *p = m; + unsigned r = s->len % 64; + + s->len += len; + if (r) { + if (len < 64 - r) { + memcpy(s->buf + r, p, len); + return; + } + memcpy(s->buf + r, p, 64 - r); + len -= 64 - r; + p += 64 - r; + processblock(s, s->buf); + } + for (; len >= 64; len -= 64, p += 64) + processblock(s, p); + memcpy(s->buf, p, len); +} + +// ---------------------------------------------------------------------- + +int dep_fd = -1; +int poolwr_fd = -1; +int poolrd_fd = -1; +int level = -1; +int implicit_jobs = 1; +int force = 0; + +static void +redo_ifcreate(char *target) +{ + dprintf(dep_fd, "-%s\n", target); +} + +static char * +check_dofile(char *fmt, ...) +{ + char dofile[1024]; + + va_list ap; + va_start(ap, fmt); + vsnprintf(dofile, sizeof dofile, fmt, ap); + va_end(ap); + + if (access (dofile, F_OK) == 0) { + return strdup(dofile); + } else { + redo_ifcreate(dofile); + return 0; + } +} + +/* +dir/base.a.b + will look for dir/base.a.b.do, + dir/default.a.b.do, dir/default.b.do, dir/default.do, default.a.b.do, + default.b.do, and default.do. + + // TODO: also traverse up directory +17:47:24 <@dalias> then yeah, just newfd=openat(dirfd, "..", O_RDONLY) +17:47:47 <@dalias> stat both of them and see if they have the same + (st_dev,st_ino) pair + +*/ +static char * +find_dofile(char *target) +{ + char *dofile; + + dofile = check_dofile("%s.do", target); + if (dofile) return dofile; + + char *s = target; + + while (*s) { + if (*s++ == '.') { + dofile = check_dofile("default.%s.do", s); + if (dofile) return dofile; + } + } + + return check_dofile("default.do"); +} + +static int +envfd(char *name) +{ + long fd; + + char *s = getenv(name); + if (!s) + return -1; + + fd = strtol(s, 0, 10); + if (fd < 0 || fd > 255) + fd = -1; + + return fd; +} + +static void +setenvfd(char *name, int i) +{ + char buf[16]; + snprintf(buf, sizeof buf, "%d", i); + setenv(name, buf, 1); +} + +static char * +hashfile(int fd) +{ + static char hex[16] = "0123456789abcdef"; + + struct sha256 ctx; + off_t off = 0; + char buf[4096]; + unsigned char hash[32]; + static char asciihash[65]; + int i; + ssize_t r; + + sha256_init(&ctx); + + while ((r = pread(fd, buf, sizeof buf, off)) > 0) { + sha256_update(&ctx, buf, r); + off += r; + } + + sha256_sum(&ctx, hash); + + for (i = 0; i < 32; i++) { + // TODO *asciihash++ = ? + asciihash[2*i] = hex[hash[i] / 16]; + asciihash[2*i+1] = hex[hash[i] % 16]; + } + asciihash[64] = 0; + + return asciihash; +} + +static int +check_deps(char *target) +{ + char *depfile; + FILE *f; + int ok = 1; + int fd; + + printf("checkdeps %s\n", target); + + if (access(target, F_OK) != 0) + return 0; + + asprintf(&depfile, ".%s.dep", target); + f = fopen(depfile, "r"); + if (!f) + ok = 0; + + while (ok && !feof(f)) { + char line[4096]; + if (fgets(line, sizeof line, f)) { + line[strlen(line)-1] = 0; // strip \n + printf ("CHECK %s\n", line); + switch (line[0]) { + case '-': // must not exist + if (access(line+1, F_OK) == 0) + ok = 0; + break; + case '=': // compare hash + fd = open(line + 1 + 64 + 1, O_RDONLY); + if (fd < 0) { + ok = 0; + } else { + char *hash = hashfile(fd); + if (strncmp(line+1, hash, 64) != 0) + ok = 0; + close(fd); + } + break; + case '!': // always rebuild + default: // dep file broken, lets recreate it + ok = 0; + } + } else { + if (!feof(f)) { + ok = 0; + break; + } + } + } + + fclose(f); + + printf("CHECKED %s %d\n", target, ok); + + return ok; +} + +struct job { + struct job *next; + pid_t pid; + char *target, *temp_depfile, *temp_target; + int implicit; +}; +struct job *jobhead; + +static void +insert_job(struct job *job) +{ + job->next = jobhead; + jobhead = job; +} + +static void +remove_job(struct job *job) +{ + if (jobhead == job) + jobhead = jobhead->next; + else { + struct job *j = jobhead; + while (j->next != job) + j = j->next; + j->next = j->next->next; + } +} + +static struct job * +find_job(pid_t pid) +{ + struct job *j; + + for (j = jobhead; j; j = j->next) { + printf("scan %d\n", j->pid); + if (j->pid == pid) + return j; + } + + return 0; +} + +static struct job * +run_script(char *target, int implicit) +{ + char *depfile; + asprintf(&depfile, ".%s.dep", target); + + char temp_depfile[] = ".dep.XXXXXX"; + int old_dep_fd = dep_fd; + dep_fd = mkstemp(temp_depfile); + + char temp_target[] = ".target.XXXXXX"; + int target_fd = mkstemp(temp_target); + close(target_fd); + + // TODO locking to detect parallel jobs building same target? + + char *dofile = find_dofile(target); + + if (!dofile) { + fprintf(stderr, "no dofile for %s.\n", target); + exit(1); + } + + int shellwrap = (access (dofile, X_OK) != 0); + + int fd = open(dofile, O_RDONLY); + dprintf(dep_fd, "=%s %s\n", hashfile(fd), dofile); + close(fd); + + pid_t pid; + + printf("redo%*.*s %s # %s\n", level*2, level*2, " ", target, dofile); + + pid = fork(); + if (pid < 0) { + perror("fork"); + exit(-1); + } else if (pid == 0) { // child +/* +djb-style default.o.do: + $1 foo.o + $2 foo + $3 whatever.tmp + + $1 all + $2 all (!!) + $3 whatever.tmp +*/ + int i; + + char *basename = strdup(target); + if (strchr(basename, '.')) { + for (i = strlen(basename)-1; i && basename[i] != '.'; i--) + basename[i] = 0; + basename[i--] = 0; + } + + close(old_dep_fd); + setenvfd("REDO_DEP_FD", dep_fd); + setenvfd("REDO_LEVEL", level + 1); + + system("ls -l /proc/$$/fd"); + + // TODO -x optional + if (shellwrap) + execl("/bin/sh", "/bin/sh", "-e", "-x", dofile, + target, basename, temp_target, (char *) 0); + else + execl(dofile, dofile, + target, basename, temp_target, (char *) 0); + exit(-1); + } else { + close(dep_fd); + dep_fd = old_dep_fd; + + struct job *job = malloc (sizeof *job); + if (!job) + exit(-1); + job->pid = pid; + job->target = target; + job->temp_depfile = strdup(temp_depfile); + job->temp_target = strdup(temp_target); + job->implicit = implicit; + + insert_job(job); + + printf("pid %d\n", pid); + + return job; + } + + // XXX vacate job when error happened before +} + +static int +try_procure(char *target) +{ + printf("try_procure imj %s %d\n", target, implicit_jobs); + + if (implicit_jobs > 0) { + implicit_jobs--; + return 1; + } else { + struct pollfd p; + + if (poolrd_fd < 0) + return 0; + + p.fd = poolrd_fd; + p.events = POLLIN; + + if (poll(&p, 1, 0) > 0 && p.revents & POLLIN) { + char buf[1]; + return read(poolrd_fd, &buf, 1) > 0; + } + return 0; + } +} + +static int +procure(char *target) +{ + printf("procure imj %s %d\n", target, implicit_jobs); + + if (implicit_jobs > 0) { + implicit_jobs--; + return 1; + } else { + char buf[1]; + return read(poolrd_fd, &buf, 1) > 0; + } +} + +void +create_pool() +{ + poolrd_fd = envfd("REDO_WR_FD"); + poolwr_fd = envfd("REDO_RD_FD"); + if (poolrd_fd < 0 || poolwr_fd < 0) { + int jobs = envfd("JOBS"); + if (jobs > 1) { + int i, fds[2]; + pipe(fds); + poolrd_fd = fds[0]; + poolwr_fd = fds[1]; + + for (i = 0; i < jobs-1; i++) + write(poolwr_fd, "\0", 1); + printf("enqueued %d tokens\n", jobs-1); + + setenvfd("REDO_RD_FD", poolrd_fd); + setenvfd("REDO_WR_FD", poolwr_fd); + } else { + poolrd_fd = -1; + poolwr_fd = -1; + } + } +} + +static void +redo_ifchange(int targetc, char *targetv[]) +{ + pid_t pid; + int status; + struct job *job; + + int targeti = 0; + + // XXX + char skip[targetc]; + + create_pool(); + + // check all targets whether needing rebuild + for (targeti = 0; targeti < targetc; targeti++) + skip[targeti] = force > 0 ? 0 : check_deps(targetv[targeti]); + + targeti = 0; + while (1) { + int procured = 0; + if (targeti < targetc) { + char *target = targetv[targeti]; + + if (skip[targeti]) { + targeti++; + continue; + } + + printf("looking at [%d] %s\n", targeti, target); + + if (try_procure(target)) { + procured = 1; + targeti++; + run_script(target, implicit_jobs >= 0); + } + } + + pid = waitpid(-1, &status, procured ? WNOHANG : 0); + + printf("waitpid %d %d %d/%d\n", pid, errno, targeti, targetc); + if (pid == 0) + continue; // nohang + + if (pid < 0) { + if (errno == ECHILD && targeti < targetc) + continue; // no child yet??? + else + break; // no child left + } + + if (WIFEXITED(status)) + status = WEXITSTATUS(status); + + job = find_job(pid); + + if (!job) { + printf("lost child pid=%d!?\n", pid); + exit(-1); + } + printf("job %d with temp_depfile %s %s exited with %d\n", + job->pid, job->temp_depfile, job->target, status); + + remove_job(job); + + if (status > 0) { + remove(job->temp_depfile); + remove(job->temp_target); + } else { + char *depfile; + asprintf(&depfile, ".%s.dep", job->target); + printf("renamed %s to %s.\n", job->temp_depfile, depfile); + rename(job->temp_depfile, depfile); + + struct stat st; + if (stat(job->temp_target, &st) == 0 && + st.st_size > 0) { + printf("renamed %s to %s.\n", job->temp_target, job->target); + rename(job->temp_target, job->target); + } + } + + printf("ji: %d\n", job->implicit); + if (job->implicit) + implicit_jobs++; + else + write(poolwr_fd, "\0", 1); + + // TODO: keep going on -k + if (status > 0) { + printf("failed with status %d\n", status); + exit(status); + } + } +} + +static void +record_deps(int targetc, char *targetv[]) +{ + int targeti = 0; + + dep_fd = envfd("REDO_DEP_FD"); + + for (targeti = 0; targeti < targetc; targeti++) { + int fd = open(targetv[targeti], O_RDONLY); + char *hash = hashfile(fd); + dprintf(dep_fd, "=%s!%s\n", hash, targetv[targeti]); + close(fd); + } +} + +int +main(int argc, char *argv[]) +{ + dep_fd = envfd("REDO_DEP_FD"); + printf("DEPFD %d\n", dep_fd); + + level = envfd("REDO_LEVEL"); + if (level < 0) + level = 0; + + force = envfd("REDO_FORCE"); + + // XXX check if this is safe... + char *program = basename(argv[0]); + + // XXX argument parsing: -k -jN -x/-v -f -C + + if (strcmp(program, "redo") == 0) { + force = 1; + redo_ifchange(argc-1, argv+1); + procure("REDO"); + } else if (strcmp(program, "redo-ifchange") == 0) { + redo_ifchange(argc-1, argv+1); + record_deps(argc-1, argv+1); + procure("REDO-IFCHANGE"); + } else if (strcmp(program, "redo-ifcreate") == 0) { + int i; + for (i = 1; i < argc; i++) + redo_ifcreate(argv[i]); + } else if (strcmp(program, "redo-always") == 0) { + dprintf(dep_fd, "!\n"); + } else if (strcmp(program, "redo-hash") == 0) { + printf("%s\n", hashfile(0)); + } else { + printf("not implemented %s\n", program); + } + + return 0; +} -- cgit 1.4.1