view release on metacpan or  search on metacpan

README  view on Meta::CPAN

    $n is the number of positions (at least 1, up to 2^24); every position
    starts at 0. Memory is "2 * next_pow2(n) * 64" bytes plus a fixed header.
    "new" and "new_memfd" croak on a $n below 1 or above 2^24. When reopening
    an existing file or memfd the stored $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 mode may be passed as the last argument to
    "new" (e.g. 0660) for cross-user sharing; it defaults to 0600
    (owner-only).

  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

    "set" assigns a single position; "add" adds a delta to a single position
    and returns its new value; "range_add" adds a delta to every position in
    the inclusive range "[$l, $r]", and "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 $l
    $r>. "range_add"/"add" gate off the gcd/product monoids (see below);
    "set"/ "range_assign" do not.

  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)

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

  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;

    "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.

SECURITY
    Backing files are created with mode 0600 (owner-only) by default; pass an
    explicit octal mode (e.g. 0660) as the last argument to "new" for
    cross-user sharing (the mode is masked to the permission bits 0777). The
    file is opened with "O_NOFOLLOW" and "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 "new_from_fd" must be resize-sealed (a "memfd"
    sealed against "F_SEAL_SHRINK"|"F_SEAL_GROW", as "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 "SIGBUS" on a later access.
    "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.

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 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 "query" may disagree with the individual "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.
    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. "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 "new" croaks with
    "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