From 63d3aa9ab8d8b0b6d8a10362e112a431dcb5b4e9 Mon Sep 17 00:00:00 2001 From: Dimitri Staessens Date: Sun, 10 May 2026 19:06:21 +0200 Subject: lib: Update FRCP implementation The Flow and Retransmission Control Protocol (FRCP) runs end-to-end between two peers over a flow. It provides reliability, in-order delivery, flow control, and liveness. Note that congestion avoidance is orthogonal to FRCP and handled in the IPCP. A fixed 16-octet header, network byte order, is prefixed to every FRCP packet: 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | flags | hcs | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | window | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | seqno | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | ackno | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | payload (variable) ... +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ hcs is a CRC-16-CCITT-FALSE checksum over the PCI (and the stream extension when present), verified before any flag-driven dispatch. A single packet can simultaneously carry DATA + ACK + FC + RXM by OR-ing flag bits. An optional CRC trailer covers the body on DATA when qs.ber == 0, and on every SACK packet; an optional AEAD wrap (per-flow keys) sits outermost. Flag bits (MSB-first; bits 13..15 reserved, MUST be zero): +------+--------+--------+----------------------------------------+ | Bit | Mask | Name | Meaning | +------+--------+--------+----------------------------------------+ | 0 | 0x8000 | DATA | Carries caller payload | | 1 | 0x4000 | DRF | Start of a fresh data run | | 2 | 0x2000 | ACK | ackno field valid | | 3 | 0x1000 | NACK | Pre-DRF nudge (seqno informational) | | 4 | 0x0800 | FC | window field valid (rwe advertisement) | | 5 | 0x0400 | RDVS | Rendezvous probe (window-closed) | | 6 | 0x0200 | FFGM | First Fragment of a multi-fragment SDU | | 7 | 0x0100 | LFGM | Last Fragment of a multi-fragment SDU | | 8 | 0x0080 | RXM | Retransmission | | 9 | 0x0040 | SACK | Block list follows in payload | | 10 | 0x0020 | RTTP | RTT probe / echo (payload follows) | | 11 | 0x0010 | KA | Keepalive | | 12 | 0x0008 | FIN | End of stream marker | | 13-15| -- | -- | Reserved (MUST be zero) | +------+--------+--------+----------------------------------------+ (FFGM, LFGM) encodes the fragment role of a DATA packet (SCTP-style B/E): 11=SOLE, 10=FIRST, 00=MID, 01=LAST. Each fragment carries its own seqno; Retransmission recovers fragments individually, reassembly runs at consume time. In stream mode FFGM/LFGM are unused; per-byte position is carried by the stream extension below and end-of-stream is signalled by FIN on a 0-byte DATA packet. SACK payload (FRCT_ACK | FRCT_FC | FRCT_SACK): 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | n_blocks | padding (2 octets) | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | start[0] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | end[0] | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ ... n_blocks pairs total ... Each block describes a *present* (received) range strictly above the cumulative ACK in the PCI ackno. D-SACK (RFC 2883) is signalled in-band as block[0] - no flag bit, no extra framing - and consumed by the RACK reo_wnd_mult scaler (RFC 8985 sec. 7.2). RTTP payload (FRCT_RTTP only; 24 octets): 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | probe_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | echo_id | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | | + nonce (16 octets, echoed verbatim) + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Stream PCI extension (in_order == STREAM only; 8 octets after the base PCI on every DATA packet): 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | start | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | end | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ start, end are monotonic 32-bit byte offsets; end - start equals the on-wire payload length. Stream mode is negotiated at flow allocation; the extension is present iff stream mode is in use, never on a per-packet basis. Service modes are an orthogonal (in_order, loss, ber) vector selected at flow_alloc; the cubes above map to the axes: +----------------+---------+------+-----+-----------------------+ | Cube | in_order| loss | ber | Engaged | +----------------+---------+------+-----+-----------------------+ | qos_raw | 0 | 1 | 1 | Raw passthrough | | qos_raw_safe | 0 | 1 | 0 | Raw + CRC trailer | | qos_rt | 1 | 1 | 1 | FRCP, no FRTX, no CRC | | qos_rt_safe | 1 | 1 | 0 | FRCP, no FRTX, CRC | | qos_msg | 1 | 0 | 0 | FRCP + FRTX | | qos_stream | 2 | 0 | 0 | FRCP + FRTX, stream | +----------------+---------+------+-----+-----------------------+ in_order=0 sends raw datagrams with no PCI (UDP-equivalent); in_order=1 engages FRCP with SDU framing; in_order=2 (stream) requires loss=0 and is rejected otherwise. loss=0 engages the FRTX retransmit machinery. ber=0 appends the CRC-32 trailer; QOS_DISABLE_CRC at build time forces ber=1 for development. Encryption is a separate per-flow attribute layered as an AEAD wrap outside the FRCP packet. Heritage: delta-t (Watson 1981) supplies timer-based connection management - no SYN/FIN handshake, the DRF marker, the t_mpl / t_a / t_r timers. RINA (Day 2008) supplies the unified flow_alloc(name, qos, ...) primitive and the orthogonal QoS-cube axes. Loss detection follows TCP/QUIC practice (RFCs 2018, 2883, 6582, 6298, 8985); RTT probing is nonce-authenticated like QUIC PATH_CHALLENGE. Adds oftp, a minimal file-transfer tool over an FRCP stream flow. The client reads from stdin or --in FILE and writes through a flow_alloc(qos_stream); the server (--listen) calls flow_accept and writes to stdout or --out FILE. Both sides compute a CRC-64/NVMe over the bytes they handle and print the result. The server rejects flows whose negotiated qs.in_order != STREAM. Two FRCP knobs are exposed via env vars on either side: OFTP_FRCT_RTO_MIN fccntl FRCTSRTOMIN (ns) OFTP_FRCT_STREAM_RING_SZ fccntl FRCTSRRINGSZ (octets) The ocbr_client gains an OCBR_QOS env var to pick the cube the client uses for flow_alloc; recognised values are raw, safe, rt, rt_safe, msg, stream. Unknown values fall back to raw with a warning on stderr. Without the env set behaviour is unchanged. Removes the deprecated lib/timerwheel.c Signed-off-by: Dimitri Staessens Signed-off-by: Sander Vrijders --- include/ouroboros/atomics.h | 1 + include/ouroboros/fccntl.h | 13 ++++++++++ include/ouroboros/np1_flow.h | 2 +- include/ouroboros/qos.h | 57 +++++++++++++++++++++++++------------------- 4 files changed, 48 insertions(+), 25 deletions(-) (limited to 'include') diff --git a/include/ouroboros/atomics.h b/include/ouroboros/atomics.h index 30361fe2..8e667522 100644 --- a/include/ouroboros/atomics.h +++ b/include/ouroboros/atomics.h @@ -27,6 +27,7 @@ #define LOAD_ACQUIRE(p) (__atomic_load_n(p, __ATOMIC_ACQUIRE)) #define LOAD(p) (__atomic_load_n(p, __ATOMIC_SEQ_CST)) +#define STORE_RELAXED(p, v) (__atomic_store_n(p, v, __ATOMIC_RELAXED)) #define STORE_RELEASE(p, v) (__atomic_store_n(p, v, __ATOMIC_RELEASE)) #define STORE(p, v) (__atomic_store_n(p, v, __ATOMIC_SEQ_CST)) diff --git a/include/ouroboros/fccntl.h b/include/ouroboros/fccntl.h index d3baea8f..e91e91dd 100644 --- a/include/ouroboros/fccntl.h +++ b/include/ouroboros/fccntl.h @@ -50,6 +50,12 @@ #define FRCTFRESCNTL 00000002 /* Feedback from receiver */ #define FRCTFLINGER 00000004 /* Send unsent data */ +/* All user-visible bits (readable via FRCTGFLAGS). */ +#define FRCTFMASK (FRCTFRTX | FRCTFRESCNTL | FRCTFLINGER) + +/* Subset writable via FRCTSFLAGS; FRCTFRTX is fixed at flow_alloc. */ +#define FRCTFSETMASK (FRCTFRESCNTL | FRCTFLINGER) + /* Flow operations */ #define FLOWSRCVTIMEO 00000001 /* Set read timeout */ #define FLOWGRCVTIMEO 00000002 /* Get read timeout */ @@ -60,10 +66,17 @@ #define FLOWGFLAGS 00000007 /* Get flags for flow */ #define FLOWGRXQLEN 00000010 /* Get queue length on rx */ #define FLOWGTXQLEN 00000011 /* Get queue length on tx */ +#define FLOWGMTU 00000012 /* Get per-packet MTU */ /* FRCT operations */ #define FRCTSFLAGS 00001000 /* Set flags for FRCT */ #define FRCTGFLAGS 00002000 /* Get flags for FRCT */ +#define FRCTSMAXSDU 00003000 /* Set max recv SDU size */ +#define FRCTGMAXSDU 00004000 /* Get max recv SDU size */ +#define FRCTSRRINGSZ 00005000 /* Set stream rcv ring sz */ +#define FRCTGRRINGSZ 00006000 /* Get stream rcv ring sz */ +#define FRCTSRTOMIN 00007000 /* Set RTO floor (ns) */ +#define FRCTGRTOMIN 00010000 /* Get RTO floor (ns) */ __BEGIN_DECLS diff --git a/include/ouroboros/np1_flow.h b/include/ouroboros/np1_flow.h index 6f341cfc..309d01c2 100644 --- a/include/ouroboros/np1_flow.h +++ b/include/ouroboros/np1_flow.h @@ -37,12 +37,12 @@ int np1_flow_dealloc(int flow_id, time_t timeo); static const qosspec_t qos_np1 = { + .service = SVC_RAW, .delay = UINT32_MAX, .bandwidth = 0, .availability = 0, .loss = UINT32_MAX, .ber = UINT32_MAX, - .in_order = 0, .max_gap = UINT32_MAX, .timeout = 0 }; diff --git a/include/ouroboros/qos.h b/include/ouroboros/qos.h index 6b0bbc17..7980ad00 100644 --- a/include/ouroboros/qos.h +++ b/include/ouroboros/qos.h @@ -28,79 +28,88 @@ #define DEFAULT_PEER_TIMEOUT 120000 +/* qos_spec.service: framing / reliability class. */ +enum qos_service { + SVC_RAW = 0, /* No FRCT; best-effort raw messages */ + SVC_MESSAGE = 1, /* FRCT, reliable ordered messages */ + SVC_STREAM = 2, /* FRCT, reliable ordered byte stream */ +}; + typedef struct qos_spec { + uint8_t service; /* enum qos_service; gates FRCT (>0). */ uint32_t delay; /* In ms. */ uint64_t bandwidth; /* In bits/s. */ uint8_t availability; /* Class of 9s. */ uint32_t loss; /* Packet loss. */ uint32_t ber; /* Bit error rate, errors per billion bits. */ - uint8_t in_order; /* In-order delivery, enables FRCT. */ uint32_t max_gap; /* In ms. */ uint32_t timeout; /* Peer timeout time, in ms, 0 = no timeout. */ } qosspec_t; +/* "_safe" = integrity check (ber=0). "rt" = latency over reliability. */ + static const qosspec_t qos_raw = { + .service = SVC_RAW, .delay = UINT32_MAX, .bandwidth = 0, .availability = 0, .loss = 1, .ber = 1, - .in_order = 0, .max_gap = UINT32_MAX, - .timeout = DEFAULT_PEER_TIMEOUT + .timeout = 0 }; -static const qosspec_t qos_raw_no_errors = { +static const qosspec_t qos_raw_safe = { + .service = SVC_RAW, .delay = UINT32_MAX, .bandwidth = 0, .availability = 0, .loss = 1, .ber = 0, - .in_order = 0, .max_gap = UINT32_MAX, - .timeout = DEFAULT_PEER_TIMEOUT + .timeout = 0 }; -static const qosspec_t qos_best_effort = { - .delay = UINT32_MAX, - .bandwidth = 0, - .availability = 0, +static const qosspec_t qos_rt = { + .service = SVC_MESSAGE, + .delay = 100, + .bandwidth = UINT64_MAX, + .availability = 3, .loss = 1, - .ber = 0, - .in_order = 1, - .max_gap = UINT32_MAX, + .ber = 1, + .max_gap = 100, .timeout = DEFAULT_PEER_TIMEOUT }; -static const qosspec_t qos_video = { +static const qosspec_t qos_rt_safe = { + .service = SVC_MESSAGE, .delay = 100, .bandwidth = UINT64_MAX, .availability = 3, .loss = 1, .ber = 0, - .in_order = 1, .max_gap = 100, .timeout = DEFAULT_PEER_TIMEOUT }; -static const qosspec_t qos_voice = { - .delay = 50, - .bandwidth = 100000, - .availability = 5, - .loss = 1, +static const qosspec_t qos_msg = { + .service = SVC_MESSAGE, + .delay = 1000, + .bandwidth = 0, + .availability = 0, + .loss = 0, .ber = 0, - .in_order = 1, - .max_gap = 50, + .max_gap = 2000, .timeout = DEFAULT_PEER_TIMEOUT }; -static const qosspec_t qos_data = { +static const qosspec_t qos_stream = { + .service = SVC_STREAM, .delay = 1000, .bandwidth = 0, .availability = 0, .loss = 0, .ber = 0, - .in_order = 1, .max_gap = 2000, .timeout = DEFAULT_PEER_TIMEOUT }; -- cgit v1.2.3