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