path: root/src/lib/ssm/rbuff.c

/*
 * Ouroboros - Copyright (C) 2016 - 2026
 *
 * Ring buffer implementations for incoming packets
 *
 *    Dimitri Staessens <dimitri@ouroboros.rocks>
 *    Sander Vrijders   <sander@ouroboros.rocks>
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public License
 * version 2.1 as published by the Free Software Foundation.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with this library; if not, write to the Free Software
 * Foundation, Inc., http://www.fsf.org/about/contact/.
 */

#define _POSIX_C_SOURCE 200809L

#include "config.h"
#include "ssm.h"

#include <ouroboros/ssm_rbuff.h>
#include <ouroboros/lockfile.h>
#include <ouroboros/errno.h>
#include <ouroboros/fccntl.h>
#include <ouroboros/pthread.h>
#include <ouroboros/time.h>

#include <assert.h>
#include <fcntl.h>
#include <signal.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>

#define FN_MAX_CHARS 255

#define SSM_RBUFF_FILESIZE ((SSM_RBUFF_SIZE) * sizeof(ssize_t)                 \
                          + 3 * sizeof(size_t)                                 \
                          + sizeof(pthread_mutex_t)                            \
                          + 2 * sizeof(pthread_cond_t))

#define MODB(x)           ((x) & (SSM_RBUFF_SIZE - 1))

#define LOAD_RELAXED(ptr) (__atomic_load_n(ptr, __ATOMIC_RELAXED))
#define LOAD_ACQUIRE(ptr) (__atomic_load_n(ptr, __ATOMIC_ACQUIRE))
#define STORE_RELEASE(ptr, val)                                                \
        (__atomic_store_n(ptr, val, __ATOMIC_RELEASE))
#define STORE_RELAXED(ptr, val)                                                \
        (__atomic_store_n(ptr, val, __ATOMIC_RELAXED))

#define HEAD(rb)       (rb->shm_base[LOAD_RELAXED(rb->head)])
#define TAIL(rb)       (rb->shm_base[LOAD_RELAXED(rb->tail)])
#define HEAD_IDX(rb)   (LOAD_ACQUIRE(rb->head))
#define TAIL_IDX(rb)   (LOAD_ACQUIRE(rb->tail))
#define ADVANCE_HEAD(rb)                                                       \
        (STORE_RELEASE(rb->head, MODB(LOAD_RELAXED(rb->head) + 1)))
#define ADVANCE_TAIL(rb)                                                       \
        (STORE_RELEASE(rb->tail, MODB(LOAD_RELAXED(rb->tail) + 1)))
#define QUEUED(rb)     (MODB(HEAD_IDX(rb) - TAIL_IDX(rb)))
#define IS_FULL(rb)    (QUEUED(rb) == (SSM_RBUFF_SIZE - 1))
#define IS_EMPTY(rb)   (HEAD_IDX(rb) == TAIL_IDX(rb))

/*
 * Occupancy limiter: bound a tx ring by queueing delay instead of
 * slot count, so a slow link does not accumulate seconds of backlog.
 * A zero target is unlimited: the wait predicate then reduces to
 * physical fullness. A ring is unlimited until a target is set.
 */
#define TXQ_MIN_SLOTS   4              /* floor: jitter margin       */
#define TXQ_PRIO_MUL    2              /* headroom kept for retx      */
#define TXQ_SHIFT       2              /* EWMA weight 1/4            */
#define TXQ_SAMPLE_MASK 15             /* resample every 16 writes   */
#define TXQ_MIN_DT_NS   10000LL        /* skip sub-10us samples      */

#define TXQ_UNLIMITED (SSM_RBUFF_SIZE - 1)

