ztask: 不依赖操作系统、无堆无锁的定时任务调度器

#ifndef ZTASK_H
#define ZTASK_H

#ifdef __cplusplus
extern "C" {
#endif

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

/**
 * @brief Opaque handle to a task structure.
 */
struct zt_task_s;
typedef struct zt_task_s* zt_task_handle_t;

/**
 * @brief Function pointer type for a task.
 */
typedef void (*zt_func_t)(void);

/**
 * @brief Storage for one task. Callers define their pool as an array of this
 * type: the size follows the pointer width of the target (16 bytes on a
 * 32-bit MCU, 24 bytes on a 64-bit host) and the union supplies alignment.
 */
typedef union zt_task_store_u {
    struct zt_task_s *next;
    void             *p;
    uint32_t          u32;
    uint8_t           raw[2u * sizeof(void *) + 8u];
} zt_task_store_t;

/**
 * @brief Diagnostic counters. Read-only for the caller.
 */
typedef struct {
    uint32_t dispatches;          /**< Task dispatches completed. */
    uint32_t overruns;            /**< Dispatches whose run time reached the period. */
    uint32_t budget_hits;         /**< Poll calls that stopped on the per-call budget. */
    uint32_t rejected_polls;      /**< Re-entrant zt_poll calls refused. */
    uint32_t rejected_unbinds;    /**< zt_unbind calls refused (foreign/stale handle). */
    uint32_t deferred_first_runs; /**< Tasks bound inside a callback, first run deferred. */
} zt_stats_t;

/** Maximum number of tasks one zt_poll call may dispatch. */
#ifndef ZT_POLL_BUDGET
#define ZT_POLL_BUDGET 8u
#endif

int32_t zt_init(void *zt_mem, uint32_t size);
zt_task_handle_t zt_bind(zt_func_t func, uint32_t repeat_ticks, uint32_t delay_ticks);
void zt_unbind(zt_task_handle_t task);
void zt_poll(void);
void zt_tick(void);
uint32_t zt_ticks_to_next_task(void);
uint32_t zt_get_ticks(void);

/** Counters snapshot. Never NULL. */
const zt_stats_t *zt_stats(void);

/** Clears the counters. */
void zt_stats_reset(void);

#ifdef __cplusplus
}
#endif

#endif /* ZTASK_H */

/*
 * ztask.c - Cooperative periodic-task scheduler, with dispatch guards and
 * handle validation.
 *
 * What the hardening buys, per mechanism:
 *   re-entry guard   - a callback may not call zt_poll again; refused and
 *                      counted.
 *   frozen time base - one pass dispatches from one time base; tasks that come
 *                      due *during* the pass wait for the next call.
 *   deferred bind    - a task bound inside a callback is not dispatched in the
 *                      same pass (its first run lies past the frozen base).
 *   budget           - a pass dispatches at most ZT_POLL_BUDGET tasks, so an
 *                      overrunning task can no longer own the main loop.
 *   overrun counter  - a dispatch that took at least one period is counted.
 *   handle checks    - a foreign, misaligned or stale handle is refused instead
 *                      of being linked into the free list twice.
 *   self-cancel      - a task may unbind itself from inside its own callback.
 *
 * The task control block keeps its four 32-bit fields; every addition lives in
 * the scheduler context, so per-task RAM is unchanged at 16 bytes (32-bit).
 */

#include "ztask.h"

typedef struct zt_task_s {
    zt_func_t func;
    uint32_t  repeat_ticks;
    uint32_t  next_schedule;
    struct zt_task_s *next;
} zt_task_t;

_Static_assert(ZT_POLL_BUDGET > 0u, "ztask: poll budget must be non-zero");
_Static_assert(sizeof(zt_task_t) <= sizeof(zt_task_store_t), "ztask: task pool too small");
_Static_assert(_Alignof(zt_task_t) <= _Alignof(zt_task_store_t), "ztask: task pool misaligned");

static struct {
    volatile uint32_t ticks;
    zt_task_t *active_tasks;
    zt_task_t *free_tasks;
    zt_task_t *running;        /* block of the callback in progress, else NULL */
    const uint8_t *pool_base;
    const uint8_t *pool_end;
    uint8_t    in_poll;
    zt_stats_t stats;
} g_ztask_ctx;

