| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || !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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| || !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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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
| Branch | True | False | Total |
| 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 |