NAME
    Data::BloomFilter::Shared - shared-memory Bloom filter for Linux

SYNOPSIS
        use Data::BloomFilter::Shared;

        # sized for 1_000_000 items at a 1% false-positive rate, anonymous mapping
        my $bf = Data::BloomFilter::Shared->new(undef, 1_000_000, 0.01);

        $bf->add("alice");
        $bf->add("bob");

        $bf->contains("alice");             # 1 (probably present)
        $bf->contains("carol");             # 0 (definitely absent)

        # "have I seen this before?" -- add returns 1 the first time, 0 after
        my $first = $bf->add("event-42");   # 1: probably new
        my $again = $bf->add("event-42");   # 0: all its bits were already set

        # bulk add in a single lock acquisition
        my $new = $bf->add_many([ map { "user-$_" } 1 .. 1000 ]);

        # merge another filter of identical geometry (bitwise OR -> union)
        my $other = Data::BloomFilter::Shared->new(undef, 1_000_000, 0.01);
        $other->add_many([ map { "user-$_" } 500 .. 1500 ]);
        $bf->merge($other);

        # share across processes via a backing file
        my $shared = Data::BloomFilter::Shared->new("/tmp/seen.bloom", 1_000_000, 0.01);

        # freeze and ship: query it read-only (lock-free) on other machines
        $shared->freeze;
        my $ro = Data::BloomFilter::Shared->new_readonly("/tmp/seen.bloom");
        $ro->contains("event-42");

DESCRIPTION
    A Bloom filter in shared memory: a compact, fixed-size structure for
    probabilistic set membership. You add items to it, then ask whether an
    item is in the set. The answer is either "definitely not present" or
    "probably present": the filter has no false negatives (if you added it,
    "contains" always returns true) but a tunable rate of false positives (it
    may occasionally report an item as present that was never added). It never
    stores the items themselves, only a bit array, so memory is proportional
    to the configured capacity and false-positive rate, not to the size of the
    items.

    Each item is hashed once with XXH3 (128-bit); the two 64-bit halves drive
    "k" probe positions into a power-of-two bit array via Kirsch-Mitzenmacher
    double hashing. "add" sets those "k" bits; "contains" reports present only
    if all "k" are set. The number of hashes "k" and the bit-array size are
    derived from the "capacity" and "fp_rate" you request.

    Because the bit array lives in a shared mapping, several processes share
    one filter: any process that opens the same backing file, inherits the
    anonymous mapping across "fork", or reopens a passed memfd, sees the
    others' additions and contributes its own. A write-preferring futex rwlock
    with dead-process recovery guards mutation, so many processes may "add"
    and "contains" concurrently. Two filters of identical geometry can be
    combined with "merge" (bitwise OR), which yields a filter whose membership
    is the union of the two input sets.

    Items are added and tested by their byte content; wide-character strings
    (any codepoint above 255) cause a "Wide character" croak -- encode such
    strings to bytes first (for example with "Encode::encode_utf8").
    Linux-only. Requires 64-bit Perl.

