/* Deterministic hosted instruction profiles. */ #define _POSIX_C_SOURCE 200809L #include #include #include #include #include #include #include "debug_map.h" #include "hosted.h" #include "io.h" #include "profile.h" /* A name and its byte offset from the start of the image's code. */ struct symbol { u32 offset; char *name; }; /* A page indexes 64 instructions. Its entry bits recognize jump targets, * and first gives the start of the page's names in the sorted symbol table. */ struct symbol_page { u64 entries; u32 first; }; /* One unique call stack, stored with its parent stack. Index zero is empty. */ struct stack_node { u32 parent; u32 pc; u64 self; }; /* One active invocation. */ struct frame { u32 node; u32 pc; u32 link; /* Guest return address. Tail calls share their caller's link. */ u64 start; u64 self; u64 invocation; /* Sequence number for a selected function, or zero. */ bool tail; /* The frame below shares this frame's return. */ }; struct profile { const u8 *memory; u32 base; u32 bytes; const struct debug_map *debug; FILE *trace; FILE *folded; FILE *pcs; FILE *calls; bool failed; bool track_calls; u32 function_pc; u64 invocations; struct symbol *symbols; size_t symbol_count; struct symbol_page *symbol_pages; /* Range updates give per-PC counts with two additions per recorded range. */ u64 *pc_delta; struct stack_node *nodes; size_t node_count; size_t node_capacity; u32 *node_hash; size_t hash_capacity; struct frame *frames; size_t depth; size_t frame_capacity; u64 total; u32 last_pc; }; static void *resize(void *data, size_t count, size_t size) { void *result = realloc(data, count * size); if (!result) bail("cannot allocate instruction profile"); return result; } static FILE *open_output(const char *prefix, const char *suffix) { size_t size = strlen(prefix) + strlen(suffix) + 1; char *path = resize(NULL, size, 1); snprintf(path, size, "%s%s", prefix, suffix); int fd = open(path, O_WRONLY | O_CREAT | O_EXCL | O_CLOEXEC, 0666); FILE *file = fd < 0 ? NULL : fdopen(fd, "wb"); if (!file) bail("cannot create profile output '%s'", path); free(path); return file; } static int compare_symbols(const void *a, const void *b) { const struct symbol *left = a, *right = b; if (left->offset != right->offset) return left->offset < right->offset ? -1 : 1; return strcmp(left->name, right->name); } static void load_symbols(struct profile *p, const char *program) { size_t size = 0; u8 *data = debug_read_sidecar(program, ".symbols", &size); if (!data) return; /* Magic and text digest, then (byte offset, name length) and name bytes. */ if (size < 40 || memcmp(data, "RADSYM01", 8)) bail("invalid symbol map for '%s'", program); blake3_hasher hasher; u8 digest[BLAKE3_OUT_LEN]; blake3_hasher_init(&hasher); blake3_hasher_update(&hasher, p->memory + p->base, p->bytes); blake3_hasher_finalize(&hasher, digest, sizeof(digest)); if (memcmp(digest, data + 8, sizeof(digest))) { fprintf(stderr, "symbol map does not match '%s'\n", program); free(data); return; } size_t capacity = 0; for (size_t pos = 40; pos < size;) { if (size - pos < 8) bail("truncated symbol map for '%s'", program); u32 offset = decode_u32_le(data + pos); u32 len = decode_u32_le(data + pos + 4); pos += 8; if (offset > p->bytes || offset % INSTR_SIZE || !len || len > size - pos || memchr(data + pos, 0, len)) bail("invalid symbol in map for '%s'", program); /* A label at the end of the text has no instructions. */ if (offset != p->bytes) { if (p->symbol_count == capacity) { capacity = capacity ? 2 * capacity : 64; p->symbols = resize(p->symbols, capacity, sizeof(*p->symbols)); } char *name = resize(NULL, (size_t)len + 1, 1); memcpy(name, data + pos, len); name[len] = 0; p->symbols[p->symbol_count++] = (struct symbol){ offset, name }; } pos += len; } free(data); if (!p->symbol_count) return; qsort(p->symbols, p->symbol_count, sizeof(*p->symbols), compare_symbols); u32 page_bytes = 64 * INSTR_SIZE; u32 pages = (p->bytes + page_bytes - 1) / page_bytes; p->symbol_pages = calloc(pages + 1, sizeof(*p->symbol_pages)); if (!p->symbol_pages) bail("cannot allocate profile symbol index"); u32 symbol = 0; for (u32 i = 0; i < pages; i++) { struct symbol_page *page = &p->symbol_pages[i]; page->first = symbol; u32 end = (i + 1) * page_bytes; while (symbol < p->symbol_count && p->symbols[symbol].offset < end) { u32 index = p->symbols[symbol++].offset / INSTR_SIZE; page->entries |= 1ull << (index % 64); } } p->symbol_pages[pages].first = symbol; } /* Return the index page if offset identifies a function entry. */ static const struct symbol_page *entry_page( const struct profile *p, u32 offset ) { if (!p->symbol_pages || offset >= p->bytes || offset % INSTR_SIZE) return NULL; u32 index = offset / INSTR_SIZE; const struct symbol_page *page = &p->symbol_pages[index / 64]; return (page->entries & (1ull << (index % 64))) ? page : NULL; } /* Render a field that is also safe as a folded-stack frame. */ static void field(FILE *file, const char *str) { size_t n = strcspn(str, ";\t\r\n"); if (!str[n]) { fputs(str, file); return; } for (; *str; str++) fputc(strchr(";\t\r\n", *str) ? '_' : (unsigned char)*str, file); } static void frame_name(FILE *file, const struct profile *p, u32 pc) { u32 offset = pc - p->base; const struct symbol_page *page = entry_page(p, offset); if (page) { /* Search backward so an exact match uses the last alias. */ u32 symbol = page[1].first - 1; while (p->symbols[symbol].offset != offset) symbol--; field(file, p->symbols[symbol].name); return; } fprintf(file, "0x%x", pc); if (offset < p->bytes) { const struct debug_entry *loc = debug_map_lookup(p->debug, offset); if (loc) { fputc('@', file); field(file, loc->file); fprintf(file, ":%u", loc->offset); } } } static size_t node_slot(const struct profile *p, u32 parent, u32 pc) { u64 key = ((u64)parent << 32) | pc; key ^= key >> 33; key *= 0xff51afd7ed558ccduLL; key ^= key >> 33; size_t slot = (size_t)key & (p->hash_capacity - 1); while (p->node_hash[slot]) { const struct stack_node *node = &p->nodes[p->node_hash[slot]]; if (node->parent == parent && node->pc == pc) break; slot = (slot + 1) & (p->hash_capacity - 1); } return slot; } static u32 stack_node(struct profile *p, u32 parent, u32 pc) { if (p->node_count * 2 >= p->hash_capacity) { free(p->node_hash); p->hash_capacity = p->hash_capacity ? p->hash_capacity * 2 : 128; p->node_hash = calloc(p->hash_capacity, sizeof(*p->node_hash)); if (!p->node_hash) bail("cannot allocate profile stack index"); for (u32 i = 1; i < p->node_count; i++) p->node_hash[node_slot(p, p->nodes[i].parent, p->nodes[i].pc)] = i; } size_t slot = node_slot(p, parent, pc); if (p->node_hash[slot]) return p->node_hash[slot]; if (p->node_count >= p->node_capacity) { p->node_capacity = p->node_capacity ? p->node_capacity * 2 : 64; p->nodes = resize(p->nodes, p->node_capacity, sizeof(*p->nodes)); } u32 index = (u32)p->node_count++; p->nodes[index] = (struct stack_node){ .parent = parent, .pc = pc }; p->node_hash[slot] = index; return index; } static void enter(struct profile *p, u32 pc, u32 link, bool tail) { if (p->depth == p->frame_capacity) { p->frame_capacity = p->frame_capacity ? p->frame_capacity * 2 : 32; p->frames = resize(p->frames, p->frame_capacity, sizeof(*p->frames)); } u32 parent = p->depth ? p->frames[p->depth - 1].node : 0; struct frame *frame = &p->frames[p->depth++]; *frame = (struct frame){ .node = p->folded ? stack_node(p, parent, pc) : 0, .pc = pc, .link = link, .start = p->total, .tail = tail, }; if (p->track_calls && pc == p->function_pc) frame->invocation = ++p->invocations; } static void leave(struct profile *p, bool returned) { const struct frame *f = &p->frames[--p->depth]; if (f->invocation) fprintf( p->calls, "%llu\t%llu\t%llu\t%s\n", (unsigned long long)f->invocation, (unsigned long long)f->self, (unsigned long long)(p->total - f->start), returned ? "returned" : "stopped" ); } static bool is_link(u32 reg) { return reg == RA || reg == T0; } /* Complete the invocation whose link is the actual return target. * A transfer to an outer frame stops any intervening active calls. */ static bool return_to(struct profile *p, u32 target) { for (size_t i = p->depth; i; i--) { if (p->frames[i - 1].link != target) continue; while (p->depth > i) leave(p, false); bool tail; do { tail = p->frames[p->depth - 1].tail; leave(p, true); } while (tail); return true; } return false; } static bool is_return(instr_t ins) { return ins.r.opcode == OP_JALR && is_link(ins.i.rs1) && (!is_link(ins.i.rd) || ins.i.rd != ins.i.rs1); } /* Apply the transfer at the end of the previous range with its actual target. */ static void transfer(struct profile *p, u32 target) { if (!p->depth) { enter(p, target, 0, false); return; } u32 prev = p->last_pc; if (prev - p->base >= p->bytes) return; instr_t ins = { .raw = decode_u32_le(p->memory + prev) }; if (ins.r.opcode != OP_JAL && ins.r.opcode != OP_JALR) return; u32 rd = ins.r.rd; if (is_return(ins) && return_to(p, target) && !is_link(rd)) { if (!p->depth) enter(p, target, 0, false); return; } if (is_link(rd)) { enter(p, target, prev + INSTR_SIZE, false); return; } const struct frame *frame = &p->frames[p->depth - 1]; if (rd == ZERO && frame->pc != target && entry_page(p, target - p->base)) enter(p, target, frame->link, true); } struct profile *profile_open( const char *program, const u8 *memory, u32 base, u32 bytes, const struct debug_map *debug, const char *prefix, const char *trace, const char *function ) { struct profile *p = calloc(1, sizeof(*p)); if (!p) bail("cannot allocate instruction profile"); p->memory = memory; p->base = base; p->bytes = bytes; p->debug = debug; p->node_count = 1; /* Reserve the empty stack. */ if (prefix || function) load_symbols(p, program); if (function) { for (size_t i = 0; i < p->symbol_count; i++) { if (!strcmp(function, p->symbols[i].name)) { p->track_calls = true; p->function_pc = base + p->symbols[i].offset; break; } } if (!p->track_calls) bail( "profile function '%s' is absent from '%s.symbols'", function, program ); if (prefix) { p->calls = open_output(prefix, ".calls.tsv"); } else { int fd = fcntl(STDERR_FILENO, F_DUPFD_CLOEXEC, 3); if (fd < 0 || !(p->calls = fdopen(fd, "w"))) bail("cannot open the call report stream"); } fputs("call\tself\tinclusive\tstatus\n", p->calls); } if (prefix) { p->folded = open_output(prefix, ".folded"); p->pcs = open_output(prefix, ".pcs.tsv"); p->pc_delta = calloc((size_t)bytes / INSTR_SIZE + 1, sizeof(*p->pc_delta)); if (!p->pc_delta) bail("cannot allocate profile PC counters"); } if (trace) { p->trace = open_output(trace, ""); /* RVTRACE1, code base and size, then packed range words. * All integer fields are little-endian. */ u8 header[16] = "RVTRACE1"; encode_le(header + 8, base, 4); encode_le(header + 12, bytes, 4); p->failed |= fwrite(header, 1, sizeof(header), p->trace) != sizeof(header); } return p; } void profile_record(struct profile *p, const u32 *ranges, const u32 *end) { if (p->trace && !p->failed) { const u16 little_endian = 1; if (*(const u8 *)&little_endian) { size_t n = (size_t)(end - ranges); p->failed |= fwrite(ranges, sizeof(*ranges), n, p->trace) != n; } else { for (const u32 *r = ranges; r < end; r++) { u8 bytes[4]; encode_le(bytes, *r, sizeof(bytes)); p->failed |= fwrite(bytes, 1, sizeof(bytes), p->trace) != sizeof(bytes); } } } if (!p->folded && !p->calls) return; for (const u32 *r = ranges; r < end;) { u32 word = *r++; u32 count = (word >> PROFILE_PC_BITS) + 1; u32 pc = word & PROFILE_PC_MASK; if (word == PROFILE_PC_ESCAPE) { pc = *r++; count = 1; } u32 offset = pc - p->base; if (p->pc_delta && offset < p->bytes) { u32 index = offset / INSTR_SIZE; u32 words = p->bytes / INSTR_SIZE - index; p->pc_delta[index]++; p->pc_delta[index + (count < words ? count : words)]--; } transfer(p, pc); struct frame *f = &p->frames[p->depth - 1]; if (p->folded) p->nodes[f->node].self += count; f->self += count; p->total += count; p->last_pc = pc + (count - 1) * INSTR_SIZE; } } bool profile_close(struct profile *p, u32 next_pc, bool continued) { if (!p) return true; if (continued && p->depth && p->last_pc - p->base < p->bytes) { instr_t ins = { .raw = decode_u32_le(p->memory + p->last_pc) }; if (is_return(ins)) return_to(p, next_pc); } while (p->depth) leave(p, false); if (p->folded) { u32 *path = resize(NULL, p->node_count, sizeof(*path)); for (u32 i = 1; i < p->node_count; i++) { if (!p->nodes[i].self) continue; size_t depth = 0; for (u32 node = i; node; node = p->nodes[node].parent) path[depth++] = p->nodes[node].pc; while (depth) { frame_name(p->folded, p, path[--depth]); if (depth) fputc(';', p->folded); } fprintf(p->folded, " %llu\n", (unsigned long long)p->nodes[i].self); } free(path); fputs("pc\tinstructions\tfunction\tsource\tbyte_offset\n", p->pcs); u64 count = 0; size_t next_symbol = 0; const struct symbol *sym = NULL; for (u32 i = 0; i < p->bytes / INSTR_SIZE; i++) { count += p->pc_delta[i]; if (!count) continue; u32 offset = i * INSTR_SIZE; while (next_symbol < p->symbol_count && p->symbols[next_symbol].offset <= offset) sym = &p->symbols[next_symbol++]; const struct debug_entry *loc = debug_map_lookup(p->debug, offset); if (sym && loc && loc->pc < sym->offset) loc = NULL; fprintf( p->pcs, "0x%x\t%llu\t", p->base + offset, (unsigned long long)count ); if (sym) field(p->pcs, sym->name); if (loc) { fputc('\t', p->pcs); field(p->pcs, loc->file); fprintf(p->pcs, "\t%u", loc->offset); } else { fputs("\t\t", p->pcs); } fputc('\n', p->pcs); } } FILE *outputs[] = { p->folded, p->pcs, p->trace, p->calls }; for (size_t i = 0; i < sizeof(outputs) / sizeof(*outputs); i++) { FILE *file = outputs[i]; if (file) { p->failed |= ferror(file) != 0; p->failed |= fclose(file) != 0; } } bool ok = !p->failed; for (size_t i = 0; i < p->symbol_count; i++) free(p->symbols[i].name); free(p->symbols); free(p->symbol_pages); free(p->pc_delta); free(p->nodes); free(p->node_hash); free(p->frames); free(p); return ok; }