include/punk_observe/po_hash.h

filter: Statementstmt 100% 62 / 62 Branchbran 83.3% 5 / 6 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 98.5% 67 / 68 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« xs/query.xs ↑ Summary include/punk_observe/po_metric.h »
1 /* po_hash.h - MurmurHash3 x64 128-bit.
2 *
3 * This produces the series id, so it is not a hash table's convenience - it
4 * is an IDENTITY, computed independently by N workers that never talk to each
5 * other. Phase 4 turns on that: if two workers hash the same label set to the
6 * same 128 bits with no coordination, per-worker writing is possible; if they
7 * do not, nothing else in the design works.
8 *
9 * WHY 128 BITS. A 64-bit id across ten million series has a birthday collision
10 * probability around 0.3%: small enough to feel safe, large enough to happen
11 * somewhere in a fleet, and a collision here silently merges two unrelated
12 * services into one chart. Nobody would ever find it. 128 bits puts that
13 * probability past the point of caring - and the full label block is STILL
14 * compared with memcmp before an id is reused, because a hash that is only
15 * probably unique is not an identity.
16 *
17 * WHY MURMUR. Fast, non-cryptographic (this is not a security boundary),
18 * fixed by its author, and - the part that matters - it has PUBLISHED TEST
19 * VECTORS, so t/0021-series-id.t can assert this implementation against
20 * something outside it rather than against itself.
21 *
22 * MurmurHash3 was written by Austin Appleby and placed in the public domain.
23 */
24 #ifndef PO_HASH_H
25 #define PO_HASH_H
26  
27 #include "punk_observe/po_compat.h"
28  
29 typedef struct { po_u64 hi, lo; } po_h128;
30  
31 2865116 static po_u64 po_rotl64(po_u64 x, int r) {
32 2865116 return (x << r) | (x >> (64 - r));
33 }
34  
35 5659856 static po_u64 po_fmix64(po_u64 k) {
36 5659856 k ^= k >> 33;
37 5659856 k *= (po_u64)0xff51afd7ed558ccdULL;
38 5659856 k ^= k >> 33;
39 5659856 k *= (po_u64)0xc4ceb9fe1a85ec53ULL;
40 5659856 k ^= k >> 33;
41 5659856 return k;
42 }
43  
44 /* Reads eight bytes little-endian regardless of host order, so the same input
45 * gives the same id on every architecture. A big-endian worker and a
46 * little-endian one must agree, or a mixed fleet splits every series in two. */
47 3638 static po_u64 po_getblock64(const uint8_t *p, size_t i) {
48 po_u64 v;
49 3638 memcpy(&v, p + i * 8, 8); /* memcpy, not a cast: alignment */
50 3638 return po_le64(v);
51 }
52  
53 2827938 static po_h128 po_murmur3_128(const void *key, size_t len, uint32_t seed) {
54 2827938 const uint8_t *data = (const uint8_t *)key;
55 2827938 const size_t nblocks = len / 16;
56 2827938 po_u64 h1 = seed, h2 = seed;
57 2827938 const po_u64 c1 = (po_u64)0x87c37b91114253d5ULL;
58 2827938 const po_u64 c2 = (po_u64)0x4cf5ad432745937fULL;
59 size_t i;
60 po_h128 out;
61  
62 2829757 ▶ for (i = 0; i < nblocks; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < nblocks; i++) { 1819 2827938 2829757
63 1819 po_u64 k1 = po_getblock64(data, i * 2 + 0);
64 1819 po_u64 k2 = po_getblock64(data, i * 2 + 1);
65  
66 1819 k1 *= c1; k1 = po_rotl64(k1, 31); k1 *= c2; h1 ^= k1;
67 1819 h1 = po_rotl64(h1, 27); h1 += h2; h1 = h1 * 5 + 0x52dce729;
68 1819 k2 *= c2; k2 = po_rotl64(k2, 33); k2 *= c1; h2 ^= k2;
69 1819 h2 = po_rotl64(h2, 31); h2 += h1; h2 = h2 * 5 + 0x38495ab5;
70 }
71  
72 {
73 2827938 const uint8_t *tail = data + nblocks * 16;
74 2827938 po_u64 k1 = 0, k2 = 0;
75 2827938 switch (len & 15) {
76 2662 case 15: k2 ^= ((po_u64)tail[14]) << 48; /* fallthrough */
77 9256 case 14: k2 ^= ((po_u64)tail[13]) << 40; /* fallthrough */
78 26749 case 13: k2 ^= ((po_u64)tail[12]) << 32; /* fallthrough */
79 30396 case 12: k2 ^= ((po_u64)tail[11]) << 24; /* fallthrough */
80 30865 case 11: k2 ^= ((po_u64)tail[10]) << 16; /* fallthrough */
81 30917 case 10: k2 ^= ((po_u64)tail[ 9]) << 8; /* fallthrough */
82 30925 case 9: k2 ^= ((po_u64)tail[ 8]) << 0;
83 30925 k2 *= c2; k2 = po_rotl64(k2, 33); k2 *= c1; h2 ^= k2;
84 /* fallthrough */
85 31935 case 8: k1 ^= ((po_u64)tail[ 7]) << 56; /* fallthrough */
86 32084 case 7: k1 ^= ((po_u64)tail[ 6]) << 48; /* fallthrough */
87 33564 case 6: k1 ^= ((po_u64)tail[ 5]) << 40; /* fallthrough */
88 38691 case 5: k1 ^= ((po_u64)tail[ 4]) << 32; /* fallthrough */
89 50819 case 4: k1 ^= ((po_u64)tail[ 3]) << 24; /* fallthrough */
90 2822292 case 3: k1 ^= ((po_u64)tail[ 2]) << 16; /* fallthrough */
91 2824559 case 2: k1 ^= ((po_u64)tail[ 1]) << 8; /* fallthrough */
92 2826915 case 1: k1 ^= ((po_u64)tail[ 0]) << 0;
93 2826915 k1 *= c1; k1 = po_rotl64(k1, 31); k1 *= c2; h1 ^= k1;
94 2826915 break;
95 1023 default: break;
96 }
97 }
98  
99 2827938 h1 ^= (po_u64)len; h2 ^= (po_u64)len;
100 2827938 h1 += h2;
101 2827938 h2 += h1;
102 2827938 h1 = po_fmix64(h1);
103 2827938 h2 = po_fmix64(h2);
104 2827938 h1 += h2;
105 2827938 h2 += h1;
106  
107 2827938 out.lo = h1;
108 2827938 out.hi = h2;
109 2827938 return out;
110 }
111  
112 /* A 32-bit hash for the in-memory tables, where a collision costs a probe and
113 * nothing else. Not used for identity. */
114 1333931 static uint32_t po_hash32(const void *key, size_t len) {
115 1333931 po_h128 h = po_murmur3_128(key, len, 0);
116 1333931 return (uint32_t)(h.lo & 0xFFFFFFFFu);
117 }
118  
119 12138 static int po_h128_eq(po_h128 a, po_h128 b) {
120 12138 ▶ return a.hi == b.hi && a.lo == b.lo;
Branch: 2 branches
BranchTrueFalseTotal
return a.hi == b.hi && a.lo == b.lo; 2641 9497 12138
return a.hi == b.hi && a.lo == b.lo; 2641 0 2641
121 }
122  
123 #endif /* PO_HASH_H */
« xs/query.xs ↑ Summary include/punk_observe/po_metric.h »