/* --- Internal helpers --- */

/* Modular order: true when a lies before b within half of the tick range.
 * This is the only comparison the scheduler is allowed to use on tick values;
 * plain < and > mis-sort the list and mis-compute the sleep length across the
 * 32-bit wrap. */
static bool zt_before(const uint32_t a, const uint32_t b)
{
    return ((int32_t)(a - b) < 0);
}

/* A handle is usable when it points at the start of a block inside our pool. */
static bool zt_handle_ok(const zt_task_t *task)
{
    const uintptr_t handle = (uintptr_t)task;
    const uintptr_t base   = (uintptr_t)g_ztask_ctx.pool_base;

    if ((handle < base) || ((handle - base) % sizeof(zt_task_t) != 0u)) { return false; }
    if (handle + sizeof(zt_task_t) > (uintptr_t)g_ztask_ctx.pool_end) { return false; }
    return true;
}

static void zt_insert_task(zt_task_t * const task)
{
    if ( (g_ztask_ctx.active_tasks == NULL) ||
         zt_before(task->next_schedule, g_ztask_ctx.active_tasks->next_schedule) )
    {
        task->next = g_ztask_ctx.active_tasks;
        g_ztask_ctx.active_tasks = task;
    }
    else
    {
        zt_task_t *current = g_ztask_ctx.active_tasks;
        while ( (current->next != NULL) &&
                zt_before(current->next->next_schedule, task->next_schedule) )
        {
            current = current->next;
        }
        task->next = current->next;
        current->next = task;
    }
}

/* Unlinks task from the active list. Returns false when it is not there. */
static bool zt_list_remove(zt_task_t * const task)
{
    if (g_ztask_ctx.active_tasks == task)
    {
        g_ztask_ctx.active_tasks = task->next;
        return true;
    }
    else
    {
        zt_task_t *current = g_ztask_ctx.active_tasks;
        while ((current != NULL) && (current->next != task))
        {
            current = current->next;
        }
        if (current == NULL)
        {
            return false;
        }
        current->next = task->next;
        return true;
    }
}

static void zt_release_block(zt_task_t * const task)
{
    task->next = g_ztask_ctx.free_tasks;
    g_ztask_ctx.free_tasks = task;
}

/* --- Public API --- */

int32_t zt_init(void * const zt_mem, const uint32_t size)
{
    uint32_t num_tasks;
    uint8_t *mem_ptr;
    zt_task_t *current;
    uint32_t i;

    if ( (zt_mem == NULL) || (size < sizeof(zt_task_t)) )
    {
        return -1;
    }

    mem_ptr   = (uint8_t *)zt_mem;
    num_tasks = size / (uint32_t)sizeof(zt_task_t);

    g_ztask_ctx.ticks        = 0U;
    g_ztask_ctx.active_tasks = NULL;
    g_ztask_ctx.free_tasks   = (zt_task_t *)mem_ptr;
    g_ztask_ctx.running      = NULL;
    g_ztask_ctx.pool_base    = mem_ptr;
    g_ztask_ctx.pool_end     = mem_ptr + (num_tasks * sizeof(zt_task_t));
    g_ztask_ctx.in_poll      = 0U;
    zt_stats_reset();

    current = g_ztask_ctx.free_tasks;
    for (i = 0U; i < (num_tasks - 1U); ++i)
    {
        mem_ptr += sizeof(zt_task_t);
        current->next = (zt_task_t *)mem_ptr;
        current = current->next;
    }
    current->next = NULL;

    return (int32_t)num_tasks;
}

void zt_tick(void)
{
    g_ztask_ctx.ticks++;
}

uint32_t zt_get_ticks(void)
{
    return g_ztask_ctx.ticks;
}

const zt_stats_t *zt_stats(void)
{
    return &g_ztask_ctx.stats;
}

void zt_stats_reset(void)
{
    g_ztask_ctx.stats.dispatches          = 0U;
    g_ztask_ctx.stats.overruns            = 0U;
    g_ztask_ctx.stats.budget_hits         = 0U;
    g_ztask_ctx.stats.rejected_polls      = 0U;
    g_ztask_ctx.stats.rejected_unbinds    = 0U;
    g_ztask_ctx.stats.deferred_first_runs = 0U;
}