struct ssm_rbuff {
        ssize_t *         shm_base;     /* start of shared memory   */
        size_t *          head;         /* start of ringbuffer      */
        size_t *          tail;
        size_t *          flags;        /* out-of-band flags (RB_*) */
        pthread_mutex_t * mtx;          /* lock for cond vars only  */
        pthread_cond_t *  add;          /* signal when new data     */
        pthread_cond_t *  del;          /* signal when data removed */
        pid_t             pid;          /* pid of the owner         */
        int               flow_id;      /* flow_id of the flow      */
        size_t            n_users;      /* in-flight users          */
        uint64_t          txq_target;   /* target queue delay, ns   */
        size_t            txq_limit;    /* current occupancy limit  */
        int64_t           txq_rate;     /* EWMA drain rate, slots/s */
        uint64_t          txq_ns;       /* last sample time, ns     */
        size_t            txq_wr;       /* writes since last sample */
        size_t            txq_q0;       /* queued count at sample   */
};

#define TXQ_ON(rb)    (LOAD_RELAXED(&(rb)->txq_target) != 0)
#define TXQ_LIMIT(rb) (TXQ_ON(rb) ? LOAD_RELAXED(&(rb)->txq_limit)         \
                                  : TXQ_UNLIMITED)
#define OVER_LIMIT(rb) (QUEUED(rb) >= TXQ_LIMIT(rb))


#define MM_FLAGS (PROT_READ | PROT_WRITE)

static struct ssm_rbuff * rbuff_create(pid_t pid,
                                       int   flow_id,
                                       int   flags)
{
        struct ssm_rbuff * rb;
        int                fd;
        ssize_t *          shm_base;
        char               fn[FN_MAX_CHARS];

        sprintf(fn, SSM_RBUFF_PREFIX "%d.%d", pid, flow_id);

        rb = malloc(sizeof(*rb));
        if (rb == NULL)
                goto fail_malloc;

        fd = shm_open(fn, flags, 0666);
        if (fd == -1)
                goto fail_open;

        if ((flags & O_CREAT) && ftruncate(fd, SSM_RBUFF_FILESIZE) < 0)
                goto fail_truncate;

        shm_base = mmap(NULL, SSM_RBUFF_FILESIZE, MM_FLAGS, MAP_SHARED, fd, 0);

        close(fd);

        rb->shm_base = shm_base;
        rb->head     = (size_t *) (rb->shm_base + (SSM_RBUFF_SIZE));
        rb->tail     = (size_t *) (rb->head + 1);
        rb->flags      = (size_t *) (rb->tail + 1);
        rb->mtx      = (pthread_mutex_t *) (rb->flags + 1);
        rb->add      = (pthread_cond_t *) (rb->mtx + 1);
        rb->del      = rb->add + 1;
        rb->pid      = pid;
        rb->flow_id  = flow_id;
        rb->n_users  = 0;
        rb->txq_target = 0;         /* unlimited until set */
        rb->txq_limit = TXQ_UNLIMITED;
        rb->txq_rate = 0;
        rb->txq_ns   = 0;
        rb->txq_wr   = 0;
        rb->txq_q0   = 0;

        return rb;

 fail_truncate:
        close(fd);
        if (flags & O_CREAT)
                shm_unlink(fn);
 fail_open:
        free(rb);
 fail_malloc:
        return NULL;
}

static void rbuff_destroy(struct ssm_rbuff * rb)
{
        munmap(rb->shm_base, SSM_RBUFF_FILESIZE);

        free(rb);
}

