/ 
Data-Graph-Shared-0.06
/ Data::Graph::Shared

NAME

Data::Graph::Shared - Shared-memory directed weighted graph for Linux

SYNOPSIS

use Data::Graph::Shared;

my $g = Data::Graph::Shared->new(undef, 100, 500);  # 100 nodes, 500 edges
my $a = $g->add_node(10);    # returns node index
my $b = $g->add_node(20);
my $c = $g->add_node(30);

$g->add_edge($a, $b, 5);     # a->b weight 5
$g->add_edge($a, $c, 3);     # a->c weight 3
$g->add_edge($b, $c, 1);     # b->c weight 1

my @nbrs = $g->neighbors($a);  # ([2,3], [1,5]) - [dst,weight] pairs, newest edge first
say $g->degree($a);            # 2
say $g->node_data($a);         # 10

$g->remove_node($b);          # removes node and outgoing edges

DESCRIPTION

Directed weighted graph in shared memory. Nodes allocated from a bitmap pool, edges stored as adjacency lists in a separate edge pool. Mutex-protected mutations with PID-based stale recovery.

Note: remove_node removes the node and its outgoing edges only. Incoming edges from other nodes are NOT automatically removed (this is an O(1) design choice) -- their dst is left dangling until the slot's bit is reused. Use remove_node_full when this matters; it additionally splices incoming edges in O(N+E).

Linux-only. Requires 64-bit Perl.

METHODS

Constructors

my $g = Data::Graph::Shared->new($path, $max_nodes, $max_edges);  # file-backed
my $g = Data::Graph::Shared->new(undef, $max_nodes, $max_edges);  # anonymous
my $g = Data::Graph::Shared->new_memfd($name, $max_nodes, $max_edges);
my $g = Data::Graph::Shared->new_from_fd($fd);                    # reopen memfd
my $ro = Data::Graph::Shared->new_readonly($path);   # frozen file, read-only

$max_nodes is rounded up to the next even number for alignment, so $g->max_nodes may report one more than requested; $max_edges is the edge-slot capacity. An optional trailing octal $mode (see "SECURITY") sets the backing-file permissions. new_readonly opens a frozen file read-only for lock-free queries (see "FROZEN (READ-ONLY) MODE"). The descriptor you pass is duplicated (F_DUPFD_CLOEXEC), so it stays yours to close and closing it does not disturb the handle.

Operations

my $id = $g->add_node($data);            # returns node index or undef
$g->add_edge($src, $dst);                # weight defaults to 1
$g->add_edge($src, $dst, $weight);
$g->remove_node($id);                    # O(1) -- outgoing edges only
$g->remove_node_full($id);               # O(N+E) -- also splices incoming
$g->has_node($id);
$g->node_data($id);
$g->set_node_data($id, $data);
my @pairs = $g->neighbors($id);          # list of [$dst, $weight]
$g->each_neighbor($id, sub { my ($dst, $w) = @_ });
$g->degree($id);
my @ids = $g->nodes;                     # all node indices
$g->node_count;  $g->edge_count;
$g->max_nodes;   $g->max_edges;

An id becomes stale once its node is removed, and the two kinds of method treat that differently. add_edge, remove_node and remove_node_full return true when they did something and false when the node is not there -- so an add_edge naming a removed node adds no edge and reports it only through that return value. node_data, set_node_data, degree, neighbors and each_neighbor instead croak on an id that does not exist. has_node is the cheap way to tell beforehand.

Lifecycle

$g->path;              # backing file path, or undef for anon/memfd
$g->memfd;             # memfd fd (-1 for file-backed/anon)
$g->stats;             # diagnostic hashref
$g->sync;              # msync mmap to backing store
$g->unlink;            # remove backing file
Class->unlink($path);  # class-method form

Event Loop Integration

my $fd = $g->eventfd;         # lazy-create eventfd, returns fd
$g->eventfd_set($fd);         # attach an external eventfd
my $fd = $g->fileno;          # current eventfd fd, or -1
$g->notify;                   # write 1 to eventfd (caller signals update)
my $n = $g->eventfd_consume;  # read+reset eventfd counter

CONCURRENCY AND CRASH SAFETY

The graph lives entirely in a shared memory mapping, so multiple processes that attach the same backing file (or inherit the same anonymous/memfd mapping) operate on one shared structure. All mutating operations are serialized by a single process-shared exclusive mutex stored in the mapping header; it is implemented directly on a Linux futex, so it works across unrelated processes without any pthread setup.

The mutex records the PID of its current owner. If a process dies while holding the lock, a waiter that times out detects the dead (or zombie) owner via kill(pid, 0) plus a /proc liveness check, reclaims the lock, and proceeds. This keeps a crash from wedging the whole graph, but it cannot undo a mutation that was only half-applied at the moment of death, so a peer crashing mid-write may leave the structure in an inconsistent state.

Any process you grant write access to the mapping is trusted not to corrupt it. This is Linux-only (it relies on futex and /proc).

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

BENCHMARKS

Single-process (10K ops, x86_64 Linux, Perl 5.40):

add_node            3.9M/s
add_edge (random)   2.3M/s
has_node           13.3M/s
node_data           5.5M/s
neighbors           2.6M/s
degree              5.6M/s

STATS

stats() returns: node_count, edge_count, max_nodes, max_edges, ops, mmap_size, frozen, readonly.

FROZEN (READ-ONLY) MODE

A file-backed graph 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 $g = Data::Graph::Shared->new("/tmp/graph.shm", 100, 500);
my $a = $g->add_node(1);
my $b = $g->add_node(2);
$g->add_edge($a, $b, 5);
$g->freeze;                  # seal: now immutable, and $g itself is read-only
# ... copy /tmp/graph.shm to another host ...

# consumer (any process, same architecture): read-only, lock-free
my $ro = Data::Graph::Shared->new_readonly("/tmp/graph.shm");
$ro->neighbors($a);

freeze takes the mutex, marks the graph permanently immutable (there is no unfreeze -- rebuild the file to change it), and flushes the seal to disk. A frozen graph rejects every mutator (add_node, add_edge, remove_node, remove_node_full, set_node_data) with a croak, and a read-write reopen (new($path, ...) or new_from_fd) of a sealed file is refused -- so a shipped artifact can never be silently mutated out from under its readers.

new_readonly($path) maps the file O_RDONLY / PROT_READ and requires it to be frozen (it croaks on a file that was never freezed). Because a sealed graph's nodes and edges are immutable, has_node, node_data, neighbors, degree, nodes, each_neighbor, node_count, edge_count and stats read them directly, taking no 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 corrupt or foreign-endian file is rejected at open (the magic check fails). Copy the file to each consumer -- do not share one file over a network filesystem: the mutex 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 "CONCURRENCY AND 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.

SEE ALSO

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

Data::Pool::Shared - fixed-size object pool

Data::HashMap::Shared - concurrent hash table

Data::Buffer::Shared - typed shared array

Data::Queue::Shared - FIFO queue

Data::Stack::Shared - LIFO stack

Data::Deque::Shared - double-ended queue

Data::Log::Shared - append-only log

Data::Sync::Shared - synchronization primitives

Data::PubSub::Shared - publish-subscribe ring

Data::ReqRep::Shared - request-reply

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

Data::RingBuffer::Shared - fixed-size overwriting ring buffer

AUTHOR

vividsnow

LICENSE

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