_ _
| |_ ___| |_ _
| | . | | | |
|_|_|___|_|_ |
|___|
git mirror - github.com/owenewans/holy - branch master
file src/graph.c
#define _POSIX_C_SOURCE 200809L
#include "graph.h"
#include "config.h"
#include "state.h"
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <unistd.h>
struct vertex {
char digest[65];
char *name;
char **providers;
size_t *links, count;
int explicit, reached;
};
struct graph {
struct vertex *vertices;
size_t count, edges;
unsigned long long generation;
};
static int digest_valid(const char *text)
{
return strlen(text) == 64 && strspn(text, "0123456789abcdef") == 64;
}
static int utf8_valid(const char *text)
{
const unsigned char *p = (const unsigned char *)text;
while (*p) {
size_t width, i;
if (*p < 128) { ++p; continue; }
width = *p >= 0xc2 && *p <= 0xdf ? 2 : *p >= 0xe0 && *p <= 0xef ? 3 :
*p >= 0xf0 && *p <= 0xf4 ? 4 : 0;
if (!width) return 0;
for (i = 1; i < width; ++i) if ((p[i] & 0xc0) != 0x80) return 0;
if ((*p == 0xe0 && p[1] < 0xa0) || (*p == 0xed && p[1] >= 0xa0) ||
(*p == 0xf0 && p[1] < 0x90) || (*p == 0xf4 && p[1] >= 0x90)) return 0;
p += width;
}
return 1;
}
static char *read_record(int dir, const char *name)
{
struct stat st;
size_t used = 0;
char *data = NULL;
errno = 0;
int fd = openat(dir, name, O_RDONLY | O_NOFOLLOW | O_NONBLOCK | O_CLOEXEC);
if (fd < 0) return NULL;
if (fstat(fd, &st) || !S_ISREG(st.st_mode) || st.st_size < 1 ||
st.st_size > 16 * 1024 * 1024) goto done;
data = malloc((size_t)st.st_size + 1);
if (!data) goto done;
while (used < (size_t)st.st_size) {
ssize_t got = read(fd, data + used, (size_t)st.st_size - used);
if (got < 0 && errno == EINTR) continue;
if (got <= 0) { free(data); data = NULL; goto done; }
used += (size_t)got;
}
if (memchr(data, 0, used) || data[used - 1] != '\n') { free(data); data = NULL; }
else data[used] = 0;
done:
close(fd);
return data;
}
static int collect(void *context, int root, int item, const char *digest)
{
struct graph *graph = context;
struct vertex *vertex, *grown;
static const char *const records[] = {"meta", "state", "graph"};
size_t r;
int reason_seen = 0, graph_member = 0, graph_root = 0;
char root_digest[65] = {0}, previous[65] = {0};
(void)root;
if (graph->count == 100000) return 1;
grown = realloc(graph->vertices, (graph->count + 1) * sizeof *grown);
if (!grown) return 1;
graph->vertices = grown;
vertex = &grown[graph->count++];
memset(vertex, 0, sizeof *vertex);
memcpy(vertex->digest, digest, 65);
for (r = 0; r < 3; ++r) {
char *data = read_record(item, records[r]), *line;
size_t number = 0;
int ok = 1;
if (!data) return r == 2 && errno == ENOENT ? 6 : 1;
for (line = data; *line; ) {
char *end = strchr(line, '\n'), **v = NULL, *error = NULL;
size_t count = 0;
++number;
if (!end || !holy_lex(line, (size_t)(end - line), &v, &count,
records[r], number, &error)) ok = 0;
if (ok && r == 0 && count && !strcmp(v[0], "name")) {
if (count != 2 || vertex->name || !v[1][0] || !utf8_valid(v[1]) ||
!(vertex->name = strdup(v[1]))) ok = 0;
} else if (ok && r == 1 && count && !strcmp(v[0], "reason")) {
if (count != 2 || reason_seen++ ||
(strcmp(v[1], "explicit") && strcmp(v[1], "dependency"))) ok = 0;
else vertex->explicit = !strcmp(v[1], "explicit");
} else if (ok && r == 1 && count && !strcmp(v[0], "generation")) {
char *last;
unsigned long long recorded;
errno = 0;
recorded = count == 2 ? strtoull(v[1], &last, 10) : 0;
if (count != 2 || errno || *last || recorded > graph->generation) ok = 0;
} else if (ok && r == 2) {
if (number == 1) ok = count == 2 && !strcmp(v[0], "format") && !strcmp(v[1], "holy-resolution-1");
else if (number == 2) ok = count == 2 && !strcmp(v[0], "scope") && !strcmp(v[1], "artifact-candidates");
else if (number == 3) {
ok = count == 2 && !strcmp(v[0], "root") && digest_valid(v[1]);
if (ok) memcpy(root_digest, v[1], 65);
} else if (count == 2 && !strcmp(v[0], "artifact")) {
ok = digest_valid(v[1]) && (!previous[0] || strcmp(previous, v[1]) < 0);
if (ok) {
memcpy(previous, v[1], 65);
if (!strcmp(v[1], digest)) graph_member = 1;
if (!strcmp(v[1], root_digest)) graph_root = 1;
}
} else if (count == 7 && !strcmp(v[0], "edge") &&
digest_valid(v[1]) && digest_valid(v[3]) && v[2][0] &&
v[4][0] && v[6][0] &&
(!strcmp(v[5], "package") || !strcmp(v[5], "file") ||
!strcmp(v[5], "command") ||
!strcmp(v[5], "interpreter") ||
!strcmp(v[5], "needed-path") || !strcmp(v[5], "soname") ||
!strcmp(v[5], "symbol"))) {
if (!strcmp(v[1], digest)) {
char **providers;
if (graph->edges == 1000000 ||
!(providers = realloc(vertex->providers, (vertex->count + 1) * sizeof *providers))) ok = 0;
else {
vertex->providers = providers;
providers[vertex->count] = strdup(v[3]);
if (!providers[vertex->count]) ok = 0;
else { ++vertex->count; ++graph->edges; }
}
}
} else ok = 0;
}
free(error);
holy_tokens_free(v, count);
if (!ok) break;
line = end + 1;
}
free(data);
if (!ok) return 1;
}
return vertex->name && reason_seen && graph_member && graph_root ? 0 : 1;
}
static size_t lookup(const struct graph *graph, const char *digest)
{
size_t low = 0, high = graph->count;
while (low < high) {
size_t mid = low + (high - low) / 2;
int order = strcmp(graph->vertices[mid].digest, digest);
if (order < 0) low = mid + 1;
else if (order > 0) high = mid;
else return mid;
}
return graph->count;
}
static void quoted(const char *text, int json)
{
const unsigned char *p = (const unsigned char *)text;
putchar('"');
for (; *p; ++p) {
if (*p == '"' || *p == '\\') printf("\\%c", *p);
else if (*p < 32 || *p == 127 || (!json && *p >= 128)) printf(json ? "\\u%04x" : "\\x%02x", *p);
else putchar(*p);
}
putchar('"');
}
static void free_graph(struct graph *graph)
{
size_t i, j;
for (i = 0; i < graph->count; ++i) {
struct vertex *v = &graph->vertices[i];
for (j = 0; j < v->count; ++j) free(v->providers[j]);
free(v->providers); free(v->links); free(v->name);
}
free(graph->vertices);
}
static int load_graph(const char *root, struct graph *graph)
{
size_t i, j;
int result = holy_state_visit(root, collect, graph, &graph->generation);
if (result) return result;
for (i = 0; i < graph->count; ++i) {
struct vertex *v = &graph->vertices[i];
v->links = calloc(v->count ? v->count : 1, sizeof *v->links);
if (!v->links) return 1;
for (j = 0; j < v->count; ++j) {
v->links[j] = lookup(graph, v->providers[j]);
if (v->links[j] == graph->count) {
fprintf(stderr, "holypkg: missing graph provider consumer=%s provider=%s\n",
v->digest, v->providers[j]);
return 4;
}
}
}
return 0;
}
int holy_orphan(const char *root, int json)
{
struct graph graph = {0};
size_t *queue = NULL, head = 0, tail = 0, roots = 0, orphans = 0, i, j;
int result = load_graph(root, &graph);
if (result) goto done;
queue = calloc(graph.count ? graph.count : 1, sizeof *queue);
if (!queue) { result = 1; goto done; }
for (i = 0; i < graph.count; ++i) {
struct vertex *v = &graph.vertices[i];
if (v->explicit) { v->reached = 1; queue[tail++] = i; ++roots; }
}
while (head < tail) {
struct vertex *v = &graph.vertices[queue[head++]];
for (j = 0; j < v->count; ++j) {
struct vertex *provider = &graph.vertices[v->links[j]];
if (!provider->reached) { provider->reached = 1; queue[tail++] = v->links[j]; }
}
}
for (i = 0; i < graph.count; ++i) if (!graph.vertices[i].reached) {
struct vertex *v = &graph.vertices[i];
++orphans;
if (json) {
printf("{\"schema\":\"holy-orphan-1\",\"type\":\"candidate\",\"artifact\":\"%s\",\"name\":", v->digest);
quoted(v->name, 1);
printf(",\"reason\":\"unreachable-from-explicit\",\"generation\":%llu}\n", graph.generation);
} else {
printf("orphan %s ", v->digest); quoted(v->name, 0);
puts(" reason=dependency unreachable-from-explicit");
}
}
if (json) printf("{\"schema\":\"holy-orphan-1\",\"type\":\"summary\",\"generation\":%llu,\"installed\":%zu,\"explicit\":%zu,\"reachable\":%zu,\"orphans\":%zu}\n",
graph.generation, graph.count, roots, tail, orphans);
else printf("generation %llu installed %zu explicit %zu reachable %zu orphans %zu read-only\n",
graph.generation, graph.count, roots, tail, orphans);
if (ferror(stdout)) result = 1;
done:
if (result) {
const char *code = result == 5 ? "incomplete-transaction" : result == 6 ? "unknown-installed-graph" :
result == 4 ? "missing-provider" : "invalid-state";
fprintf(stderr, "holypkg: orphan analysis unavailable: %s\n", code);
if (json) printf("{\"schema\":\"holy-orphan-1\",\"type\":\"error\",\"code\":\"%s\",\"status\":%d}\n", code, result);
}
free(queue); free_graph(&graph);
return result;
}
int holy_why(const char *digest, const char *root, int json)
{
struct graph graph = {0};
size_t *queue = NULL, *parent = NULL, *chain = NULL;
size_t i, j, head = 0, tail = 0, target, length = 0;
int result;
if (!digest || strlen(digest) != 64 ||
strspn(digest, "0123456789abcdef") != 64) return 2;
result = load_graph(root, &graph);
if (result) goto done;
target = lookup(&graph, digest);
if (target == graph.count) { result = 6; goto done; }
queue = calloc(graph.count, sizeof *queue);
parent = malloc(graph.count * sizeof *parent);
chain = malloc(graph.count * sizeof *chain);
if (!queue || !parent || !chain) { result = 1; goto done; }
for (i = 0; i < graph.count; ++i) parent[i] = graph.count;
for (i = 0; i < graph.count; ++i) if (graph.vertices[i].explicit) {
parent[i] = i;
queue[tail++] = i;
}
while (head < tail && parent[target] == graph.count) {
struct vertex *v = &graph.vertices[queue[head++]];
size_t from = (size_t)(v - graph.vertices);
for (j = 0; j < v->count; ++j) {
size_t to = v->links[j];
if (parent[to] == graph.count) {
parent[to] = from;
queue[tail++] = to;
}
}
}
if (parent[target] != graph.count) {
for (i = target; ; i = parent[i]) {
chain[length++] = i;
if (parent[i] == i) break;
}
for (i = length; i > 0; --i) {
struct vertex *v = &graph.vertices[chain[i - 1]];
if (json) {
printf("{\"schema\":\"holy-why-1\",\"type\":\"path\",\"depth\":%zu,\"artifact\":\"%s\",\"name\":",
length - i, v->digest);
quoted(v->name, 1);
printf(",\"reason\":\"%s\"}\n", v->explicit ? "explicit" : "dependency");
} else {
printf("path %zu %s ", length - i, v->digest);
quoted(v->name, 0);
printf(" reason=%s\n", v->explicit ? "explicit" : "dependency");
}
}
} else {
struct vertex *v = &graph.vertices[target];
if (json) {
printf("{\"schema\":\"holy-why-1\",\"type\":\"orphan\",\"artifact\":\"%s\",\"name\":",
v->digest);
quoted(v->name, 1);
puts(",\"reason\":\"unreachable-from-explicit\"}");
} else {
printf("orphan %s ", v->digest);
quoted(v->name, 0);
puts(" reason=dependency unreachable-from-explicit");
}
}
if (json)
printf("{\"schema\":\"holy-why-1\",\"type\":\"summary\",\"artifact\":\"%s\",\"generation\":%llu,\"reachable\":%s,\"depth\":%zu}\n",
digest, graph.generation, length ? "true" : "false", length);
else printf("generation %llu read-only\n", graph.generation);
if (ferror(stdout)) result = 1;
done:
if (result) {
const char *code = result == 5 ? "incomplete-transaction" :
result == 6 ? "unavailable-instance-or-graph" :
result == 4 ? "missing-provider" : "invalid-state";
fprintf(stderr, "holypkg: why unavailable: %s\n", code);
if (json) printf("{\"schema\":\"holy-why-1\",\"type\":\"error\",\"code\":\"%s\",\"status\":%d}\n",
code, result);
}
free(queue); free(parent); free(chain); free_graph(&graph);
return result;
}