struct ssm_rbuff * ssm_rbuff_create(pid_t pid,
                                    int   flow_id)
{
        struct ssm_rbuff *  rb;
        pthread_mutexattr_t mattr;
        pthread_condattr_t  cattr;
        mode_t              mask;

        mask = umask(0);

        rb = rbuff_create(pid, flow_id, O_CREAT | O_EXCL | O_RDWR);

        umask(mask);

        if (rb == NULL)
                goto fail_rb;

        if (pthread_mutexattr_init(&mattr))
                goto fail_mattr;

        pthread_mutexattr_setpshared(&mattr, PTHREAD_PROCESS_SHARED);
#ifdef HAVE_ROBUST_MUTEX
        pthread_mutexattr_setrobust(&mattr, PTHREAD_MUTEX_ROBUST);
#endif
        if (pthread_mutex_init(rb->mtx, &mattr))
                goto fail_mutex;

        if (pthread_condattr_init(&cattr))
                goto fail_cattr;

        pthread_condattr_setpshared(&cattr, PTHREAD_PROCESS_SHARED);
#ifndef __APPLE__
        pthread_condattr_setclock(&cattr, PTHREAD_COND_CLOCK);
#endif
        if (pthread_cond_init(rb->add, &cattr))
                goto fail_add;

        if (pthread_cond_init(rb->del, &cattr))
                goto fail_del;

        *rb->flags  = RB_RDWR;
        *rb->head = 0;
        *rb->tail = 0;

        rb->pid     = pid;
        rb->flow_id = flow_id;

        pthread_mutexattr_destroy(&mattr);
        pthread_condattr_destroy(&cattr);

        return rb;

 fail_del:
        pthread_cond_destroy(rb->add);
 fail_add:
        pthread_condattr_destroy(&cattr);
 fail_cattr:
        pthread_mutex_destroy(rb->mtx);
 fail_mutex:
        pthread_mutexattr_destroy(&mattr);
 fail_mattr:
        ssm_rbuff_destroy(rb);
 fail_rb:
        return NULL;
}

void ssm_rbuff_destroy(struct ssm_rbuff * rb)
{
        char fn[FN_MAX_CHARS];

        assert(rb != NULL);

        sprintf(fn, SSM_RBUFF_PREFIX "%d.%d", rb->pid, rb->flow_id);

        ssm_rbuff_close(rb);

        shm_unlink(fn);
}

struct ssm_rbuff * ssm_rbuff_open(pid_t pid,
                                  int   flow_id)
{
        return rbuff_create(pid, flow_id, O_RDWR);
}

void ssm_rbuff_close(struct ssm_rbuff * rb)
{
        assert(rb);

        /*
         * Caller must set RB_FLOWDOWN first; if a user becomes
         * cancellable, push a cleanup that decrements n_users.
         */
        while (__atomic_load_n(&rb->n_users, __ATOMIC_SEQ_CST) > 0) {
                struct timespec tic = { 0, 100000 };
                nanosleep(&tic, NULL);
        }

        rbuff_destroy(rb);
}

/* Cancel cleanup for a blocked reader: unlock mtx AND drop the n_users ref. */
static void __cleanup_rbuff_reader(void * o)
{
        struct ssm_rbuff * rb = (struct ssm_rbuff *) o;

        pthread_mutex_unlock(rb->mtx);
        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
}

/*
 * Refresh the drain-rate estimate and derived occupancy limit.
 * Called with rb->mtx held, at most once per TXQ_SAMPLE_MASK writes.
 */
static void rbuff_txq_sample(struct ssm_rbuff * rb,
                             size_t             queued)
{
        struct timespec now;
        uint64_t        now_ns;
        uint64_t        last_ns;
        int64_t         dt_ns;
        int64_t         written;
        int64_t         grown;
        int64_t         drained;
        int64_t         sample_rate;
        int64_t         rate;
        int64_t         target;
        size_t          limit;

        clock_gettime(PTHREAD_COND_CLOCK, &now);

        now_ns = TS_TO_UINT64(now);

        last_ns = LOAD_RELAXED(&rb->txq_ns);
        if (last_ns == 0) {
                /* No prior sample: seed and stay at the default limit. */
                STORE_RELAXED(&rb->txq_ns, now_ns);
                STORE_RELAXED(&rb->txq_q0, queued);
                STORE_RELAXED(&rb->txq_wr, 0);
                return;
        }

        dt_ns = (int64_t) (now_ns - last_ns);
        if (dt_ns < TXQ_MIN_DT_NS)
                return;

        written = (int64_t) LOAD_RELAXED(&rb->txq_wr);
        grown   = (int64_t) queued - (int64_t) LOAD_RELAXED(&rb->txq_q0);

        drained = written - grown;
        if (drained < 0)
                drained = 0;

        sample_rate = drained * BILLION / dt_ns;

        rate  = LOAD_RELAXED(&rb->txq_rate);
        rate += (sample_rate - rate) >> TXQ_SHIFT;
        if (rate < 0)
                rate = 0;

        target = (int64_t) LOAD_RELAXED(&rb->txq_target);

        limit  = (size_t) (rate * target / BILLION);
        if (limit < TXQ_MIN_SLOTS)
                limit = TXQ_MIN_SLOTS;

        if (limit > TXQ_UNLIMITED)
                limit = TXQ_UNLIMITED;

        STORE_RELAXED(&rb->txq_rate, rate);
        STORE_RELAXED(&rb->txq_limit, limit);
        STORE_RELAXED(&rb->txq_ns, now_ns);
        STORE_RELAXED(&rb->txq_q0, queued);
        STORE_RELAXED(&rb->txq_wr, 0);
}

