Data-SpatialHash-Shared
view release on metacpan or search on metacpan
file left behind by an interrupted create is re-initialized (see "CRASH
SAFETY"); a file already in use keeps its own permissions. The file is
opened with "O_NOFOLLOW", so a symlink planted at the path is refused, and
created with "O_EXCL"; the on-disk header is validated when the file is
attached. Any process you grant write access to a shared mapping is
trusted not to corrupt its contents while other processes are using it.
CRASH SAFETY
The write lock is a futex-based rwlock with PID-encoded ownership. If the
writer process dies while holding the lock, the next writer that cannot
acquire the lock checks whether the owner PID is still alive and, if not,
recovers the lock. Reader slots are similarly reclaimed when a dead
reader's slot is detected.
Limitation: PID reuse is not detected. If a new process acquires the same
PID as a dead lock holder before recovery runs, the stale lock may not be
released automatically. This edge case requires the kernel to reassign
PIDs faster than lock-recovery attempts, which is very unlikely in
practice but cannot be ruled out.
Reader-slot exhaustion (slotless readers): dead-process recovery
eg/memfd_share.pl view on Meta::CPAN
unless (-d '/proc/self/fd') { print "needs Linux /proc\n"; exit 0 }
pipe(my $R, my $W) or die "pipe: $!";
my $pid = fork // die "fork: $!";
if (!$pid) { # producer
close $R;
my $s = Data::SpatialHash::Shared->new_memfd('shared-index', 1000, 0, 1.0);
$s->insert(rand()*100, rand()*100, $_) for 1 .. 50;
syswrite $W, $$ . ' ' . $s->memfd . "\n";
select undef, undef, undef, 2; # stay alive while the consumer attaches
exit 0;
}
close $W;
my ($cpid, $cfd) = split ' ', scalar(<$R>);
open my $fh, '+<', "/proc/$cpid/fd/$cfd" or die "attach: $!";
my $idx = Data::SpatialHash::Shared->new_from_fd(fileno $fh);
my @near = $idx->query_radius(50, 50, 20);
printf "consumer attached to producer's memfd: %d points, %d near (50,50)\n",
$idx->count, scalar @near;
kill 'TERM', $cpid; waitpid $cpid, 0;
lib/Data/SpatialHash/Shared.pm view on Meta::CPAN
SAFETY>); a file already in use keeps its own permissions. The file is opened
with C<O_NOFOLLOW>, so a symlink planted at the path is refused, and created
with C<O_EXCL>; the on-disk header is validated when the file is attached. Any
process you grant write access to a shared mapping is trusted not to corrupt
its contents while other processes are using it.
=head1 CRASH SAFETY
The write lock is a futex-based rwlock with PID-encoded ownership.
If the writer process dies while holding the lock, the next writer that
cannot acquire the lock checks whether the owner PID is still alive and,
if not, recovers the lock. Reader slots are similarly reclaimed when
a dead reader's slot is detected.
B<Limitation>: PID reuse is not detected. If a new process acquires
the same PID as a dead lock holder before recovery runs, the stale lock
may not be released automatically. This edge case requires the kernel
to reassign PIDs faster than lock-recovery attempts, which is very
unlikely in practice but cannot be ruled out.
Reader-slot exhaustion (slotless readers): dead-process recovery attributes a
#else
__asm__ volatile("" ::: "memory");
#endif
}
/* Writer word encoding: WRITER_BIT|pid when write-locked, 0 when free. */
#define SPH_RWLOCK_WRITER_BIT 0x80000000U
#define SPH_RWLOCK_PID_MASK 0x7FFFFFFFU
#define SPH_RWLOCK_WR(pid) (SPH_RWLOCK_WRITER_BIT | ((uint32_t)(pid) & SPH_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 sph_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 sph_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 !sph_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 sph_recover_stale_lock(SpatialHandle *h, uint32_t observed_wlock) {
SphHeader *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 < SPH_READER_SLOTS; i++) {
uint32_t dpid = __atomic_load_n(&h->reader_slots[i].pid, __ATOMIC_ACQUIRE);
if (dpid == 0 || dpid == now_pid || sph_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);
sph_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 sph_recover_after_timeout(SpatialHandle *h) {
uint32_t val = __atomic_load_n(&h->hdr->wlock, __ATOMIC_RELAXED);
if (val >= SPH_RWLOCK_WRITER_BIT) {
uint32_t pid = val & SPH_RWLOCK_PID_MASK;
if (!sph_pid_alive(pid))
sph_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 sph_park(SpatialHandle *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). */
sph_rdepth_dec(h);
sph_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 >= SPH_RWLOCK_WRITER_BIT &&
!sph_pid_alive(cur & SPH_RWLOCK_PID_MASK)) {
sph_recover_stale_lock(h, cur);
spin = 0;
continue;
}
if (__builtin_expect(spin < SPH_RWLOCK_SPIN_LIMIT, 1)) {
sph_rwlock_spin_pause();
continue;
}
sph_park(h);
cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
* crash window between acquiring the lock and storing the owner. */
uint32_t mypid = SPH_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 >= SPH_RWLOCK_WRITER_BIT &&
!sph_pid_alive(expected & SPH_RWLOCK_PID_MASK)) {
sph_recover_stale_lock(h, expected);
spin = 0;
continue;
}
if (__builtin_expect(spin < SPH_RWLOCK_SPIN_LIMIT, 1)) {
sph_rwlock_spin_pause();
continue;
}
sph_park(h);
uint32_t cur = __atomic_load_n(&hdr->wlock, __ATOMIC_RELAXED);
* instead of O(SPH_READER_SLOTS). */
for (uint32_t w = 0; w < SPH_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 (!sph_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/memfd_xproc.t view on Meta::CPAN
# (SCM_RIGHTS over a unix socket is the alternative when the creator may exit.)
pipe(my $R, my $W) or die "pipe: $!";
my $pid = fork // die "fork: $!";
if (!$pid) { # creator builds the index AFTER fork
close $R;
my $s = Data::SpatialHash::Shared->new_memfd('xproc', 1000, 0, 1.0);
$s->insert($_ + 0.5, 0.5, $_ * 100) for 1 .. 20;
syswrite $W, $$ . ' ' . $s->memfd . "\n";
close $W;
select undef, undef, undef, 5; # stay alive so /proc/$$/fd/N persists
_exit(0);
}
close $W;
my ($cpid, $cfd) = split ' ', scalar(<$R>);
open my $fh, '+<', "/proc/$cpid/fd/$cfd" or die "open /proc/$cpid/fd/$cfd: $!";
my $s2 = Data::SpatialHash::Shared->new_from_fd(fileno $fh);
is $s2->count, 20, "unrelated process sees the creator's 20 entries";
is_deeply [sort { $a <=> $b } $s2->query_aabb(-1, -1, 100, 100)],
[map { $_ * 100 } 1 .. 20], 'all entries visible via the passed memfd';
( run in 1.684 second using v1.01-cache-2.11-cpan-14f38c9f855 )