phash.h

filter: Statementstmt 98.4% 63 / 64 Branchbran 84.2% 64 / 76 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 90.7% 127 / 140 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« chd.h ↑ Summary
1 #ifndef PHASH_H
2 #define PHASH_H
3 #include <stdint.h>
4 #include <string.h>
5 #include <stddef.h>
6 #include <stdlib.h>
7 #include <errno.h>
8 #include <fcntl.h>
9 #include <unistd.h>
10 #include <sys/mman.h>
11 #include <sys/stat.h>
12 #include <stdio.h>
13  
14 /* Older/rarer libc may lack O_NOFOLLOW; degrade to 0 (no-op) rather than fail to compile. */
15 #ifndef O_NOFOLLOW
16 #define O_NOFOLLOW 0
17 #endif
18  
19 #define XXH_INLINE_ALL
20 #include "xxhash.h"
21  
22 #define PH_MAGIC 0x31534850u /* 'P''H''S''1' little-endian */
23 #define PH_VERSION 2u /* v2: bucket_count=ceil(n/lambda), byte-packed disp[] (disp_width bytes/entry) */
24 #define PH_ENDIAN_MARK 0x0102030405060708ull
25 #define PH_TYPE_INT 1u
26 #define PH_TYPE_STR 2u
27 /* Heap-handle type tags (PhSet/PhBuilder only, NOT on-disk format). Catches a
28 * handle reblessed into the wrong package -- sv_derived_from() can't detect
29 * that, since blessing is just a stash pointer and the C struct underneath is
30 * reinterpreted regardless. type_tag is the first member of both structs, so
31 * even a cross-blessed pointer reads a valid tag (never OOB); mismatch = wrong struct. */
32 #define PH_SET_TAG 0x50534554u /* PSET */
33 #define PH_BUILDER_TAG 0x50424c44u /* PBLD */
34 typedef struct { uint64_t off, len; } PhStrSlot;
35 typedef struct {
36 /* disp_width (v2; reuses v1's _pad slot, struct size/layout unchanged): byte
37 * width of each byte-packed disp[] entry (1..4); disp[b] is disp_width
38 * little-endian bytes at disp_off + b*disp_width. */
39 uint32_t magic, version, key_type, disp_width;
40 uint64_t endian, n, bucket_count, seed0;
41 uint64_t disp_off, disp_len, slots_off, slots_len, arena_off, arena_len, file_size;
42 } PhHeader;
43 _Static_assert(sizeof(PhHeader) % 8 == 0, "PhHeader must be 8-aligned");
44  
45 /* Build side (chd.h) and lookup side (ph_has_*) MUST compute the slot with
46 * byte-identical arithmetic: same hash fn, same ph_mix, same modulo order, same seed. */
47 11609557 static inline uint64_t ph_h_int(int64_t k, uint64_t seed){ return XXH3_64bits_withSeed(&k,sizeof k,seed); }
48 4240187 static inline uint64_t ph_h_str(const void*k,size_t n,uint64_t seed){ return XXH3_64bits_withSeed(k,n,seed); }
49 14661933 static inline uint64_t ph_mix(uint64_t s,uint64_t d){ return s ^ (d*0x9E3779B97F4A7C15ull + 0x1ull); }
50 /* Reads a width-byte (1..4) little-endian uint -- the byte-packed disp[]
51 * entry. Fixed <=4-iteration loop, byte-addressed so no alignment requirement (unlike the v1 uint32 disp[]). */
52 53056 static inline uint32_t ph_load_uint_le(const uint8_t *p, uint32_t width) {
53 53056 uint32_t v = 0, i;
54 188991 ▶ for (i = 0; i < width; i++) v |= (uint32_t)p[i] << (8u*i);
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < width; i++) v |= (uint32_t)p[i] << (8u*i); 135935 53056 188991
55 53056 return v;
56 }
57  
58 /* --- read-only mmapped handle to a built image --- */
59 typedef struct {
60 uint32_t type_tag; /* PH_SET_TAG; must stay the first member -- see above */
61 int fd; void *map; size_t map_size;
62 const PhHeader *hdr; const uint8_t *disp; const void *slots; const uint8_t *arena;
63 char *path;
64 uint8_t path_utf8;
65 } PhSet;
66  
67 /* disp[b] = disp_width little-endian bytes at s->disp + b*disp_width; in bounds
68 * because b < bucket_count and ph_open checked bucket_count*disp_width <= disp_len. */
69 53056 static inline uint32_t ph_disp(const PhSet *s, uint64_t b) {
70 53056 uint32_t w = s->hdr->disp_width; /* single load, avoid re-reading the mapped header */
71 53056 return ph_load_uint_le(s->disp + b * w, w);
72 }
73 46378 static inline int ph_has_int(const PhSet *s, int64_t key) {
74 46378 ▶ const PhHeader *h = s->hdr; if (!h->n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
const PhHeader *h = s->hdr; if (!h->n) return 0; 124 46254 46378
75 46254 uint64_t b = ph_h_int(key, h->seed0) % h->bucket_count;
76 46254 uint64_t slot = ph_h_int(key, ph_mix(h->seed0, ph_disp(s, b))) % h->n;
77 46254 return ((const int64_t*)s->slots)[slot] == key;
78 }
79 6926 static inline int ph_has_str(const PhSet *s, const void *key, size_t klen) {
80 6926 ▶ const PhHeader *h = s->hdr; if (!h->n) return 0;
Branch: 1 branch
BranchTrueFalseTotal
const PhHeader *h = s->hdr; if (!h->n) return 0; 124 6802 6926
81 6802 uint64_t b = ph_h_str(key, klen, h->seed0) % h->bucket_count;
82 6802 uint64_t slot = ph_h_str(key, klen, ph_mix(h->seed0, ph_disp(s, b))) % h->n;
83 6802 const PhStrSlot *ss = &((const PhStrSlot*)s->slots)[slot];
84 /* ss (off,len) comes straight from the mmapped file -- untrusted, a
85 * crafted/corrupt image can put anything there; ph_open only validates the
86 * arena region as a whole, not this slot. A violation means "not present",
87 * never OOB. Overflow-safe: never forms off+len (checks off<=limit first so limit-off can't underflow). */
88 6802 ▶ if (ss->off > h->arena_len || ss->len > h->arena_len - ss->off) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (ss->off > h->arena_len || ss->len > h->arena_len - ss->off) return 0; 6802 0 6802
if (ss->off > h->arena_len || ss->len > h->arena_len - ss->off) return 0; 1 6801 6802
89 6801 ▶ return ss->len == klen && memcmp(s->arena + ss->off, key, klen) == 0;
Branch: 2 branches
BranchTrueFalseTotal
return ss->len == klen && memcmp(s->arena + ss->off, key, klen) == 0; 5937 864 6801
return ss->len == klen && memcmp(s->arena + ss->off, key, klen) == 0; 5935 2 5937
90 }
91  
92 /* [off, off+len) fits inside [0, limit); overflow-safe -- never computes
93 * off+len, so a huge off/len can't wrap around and slip past the check. */
94 6129 static inline int ph_region_ok(uint64_t off, uint64_t len, uint64_t limit) {
95 6129 ▶ return off <= limit && len <= limit - off;
Branch: 2 branches
BranchTrueFalseTotal
return off <= limit && len <= limit - off; 6127 2 6129
return off <= limit && len <= limit - off; 6127 0 6127
96 }
97 /* count*size <= have, overflow-safe via pre-divide (count > MAX/size) instead of checking after multiplying. */
98 163 static inline int ph_mul_le(uint64_t count, uint64_t size, uint64_t have) {
99 163 ▶ if (size != 0 && count > UINT64_MAX / size) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (size != 0 && count > UINT64_MAX / size) return 0; 163 0 163
if (size != 0 && count > UINT64_MAX / size) return 0; 0 163 163
100 163 return count * size <= have;
101 }
102  
103 94 static PhSet *ph_open(const char *path, char *err, size_t el) {
104 /* O_NOFOLLOW: refuse a symlink at the final component -- a .phs path can
105 * come from anywhere, and following a planted symlink is a classic TOCTOU/redirection trap. */
106 94 int fd = open(path, O_RDONLY | O_CLOEXEC | O_NOFOLLOW);
107 94 ▶ if (fd < 0) { snprintf(err,el,"open: %s", strerror(errno)); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (fd < 0) { snprintf(err,el,"open: %s", strerror(errno)); return NULL; } 2 92 94
108 struct stat st;
109 92 ▶ if (fstat(fd,&st) < 0) { snprintf(err,el,"fstat: %s", strerror(errno)); close(fd); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (fstat(fd,&st) < 0) { snprintf(err,el,"fstat: %s", strerror(errno)); close(fd); return NULL; } 0 92 92
110 92 ▶ if ((uint64_t)st.st_size < sizeof(PhHeader)) { snprintf(err,el,"truncated file"); close(fd); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if ((uint64_t)st.st_size < sizeof(PhHeader)) { snprintf(err,el,"truncated file"); close(fd); return NULL; } 1 91 92
111 91 void *m = mmap(NULL, st.st_size, PROT_READ, MAP_SHARED, fd, 0);
112 91 ▶ if (m == MAP_FAILED) { snprintf(err,el,"mmap: %s", strerror(errno)); close(fd); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (m == MAP_FAILED) { snprintf(err,el,"mmap: %s", strerror(errno)); close(fd); return NULL; } 0 91 91
113 91 const PhHeader *h = (const PhHeader*)m;
114 91 const char *bad = NULL;
115 /* Untrusted input (dump/load can load a .phs from anywhere, crafted or
116 * corrupt): every check below uses exact equality or the overflow-safe
117 * helpers above, never a bare "off+len > limit" that a huge off/len can wrap past. */
118 91 ▶ if (h->magic != PH_MAGIC) bad = "bad magic (not a PerfectHash image)";
Branch: 1 branch
BranchTrueFalseTotal
if (h->magic != PH_MAGIC) bad = "bad magic (not a PerfectHash image)"; 1 90 91
119 90 ▶ else if (h->version != PH_VERSION) bad = "unsupported format version";
Branch: 1 branch
BranchTrueFalseTotal
else if (h->version != PH_VERSION) bad = "unsupported format version"; 0 90 90
120 90 ▶ else if (h->endian != PH_ENDIAN_MARK) bad = "built for a different architecture";
Branch: 1 branch
BranchTrueFalseTotal
else if (h->endian != PH_ENDIAN_MARK) bad = "built for a different architecture"; 1 89 90
121 89 ▶ else if (h->file_size != (uint64_t)st.st_size) bad = "size mismatch";
Branch: 1 branch
BranchTrueFalseTotal
else if (h->file_size != (uint64_t)st.st_size) bad = "size mismatch"; 0 89 89
122 89 ▶ else if (h->key_type != PH_TYPE_INT && h->key_type != PH_TYPE_STR) bad = "corrupt PerfectHash image";
Branch: 2 branches
BranchTrueFalseTotal
else if (h->key_type != PH_TYPE_INT && h->key_type != PH_TYPE_STR) bad = "corrupt PerfectHash image"; 36 53 89
else if (h->key_type != PH_TYPE_INT && h->key_type != PH_TYPE_STR) bad = "corrupt PerfectHash image"; 1 35 36
123 88 ▶ else if (h->n > 0 && h->bucket_count == 0) bad = "corrupt PerfectHash image"; /* else hash%bucket_count divides by zero */
Branch: 2 branches
BranchTrueFalseTotal
else if (h->n > 0 && h->bucket_count == 0) bad = "corrupt PerfectHash image"; /* else hash%bucket_count divides by zero */ 80 8 88
else if (h->n > 0 && h->bucket_count == 0) bad = "corrupt PerfectHash image"; /* else hash%bucket_count divides by zero */ 1 79 80
124 87 ▶ else if (h->disp_width < 1u || h->disp_width > 4u) bad = "corrupt PerfectHash image"; /* byte-packed disp: 1..4 bytes/entry, validate before it feeds ph_mul_le */
Branch: 2 branches
BranchTrueFalseTotal
else if (h->disp_width < 1u || h->disp_width > 4u) bad = "corrupt PerfectHash image"; /* byte-packed disp: 1..4 bytes/entry, validate before it feeds ph_mul_le */ 86 1 87
else if (h->disp_width < 1u || h->disp_width > 4u) bad = "corrupt PerfectHash image"; /* byte-packed disp: 1..4 bytes/entry, validate before it feeds ph_mul_le */ 2 84 86
125 84 ▶ else if (!ph_region_ok(h->disp_off, h->disp_len, h->file_size)
Branch: 1 branch
BranchTrueFalseTotal
else if (!ph_region_ok(h->disp_off, h->disp_len, h->file_size) 83 1 84
126 84 ▶ || !ph_mul_le(h->bucket_count, h->disp_width, h->disp_len)) bad = "corrupt PerfectHash image";
Branch: 1 branch
BranchTrueFalseTotal
|| !ph_mul_le(h->bucket_count, h->disp_width, h->disp_len)) bad = "corrupt PerfectHash image"; 2 81 83
127 81 ▶ else if (!ph_region_ok(h->slots_off, h->slots_len, h->file_size)
Branch: 1 branch
BranchTrueFalseTotal
else if (!ph_region_ok(h->slots_off, h->slots_len, h->file_size) 80 1 81
128 80 ▶ || !ph_mul_le(h->n, h->key_type==PH_TYPE_INT ? sizeof(int64_t) : sizeof(PhStrSlot), h->slots_len))
Branch: 2 branches
BranchTrueFalseTotal
|| !ph_mul_le(h->n, h->key_type==PH_TYPE_INT ? sizeof(int64_t) : sizeof(PhStrSlot), h->slots_len)) 45 35 80
|| !ph_mul_le(h->n, h->key_type==PH_TYPE_INT ? sizeof(int64_t) : sizeof(PhStrSlot), h->slots_len)) 1 79 80
129 2 bad = "corrupt PerfectHash image";
130 79 ▶ else if (h->key_type == PH_TYPE_STR && !ph_region_ok(h->arena_off, h->arena_len, h->file_size))
Branch: 2 branches
BranchTrueFalseTotal
else if (h->key_type == PH_TYPE_STR && !ph_region_ok(h->arena_off, h->arena_len, h->file_size)) 35 44 79
else if (h->key_type == PH_TYPE_STR && !ph_region_ok(h->arena_off, h->arena_len, h->file_size)) 0 35 35
131 0 bad = "corrupt PerfectHash image";
132 /* disp[] is byte-packed, so no alignment requirement (the old v1 disp_off&3
133 * check is gone). slots[] (int64_t/PhStrSlot) still needs 8-alignment -- a
134 * crafted image with an in-bounds but misaligned slots_off would otherwise reach
135 * an unaligned load in ph_has_int/ph_has_str/each_key (UB; SIGBUS on strict-alignment CPUs). */
136 79 ▶ else if (h->slots_off & 7u) bad = "misaligned region";
Branch: 1 branch
BranchTrueFalseTotal
else if (h->slots_off & 7u) bad = "misaligned region"; 1 78 79
137 91 ▶ if (bad) { snprintf(err,el,"%s",bad); munmap(m,st.st_size); close(fd); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (bad) { snprintf(err,el,"%s",bad); munmap(m,st.st_size); close(fd); return NULL; } 13 78 91
138 78 PhSet *s = (PhSet*)malloc(sizeof *s);
139 78 ▶ if (!s) { snprintf(err,el,"out of memory"); munmap(m,st.st_size); close(fd); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!s) { snprintf(err,el,"out of memory"); munmap(m,st.st_size); close(fd); return NULL; } 0 78 78
140 78 s->type_tag = PH_SET_TAG;
141 78 s->path_utf8 = 0;
142 78 s->path = strdup(path);
143 78 ▶ if (!s->path) { snprintf(err,el,"strdup: %s", strerror(errno)); free(s); munmap(m,st.st_size); close(fd); return NULL; }
Branch: 1 branch
BranchTrueFalseTotal
if (!s->path) { snprintf(err,el,"strdup: %s", strerror(errno)); free(s); munmap(m,st.st_size); close(fd); return NULL; } 0 78 78
144 78 s->fd=fd; s->map=m; s->map_size=st.st_size; s->hdr=h;
145 78 s->disp=(const uint8_t*)m + h->disp_off;
146 78 s->slots=(const uint8_t*)m + h->slots_off;
147 78 ▶ s->arena = h->key_type==PH_TYPE_STR ? (const uint8_t*)m + h->arena_off : NULL;
Branch: 1 branch
BranchTrueFalseTotal
s->arena = h->key_type==PH_TYPE_STR ? (const uint8_t*)m + h->arena_off : NULL; 35 43 78
148 78 return s;
149 }
150 78 ▶static void ph_close(PhSet *s){ if(!s) return; free(s->path); munmap(s->map,s->map_size); close(s->fd); free(s); }
Branch: 1 branch
BranchTrueFalseTotal
static void ph_close(PhSet *s){ if(!s) return; free(s->path); munmap(s->map,s->map_size); close(s->fd); free(s); } 0 78 78
151  
152 #endif
« chd.h ↑ Summary