/* Bumps the write counter, resampling every TXQ_SAMPLE_MASK writes. */
static void rbuff_txq_touch(struct ssm_rbuff * rb)
{
        size_t wr;

        wr = LOAD_RELAXED(&rb->txq_wr) + 1;

        STORE_RELAXED(&rb->txq_wr, wr);

        if ((wr & TXQ_SAMPLE_MASK) == 0)
                rbuff_txq_sample(rb, QUEUED(rb));
}

/*
 * A retransmission outranks new data but stays bounded: its ceiling is
 * a multiple of the limit, so the headroom above it is reserved and the
 * queueing delay stays within a known factor of the target.
 */
static size_t rbuff_txq_prio_limit(struct ssm_rbuff * rb)
{
        size_t lim;

        if (!TXQ_ON(rb))
                return TXQ_UNLIMITED;

        lim = LOAD_RELAXED(&rb->txq_limit) * TXQ_PRIO_MUL;

        return lim > TXQ_UNLIMITED ? TXQ_UNLIMITED : lim;
}

/* prio outranks new data up to its own, higher, ceiling. */
static int rbuff_write_nb(struct ssm_rbuff * rb,
                          size_t             off,
                          bool               prio)
{
        size_t flags;
        bool   was_empty;
        int    ret = 0;

        assert(rb != NULL);

        __atomic_fetch_add(&rb->n_users, 1, __ATOMIC_SEQ_CST);

        flags = __atomic_load_n(rb->flags, __ATOMIC_SEQ_CST);
        if (flags != RB_RDWR) {
                if (flags & RB_FLOWDOWN) {
                        ret = -EFLOWDOWN;
                        goto fail_flags;
                }
                if (!(flags & RB_WR)) {
                        ret = -ENOTALLOC;
                        goto fail_flags;
                }
        }

        robust_mutex_lock(rb->mtx);

        if (QUEUED(rb) >= (prio ? rbuff_txq_prio_limit(rb)
                                : TXQ_LIMIT(rb))) {
                ret = -EAGAIN;
                goto fail_mutex;
        }

        was_empty = IS_EMPTY(rb);

        HEAD(rb) = (ssize_t) off;
        ADVANCE_HEAD(rb);

        if (was_empty)
                pthread_cond_broadcast(rb->add);

        /* Only an enqueue feeds the estimator; a refusal wrote nothing. */
        if (TXQ_ON(rb))
                rbuff_txq_touch(rb);

        pthread_mutex_unlock(rb->mtx);

        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
        return 0;

 fail_mutex:
        pthread_mutex_unlock(rb->mtx);
 fail_flags:
        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
        return ret;
}

int ssm_rbuff_write(struct ssm_rbuff * rb,
                    size_t             off)
{
        return rbuff_write_nb(rb, off, false);
}

