view release on metacpan or  search on metacpan

lib/Data/SpatialHash/Shared.pm  view on Meta::CPAN

A file-backed spatial hash can be B<frozen> and then shipped to other
machines, where consumers open it B<read-only> and query it with B<no
locking at all>.

    # producer: build, freeze, ship the file
    my $s = Data::SpatialHash::Shared->new("/tmp/world.sph", 100_000, 0, 1.0);
    $s->insert($_, $_, $_) for 1 .. 1000;
    $s->freeze;                 # seal: now immutable, and $s itself is read-only
    # ... copy /tmp/world.sph to another host ...

    # consumer (any process, same architecture): read-only, lock-free
    my $ro = Data::SpatialHash::Shared->new_readonly("/tmp/world.sph");
    my @near = $ro->query_radius(5, 5, 10);

C<freeze> takes the write lock, marks the spatial hash B<permanently
immutable> (there is no unfreeze -- rebuild the file to change it), and
flushes the seal to disk. A frozen spatial hash rejects every mutator
(C<insert>, C<insert_many>, C<insert_geo>, C<move>, C<move_many>,
C<move_geo>, C<remove>, C<set_value>, C<set_radius>, C<clear>) with a croak,
and a read-write reopen (C<< new($path, ...) >> or C<new_from_fd>) of a
sealed file is B<refused> -- so a shipped artifact can never be silently
mutated out from under its readers.

C<new_readonly($path)> maps the file C<O_RDONLY> / C<PROT_READ> and
B<requires it to be frozen> (it croaks on a file that was never C<freeze>d).
Because a sealed spatial hash's entries and geometry are immutable, every
accessor and query method -- C<has>, C<value>, C<get_radius>, C<position>,
C<position_geo>, C<count>, C<query_cell>, C<query_aabb>, C<query_radius>,
C<query_radius_many>, C<query_knn>, C<query_geo_radius>, C<each_in_radius>,
C<each_pair_within>, C<each_colliding_pair>, and C<stats> -- reads it
B<directly, taking no reader lock>. The mapping is never written, so a
read-only view works from a read-only file descriptor or a read-only
filesystem, and any number of processes can share one C<PROT_READ> mapping.
C<sync> is a silent no-op on a read-only view. C<frozen> and C<readonly>
report the two states.

B<Portability.> The on-disk format is native binary (native-endian 64-bit
words), so a frozen file may be copied only between machines of the B<same
architecture>; a wrong-endian file is rejected at open by the magic check.
B<Copy the file to each consumer> -- do not share one file over a network
filesystem: the lock is a Linux futex (process-local to one kernel), and the
"no live writer" contract assumes a static copy. Linux-only; 64-bit Perl.

=head1 SECURITY

Backing files are created with mode C<0600> (owner-only) by default, so only
the creating user can open and attach them. To share a backing file across
users, pass an explicit octal file mode such as C<0660> via a C<< mode => 0660
>> option to C<new>; the mode is applied when the file is created, and when a
file left behind by an interrupted create is re-initialized (see L</CRASH
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
crashed lock holder's contribution through its reader-slot. The slot table holds
1024 entries (one per concurrent reader process). If more than that many reader
processes share one mapping at once, a reader that cannot claim a slot proceeds
"slotless" -- it still takes the read lock but leaves no per-process record. If
such a slotless reader is then killed while holding the read lock, its share of
the lock cannot be attributed to a dead process, so writer recovery cannot
reclaim it and writers may block until the mapping is recreated. Reaching this
needs more than 1024 concurrent reader processes on one mapping plus a crash in
the brief read-lock window; the dead-process slot reclaim keeps the table from
filling with stale entries, so in practice it is very unlikely.

An interrupted create is recovered too. A creator killed after the backing
file is sized but before its header is committed leaves a full-size, all-zero
file. C<new> re-initializes such a file automatically, but only when it is
exactly the size the requested geometry needs, is owned by your effective uid,
and is still entirely zero -- a file holding data is never re-initialized. If
the creator got as far as writing part of the header, the file cannot be told
apart from a corrupt one and C<new> croaks with C<incomplete spatial hash file
left by an interrupted create; remove it and retry>. A file left behind by an
interrupted create never held data, so removing it is safe -- but a file whose
header was corrupted after the fact reaches the same croak, so confirm it is
an abandoned create before deleting anything you care about.

=head1 SEE ALSO

L<Data::Graph::Shared> - directed weighted graph

L<Data::Heap::Shared> - priority queue (for Dijkstra, Prim, etc.)

L<Data::Pool::Shared> - fixed-size object pool

L<Data::HashMap::Shared> - concurrent hash table

L<Data::Buffer::Shared> - typed shared array

L<Data::Queue::Shared> - FIFO queue

L<Data::Stack::Shared> - LIFO stack

L<Data::Deque::Shared> - double-ended queue

L<Data::Log::Shared> - append-only log

L<Data::Sync::Shared> - synchronization primitives

L<Data::PubSub::Shared> - publish-subscribe ring

L<Data::ReqRep::Shared> - request-reply

L<Data::BitSet::Shared> - shared bitset (lock-free per-bit ops)