|
1
|
|
-/* Merge HPC prototype run-length-encoded .tix files (NOT part of GHC).
|
|
|
1
|
+/* Group and merge HPC binary RLE .tix files without combining incompatible
|
|
|
2
|
+ * versions of the same module.
|
|
2
|
3
|
*
|
|
3
|
|
- * Build: cc -O3 -std=c11 -Wall -Wextra -o tix-rle-merge tix-rle-merge.c
|
|
4
|
|
- * Usage: ./tix-rle-merge RLE_DIRECTORY OUTPUT.tix
|
|
|
4
|
+ * Build: cc -O2 -std=c11 -Wall -Wextra -pedantic -o tix-rle-merge tix-rle-merge-grouped.c
|
|
|
5
|
+ * Usage: tix-rle-merge INPUT_DIRECTORY EMPTY_OUTPUT_DIRECTORY
|
|
5
|
6
|
*
|
|
6
|
|
- * Input and output format (HPCTIX\2):
|
|
7
|
|
- * 7 bytes "HPCTIX\2", ULEB128 module count;
|
|
8
|
|
- * for each module:
|
|
9
|
|
- * ULEB128 name length, name bytes, little-endian uint32 hash,
|
|
10
|
|
- * ULEB128 box count;
|
|
11
|
|
- * repeated (ULEB128 zero-run length, ULEB128 nonzero-run length,
|
|
12
|
|
- * that many positive ULEB128 Word64 counts)
|
|
13
|
|
- * until exactly 'box count' counters are described.
|
|
|
7
|
+ * Input format: "HPCTIX\0", ULEB128 number of modules; each module has
|
|
|
8
|
+ * ULEB128 name length, name bytes, little-endian uint32 HPC hash, ULEB128
|
|
|
9
|
+ * box count, then alternating (zero run, nonzero run, positive counter values)
|
|
|
10
|
+ * encoded in ULEB128 until all box positions are covered. Output is the same.
|
|
14
|
11
|
*
|
|
15
|
|
- * No terminator follows an RLE module. A trailing zero run is represented
|
|
16
|
|
- * by (zero-run length, 0). Modules with zero boxes contain no run records.
|
|
|
12
|
+ * Group assignment is greedy, deterministic (lexicographic filename order):
|
|
|
13
|
+ * - never group files with a shared module name but different hash/box count;
|
|
|
14
|
+ * - require at least one shared module to merge into an existing group;
|
|
|
15
|
+ * - prefer the compatible group sharing the most boxes, then most modules,
|
|
|
16
|
+ * then most existing files, then lowest group number;
|
|
|
17
|
+ * - otherwise create a new group.
|
|
17
|
18
|
*
|
|
18
|
|
- * The accumulator is a dense uint64_t array per distinct module, as in
|
|
19
|
|
- * tix-sparse-prototype.c. Checks counter overflow and malformed inputs.
|
|
|
19
|
+ * This is a conservative heuristic, not a unique/optimal partition.
|
|
|
20
|
+ * Results are in merged-0001.tix, ... ; assignments.tsv lists every input;
|
|
|
21
|
+ * groups.txt gives group sizes, contents and split explanations. The output
|
|
|
22
|
+ * directory must be empty (or nonexistent) to avoid stale results.
|
|
|
23
|
+ *
|
|
|
24
|
+ * Two passes: inspect all inputs and assign groups without retaining counters;
|
|
|
25
|
+ * then merge and write one group at a time. Thus memory is bounded by the
|
|
|
26
|
+ * metadata for the groups plus one dense set of counters.
|
|
20
|
27
|
*/
|
|
21
|
28
|
#define _POSIX_C_SOURCE 200809L
|
|
22
|
29
|
#include <dirent.h>
|
|
23
|
30
|
#include <errno.h>
|
|
24
|
31
|
#include <inttypes.h>
|
|
|
32
|
+#include <limits.h>
|
|
25
|
33
|
#include <stdint.h>
|
|
26
|
34
|
#include <stdio.h>
|
|
27
|
35
|
#include <stdlib.h>
|
| ... |
... |
@@ -29,16 +37,35 @@ |
|
29
|
37
|
#include <sys/stat.h>
|
|
30
|
38
|
|
|
31
|
39
|
#define MAGIC "HPCTIX\0"
|
|
|
40
|
+#define MAGIC_SIZE 7
|
|
32
|
41
|
#define BUCKETS 8192
|
|
33
|
42
|
|
|
34
|
43
|
typedef struct { unsigned char *data; size_t len, cap; } Buffer;
|
|
35
|
44
|
typedef struct { const unsigned char *p, *end; } Reader;
|
|
|
45
|
+typedef struct { char *name; uint32_t hash; size_t n; } InputMod;
|
|
|
46
|
+typedef struct { InputMod *mods; size_t len, cap; } Input;
|
|
|
47
|
+typedef struct Sig {
|
|
|
48
|
+ char *name;
|
|
|
49
|
+ uint32_t hash;
|
|
|
50
|
+ size_t n;
|
|
|
51
|
+ const char *first_path; /* borrowed from sorted input path list */
|
|
|
52
|
+ struct Sig *next;
|
|
|
53
|
+} Sig;
|
|
|
54
|
+typedef struct {
|
|
|
55
|
+ Sig *buckets[BUCKETS];
|
|
|
56
|
+ size_t *indices; /* indices into the sorted input path list */
|
|
|
57
|
+ size_t len, cap, modules;
|
|
|
58
|
+ char *reason;
|
|
|
59
|
+} Group;
|
|
|
60
|
+typedef struct {
|
|
|
61
|
+ size_t group, shared_modules;
|
|
|
62
|
+ uint64_t shared_boxes;
|
|
|
63
|
+} Assignment;
|
|
36
|
64
|
typedef struct Module {
|
|
37
|
65
|
char *name;
|
|
38
|
66
|
uint32_t hash;
|
|
39
|
67
|
size_t n;
|
|
40
|
|
- uint64_t *ticks;
|
|
41
|
|
- uint64_t seen_epoch;
|
|
|
68
|
+ uint64_t *ticks, seen_epoch;
|
|
42
|
69
|
struct Module *next;
|
|
43
|
70
|
} Module;
|
|
44
|
71
|
typedef struct {
|
| ... |
... |
@@ -58,11 +85,22 @@ static void *xmalloc(size_t n) { |
|
58
|
85
|
if (!p) die("out of memory");
|
|
59
|
86
|
return p;
|
|
60
|
87
|
}
|
|
|
88
|
+static void *xcalloc(size_t n, size_t s) {
|
|
|
89
|
+ if (s && n > SIZE_MAX / s) die("allocation overflow");
|
|
|
90
|
+ void *p = calloc(n ? n : 1, s ? s : 1);
|
|
|
91
|
+ if (!p) die("out of memory");
|
|
|
92
|
+ return p;
|
|
|
93
|
+}
|
|
61
|
94
|
static void *xrealloc(void *p, size_t n) {
|
|
62
|
95
|
void *q = realloc(p, n ? n : 1);
|
|
63
|
96
|
if (!q) die("out of memory");
|
|
64
|
97
|
return q;
|
|
65
|
98
|
}
|
|
|
99
|
+static char *xstrdup(const char *s) {
|
|
|
100
|
+ char *p = strdup(s);
|
|
|
101
|
+ if (!p) die("out of memory");
|
|
|
102
|
+ return p;
|
|
|
103
|
+}
|
|
66
|
104
|
static void reserve(Buffer *b, size_t add) {
|
|
67
|
105
|
if (add > SIZE_MAX - b->len) die("buffer too large");
|
|
68
|
106
|
size_t need = b->len + add;
|
| ... |
... |
@@ -97,20 +135,20 @@ static void put32(Buffer *b, uint32_t x) { |
|
97
|
135
|
static uint64_t getvar(Reader *r) {
|
|
98
|
136
|
uint64_t x = 0;
|
|
99
|
137
|
for (unsigned k = 0; k < 10; k++) {
|
|
100
|
|
- if (r->p == r->end) die("truncated variable-length integer");
|
|
|
138
|
+ if (r->p == r->end) die("truncated ULEB128");
|
|
101
|
139
|
unsigned c = *r->p++;
|
|
102
|
|
- if (k == 9 && (c & 0xfe)) die("variable-length integer overflow");
|
|
|
140
|
+ if (k == 9 && (c & 0xfe)) die("ULEB128 overflow");
|
|
103
|
141
|
x |= (uint64_t)(c & 127) << (7*k);
|
|
104
|
142
|
if (!(c & 128)) {
|
|
105
|
|
- if (k && c == 0) die("noncanonical variable-length integer");
|
|
|
143
|
+ if (k && c == 0) die("noncanonical ULEB128");
|
|
106
|
144
|
return x;
|
|
107
|
145
|
}
|
|
108
|
146
|
}
|
|
109
|
|
- die("unterminated variable-length integer");
|
|
|
147
|
+ die("unterminated ULEB128");
|
|
110
|
148
|
return 0;
|
|
111
|
149
|
}
|
|
112
|
150
|
static uint32_t get32(Reader *r) {
|
|
113
|
|
- if ((size_t)(r->end - r->p) < 4) die("truncated hash");
|
|
|
151
|
+ if ((size_t)(r->end - r->p) < 4) die("truncated module hash");
|
|
114
|
152
|
uint32_t x = 0;
|
|
115
|
153
|
for (unsigned k = 0; k < 4; k++) x |= (uint32_t)(*r->p++) << (8*k);
|
|
116
|
154
|
return x;
|
| ... |
... |
@@ -139,24 +177,194 @@ static uint64_t namehash(const char *s) { |
|
139
|
177
|
for (; *s; s++) { h ^= (unsigned char)*s; h *= UINT64_C(1099511628211); }
|
|
140
|
178
|
return h;
|
|
141
|
179
|
}
|
|
142
|
|
-static Module *module(Acc *a, const char *name, uint32_t hash, size_t n) {
|
|
143
|
|
- size_t bucket = namehash(name) % BUCKETS;
|
|
144
|
|
- for (Module *m = a->buckets[bucket]; m; m = m->next) {
|
|
|
180
|
+static size_t bucket_of(const char *s) { return (size_t)(namehash(s) % BUCKETS); }
|
|
|
181
|
+static char *join(const char *dir, const char *file) {
|
|
|
182
|
+ size_t a = strlen(dir), b = strlen(file);
|
|
|
183
|
+ if (a > SIZE_MAX - b - 2) die("path too long");
|
|
|
184
|
+ char *p = xmalloc(a + b + 2);
|
|
|
185
|
+ snprintf(p, a + b + 2, "%s/%s", dir, file);
|
|
|
186
|
+ return p;
|
|
|
187
|
+}
|
|
|
188
|
+static int is_tix(const char *s) {
|
|
|
189
|
+ size_t n = strlen(s);
|
|
|
190
|
+ return n >= 4 && strcmp(s + n - 4, ".tix") == 0;
|
|
|
191
|
+}
|
|
|
192
|
+static int cmpstr(const void *a, const void *b) {
|
|
|
193
|
+ return strcmp(*(char *const *)a, *(char *const *)b);
|
|
|
194
|
+}
|
|
|
195
|
+static int cmp_input_mod(const void *a, const void *b) {
|
|
|
196
|
+ return strcmp(((const InputMod *)a)->name, ((const InputMod *)b)->name);
|
|
|
197
|
+}
|
|
|
198
|
+static void input_append(Input *in, const char *name, uint32_t hash, size_t n) {
|
|
|
199
|
+ if (in->len == in->cap) {
|
|
|
200
|
+ if (in->cap > SIZE_MAX / (2 * sizeof(*in->mods))) die("too many modules");
|
|
|
201
|
+ in->cap = in->cap ? in->cap * 2 : 64;
|
|
|
202
|
+ in->mods = xrealloc(in->mods, in->cap * sizeof(*in->mods));
|
|
|
203
|
+ }
|
|
|
204
|
+ in->mods[in->len++] = (InputMod){xstrdup(name), hash, n};
|
|
|
205
|
+}
|
|
|
206
|
+static void input_free(Input *in) {
|
|
|
207
|
+ for (size_t i = 0; i < in->len; i++) free(in->mods[i].name);
|
|
|
208
|
+ free(in->mods);
|
|
|
209
|
+}
|
|
|
210
|
+/* Validate the complete file and collect just its module signatures. */
|
|
|
211
|
+static Input inspect(const char *path) {
|
|
|
212
|
+ context = path;
|
|
|
213
|
+ size_t size;
|
|
|
214
|
+ unsigned char *data = readfile(path, &size);
|
|
|
215
|
+ Reader r = {data, data + size};
|
|
|
216
|
+ if (size < MAGIC_SIZE || memcmp(r.p, MAGIC, MAGIC_SIZE))
|
|
|
217
|
+ die("wrong magic/version (expected HPCTIX\\0)");
|
|
|
218
|
+ r.p += MAGIC_SIZE;
|
|
|
219
|
+ uint64_t nmods = getvar(&r);
|
|
|
220
|
+ if (nmods > (uint64_t)(r.end - r.p)) die("invalid module count");
|
|
|
221
|
+ Input in = {0};
|
|
|
222
|
+ for (uint64_t j = 0; j < nmods; j++) {
|
|
|
223
|
+ uint64_t length = getvar(&r);
|
|
|
224
|
+ if (length > SIZE_MAX - 1 || length > (uint64_t)(r.end - r.p))
|
|
|
225
|
+ die("invalid module name length");
|
|
|
226
|
+ char *name = xmalloc((size_t)length + 1);
|
|
|
227
|
+ memcpy(name, r.p, (size_t)length);
|
|
|
228
|
+ name[length] = 0;
|
|
|
229
|
+ if (memchr(name, 0, (size_t)length)) die("embedded NUL in module name");
|
|
|
230
|
+ r.p += (size_t)length;
|
|
|
231
|
+ uint32_t hash = get32(&r);
|
|
|
232
|
+ uint64_t boxes = getvar(&r);
|
|
|
233
|
+ if (boxes > SIZE_MAX / sizeof(uint64_t)) die("too many counters");
|
|
|
234
|
+ input_append(&in, name, hash, (size_t)boxes);
|
|
|
235
|
+ free(name);
|
|
|
236
|
+ size_t pos = 0;
|
|
|
237
|
+ while (pos < (size_t)boxes) {
|
|
|
238
|
+ uint64_t zeros = getvar(&r);
|
|
|
239
|
+ if (zeros > boxes - pos) die("zero run exceeds box count");
|
|
|
240
|
+ pos += (size_t)zeros;
|
|
|
241
|
+ uint64_t nonzeros = getvar(&r);
|
|
|
242
|
+ if (nonzeros > boxes - pos) die("nonzero run exceeds box count");
|
|
|
243
|
+ if (!zeros && !nonzeros) die("empty RLE record");
|
|
|
244
|
+ for (uint64_t k = 0; k < nonzeros; k++) {
|
|
|
245
|
+ if (!getvar(&r)) die("zero counter in nonzero run");
|
|
|
246
|
+ }
|
|
|
247
|
+ pos += (size_t)nonzeros;
|
|
|
248
|
+ }
|
|
|
249
|
+ }
|
|
|
250
|
+ if (r.p != r.end) die("unexpected trailing bytes");
|
|
|
251
|
+ free(data);
|
|
|
252
|
+ qsort(in.mods, in.len, sizeof(*in.mods), cmp_input_mod);
|
|
|
253
|
+ for (size_t i = 1; i < in.len; i++)
|
|
|
254
|
+ if (!strcmp(in.mods[i-1].name, in.mods[i].name)) die("duplicate module in input");
|
|
|
255
|
+ return in;
|
|
|
256
|
+}
|
|
|
257
|
+static Sig *lookup(const Group *g, const char *name) {
|
|
|
258
|
+ for (Sig *s = g->buckets[bucket_of(name)]; s; s = s->next)
|
|
|
259
|
+ if (!strcmp(s->name, name)) return s;
|
|
|
260
|
+ return NULL;
|
|
|
261
|
+}
|
|
|
262
|
+typedef struct {
|
|
|
263
|
+ size_t shared, conflicts;
|
|
|
264
|
+ uint64_t boxes;
|
|
|
265
|
+ const InputMod *bad_input;
|
|
|
266
|
+ const Sig *bad_group;
|
|
|
267
|
+} Comparison;
|
|
|
268
|
+static Comparison compare(const Group *g, const Input *in) {
|
|
|
269
|
+ Comparison c = {0};
|
|
|
270
|
+ for (size_t j = 0; j < in->len; j++) {
|
|
|
271
|
+ const InputMod *m = &in->mods[j];
|
|
|
272
|
+ const Sig *s = lookup(g, m->name);
|
|
|
273
|
+ if (!s) continue;
|
|
|
274
|
+ if (s->hash != m->hash || s->n != m->n) {
|
|
|
275
|
+ c.conflicts++;
|
|
|
276
|
+ if (!c.bad_input) { c.bad_input = m; c.bad_group = s; }
|
|
|
277
|
+ } else {
|
|
|
278
|
+ c.shared++;
|
|
|
279
|
+ if (UINT64_MAX - c.boxes < m->n) c.boxes = UINT64_MAX;
|
|
|
280
|
+ else c.boxes += m->n;
|
|
|
281
|
+ }
|
|
|
282
|
+ }
|
|
|
283
|
+ return c;
|
|
|
284
|
+}
|
|
|
285
|
+static void group_add(Group *g, const Input *in, size_t index, const char *path) {
|
|
|
286
|
+ for (size_t j = 0; j < in->len; j++) {
|
|
|
287
|
+ const InputMod *m = &in->mods[j];
|
|
|
288
|
+ if (lookup(g, m->name)) continue;
|
|
|
289
|
+ Sig *s = xmalloc(sizeof(*s));
|
|
|
290
|
+ *s = (Sig){xstrdup(m->name), m->hash, m->n, path, g->buckets[bucket_of(m->name)]};
|
|
|
291
|
+ g->buckets[bucket_of(m->name)] = s;
|
|
|
292
|
+ g->modules++;
|
|
|
293
|
+ }
|
|
|
294
|
+ if (g->len == g->cap) {
|
|
|
295
|
+ if (g->cap > SIZE_MAX / (2 * sizeof(*g->indices))) die("too many input files");
|
|
|
296
|
+ g->cap = g->cap ? 2 * g->cap : 16;
|
|
|
297
|
+ g->indices = xrealloc(g->indices, g->cap * sizeof(*g->indices));
|
|
|
298
|
+ }
|
|
|
299
|
+ g->indices[g->len++] = index;
|
|
|
300
|
+}
|
|
|
301
|
+static void group_free(Group *g) {
|
|
|
302
|
+ for (size_t i = 0; i < BUCKETS; i++) {
|
|
|
303
|
+ Sig *s = g->buckets[i];
|
|
|
304
|
+ while (s) { Sig *next = s->next; free(s->name); free(s); s = next; }
|
|
|
305
|
+ }
|
|
|
306
|
+ free(g->indices);
|
|
|
307
|
+ free(g->reason);
|
|
|
308
|
+ free(g);
|
|
|
309
|
+}
|
|
|
310
|
+static int better(const Comparison *a, const Group *ga,
|
|
|
311
|
+ const Comparison *b, const Group *gb) {
|
|
|
312
|
+ if (a->boxes != b->boxes) return a->boxes > b->boxes;
|
|
|
313
|
+ if (a->shared != b->shared) return a->shared > b->shared;
|
|
|
314
|
+ return ga->len > gb->len;
|
|
|
315
|
+}
|
|
|
316
|
+static char *reason_for_new_group(Group **groups, size_t ng, const Input *in) {
|
|
|
317
|
+ if (!ng) return xstrdup("first input");
|
|
|
318
|
+ size_t nearest = SIZE_MAX, rejected = 0, unrelated = 0;
|
|
|
319
|
+ Comparison closest = {0};
|
|
|
320
|
+ for (size_t i = 0; i < ng; i++) {
|
|
|
321
|
+ Comparison c = compare(groups[i], in);
|
|
|
322
|
+ if (c.conflicts) {
|
|
|
323
|
+ rejected++;
|
|
|
324
|
+ if (nearest == SIZE_MAX || c.boxes > closest.boxes ||
|
|
|
325
|
+ (c.boxes == closest.boxes && c.shared > closest.shared)) {
|
|
|
326
|
+ nearest = i;
|
|
|
327
|
+ closest = c;
|
|
|
328
|
+ }
|
|
|
329
|
+ } else if (!c.shared) unrelated++;
|
|
|
330
|
+ }
|
|
|
331
|
+ char msg[1024];
|
|
|
332
|
+ if (nearest != SIZE_MAX) {
|
|
|
333
|
+ const InputMod *m = closest.bad_input;
|
|
|
334
|
+ const Sig *s = closest.bad_group;
|
|
|
335
|
+ snprintf(msg, sizeof(msg),
|
|
|
336
|
+ "incompatible with %zu group(s); closest group %04zu shares "
|
|
|
337
|
+ "%zu modules (%" PRIu64 " boxes), but %zu conflict(s); "
|
|
|
338
|
+ "e.g. %s: existing hash=%08" PRIx32 " boxes=%zu (from %s); "
|
|
|
339
|
+ "incoming hash=%08" PRIx32 " boxes=%zu",
|
|
|
340
|
+ rejected, nearest + 1, closest.shared, closest.boxes,
|
|
|
341
|
+ closest.conflicts, m->name, s->hash, s->n, s->first_path,
|
|
|
342
|
+ m->hash, m->n);
|
|
|
343
|
+ } else {
|
|
|
344
|
+ snprintf(msg, sizeof(msg),
|
|
|
345
|
+ "no shared module signatures with %zu existing group(s) (%zu disjoint)",
|
|
|
346
|
+ ng, unrelated);
|
|
|
347
|
+ }
|
|
|
348
|
+ return xstrdup(msg);
|
|
|
349
|
+}
|
|
|
350
|
+
|
|
|
351
|
+/* The second pass is the original dense-counter merger, one group at a time. */
|
|
|
352
|
+static Module *acc_module(Acc *a, const char *name, uint32_t hash, size_t n) {
|
|
|
353
|
+ size_t b = bucket_of(name);
|
|
|
354
|
+ for (Module *m = a->buckets[b]; m; m = m->next) {
|
|
145
|
355
|
if (strcmp(m->name, name)) continue;
|
|
146
|
|
- if (m->hash != hash || m->n != n) die("incompatible module hash/number of boxes");
|
|
|
356
|
+ if (m->hash != hash || m->n != n) die("grouping error: incompatible module");
|
|
147
|
357
|
return m;
|
|
148
|
358
|
}
|
|
149
|
359
|
if (n > SIZE_MAX / sizeof(uint64_t)) die("module too large");
|
|
150
|
360
|
Module *m = xmalloc(sizeof(*m));
|
|
151
|
|
- m->name = strdup(name);
|
|
152
|
|
- if (!m->name) die("out of memory");
|
|
|
361
|
+ *m = (Module){0};
|
|
|
362
|
+ m->name = xstrdup(name);
|
|
153
|
363
|
m->hash = hash;
|
|
154
|
364
|
m->n = n;
|
|
155
|
|
- m->ticks = calloc(n ? n : 1, sizeof(uint64_t));
|
|
156
|
|
- if (!m->ticks) die("out of memory");
|
|
157
|
|
- m->seen_epoch = 0;
|
|
158
|
|
- m->next = a->buckets[bucket];
|
|
159
|
|
- a->buckets[bucket] = m;
|
|
|
365
|
+ m->ticks = xcalloc(n ? n : 1, sizeof(uint64_t));
|
|
|
366
|
+ m->next = a->buckets[b];
|
|
|
367
|
+ a->buckets[b] = m;
|
|
160
|
368
|
if (a->len == a->cap) {
|
|
161
|
369
|
if (a->cap > SIZE_MAX / (2 * sizeof(*a->mods))) die("too many modules");
|
|
162
|
370
|
a->cap = a->cap ? 2 * a->cap : 256;
|
| ... |
... |
@@ -170,47 +378,40 @@ static void mergeone(Acc *a, const char *path) { |
|
170
|
378
|
size_t size;
|
|
171
|
379
|
unsigned char *data = readfile(path, &size);
|
|
172
|
380
|
Reader r = {data, data + size};
|
|
173
|
|
- if (size < 7 || memcmp(r.p, MAGIC, 7)) die("wrong magic/version (expected HPCTIX\\2)");
|
|
174
|
|
- r.p += 7;
|
|
|
381
|
+ if (size < MAGIC_SIZE || memcmp(r.p, MAGIC, MAGIC_SIZE)) die("wrong magic/version");
|
|
|
382
|
+ r.p += MAGIC_SIZE;
|
|
175
|
383
|
uint64_t nmods = getvar(&r);
|
|
176
|
|
- if (nmods > (uint64_t)(r.end - r.p)) die("invalid module count");
|
|
177
|
384
|
if (++a->epoch == 0) die("epoch overflow");
|
|
178
|
|
-
|
|
179
|
385
|
for (uint64_t j = 0; j < nmods; j++) {
|
|
180
|
|
- uint64_t name_len = getvar(&r);
|
|
181
|
|
- if (name_len > SIZE_MAX - 1 || name_len > (uint64_t)(r.end - r.p))
|
|
|
386
|
+ uint64_t length = getvar(&r);
|
|
|
387
|
+ if (length > SIZE_MAX - 1 || length > (uint64_t)(r.end - r.p))
|
|
182
|
388
|
die("invalid name length");
|
|
183
|
|
- char *name = xmalloc((size_t)name_len + 1);
|
|
184
|
|
- memcpy(name, r.p, (size_t)name_len);
|
|
185
|
|
- name[name_len] = 0;
|
|
186
|
|
- if (memchr(name, 0, (size_t)name_len)) die("embedded NUL in module name");
|
|
187
|
|
- r.p += (size_t)name_len;
|
|
|
389
|
+ char *name = xmalloc((size_t)length + 1);
|
|
|
390
|
+ memcpy(name, r.p, (size_t)length);
|
|
|
391
|
+ name[length] = 0;
|
|
|
392
|
+ r.p += (size_t)length;
|
|
188
|
393
|
uint32_t hash = get32(&r);
|
|
189
|
394
|
uint64_t boxes = getvar(&r);
|
|
190
|
395
|
if (boxes > SIZE_MAX / sizeof(uint64_t)) die("too many counters");
|
|
191
|
|
- Module *m = module(a, name, hash, (size_t)boxes);
|
|
|
396
|
+ Module *m = acc_module(a, name, hash, (size_t)boxes);
|
|
192
|
397
|
free(name);
|
|
193
|
|
- if (m->seen_epoch == a->epoch) die("duplicate module");
|
|
|
398
|
+ if (m->seen_epoch == a->epoch) die("duplicate module in input");
|
|
194
|
399
|
m->seen_epoch = a->epoch;
|
|
195
|
|
-
|
|
196
|
|
- /* RLE records account for exactly 'boxes' positions. */
|
|
197
|
400
|
size_t pos = 0;
|
|
198
|
401
|
while (pos < m->n) {
|
|
199
|
402
|
uint64_t zeros = getvar(&r);
|
|
200
|
|
- if (zeros > m->n - pos) die("zero run exceeds module box count");
|
|
|
403
|
+ if (zeros > m->n - pos) die("zero run exceeds box count");
|
|
201
|
404
|
pos += (size_t)zeros;
|
|
202
|
405
|
uint64_t nonzeros = getvar(&r);
|
|
203
|
|
- if (nonzeros > m->n - pos) die("nonzero run exceeds module box count");
|
|
|
406
|
+ if (nonzeros > m->n - pos) die("nonzero run exceeds box count");
|
|
204
|
407
|
if (!zeros && !nonzeros) die("empty RLE record");
|
|
205
|
|
-
|
|
206
|
|
- size_t stop = pos + (size_t)nonzeros;
|
|
207
|
|
- for (; pos < stop; pos++) {
|
|
208
|
|
- uint64_t value = getvar(&r);
|
|
209
|
|
- if (!value) die("zero value in nonzero run");
|
|
210
|
|
- if (UINT64_MAX - m->ticks[pos] < value) die("counter overflow");
|
|
211
|
|
- m->ticks[pos] += value;
|
|
|
408
|
+ for (uint64_t k = 0; k < nonzeros; k++, pos++) {
|
|
|
409
|
+ uint64_t v = getvar(&r);
|
|
|
410
|
+ if (!v) die("zero counter in nonzero run");
|
|
|
411
|
+ if (v > UINT64_MAX - m->ticks[pos]) die("counter overflow");
|
|
|
412
|
+ m->ticks[pos] += v;
|
|
212
|
413
|
}
|
|
213
|
|
- if (UINT64_MAX - a->input_entries < nonzeros) die("entry count overflow");
|
|
|
414
|
+ if (nonzeros > UINT64_MAX - a->input_entries) die("entry count overflow");
|
|
214
|
415
|
a->input_entries += nonzeros;
|
|
215
|
416
|
}
|
|
216
|
417
|
}
|
| ... |
... |
@@ -222,60 +423,78 @@ static int cmpmod(const void *a, const void *b) { |
|
222
|
423
|
const Module *const *x = a, *const *y = b;
|
|
223
|
424
|
return strcmp((*x)->name, (*y)->name);
|
|
224
|
425
|
}
|
|
225
|
|
-static Buffer serialise(const Acc *a) {
|
|
|
426
|
+static Buffer serialise(Acc *a) {
|
|
226
|
427
|
Buffer b = {0};
|
|
227
|
|
- bytes(&b, MAGIC, 7);
|
|
|
428
|
+ qsort(a->mods, a->len, sizeof(*a->mods), cmpmod);
|
|
|
429
|
+ bytes(&b, MAGIC, MAGIC_SIZE);
|
|
228
|
430
|
putvar(&b, a->len);
|
|
229
|
431
|
for (size_t j = 0; j < a->len; j++) {
|
|
230
|
432
|
Module *m = a->mods[j];
|
|
231
|
|
- size_t name_len = strlen(m->name);
|
|
232
|
|
- putvar(&b, name_len);
|
|
233
|
|
- bytes(&b, m->name, name_len);
|
|
|
433
|
+ size_t length = strlen(m->name);
|
|
|
434
|
+ putvar(&b, length);
|
|
|
435
|
+ bytes(&b, m->name, length);
|
|
234
|
436
|
put32(&b, m->hash);
|
|
235
|
437
|
putvar(&b, m->n);
|
|
236
|
|
-
|
|
237
|
438
|
size_t i = 0;
|
|
238
|
439
|
while (i < m->n) {
|
|
239
|
440
|
size_t start = i;
|
|
240
|
|
- while (i < m->n && m->ticks[i] == 0) i++;
|
|
|
441
|
+ while (i < m->n && !m->ticks[i]) i++;
|
|
241
|
442
|
putvar(&b, i - start);
|
|
242
|
443
|
start = i;
|
|
243
|
|
- while (i < m->n && m->ticks[i] != 0) i++;
|
|
|
444
|
+ while (i < m->n && m->ticks[i]) i++;
|
|
244
|
445
|
putvar(&b, i - start);
|
|
245
|
446
|
for (size_t k = start; k < i; k++) putvar(&b, m->ticks[k]);
|
|
246
|
447
|
}
|
|
247
|
448
|
}
|
|
248
|
449
|
return b;
|
|
249
|
450
|
}
|
|
250
|
|
-static int is_tix(const char *s) {
|
|
251
|
|
- size_t n = strlen(s);
|
|
252
|
|
- return n >= 4 && strcmp(s + n - 4, ".tix") == 0;
|
|
|
451
|
+static void acc_free(Acc *a) {
|
|
|
452
|
+ for (size_t i = 0; i < a->len; i++) {
|
|
|
453
|
+ free(a->mods[i]->name);
|
|
|
454
|
+ free(a->mods[i]->ticks);
|
|
|
455
|
+ free(a->mods[i]);
|
|
|
456
|
+ }
|
|
|
457
|
+ free(a->mods);
|
|
253
|
458
|
}
|
|
254
|
|
-static int cmpstr(const void *a, const void *b) {
|
|
255
|
|
- return strcmp(*(char *const *)a, *(char *const *)b);
|
|
|
459
|
+static void output_name(char *buf, size_t cap, size_t group) {
|
|
|
460
|
+ if (snprintf(buf, cap, "merged-%04zu.tix", group + 1) >= (int)cap)
|
|
|
461
|
+ die("too many output groups");
|
|
|
462
|
+}
|
|
|
463
|
+static void ensure_empty_output_dir(const char *in, const char *out) {
|
|
|
464
|
+ if (mkdir(out, 0777) && errno != EEXIST) { perror(out); exit(1); }
|
|
|
465
|
+ struct stat a, b;
|
|
|
466
|
+ if (stat(in, &a) || stat(out, &b) || !S_ISDIR(b.st_mode))
|
|
|
467
|
+ die("invalid input/output directory");
|
|
|
468
|
+ if (a.st_dev == b.st_dev && a.st_ino == b.st_ino)
|
|
|
469
|
+ die("output directory must differ from input directory");
|
|
|
470
|
+ DIR *d = opendir(out);
|
|
|
471
|
+ if (!d) { perror(out); exit(1); }
|
|
|
472
|
+ struct dirent *e;
|
|
|
473
|
+ while ((e = readdir(d))) {
|
|
|
474
|
+ if (!strcmp(e->d_name, ".") || !strcmp(e->d_name, "..")) continue;
|
|
|
475
|
+ closedir(d);
|
|
|
476
|
+ die("output directory is not empty");
|
|
|
477
|
+ }
|
|
|
478
|
+ closedir(d);
|
|
256
|
479
|
}
|
|
257
|
|
-static void merge_dir(const char *dir, const char *output) {
|
|
|
480
|
+static void checked_close(FILE *f) {
|
|
|
481
|
+ if (fclose(f)) die("could not write report");
|
|
|
482
|
+}
|
|
|
483
|
+static void merge_dir(const char *dir, const char *dest) {
|
|
|
484
|
+ context = dir;
|
|
258
|
485
|
DIR *d = opendir(dir);
|
|
259
|
486
|
if (!d) { perror(dir); exit(1); }
|
|
260
|
487
|
char **paths = NULL;
|
|
261
|
488
|
size_t n = 0, cap = 0;
|
|
262
|
489
|
struct dirent *e;
|
|
263
|
|
- struct stat outstat;
|
|
264
|
|
- int output_exists = stat(output, &outstat) == 0;
|
|
265
|
490
|
while ((e = readdir(d))) {
|
|
266
|
491
|
if (!is_tix(e->d_name)) continue;
|
|
267
|
|
- size_t dlen = strlen(dir), flen = strlen(e->d_name);
|
|
268
|
|
- if (dlen > SIZE_MAX - flen - 2) die("path too long");
|
|
269
|
|
- char *path = xmalloc(dlen + flen + 2);
|
|
270
|
|
- snprintf(path, dlen + flen + 2, "%s/%s", dir, e->d_name);
|
|
|
492
|
+ char *path = join(dir, e->d_name);
|
|
271
|
493
|
struct stat st;
|
|
272
|
494
|
if (stat(path, &st) || !S_ISREG(st.st_mode)) { free(path); continue; }
|
|
273
|
|
- if (!strcmp(path, output) ||
|
|
274
|
|
- (output_exists && st.st_dev == outstat.st_dev && st.st_ino == outstat.st_ino))
|
|
275
|
|
- die("output file is among input files");
|
|
276
|
495
|
if (n == cap) {
|
|
277
|
496
|
if (cap > SIZE_MAX / (2 * sizeof(*paths))) die("too many input files");
|
|
278
|
|
- cap = cap ? 2 * cap : 256;
|
|
|
497
|
+ cap = cap ? cap * 2 : 256;
|
|
279
|
498
|
paths = xrealloc(paths, cap * sizeof(*paths));
|
|
280
|
499
|
}
|
|
281
|
500
|
paths[n++] = path;
|
| ... |
... |
@@ -283,32 +502,104 @@ static void merge_dir(const char *dir, const char *output) { |
|
283
|
502
|
closedir(d);
|
|
284
|
503
|
if (!n) die("no input .tix files");
|
|
285
|
504
|
qsort(paths, n, sizeof(*paths), cmpstr);
|
|
286
|
|
- Acc a = {0};
|
|
|
505
|
+ ensure_empty_output_dir(dir, dest);
|
|
|
506
|
+
|
|
|
507
|
+ Group **groups = NULL;
|
|
|
508
|
+ size_t ng = 0, gcap = 0;
|
|
|
509
|
+ Assignment *assign = xcalloc(n, sizeof(*assign));
|
|
287
|
510
|
for (size_t i = 0; i < n; i++) {
|
|
288
|
|
- mergeone(&a, paths[i]);
|
|
289
|
|
- free(paths[i]);
|
|
290
|
|
- if (a.filecount % 1000 == 0)
|
|
291
|
|
- fprintf(stderr, "Merged %" PRIu64 " files\n", a.filecount);
|
|
|
511
|
+ Input in = inspect(paths[i]);
|
|
|
512
|
+ size_t best = SIZE_MAX;
|
|
|
513
|
+ Comparison bestc = {0};
|
|
|
514
|
+ for (size_t j = 0; j < ng; j++) {
|
|
|
515
|
+ Comparison c = compare(groups[j], &in);
|
|
|
516
|
+ if (c.conflicts || !c.shared) continue;
|
|
|
517
|
+ if (best == SIZE_MAX || better(&c, groups[j], &bestc, groups[best])) {
|
|
|
518
|
+ best = j;
|
|
|
519
|
+ bestc = c;
|
|
|
520
|
+ }
|
|
|
521
|
+ }
|
|
|
522
|
+ if (best == SIZE_MAX) {
|
|
|
523
|
+ if (ng == gcap) {
|
|
|
524
|
+ if (gcap > SIZE_MAX / (2 * sizeof(*groups))) die("too many groups");
|
|
|
525
|
+ gcap = gcap ? gcap * 2 : 8;
|
|
|
526
|
+ groups = xrealloc(groups, gcap * sizeof(*groups));
|
|
|
527
|
+ }
|
|
|
528
|
+ Group *g = xcalloc(1, sizeof(*g));
|
|
|
529
|
+ g->reason = reason_for_new_group(groups, ng, &in);
|
|
|
530
|
+ groups[ng] = g;
|
|
|
531
|
+ best = ng++;
|
|
|
532
|
+ fprintf(stderr, "New group %04zu from %s: %s\n",
|
|
|
533
|
+ best + 1, paths[i], g->reason);
|
|
|
534
|
+ }
|
|
|
535
|
+ group_add(groups[best], &in, i, paths[i]);
|
|
|
536
|
+ assign[i] = (Assignment){best, bestc.shared, bestc.boxes};
|
|
|
537
|
+ input_free(&in);
|
|
|
538
|
+ if ((i + 1) % 1000 == 0)
|
|
|
539
|
+ fprintf(stderr, "Classified %zu/%zu inputs into %zu groups\n", i + 1, n, ng);
|
|
292
|
540
|
}
|
|
293
|
|
- free(paths);
|
|
294
|
|
- qsort(a.mods, a.len, sizeof(*a.mods), cmpmod);
|
|
295
|
|
- Buffer out = serialise(&a);
|
|
296
|
|
- context = output;
|
|
297
|
|
- writefile(output, out.data, out.len);
|
|
298
|
|
- fprintf(stderr, "Merged %" PRIu64 " files, %zu modules, %" PRIu64
|
|
299
|
|
- " nonzero input counters; result %zu bytes\n",
|
|
300
|
|
- a.filecount, a.len, a.input_entries, out.len);
|
|
301
|
|
- free(out.data);
|
|
302
|
|
- for (size_t i = 0; i < a.len; i++) {
|
|
303
|
|
- free(a.mods[i]->ticks);
|
|
304
|
|
- free(a.mods[i]->name);
|
|
305
|
|
- free(a.mods[i]);
|
|
|
541
|
+
|
|
|
542
|
+ char *manifest_path = join(dest, "assignments.tsv");
|
|
|
543
|
+ FILE *manifest = fopen(manifest_path, "wb");
|
|
|
544
|
+ if (!manifest) { perror(manifest_path); exit(1); }
|
|
|
545
|
+ fprintf(manifest, "output\tinput\tshared_modules\tshared_boxes\n");
|
|
|
546
|
+ for (size_t i = 0; i < n; i++) {
|
|
|
547
|
+ char name[80];
|
|
|
548
|
+ output_name(name, sizeof(name), assign[i].group);
|
|
|
549
|
+ fprintf(manifest, "%s\t%s\t%zu\t%" PRIu64 "\n",
|
|
|
550
|
+ name, paths[i], assign[i].shared_modules, assign[i].shared_boxes);
|
|
306
|
551
|
}
|
|
307
|
|
- free(a.mods);
|
|
|
552
|
+ checked_close(manifest);
|
|
|
553
|
+ free(manifest_path);
|
|
|
554
|
+
|
|
|
555
|
+ char *report_path = join(dest, "groups.txt");
|
|
|
556
|
+ FILE *report = fopen(report_path, "wb");
|
|
|
557
|
+ if (!report) { perror(report_path); exit(1); }
|
|
|
558
|
+ fprintf(report, "%zu input files -> %zu output groups\n", n, ng);
|
|
|
559
|
+ fprintf(report, "Assignments: largest shared box count, then module count, "
|
|
|
560
|
+ "then existing file count; no incompatible modules permitted.\n\n");
|
|
|
561
|
+
|
|
|
562
|
+ for (size_t gi = 0; gi < ng; gi++) {
|
|
|
563
|
+ Group *g = groups[gi];
|
|
|
564
|
+ Acc *a = xcalloc(1, sizeof(*a));
|
|
|
565
|
+ for (size_t j = 0; j < g->len; j++) mergeone(a, paths[g->indices[j]]);
|
|
|
566
|
+ if (a->len != g->modules) die("grouping error: module count changed");
|
|
|
567
|
+ Buffer b = serialise(a);
|
|
|
568
|
+ char name[80];
|
|
|
569
|
+ output_name(name, sizeof(name), gi);
|
|
|
570
|
+ char *target = join(dest, name);
|
|
|
571
|
+ context = target;
|
|
|
572
|
+ writefile(target, b.data, b.len);
|
|
|
573
|
+ fprintf(stderr, "%s: %zu input files, %zu modules, %" PRIu64
|
|
|
574
|
+ " nonzero input counters, %zu output bytes\n",
|
|
|
575
|
+ target, g->len, a->len, a->input_entries, b.len);
|
|
|
576
|
+ fprintf(report, "%s: %zu files, %zu modules, %zu bytes\n",
|
|
|
577
|
+ name, g->len, a->len, b.len);
|
|
|
578
|
+ fprintf(report, " Started by: %s\n Reason: %s\n",
|
|
|
579
|
+ paths[g->indices[0]], g->reason);
|
|
|
580
|
+ for (size_t j = 0; j < g->len; j++) {
|
|
|
581
|
+ size_t index = g->indices[j];
|
|
|
582
|
+ fprintf(report, " %s [matched %zu modules, %" PRIu64 " boxes]\n",
|
|
|
583
|
+ paths[index], assign[index].shared_modules, assign[index].shared_boxes);
|
|
|
584
|
+ }
|
|
|
585
|
+ fputc('\n', report);
|
|
|
586
|
+ free(target);
|
|
|
587
|
+ free(b.data);
|
|
|
588
|
+ acc_free(a);
|
|
|
589
|
+ free(a);
|
|
|
590
|
+ }
|
|
|
591
|
+ checked_close(report);
|
|
|
592
|
+ fprintf(stderr, "Done: %zu files -> %zu output groups; diagnostics: %s\n", n, ng, report_path);
|
|
|
593
|
+ free(report_path);
|
|
|
594
|
+ for (size_t i = 0; i < ng; i++) group_free(groups[i]);
|
|
|
595
|
+ free(groups);
|
|
|
596
|
+ free(assign);
|
|
|
597
|
+ for (size_t i = 0; i < n; i++) free(paths[i]);
|
|
|
598
|
+ free(paths);
|
|
308
|
599
|
}
|
|
309
|
600
|
int main(int argc, char **argv) {
|
|
310
|
601
|
if (argc != 3) {
|
|
311
|
|
- fprintf(stderr, "Usage: %s RLE_DIRECTORY OUTPUT.tix\n", argv[0]);
|
|
|
602
|
+ fprintf(stderr, "Usage: %s INPUT_DIRECTORY EMPTY_OUTPUT_DIRECTORY\n", argv[0]);
|
|
312
|
603
|
return 2;
|
|
313
|
604
|
}
|
|
314
|
605
|
merge_dir(argv[1], argv[2]);
|