commit de8c3b62f7bba21c192e5a973d5f73ae94c2a0f8
parent 175b6648929c92b677c5afed25e450da1a9cb2e0
Author: Ryan Sepassi <rsepassi@gmail.com>
Date: Sat, 13 Jun 2026 08:26:44 -0700
perf(obj): shared ObjStrtab — kill the O(n^2) strtab_add (ELF/COFF/Mach-O)
Each object writer's strtab_add re-flattened the whole growing string table and
linear-substring-scanned it on every symbol add — O(n^2) in the symbol count.
On Linux callgrind it was 31% of all instructions compiling sqlite to ELF (1.0B
of 3.3B Ir), invisible on the macOS Mach-O path (Mach-O didn't dedupe at all).
A string table is just bytes and dedup is a pure size optimization, so the
policy is identical across formats: factor one shared ObjStrtab (obj.h/obj.c) —
a contiguous buffer + an open-addressed {hash,off,len} index that verifies a
candidate by reading data+off (no retained pointers, no per-add flatten) — and
route ELF, COFF, and Mach-O through it. ELF/COFF keep their leading NUL / 4-byte
size-field prefix via obj_strtab_put_raw; Mach-O gains dedup it never had.
Dedup is exact-match, not the old suffix/tail-merge, so a strtab is marginally
larger where a name is another's suffix — a deliberate, valid output change
(gate: run-correctness + determinism, not byte-identity).
sqlite3.c -c to ELF (Linux callgrind): obj_strtab_add 31.05% -> 0.07% self;
total 3.30 B -> 2.04 B Ir (-38%, alongside the in-tree coalescing/lazy-home
work). ELF compile byte-deterministic. Mach-O object -6 KB (new dedup).
Green: test-elf 41/0, test-link 124/0, test-ar 20/20, test-macho 80/0, test-coff
(env-skip only); test-toy 1392/0, test-parse 3920+129/0, test-smoke-x64/rv64
3/0; sqlite e2e 84|2 (macOS Mach-O). Linux callgrind profiling path documented
in PERF.md.
Diffstat:
6 files changed, 242 insertions(+), 113 deletions(-)
diff --git a/doc/plan/PERF.md b/doc/plan/PERF.md
@@ -140,6 +140,70 @@ build/release/kit cc sqlite3.c shell.c -o /tmp/sq --sysroot "$SDK" -lc
select sum(a)+sum(b), count(*) from t;" # -> 84|2
```
+**6. Inclusive instruction profile — Linux + `callgrind` (the "where do the
+instructions *go*" tool).** macOS `sample` (step 4) gives only **wall-clock
+self-time leaves** — it shows the single fat leaf (`lex_next`) and hides
+everything inclusive, so a router like `parse_stmt` or a per-symbol object-write
+loop is invisible. For inclusive, **instruction-grounded** attribution use
+**`valgrind --tool=callgrind`** on Linux: it counts every instruction (`Ir`,
+the same metric we trust) exactly and deterministically, and attributes it up
+the call tree. (This is what surfaced the `strtab_add` O(n²) — 31% of `-c`
+instructions — that `sample` could not see, because it never appears on the
+macOS Mach-O path.) **Linux is the profiling/comparison platform** for this
+reason; backport fixes to the Mach-O path where they apply.
+
+That O(n²) is **fixed**: the per-add `buf_flatten` + linear substring scan in
+each writer's `strtab_add` is now a shared `ObjStrtab` (obj.h/obj.c) — one
+contiguous buffer + an open-addressed hash, used by ELF/COFF/Mach-O alike (the
+dedup policy is identical because a string table is just bytes; sharing is a
+size optimization, not a format requirement). `obj_strtab_add` dropped from
+31.05% to **0.07%** self; the full sqlite `-c` to ELF fell **3.30 B → 2.04 B
+`Ir` (−38%)**. (Mach-O previously didn't dedupe at all and so had no O(n²);
+adopting the shared deduping builder shrank its object too.)
+
+Run it in the same arm64 container family as the hosted suite (no valgrind on
+macOS). The recipe, with its non-obvious gotchas baked in:
+
+```sh
+podman run --rm --platform linux/arm64 -v "$PWD":/work:Z \
+ docker.io/arm64v8/debian:bookworm-slim sh -c '
+ set -eu; export DEBIAN_FRONTEND=noninteractive
+ apt-get update -qq && apt-get install -y -qq clang lld make libc6-dev binutils valgrind perl
+ cd /work
+ make bin RELEASE=1 PROFILE=1 CC=clang AR=ar BUILD_DIR=build/linux-prof
+ strip --strip-debug build/linux-prof/kit # see (b)
+ cd tmp/projects/sqlite-amalg
+ valgrind --tool=callgrind --cache-sim=no --branch-sim=no --dump-instr=no \
+ --collect-jumps=no --callgrind-out-file=/work/build/linux-prof/cg.out \
+ /work/build/linux-prof/kit cc -c sqlite3.c -lc -o /tmp/k.o # see (a)
+ callgrind_annotate --threshold=95 /work/build/linux-prof/cg.out # self Ir + callers
+'
+```
+
+Gotchas (each cost a round trip — do not relearn them):
+- **(a) Headers via `-lc`.** kit on Linux discovers the libc sysroot through its
+ hosted profile, which `-lc` triggers even for `-c`; without it, `time.h not
+ found`. **Use `bookworm` (glibc 2.36), not `ubuntu:24.04`** — glibc 2.39's
+ `bits/math-vector.h` uses a vector-typedef attribute the C frontend rejects
+ (`expected ';' after typedef`), aborting the compile mid-profile.
+- **(b) `strip --strip-debug` before profiling.** clang-14 emits DWARF5
+ (`DW_FORM_addrx`/`rnglistx`) that bookworm's valgrind 3.19 chokes on
+ ("unhandled dwarf2 abbrev form 0x25" -> fatal). callgrind builds its call graph
+ from executed `CALL`s, not DWARF, and needs only the ELF **`.symtab`** to name
+ functions — `--strip-debug` drops `.debug_*` but keeps `.symtab`. (A newer
+ valgrind, e.g. ubuntu's 3.22, reads the DWARF — but then hits (a). Stripping is
+ the portable fix.) **Strip in place**, do not copy the binary elsewhere: kit
+ resolves its `support/rt` dir relative to its own path, so a copied binary
+ fails `cc: support dir not found`.
+- **(c) Trust self/exclusive, not inclusive %.** `callgrind_annotate
+ --inclusive=yes` double-counts around recursion cycles (the recursive-descent
+ parser), printing absurd percentages (`lex_open_mem` at 14,000,000%). The
+ self/exclusive ranking sums cleanly to 100% — use it; read inclusive only as
+ "function X's subtree is hot," not a number.
+- callgrind is ~10x slower; the sqlite `-c` collects ~3.3 B `Ir` (more than the
+ 2.13 B hardware figure — it counts glibc + the loader + the `-lc` probe). The
+ *distribution* is the point, not the absolute total.
+
## Current state
**Real-world compilation is frontend-bound, not codegen-bound.** The phase split
diff --git a/src/obj/coff/emit.c b/src/obj/coff/emit.c
@@ -124,53 +124,22 @@ static u32 sec_characteristics(const Section* s, int in_group) {
return r;
}
-/* Append `len` bytes of `s` followed by a single NUL to `b`, returning
- * the offset at which `s` was placed. Dedupe linearly — strtabs are
- * small enough that this is fine without a hash table, and the
- * dedupe matches what binutils / llvm-objcopy emit. Mirror of the
- * helper in elf_emit. */
-static u32 strtab_add(Buf* b, const char* s, u32 len) {
- if (len == 0) return 0;
- u32 total = buf_pos(b);
- if (total > len) {
- u8 stack[256];
- u8* tmp =
- total <= sizeof stack ? stack : (u8*)b->heap->alloc(b->heap, total, 1);
- if (tmp) {
- buf_flatten(b, tmp);
- /* Skip the first 4 bytes (the size-prefix placeholder) when
- * searching for matches. */
- u32 start = COFF_STRTAB_SIZE_FIELD_BYTES;
- if (total > start + len) {
- for (u32 i = start; i + len < total; ++i) {
- if (tmp[i + len] == 0 && memcmp(tmp + i, s, len) == 0) {
- if (tmp != stack) b->heap->free(b->heap, tmp, total);
- return i;
- }
- }
- }
- if (tmp != stack) b->heap->free(b->heap, tmp, total);
- }
- }
- u32 off = total;
- buf_write(b, s, len);
- {
- u8 z = 0;
- buf_write(b, &z, 1);
- }
- return off;
-}
+/* The string-table dedup + build moved to the shared ObjStrtab (obj.h); the
+ * former per-add buf_flatten + linear substring scan here was the same O(n^2)
+ * the ELF writer had. The COFF strtab keeps its leading 4-byte size field (a
+ * raw prefix the dedup never targets, see obj_strtab_put_raw). */
/* Encode an 8-byte Name field. If the name fits in 8 bytes, copy
* verbatim and zero-pad. Otherwise allocate the name in `strtab` and
* write "/<decimal-offset>" (NUL-padded to 8 bytes). */
-static void encode_name8(char out[8], const char* name, u32 nlen, Buf* strtab) {
+static void encode_name8(char out[8], const char* name, u32 nlen,
+ ObjStrtab* strtab) {
memset(out, 0, 8);
if (nlen <= 8) {
if (nlen) memcpy(out, name, nlen);
return;
}
- u32 off = strtab_add(strtab, name, nlen);
+ u32 off = obj_strtab_add(strtab, name, nlen);
/* "/<decimal-offset>" — up to 7 decimal digits leaves room for the
* leading slash within 8 bytes. COFF .obj strtabs are < 1 MiB in
* practice, so 7 digits is plenty. */
@@ -278,11 +247,11 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
/* String table — leading 4-byte size placeholder. Real strings start
* at offset 4. */
- Buf strtab;
- buf_init(&strtab, h);
+ ObjStrtab strtab;
+ obj_strtab_init(&strtab, h, /*dedup=*/1);
{
u8 zero4[COFF_STRTAB_SIZE_FIELD_BYTES] = {0, 0, 0, 0};
- buf_write(&strtab, zero4, COFF_STRTAB_SIZE_FIELD_BYTES);
+ obj_strtab_put_raw(&strtab, zero4, COFF_STRTAB_SIZE_FIELD_BYTES);
}
for (u32 i = 1; i < nobjsec; ++i) {
@@ -488,7 +457,7 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
if (nlen) memcpy(short_name, nm, nlen);
} else {
zeroes = 0;
- offset = strtab_add(&strtab, nm, nlen);
+ offset = obj_strtab_add(&strtab, nm, nlen);
}
i16 section_number = 0;
@@ -654,7 +623,7 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
/* String table starts immediately after the symtab. Patch the 4-byte
* size prefix (inclusive). */
- u32 strtab_size = buf_pos(&strtab);
+ u32 strtab_size = obj_strtab_size(&strtab);
/* The size field is part of the on-disk strtab and is the total
* inclusive byte count. Patch it now. */
{
@@ -722,7 +691,7 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
* them with the real size before flushing. */
{
u8* flat = (u8*)arena_alloc(c->scratch, strtab_size ? strtab_size : 1, 1);
- if (strtab_size) buf_flatten(&strtab, flat);
+ if (strtab_size) memcpy(flat, obj_strtab_data(&strtab), strtab_size);
/* Patch the 4-byte size prefix in place. */
if (strtab_size >= COFF_STRTAB_SIZE_FIELD_BYTES) {
wr_u32_le(flat, strtab_size);
@@ -730,5 +699,5 @@ void emit_coff(Compiler* c, ObjBuilder* ob, Writer* w) {
kit_writer_seek(w, strtab_off);
kit_writer_write(w, flat, strtab_size);
}
- buf_fini(&strtab);
+ obj_strtab_fini(&strtab);
}
diff --git a/src/obj/elf/emit.c b/src/obj/elf/emit.c
@@ -144,50 +144,9 @@ static const char* sym_to_str(Compiler* c, Sym n, u32* len_out) {
return s;
}
-/* Append `len` bytes of `s` followed by a single NUL to `b`, return
- * the offset at which `s` was placed.
- *
- * If `s` already exists at some offset (as a NUL-terminated substring
- * starting at any offset), reuse that offset — clang/binutils both
- * dedupe trivially identical strings, and matching the convention
- * keeps our strtab the same size as theirs. The dedupe is linear in
- * the strtab; section + symbol counts are small enough that this is
- * fine without a hash. */
-static u32 strtab_add(Buf* b, const char* s, u32 len) {
- /* Empty string: always at offset 0 (the leading NUL). */
- if (len == 0) return 0;
-
- /* Linear search for an existing copy. We must scan chunk-by-chunk
- * because Buf is segmented; flatten to a temp scratch buffer first
- * if non-empty and search there. For our tiny strtabs, the cost is
- * dominated by the writes anyway. */
- u32 total = buf_pos(b);
- if (total > len) {
- /* Flatten just to search — not optimal but the strtab here is
- * always small (low kilobytes at most). */
- u8 stack[256];
- u8* tmp =
- total <= sizeof stack ? stack : (u8*)b->heap->alloc(b->heap, total, 1);
- if (tmp) {
- buf_flatten(b, tmp);
- for (u32 i = 0; i + len < total; ++i) {
- if (tmp[i + len] == 0 && memcmp(tmp + i, s, len) == 0) {
- if (tmp != stack) b->heap->free(b->heap, tmp, total);
- return i;
- }
- }
- if (tmp != stack) b->heap->free(b->heap, tmp, total);
- }
- }
-
- u32 off = total;
- buf_write(b, s, len);
- {
- u8 z = 0;
- buf_write(b, &z, 1);
- }
- return off;
-}
+/* The string table dedup + build moved to the shared ObjStrtab (obj.h): the
+ * former per-add buf_flatten + linear substring scan here was O(n^2) in the
+ * symbol count (31% of instructions compiling sqlite to ELF). */
void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
Heap* h = (Heap*)c->ctx->heap;
@@ -282,11 +241,11 @@ void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
/* ---- pass 2: build .symtab + .strtab content -------------------- */
/* .strtab: leading NUL byte. Then a name per emitted symbol. */
- Buf strtab;
- buf_init(&strtab, h);
+ ObjStrtab strtab;
+ obj_strtab_init(&strtab, h, /*dedup=*/1);
{
u8 z = 0;
- buf_write(&strtab, &z, 1);
+ obj_strtab_put_raw(&strtab, &z, 1);
}
/* The .symtab is built into a contiguous arena buffer of fixed-size
@@ -364,7 +323,7 @@ void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
if ((pass == 0) != is_local) continue;
u32 nlen;
const char* nm = sym_to_str(c, s->name, &nlen);
- u32 nameoff = nlen ? strtab_add(&strtab, nm, nlen) : 0;
+ u32 nameoff = nlen ? obj_strtab_add(&strtab, nm, nlen) : 0;
u8 info =
ELF64_ST_INFO(sym_bind_to_elf(s->bind), sym_kind_to_elf(s->kind));
u8 other = sym_vis_to_elf(s->vis);
@@ -584,7 +543,7 @@ void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
/* secs[0] (SHN_UNDEF) carries name "" → offset 0. */
secs[0].sh_name = 0;
for (u32 i = 1; i < nsecs; ++i) {
- secs[i].sh_name = strtab_add(&strtab, secs[i].name, secs[i].name_len);
+ secs[i].sh_name = obj_strtab_add(&strtab, secs[i].name, secs[i].name_len);
}
/* Append the .strtab section record itself; its own name lands in
@@ -592,11 +551,11 @@ void emit_elf(Compiler* c, ObjBuilder* ob, Writer* w) {
{
const char* nm = ".strtab";
u32 nlen = 7;
- u32 nameoff = strtab_add(&strtab, nm, nlen);
- u32 sz = buf_pos(&strtab);
+ u32 nameoff = obj_strtab_add(&strtab, nm, nlen);
+ u32 sz = obj_strtab_size(&strtab);
u8* flat = (u8*)arena_alloc(c->scratch, sz, 1);
- buf_flatten(&strtab, flat);
- buf_fini(&strtab);
+ memcpy(flat, obj_strtab_data(&strtab), sz);
+ obj_strtab_fini(&strtab);
ElfSec* es = &secs[nsecs];
memset(es, 0, sizeof *es);
diff --git a/src/obj/macho/emit.c b/src/obj/macho/emit.c
@@ -378,13 +378,16 @@ void emit_macho(Compiler* c, ObjBuilder* ob, Writer* w) {
u32* sym_obj_to_macho =
arena_zarray(c->scratch, u32, nobjsym + 2); /* obj_id -> mach idx */
- Buf strtab;
- buf_init(&strtab, h);
+ /* Shared deduping string-table builder (obj.h). Mach-O previously appended
+ * names without dedup; one shared policy across formats both unifies the code
+ * and shrinks the table (repeated names share one copy) at O(n) cost. */
+ ObjStrtab strtab;
+ obj_strtab_init(&strtab, h, /*dedup=*/1);
/* Mach-O strtab convention: the first byte is " " (space) or NUL —
* llvm/Apple emit a single NUL. We start with NUL for offset 0. */
{
u8 z = 0;
- buf_write(&strtab, &z, 1);
+ obj_strtab_put_raw(&strtab, &z, 1);
}
/* Emit in three passes so n_type/sect ordering matches LC_DYSYMTAB
@@ -414,15 +417,7 @@ void emit_macho(Compiler* c, ObjBuilder* ob, Writer* w) {
* Name-canonicalization for API callers (kit_jit_lookup,
* link_set_entry) lives one layer up at the linker boundary
* (link.c), so emit/read stay byte-for-byte stable. */
- if (nlen && nm) {
- u32 off = buf_pos(&strtab);
- buf_write(&strtab, nm, nlen);
- u8 z = 0;
- buf_write(&strtab, &z, 1);
- ms->strx = off;
- } else {
- ms->strx = 0;
- }
+ ms->strx = (nlen && nm) ? obj_strtab_add(&strtab, nm, (u32)nlen) : 0;
u8 type = 0;
if (extdef) type |= N_EXT;
@@ -717,7 +712,7 @@ void emit_macho(Compiler* c, ObjBuilder* ob, Writer* w) {
u64 symoff = cur;
cur += (u64)nmsyms * MACHO_NLIST64_SIZE;
u64 stroff = cur;
- u32 strtab_size = buf_pos(&strtab);
+ u32 strtab_size = obj_strtab_size(&strtab);
cur += strtab_size;
/* ---- pass 6: write the file ------------------------------------ */
@@ -857,9 +852,9 @@ void emit_macho(Compiler* c, ObjBuilder* ob, Writer* w) {
/* strtab */
{
u8* flat = (u8*)arena_alloc(c->scratch, strtab_size ? strtab_size : 1, 1);
- if (strtab_size) buf_flatten(&strtab, flat);
+ if (strtab_size) memcpy(flat, obj_strtab_data(&strtab), strtab_size);
kit_writer_seek(w, stroff);
kit_writer_write(w, flat, strtab_size);
}
- buf_fini(&strtab);
+ obj_strtab_fini(&strtab);
}
diff --git a/src/obj/obj.c b/src/obj/obj.c
@@ -1472,3 +1472,100 @@ const char* reloc_kind_name(RelocKind k) {
}
return "UNKNOWN";
}
+
+/* ---- shared string-table builder (see obj.h ObjStrtab) ------------------ */
+
+static u32 obj_strtab_hash(const char* s, u32 len) {
+ u32 h = 2166136261u; /* FNV-1a */
+ for (u32 i = 0; i < len; ++i) {
+ h ^= (u8)s[i];
+ h *= 16777619u;
+ }
+ return h;
+}
+
+void obj_strtab_init(ObjStrtab* t, Heap* h, int dedup) {
+ memset(t, 0, sizeof *t);
+ t->heap = h;
+ t->dedup = dedup ? 1u : 0u;
+}
+
+static void obj_strtab_reserve(ObjStrtab* t, u32 extra) {
+ u32 ncap;
+ u8* nd;
+ if (t->len + extra <= t->cap) return;
+ ncap = t->cap ? t->cap : 256u;
+ while (t->len + extra > ncap) ncap *= 2u;
+ nd = (u8*)t->heap->alloc(t->heap, ncap, 1);
+ if (t->data) {
+ memcpy(nd, t->data, t->len);
+ t->heap->free(t->heap, t->data, t->cap);
+ }
+ t->data = nd;
+ t->cap = ncap;
+}
+
+void obj_strtab_put_raw(ObjStrtab* t, const void* bytes, u32 n) {
+ if (!n) return;
+ obj_strtab_reserve(t, n);
+ memcpy(t->data + t->len, bytes, n);
+ t->len += n;
+}
+
+static void obj_strtab_index_grow(ObjStrtab* t) {
+ u32 ncap = t->scap ? t->scap * 2u : 256u;
+ u32 mask = ncap - 1u;
+ ObjStrtabEnt* ns =
+ (ObjStrtabEnt*)t->heap->alloc(t->heap, sizeof(*ns) * ncap, _Alignof(ObjStrtabEnt));
+ memset(ns, 0, sizeof(*ns) * ncap);
+ for (u32 i = 0; i < t->scap; ++i) {
+ u32 j;
+ if (!t->slots[i].len) continue;
+ j = t->slots[i].hash & mask;
+ while (ns[j].len) j = (j + 1u) & mask;
+ ns[j] = t->slots[i];
+ }
+ if (t->slots) t->heap->free(t->heap, t->slots, sizeof(*t->slots) * t->scap);
+ t->slots = ns;
+ t->scap = ncap;
+}
+
+static u32 obj_strtab_append(ObjStrtab* t, const char* s, u32 len) {
+ u32 off = t->len;
+ obj_strtab_reserve(t, len + 1u);
+ memcpy(t->data + off, s, len);
+ t->data[off + len] = 0;
+ t->len += len + 1u;
+ return off;
+}
+
+u32 obj_strtab_add(ObjStrtab* t, const char* s, u32 len) {
+ u32 h, mask, j, off;
+ if (len == 0) return 0;
+ if (!t->dedup) return obj_strtab_append(t, s, len);
+ if ((t->sused + 1u) * 4u >= t->scap * 3u) obj_strtab_index_grow(t);
+ h = obj_strtab_hash(s, len);
+ mask = t->scap - 1u;
+ j = h & mask;
+ while (t->slots[j].len) {
+ ObjStrtabEnt* e = &t->slots[j];
+ if (e->hash == h && e->len == len && memcmp(t->data + e->off, s, len) == 0)
+ return e->off;
+ j = (j + 1u) & mask;
+ }
+ off = obj_strtab_append(t, s, len);
+ t->slots[j].hash = h;
+ t->slots[j].off = off;
+ t->slots[j].len = len;
+ t->sused++;
+ return off;
+}
+
+u32 obj_strtab_size(const ObjStrtab* t) { return t->len; }
+u8* obj_strtab_data(ObjStrtab* t) { return t->data; }
+
+void obj_strtab_fini(ObjStrtab* t) {
+ if (t->data) t->heap->free(t->heap, t->data, t->cap);
+ if (t->slots) t->heap->free(t->heap, t->slots, sizeof(*t->slots) * t->scap);
+ memset(t, 0, sizeof *t);
+}
diff --git a/src/obj/obj.h b/src/obj/obj.h
@@ -1121,4 +1121,49 @@ ObjBuilder* read_macho_dso(Compiler*, const char* name, const u8* data,
ObjBuilder* read_tbd(Compiler*, const char* name, const u8* data, size_t len,
Sym* install_name_out);
+/* ---- shared string-table builder (ELF / COFF / Mach-O symtab strtabs) ----
+ *
+ * Each object writer builds a string table: a leading prefix byte(s) followed
+ * by NUL-terminated names, with each name's byte offset recorded in its symbol
+ * record. Names repeat (a symbol defined and referenced; many `.rela.<sec>`
+ * section names), so the table dedupes identical strings — purely a size
+ * optimization (any valid offset to the right bytes is conformant), which is
+ * why the policy can be identical across all three formats.
+ *
+ * The bytes live in one contiguous, growable buffer; dedup is an open-addressed
+ * hash of {hash,off,len} that verifies a candidate by reading `data+off` (so it
+ * retains no external pointers and needs no per-add flatten). This replaced a
+ * per-add buf_flatten + linear substring scan that was O(n^2) in the symbol
+ * count -- 31% of all instructions when compiling sqlite to ELF. The dedup is
+ * exact-match (not the old suffix/tail-merge), so the table is marginally larger
+ * than binutils' where a name is a suffix of another, but still minimal and
+ * valid. */
+typedef struct ObjStrtabEnt {
+ u32 hash;
+ u32 off;
+ u32 len; /* 0 marks an empty slot (len-0 strings are never stored) */
+} ObjStrtabEnt;
+
+typedef struct ObjStrtab {
+ u8* data; /* contiguous table bytes (mutable: a caller may patch a prefix) */
+ u32 len;
+ u32 cap;
+ ObjStrtabEnt* slots; /* dedup index; NULL/empty when !dedup */
+ u32 scap; /* power-of-two slot capacity */
+ u32 sused;
+ Heap* heap;
+ u8 dedup;
+} ObjStrtab;
+
+void obj_strtab_init(ObjStrtab*, Heap*, int dedup);
+/* Append prefix bytes that belong to the table but are never a dedup target
+ * (a leading NUL, a COFF 4-byte size-field placeholder). */
+void obj_strtab_put_raw(ObjStrtab*, const void* bytes, u32 n);
+/* Add a name; return its byte offset. With dedup an exact duplicate returns the
+ * prior offset (O(1) amortized). len 0 -> offset 0 (the empty string). */
+u32 obj_strtab_add(ObjStrtab*, const char* s, u32 len);
+u32 obj_strtab_size(const ObjStrtab*);
+u8* obj_strtab_data(ObjStrtab*);
+void obj_strtab_fini(ObjStrtab*);
+
#endif
