| line |
true |
false |
branch |
|
145
|
0 |
0 |
if (pid == 0) return 1; /* no owner recorded, assume alive */ |
|
146
|
0 |
0 |
return !(kill((pid_t)pid, 0) == -1 && errno == ESRCH); |
|
|
0 |
0 |
return !(kill((pid_t)pid, 0) == -1 && errno == ESRCH); |
|
156
|
0 |
0 |
if (!__atomic_compare_exchange_n(&hdr->rwlock, &observed_rwlock, |
|
162
|
0 |
0 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
186
|
52656 |
18 |
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) |
|
|
52656 |
0 |
if (__builtin_expect(cur_gen == h->cached_fork_gen && h->my_slot_idx != UINT32_MAX, 1)) |
|
197
|
20 |
0 |
for (uint32_t i = 0; i < CF_READER_SLOTS; i++) { |
|
200
|
18 |
2 |
if (__atomic_compare_exchange_n(&h->reader_slots[s].pid, |
|
220
|
0 |
0 |
if (!sub) return; |
|
223
|
0 |
0 |
uint32_t want = (cur > sub) ? cur - sub : 0; |
|
224
|
0 |
0 |
if (__atomic_compare_exchange_n(p, &cur, want, |
|
247
|
0 |
0 |
if (!__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, 0, |
|
252
|
0 |
0 |
if (wp) cf_atomic_sub_cap(&hdr->rwlock_waiters, wp); |
|
253
|
0 |
0 |
if (writp) cf_atomic_sub_cap(&hdr->rwlock_writers_waiting, writp); |
|
267
|
0 |
0 |
if (!h->reader_slots) return; |
|
280
|
0 |
0 |
for (uint32_t i = 0; i < CF_READER_SLOTS; i++) { |
|
282
|
0 |
0 |
if (pid == 0) continue; |
|
284
|
0 |
0 |
if (cf_pid_alive(pid)) { |
|
285
|
0 |
0 |
if (sc > 0) any_live_reader = 1; |
|
288
|
0 |
0 |
if (sc > 0) { found_dead_reader = 1; continue; } |
|
305
|
0 |
0 |
if (found_dead_reader && !any_live_reader) { |
|
|
0 |
0 |
if (found_dead_reader && !any_live_reader) { |
|
307
|
0 |
0 |
if (cur > 0 && cur < CF_RWLOCK_WRITER_BIT) { |
|
|
0 |
0 |
if (cur > 0 && cur < CF_RWLOCK_WRITER_BIT) { |
|
308
|
0 |
0 |
if (__atomic_compare_exchange_n(&hdr->rwlock, &cur, 0, |
|
310
|
0 |
0 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
314
|
0 |
0 |
for (uint32_t i = 0; i < CF_READER_SLOTS; i++) { |
|
316
|
0 |
0 |
if (pid == 0 || cf_pid_alive(pid)) continue; |
|
|
0 |
0 |
if (pid == 0 || cf_pid_alive(pid)) continue; |
|
329
|
0 |
0 |
if (val >= CF_RWLOCK_WRITER_BIT) { |
|
331
|
0 |
0 |
if (!cf_pid_alive(pid)) |
|
343
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
349
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
353
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) { |
|
363
|
0 |
0 |
if (h->my_slot_idx != UINT32_MAX) { |
|
381
|
26841 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
388
|
0 |
26841 |
if (cur > 0 && cur < CF_RWLOCK_WRITER_BIT) { |
|
|
0 |
0 |
if (cur > 0 && cur < CF_RWLOCK_WRITER_BIT) { |
|
389
|
0 |
0 |
if (__atomic_compare_exchange_n(lock, &cur, cur + 1, |
|
392
|
26841 |
0 |
} else if (cur == 0 && !__atomic_load_n(writers_waiting, __ATOMIC_RELAXED)) { |
|
|
26841 |
0 |
} else if (cur == 0 && !__atomic_load_n(writers_waiting, __ATOMIC_RELAXED)) { |
|
393
|
26841 |
0 |
if (__atomic_compare_exchange_n(lock, &cur, 1, |
|
397
|
0 |
0 |
if (__builtin_expect(spin < CF_RWLOCK_SPIN_LIMIT, 1)) { |
|
404
|
0 |
0 |
if (cur >= CF_RWLOCK_WRITER_BIT || cur == 0) { |
|
|
0 |
0 |
if (cur >= CF_RWLOCK_WRITER_BIT || cur == 0) { |
|
407
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
427
|
26841 |
0 |
if (h->my_slot_idx != UINT32_MAX) |
|
429
|
26841 |
0 |
if (after == 0 && __atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
|
0 |
26841 |
if (after == 0 && __atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
442
|
25833 |
0 |
if (__atomic_compare_exchange_n(lock, &expected, mypid, |
|
445
|
0 |
0 |
if (__builtin_expect(spin < CF_RWLOCK_SPIN_LIMIT, 1)) { |
|
451
|
0 |
0 |
if (cur != 0) { |
|
454
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
|
0 |
0 |
if (rc == -1 && errno == ETIMEDOUT) { |
|
469
|
0 |
25833 |
if (__atomic_load_n(&hdr->rwlock_waiters, __ATOMIC_RELAXED) > 0) |
|
498
|
1 |
21 |
if (v <= CF_MIN_BUCKETS) return CF_MIN_BUCKETS; |
|
517
|
0 |
20 |
if (hdr->rng_state == 0) hdr->rng_state = 1; |
|
532
|
0 |
22 |
if (!h) { |
|
534
|
0 |
0 |
if (backing_fd >= 0) close(backing_fd); |
|
541
|
4 |
18 |
h->path = path ? strdup(path) : NULL; |
|
549
|
0 |
2 |
if (hdr->magic != CF_MAGIC) return 0; |
|
550
|
0 |
2 |
if (hdr->version != CF_VERSION) return 0; |
|
551
|
2 |
0 |
if (hdr->num_buckets < CF_MIN_BUCKETS || hdr->num_buckets > CF_MAX_BUCKETS) return 0; |
|
|
0 |
2 |
if (hdr->num_buckets < CF_MIN_BUCKETS || hdr->num_buckets > CF_MAX_BUCKETS) return 0; |
|
552
|
0 |
2 |
if ((hdr->num_buckets & (hdr->num_buckets - 1)) != 0) return 0; /* power of two */ |
|
553
|
0 |
2 |
if (hdr->bucket_mask != hdr->num_buckets - 1) return 0; |
|
554
|
0 |
2 |
if (hdr->capacity == 0) return 0; |
|
555
|
0 |
2 |
if (hdr->rng_state == 0) return 0; |
|
556
|
0 |
2 |
if (hdr->count > hdr->num_buckets * (uint64_t)CF_SLOTS) return 0; |
|
557
|
0 |
2 |
if (hdr->total_size != file_size) return 0; |
|
558
|
0 |
2 |
if (hdr->total_size != cf_total_size(hdr->num_buckets)) return 0; |
|
560
|
0 |
2 |
if (hdr->reader_slots_off != L.reader_slots) return 0; |
|
561
|
0 |
2 |
if (hdr->slots_off != L.slots) return 0; |
|
568
|
23 |
0 |
if (errbuf) errbuf[0] = '\0'; |
|
569
|
0 |
23 |
if (capacity < 1) { CF_ERR("capacity must be >= 1"); return 0; } |
|
|
0 |
0 |
if (capacity < 1) { CF_ERR("capacity must be >= 1"); return 0; } |
|
576
|
1 |
22 |
if (want_d > (double)CF_MAX_BUCKETS) { CF_ERR("capacity too large for the bucket cap"); return 0; } |
|
|
1 |
0 |
if (want_d > (double)CF_MAX_BUCKETS) { CF_ERR("capacity too large for the bucket cap"); return 0; } |
|
585
|
1 |
20 |
if (!cf_validate_create_args(capacity, &num_buckets, errbuf)) return NULL; |
|
593
|
15 |
5 |
if (anonymous) { |
|
596
|
0 |
15 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
599
|
0 |
5 |
if (fd < 0) { CF_ERR("open: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fd < 0) { CF_ERR("open: %s", strerror(errno)); return NULL; } |
|
600
|
0 |
5 |
if (flock(fd, LOCK_EX) < 0) { CF_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
|
|
0 |
0 |
if (flock(fd, LOCK_EX) < 0) { CF_ERR("flock: %s", strerror(errno)); close(fd); return NULL; } |
|
602
|
0 |
5 |
if (fstat(fd, &st) < 0) { CF_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
|
0 |
0 |
if (fstat(fd, &st) < 0) { CF_ERR("fstat: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
604
|
2 |
3 |
if (!is_new && (uint64_t)st.st_size < sizeof(CfHeader)) { |
|
|
1 |
1 |
if (!is_new && (uint64_t)st.st_size < sizeof(CfHeader)) { |
|
605
|
1 |
0 |
CF_ERR("%s: file too small (%lld)", path, (long long)st.st_size); |
|
608
|
3 |
1 |
if (is_new && ftruncate(fd, (off_t)total) < 0) { |
|
|
0 |
3 |
if (is_new && ftruncate(fd, (off_t)total) < 0) { |
|
609
|
0 |
0 |
CF_ERR("ftruncate: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; |
|
611
|
1 |
3 |
map_size = is_new ? (size_t)total : (size_t)st.st_size; |
|
613
|
0 |
4 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); flock(fd, LOCK_UN); close(fd); return NULL; } |
|
614
|
1 |
3 |
if (!is_new) { |
|
615
|
0 |
1 |
if (!cf_validate_header((CfHeader *)base, (uint64_t)st.st_size)) { |
|
616
|
0 |
0 |
CF_ERR("invalid Cuckoo filter file"); munmap(base, map_size); flock(fd, LOCK_UN); close(fd); return NULL; |
|
623
|
3 |
15 |
if (fd >= 0) { flock(fd, LOCK_UN); close(fd); } |
|
629
|
0 |
2 |
if (!cf_validate_create_args(capacity, &num_buckets, errbuf)) return NULL; |
|
632
|
1 |
1 |
int fd = memfd_create(name ? name : "cuckoo", MFD_CLOEXEC | MFD_ALLOW_SEALING); |
|
633
|
0 |
2 |
if (fd < 0) { CF_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fd < 0) { CF_ERR("memfd_create: %s", strerror(errno)); return NULL; } |
|
634
|
0 |
2 |
if (ftruncate(fd, (off_t)total) < 0) { |
|
635
|
0 |
0 |
CF_ERR("ftruncate: %s", strerror(errno)); close(fd); return NULL; |
|
639
|
0 |
2 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); close(fd); return NULL; } |
|
645
|
2 |
0 |
if (errbuf) errbuf[0] = '\0'; |
|
647
|
0 |
2 |
if (fstat(fd, &st) < 0) { CF_ERR("fstat: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (fstat(fd, &st) < 0) { CF_ERR("fstat: %s", strerror(errno)); return NULL; } |
|
648
|
1 |
1 |
if ((uint64_t)st.st_size < sizeof(CfHeader)) { CF_ERR("too small"); return NULL; } |
|
|
1 |
0 |
if ((uint64_t)st.st_size < sizeof(CfHeader)) { CF_ERR("too small"); return NULL; } |
|
651
|
0 |
1 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
|
0 |
0 |
if (base == MAP_FAILED) { CF_ERR("mmap: %s", strerror(errno)); return NULL; } |
|
652
|
0 |
1 |
if (!cf_validate_header((CfHeader *)base, (uint64_t)st.st_size)) { |
|
653
|
0 |
0 |
CF_ERR("invalid Cuckoo filter table"); munmap(base, ms); return NULL; |
|
656
|
0 |
1 |
if (myfd < 0) { CF_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
|
|
0 |
0 |
if (myfd < 0) { CF_ERR("fcntl: %s", strerror(errno)); munmap(base, ms); return NULL; } |
|
661
|
0 |
22 |
if (!h) return; |
|
662
|
3 |
19 |
if (h->backing_fd >= 0) close(h->backing_fd); |
|
663
|
22 |
0 |
if (h->base) munmap(h->base, h->mmap_size); |
|
669
|
2 |
0 |
if (!h || !h->base) return 0; |
|
|
0 |
2 |
if (!h || !h->base) return 0; |
|
704
|
35 |
64180 |
if (fh == 0) fh = 1; |
|
716
|
143035 |
26868 |
for (int j = 0; j < CF_SLOTS; j++) |
|
717
|
18324 |
124711 |
if (b[j] == fp) return j; |
|
724
|
83809 |
7776 |
for (int j = 0; j < CF_SLOTS; j++) { |
|
725
|
27321 |
56488 |
if (b[j] == 0) { b[j] = fp; return 1; } |
|
735
|
0 |
58152 |
if (fp == 0) fp = 1; /* 0 means empty slot; never use it */ |
|
753
|
1712 |
25610 |
if (cf_bucket_insert(h, i1, fp) || cf_bucket_insert(h, i2, fp)) { |
|
|
1274 |
438 |
if (cf_bucket_insert(h, i1, fp) || cf_bucket_insert(h, i2, fp)) { |
|
762
|
226 |
212 |
uint64_t i = (cf_rng_next(h) & 1) ? i1 : i2; |
|
764
|
6063 |
1 |
for (int n = 0; n < CF_MAX_KICKS; n++) { |
|
772
|
437 |
5626 |
if (cf_bucket_insert(h, i, carried)) { /* free slot in the new bucket? */ |
|
779
|
500 |
1 |
for (int n = CF_MAX_KICKS - 1; n >= 0; n--) { |
|
792
|
14157 |
12668 |
return cf_bucket_find(h, i1, fp) >= 0 || cf_bucket_find(h, i2, fp) >= 0; |
|
|
1653 |
12504 |
return cf_bucket_find(h, i1, fp) >= 0 || cf_bucket_find(h, i2, fp) >= 0; |
|
804
|
3800 |
205 |
if (j >= 0) { cf_bucket(h, i1)[j] = 0; h->hdr->count--; return 1; } |
|
806
|
203 |
2 |
if (j >= 0) { cf_bucket(h, i2)[j] = 0; h->hdr->count--; return 1; } |