Update the syslink documentation. A number of major design changes have

[games.git] / lib / libc / sys / syslink.2

.\" Copyright (c) 2007 The DragonFly Project.  All rights reserved.
.\"
.\" This code is derived from software contributed to The DragonFly Project
.\" by Matthew Dillon <dillon@backplane.com>
.\"
.\" Redistribution and use in source and binary forms, with or without
.\" modification, are permitted provided that the following conditions
.\" are met:
.\"
.\" 1. Redistributions of source code must retain the above copyright
.\"    notice, this list of conditions and the following disclaimer.
.\" 2. Redistributions in binary form must reproduce the above copyright
.\"    notice, this list of conditions and the following disclaimer in
.\"    the documentation and/or other materials provided with the
.\"    distribution.
.\" 3. Neither the name of The DragonFly Project nor the names of its
.\"    contributors may be used to endorse or promote products derived
.\"    from this software without specific, prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
.\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
.\" LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
.\" FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE
.\" COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
.\" INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
.\" BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
.\" LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
.\" AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
.\" OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
.\" OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
.\" SUCH DAMAGE.
.\"
.\" $DragonFly: src/lib/libc/sys/syslink.2,v 1.3 2007/03/24 18:53:57 dillon Exp $
.\"
.Dd March 13, 2007
.Dt SYSLINK 2
.Os
.Sh NAME
.Nm syslink
.Nd low level connect to the cluster mesh
.Sh LIBRARY
.Lb libc
.Sh SYNOPSIS
.In sys/syslink.h
.Ft int
.Fn syslink "int fd" "int flags" "sysid_t routenode"
.Sh DESCRIPTION
The
.Fn syslink
function establishes a link to a kernel-implemented syslink route node
as specified by
.Fa routenode .
If a file descriptor of -1 is specified, a file descriptor representing
a direct connection to the specified route node will be allocated and
returned.
If a file descriptor is specified, it will be connected to the specified
route node via full-duplex communication and kernel threads will be
created to shuttle data between the descriptor and the route node.  The
kernel may optimize and shortcut this operation.
.Pp
It is also perfectly legal to allocate two route nodes and then connect them
together by passing the file descriptor returned by the first
.Fn syslink
call to the second
.Fn syslink
call.  It is legal (and usually necessary) to obtain multiple descriptors to
the same kernel-managed syslink route node.
.Pp
The syslink protocol revolves around 64 bit system ids using the
.Ft sysid_t
type.  A sysid can represent one of three entities:  A session identifier,
a logical identifier, or a physical identifier.
Session ids are synthesized by machine nodes and used to
uniquely identify a communications session between two entities in a way
that prevents any possible duplication or confusion in the face of a
constantly changing mesh, migration of logical elements, and other activities.
Logical ids are persistent entities which uniquely identify resources.
Examples of resources include filesystems, hard drive partitions, devices,
VM spaces, memory, cpus, and so forth.  The logical id migrates with the
resource, meaning that you can physically move a hard drive from one part
of the mesh to another and the mesh will automatically figure out the
new location.  New logical identifiers are also typically synthesized
entities.  Physical ids are dynamically propogated through the mesh from
seed nodes and used to route messages.  Any given node in the mesh may be
addressable via multiple physical ids, each representing a different path
to the node.
.Pp
For example, a particular filesystem mount will have a persistent logical
sysid, a separate session id for every entity connecting to it, and one or
more dynamic (changable) physical sysids depending on the mesh topology.
.Sh SYSLINK PROTOCOL - PHYSICAL SYSIDS
The Syslink protocol is used to glue the cluster mesh together.  It is
based on the concept of (mostly) reliable packets and buffered streams.
Adding a new node to the mesh is as simple as obtaining a stream connection
to any node already in the mesh, or tying into a packet switch with UDP.
.Pp
Physical sysids are propogated from seed nodes in the mesh.  There must be
at least one seed node and there are usually on the order of 2-4.  Seed
nodes are usually located at key points in the cluster topology.  A seed
node has a statically assigned physical space.  Propogation consists of
chopping a number of bits off the space and assigning an address value 
for each connecting entity, then propogating the space through the connecting
entity.  The connecting entity chops more bits off the space for its own
connecting entities and continues propogating the address space.  Loops in
the graph are trivially detected simply by observing the number of free bits
in the propogated space.
.Pp
Physical sysid propogation occurs continuously and allows the mesh to
dynamically adapt to changes in the topology within a few seconds.
Due to the nature of the propogation of the space, each physical sysid
can be used to trivially route messages between two entities.
Link-layer communication (that is, communication between directly adjacent
nodes) can occur independantly of physical sysid space propogation.
Communication with seed nodes is also trivial, since seed nodes represent
static physical sysids.
The physical sysid of a node can change at any time, sometimes radically.
Session ids are used to maintain sanity in a changing topology.
.Sh SYSLINK PROTOCOL - SESSION SYSIDS
Session sysids are used to uniquely identify a communications link between
two entities in the mesh.  Session sysids are synthesized by individual
machines and maintained by the two route nodes at the two end points for
any particular communications session.  For example, if a device A wishes to
communicate with a filesystem B, and device A connects to route node Ra
and filesystem B connects to route node Rb, then Ra and Rb are responsible
for translating the session sysid in the message to physical sysids for
routing the message.  The end points simply use the session id.  Creating
the 'connection'... that is, allocating the session id in the first place,
is similar to an 'open' command.  The entity issuing the open talks to its
immediate route node (A would talk to Ra) to initiate the session and obtain
the session id.
.Pp
Session sysids are forever unique.  A communications session can survive
migration and topological changes, even if the route node changes.  When
a topological change is detected, the session must be re-trained, which is
a simple protocol from the point of view of leaf and route nodes.
Route nodes manage timeouts, retries, and error handling for the sessions
under their care, greatly reducing the protocol complexity from the viewpoint
of a leaf node (e.g. filesystem, device, whatever).  Leaf nodes (connected
to the route node via a stream) need only detect disconnections of the
stream.
.Pp
Establishment of a new session or retraining an existing session is usually
based on the logical sysid for the two entities involved.  That is, sessions
are created between entities defined by a logical sysid for each entity.
The logical sysid is the ultimate rendezvous, the session sysid identifies
a session or transaction, the physical sysid routes the message.
.Sh SYSLINK PROTOCOL - LOGICAL SYSIDS
Logical sysids are forever-unique, persistent entities which represent
the ultimate rendezvous identifier.  When you label a new disk, a unique
logical sysid will be assigned to that label which allows the disk to be
properly identified no matter where it resides in the cluster.  
A logical sysid is associated with an ascii name and a type for
identification purposes.  For example, when you label a new disk it will
be given a unique 64 bit logical sysid and you must also supply a name,
such as 'MYDISK01'.  The disk can then be located by its logical sysid or
by its name and type.
Resources can be broken up into smaller pieces and those pieces can
also be assigned logical sysids.  For example, an ANVIL disk partition can
have its own logical sysid and name independant of the one assigned to the
label.
.Pp
Logical sysids are typically synthesized by individual machines without
mesh involvement.  Synthesized logical sysids are usually based on a
hash of an interface MAC address combined with a timestamp and iterator.
When making resources available to a named cluster, the logical sysids
of the resources may be translated to cluster-friendly logical sysids
as part of the setup, but intervention (in the form of translation) is only
needed if an actual conflict occurs.  An external mechanism unrelated to
the cluster itself detects conflicts -- usually a database of some sort
which associates a much larger unique id made up of a full domain name and
timestamp with the hash.  Typically 24 Machine-unique bits are reserved out
of the 64 bit sysid, leaving 40 bits.  This allows several hundred to
several thousand new unique, logical sysids to be allocated per second.
The actual number is usually far smaller (how often do you create a new
disklabel?).  This may seem confusing but it is really nothing more then
a simple translation layer that allows unrelated machine resources (e.g.
owned by different people) to be associated with the same cluster.
Only the machine-unique bits may need to be translated.
.Sh SYSLINK PROTOCOL - PROPOGATION OF PHYSICAL SYSID SPACE
Assignment of physical sysid space is simple.  The seed nodes take their
statically assigned sysid space (specified by a 64 bit CIDR block), cut out
enough bits to handle the number of connections that need to be supported,
and then dole out a subnet to each connectee.  If a connectee is a route node
it is then able to cut up the subnet CIDR block and dole out subnets to
nodes that connect to it.  Leaf nodes have fixed SYSID space requirements,
typically 10 bits.  If a leaf node is handed a 24 bit sysid space it will
still use only 10 bits of it.  A leaf node handed a sysid space below its
minimum requirement simply ignores that space.
.Pp
Eventually every seed node propogates its physical sysid space to every other
node in the mesh.  If a mesh has four seed nodes, then every node in the mesh
will wind up with at least four physical SYSID spaces.
Nodes may obtain additional physical SYSID assignments due to loops
in the graph.  For example, if you create a triangle between nodes A, B,
and C, with B as the seed node, then SYSID will propogate B->C->A->B and
B->A->C->B and node A will wind up with two physical SYSID assignments (and
node B will have four) even though there was only one seed node.
Physical SYSID assignments represent routing paths.
Because the mesh is potentially too large to store the full graph
in memory, the SYSLINK protocol only requires that the four largest SYSID
spaces for any given seed be retained by every node.  This creates a
self-healing mesh with reasonable, but not ultimate redundancy.
.Pp
Only a limited number of hops are supported in the mesh due to the
limitations of the 64 bit ID space and the need to be able to route
messages trivially using a single 64 bit physical id - without having to
retain a route table for the whole mesh in each route node.  Very large
meshes require some attention to the design of the topology to retain
reasonable redundancy.
For example, if you are trying to create an internet-wide mesh to handle
a massively distributed problem which requires low data bandwidths,
you might implement a couple of very large CIDR distribution blocks
for people to connect to via TCP streams.
.Pp
Once physical SYSID space is assigned (and remember, the physical SYSID
space can change on the fly as nodes go up and down), messages may be sent
from one physical SYSID to another, or broadcast across the entire mesh.
Only messages to immediate neighbors are guaranteed to be reliable, but
for the cluster to operate efficiently packet loss is not tolerated.
Message delivery failures must be almost solely due to losses which occur
when the topology changes (due to a node going up or down).
.Sh SYSLINK PROTOCOL - LOGICAL AND SESSION SYSIDS, ALLOCATION
Logical and session sysids are synthesized based on a unique per-machine
mesh id (usually a hash of an interface MAC address), plus timestamp and
iterator.  As long as the machine's system time is reasonably accurate (and
it had better be), the uniqueness will be maintained across reboots and other
spurious events.
.Sh SYSLINK PROTOCOL - LOGICAL AND SESSION SYSIDS, REGISTRATION AND RESOLUTION
A leaf node must register the logical sysids it wishes to make available to
the cluster with the route node it connects to.  These registrations allow
the route node to resolve lookup requests from the cluster to that particular
leaf node.  By default, lookup requests are broadcast to all route nodes.
Bandwidth can be reduced by allowing route nodes near the leafs of the
cluster mesh to propogate the registration(s) to a tighter set of route
nodes within the cluster, greatly reducing the cost of doing a logical sysid
lookup.
.Sh SYSLINK PROTOCOL - MESSAGE ROUTING
Session sysids are the 'open/connected' abstraction for leaf entities and
are maintained by route nodes, allowing leaf nodes to construct syslink
messages using only the session sysid and a direction bit.  A route node
can lose track of a session sysid... for example, a leaf node might migrate
to another part of the cluster or might have to use a communications path
via a different route node due to a failure or a change in the topology.  If
a route node does not recognize the session id of a syslink message, it
replies with a RETRAIN request to the leaf node.  The leaf node then retrains
the session id by providing all the information required for the route node
to reconstruct the connection (typically the originating and target logical
sysid).  The routing node not only caches the logical sysid information, it
is also responsible for looking up and caching physical sysids to actually
route message(s).
.Pp
This may seem complex but it all comes down to a very simple messaging
format and protocol.  The retraining protocol also serves to validate 
communications links between entities and to allow massive changes in
mesh topology to occur without disrupting the cluster.  For example, if
the physical sysid of a node changes it will set off a chain of events
at the route nodes due to the now-mismatched physical sysid and session
sysid.  A message winds up being routed to the wrong target which detects
the misrouting due to the unknown session id.  The error feeds back to
the route node which can then clear its physical sysid cache and relookup
the route.
.Pp
Syslink messages are transactional in nature and it is possible for a single
transaction to be made up of multiple messages... for example, to break down
a large buffer into smaller pieces for the purposes of transmission over the
mesh.  The syslink protocol imposes fairly severe limitations on transactional
messages and sizes... syslink messages are not meant to abstract very large
multi-megabyte I/O operations but instead are meant to provide a reliable
communications abstraction for smaller messages and buffers.
A transaction may contain no more than 32 individual messages, allowing
the route node to use a simple bitmap to track messages which may arrive
out of order.
Any given session may only have one transaction pending at a time... parallel
transactions are implemented by creating multiple sessions between the same
two entities.
.Pp
The messages making up a transaction can arrive out of order and will be
collected by the target until all messages are present.  The originator
must hold onto all messages it sends (so it can re-send if requested by
the route node), until it has the complete response.
The route node for a leaf is responsible for weeding out duplicate messages,
monitoring transactions, and handling timeouts (returning a retry indication
to the leaf).
Route nodes are not responsible for buffering messages.  It is the leaf nodes
that must buffer and collect the messages, the route nodes only track the
transaction.
If the physical sysid becomes invalid the route node is typically responsible
for locating a new physical sysid and returning a transaction abort to the
leaf.
.Pp
Message transactions are uniquely identified by the (sessionid, msgid) fields
in the syslink message.  Bits in the msgid field identify whether a request
is being sent from the originator or target (determined by who initiated the
original 'connection'), and whether the message is a command message or a
reply message.
Either side can initiate a transaction over an established session, which
means that there may be a transaction going in both directions at the same
time, each with request and reply messages.  Transactions initiated by
the target are usually used for event and blocking/unblocking notifications.
.Pp
The SYSLINK protocol is not intended to take the place of a reliable link
level protocol such as TCP and mesh links should only use UDP when packet
delivery can be virtually guarenteed (such as when operating over switched
ethernet).  UDP-based syslinks may still buffer multiple messages within
the limitations of the UDP packet.
.Pp
The SYSLINK protocol is not intended to provide quorum guarentees.  Quorum
protocols operate over SYSLINK, but are not implemented by SYSLINK.
.Sh SYSLINK PROTOCOL - MESSAGE BUFFERING
Syslinks which operate over buffered connections where messages may be
sent or received in bulk must adhere to certain alignment and cross-over
requirements to allow buffers to be implemented as FIFOs.  The message length
field in a syslink message is not particular aligned, but syslink messages
themselves must always be 16-byte aligned, creating small amounts of dead
space in the buffer (and the data stream).  Additionally, the physical
sysid propogation protocol also propogates a FIFO cross-over size, which is
always a power of 2.  Typical values range from 64KB to 1024KB.  Messages
received on a stream can be written into a buffer in FIFO fashion.  No single
message may straddle the end of the FIFO's physical buffer (that is, cross
back over to the beginning).  All transmitters must adhere to the FIFO
size supplied in the initial message traffic by generating a PAD message
when necessary.  Larger FIFO sizes are usually better since they result
in smaller PADs.  I/O transactions containing data are typically broken up
into smaller messages not only to accomodate limitations in transport
protocols (such as UDP), but also to reduce the dead space created by PADs.
On the bright side, these requirements allow very optimal hardware and
software buffering of syslink message traffic.
.Sh BLOCKING TRANSACTIONS
Certain operations can block.  That is, the target may not be able to
immediately complete the requested transaction.  When a transaction blocks
the target is responsible for returning a keep-alive blocking indication
to the originator to prevent the originator from retrying or aborting
the transaction.  Keep-alives can be directly handled by the route node
connected to the target (since it knows if the leaf disconnects),
simplifying leaf operation.  A route node will very occassionally do a sanity
check request to the leaf (perhaps once a minute) to verify that
transactions blocked for a long time are still known to the leaf.
.Pp
Blocking indications are special response messages that set the
blocked-operation bit in the sequence field and do not set the
end-transaction bit.
.Sh TRANSACTION ABORTS
A transaction can be aborted.  Normally aborted transactions still
required an acknowledgement (since the abort may race completion).
If the target completes the transaction before receiving the abort
request, it is as if the abort never occured.
.Sh ASYNCHRONOUS PUSH TRANSACTIONS
Most syslink transactions require an acknowledgement to terminate the
transaction.  The acknowledgement is typically a single message in the
return direction with both the start and stop bits set.  Multi-message
responses are of course possible, such as when the transaction is
implementing an I/O read operation.
.Pp
Certain syslink transactions do not require an acknowledgement and do not
implement the retry or timeout protocols.  Such transactions are typically
cache-push operations which are used to optimize operation of the cluster
by allowing a node to asynchronously push data to places where it thinks
it will be needed immediately.  The most commmon use of this sort of
operation is the read-ahead optimization.  When one node performs a read
transaction with another node, and the target node is capable of read-ahead
and detemines that read-ahead is useful, the target node can initiate the
read-ahead and push the data to the originating node in a separate
asyncnronous transaction.  Read-aheads are typically not directly adjacent
to the read that just occured in order to allow the originator to initiate
the next synchronous transaction without it crossing paths with the
asynchronous read-ahead push (resulting in the same data being returned to
the originator twice).
.Sh OPERATING AS A ROUTE NODE
Most userland applications using syslink will operate as leaf nodes, but
there is nothing preventing you from oprating as a route node.  Operating
as a route node requires implementing all route node requirements including
the handling of logical sysid registrations and the tracking of transactions
initiated by nodes that directly connect to you.  In fact, sysid seeding
nodes are user processes which operate as degenerate route nodes.
.Sh RETURN VALUES
The value -1 is returned if an error occurs in either call.
The external variable
.Va errno
indicates the cause of the error.
If a descriptor is supplied and the system call is successful, 0 is
returned.  If a descriptor is not supplied and the system call is successful,
a descriptor is returned representing a direct connection to the mesh's
route node.
.Sh SEE ALSO
.Sh HISTORY
The
.Fn syslink
function first appeared in
.Dx 1.9 .