1/*
2 * Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 */
6
7#include <types.h>
8#include <api/failures.h>
9#include <object/structures.h>
10
11/* functions to manage the circular buffer of
12 * sporadic budget replenishments (refills for short).
13 *
14 * The circular buffer always has at least one item in it.
15 *
16 * Items are appended at the tail (the back) and
17 * removed from the head (the front). Below is
18 * an example of a queue with 4 items (h = head, t = tail, x = item, [] = slot)
19 * and max size 8.
20 *
21 * [][h][x][x][t][][][]
22 *
23 * and another example of a queue with 5 items
24 *
25 * [x][t][][][][h][x][x]
26 *
27 * The queue has a minimum size of 1, so it is possible that h == t.
28 *
29 * The queue is implemented as head + tail rather than head + size as
30 * we cannot use the mod operator on all architectures without accessing
31 * the fpu or implementing divide.
32 */
33
34/* return the index of the next item in the refill queue */
35static inline word_t refill_next(sched_context_t *sc, word_t index)
36{
37    return (index == sc->scRefillMax - 1u) ? (0) : index + 1u;
38}
39
40#ifdef CONFIG_PRINTING
41/* for debugging */
42UNUSED static inline void print_index(sched_context_t *sc, word_t index)
43{
44
45    printf("index %lu, Amount: %llx, time %llx\n", index, refill_index(sc, index)->rAmount,
46           refill_index(sc, index)->rTime);
47}
48
49UNUSED static inline void refill_print(sched_context_t *sc)
50{
51    printf("Head %lu tail %lu\n", sc->scRefillHead, sc->scRefillTail);
52    word_t current = sc->scRefillHead;
53    /* always print the head */
54    print_index(sc, current);
55
56    while (current != sc->scRefillTail) {
57        current = refill_next(sc, current);
58        print_index(sc, current);
59    }
60
61}
62#endif /* CONFIG_PRINTING */
63#ifdef CONFIG_DEBUG_BUILD
64/* check a refill queue is ordered correctly */
65static UNUSED bool_t refill_ordered(sched_context_t *sc)
66{
67    word_t current = sc->scRefillHead;
68    word_t next = refill_next(sc, sc->scRefillHead);
69
70    while (current != sc->scRefillTail) {
71        if (!(refill_index(sc, current)->rTime <= refill_index(sc, next)->rTime)) {
72            refill_print(sc);
73            return false;
74        }
75        current = next;
76        next = refill_next(sc, current);
77    }
78
79    return true;
80}
81
82#define REFILL_SANITY_START(sc) ticks_t _sum = refill_sum(sc); assert(refill_ordered(sc));
83#define REFILL_SANITY_CHECK(sc, budget) \
84    do { \
85        assert(refill_sum(sc) == budget); assert(refill_ordered(sc)); \
86    } while (0)
87
88#define REFILL_SANITY_END(sc) \
89    do {\
90        REFILL_SANITY_CHECK(sc, _sum);\
91    } while (0)
92#else
93#define REFILL_SANITY_START(sc)
94#define REFILL_SANITY_CHECK(sc, budget)
95#define REFILL_SANITY_END(sc)
96#endif /* CONFIG_DEBUG_BUILD */
97
98/* compute the sum of a refill queue */
99static UNUSED ticks_t refill_sum(sched_context_t *sc)
100{
101    ticks_t sum = refill_head(sc)->rAmount;
102    word_t current = sc->scRefillHead;
103
104    while (current != sc->scRefillTail) {
105        current = refill_next(sc, current);
106        sum += refill_index(sc, current)->rAmount;
107    }
108
109    return sum;
110}
111
112/* pop head of refill queue */
113static inline refill_t refill_pop_head(sched_context_t *sc)
114{
115    /* queues cannot be smaller than 1 */
116    assert(!refill_single(sc));
117
118    UNUSED word_t prev_size = refill_size(sc);
119    refill_t refill = *refill_head(sc);
120    sc->scRefillHead = refill_next(sc, sc->scRefillHead);
121
122    /* sanity */
123    assert(prev_size == (refill_size(sc) + 1));
124    assert(sc->scRefillHead < sc->scRefillMax);
125    return refill;
126}
127
128/* add item to tail of refill queue */
129static inline void refill_add_tail(sched_context_t *sc, refill_t refill)
130{
131    /* cannot add beyond queue size */
132    assert(refill_size(sc) < sc->scRefillMax);
133
134    word_t new_tail = refill_next(sc, sc->scRefillTail);
135    sc->scRefillTail = new_tail;
136    *refill_tail(sc) = refill;
137
138    /* sanity */
139    assert(new_tail < sc->scRefillMax);
140}
141
142static inline void maybe_add_empty_tail(sched_context_t *sc)
143{
144    if (isRoundRobin(sc)) {
145        /* add an empty refill - we track the used up time here */
146        refill_t empty_tail = { .rTime = NODE_STATE(ksCurTime)};
147        refill_add_tail(sc, empty_tail);
148        assert(refill_size(sc) == MIN_REFILLS);
149    }
150}
151
152#ifdef ENABLE_SMP_SUPPORT
153void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period, word_t core)
154#else
155void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period)
156#endif
157{
158    sc->scPeriod = period;
159    sc->scRefillHead = 0;
160    sc->scRefillTail = 0;
161    sc->scRefillMax = max_refills;
162    assert(budget > MIN_BUDGET);
163    /* full budget available */
164    refill_head(sc)->rAmount = budget;
165    /* budget can be used from now */
166    refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, core);
167    maybe_add_empty_tail(sc);
168    REFILL_SANITY_CHECK(sc, budget);
169}
170
171void refill_update(sched_context_t *sc, ticks_t new_period, ticks_t new_budget, word_t new_max_refills)
172{
173
174    /* refill must be initialised in order to be updated - otherwise refill_new should be used */
175    assert(sc->scRefillMax > 0);
176
177    /* this is called on an active thread. We want to preserve the sliding window constraint -
178     * so over new_period, new_budget should not be exceeded even temporarily */
179
180    /* move the head refill to the start of the list - it's ok as we're going to truncate the
181     * list to size 1 - and this way we can't be in an invalid list position once new_max_refills
182     * is updated */
183    *refill_index(sc, 0) = *refill_head(sc);
184    sc->scRefillHead = 0;
185    /* truncate refill list to size 1 */
186    sc->scRefillTail = sc->scRefillHead;
187    /* update max refills */
188    sc->scRefillMax = new_max_refills;
189    /* update period */
190    sc->scPeriod = new_period;
191
192    if (refill_ready(sc)) {
193        refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, sc->scCore);
194    }
195
196    if (refill_head(sc)->rAmount >= new_budget) {
197        /* if the heads budget exceeds the new budget just trim it */
198        refill_head(sc)->rAmount = new_budget;
199        maybe_add_empty_tail(sc);
200    } else {
201        /* otherwise schedule the rest for the next period */
202        refill_t new = { .rAmount = (new_budget - refill_head(sc)->rAmount),
203                         .rTime = refill_head(sc)->rTime + new_period
204                       };
205        refill_add_tail(sc, new);
206    }
207
208    REFILL_SANITY_CHECK(sc, new_budget);
209}
210
211static inline void schedule_used(sched_context_t *sc, refill_t new)
212{
213    /* schedule the used amount */
214    if (new.rAmount < MIN_BUDGET && !refill_single(sc)) {
215        /* used amount is to small - merge with last and delay */
216        refill_tail(sc)->rAmount += new.rAmount;
217        refill_tail(sc)->rTime = MAX(new.rTime, refill_tail(sc)->rTime);
218    } else if (new.rTime <= refill_tail(sc)->rTime) {
219        refill_tail(sc)->rAmount += new.rAmount;
220    } else {
221        refill_add_tail(sc, new);
222    }
223}
224
225static inline void ensure_sufficient_head(sched_context_t *sc)
226{
227    /* ensure the refill head is sufficient, such that when we wake in awaken,
228     * there is enough budget to run */
229    while (refill_head(sc)->rAmount < MIN_BUDGET || refill_full(sc)) {
230        refill_t refill = refill_pop_head(sc);
231        refill_head(sc)->rAmount += refill.rAmount;
232        /* this loop is guaranteed to terminate as the sum of
233         * rAmount in a refill must be >= MIN_BUDGET */
234    }
235}
236
237void refill_budget_check(ticks_t usage)
238{
239    sched_context_t *sc = NODE_STATE(ksCurSC);
240    /* this function should only be called when the sc is out of budget */
241    ticks_t capacity = refill_capacity(NODE_STATE(ksCurSC), usage);
242    assert(capacity < MIN_BUDGET || refill_full(sc));
243    assert(sc->scPeriod > 0);
244    REFILL_SANITY_START(sc);
245
246    if (capacity == 0) {
247        while (refill_head(sc)->rAmount <= usage) {
248            /* exhaust and schedule replenishment */
249            usage -= refill_head(sc)->rAmount;
250            if (refill_single(sc)) {
251                /* update in place */
252                refill_head(sc)->rTime += sc->scPeriod;
253            } else {
254                refill_t old_head = refill_pop_head(sc);
255                old_head.rTime = old_head.rTime + sc->scPeriod;
256                schedule_used(sc, old_head);
257            }
258        }
259
260        /* budget overrun */
261        if (usage > 0) {
262            /* budget reduced when calculating capacity */
263            /* due to overrun delay next replenishment */
264            refill_head(sc)->rTime += usage;
265            /* merge front two replenishments if times overlap */
266            if (!refill_single(sc) &&
267                refill_head(sc)->rTime + refill_head(sc)->rAmount >=
268                refill_index(sc, refill_next(sc, sc->scRefillHead))->rTime) {
269
270                refill_t refill = refill_pop_head(sc);
271                refill_head(sc)->rAmount += refill.rAmount;
272                refill_head(sc)->rTime = refill.rTime;
273            }
274        }
275    }
276
277    capacity = refill_capacity(sc, usage);
278    if (capacity > 0 && refill_ready(sc)) {
279        refill_split_check(usage);
280    }
281
282    ensure_sufficient_head(sc);
283
284    REFILL_SANITY_END(sc);
285}
286
287void refill_split_check(ticks_t usage)
288{
289    sched_context_t *sc = NODE_STATE(ksCurSC);
290    /* invalid to call this on a NULL sc */
291    assert(sc != NULL);
292    /* something is seriously wrong if this is called and no
293     * time has been used */
294    assert(usage > 0);
295    assert(usage <= refill_head(sc)->rAmount);
296    assert(sc->scPeriod > 0);
297
298    REFILL_SANITY_START(sc);
299
300    /* first deal with the remaining budget of the current replenishment */
301    ticks_t remnant = refill_head(sc)->rAmount - usage;
302
303    /* set up a new replenishment structure */
304    refill_t new = (refill_t) {
305        .rAmount = usage, .rTime = refill_head(sc)->rTime + sc->scPeriod
306    };
307
308    if (refill_size(sc) == sc->scRefillMax || remnant < MIN_BUDGET) {
309        /* merge remnant with next replenishment - either it's too small
310         * or we're out of space */
311        if (refill_single(sc)) {
312            /* update inplace */
313            new.rAmount += remnant;
314            *refill_head(sc) = new;
315        } else {
316            refill_pop_head(sc);
317            refill_head(sc)->rAmount += remnant;
318            schedule_used(sc, new);
319            ensure_sufficient_head(sc);
320        }
321        assert(refill_ordered(sc));
322    } else {
323        /* leave remnant as reduced replenishment */
324        assert(remnant >= MIN_BUDGET);
325        /* split the head refill  */
326        refill_head(sc)->rAmount = remnant;
327        schedule_used(sc, new);
328    }
329
330    REFILL_SANITY_END(sc);
331}
332
333
334static bool_t refill_unblock_check_mergable(sched_context_t *sc)
335{
336    ticks_t amount = refill_head(sc)->rAmount;
337    ticks_t tail = NODE_STATE_ON_CORE(ksCurTime, sc->scCore) + amount;
338    bool_t enough_time = refill_index(sc, refill_next(sc, sc->scRefillHead))->rTime <= tail;
339    return !refill_single(sc) && enough_time;
340}
341
342void refill_unblock_check(sched_context_t *sc)
343{
344
345    if (isRoundRobin(sc)) {
346        /* nothing to do */
347        return;
348    }
349
350    /* advance earliest activation time to now */
351    REFILL_SANITY_START(sc);
352    if (refill_ready(sc)) {
353        refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, sc->scCore);
354        NODE_STATE(ksReprogram) = true;
355
356        /* merge available replenishments */
357        while (refill_unblock_check_mergable(sc)) {
358            ticks_t amount = refill_head(sc)->rAmount;
359            refill_pop_head(sc);
360            refill_head(sc)->rAmount += amount;
361            refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, sc->scCore);
362        }
363
364        assert(refill_sufficient(sc, 0));
365    }
366    REFILL_SANITY_END(sc);
367}
368