zt_task_handle_t zt_bind(zt_func_t const func, const uint32_t repeat_ticks, const uint32_t delay_ticks)
{
    zt_task_t *new_task;
    uint32_t first_delay = delay_ticks;

    if (func == NULL)
    {
        return NULL;
    }

    new_task = g_ztask_ctx.free_tasks;
    if (new_task == NULL)
    {
        return NULL;                      /* pool exhausted */
    }
    g_ztask_ctx.free_tasks = new_task->next;

    /* A task bound from inside a callback must not be dispatched in the same
     * pass: its first due time is pushed past the pass's frozen base. */
    if ( (g_ztask_ctx.in_poll != 0U) && (first_delay == 0U) )
    {
        first_delay = 1U;
        g_ztask_ctx.stats.deferred_first_runs++;
    }

    new_task->func          = func;
    new_task->repeat_ticks  = repeat_ticks;
    new_task->next_schedule = g_ztask_ctx.ticks + first_delay;
    zt_insert_task(new_task);

    return new_task;
}

void zt_unbind(zt_task_handle_t const task)
{
    zt_task_t * const to_remove = (zt_task_t *)task;

    if (task == NULL)
    {
        return;
    }
    if (!zt_handle_ok(to_remove))
    {
        g_ztask_ctx.stats.rejected_unbinds++;   /* foreign or misaligned pointer */
        return;
    }

    /* Self-cancellation from inside the callback: the block is not on the active
     * list at this moment (zt_poll already popped it). Marking it as one-shot
     * makes zt_poll return it to the pool once the callback has returned. */
    if (to_remove == g_ztask_ctx.running)
    {
        to_remove->repeat_ticks = 0U;
        return;
    }

    /* A stale handle - one whose block was already returned - is refused; the
     * block is never linked into the free list twice. */
    if (!zt_list_remove(to_remove))
    {
        g_ztask_ctx.stats.rejected_unbinds++;
        return;
    }

    zt_release_block(to_remove);
}

void zt_poll(void)
{
    uint32_t now;
    uint8_t  budget = (uint8_t)ZT_POLL_BUDGET;

    if (g_ztask_ctx.in_poll != 0U)
    {
        g_ztask_ctx.stats.rejected_polls++;     /* re-entry guard */
        return;
    }
    g_ztask_ctx.in_poll = 1U;

    now = g_ztask_ctx.ticks;                    /* one time base for the pass */

    while (budget > 0U)
    {
        zt_task_t *task = g_ztask_ctx.active_tasks;
        uint32_t started;

        if (task == NULL)
        {
            break;
        }
        if (zt_before(now, task->next_schedule))
        {
            break;                              /* head is not due yet */
        }

        g_ztask_ctx.active_tasks = task->next;
        task->next = NULL;

        g_ztask_ctx.running = task;
        started = g_ztask_ctx.ticks;
        task->func();                           /* the callback must return */
        g_ztask_ctx.running = NULL;

        g_ztask_ctx.stats.dispatches++;

        if (task->repeat_ticks > 0U)
        {
            if ((g_ztask_ctx.ticks - started) >= task->repeat_ticks)
            {
                g_ztask_ctx.stats.overruns++;   /* the task did not complete in time */
            }
            task->next_schedule += task->repeat_ticks;
            zt_insert_task(task);
        }
        else
        {
            zt_release_block(task);
        }

        budget--;
    }

    if ( (budget == 0U) && (g_ztask_ctx.active_tasks != NULL) &&
         (!zt_before(now, g_ztask_ctx.active_tasks->next_schedule)) )
    {
        g_ztask_ctx.stats.budget_hits++;        /* more due work waits for the next call */
    }

    g_ztask_ctx.in_poll = 0U;
}

uint32_t zt_ticks_to_next_task(void)
{
    const zt_task_t *task = g_ztask_ctx.active_tasks;
    uint32_t next_event_in;

    if (task == NULL)
    {
        next_event_in = UINT32_MAX;
    }
    else
    {
        const uint32_t now    = g_ztask_ctx.ticks;
        const uint32_t remain = task->next_schedule - now;

        /* Same convention as the due test in zt_poll: a remainder below 2^31
         * means "still ahead", anything else means "already due". */
        next_event_in = (remain < (UINT32_MAX / 2U)) ? remain : 0U;
    }

    return next_event_in;
}

