| 1 |
|
| /* po_labels.h - the series id, derived rather than assigned. |
| 2 |
|
| * |
| 3 |
|
| * The obvious design hands the compactor a dictionary and has it allocate |
| 4 |
|
| * dense monotonic ids. That needs a single authority, and phase 4 has just |
| 5 |
|
| * removed the one place an authority could live: every worker seals its own |
| 6 |
|
| * segments, so an assigner would be a lock on the hottest path in the system. |
| 7 |
|
| * |
| 8 |
|
| * It is also unnecessary. A series IS its label set, so: |
| 9 |
|
| * |
| 10 |
|
| * series_id = H128(canonical sorted label block) |
| 11 |
|
| * |
| 12 |
|
| * Two workers computing that independently get the same answer with no |
| 13 |
|
| * coordination, no lock and no shared file. That single property is what |
| 14 |
|
| * makes per-worker writing affordable. |
| 15 |
|
| * |
| 16 |
|
| * The canonical block is what po_attrs_encode already produces in phase 1 - |
| 17 |
|
| * sorted by key, then tag, then value bytes - and the sort is load-bearing |
| 18 |
|
| * here rather than tidiness: if the input order leaked into the bytes, the |
| 19 |
|
| * same series would get two ids, storage would double, and the cardinality |
| 20 |
|
| * cap would count everything twice. |
| 21 |
|
| * |
| 22 |
|
| * AND THE HASH IS STILL VERIFIED. Every lookup compares the full block with |
| 23 |
|
| * memcmp before returning an existing id. 128 bits makes a collision |
| 24 |
|
| * vanishingly unlikely; the memcmp makes it impossible. A hash that is only |
| 25 |
|
| * probably unique is not an identity, and the failure it would cause - two |
| 26 |
|
| * unrelated services silently merged into one chart - is one nobody would |
| 27 |
|
| * ever find. |
| 28 |
|
| */ |
| 29 |
|
| #ifndef PO_LABELS_H |
| 30 |
|
| #define PO_LABELS_H |
| 31 |
|
| |
| 32 |
|
| #include "punk_observe/po_compat.h" |
| 33 |
|
| #include "punk_observe/po_hash.h" |
| 34 |
|
| #include "punk_observe/po_rec.h" |
| 35 |
|
| |
| 36 |
|
| /* One interned series: its id, and where its label block lives. */ |
| 37 |
|
| typedef struct { |
| 38 |
|
| po_h128 id; |
| 39 |
|
| uint32_t off; /* into the owning arena */ |
| 40 |
|
| uint32_t len; |
| 41 |
|
| uint32_t slot; /* dense ordinal within this segment */ |
| 42 |
|
| } po_series; |
| 43 |
|
| |
| 44 |
|
| typedef struct { |
| 45 |
|
| po_series *ent; |
| 46 |
|
| uint32_t *idx; /* open-addressed: hash -> ent index + 1, 0 = empty */ |
| 47 |
|
| uint32_t n; |
| 48 |
|
| uint32_t cap; /* entries */ |
| 49 |
|
| uint32_t mask; /* idx is a power of two */ |
| 50 |
|
| po_arena *arena; /* borrowed: where label blocks live */ |
| 51 |
|
| uint32_t collisions; /* full-hash collisions caught by memcmp */ |
| 52 |
|
| } po_series_tab; |
| 53 |
|
| |
| 54 |
38 |
| static int po_series_tab_init(po_series_tab *t, po_arena *arena, uint32_t hint) { |
| 55 |
38 |
| uint32_t slots = 64; |
| 56 |
119 |
▶ | while (slots < hint * 2) slots <<= 1; |
Branch: 1 branch
| Branch | True | False | Total |
| while (slots < hint * 2) slots <<= 1; |
81 |
38 |
119 |
|
| 57 |
38 |
| memset(t, 0, sizeof(*t)); |
| 58 |
38 |
| t->cap = hint < 32 ? 32 : hint; |
| 59 |
38 |
| t->ent = (po_series *)calloc(t->cap, sizeof(po_series)); |
| 60 |
38 |
▶ | if (!t->ent) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!t->ent) return 0; |
0 |
38 |
38 |
|
| 61 |
38 |
| t->idx = (uint32_t *)calloc(slots, sizeof(uint32_t)); |
| 62 |
38 |
▶ | if (!t->idx) { free(t->ent); t->ent = NULL; return 0; } |
Branch: 1 branch
| Branch | True | False | Total |
| if (!t->idx) { free(t->ent); t->ent = NULL; return 0; } |
0 |
38 |
38 |
|
| 63 |
38 |
| t->mask = slots - 1; |
| 64 |
38 |
| t->arena = arena; |
| 65 |
38 |
| return 1; |
| 66 |
|
| } |
| 67 |
|
| |
| 68 |
38 |
| static void po_series_tab_free(po_series_tab *t) { |
| 69 |
38 |
| free(t->ent); free(t->idx); |
| 70 |
38 |
| t->ent = NULL; t->idx = NULL; t->n = t->cap = 0; |
| 71 |
38 |
| } |
| 72 |
|
| |
| 73 |
26 |
| static int po_series_grow(po_series_tab *t) { |
| 74 |
26 |
| uint32_t slots = (t->mask + 1) * 2; |
| 75 |
26 |
| uint32_t *ni = (uint32_t *)calloc(slots, sizeof(uint32_t)); |
| 76 |
|
| uint32_t i; |
| 77 |
26 |
▶ | if (!ni) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ni) return 0; |
0 |
26 |
26 |
|
| 78 |
18842 |
▶ | for (i = 0; i < t->n; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < t->n; i++) { |
18816 |
26 |
18842 |
|
| 79 |
18816 |
| uint32_t h = (uint32_t)(t->ent[i].id.lo) & (slots - 1); |
| 80 |
21900 |
▶ | while (ni[h]) h = (h + 1) & (slots - 1); |
Branch: 1 branch
| Branch | True | False | Total |
| while (ni[h]) h = (h + 1) & (slots - 1); |
3084 |
18816 |
21900 |
|
| 81 |
18816 |
| ni[h] = i + 1; |
| 82 |
|
| } |
| 83 |
26 |
| free(t->idx); |
| 84 |
26 |
| t->idx = ni; |
| 85 |
26 |
| t->mask = slots - 1; |
| 86 |
26 |
| return 1; |
| 87 |
|
| } |
| 88 |
|
| |
| 89 |
|
| /* Look up or intern. `block` is the canonical attribute block from |
| 90 |
|
| * po_attrs_encode. Returns the dense slot, or 0xFFFFFFFF on failure. |
| 91 |
|
| * |
| 92 |
|
| * `created` is set when this call introduced the series - which is the ONLY |
| 93 |
|
| * moment the cardinality cap can be enforced, because it is the only moment |
| 94 |
|
| * anything knows the set is new. */ |
| 95 |
|
| #define PO_SERIES_ERR 0xFFFFFFFFu |
| 96 |
|
| |
| 97 |
15277 |
| static uint32_t po_series_intern(po_series_tab *t, |
| 98 |
|
| const char *block, uint32_t len, |
| 99 |
|
| po_h128 *id_out, int *created) { |
| 100 |
15277 |
| po_h128 h = po_murmur3_128(block, (size_t)len, 0); |
| 101 |
15277 |
| uint32_t pos = (uint32_t)h.lo & t->mask; |
| 102 |
|
| |
| 103 |
15277 |
▶ | if (created) *created = 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (created) *created = 0; |
15273 |
4 |
15277 |
|
| 104 |
|
| |
| 105 |
9497 |
| for (;;) { |
| 106 |
24774 |
| uint32_t e = t->idx[pos]; |
| 107 |
24774 |
▶ | if (!e) break; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!e) break; |
12636 |
12138 |
24774 |
|
| 108 |
|
| { |
| 109 |
12138 |
| po_series *s = &t->ent[e - 1]; |
| 110 |
12138 |
▶ | if (po_h128_eq(s->id, h)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (po_h128_eq(s->id, h)) { |
2641 |
9497 |
12138 |
|
| 111 |
|
| /* The hash matched. Now VERIFY, because a 128-bit match is |
| 112 |
|
| * not proof and the failure it would hide is invisible. */ |
| 113 |
2641 |
▶ | if (s->len == len && |
Branch: 2 branches
| Branch | True | False | Total |
| if (s->len == len && |
2641 |
0 |
2641 |
| if (s->len == len && |
2640 |
1 |
2641 |
|
| 114 |
2640 |
▶ | (len == 0 || memcmp(t->arena->base + s->off, block, len) == 0)) { |
Branch: 1 branch
| Branch | True | False | Total |
| (len == 0 || memcmp(t->arena->base + s->off, block, len) == 0)) { |
2640 |
0 |
2640 |
|
| 115 |
2641 |
▶ | if (id_out) *id_out = h; |
Branch: 1 branch
| Branch | True | False | Total |
| if (id_out) *id_out = h; |
2641 |
0 |
2641 |
|
| 116 |
2641 |
| return s->slot; |
| 117 |
|
| } |
| 118 |
|
| /* A genuine full-hash collision on different bytes. Counted, |
| 119 |
|
| * because if this is ever non-zero in the field it is worth |
| 120 |
|
| * knowing rather than guessing at. */ |
| 121 |
0 |
| t->collisions++; |
| 122 |
|
| } |
| 123 |
|
| } |
| 124 |
9497 |
| pos = (pos + 1) & t->mask; |
| 125 |
|
| } |
| 126 |
|
| |
| 127 |
12636 |
▶ | if (t->n == t->cap) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (t->n == t->cap) { |
26 |
12610 |
12636 |
|
| 128 |
26 |
| uint32_t want = t->cap * 2; |
| 129 |
26 |
| po_series *ne = (po_series *)realloc(t->ent, want * sizeof(po_series)); |
| 130 |
26 |
▶ | if (!ne) return PO_SERIES_ERR; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!ne) return PO_SERIES_ERR; |
0 |
26 |
26 |
|
| 131 |
26 |
| t->ent = ne; t->cap = want; |
| 132 |
|
| } |
| 133 |
12636 |
▶ | if ((t->n + 1) * 2 > t->mask + 1) { |
Branch: 1 branch
| Branch | True | False | Total |
| if ((t->n + 1) * 2 > t->mask + 1) { |
26 |
12610 |
12636 |
|
| 134 |
26 |
▶ | if (!po_series_grow(t)) return PO_SERIES_ERR; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!po_series_grow(t)) return PO_SERIES_ERR; |
0 |
26 |
26 |
|
| 135 |
26 |
| pos = (uint32_t)h.lo & t->mask; |
| 136 |
30 |
▶ | while (t->idx[pos]) pos = (pos + 1) & t->mask; |
Branch: 1 branch
| Branch | True | False | Total |
| while (t->idx[pos]) pos = (pos + 1) & t->mask; |
4 |
26 |
30 |
|
| 137 |
|
| } |
| 138 |
|
| |
| 139 |
|
| { |
| 140 |
12636 |
▶ | uint32_t off = len ? po_arena_put(t->arena, block, (size_t)len) : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t off = len ? po_arena_put(t->arena, block, (size_t)len) : 0; |
12635 |
1 |
12636 |
|
| 141 |
|
| po_series *s; |
| 142 |
12636 |
▶ | if (len && off == PO_ARENA_ERR) return PO_SERIES_ERR; |
Branch: 2 branches
| Branch | True | False | Total |
| if (len && off == PO_ARENA_ERR) return PO_SERIES_ERR; |
12635 |
1 |
12636 |
| if (len && off == PO_ARENA_ERR) return PO_SERIES_ERR; |
0 |
12635 |
12635 |
|
| 143 |
12636 |
| s = &t->ent[t->n]; |
| 144 |
12636 |
| s->id = h; |
| 145 |
12636 |
| s->off = off; |
| 146 |
12636 |
| s->len = len; |
| 147 |
12636 |
| s->slot = t->n; |
| 148 |
12636 |
| t->idx[pos] = t->n + 1; |
| 149 |
12636 |
| t->n++; |
| 150 |
12636 |
▶ | if (id_out) *id_out = h; |
Branch: 1 branch
| Branch | True | False | Total |
| if (id_out) *id_out = h; |
12636 |
0 |
12636 |
|
| 151 |
12636 |
▶ | if (created) *created = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (created) *created = 1; |
12632 |
4 |
12636 |
|
| 152 |
12636 |
| return s->slot; |
| 153 |
|
| } |
| 154 |
|
| } |
| 155 |
|
| |
| 156 |
|
| /* The 64 bits stored in po_rec.series. The full 128 live in the segment's |
| 157 |
|
| * series table; the record carries the low half plus its dense slot, which is |
| 158 |
|
| * all a reader needs to get back to the whole thing. */ |
| 159 |
715 |
| static po_u64 po_series_key(po_h128 id) { return id.lo; } |
| 160 |
|
| |
| 161 |
|
| #endif /* PO_LABELS_H */ |