| 1 |
|
| /* |
| 2 |
|
| * bitset.h -- Shared-memory fixed-size bitset for Linux |
| 3 |
|
| * |
| 4 |
|
| * CAS-based atomic per-bit operations on uint64_t words. |
| 5 |
|
| * Lock-free set/clear/test/toggle with popcount. |
| 6 |
|
| */ |
| 7 |
|
| |
| 8 |
|
| #ifndef BITSET_H |
| 9 |
|
| #define BITSET_H |
| 10 |
|
| |
| 11 |
|
| #include <stddef.h> |
| 12 |
|
| #include <stdint.h> |
| 13 |
|
| #include <stdbool.h> |
| 14 |
|
| #include <stdlib.h> |
| 15 |
|
| #include <string.h> |
| 16 |
|
| #include <unistd.h> |
| 17 |
|
| #include <fcntl.h> |
| 18 |
|
| #include <errno.h> |
| 19 |
|
| #include <limits.h> |
| 20 |
|
| #include <signal.h> |
| 21 |
|
| #include <sys/mman.h> |
| 22 |
|
| #include <sys/stat.h> |
| 23 |
|
| #include <sys/file.h> |
| 24 |
|
| |
| 25 |
|
| #define BS_MAGIC 0x42535431U /* "BST1" */ |
| 26 |
|
| #define BS_VERSION 1 |
| 27 |
|
| #define BS_ERR_BUFLEN (PATH_MAX + 256) |
| 28 |
|
| |
| 29 |
|
| /* ================================================================ |
| 30 |
|
| * Header (128 bytes) |
| 31 |
|
| * ================================================================ */ |
| 32 |
|
| |
| 33 |
|
| typedef struct { |
| 34 |
|
| uint32_t magic; |
| 35 |
|
| uint32_t version; |
| 36 |
|
| uint64_t capacity; /* 8: number of bits */ |
| 37 |
|
| uint64_t total_size; /* 16 */ |
| 38 |
|
| uint64_t data_off; /* 24 */ |
| 39 |
|
| uint32_t num_words; /* 32: ceil(capacity/64) */ |
| 40 |
|
| uint8_t _pad0[28]; /* 36-63 */ |
| 41 |
|
| |
| 42 |
|
| uint64_t stat_sets; /* 64 */ |
| 43 |
|
| uint64_t stat_clears; /* 72 */ |
| 44 |
|
| uint64_t stat_toggles; /* 80 */ |
| 45 |
|
| uint8_t sealed; /* 88: 0 = mutable, 1 = frozen (read-only; lock-free reads) */ |
| 46 |
|
| uint8_t _pad1[39]; /* 89-127 */ |
| 47 |
|
| } BsHeader; |
| 48 |
|
| |
| 49 |
|
| #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 201112L |
| 50 |
|
| _Static_assert(sizeof(BsHeader) == 128, "BsHeader must be 128 bytes"); |
| 51 |
|
| #endif |
| 52 |
|
| |
| 53 |
|
| typedef struct { |
| 54 |
|
| BsHeader *hdr; |
| 55 |
|
| uint64_t *data; |
| 56 |
|
| size_t mmap_size; |
| 57 |
|
| char *path; |
| 58 |
|
| int backing_fd; |
| 59 |
|
| int readonly; /* 1 = frozen O_RDONLY/PROT_READ view. Bit ops are already |
| 60 |
|
| * lock-free CAS/atomics; this only gates mutation. */ |
| 61 |
|
| } BsHandle; |
| 62 |
|
| |
| 63 |
|
| /* Max words the current mapping can physically hold -- derived from the |
| 64 |
|
| * process-private mmap_size (NOT from any attacker-writable header field). |
| 65 |
|
| * Used to bound every file-stored count/index at use against the region size. */ |
| 66 |
9882 |
| static inline uint32_t bs_max_words(const BsHandle *h) { |
| 67 |
9882 |
▶ | if (h->mmap_size < sizeof(BsHeader)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->mmap_size < sizeof(BsHeader)) return 0; |
0 |
9882 |
9882 |
|
| 68 |
9882 |
| uint64_t mw = (h->mmap_size - sizeof(BsHeader)) / 8; |
| 69 |
9882 |
▶ | return mw > UINT32_MAX ? UINT32_MAX : (uint32_t)mw; |
Branch: 1 branch
| Branch | True | False | Total |
| return mw > UINT32_MAX ? UINT32_MAX : (uint32_t)mw; |
9882 |
0 |
9882 |
|
| 70 |
|
| } |
| 71 |
|
| |
| 72 |
|
| /* ================================================================ |
| 73 |
|
| * Bit operations (lock-free CAS) |
| 74 |
|
| * ================================================================ */ |
| 75 |
|
| |
| 76 |
25 |
| static inline int bs_test(BsHandle *h, uint64_t bit) { |
| 77 |
25 |
▶ | if (bit / 64 >= bs_max_words(h)) return 0; /* corrupted header: beyond mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (bit / 64 >= bs_max_words(h)) return 0; /* corrupted header: beyond mapping */ |
0 |
25 |
25 |
|
| 78 |
25 |
| uint64_t word = __atomic_load_n(&h->data[bit / 64], __ATOMIC_ACQUIRE); |
| 79 |
25 |
| return (word >> (bit % 64)) & 1; |
| 80 |
|
| } |
| 81 |
|
| |
| 82 |
|
| /* Set bit. Returns old value (0 or 1). */ |
| 83 |
9698 |
| static inline int bs_set(BsHandle *h, uint64_t bit) { |
| 84 |
9698 |
| uint32_t widx = (uint32_t)(bit / 64); |
| 85 |
9698 |
| uint64_t mask = (uint64_t)1 << (bit % 64); |
| 86 |
9698 |
▶ | if (bit / 64 >= bs_max_words(h)) return 1; /* corrupted header: skip OOB write */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (bit / 64 >= bs_max_words(h)) return 1; /* corrupted header: skip OOB write */ |
9698 |
0 |
9698 |
|
| 87 |
0 |
| for (;;) { |
| 88 |
9698 |
| uint64_t word = __atomic_load_n(&h->data[widx], __ATOMIC_RELAXED); |
| 89 |
19394 |
▶ | if (word & mask) return 1; /* already set */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (word & mask) return 1; /* already set */ |
2 |
9696 |
9698 |
|
| 90 |
9696 |
▶ | if (__atomic_compare_exchange_n(&h->data[widx], &word, word | mask, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(&h->data[widx], &word, word | mask, |
9696 |
0 |
9696 |
|
| 91 |
|
| 1, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) { |
| 92 |
9696 |
| __atomic_add_fetch(&h->hdr->stat_sets, 1, __ATOMIC_RELAXED); |
| 93 |
9696 |
| return 0; |
| 94 |
|
| } |
| 95 |
|
| } |
| 96 |
|
| } |
| 97 |
|
| |
| 98 |
|
| /* Clear bit. Returns old value (0 or 1). */ |
| 99 |
6 |
| static inline int bs_clear(BsHandle *h, uint64_t bit) { |
| 100 |
6 |
| uint32_t widx = (uint32_t)(bit / 64); |
| 101 |
6 |
| uint64_t mask = (uint64_t)1 << (bit % 64); |
| 102 |
6 |
▶ | if (bit / 64 >= bs_max_words(h)) return 0; /* corrupted header: skip OOB write */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (bit / 64 >= bs_max_words(h)) return 0; /* corrupted header: skip OOB write */ |
6 |
0 |
6 |
|
| 103 |
0 |
| for (;;) { |
| 104 |
6 |
| uint64_t word = __atomic_load_n(&h->data[widx], __ATOMIC_RELAXED); |
| 105 |
10 |
▶ | if (!(word & mask)) return 0; /* already clear */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!(word & mask)) return 0; /* already clear */ |
2 |
4 |
6 |
|
| 106 |
4 |
▶ | if (__atomic_compare_exchange_n(&h->data[widx], &word, word & ~mask, |
Branch: 1 branch
| Branch | True | False | Total |
| if (__atomic_compare_exchange_n(&h->data[widx], &word, word & ~mask, |
4 |
0 |
4 |
|
| 107 |
|
| 1, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) { |
| 108 |
4 |
| __atomic_add_fetch(&h->hdr->stat_clears, 1, __ATOMIC_RELAXED); |
| 109 |
4 |
| return 1; |
| 110 |
|
| } |
| 111 |
|
| } |
| 112 |
|
| } |
| 113 |
|
| |
| 114 |
|
| /* Toggle bit. Returns new value (0 or 1). */ |
| 115 |
2 |
| static inline int bs_toggle(BsHandle *h, uint64_t bit) { |
| 116 |
2 |
| uint32_t widx = (uint32_t)(bit / 64); |
| 117 |
2 |
| uint64_t mask = (uint64_t)1 << (bit % 64); |
| 118 |
2 |
▶ | if (bit / 64 >= bs_max_words(h)) return 0; /* corrupted header: skip OOB write */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (bit / 64 >= bs_max_words(h)) return 0; /* corrupted header: skip OOB write */ |
0 |
2 |
2 |
|
| 119 |
2 |
| uint64_t old = __atomic_fetch_xor(&h->data[widx], mask, __ATOMIC_ACQ_REL); |
| 120 |
2 |
| __atomic_add_fetch(&h->hdr->stat_toggles, 1, __ATOMIC_RELAXED); |
| 121 |
2 |
| return (old & mask) ? 0 : 1; |
| 122 |
|
| } |
| 123 |
|
| |
| 124 |
13781 |
| static inline int bs_popcount(uint64_t word) { |
| 125 |
|
| #if defined(__x86_64__) && !defined(__POPCNT__) |
| 126 |
|
| /* Keep the software fallback inline on baseline x86-64 builds. */ |
| 127 |
13781 |
| word -= (word >> 1) & UINT64_C(0x5555555555555555); |
| 128 |
13781 |
| word = (word & UINT64_C(0x3333333333333333)) |
| 129 |
13781 |
| + ((word >> 2) & UINT64_C(0x3333333333333333)); |
| 130 |
13781 |
| word = (word + (word >> 4)) & UINT64_C(0x0f0f0f0f0f0f0f0f); |
| 131 |
13781 |
| return (int)((word * UINT64_C(0x0101010101010101)) >> 56); |
| 132 |
|
| #else |
| 133 |
|
| return __builtin_popcountll(word); |
| 134 |
|
| #endif |
| 135 |
|
| } |
| 136 |
|
| |
| 137 |
|
| /* Population count -- total set bits. */ |
| 138 |
34 |
| static inline uint64_t bs_count(BsHandle *h) { |
| 139 |
34 |
| uint64_t total = 0; |
| 140 |
34 |
| uint32_t nw = h->hdr->num_words; |
| 141 |
34 |
▶ | uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
0 |
34 |
34 |
|
| 142 |
34 |
| uint64_t cap = h->hdr->capacity; |
| 143 |
1163 |
▶ | for (uint32_t i = 0; i < nw; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < nw; i++) { |
1129 |
34 |
1163 |
|
| 144 |
1129 |
| uint64_t word = __atomic_load_n(&h->data[i], __ATOMIC_RELAXED); |
| 145 |
1129 |
▶ | if (i == nw - 1 && (cap % 64)) |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == nw - 1 && (cap % 64)) |
34 |
1095 |
1129 |
| if (i == nw - 1 && (cap % 64)) |
10 |
24 |
34 |
|
| 146 |
10 |
| word &= ((uint64_t)1 << (cap % 64)) - 1; |
| 147 |
1129 |
| total += (uint64_t)bs_popcount(word); |
| 148 |
|
| } |
| 149 |
34 |
| return total; |
| 150 |
|
| } |
| 151 |
|
| |
| 152 |
11 |
| static inline int bs_any(BsHandle *h) { |
| 153 |
11 |
| uint32_t nw = h->hdr->num_words; |
| 154 |
11 |
▶ | uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
0 |
11 |
11 |
|
| 155 |
11 |
| uint64_t cap = h->hdr->capacity; |
| 156 |
22 |
▶ | for (uint32_t i = 0; i < nw; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < nw; i++) { |
17 |
5 |
22 |
|
| 157 |
17 |
| uint64_t word = __atomic_load_n(&h->data[i], __ATOMIC_RELAXED); |
| 158 |
17 |
▶ | if (i == nw - 1 && (cap % 64)) |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == nw - 1 && (cap % 64)) |
5 |
12 |
17 |
| if (i == nw - 1 && (cap % 64)) |
2 |
3 |
5 |
|
| 159 |
2 |
| word &= ((uint64_t)1 << (cap % 64)) - 1; |
| 160 |
17 |
▶ | if (word) return 1; |
Branch: 1 branch
| Branch | True | False | Total |
| if (word) return 1; |
6 |
11 |
17 |
|
| 161 |
|
| } |
| 162 |
5 |
| return 0; |
| 163 |
|
| } |
| 164 |
|
| |
| 165 |
5 |
| static inline int bs_none(BsHandle *h) { return !bs_any(h); } |
| 166 |
|
| |
| 167 |
|
| /* Fill all bits. NOT safe concurrently with per-bit CAS ops. */ |
| 168 |
12 |
| static inline void bs_fill(BsHandle *h) { |
| 169 |
12 |
| uint32_t nw = h->hdr->num_words; |
| 170 |
12 |
▶ | uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound OOB write against mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound OOB write against mapping */ |
0 |
12 |
12 |
|
| 171 |
12 |
| uint64_t cap = h->hdr->capacity; |
| 172 |
1072 |
▶ | for (uint32_t i = 0; i < nw; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < nw; i++) { |
1060 |
12 |
1072 |
|
| 173 |
12 |
▶ | uint64_t valid = (i == nw - 1 && cap % 64) |
Branch: 1 branch
| Branch | True | False | Total |
| uint64_t valid = (i == nw - 1 && cap % 64) |
7 |
5 |
12 |
|
| 174 |
1072 |
▶ | ? ((uint64_t)1 << (cap % 64)) - 1 : ~(uint64_t)0; |
Branch: 1 branch
| Branch | True | False | Total |
| ? ((uint64_t)1 << (cap % 64)) - 1 : ~(uint64_t)0; |
12 |
1048 |
1060 |
|
| 175 |
1060 |
| __atomic_store_n(&h->data[i], valid, __ATOMIC_RELEASE); |
| 176 |
|
| } |
| 177 |
12 |
| } |
| 178 |
|
| |
| 179 |
|
| /* Zero all bits. NOT safe concurrently with per-bit CAS ops. */ |
| 180 |
4 |
| static inline void bs_zero(BsHandle *h) { |
| 181 |
4 |
| uint32_t nw = h->hdr->num_words; |
| 182 |
4 |
▶ | uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound OOB write against mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound OOB write against mapping */ |
0 |
4 |
4 |
|
| 183 |
20 |
▶ | for (uint32_t i = 0; i < nw; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < nw; i++) |
16 |
4 |
20 |
|
| 184 |
16 |
| __atomic_store_n(&h->data[i], 0, __ATOMIC_RELEASE); |
| 185 |
4 |
| } |
| 186 |
|
| |
| 187 |
|
| /* Find first set bit. Returns -1 if none. */ |
| 188 |
5 |
| static inline int64_t bs_first_set(BsHandle *h) { |
| 189 |
5 |
| uint32_t nw = h->hdr->num_words; |
| 190 |
5 |
▶ | uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
0 |
5 |
5 |
|
| 191 |
5 |
| uint64_t cap = h->hdr->capacity; |
| 192 |
9 |
▶ | for (uint32_t i = 0; i < nw; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < nw; i++) { |
8 |
1 |
9 |
|
| 193 |
8 |
| uint64_t word = __atomic_load_n(&h->data[i], __ATOMIC_RELAXED); |
| 194 |
8 |
▶ | if (word) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (word) { |
4 |
4 |
8 |
|
| 195 |
4 |
| uint64_t bit = (uint64_t)i * 64 + __builtin_ctzll(word); |
| 196 |
4 |
▶ | return bit < cap ? (int64_t)bit : -1; |
Branch: 1 branch
| Branch | True | False | Total |
| return bit < cap ? (int64_t)bit : -1; |
4 |
0 |
4 |
|
| 197 |
|
| } |
| 198 |
|
| } |
| 199 |
1 |
| return -1; |
| 200 |
|
| } |
| 201 |
|
| |
| 202 |
|
| /* Find first clear bit. Returns -1 if none. */ |
| 203 |
5 |
| static inline int64_t bs_first_clear(BsHandle *h) { |
| 204 |
5 |
| uint32_t nw = h->hdr->num_words; |
| 205 |
5 |
▶ | uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
Branch: 1 branch
| Branch | True | False | Total |
| uint32_t mw = bs_max_words(h); if (nw > mw) nw = mw; /* bound against mapping */ |
0 |
5 |
5 |
|
| 206 |
5 |
| uint64_t cap = h->hdr->capacity; |
| 207 |
10 |
▶ | for (uint32_t i = 0; i < nw; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint32_t i = 0; i < nw; i++) { |
9 |
1 |
10 |
|
| 208 |
9 |
| uint64_t word = __atomic_load_n(&h->data[i], __ATOMIC_RELAXED); |
| 209 |
9 |
▶ | if (word != ~(uint64_t)0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (word != ~(uint64_t)0) { |
4 |
5 |
9 |
|
| 210 |
4 |
| uint64_t bit = (uint64_t)i * 64 + __builtin_ctzll(~word); |
| 211 |
4 |
▶ | return bit < cap ? (int64_t)bit : -1; |
Branch: 1 branch
| Branch | True | False | Total |
| return bit < cap ? (int64_t)bit : -1; |
3 |
1 |
4 |
|
| 212 |
|
| } |
| 213 |
|
| } |
| 214 |
1 |
| return -1; |
| 215 |
|
| } |
| 216 |
|
| |
| 217 |
|
| /* ================================================================ |
| 218 |
|
| * Create / Open / Close |
| 219 |
|
| * ================================================================ */ |
| 220 |
|
| |
| 221 |
|
| #define BS_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, BS_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while(0) |
| 222 |
|
| |
| 223 |
29 |
| static inline void bs_init_header(void *base, uint64_t total, uint64_t capacity, uint32_t nw) { |
| 224 |
29 |
| BsHeader *hdr = (BsHeader *)base; |
| 225 |
29 |
| memset(base, 0, (size_t)total); |
| 226 |
29 |
| hdr->version = BS_VERSION; |
| 227 |
29 |
| hdr->capacity = capacity; |
| 228 |
29 |
| hdr->total_size = total; |
| 229 |
29 |
| hdr->data_off = sizeof(BsHeader); |
| 230 |
29 |
| hdr->num_words = nw; |
| 231 |
|
| /* Publish magic LAST, as a release store: it is the commit point, so a |
| 232 |
|
| creator killed before it leaves magic==0 and never a file mistaken for |
| 233 |
|
| a valid one. A kill during the field stores leaves one to remove by |
| 234 |
|
| hand. */ |
| 235 |
29 |
| __atomic_store_n(&hdr->magic, BS_MAGIC, __ATOMIC_RELEASE); |
| 236 |
29 |
| __atomic_thread_fence(__ATOMIC_SEQ_CST); |
| 237 |
29 |
| } |
| 238 |
|
| |
| 239 |
|
| /* Validate a mapped header (shared by bs_create reopen and bs_open_fd). */ |
| 240 |
10 |
| static inline int bs_validate_header(const BsHeader *hdr, uint64_t file_size) { |
| 241 |
10 |
▶ | if (hdr->magic != BS_MAGIC) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->magic != BS_MAGIC) return 0; |
0 |
10 |
10 |
|
| 242 |
10 |
▶ | if (hdr->version != BS_VERSION) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->version != BS_VERSION) return 0; |
0 |
10 |
10 |
|
| 243 |
10 |
▶ | if (hdr->capacity == 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->capacity == 0) return 0; |
0 |
10 |
10 |
|
| 244 |
10 |
▶ | if (hdr->capacity > (uint64_t)(UINT32_MAX - 63) * 64) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->capacity > (uint64_t)(UINT32_MAX - 63) * 64) return 0; |
0 |
10 |
10 |
|
| 245 |
10 |
▶ | if (hdr->total_size != file_size) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->total_size != file_size) return 0; |
0 |
10 |
10 |
|
| 246 |
10 |
▶ | if (hdr->data_off != sizeof(BsHeader)) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->data_off != sizeof(BsHeader)) return 0; |
0 |
10 |
10 |
|
| 247 |
10 |
| uint32_t exp_nw = (uint32_t)((hdr->capacity + 63) / 64); |
| 248 |
10 |
▶ | if (hdr->num_words != exp_nw) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->num_words != exp_nw) return 0; |
0 |
10 |
10 |
|
| 249 |
10 |
| uint64_t exp_total = sizeof(BsHeader) + (uint64_t)exp_nw * 8; |
| 250 |
10 |
▶ | if (hdr->total_size != exp_total) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (hdr->total_size != exp_total) return 0; |
0 |
10 |
10 |
|
| 251 |
10 |
| return 1; |
| 252 |
|
| } |
| 253 |
|
| |
| 254 |
36 |
| static inline BsHandle *bs_setup(void *base, size_t ms, const char *path, int bfd) { |
| 255 |
36 |
| BsHeader *hdr = (BsHeader *)base; |
| 256 |
36 |
| BsHandle *h = (BsHandle *)calloc(1, sizeof(BsHandle)); |
| 257 |
36 |
▶ | if (!h) { munmap(base, ms); if (bfd >= 0) close(bfd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h) { munmap(base, ms); if (bfd >= 0) close(bfd); return NULL; } |
0 |
36 |
36 |
| if (!h) { munmap(base, ms); if (bfd >= 0) close(bfd); return NULL; } |
0 |
0 |
0 |
|
| 258 |
36 |
| h->hdr = hdr; |
| 259 |
|
| /* validation pins data_off to sizeof(BsHeader); use the constant so a |
| 260 |
|
| * racing write-peer cannot poison the base pointer after validation */ |
| 261 |
36 |
| h->data = (uint64_t *)((uint8_t *)base + sizeof(BsHeader)); |
| 262 |
36 |
| h->mmap_size = ms; |
| 263 |
36 |
▶ | h->path = path ? strdup(path) : NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| h->path = path ? strdup(path) : NULL; |
13 |
23 |
36 |
|
| 264 |
36 |
| h->backing_fd = bfd; |
| 265 |
36 |
| return h; |
| 266 |
|
| } |
| 267 |
|
| |
| 268 |
|
| /* Securely obtain a fd: create exclusively (O_CREAT|O_EXCL|O_NOFOLLOW at mode, |
| 269 |
|
| * default 0600), or attach an existing file (O_RDWR|O_NOFOLLOW, no O_CREAT). */ |
| 270 |
14 |
| static int bs_secure_open(const char *path, mode_t mode, char *errbuf) { |
| 271 |
14 |
▶ | for (int attempt = 0; attempt < 100; attempt++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (int attempt = 0; attempt < 100; attempt++) { |
14 |
0 |
14 |
|
| 272 |
14 |
| int fd = open(path, O_RDWR|O_CREAT|O_EXCL|O_NOFOLLOW|O_CLOEXEC, mode); |
| 273 |
14 |
▶ | if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd >= 0) { (void)fchmod(fd, mode); return fd; } /* exact mode: umask narrowed the O_EXCL create */ |
5 |
9 |
14 |
|
| 274 |
9 |
▶ | if (errno != EEXIST) { BS_ERR("create %s: %s", path, strerror(errno)); return -1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (errno != EEXIST) { BS_ERR("create %s: %s", path, strerror(errno)); return -1; } |
0 |
9 |
9 |
| if (errno != EEXIST) { BS_ERR("create %s: %s", path, strerror(errno)); return -1; } |
0 |
0 |
0 |
|
| 275 |
9 |
| fd = open(path, O_RDWR|O_NOFOLLOW|O_CLOEXEC); |
| 276 |
9 |
▶ | if (fd >= 0) return fd; |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd >= 0) return fd; |
9 |
0 |
9 |
|
| 277 |
0 |
▶ | if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (errno == ENOENT) continue; /* creator unlinked between our two opens; retry */ |
0 |
0 |
0 |
|
| 278 |
0 |
▶ | BS_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("open %s: %s", path, strerror(errno)); /* ELOOP => symlink rejected */ |
0 |
0 |
0 |
|
| 279 |
0 |
| return -1; |
| 280 |
|
| } |
| 281 |
0 |
▶ | BS_ERR("open %s: create/attach kept racing", path); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("open %s: create/attach kept racing", path); |
0 |
0 |
0 |
|
| 282 |
0 |
| return -1; |
| 283 |
|
| } |
| 284 |
|
| |
| 285 |
|
| /* True iff the whole file is zero -- what an abandoned mid-init |
| 286 |
|
| creator leaves. Lets recovery re-init only a provably-empty file, never |
| 287 |
|
| one that merely starts with a zero word. Cold path, so a byte scan is |
| 288 |
|
| fine. Read, not mapped: a read fault on a tmpfs hole allocates the page. */ |
| 289 |
2 |
| static int bs_file_is_zero(int fd, uint64_t size) { |
| 290 |
|
| char buf[16384]; |
| 291 |
3 |
▶ | for (uint64_t off = 0; off < size; ) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (uint64_t off = 0; off < size; ) { |
2 |
1 |
3 |
|
| 292 |
2 |
| ssize_t n = pread(fd, buf, size - off < sizeof buf ? (size_t)(size - off) : sizeof buf, (off_t)off); |
| 293 |
2 |
▶ | if (n < 0 && errno == EINTR) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if (n < 0 && errno == EINTR) continue; |
0 |
2 |
2 |
| if (n < 0 && errno == EINTR) continue; |
0 |
0 |
0 |
|
| 294 |
2 |
▶ | if (n <= 0) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n <= 0) return 0; |
0 |
2 |
2 |
|
| 295 |
321 |
▶ | for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; |
1 |
319 |
320 |
| for (ssize_t i = 0; i < n; i++) if (buf[i]) return 0; |
320 |
1 |
321 |
|
| 296 |
1 |
| off += (uint64_t)n; |
| 297 |
|
| } |
| 298 |
1 |
| return 1; |
| 299 |
|
| } |
| 300 |
|
| |
| 301 |
|
| /* A sparse segment would SIGBUS at the first write the filesystem cannot back. */ |
| 302 |
14 |
| static int bs_reserve(int fd, uint64_t size) { |
| 303 |
14 |
| const char *sp = getenv("DATA_BITSET_SHARED_SPARSE"); |
| 304 |
14 |
▶ | if (sp && *sp && strcmp(sp, "0")) return 0; |
Branch: 3 branches
| Branch | True | False | Total |
| if (sp && *sp && strcmp(sp, "0")) return 0; |
0 |
14 |
14 |
| if (sp && *sp && strcmp(sp, "0")) return 0; |
0 |
0 |
0 |
| if (sp && *sp && strcmp(sp, "0")) return 0; |
0 |
0 |
0 |
|
| 305 |
|
| /* Before Linux 6.11 tmpfs gives up at any pending signal and undoes the allocation, so a |
| 306 |
|
| * periodic one could keep it from ever completing; SIGSTOP cannot be blocked. */ |
| 307 |
|
| sigset_t all, old; |
| 308 |
14 |
| sigfillset(&all); |
| 309 |
14 |
| sigprocmask(SIG_BLOCK, &all, &old); |
| 310 |
|
| int e; |
| 311 |
14 |
▶ | do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); |
Branch: 1 branch
| Branch | True | False | Total |
| do e = posix_fallocate(fd, 0, (off_t)size); while (e == EINTR); |
0 |
14 |
14 |
|
| 312 |
14 |
| sigprocmask(SIG_SETMASK, &old, NULL); |
| 313 |
14 |
▶ | if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
Branch: 3 branches
| Branch | True | False | Total |
| if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
0 |
14 |
14 |
| if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
0 |
0 |
0 |
| if (e == 0 || e == EOPNOTSUPP || e == EINVAL) return 0; |
0 |
0 |
0 |
|
| 314 |
0 |
| errno = e; |
| 315 |
0 |
| return -1; |
| 316 |
|
| } |
| 317 |
|
| |
| 318 |
29 |
| static BsHandle *bs_create(const char *path, uint64_t capacity, mode_t mode, char *errbuf) { |
| 319 |
29 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
29 |
0 |
29 |
|
| 320 |
29 |
▶ | if (capacity == 0) { BS_ERR("capacity must be > 0"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity == 0) { BS_ERR("capacity must be > 0"); return NULL; } |
0 |
29 |
29 |
| if (capacity == 0) { BS_ERR("capacity must be > 0"); return NULL; } |
0 |
0 |
0 |
|
| 321 |
29 |
| uint32_t nw = (uint32_t)((capacity + 63) / 64); |
| 322 |
29 |
▶ | if (capacity > (uint64_t)(UINT32_MAX - 63) * 64) { BS_ERR("capacity too large"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity > (uint64_t)(UINT32_MAX - 63) * 64) { BS_ERR("capacity too large"); return NULL; } |
0 |
29 |
29 |
| if (capacity > (uint64_t)(UINT32_MAX - 63) * 64) { BS_ERR("capacity too large"); return NULL; } |
0 |
0 |
0 |
|
| 323 |
29 |
| uint64_t total = sizeof(BsHeader) + (uint64_t)nw * 8; |
| 324 |
|
| |
| 325 |
29 |
| int anonymous = (path == NULL); |
| 326 |
29 |
| int fd = -1; |
| 327 |
|
| size_t map_size; |
| 328 |
|
| void *base; |
| 329 |
|
| |
| 330 |
29 |
▶ | if (anonymous) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (anonymous) { |
15 |
14 |
29 |
|
| 331 |
15 |
| map_size = (size_t)total; |
| 332 |
15 |
| base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED|MAP_ANONYMOUS, -1, 0); |
| 333 |
15 |
▶ | if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
15 |
15 |
| if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 334 |
|
| } else { |
| 335 |
14 |
| fd = bs_secure_open(path, mode, errbuf); |
| 336 |
21 |
▶ | if (fd < 0) return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd < 0) return NULL; |
0 |
14 |
14 |
|
| 337 |
14 |
▶ | if (flock(fd, LOCK_EX) < 0) { BS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flock(fd, LOCK_EX) < 0) { BS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
0 |
14 |
14 |
| if (flock(fd, LOCK_EX) < 0) { BS_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 338 |
|
| struct stat st; |
| 339 |
14 |
▶ | if (fstat(fd, &st) < 0) { BS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fstat(fd, &st) < 0) { BS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
0 |
14 |
14 |
| if (fstat(fd, &st) < 0) { BS_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 340 |
14 |
| int is_new = (st.st_size == 0); |
| 341 |
14 |
▶ | if (!is_new && (uint64_t)st.st_size < sizeof(BsHeader)) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!is_new && (uint64_t)st.st_size < sizeof(BsHeader)) { |
8 |
6 |
14 |
| if (!is_new && (uint64_t)st.st_size < sizeof(BsHeader)) { |
0 |
8 |
8 |
|
| 342 |
0 |
▶ | BS_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
0 |
0 |
0 |
|
| 343 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 344 |
|
| } |
| 345 |
14 |
| int recover = 0; |
| 346 |
14 |
▶ | if (!is_new) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!is_new) { |
8 |
6 |
14 |
|
| 347 |
|
| uint32_t magic; |
| 348 |
|
| ssize_t n; |
| 349 |
8 |
▶ | do n = pread(fd, &magic, sizeof magic, 0); while (n < 0 && errno == EINTR); |
Branch: 2 branches
| Branch | True | False | Total |
| do n = pread(fd, &magic, sizeof magic, 0); while (n < 0 && errno == EINTR); |
0 |
8 |
8 |
| do n = pread(fd, &magic, sizeof magic, 0); while (n < 0 && errno == EINTR); |
0 |
0 |
0 |
|
| 350 |
8 |
▶ | if (n != (ssize_t)sizeof magic) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (n != (ssize_t)sizeof magic) { |
0 |
8 |
8 |
|
| 351 |
3 |
▶ | BS_ERR("invalid bitset file"); flock(fd, LOCK_UN); close(fd); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("invalid bitset file"); flock(fd, LOCK_UN); close(fd); return NULL; |
0 |
0 |
0 |
|
| 352 |
|
| } |
| 353 |
|
| /* Check abandoned files before mmap: even a read fault on a full tmpfs can SIGBUS. */ |
| 354 |
8 |
▶ | if (magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { |
Branch: 3 branches
| Branch | True | False | Total |
| if (magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { |
3 |
5 |
8 |
| if (magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { |
2 |
1 |
3 |
| if (magic == 0 && (uint64_t)st.st_size == total && st.st_uid == geteuid()) { |
2 |
0 |
2 |
|
| 355 |
2 |
▶ | if (!bs_file_is_zero(fd, total)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!bs_file_is_zero(fd, total)) { |
1 |
1 |
2 |
|
| 356 |
1 |
▶ | BS_ERR("%s: incomplete bitset file left by an interrupted create; remove it and retry", path); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: incomplete bitset file left by an interrupted create; remove it and retry", path); |
1 |
0 |
1 |
|
| 357 |
1 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 358 |
|
| } |
| 359 |
1 |
| recover = 1; |
| 360 |
6 |
▶ | } else if (magic != BS_MAGIC) { |
Branch: 1 branch
| Branch | True | False | Total |
| } else if (magic != BS_MAGIC) { |
2 |
4 |
6 |
|
| 361 |
2 |
▶ | BS_ERR("invalid bitset file"); flock(fd, LOCK_UN); close(fd); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("invalid bitset file"); flock(fd, LOCK_UN); close(fd); return NULL; |
2 |
0 |
2 |
|
| 362 |
|
| } |
| 363 |
|
| } |
| 364 |
11 |
▶ | if (is_new && st.st_uid != geteuid()) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (is_new && st.st_uid != geteuid()) { |
6 |
5 |
11 |
| if (is_new && st.st_uid != geteuid()) { |
0 |
6 |
6 |
|
| 365 |
0 |
▶ | BS_ERR("%s: refusing to initialize file not owned by us", path); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: refusing to initialize file not owned by us", path); |
0 |
0 |
0 |
|
| 366 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 367 |
|
| } |
| 368 |
11 |
▶ | if ((is_new || recover) && fchmod(fd, mode) < 0) { |
Branch: 3 branches
| Branch | True | False | Total |
| if ((is_new || recover) && fchmod(fd, mode) < 0) { |
5 |
6 |
11 |
| if ((is_new || recover) && fchmod(fd, mode) < 0) { |
1 |
4 |
5 |
| if ((is_new || recover) && fchmod(fd, mode) < 0) { |
0 |
7 |
7 |
|
| 369 |
0 |
▶ | BS_ERR("%s: fchmod: %s", path, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: fchmod: %s", path, strerror(errno)); |
0 |
0 |
0 |
|
| 370 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 371 |
|
| } |
| 372 |
11 |
▶ | if (is_new && ftruncate(fd, (off_t)total) < 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (is_new && ftruncate(fd, (off_t)total) < 0) { |
6 |
5 |
11 |
| if (is_new && ftruncate(fd, (off_t)total) < 0) { |
0 |
6 |
6 |
|
| 373 |
0 |
▶ | BS_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
0 |
0 |
0 |
|
| 374 |
|
| } |
| 375 |
11 |
▶ | if ((is_new || recover) && bs_reserve(fd, total) < 0) { |
Branch: 3 branches
| Branch | True | False | Total |
| if ((is_new || recover) && bs_reserve(fd, total) < 0) { |
5 |
6 |
11 |
| if ((is_new || recover) && bs_reserve(fd, total) < 0) { |
1 |
4 |
5 |
| if ((is_new || recover) && bs_reserve(fd, total) < 0) { |
0 |
7 |
7 |
|
| 376 |
0 |
▶ | BS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: cannot reserve %llu bytes: %s", path, (unsigned long long)total, strerror(errno)); |
0 |
0 |
0 |
|
| 377 |
0 |
▶ | if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } |
0 |
0 |
0 |
|
| 378 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 379 |
|
| } |
| 380 |
11 |
▶ | map_size = is_new ? (size_t)total : (size_t)st.st_size; |
Branch: 1 branch
| Branch | True | False | Total |
| map_size = is_new ? (size_t)total : (size_t)st.st_size; |
5 |
6 |
11 |
|
| 381 |
11 |
| base = mmap(NULL, map_size, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); |
| 382 |
11 |
▶ | if (base == MAP_FAILED) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (base == MAP_FAILED) { |
0 |
11 |
11 |
|
| 383 |
0 |
▶ | BS_ERR("mmap: %s", strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("mmap: %s", strerror(errno)); |
0 |
0 |
0 |
|
| 384 |
0 |
▶ | if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } |
Branch: 1 branch
| Branch | True | False | Total |
| if (is_new && ftruncate(fd, 0) < 0) { /* best effort */ } |
0 |
0 |
0 |
|
| 385 |
0 |
| flock(fd, LOCK_UN); close(fd); return NULL; |
| 386 |
|
| } |
| 387 |
11 |
▶ | if (!is_new && !recover) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (!is_new && !recover) { |
5 |
6 |
11 |
| if (!is_new && !recover) { |
4 |
1 |
5 |
|
| 388 |
4 |
▶ | if (!bs_validate_header((BsHeader *)base, (uint64_t)st.st_size)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!bs_validate_header((BsHeader *)base, (uint64_t)st.st_size)) { |
0 |
4 |
4 |
|
| 389 |
0 |
▶ | BS_ERR("invalid bitset file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("invalid bitset file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
0 |
0 |
0 |
|
| 390 |
|
| } |
| 391 |
4 |
▶ | if (((BsHeader *)base)->sealed) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (((BsHeader *)base)->sealed) { |
1 |
3 |
4 |
|
| 392 |
1 |
▶ | BS_ERR("%s is frozen (read-only); open it with new_readonly", path); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s is frozen (read-only); open it with new_readonly", path); |
1 |
0 |
1 |
|
| 393 |
1 |
| munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
| 394 |
|
| } |
| 395 |
3 |
| flock(fd, LOCK_UN); close(fd); |
| 396 |
3 |
| return bs_setup(base, map_size, path, -1); |
| 397 |
|
| } |
| 398 |
|
| } |
| 399 |
22 |
| bs_init_header(base, total, capacity, nw); |
| 400 |
22 |
▶ | if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
Branch: 1 branch
| Branch | True | False | Total |
| if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
7 |
15 |
22 |
|
| 401 |
22 |
| return bs_setup(base, map_size, path, -1); |
| 402 |
|
| } |
| 403 |
|
| |
| 404 |
7 |
| static BsHandle *bs_create_memfd(const char *name, uint64_t capacity, char *errbuf) { |
| 405 |
7 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
7 |
0 |
7 |
|
| 406 |
7 |
▶ | if (capacity == 0) { BS_ERR("capacity must be > 0"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity == 0) { BS_ERR("capacity must be > 0"); return NULL; } |
0 |
7 |
7 |
| if (capacity == 0) { BS_ERR("capacity must be > 0"); return NULL; } |
0 |
0 |
0 |
|
| 407 |
7 |
| uint32_t nw = (uint32_t)((capacity + 63) / 64); |
| 408 |
7 |
▶ | if (capacity > (uint64_t)(UINT32_MAX - 63) * 64) { BS_ERR("capacity too large"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (capacity > (uint64_t)(UINT32_MAX - 63) * 64) { BS_ERR("capacity too large"); return NULL; } |
0 |
7 |
7 |
| if (capacity > (uint64_t)(UINT32_MAX - 63) * 64) { BS_ERR("capacity too large"); return NULL; } |
0 |
0 |
0 |
|
| 409 |
7 |
| uint64_t total = sizeof(BsHeader) + (uint64_t)nw * 8; |
| 410 |
7 |
▶ | int fd = memfd_create(name ? name : "bitset", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
Branch: 1 branch
| Branch | True | False | Total |
| int fd = memfd_create(name ? name : "bitset", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
7 |
0 |
7 |
|
| 411 |
7 |
▶ | if (fd < 0) { BS_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fd < 0) { BS_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
0 |
7 |
7 |
| if (fd < 0) { BS_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 412 |
7 |
▶ | if (ftruncate(fd, (off_t)total) < 0) { BS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (ftruncate(fd, (off_t)total) < 0) { BS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } |
0 |
7 |
7 |
| if (ftruncate(fd, (off_t)total) < 0) { BS_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 413 |
7 |
▶ | if (bs_reserve(fd, total) < 0) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (bs_reserve(fd, total) < 0) { |
0 |
7 |
7 |
|
| 414 |
0 |
▶ | BS_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("memfd: cannot reserve %llu bytes: %s", (unsigned long long)total, strerror(errno)); |
0 |
0 |
0 |
|
| 415 |
0 |
| close(fd); return NULL; |
| 416 |
|
| } |
| 417 |
7 |
| (void)fcntl(fd, F_ADD_SEALS, F_SEAL_SHRINK | F_SEAL_GROW); |
| 418 |
7 |
| void *base = mmap(NULL, (size_t)total, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); |
| 419 |
7 |
▶ | if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
0 |
7 |
7 |
| if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 420 |
7 |
| bs_init_header(base, total, capacity, nw); |
| 421 |
7 |
| return bs_setup(base, (size_t)total, NULL, fd); |
| 422 |
|
| } |
| 423 |
|
| |
| 424 |
2 |
| static BsHandle *bs_open_fd(int fd, char *errbuf) { |
| 425 |
2 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
2 |
0 |
2 |
|
| 426 |
|
| struct stat st; |
| 427 |
2 |
▶ | if (fstat(fd, &st) < 0) { BS_ERR("fstat: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fstat(fd, &st) < 0) { BS_ERR("fstat: %s", strerror(errno)); return NULL; } |
0 |
2 |
2 |
| if (fstat(fd, &st) < 0) { BS_ERR("fstat: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 428 |
2 |
▶ | if ((uint64_t)st.st_size < sizeof(BsHeader)) { BS_ERR("too small"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if ((uint64_t)st.st_size < sizeof(BsHeader)) { BS_ERR("too small"); return NULL; } |
0 |
2 |
2 |
| if ((uint64_t)st.st_size < sizeof(BsHeader)) { BS_ERR("too small"); return NULL; } |
0 |
0 |
0 |
|
| 429 |
|
| /* before mmap: a creator may truncate the file until it has set magic */ |
| 430 |
|
| uint32_t magic; |
| 431 |
2 |
▶ | if (pread(fd, &magic, sizeof magic, offsetof(BsHeader, magic)) != (ssize_t)sizeof magic || magic != BS_MAGIC) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (pread(fd, &magic, sizeof magic, offsetof(BsHeader, magic)) != (ssize_t)sizeof magic || magic != BS_MAGIC) { |
2 |
0 |
2 |
| if (pread(fd, &magic, sizeof magic, offsetof(BsHeader, magic)) != (ssize_t)sizeof magic || magic != BS_MAGIC) { |
0 |
2 |
2 |
|
| 432 |
0 |
▶ | BS_ERR("invalid bitset"); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("invalid bitset"); return NULL; |
0 |
0 |
0 |
|
| 433 |
|
| } |
| 434 |
2 |
| size_t ms = (size_t)st.st_size; |
| 435 |
2 |
| void *base = mmap(NULL, ms, PROT_READ|PROT_WRITE, MAP_SHARED, fd, 0); |
| 436 |
2 |
▶ | if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
2 |
2 |
| if (base == MAP_FAILED) { BS_ERR("mmap: %s", strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 437 |
2 |
▶ | if (!bs_validate_header((BsHeader *)base, (uint64_t)st.st_size)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!bs_validate_header((BsHeader *)base, (uint64_t)st.st_size)) { |
0 |
2 |
2 |
|
| 438 |
0 |
▶ | BS_ERR("invalid bitset"); munmap(base, ms); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("invalid bitset"); munmap(base, ms); return NULL; |
0 |
0 |
0 |
|
| 439 |
|
| } |
| 440 |
2 |
▶ | if (((BsHeader *)base)->sealed) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (((BsHeader *)base)->sealed) { |
1 |
1 |
2 |
|
| 441 |
1 |
▶ | BS_ERR("this bitset is frozen (read-only); open it with new_readonly"); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("this bitset is frozen (read-only); open it with new_readonly"); |
1 |
0 |
1 |
|
| 442 |
1 |
| munmap(base, ms); return NULL; |
| 443 |
|
| } |
| 444 |
1 |
| int myfd = fcntl(fd, F_DUPFD_CLOEXEC, 0); |
| 445 |
1 |
▶ | if (myfd < 0) { BS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (myfd < 0) { BS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
0 |
1 |
1 |
| if (myfd < 0) { BS_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
0 |
0 |
0 |
|
| 446 |
1 |
| return bs_setup(base, ms, NULL, myfd); |
| 447 |
|
| } |
| 448 |
|
| |
| 449 |
36 |
| static void bs_destroy(BsHandle *h) { |
| 450 |
36 |
▶ | if (!h) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!h) return; |
0 |
36 |
36 |
|
| 451 |
36 |
▶ | if (h->backing_fd >= 0) close(h->backing_fd); |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->backing_fd >= 0) close(h->backing_fd); |
8 |
28 |
36 |
|
| 452 |
36 |
▶ | if (h->hdr) munmap(h->hdr, h->mmap_size); |
Branch: 1 branch
| Branch | True | False | Total |
| if (h->hdr) munmap(h->hdr, h->mmap_size); |
36 |
0 |
36 |
|
| 453 |
36 |
| free(h->path); |
| 454 |
36 |
| free(h); |
| 455 |
|
| } |
| 456 |
|
| |
| 457 |
1 |
| static int bs_msync(BsHandle *h) { return msync(h->hdr, h->mmap_size, MS_SYNC); } |
| 458 |
|
| |
| 459 |
|
| /* Open a FROZEN (sealed) file read-only: O_RDONLY + PROT_READ, no lock ever. |
| 460 |
|
| * A sealed file is immutable and no read path writes the mapping, so queries |
| 461 |
|
| * take no reader-slot / rwlock traffic and any number of processes can share |
| 462 |
|
| * one PROT_READ mapping (same architecture; the magic rejects a wrong-endian |
| 463 |
|
| * file). */ |
| 464 |
5 |
| static BsHandle *bs_open_readonly(const char *path, char *errbuf) { |
| 465 |
5 |
▶ | if (errbuf) errbuf[0] = '\0'; |
Branch: 1 branch
| Branch | True | False | Total |
| if (errbuf) errbuf[0] = '\0'; |
5 |
0 |
5 |
|
| 466 |
5 |
| int fd = open(path, O_RDONLY|O_NOFOLLOW|O_CLOEXEC); |
| 467 |
5 |
▶ | if (fd < 0) { BS_ERR("open %s: %s", path, strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fd < 0) { BS_ERR("open %s: %s", path, strerror(errno)); return NULL; } |
1 |
4 |
5 |
| if (fd < 0) { BS_ERR("open %s: %s", path, strerror(errno)); return NULL; } |
1 |
0 |
1 |
|
| 468 |
|
| struct stat st; |
| 469 |
4 |
▶ | if (fstat(fd, &st) < 0) { BS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (fstat(fd, &st) < 0) { BS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } |
0 |
4 |
4 |
| if (fstat(fd, &st) < 0) { BS_ERR("fstat %s: %s", path, strerror(errno)); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 470 |
4 |
▶ | if ((uint64_t)st.st_size < sizeof(BsHeader)) { BS_ERR("%s: file too small", path); close(fd); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if ((uint64_t)st.st_size < sizeof(BsHeader)) { BS_ERR("%s: file too small", path); close(fd); return NULL; } |
0 |
4 |
4 |
| if ((uint64_t)st.st_size < sizeof(BsHeader)) { BS_ERR("%s: file too small", path); close(fd); return NULL; } |
0 |
0 |
0 |
|
| 471 |
|
| /* before mmap: a creator may truncate the file until it has set magic */ |
| 472 |
|
| uint32_t magic; |
| 473 |
4 |
▶ | if (pread(fd, &magic, sizeof magic, offsetof(BsHeader, magic)) != (ssize_t)sizeof magic || magic != BS_MAGIC) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (pread(fd, &magic, sizeof magic, offsetof(BsHeader, magic)) != (ssize_t)sizeof magic || magic != BS_MAGIC) { |
4 |
0 |
4 |
| if (pread(fd, &magic, sizeof magic, offsetof(BsHeader, magic)) != (ssize_t)sizeof magic || magic != BS_MAGIC) { |
0 |
4 |
4 |
|
| 474 |
0 |
▶ | BS_ERR("%s: invalid bitset file", path); close(fd); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: invalid bitset file", path); close(fd); return NULL; |
0 |
0 |
0 |
|
| 475 |
|
| } |
| 476 |
4 |
| size_t ms = (size_t)st.st_size; |
| 477 |
4 |
| void *base = mmap(NULL, ms, PROT_READ, MAP_SHARED, fd, 0); |
| 478 |
4 |
| close(fd); /* the mapping keeps the file; a read-only view needs no fd (no msync/ftruncate) */ |
| 479 |
4 |
▶ | if (base == MAP_FAILED) { BS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (base == MAP_FAILED) { BS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } |
0 |
4 |
4 |
| if (base == MAP_FAILED) { BS_ERR("mmap %s: %s", path, strerror(errno)); return NULL; } |
0 |
0 |
0 |
|
| 480 |
4 |
▶ | if (!bs_validate_header((BsHeader *)base, (uint64_t)st.st_size)) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!bs_validate_header((BsHeader *)base, (uint64_t)st.st_size)) { |
0 |
4 |
4 |
|
| 481 |
0 |
▶ | BS_ERR("%s: invalid bitset file", path); munmap(base, ms); return NULL; |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s: invalid bitset file", path); munmap(base, ms); return NULL; |
0 |
0 |
0 |
|
| 482 |
|
| } |
| 483 |
4 |
▶ | if (!((BsHeader *)base)->sealed) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!((BsHeader *)base)->sealed) { |
1 |
3 |
4 |
|
| 484 |
1 |
▶ | BS_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); |
Branch: 1 branch
| Branch | True | False | Total |
| BS_ERR("%s is not frozen: call ->freeze on the producer before opening read-only", path); |
1 |
0 |
1 |
|
| 485 |
1 |
| munmap(base, ms); return NULL; |
| 486 |
|
| } |
| 487 |
3 |
| BsHandle *h = bs_setup(base, ms, path, -1); /* munmaps on OOM */ |
| 488 |
3 |
▶ | if (!h) { BS_ERR("out of memory"); return NULL; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (!h) { BS_ERR("out of memory"); return NULL; } |
0 |
3 |
3 |
| if (!h) { BS_ERR("out of memory"); return NULL; } |
0 |
0 |
0 |
|
| 489 |
3 |
| h->readonly = 1; |
| 490 |
3 |
| return h; |
| 491 |
|
| } |
| 492 |
|
| |
| 493 |
|
| /* Writers must be quiescent before publishing and flushing the seal. */ |
| 494 |
11 |
| static int bs_freeze(BsHandle *h) { |
| 495 |
11 |
| __atomic_store_n(&h->hdr->sealed, 1, __ATOMIC_RELEASE); |
| 496 |
11 |
▶ | if (h->path || h->backing_fd >= 0) return bs_msync(h); /* durability for file/memfd-backed */ |
Branch: 2 branches
| Branch | True | False | Total |
| if (h->path || h->backing_fd >= 0) return bs_msync(h); /* durability for file/memfd-backed */ |
10 |
1 |
11 |
| if (h->path || h->backing_fd >= 0) return bs_msync(h); /* durability for file/memfd-backed */ |
0 |
10 |
10 |
|
| 497 |
10 |
| return 0; /* anonymous: the seal lives in shared memory (visible to forks); nothing to flush */ |
| 498 |
|
| } |
| 499 |
|
| |
| 500 |
|
| #endif /* BITSET_H */ |