1/*
2 * Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 */
6
7#pragma once
8/* This header presents the interface for sporadic servers,
9 * implemented according to Stankcovich et. al in
10 * "Defects of the POSIX Spoardic Server and How to correct them",
11 * although without the priority management.
12 *
13 * Briefly, a sporadic server is a period and a queue of refills. Each
14 * refill consists of an amount, and a period. No thread is allowed to consume
15 * more than amount ticks per period.
16 *
17 * The sum of all refill amounts in the refill queue is always the budget of the scheduling context -
18 * that is it should never change, unless it is being updated / configured.
19 *
20 * Every time budget is consumed, that amount of budget is scheduled
21 * for reuse in period time. If the refill queue is full (the queue's
22 * minimum size is 2, and can be configured by the user per scheduling context
23 * above this) the next refill is merged.
24 */
25#include <config.h>
26#include <types.h>
27#include <util.h>
28#include <object/structures.h>
29#include <machine/timer.h>
30#include <model/statedata.h>
31
32/* To do an operation in the kernel, the thread must have
33 * at least this much budget - see comment on refill_sufficient */
34#define MIN_BUDGET_US (2u * getKernelWcetUs() * CONFIG_KERNEL_WCET_SCALE)
35#define MIN_BUDGET    (2u * getKernelWcetTicks() * CONFIG_KERNEL_WCET_SCALE)
36#if (CONFIG_KERNEL_STATIC_MAX_BUDGET_US) != 0
37#define MAX_BUDGET_US (CONFIG_KERNEL_STATIC_MAX_BUDGET_US)
38#else
39#define MAX_BUDGET_US getMaxUsToTicks()
40#endif /* CONFIG_KERNEL_STATIC_MAX_BUDGET_US != 0 */
41
42/* Short hand for accessing refill queue items */
43static inline refill_t *refill_index(sched_context_t *sc, word_t index)
44{
45    return ((refill_t *)(SC_REF(sc) + sizeof(sched_context_t))) + index;
46}
47static inline refill_t *refill_head(sched_context_t *sc)
48{
49    return refill_index(sc, sc->scRefillHead);
50}
51static inline refill_t *refill_tail(sched_context_t *sc)
52{
53    return refill_index(sc, sc->scRefillTail);
54}
55
56
57/* Scheduling context objects consist of a sched_context_t at the start, followed by a
58 * circular buffer of refills. As scheduling context objects are of variable size, the
59 * amount of refill_ts that can fit into a scheduling context object is also variable.
60 *
61 * @return the maximum number of refill_t data structures that can fit into this
62 * specific scheduling context object.
63 */
64static inline word_t refill_absolute_max(cap_t sc_cap)
65{
66    return (BIT(cap_sched_context_cap_get_capSCSizeBits(sc_cap)) - sizeof(sched_context_t)) / sizeof(refill_t);
67}
68
69/* @return the current amount of empty slots in the refill buffer */
70static inline word_t refill_size(sched_context_t *sc)
71{
72    if (sc->scRefillHead <= sc->scRefillTail) {
73        return (sc->scRefillTail - sc->scRefillHead + 1u);
74    }
75    return sc->scRefillTail + 1u + (sc->scRefillMax - sc->scRefillHead);
76}
77
78/* @return true if the circular buffer of refills is current full (all slots in the
79 * buffer are currently being used */
80static inline bool_t refill_full(sched_context_t *sc)
81{
82    return refill_size(sc) == sc->scRefillMax;
83}
84
85/* @return true if the ciruclar buffer only contains 1 used slot */
86static inline bool_t refill_single(sched_context_t *sc)
87{
88    return sc->scRefillHead == sc->scRefillTail;
89}
90
91/* Return the amount of budget this scheduling context
92 * has available if usage is charged to it. */
93static inline ticks_t refill_capacity(sched_context_t *sc, ticks_t usage)
94{
95    if (unlikely(usage > refill_head(sc)->rAmount)) {
96        return 0;
97    }
98
99    return refill_head(sc)->rAmount - usage;
100}
101
102/*
103 * Return true if the head refill has sufficient capacity
104 * to enter and exit the kernel after usage is charged to it.
105 */
106static inline bool_t refill_sufficient(sched_context_t *sc, ticks_t usage)
107{
108    return refill_capacity(sc, usage) >= MIN_BUDGET;
109}
110
111/*
112 * Return true if the head refill is eligible to be used.
113 * This indicates if the thread bound to the sc can be placed
114 * into the scheduler, otherwise it needs to go into the release queue
115 * to wait.
116 */
117static inline bool_t refill_ready(sched_context_t *sc)
118{
119    return refill_head(sc)->rTime <= (NODE_STATE_ON_CORE(ksCurTime, sc->scCore) + getKernelWcetTicks());
120}
121
122/* Create a new refill in a non-active sc */
123#ifdef ENABLE_SMP_SUPPORT
124void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period, word_t core);
125#define REFILL_NEW(sc, max_refills, budget, period, core) refill_new(sc, max_refills, budget, period, core)
126#else
127void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period);
128#define REFILL_NEW(sc, max_refills, budget, period, core) refill_new(sc, max_refills, budget, period)
129#endif
130
131/* Update refills in an active sc without violating bandwidth constraints */
132void refill_update(sched_context_t *sc, ticks_t new_period, ticks_t new_budget, word_t new_max_refills);
133
134
135/* Charge `usage` to the current scheduling context.
136 * This function should only be called only when charging `used` will deplete
137 * the head refill, resulting in refill_sufficient failing.
138 *
139 * @param usage the amount of time to charge.
140 */
141void refill_budget_check(ticks_t used);
142
143/*
144 * Charge a the current scheduling context `used` amount from its
145 * current refill. This will split the refill, leaving whatever is
146 * left over at the head of the refill. This is only called when charging
147 * `used` will not deplete the head refill.
148 */
149void refill_split_check(ticks_t used);
150
151/*
152 * This is called when a thread is eligible to start running: it
153 * iterates through the refills queue and merges any
154 * refills that overlap.
155 */
156void refill_unblock_check(sched_context_t *sc);
157
158