/* For a packet the peer is already waiting on; skips the limit. */
int ssm_rbuff_write_prio(struct ssm_rbuff * rb,
                         size_t             off)
{
        return rbuff_write_nb(rb, off, true);
}

int ssm_rbuff_write_b(struct ssm_rbuff *      rb,
                      size_t                  off,
                      const struct timespec * abstime)
{
        size_t flags;
        int    ret = 0;
        bool   was_empty;

        assert(rb != NULL);

        __atomic_fetch_add(&rb->n_users, 1, __ATOMIC_SEQ_CST);

        flags = __atomic_load_n(rb->flags, __ATOMIC_SEQ_CST);
        if (flags != RB_RDWR) {
                if (flags & RB_FLOWDOWN) {
                        ret = -EFLOWDOWN;
                        goto fail_flags;
                }
                if (!(flags & RB_WR)) {
                        ret = -ENOTALLOC;
                        goto fail_flags;
                }
        }

        robust_mutex_lock(rb->mtx);

        pthread_cleanup_push(__cleanup_rbuff_reader, rb);

        while (OVER_LIMIT(rb) && ret != -ETIMEDOUT) {
                flags = __atomic_load_n(rb->flags, __ATOMIC_SEQ_CST);
                if (flags & RB_FLOWDOWN) {
                        ret = -EFLOWDOWN;
                        break;
                }
                ret = -robust_wait(rb->del, rb->mtx, abstime);
        }

        pthread_cleanup_pop(false);

        if (ret != -ETIMEDOUT && ret != -EFLOWDOWN) {
                was_empty = IS_EMPTY(rb);
                HEAD(rb) = (ssize_t) off;
                ADVANCE_HEAD(rb);
                if (was_empty)
                        pthread_cond_broadcast(rb->add);

                if (TXQ_ON(rb))
                        rbuff_txq_touch(rb);
        }

        pthread_mutex_unlock(rb->mtx);

 fail_flags:
        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
        return ret;
}

static int check_rb_flags(struct ssm_rbuff * rb)
{
        size_t flags;

        assert(rb != NULL);

        flags = __atomic_load_n(rb->flags, __ATOMIC_SEQ_CST);

        if (flags & RB_FLOWDOWN)
                return -EFLOWDOWN;

        if (flags & RB_FLOWPEER)
                return -EFLOWPEER;

        if (!(flags & RB_RD))
                return -ENOTALLOC;

        return -EAGAIN;
}

ssize_t ssm_rbuff_read(struct ssm_rbuff * rb)
{
        ssize_t ret;

        assert(rb != NULL);

        __atomic_fetch_add(&rb->n_users, 1, __ATOMIC_SEQ_CST);

        if (IS_EMPTY(rb)) {
                ret = check_rb_flags(rb);
                goto out;
        }

        robust_mutex_lock(rb->mtx);

        if (IS_EMPTY(rb)) {
                pthread_mutex_unlock(rb->mtx);
                ret = check_rb_flags(rb);
                goto out;
        }

        ret = TAIL(rb);
        ADVANCE_TAIL(rb);

        pthread_cond_broadcast(rb->del);

        pthread_mutex_unlock(rb->mtx);

 out:
        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
        return ret;
}

ssize_t ssm_rbuff_read_b(struct ssm_rbuff *      rb,
                         const struct timespec * abstime)
{
        ssize_t idx = -1;
        size_t  flags;

        assert(rb != NULL);

        __atomic_fetch_add(&rb->n_users, 1, __ATOMIC_SEQ_CST);

        flags = __atomic_load_n(rb->flags, __ATOMIC_SEQ_CST);
        if (IS_EMPTY(rb) && (flags & RB_FLOWDOWN)) {
                idx = -EFLOWDOWN;
                goto out;
        }

        robust_mutex_lock(rb->mtx);

        pthread_cleanup_push(__cleanup_rbuff_reader, rb);

        while (IS_EMPTY(rb) &&
               idx != -ETIMEDOUT &&
               check_rb_flags(rb) == -EAGAIN) {
                idx = -robust_wait(rb->add, rb->mtx, abstime);
        }

        pthread_cleanup_pop(false);

        if (!IS_EMPTY(rb)) {
                idx = TAIL(rb);
                ADVANCE_TAIL(rb);
                pthread_cond_broadcast(rb->del);
        } else if (idx != -ETIMEDOUT) {
                idx = check_rb_flags(rb);
        }

        pthread_mutex_unlock(rb->mtx);

        assert(idx != -EAGAIN);

 out:
        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
        return idx;
}

