profile.c 17.5 KiB raw
1
/* Deterministic hosted instruction profiles. */
2
#define _POSIX_C_SOURCE 200809L
3
4
#include <fcntl.h>
5
#include <stdio.h>
6
#include <stdlib.h>
7
#include <string.h>
8
#include <unistd.h>
9
10
#include <blake3.h>
11
12
#include "debug_map.h"
13
#include "hosted.h"
14
#include "io.h"
15
#include "profile.h"
16
17
/* A name and its byte offset from the start of the image's code. */
18
struct symbol {
19
    u32   offset;
20
    char *name;
21
};
22
23
/* A page indexes 64 instructions. Its entry bits recognize jump targets,
24
 * and first gives the start of the page's names in the sorted symbol table. */
25
struct symbol_page {
26
    u64 entries;
27
    u32 first;
28
};
29
30
/* One unique call stack, stored with its parent stack. Index zero is empty. */
31
struct stack_node {
32
    u32 parent;
33
    u32 pc;
34
    u64 self;
35
};
36
37
/* One active invocation. */
38
struct frame {
39
    u32  node;
40
    u32  pc;
41
    u32  link; /* Guest return address. Tail calls share their caller's link. */
42
    u64  start;
43
    u64  self;
44
    u64  invocation; /* Sequence number for a selected function, or zero. */
45
    bool tail;       /* The frame below shares this frame's return. */
46
};
47
48
struct profile {
49
    const u8               *memory;
50
    u32                     base;
51
    u32                     bytes;
52
    const struct debug_map *debug;
53
    FILE                   *trace;
54
    FILE                   *folded;
55
    FILE                   *pcs;
56
    FILE                   *calls;
57
    bool                    failed;
58
    bool                    track_calls;
59
    u32                     function_pc;
60
    u64                     invocations;
61
    struct symbol          *symbols;
62
    size_t                  symbol_count;
63
    struct symbol_page     *symbol_pages;
64
    /* Range updates give per-PC counts with two additions per recorded range.
65
     */
66
    u64               *pc_delta;
67
    struct stack_node *nodes;
68
    size_t             node_count;
69
    size_t             node_capacity;
70
    u32               *node_hash;
71
    size_t             hash_capacity;
72
    struct frame      *frames;
73
    size_t             depth;
74
    size_t             frame_capacity;
75
    u64                total;
76
    u32                last_pc;
77
};
78
79
static void *resize(void *data, size_t count, size_t size) {
80
    void *result = realloc(data, count * size);
81
    if (!result)
82
        bail("cannot allocate instruction profile");
83
    return result;
84
}
85
86
static FILE *open_output(const char *prefix, const char *suffix) {
87
    size_t size = strlen(prefix) + strlen(suffix) + 1;
88
    char  *path = resize(NULL, size, 1);
89
    snprintf(path, size, "%s%s", prefix, suffix);
90
    int   fd   = open(path, O_WRONLY | O_CREAT | O_EXCL | O_CLOEXEC, 0666);
91
    FILE *file = fd < 0 ? NULL : fdopen(fd, "wb");
92
    if (!file)
93
        bail("cannot create profile output '%s'", path);
94
    free(path);
95
    return file;
96
}
97
98
static int compare_symbols(const void *a, const void *b) {
99
    const struct symbol *left = a, *right = b;
100
    if (left->offset != right->offset)
101
        return left->offset < right->offset ? -1 : 1;
102
    return strcmp(left->name, right->name);
103
}
104
105
static void load_symbols(struct profile *p, const char *program) {
106
    size_t size = 0;
107
    u8    *data = debug_read_sidecar(program, ".symbols", &size);
108
    if (!data)
109
        return;
110
111
    /* Magic and text digest, then (byte offset, name length) and name bytes. */
112
    if (size < 40 || memcmp(data, "RADSYM01", 8))
113
        bail("invalid symbol map for '%s'", program);
114
    blake3_hasher hasher;
115
    u8            digest[BLAKE3_OUT_LEN];
116
    blake3_hasher_init(&hasher);
117
    blake3_hasher_update(&hasher, p->memory + p->base, p->bytes);
118
    blake3_hasher_finalize(&hasher, digest, sizeof(digest));
119
    if (memcmp(digest, data + 8, sizeof(digest))) {
120
        fprintf(stderr, "symbol map does not match '%s'\n", program);
121
        free(data);
122
        return;
123
    }
124
    size_t capacity = 0;
125
    for (size_t pos = 40; pos < size;) {
126
        if (size - pos < 8)
127
            bail("truncated symbol map for '%s'", program);
128
        u32 offset  = decode_u32_le(data + pos);
129
        u32 len     = decode_u32_le(data + pos + 4);
130
        pos        += 8;
131
        if (offset > p->bytes || offset % INSTR_SIZE || !len ||
132
            len > size - pos || memchr(data + pos, 0, len))
133
            bail("invalid symbol in map for '%s'", program);
134
        /* A label at the end of the text has no instructions. */
135
        if (offset != p->bytes) {
136
            if (p->symbol_count == capacity) {
137
                capacity   = capacity ? 2 * capacity : 64;
138
                p->symbols = resize(p->symbols, capacity, sizeof(*p->symbols));
139
            }
140
            char *name = resize(NULL, (size_t)len + 1, 1);
141
            memcpy(name, data + pos, len);
142
            name[len]                     = 0;
143
            p->symbols[p->symbol_count++] = (struct symbol){ offset, name };
144
        }
145
        pos += len;
146
    }
147
    free(data);
148
    if (!p->symbol_count)
149
        return;
150
    qsort(p->symbols, p->symbol_count, sizeof(*p->symbols), compare_symbols);
151
152
    u32 page_bytes  = 64 * INSTR_SIZE;
153
    u32 pages       = (p->bytes + page_bytes - 1) / page_bytes;
154
    p->symbol_pages = calloc(pages + 1, sizeof(*p->symbol_pages));
155
    if (!p->symbol_pages)
156
        bail("cannot allocate profile symbol index");
157
    u32 symbol = 0;
158
    for (u32 i = 0; i < pages; i++) {
159
        struct symbol_page *page = &p->symbol_pages[i];
160
        page->first              = symbol;
161
        u32 end                  = (i + 1) * page_bytes;
162
        while (symbol < p->symbol_count && p->symbols[symbol].offset < end) {
163
            u32 index      = p->symbols[symbol++].offset / INSTR_SIZE;
164
            page->entries |= 1ull << (index % 64);
165
        }
166
    }
167
    p->symbol_pages[pages].first = symbol;
168
}
169
170
/* Return the index page if offset identifies a function entry. */
171
static const struct symbol_page *entry_page(
172
    const struct profile *p, u32 offset
173
) {
174
    if (!p->symbol_pages || offset >= p->bytes || offset % INSTR_SIZE)
175
        return NULL;
176
    u32                       index = offset / INSTR_SIZE;
177
    const struct symbol_page *page  = &p->symbol_pages[index / 64];
178
    return (page->entries & (1ull << (index % 64))) ? page : NULL;
179
}
180
181
/* Render a field that is also safe as a folded-stack frame. */
182
static void field(FILE *file, const char *str) {
183
    size_t n = strcspn(str, ";\t\r\n");
184
    if (!str[n]) {
185
        fputs(str, file);
186
        return;
187
    }
188
    for (; *str; str++)
189
        fputc(strchr(";\t\r\n", *str) ? '_' : (unsigned char)*str, file);
190
}
191
192
static void frame_name(FILE *file, const struct profile *p, u32 pc) {
193
    u32                       offset = pc - p->base;
194
    const struct symbol_page *page   = entry_page(p, offset);
195
    if (page) {
196
        /* Search backward so an exact match uses the last alias. */
197
        u32 symbol = page[1].first - 1;
198
        while (p->symbols[symbol].offset != offset)
199
            symbol--;
200
        field(file, p->symbols[symbol].name);
201
        return;
202
    }
203
    fprintf(file, "0x%x", pc);
204
    if (offset < p->bytes) {
205
        const struct debug_entry *loc = debug_map_lookup(p->debug, offset);
206
        if (loc) {
207
            fputc('@', file);
208
            field(file, loc->file);
209
            fprintf(file, ":%u", loc->offset);
210
        }
211
    }
212
}
213
214
static size_t node_slot(const struct profile *p, u32 parent, u32 pc) {
215
    u64 key      = ((u64)parent << 32) | pc;
216
    key         ^= key >> 33;
217
    key         *= 0xff51afd7ed558ccduLL;
218
    key         ^= key >> 33;
219
    size_t slot  = (size_t)key & (p->hash_capacity - 1);
220
    while (p->node_hash[slot]) {
221
        const struct stack_node *node = &p->nodes[p->node_hash[slot]];
222
        if (node->parent == parent && node->pc == pc)
223
            break;
224
        slot = (slot + 1) & (p->hash_capacity - 1);
225
    }
226
    return slot;
227
}
228
229
static u32 stack_node(struct profile *p, u32 parent, u32 pc) {
230
    if (p->node_count * 2 >= p->hash_capacity) {
231
        free(p->node_hash);
232
        p->hash_capacity = p->hash_capacity ? p->hash_capacity * 2 : 128;
233
        p->node_hash     = calloc(p->hash_capacity, sizeof(*p->node_hash));
234
        if (!p->node_hash)
235
            bail("cannot allocate profile stack index");
236
        for (u32 i = 1; i < p->node_count; i++)
237
            p->node_hash[node_slot(p, p->nodes[i].parent, p->nodes[i].pc)] = i;
238
    }
239
    size_t slot = node_slot(p, parent, pc);
240
    if (p->node_hash[slot])
241
        return p->node_hash[slot];
242
    if (p->node_count >= p->node_capacity) {
243
        p->node_capacity = p->node_capacity ? p->node_capacity * 2 : 64;
244
        p->nodes = resize(p->nodes, p->node_capacity, sizeof(*p->nodes));
245
    }
246
    u32 index          = (u32)p->node_count++;
247
    p->nodes[index]    = (struct stack_node){ .parent = parent, .pc = pc };
248
    p->node_hash[slot] = index;
249
    return index;
250
}
251
252
static void enter(struct profile *p, u32 pc, u32 link, bool tail) {
253
    if (p->depth == p->frame_capacity) {
254
        p->frame_capacity = p->frame_capacity ? p->frame_capacity * 2 : 32;
255
        p->frames = resize(p->frames, p->frame_capacity, sizeof(*p->frames));
256
    }
257
    u32           parent = p->depth ? p->frames[p->depth - 1].node : 0;
258
    struct frame *frame  = &p->frames[p->depth++];
259
    *frame               = (struct frame){
260
        .node  = p->folded ? stack_node(p, parent, pc) : 0,
261
        .pc    = pc,
262
        .link  = link,
263
        .start = p->total,
264
        .tail  = tail,
265
    };
266
    if (p->track_calls && pc == p->function_pc)
267
        frame->invocation = ++p->invocations;
268
}
269
270
static void leave(struct profile *p, bool returned) {
271
    const struct frame *f = &p->frames[--p->depth];
272
    if (f->invocation)
273
        fprintf(
274
            p->calls,
275
            "%llu\t%llu\t%llu\t%s\n",
276
            (unsigned long long)f->invocation,
277
            (unsigned long long)f->self,
278
            (unsigned long long)(p->total - f->start),
279
            returned ? "returned" : "stopped"
280
        );
281
}
282
283
static bool is_link(u32 reg) {
284
    return reg == RA || reg == T0;
285
}
286
287
/* Complete the invocation whose link is the actual return target.
288
 * A transfer to an outer frame stops any intervening active calls. */
