Data-SegmentTree-Shared
view release on metacpan or search on metacpan
"monoids_valid" reports whether "gcd"/"product" are currently usable
(false once a "range_add"/"add" has gated them off). "clear" resets every
position to 0 and re-enables the monoids. "sync" flushes the mapping to
its backing store (a no-op for anonymous and memfd trees); "unlink"
removes the backing file (also callable as "Class->unlink($path)"); "path"
returns the backing path ("undef" for anonymous, memfd, or fd-reopened
trees) and "memfd" the backing descriptor. The descriptor "memfd" returns
is owned by the object and closed when the object is destroyed; do not
close it yourself. Pass it to another process (or "new_from_fd") while the
object is still alive.
SHARING ACROSS PROCESSES
The tree lives in a shared mapping, exposed the same three ways as the
rest of the family: a backing file, an anonymous mapping inherited across
"fork", or a memfd passed to an unrelated process and reopened with
new_from_fd($fd). The descriptor you pass is duplicated
("F_DUPFD_CLOEXEC"), so it stays yours to close and closing it does not
disturb the handle. Every process's updates land in the one shared array,
and queries take only the read lock so many readers proceed concurrently.
lib/Data/SegmentTree/Shared.pm view on Meta::CPAN
$st->path; $st->memfd; $st->sync; $st->unlink;
C<monoids_valid> reports whether C<gcd>/C<product> are currently usable (false once
a C<range_add>/C<add> has gated them off). C<clear> resets every position to 0 and
re-enables the monoids. C<sync> flushes the mapping to its backing
store (a no-op for anonymous and memfd trees); C<unlink> removes the backing file
(also callable as C<< Class->unlink($path) >>); C<path> returns the backing path
(C<undef> for anonymous, memfd, or fd-reopened trees) and C<memfd> the backing
descriptor. The descriptor C<memfd> returns is B<owned by the object> and closed
when the object is destroyed; do not close it yourself. Pass it to another process
(or C<new_from_fd>) while the object is still alive.
=head1 SHARING ACROSS PROCESSES
The tree lives in a shared mapping, exposed the same three ways as the rest of
the family: a B<backing file>, an B<anonymous mapping inherited across
C<fork>>, or a B<memfd> passed to an unrelated process and reopened with C<<
new_from_fd($fd) >>. The descriptor you pass is duplicated
(C<F_DUPFD_CLOEXEC>), so it stays yours to close and closing it does not
disturb the handle. Every process's updates land in the one shared array, and
queries take only the read lock so many readers proceed concurrently.
#else
__asm__ volatile("" ::: "memory");
#endif
}
/* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
#define ST_RWLOCK_WRITER_BIT 0x80000000U
#define ST_RWLOCK_PID_MASK 0x7FFFFFFFU
#define ST_RWLOCK_WR(pid) (ST_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & ST_RWLOCK_PID_MASK))
/* A zombie (dead, unreaped) still answers kill(pid,0) as alive, so a crashed
* lock-holder that lingers unreaped would never be recovered. Treat
* /proc/<pid>/stat state 'Z' as dead. Linux-only; if /proc is unreadable,
* fall back to "alive" (never force-recover a possibly-live holder). */
static inline int st_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 st_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 !st_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 st_recover_stale_lock(StHandle *h, uint32_t observed_wlock) {
StHeader *hdr = h->hdr;
return;
}
}
/* Pass 2: no free slot -- reclaim one whose owner is dead. Safe 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. No orphaned shared counter exists, so dead slots need not be
* skipped even if they still show a read count. */
for (uint32_t i = 0; i < ST_READER_SLOTS; i++) {
uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
if (dpid == 0 || dpid == now_pid || st_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);
st_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 st_recover_after_timeout(StHandle *h) {
uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
if (val >= ST_RWLOCK_WRITER_BIT) {
uint32_t pid = val & ST_RWLOCK_PID_MASK;
if (!st_pid_alive(pid))
st_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 st_park(StHandle *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). */
st_rdepth_dec(h);
st_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 >= ST_RWLOCK_WRITER_BIT &&
!st_pid_alive(cur & ST_RWLOCK_PID_MASK)) {
st_recover_stale_lock(h, cur);
spin = 0;
continue;
}
if (__builtin_expect(spin < ST_RWLOCK_SPIN_LIMIT, 1)) {
st_rwlock_spin_pause();
continue;
}
st_park(h);
cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
* crash window between acquiring the lock and storing the owner. */
uint32_t mypid = ST_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 >= ST_RWLOCK_WRITER_BIT &&
!st_pid_alive(expected & ST_RWLOCK_PID_MASK)) {
st_recover_stale_lock(h, expected);
spin = 0;
continue;
}
if (__builtin_expect(spin < ST_RWLOCK_SPIN_LIMIT, 1)) {
st_rwlock_spin_pause();
continue;
}
st_park(h);
uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
* instead of O(ST_READER_SLOTS). */
for (uint32_t w = 0; w < ST_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 (!st_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 */
}
( run in 1.956 second using v1.01-cache-2.11-cpan-14f38c9f855 )