void ssm_rbuff_set_bits(struct ssm_rbuff * rb,
                        uint32_t           bits)
{
        assert(rb != NULL);

        robust_mutex_lock(rb->mtx);
        __atomic_fetch_or(rb->flags, (size_t) bits, __ATOMIC_SEQ_CST);
        pthread_cond_broadcast(rb->add);
        pthread_cond_broadcast(rb->del);
        pthread_mutex_unlock(rb->mtx);
}

void ssm_rbuff_clr_bits(struct ssm_rbuff * rb,
                        uint32_t           bits)
{
        assert(rb != NULL);

        robust_mutex_lock(rb->mtx);
        __atomic_fetch_and(rb->flags, ~(size_t) bits, __ATOMIC_SEQ_CST);
        pthread_cond_broadcast(rb->add);
        pthread_cond_broadcast(rb->del);
        pthread_mutex_unlock(rb->mtx);
}

uint32_t ssm_rbuff_get_flags(struct ssm_rbuff * rb)
{
        assert(rb != NULL);

        return (uint32_t) __atomic_load_n(rb->flags, __ATOMIC_SEQ_CST);
}

/* Current occupancy limit; SSM_RBUFF_SIZE - 1 when unlimited. */
size_t ssm_rbuff_get_limit(struct ssm_rbuff * rb)
{
        assert(rb != NULL);

        return TXQ_LIMIT(rb);
}

/* Target queueing delay; a zero target is unlimited. */
void ssm_rbuff_set_txq_target(struct ssm_rbuff *      rb,
                              const struct timespec * ts)
{
        assert(rb != NULL);
        assert(ts != NULL);

        STORE_RELAXED(&rb->txq_limit, TXQ_UNLIMITED);
        STORE_RELAXED(&rb->txq_rate, 0);
        STORE_RELAXED(&rb->txq_ns, 0);
        STORE_RELAXED(&rb->txq_wr, 0);
        STORE_RELAXED(&rb->txq_q0, 0);

        STORE_RELAXED(&rb->txq_target, TS_TO_UINT64(*ts));
}

/* Current target queueing delay for the tx occupancy limiter. */
void ssm_rbuff_get_txq_target(struct ssm_rbuff * rb,
                              struct timespec *  ts)
{
        assert(rb != NULL);
        assert(ts != NULL);

        UINT64_TO_TS(LOAD_RELAXED(&rb->txq_target), ts);
}

void ssm_rbuff_fini(struct ssm_rbuff * rb)
{
        assert(rb != NULL);

        __atomic_fetch_add(&rb->n_users, 1, __ATOMIC_SEQ_CST);

        robust_mutex_lock(rb->mtx);

        pthread_cleanup_push(__cleanup_rbuff_reader, rb);

        while (!IS_EMPTY(rb))
                robust_wait(rb->del, rb->mtx, NULL);

        pthread_cleanup_pop(false);

        pthread_mutex_unlock(rb->mtx);

        __atomic_fetch_sub(&rb->n_users, 1, __ATOMIC_SEQ_CST);
}

size_t ssm_rbuff_queued(struct ssm_rbuff * rb)
{
        assert(rb != NULL);

        return QUEUED(rb);
}

int ssm_rbuff_mlock(struct ssm_rbuff * rb)
{
        assert(rb != NULL);

        return mlock(rb->shm_base, SSM_RBUFF_FILESIZE);
}