| 1 |
|
| /* po_intern.h - the per-segment symbol table. |
| 2 |
|
| * |
| 3 |
|
| * Where the compression actually comes from. Not the codecs: this. |
| 4 |
|
| * |
| 5 |
|
| * Every attribute key, string value, service name, span name and metric name |
| 6 |
|
| * in a segment becomes a uint32_t, stored once. A million spans from one |
| 7 |
|
| * service store the string "checkout" once and a four-byte reference a |
| 8 |
|
| * million times. It also means predicate evaluation in phase 9 compares |
| 9 |
|
| * integers rather than strings, which is the difference between a scan that |
| 10 |
|
| * is memory-bound and one that is not. |
| 11 |
|
| * |
| 12 |
|
| * Interning is PER SEGMENT, not global. Phase 4 has no global authority by |
| 13 |
|
| * design - every worker seals its own segments - so each segment carries its |
| 14 |
|
| * own table and compaction re-interns globally for the block. The duplication |
| 15 |
|
| * across N workers is bounded by distinct-strings times workers within one |
| 16 |
|
| * two-hour block, and it is paid off exactly once, later, off the hot path. |
| 17 |
|
| */ |
| 18 |
|
| #ifndef PO_INTERN_H |
| 19 |
|
| #define PO_INTERN_H |
| 20 |
|
| |
| 21 |
|
| #include "punk_observe/po_compat.h" |
| 22 |
|
| #include "punk_observe/po_hash.h" |
| 23 |
|
| #include "punk_observe/po_rec.h" |
| 24 |
|
| |
| 25 |
|
| #define PO_SYM_NONE 0xFFFFFFFFu |
| 26 |
|
| |
| 27 |
|
| typedef struct { |
| 28 |
|
| uint32_t off; /* into the blob */ |
| 29 |
|
| uint32_t len; |
| 30 |
|
| } po_sym; |
| 31 |
|
| |
| 32 |
|
| typedef struct { |
| 33 |
|
| po_sym *sym; |
| 34 |
|
| uint32_t *idx; /* open-addressed: hash -> sym index + 1 */ |
| 35 |
|
| uint32_t n, cap, mask; |
| 36 |
|
| po_arena blob; /* the bytes, owned */ |
| 37 |
|
| } po_intern; |
| 38 |
|
| |
| 39 |
269 |
| static int po_intern_init(po_intern *t, uint32_t hint) { |
| 40 |
269 |
| uint32_t slots = 64; |
| 41 |
888 |
▶ | while (slots < hint * 2) slots <<= 1; |
Branch: 1 branch
| Branch | True | False | Total |
| while (slots < hint * 2) slots <<= 1; |
619 |
269 |
888 |
|
| 42 |
269 |
| memset(t, 0, sizeof(*t)); |
| 43 |
269 |
| t->cap = hint < 32 ? 32 : hint; |
| 44 |
269 |
| t->sym = (po_sym *)calloc(t->cap, sizeof(po_sym)); |
| 45 |
269 |
▶ | if (!t->sym) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!t->sym) return 0; |
0 |
269 |
269 |
|
| 46 |
269 |
| t->idx = (uint32_t *)calloc(slots, sizeof(uint32_t)); |
| 47 |
269 |
▶ | if (!t->idx) { free(t->sym); t->sym = NULL; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!t->idx) { free(t->sym); t->sym = NULL; return 0; } |
0 |
269 |
269 |
|
| 48 |
269 |
▶ | if (!po_arena_init(&t->blob, 4096)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_arena_init(&t->blob, 4096)) { |
0 |
269 |
269 |
|
| 49 |
0 |
| free(t->sym); free(t->idx); t->sym = NULL; t->idx = NULL; return 0; |
| 50 |
|
| } |
| 51 |
269 |
| t->mask = slots - 1; |
| 52 |
269 |
| return 1; |
| 53 |
|
| } |
| 54 |
|
| |
| 55 |
269 |
| static void po_intern_free(po_intern *t) { |
| 56 |
269 |
| free(t->sym); free(t->idx); |
| 57 |
269 |
| po_arena_free(&t->blob); |
| 58 |
269 |
| t->sym = NULL; t->idx = NULL; t->n = t->cap = 0; |
| 59 |
269 |
| } |
| 60 |
|
| |
| 61 |
12 |
| static int po_intern_grow(po_intern *t) { |
| 62 |
12 |
| uint32_t slots = (t->mask + 1) * 2; |
| 63 |
12 |
| uint32_t *ni = (uint32_t *)calloc(slots, sizeof(uint32_t)); |
| 64 |
|
| uint32_t i; |
| 65 |
12 |
▶ | if (!ni) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ni) return 0; |
0 |
12 |
12 |
|
| 66 |
7180 |
▶ | for (i = 0; i < t->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < t->n; i++) { |
7168 |
12 |
7180 |
|
| 67 |
7168 |
| uint32_t h = po_hash32(t->blob.base + t->sym[i].off, t->sym[i].len) |
| 68 |
7168 |
| & (slots - 1); |
| 69 |
8300 |
▶ | while (ni[h]) h = (h + 1) & (slots - 1); |
Branch: 1 branch
| Branch | True | False | Total |
| while (ni[h]) h = (h + 1) & (slots - 1); |
1132 |
7168 |
8300 |
|
| 70 |
7168 |
| ni[h] = i + 1; |
| 71 |
|
| } |
| 72 |
12 |
| free(t->idx); |
| 73 |
12 |
| t->idx = ni; |
| 74 |
12 |
| t->mask = slots - 1; |
| 75 |
12 |
| return 1; |
| 76 |
|
| } |
| 77 |
|
| |
| 78 |
|
| /* Intern a string, returning its id. Same bytes always give the same id |
| 79 |
|
| * WITHIN a segment; ids mean nothing across segments, which is why a reader |
| 80 |
|
| * always resolves through the segment's own table. */ |
| 81 |
32802 |
| static uint32_t po_intern_put(po_intern *t, const char *p, size_t len) { |
| 82 |
32802 |
| uint32_t h = po_hash32(p, len) & t->mask; |
| 83 |
|
| |
| 84 |
6097 |
| for (;;) { |
| 85 |
38899 |
| uint32_t e = t->idx[h]; |
| 86 |
38899 |
▶ | if (!e) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) break; |
8988 |
29911 |
38899 |
|
| 87 |
|
| { |
| 88 |
29911 |
| po_sym *s = &t->sym[e - 1]; |
| 89 |
|
| /* memcmp, always: a 32-bit hash match here is a probe hint and |
| 90 |
|
| * nothing more. */ |
| 91 |
29911 |
▶ | if (s->len == len && |
Branch: 2 branches
| Branch | True | False | Total |
| if (s->len == len && |
27272 |
2639 |
29911 |
| if (s->len == len && |
27272 |
0 |
27272 |
|
| 92 |
27272 |
▶ | (len == 0 || memcmp(t->blob.base + s->off, p, len) == 0)) |
Branch: 1 branch
| Branch | True | False | Total |
| (len == 0 || memcmp(t->blob.base + s->off, p, len) == 0)) |
23814 |
3458 |
27272 |
|
| 93 |
23814 |
| return e - 1; |
| 94 |
|
| } |
| 95 |
6097 |
| h = (h + 1) & t->mask; |
| 96 |
|
| } |
| 97 |
|
| |
| 98 |
8988 |
▶ | if (t->n == t->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (t->n == t->cap) { |
12 |
8976 |
8988 |
|
| 99 |
12 |
| uint32_t want = t->cap * 2; |
| 100 |
12 |
| po_sym *ns = (po_sym *)realloc(t->sym, want * sizeof(po_sym)); |
| 101 |
12 |
▶ | if (!ns) return PO_SYM_NONE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ns) return PO_SYM_NONE; |
0 |
12 |
12 |
|
| 102 |
12 |
| t->sym = ns; t->cap = want; |
| 103 |
|
| } |
| 104 |
8988 |
▶ | if ((t->n + 1) * 2 > t->mask + 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((t->n + 1) * 2 > t->mask + 1) { |
12 |
8976 |
8988 |
|
| 105 |
12 |
▶ | if (!po_intern_grow(t)) return PO_SYM_NONE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_intern_grow(t)) return PO_SYM_NONE; |
0 |
12 |
12 |
|
| 106 |
12 |
| h = po_hash32(p, len) & t->mask; |
| 107 |
20 |
▶ | while (t->idx[h]) h = (h + 1) & t->mask; |
Branch: 1 branch
| Branch | True | False | Total |
| while (t->idx[h]) h = (h + 1) & t->mask; |
8 |
12 |
20 |
|
| 108 |
|
| } |
| 109 |
|
| |
| 110 |
|
| { |
| 111 |
8988 |
| uint32_t off = po_arena_put(&t->blob, p, len); |
| 112 |
8988 |
▶ | if (off == PO_ARENA_ERR) return PO_SYM_NONE; |
Branch: 1 branch
| Branch | True | False | Total |
| if (off == PO_ARENA_ERR) return PO_SYM_NONE; |
0 |
8988 |
8988 |
|
| 113 |
8988 |
| t->sym[t->n].off = off; |
| 114 |
8988 |
| t->sym[t->n].len = (uint32_t)len; |
| 115 |
8988 |
| t->idx[h] = t->n + 1; |
| 116 |
8988 |
| return t->n++; |
| 117 |
|
| } |
| 118 |
|
| } |
| 119 |
|
| |
| 120 |
1104 |
| static const char *po_intern_get(const po_intern *t, uint32_t id, uint32_t *len) { |
| 121 |
1104 |
▶ | if (id >= t->n) { if (len) *len = 0; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (id >= t->n) { if (len) *len = 0; return NULL; } |
0 |
1104 |
1104 |
| if (id >= t->n) { if (len) *len = 0; return NULL; } |
0 |
0 |
0 |
|
| 122 |
1104 |
▶ | if (len) *len = t->sym[id].len; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len) *len = t->sym[id].len; |
1104 |
0 |
1104 |
|
| 123 |
1104 |
| return t->blob.base + t->sym[id].off; |
| 124 |
|
| } |
| 125 |
|
| |
| 126 |
|
| /* Serialise: [count][offsets][blob]. The offsets are relative to the blob, so |
| 127 |
|
| * the whole region is position-independent once mmap'd. */ |
| 128 |
29 |
| static size_t po_intern_size(const po_intern *t) { |
| 129 |
29 |
| return 8 + (size_t)t->n * 8 + t->blob.len; |
| 130 |
|
| } |
| 131 |
|
| |
| 132 |
29 |
| static void po_intern_write(const po_intern *t, char *out) { |
| 133 |
|
| uint32_t i; |
| 134 |
|
| uint32_t v; |
| 135 |
29 |
| char *q = out; |
| 136 |
29 |
| v = po_le32(t->n); memcpy(q, &v, 4); q += 4; |
| 137 |
29 |
| v = po_le32((uint32_t)t->blob.len); memcpy(q, &v, 4); q += 4; |
| 138 |
749 |
▶ | for (i = 0; i < t->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < t->n; i++) { |
720 |
29 |
749 |
|
| 139 |
720 |
| v = po_le32(t->sym[i].off); memcpy(q, &v, 4); q += 4; |
| 140 |
720 |
| v = po_le32(t->sym[i].len); memcpy(q, &v, 4); q += 4; |
| 141 |
|
| } |
| 142 |
29 |
▶ | if (t->blob.len) memcpy(q, t->blob.base, t->blob.len); |
Branch: 1 branch
| Branch | True | False | Total |
| if (t->blob.len) memcpy(q, t->blob.base, t->blob.len); |
29 |
0 |
29 |
|
| 143 |
29 |
| } |
| 144 |
|
| |
| 145 |
|
| /* A read-only view over a serialised table, straight out of an mmap. Nothing |
| 146 |
|
| * is copied and nothing is allocated. */ |
| 147 |
|
| typedef struct { |
| 148 |
|
| const char *base; |
| 149 |
|
| uint32_t n; |
| 150 |
|
| const char *offs; /* n pairs of (off, len) */ |
| 151 |
|
| const char *blob; |
| 152 |
|
| uint32_t bloblen; |
| 153 |
|
| } po_intern_view; |
| 154 |
|
| |
| 155 |
656 |
| static int po_intern_open(po_intern_view *v, const char *p, size_t len) { |
| 156 |
|
| uint32_t n, bl; |
| 157 |
656 |
▶ | if (len < 8) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len < 8) return 0; |
0 |
656 |
656 |
|
| 158 |
656 |
| memcpy(&n, p, 4); n = po_le32(n); |
| 159 |
656 |
| memcpy(&bl, p + 4, 4); bl = po_le32(bl); |
| 160 |
656 |
▶ | if ((size_t)8 + (size_t)n * 8 + bl > len) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if ((size_t)8 + (size_t)n * 8 + bl > len) return 0; |
0 |
656 |
656 |
|
| 161 |
656 |
| v->base = p; v->n = n; |
| 162 |
656 |
| v->offs = p + 8; |
| 163 |
656 |
| v->blob = p + 8 + (size_t)n * 8; |
| 164 |
656 |
| v->bloblen = bl; |
| 165 |
656 |
| return 1; |
| 166 |
|
| } |
| 167 |
|
| |
| 168 |
83 |
| static const char *po_intern_view_get(const po_intern_view *v, uint32_t id, |
| 169 |
|
| uint32_t *len) { |
| 170 |
|
| uint32_t off, l; |
| 171 |
83 |
▶ | if (id >= v->n) { if (len) *len = 0; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (id >= v->n) { if (len) *len = 0; return NULL; } |
0 |
83 |
83 |
| if (id >= v->n) { if (len) *len = 0; return NULL; } |
0 |
0 |
0 |
|
| 172 |
83 |
| memcpy(&off, v->offs + (size_t)id * 8, 4); off = po_le32(off); |
| 173 |
83 |
| memcpy(&l, v->offs + (size_t)id * 8 + 4, 4); l = po_le32(l); |
| 174 |
83 |
▶ | if ((size_t)off + l > v->bloblen) { if (len) *len = 0; return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if ((size_t)off + l > v->bloblen) { if (len) *len = 0; return NULL; } |
0 |
83 |
83 |
| if ((size_t)off + l > v->bloblen) { if (len) *len = 0; return NULL; } |
0 |
0 |
0 |
|
| 175 |
83 |
▶ | if (len) *len = l; |
Branch: 1 branch
| Branch | True | False | Total |
| if (len) *len = l; |
83 |
0 |
83 |
|
| 176 |
83 |
| return v->blob + off; |
| 177 |
|
| } |
| 178 |
|
| |
| 179 |
|
| #endif /* PO_INTERN_H */ |