METHODS
  Constructors
        my $bf = Data::BloomFilter::Shared->new($path, $capacity, $fp_rate);
        my $bf = Data::BloomFilter::Shared->new(undef, 1_000_000);          # fp_rate 0.01
        my $bf = Data::BloomFilter::Shared->new_memfd($name, $capacity, $fp_rate);
        my $bf = Data::BloomFilter::Shared->new_from_fd($fd);
        my $ro = Data::BloomFilter::Shared->new_readonly($path);   # frozen file, read-only

    $path is the backing file ("undef" or omitted for an anonymous mapping).
    $capacity is the number of items you expect to add; it must be at least 1.
    $fp_rate is the target false-positive rate at that capacity; it is
    optional, defaults to 0.01 (1%), and must be strictly between 0 and 1.
    "new" and "new_memfd" croak if $capacity is less than 1 or $fp_rate is out
    of range.

    From $capacity and $fp_rate the filter derives its geometry: "k =
    round(-log2(fp_rate))" hashes (clamped to the range 1..32), and a bit
    array of "m = next_power_of_two(ceil(capacity * k / ln 2))" bits (with a
    floor of 64 bits). Rounding the bit count up to a power of two means the
    realised false-positive rate at capacity is typically at or below the
    configured target. When reopening an existing file or memfd, the stored
    geometry wins and the caller's $capacity/$fp_rate do not resize it -- but
    they are still range-checked, so an out-of-range value croaks. "new_memfd"
    creates a Linux memfd (transferable via its "memfd" descriptor);
    "new_from_fd" reopens one in another process. The descriptor you pass is
    duplicated ("F_DUPFD_CLOEXEC"), so it stays yours to close and closing it
    does not disturb the handle. "new_readonly" opens a frozen file read-only
    for lock-free querying (see "FROZEN (READ-ONLY) MODE").

  Adding and testing
        my $new   = $bf->add($item);            # 1 if probably new, else 0
        my $added = $bf->add_many(\@items);     # count of items that were probably new
        my $in    = $bf->contains($item);       # 1 if probably present, 0 if definitely absent
        $bf->clear;                             # reset to empty (all bits 0)

    "add" hashes $item (taken by its bytes; wide characters croak, encode
    first) and sets its "k" bits, returning 1 if the item was probably new --
    that is, if at least one of its bits was previously unset -- and 0 if all
    "k" bits were already set (the item was probably added before). A return
    of 0 is therefore a "probably seen this already" signal, subject to the
    same false-positive rate as "contains". "add_many" takes an array
    reference and does the whole batch under a single write lock, returning
    how many of its elements were probably new.

    "contains" returns 1 if the item is probably present and 0 if it is
    definitely absent. The contract is asymmetric and is the whole point of a
    Bloom filter: a 0 is exact (the item was never added), while a 1 may be a
    false positive (some other items happened to set all of this item's bits).
    There are never false negatives: any item you have added always reports as
    present.

  Merging
        $bf->merge($other);

    Folds $other's bit array into $bf by bitwise OR, so $bf then reports as
    present the union of the two filters' item sets (still with no false
    negatives). Both filters must have identical geometry -- the same number
    of bits and the same number of hashes, which follows from constructing
    both with the same $capacity and $fp_rate ("merge" croaks on a mismatch).
    $other is read under its own lock into a private snapshot first, so
    merging is deadlock-free even if two processes merge each other
    concurrently; $other is not modified.

  Introspection and lifecycle
        $bf->capacity; $bf->bits; $bf->hashes; $bf->fp_rate; $bf->count; $bf->stats;
        $bf->path; $bf->memfd; $bf->sync; $bf->unlink;   # or Class->unlink($path)

    "capacity" is the configured item capacity; "bits" is the bit-array size
    in bits (a power of two); "hashes" is the number of hash probes "k";
    "fp_rate" is the configured target false-positive rate. "count" returns an
    estimate of the number of distinct items added, computed from the fraction
    of bits set (accurate while the filter is not saturated, and capped at
    "capacity" once it is). "sync" flushes the mapping to its backing store (a
    no-op for anonymous and memfd filters, which have none); "unlink" removes
    the backing file (also callable as "Class->unlink($path)") and croaks if
    the removal fails -- except when the file is already gone, which is what
    you asked for; it is likewise a no-op when there is no backing file
    (anonymous or memfd); "path" returns the backing path ("undef" for
    anonymous, memfd, or fd-reopened filters) and "memfd" the backing
    descriptor -- the memfd of a "new_memfd" filter or the dup'd fd of a
    "new_from_fd" filter, and -1 for file-backed or anonymous filters.

STATS
    stats() returns a hashref describing the filter:

    *   "capacity" -- the configured item capacity.

    *   "fp_rate" -- the configured target false-positive rate.

    *   "bits" -- the bit-array size in bits (a power of two).

    *   "hashes" -- the number of hash probes "k" per item.

    *   "bits_set" -- how many bits are currently set.

    *   "count" -- the estimated number of distinct items added.

    *   "fill_ratio" -- "bits_set / bits", between 0 and 1. As this approaches
        0.5 the filter is near its designed capacity and the realised
        false-positive rate approaches the configured target; well above that
        the rate climbs.

    *   "ops" -- running count of mutating operations ("add", "add_many",
        "merge", "clear").

    *   "mmap_size" -- bytes of the shared mapping.

    *   "frozen" -- 1 if the filter has been sealed by "freeze" (immutable),
        else 0.

    *   "readonly" -- 1 if this handle is a read-only view (from
        "new_readonly", or the handle that called "freeze"), else 0.

