view release on metacpan or  search on metacpan

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

C<$n> is the number of positions (at least 1, up to 2^24); every position
starts at 0. Memory is C<2 * next_pow2(n) * 64> bytes plus a fixed header.
C<new> and C<new_memfd> croak on a C<$n> below 1 or above 2^24. When reopening
an existing file or memfd the stored C<$n> wins and the caller's arguments do
not resize it -- but they are still range-checked, so an out-of-range value
croaks. An optional file B<mode> may be passed as the last argument to C<new>
(e.g. C<0660>) for cross-user sharing; it defaults to C<0600> (owner-only).

=head2 Updates

    $st->set($i, $value);              # position $i := $value
    my $new = $st->add($i, $delta);     # position $i += $delta; returns the new value
    $st->range_add($l, $r, $delta);     # add $delta to every position in [$l, $r]
    $st->range_assign($l, $r, $value);  # set every position in [$l, $r] to $value

C<set> assigns a single position; C<add> adds a delta to a single position and
returns its new value; C<range_add> adds a delta to every position in the
inclusive range C<[$l, $r]>, and C<range_assign> sets every position in the range
to a constant -- each in O(log n) via lazy propagation. All indices are 0-based
and croak if out of range; the range forms croak if C<$l > $r>.
C<range_add>/C<add> gate off the gcd/product monoids (see below); C<set>/
C<range_assign> do not.

=head2 Queries

    my $v = $st->get($i);          # value at position $i
    my $s = $st->sum($l, $r);      # sum over [$l, $r]
    my $lo = $st->min($l, $r);     # minimum over [$l, $r]
    my $hi = $st->max($l, $r);     # maximum over [$l, $r]
    my $q = $st->query($l, $r);    # { sum, min, max, count } in one locked call
    my $g = $st->gcd($l, $r);      # gcd over [$l, $r]     (assign/set-only trees)
    my $p = $st->product($l, $r);  # product over [$l, $r] (assign/set-only trees)

C<get> returns a single position's value. C<sum>, C<min>, and C<max> return one
aggregate over the inclusive range C<[$l, $r]>. C<query> returns all of them at
once as a hash reference C<< { sum, min, max, count } >> (C<count> is
C<$r - $l + 1>), computed under a single read lock so the four values are
mutually consistent. C<gcd> returns the greatest common divisor of C<|values|>
over the range (0 for an all-zero range), and C<product> returns their product;
both require an B<assign/set-only> tree and croak once any C<range_add>/C<add> has run
(see L</"Range assign and the gcd/product monoids">), and C<product> also croaks
on 64-bit overflow. Ranges croak if an index is out of range or C<$l > $r>.

=head2 Introspection and lifecycle

    $st->size;          # n, the number of positions
    $st->monoids_valid; # true if gcd/product are still usable (no range_add yet)
    $st->clear;         # reset every position to 0
    $st->stats;         # { n, size, tree_size, ops, mmap_size }
    $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.

=head1 SECURITY

Backing files are created with mode C<0600> (owner-only) by default; pass an
explicit octal mode (e.g. C<0660>) as the last argument to C<new> for cross-user
sharing (the mode is masked to the permission bits C<0777>). The file is opened
with C<O_NOFOLLOW> and C<O_EXCL>, and the header is validated on attach. Any
process granted write access is trusted not to corrupt the mapping.

A descriptor passed to C<new_from_fd> must be B<resize-sealed> (a C<memfd> sealed
against C<F_SEAL_SHRINK>|C<F_SEAL_GROW>, as C<new_memfd> produces) or come from a
trusted owner: a hostile donor that truncates the fd after it is mapped can fault
the reader with C<SIGBUS> on a later access. C<new_from_fd> rejects a sealable fd
that lacks both resize seals; a non-sealable fd (e.g. a regular file) cannot carry
seals and is accepted on the caller's trust.

=head1 CRASH SAFETY

Mutation is guarded by a futex-based write-preferring rwlock with PID-encoded
ownership and dead-owner recovery. Dead-owner recovery restores lock
B<availability> only. Each mutation is a multi-store O(log n) tree walk with no
commit protocol, so a writer killed mid-update leaves that update partially
applied: the tree can be left internally inconsistent (a later C<query> may
disagree with the individual C<get> values), and recovery neither detects nor
repairs the torn update. Treat a crash during a mutation as leaving the tree in
an undefined state, and rebuild from a trusted source if you need consistency
across crashes. B<Limitation>: PID reuse is not detected (very unlikely in
practice).

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 segment-tree 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