#include <stdio.h>
#include <time.h>
#include "ztask.h"

#define ZT_MAX_TASKS 8
static zt_task_store_t  zt_pool[ZT_MAX_TASKS];
static zt_task_handle_t h_report;
static zt_task_handle_t h_sample;
static uint32_t         t0_ms;

static uint32_t now_ms(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (uint32_t)(ts.tv_sec * 1000u + ts.tv_nsec / 1000000u);
}

static void task_sample(void) { printf("[%4u] sample\n", zt_get_ticks()); }
static void task_report(void) { printf("[%4u] report\n", zt_get_ticks()); }
static void task_once(void)   { printf("[%4u] once\n",   zt_get_ticks()); }
static void task_stop(void)
{
    printf("[%4u] stop: unbind report\n", zt_get_ticks());
    zt_unbind(h_report);
    h_report = NULL;                       /* the handle is dead after this */
}

int main(void)
{
    t0_ms = now_ms();
    zt_init(zt_pool, sizeof(zt_pool));     /* ticks start at 0, as on a real MCU */

    h_sample = zt_bind(task_sample, 100, 100);
    h_report = zt_bind(task_report, 250, 250);
    zt_bind(task_once, 0, 300);            /* one-shot, handle not kept */
    zt_bind(task_stop, 0, 800);

    while (zt_get_ticks() < 1000u) {
        const uint32_t elapsed = now_ms() - t0_ms;
        while (zt_get_ticks() < elapsed) { zt_tick(); }   /* stand-in for the 1 ms ISR */

        zt_poll();

        const uint32_t sleep_ticks = zt_ticks_to_next_task();
        if (sleep_ticks == UINT32_MAX) { printf("no task left\n"); break; }
        if (sleep_ticks > 0u) {
            struct timespec req = { 0, (long)sleep_ticks * 1000000L };
            nanosleep(&req, NULL);
        }
    }

    zt_unbind(h_sample);
    printf("[%4u] unbind sample, ticks_to_next_task = %u (UINT32_MAX = %u)\n",
           zt_get_ticks(), zt_ticks_to_next_task(), UINT32_MAX);
    return 0;
}

[ 101] sample
[ 200] sample
[ 250] report
[ 300] sample
[ 300] once
[ 400] sample
[ 500] report
[ 500] sample
[ 600] sample
[ 700] sample
[ 750] report
[ 800] sample
[ 800] stop: unbind report
[ 901] sample
[1000] sample
[1000] unbind sample, ticks_to_next_task = 4294967295 (UINT32_MAX = 4294967295)

#include <stdio.h>
#include <stdint.h>
#include "ztask.h"

#define ZT_MAX_TASKS 8
static zt_task_store_t  zt_pool[ZT_MAX_TASKS];

static int  runs;
static void task_periodic(void) { runs++; }
static void task_noop(void) {}

int main(void)
{
    /* V1: a 350-tick stall against a 100-tick period */
    zt_init(zt_pool, sizeof(zt_pool));
    zt_bind(task_periodic, 100, 100);
    while (zt_get_ticks() < 350U) { zt_tick(); }
    zt_poll();
    printf("V1  stall 350 ticks, period 100 -> runs in one poll = %d, next due in %u ticks\n",
           runs, zt_ticks_to_next_task());

    /* V4: unbinding a one-shot task again after it has run */
    zt_init(zt_pool, sizeof(zt_pool));
    zt_task_handle_t h = zt_bind(task_noop, 0, 1);
    zt_tick(); zt_poll();            /* runs once, the block goes back to the pool */
    zt_unbind(h);                    /* the handle is stale */
    zt_task_handle_t p = zt_bind(task_noop, 0, 1000);
    zt_task_handle_t q = zt_bind(task_noop, 0, 1000);
    printf("V4  two binds after the stale unbind -> %s\n",
           (p == q) ? "same block (aliased)" : "two distinct blocks");
    return 0;
}

V1  stall 350 ticks, period 100 -> runs in one poll = 3, next due in 50 ticks
V4  two binds after the stale unbind -> same block (aliased)

V1  stall 350 ticks, period 100 -> runs in one poll = 3, next due in 50 ticks
V4  two binds after the stale unbind -> two distinct blocks