289
static bool return_to(struct profile *p, u32 target) {
290
    for (size_t i = p->depth; i; i--) {
291
        if (p->frames[i - 1].link != target)
292
            continue;
293
        while (p->depth > i)
294
            leave(p, false);
295
        bool tail;
296
        do {
297
            tail = p->frames[p->depth - 1].tail;
298
            leave(p, true);
299
        } while (tail);
300
        return true;
301
    }
302
    return false;
303
}
304
305
static bool is_return(instr_t ins) {
306
    return ins.r.opcode == OP_JALR && is_link(ins.i.rs1) &&
307
           (!is_link(ins.i.rd) || ins.i.rd != ins.i.rs1);
308
}
309
310
/* Apply the transfer at the end of the previous range with its actual target.
311
 */
312
static void transfer(struct profile *p, u32 target) {
313
    if (!p->depth) {
314
        enter(p, target, 0, false);
315
        return;
316
    }
317
    u32 prev = p->last_pc;
318
    if (prev - p->base >= p->bytes)
319
        return;
320
    instr_t ins = { .raw = decode_u32_le(p->memory + prev) };
321
    if (ins.r.opcode != OP_JAL && ins.r.opcode != OP_JALR)
322
        return;
323
    u32 rd = ins.r.rd;
324
    if (is_return(ins) && return_to(p, target) && !is_link(rd)) {
325
        if (!p->depth)
326
            enter(p, target, 0, false);
327
        return;
328
    }
329
    if (is_link(rd)) {
330
        enter(p, target, prev + INSTR_SIZE, false);
331
        return;
332
    }
333
334
    const struct frame *frame = &p->frames[p->depth - 1];
335
    if (rd == ZERO && frame->pc != target && entry_page(p, target - p->base))
336
        enter(p, target, frame->link, true);
337
}
338
339
struct profile *profile_open(
340
    const char             *program,
341
    const u8               *memory,
342
    u32                     base,
343
    u32                     bytes,
344
    const struct debug_map *debug,
345
    const char             *prefix,
346
    const char             *trace,
347
    const char             *function
348
) {
349
    struct profile *p = calloc(1, sizeof(*p));
350
    if (!p)
351
        bail("cannot allocate instruction profile");
352
    p->memory     = memory;
353
    p->base       = base;
354
    p->bytes      = bytes;
355
    p->debug      = debug;
356
    p->node_count = 1; /* Reserve the empty stack. */
357
    if (prefix || function)
358
        load_symbols(p, program);
359
    if (function) {
360
        for (size_t i = 0; i < p->symbol_count; i++) {
361
            if (!strcmp(function, p->symbols[i].name)) {
362
                p->track_calls = true;
363
                p->function_pc = base + p->symbols[i].offset;
364
                break;
365
            }
366
        }
367
        if (!p->track_calls)
368
            bail(
369
                "profile function '%s' is absent from '%s.symbols'",
370
                function,
371
                program
372
            );
373
        if (prefix) {
374
            p->calls = open_output(prefix, ".calls.tsv");
375
        } else {
376
            int fd = fcntl(STDERR_FILENO, F_DUPFD_CLOEXEC, 3);
377
            if (fd < 0 || !(p->calls = fdopen(fd, "w")))
378
                bail("cannot open the call report stream");
379
        }
380
        fputs("call\tself\tinclusive\tstatus\n", p->calls);
381
    }
382
    if (prefix) {
383
        p->folded = open_output(prefix, ".folded");
384
        p->pcs    = open_output(prefix, ".pcs.tsv");
385
        p->pc_delta =
386
            calloc((size_t)bytes / INSTR_SIZE + 1, sizeof(*p->pc_delta));
387
        if (!p->pc_delta)
388
            bail("cannot allocate profile PC counters");
389
    }
390
    if (trace) {
391
        p->trace = open_output(trace, "");
392
        /* RVTRACE1, code base and size, then packed range words.
393
         * All integer fields are little-endian. */
394
        u8 header[16] = "RVTRACE1";
395
        encode_le(header + 8, base, 4);
396
        encode_le(header + 12, bytes, 4);
397
        p->failed |=
398
            fwrite(header, 1, sizeof(header), p->trace) != sizeof(header);
399
    }
400
    return p;
401
}
402
403
void profile_record(struct profile *p, const u32 *ranges, const u32 *end) {
404
    if (p->trace && !p->failed) {
405
        const u16 little_endian = 1;
406
        if (*(const u8 *)&little_endian) {
407
            size_t n   = (size_t)(end - ranges);
408
            p->failed |= fwrite(ranges, sizeof(*ranges), n, p->trace) != n;
409
        } else {
410
            for (const u32 *r = ranges; r < end; r++) {
411
                u8 bytes[4];
412
                encode_le(bytes, *r, sizeof(bytes));
413
                p->failed |=
414
                    fwrite(bytes, 1, sizeof(bytes), p->trace) != sizeof(bytes);
415
            }
416
        }
417
    }
418
    if (!p->folded && !p->calls)
419
        return;
420
    for (const u32 *r = ranges; r < end;) {
421
        u32 word  = *r++;
422
        u32 count = (word >> PROFILE_PC_BITS) + 1;
423
        u32 pc    = word & PROFILE_PC_MASK;
424
        if (word == PROFILE_PC_ESCAPE) {
425
            pc    = *r++;
426
            count = 1;
427
        }
428
        u32 offset = pc - p->base;
429
        if (p->pc_delta && offset < p->bytes) {
430
            u32 index = offset / INSTR_SIZE;
431
            u32 words = p->bytes / INSTR_SIZE - index;
432
            p->pc_delta[index]++;
433
            p->pc_delta[index + (count < words ? count : words)]--;
434
        }
435
        transfer(p, pc);
436
        struct frame *f = &p->frames[p->depth - 1];
437
        if (p->folded)
438
            p->nodes[f->node].self += count;
439
        f->self    += count;
440
        p->total   += count;
441
        p->last_pc  = pc + (count - 1) * INSTR_SIZE;
442
    }
443
}
444
445
bool profile_close(struct profile *p, u32 next_pc, bool continued) {
446
    if (!p)
447
        return true;
448
    if (continued && p->depth && p->last_pc - p->base < p->bytes) {
449
        instr_t ins = { .raw = decode_u32_le(p->memory + p->last_pc) };
450
        if (is_return(ins))
451
            return_to(p, next_pc);
452
    }
453
    while (p->depth)
454
        leave(p, false);
455
456
    if (p->folded) {
457
        u32 *path = resize(NULL, p->node_count, sizeof(*path));
458
        for (u32 i = 1; i < p->node_count; i++) {
459
            if (!p->nodes[i].self)
460
                continue;
461
            size_t depth = 0;
462
            for (u32 node = i; node; node = p->nodes[node].parent)
463
                path[depth++] = p->nodes[node].pc;
464
            while (depth) {
465
                frame_name(p->folded, p, path[--depth]);
466
                if (depth)
467
                    fputc(';', p->folded);
468
            }
469
            fprintf(p->folded, " %llu\n", (unsigned long long)p->nodes[i].self);
470
        }
471
        free(path);
472
473
        fputs("pc\tinstructions\tfunction\tsource\tbyte_offset\n", p->pcs);
474
        u64                  count       = 0;
475
        size_t               next_symbol = 0;
476
        const struct symbol *sym         = NULL;
477
        for (u32 i = 0; i < p->bytes / INSTR_SIZE; i++) {
478
            count += p->pc_delta[i];
479
            if (!count)
480
                continue;
481
            u32 offset = i * INSTR_SIZE;
482
            while (next_symbol < p->symbol_count &&
483
                   p->symbols[next_symbol].offset <= offset)
484
                sym = &p->symbols[next_symbol++];
485
            const struct debug_entry *loc = debug_map_lookup(p->debug, offset);
486
            if (sym && loc && loc->pc < sym->offset)
487
                loc = NULL;
488
            fprintf(
489
                p->pcs,
490
                "0x%x\t%llu\t",
491
                p->base + offset,
492
                (unsigned long long)count
493
            );
494
            if (sym)
495
                field(p->pcs, sym->name);
496
            if (loc) {
497
                fputc('\t', p->pcs);
498
                field(p->pcs, loc->file);
499
                fprintf(p->pcs, "\t%u", loc->offset);
500
            } else {
501
                fputs("\t\t", p->pcs);
502
            }
503
            fputc('\n', p->pcs);
504
        }
505
    }
506
507
    FILE *outputs[] = { p->folded, p->pcs, p->trace, p->calls };
508
    for (size_t i = 0; i < sizeof(outputs) / sizeof(*outputs); i++) {
509
        FILE *file = outputs[i];
510
        if (file) {
511
            p->failed |= ferror(file) != 0;
512
            p->failed |= fclose(file) != 0;
513
        }
514
    }
515
    bool ok = !p->failed;
516
    for (size_t i = 0; i < p->symbol_count; i++)
517
        free(p->symbols[i].name);
518
    free(p->symbols);
519
    free(p->symbol_pages);
520
    free(p->pc_delta);
521
    free(p->nodes);
522
    free(p->node_hash);
523
    free(p->frames);
524
    free(p);
525
    return ok;
526
}