Data-KDTree-Shared
view release on metacpan or search on metacpan
#else
__asm__ volatile("" ::: "memory");
#endif
}
/* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
#define KD_RWLOCK_WRITER_BIT 0x80000000U
#define KD_RWLOCK_PID_MASK 0x7FFFFFFFU
#define KD_RWLOCK_WR(pid) (KD_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & KD_RWLOCK_PID_MASK))
/* A zombie (dead but not yet reaped) still answers kill(pid,0) as alive, so a
* process that crashed while holding the lock and lingers unreaped would never
* be recovered. Treat /proc/<pid>/stat state 'Z' as dead. Linux-only (as is
* this module); if /proc is unreadable we fall back to "alive" (safe: we never
* force-recover a possibly-live holder). */
static inline int kd_pid_is_zombie(uint32_t pid) {
char path[32], buf[256];
snprintf(path, sizeof(path), "/proc/%u/stat", (unsigned)pid);
int fd = open(path, O_RDONLY | O_CLOEXEC);
if (fd < 0) return 0;
ssize_t n = read(fd, buf, sizeof(buf) - 1);
close(fd);
if (n <= 0) return 0;
buf[n] = '\0';
/* "pid (comm) state ..."; comm may contain ')', so scan to the last one. */
char *rp = strrchr(buf, ')');
if (!rp || rp + 2 >= buf + n) return 0; /* need ") X" within the bytes read */
return rp[1] == ' ' && rp[2] == 'Z';
}
/* 1 if alive or unknown, 0 if definitely dead. Cannot detect PID reuse: a
* recycled PID reports "alive" and the slot is not reclaimed until that
* process exits. See "Crash Safety" in the POD. */
static inline int kd_pid_alive(uint32_t pid) {
if (pid == 0) return 1; /* no owner recorded, assume alive */
if (kill((pid_t)pid, 0) == -1 && errno == ESRCH) return 0; /* definitely dead */
return !kd_pid_is_zombie(pid); /* kill() also succeeds for a zombie -> treat as dead */
}
/* Force-recover a stale WRITE lock left by a dead writer (held or mid-drain).
* CAS to OUR pid to hold the lock while fixing shared state, then release.
* Using our pid (not a bare WRITER_BIT sentinel) means a subsequent recovering
* process can detect and re-recover if we crash mid-recovery. */
static inline void kd_recover_stale_lock(KdHandle *h, uint32_t observed_wlock) {
KdHeader *hdr = h->hdr;
h->my_slot_idx = s;
return;
}
}
/* Pass 2: no free slot -- reclaim one whose owner is dead. Safe to take even
* if its rdepth>0: clearing pid drops the dead reader's entire contribution
* (a writer scan ignores rdepth when pid==0) and we reset rdepth to 0 as we
* claim it. */
for (uint32_t i = 0; i < KD_READER_SLOTS; i++) {
uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
if (dpid == 0 || dpid == now_pid || kd_pid_alive(dpid)) continue;
uint32_t expected = dpid;
if (__atomic_compare_exchange_n(&h->reader_slots[i].pid, &expected, now_pid, 0,
__ATOMIC_ACQUIRE, __ATOMIC_RELAXED)) {
__atomic_store_n(&h->reader_slots[i].rdepth, 0, __ATOMIC_RELAXED);
kd_occ_set(h, i);
h->my_slot_idx = i;
return;
}
}
/* Table full -- leave my_slot_idx = UINT32_MAX so this handle takes the
* documented slotless limitation). */
}
/* Inspect the writer word after a futex-wait timeout. If a dead writer holds
* it, force-recover. Dead READERS need no action here: only a writer that owns
* wlock drains readers, and it clears dead readers inline in its own scan. */
static inline void kd_recover_after_timeout(KdHandle *h) {
uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
if (val >= KD_RWLOCK_WRITER_BIT) {
uint32_t pid = val & KD_RWLOCK_PID_MASK;
if (!kd_pid_alive(pid))
kd_recover_stale_lock(h, val);
}
}
/* Bump/drop the parked-waiter hint. Both readers (blocked at the gate) and
* writers (blocked acquiring wlock) wait on the wlock futex and use this, so
* wrunlock/recover know whether a FUTEX_WAKE is worth a syscall. A waiter
* SIGKILLed while parked leaves rwait over-counted -> at most a spurious wake
* (harmless); it can never under-count, so no wakeup is lost. */
static inline void kd_park(KdHandle *h) {
if (__atomic_load_n(&hdr->wlock, __ATOMIC_SEQ_CST) == 0)
return; /* no writer after our publish -> we hold the read lock */
/* A writer appeared during our publish -- yield to it (write-preferring). */
kd_rdepth_dec(h);
kd_reader_wake_drain(h); /* let the draining writer see rdepth drop */
spin = 0;
continue;
}
/* wlock != 0: a writer holds or is acquiring. Recover if it is dead. */
if (cur >= KD_RWLOCK_WRITER_BIT &&
!kd_pid_alive(cur & KD_RWLOCK_PID_MASK)) {
kd_recover_stale_lock(h, cur);
spin = 0;
continue;
}
if (__builtin_expect(spin < KD_RWLOCK_SPIN_LIMIT, 1)) {
kd_rwlock_spin_pause();
continue;
}
kd_park(h);
cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
* crash window between acquiring the lock and storing the owner. */
uint32_t mypid = KD_RWLOCK_WR(h->cached_pid);
/* Phase 1: acquire the writer word (mutual exclusion among writers). */
for (int spin = 0; ; spin++) {
uint32_t expected = 0;
if (__atomic_compare_exchange_n(&hdr->wlock, &expected, mypid,
0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
break;
/* Contended: expected now holds the current wlock value. */
if (expected >= KD_RWLOCK_WRITER_BIT &&
!kd_pid_alive(expected & KD_RWLOCK_PID_MASK)) {
kd_recover_stale_lock(h, expected);
spin = 0;
continue;
}
if (__builtin_expect(spin < KD_RWLOCK_SPIN_LIMIT, 1)) {
kd_rwlock_spin_pause();
continue;
}
kd_park(h);
uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
* instead of O(KD_READER_SLOTS). */
for (uint32_t w = 0; w < KD_OCC_WORDS; w++) {
uint64_t word = __atomic_load_n(&h->occ[w], __ATOMIC_SEQ_CST);
while (word) {
uint32_t i = (w << 6) + (uint32_t)__builtin_ctzll(word);
word &= word - 1; /* consume this bit (local copy) */
uint32_t rd = __atomic_load_n(&h->reader_slots[i].rdepth, __ATOMIC_SEQ_CST);
if (rd == 0) continue; /* occupied but not read-locking now */
uint32_t pid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
if (pid == 0) continue; /* stale rdepth on a freed slot */
if (!kd_pid_alive(pid)) {
/* Dead reader: drop its pid so the slot no longer counts. Leave
* the occ bit set (harmless -- a later scan hits pid==0 and skips,
* a re-claim re-sets it) to avoid racing a concurrent claimant. */
uint32_t ep = pid;
__atomic_compare_exchange_n(&h->reader_slots[i].pid, &ep, 0,
0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED);
continue;
}
busy = 1; /* live reader still holding */
}
xt/destroy_during_call.t view on Meta::CPAN
use strict;
use warnings;
use Test::More;
use Config;
use POSIX ();
use Data::KDTree::Shared;
plan skip_all => 'fork required' unless $Config{d_fork};
our $victim;
our $groom; # keeps the realloc tree alive so its handle is not re-freed
# tied array whose FETCHSIZE (reached via av_len) destroys the tree
{ package Tied::Destroy;
sub TIEARRAY { bless { obj => $_[1] }, $_[0] }
sub FETCHSIZE { $_[0]{obj}->DESTROY; 2 }
sub FETCH { 1.0 }
}
# tied array whose FETCHSIZE destroys the tree AND grooms the freed handle:
# a fresh dims=3 tree calloc's the same-sized KdHandle chunk (tcache LIFO), so a
# stale h->dims read sees 3 and kd_read_point(hi) dies with the WRONG message --
( run in 1.393 second using v1.01-cache-2.11-cpan-14f38c9f855 )