SHARING ACROSS PROCESSES
    The filter lives in a shared mapping, shared the same three ways as the
    rest of the family: a backing file (every process calls "new($path, ...)"
    on the same path with matching capacity and rate), an anonymous mapping
    inherited across "fork", or a memfd whose descriptor is passed to an
    unrelated process (over a UNIX socket via "SCM_RIGHTS", or via
    "/proc/$pid/fd/$n") and reopened with new_from_fd($fd). Because the
    mapping is shared, every process adds into and tests against the same bit
    array, so membership reflects the union of what all of them have added.

        # producer and consumer share one filter with no coordination
        my $bf = Data::BloomFilter::Shared->new(undef, 100_000, 0.01);   # before fork
        unless (fork) { $bf->add_many([ map { "ev-$_" } 1 .. 1000 ]); exit }
        wait;
        print $bf->contains("ev-500") ? "seen\n" : "no\n";   # seen -- the child's add

FROZEN (READ-ONLY) MODE
    A file-backed filter can be frozen and then shipped to other machines,
    where consumers open it read-only and query it with no locking at all.

        # producer: build, freeze, ship the file
        my $bf = Data::BloomFilter::Shared->new("/tmp/seen.bloom", 1_000_000, 0.01);
        $bf->add_many(\@known);
        $bf->freeze;                 # seal: now immutable, and $bf itself is read-only
        # ... copy /tmp/seen.bloom to another host ...

        # consumer (any process, same architecture): read-only, lock-free
        my $ro = Data::BloomFilter::Shared->new_readonly("/tmp/seen.bloom");
        $ro->contains($item) for @queries;

    "freeze" takes the write lock, marks the filter permanently immutable
    (there is no unfreeze -- rebuild the file to change it), and flushes the
    seal to disk. A frozen filter rejects every mutator ("add", "add_many",
    "merge", "clear") with a croak, and a read-write reopen ("new($path,
    ...)") of a sealed file is refused -- so a shipped artifact can never be
    silently mutated out from under its readers. That protection is enforced
    by the reader: the seal is a header flag that 0.04 and earlier do not know
    about, and the on-disk format version is deliberately unchanged so those
    releases can still open files written here. A pre-0.05 build therefore
    opens a sealed file read-write and can modify it, so keep producers and
    consumers on 0.05 or later if you rely on the seal. "freeze" itself is not
    idempotent: the handle that seals the file becomes a read-only view of it,
    so calling "freeze" on that handle again croaks.

    new_readonly($path) maps the file "O_RDONLY" / "PROT_READ" and requires it
    to be frozen (it croaks on a file that was never "freeze"d). Because a
    sealed filter's bits and geometry are immutable, "contains", "count" and
    "stats" read them 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
    "PROT_READ" mapping. "frozen" and "readonly" report the two states.

    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 same
    architecture; a wrong-endian file is rejected at open by the magic check.
    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.

SECURITY
    Backing files are created with mode 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 0660 as the last argument
    to "new"; the mode is applied when the file is created, and when a 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
    Mutation is guarded by a futex-based write-preferring rwlock with
    PID-encoded ownership; if a holder dies, the next contender detects the
    dead owner and recovers. Each bit set is a single word store, so a crash
    leaves the filter consistent up to the last completed "add". 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. Those
    preconditions cover the live-process route only. The count lives in the
    mapping and "new" validates the geometry, not this transient value, so a
    backing file damaged at rest -- bit rot, a partial copy, or a process that
    scribbled on the mapping -- can present a non-zero slotless count and
    block every writer the same way, with none of the above. If writers hang
    on a file no live reader is using, recreate it.

    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 Bloom filter 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.

    Disk space. The backing file is created sparse: "new" sizes it, but blocks
    are allocated only as you write, so a large filter costs almost nothing on
    disk until it is used. The cost of that is a late failure, and how it
    reaches you depends on the filesystem. Where blocks are allocated at fault
    time -- tmpfs, so "/dev/shm" and many "/tmp" mounts -- a write to a page
    that cannot be backed raises "SIGBUS" and kills the process, because an
    "mmap" store has no way to report "ENOSPC". Where allocation is delayed to
    writeback (ext4, xfs), the store lands in page cache and the failure
    appears later: the write is lost, and "sync" is what reports it, croaking
    with the underlying error. Keep the filesystem sized for the filter you
    asked for, and call "sync" when you need to know your writes reached disk.

SEE ALSO
    Data::HyperLogLog::Shared, Data::Intern::Shared, Data::SortedSet::Shared,
    Data::SpatialHash::Shared, and the rest of the "Data::*::Shared" family.

AUTHOR
    vividsnow

LICENSE
    This is free software; you can redistribute it and/or modify it under the
    same terms as Perl itself.