forked from open-telemetry/opentelemetry-ebpf-profiler
-
Notifications
You must be signed in to change notification settings - Fork 1
/
hash.h
92 lines (78 loc) · 2.2 KB
/
hash.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#ifndef OPTI_HASH_H
#define OPTI_HASH_H
#include "types.h"
#define ROUNDUP_8(x) ((x + 7) & ~7)
static inline __attribute__((__always_inline__))
bool hash_custom_labels(CustomLabelsArray *lbls, int seed, u64 *out) {
// apply murmurhash2 as though this is an array of
// the number of labels (8 bytes), followed by all the key/val lengths,
// followed by all the keys/vals.
const u64 m = 0xc6a4a7935bd1e995LLU;
const int r = 47;
int len = 8;
for (int i = 0; i < MAX_CUSTOM_LABELS; ++i) {
if (i >= lbls->len)
break;
len += 8;
len += ROUNDUP_8(lbls->labels[i].key_len);
len += ROUNDUP_8(lbls->labels[i].val_len);
}
u64 h = seed ^ (len * m);
// hash the number of labels
{
u64 k = lbls->len;
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
// hash each k/v len
for (int i = 0; i < MAX_CUSTOM_LABELS; ++i) {
// force clang not to unroll the loop by hiding the value of i.
// Unrolling this loop confuses the verifier.
asm volatile("" : "=r"(i) : "0"(i));
if (i >= lbls->len)
break;
u64 k = (((u64)lbls->labels[i].key_len) << 32) | ((u64)lbls->labels[i].val_len);
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
// hash each k/v
for (int i = 0; i < MAX_CUSTOM_LABELS; ++i) {
if (i >= lbls->len)
break;
CustomLabel *lbl = &lbls->labels[i];
u64 kl = ROUNDUP_8(lbl->key_len);
for (int j = 0; j < CUSTOM_LABEL_MAX_VAL_LEN / 8; ++j) {
if (j >= kl)
return false;
u64 k = lbl->key.key_u64[j];
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
u64 vl = ROUNDUP_8(lbl->val_len);
for (int j = 0; j < CUSTOM_LABEL_MAX_VAL_LEN / 8; ++j) {
if (j >= vl)
return false;
u64 k = lbl->val.val_u64[j];
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
}
h ^= h >> r;
h *= m;
h ^= h >> r;
*out = h;
return true;
}
#endif