src/kernel/sporadic.c

35 static inline word_t refill_next(sched_context_t *sc, word_t index)
37     return (index == sc->scRefillMax - 1u) ? (0) : index + 1u;
42 UNUSED static inline void print_index(sched_context_t *sc, word_t index)
45     printf("index %lu, Amount: %llx, time %llx\n", index, refill_index(sc, index)->rAmount,
46            refill_index(sc, index)->rTime);
49 UNUSED static inline void refill_print(sched_context_t *sc)
51     printf("Head %lu tail %lu\n", sc->scRefillHead, sc->scRefillTail);
52     word_t current = sc->scRefillHead;
54     print_index(sc, current);
56     while (current != sc->scRefillTail) {
57         current = refill_next(sc, current);
58         print_index(sc, current);
65 static UNUSED bool_t refill_ordered(sched_context_t *sc)
67     word_t current = sc->scRefillHead;
68     word_t next = refill_next(sc, sc->scRefillHead);
70     while (current != sc->scRefillTail) {
71         if (!(refill_index(sc, current)->rTime <= refill_index(sc, next)->rTime)) {
72             refill_print(sc);
76         next = refill_next(sc, current);
82 #define REFILL_SANITY_START(sc) ticks_t _sum = refill_sum(sc); assert(refill_ordered(sc));
83 #define REFILL_SANITY_CHECK(sc, budget) \
85         assert(refill_sum(sc) == budget); assert(refill_ordered(sc)); \
88 #define REFILL_SANITY_END(sc) \
90         REFILL_SANITY_CHECK(sc, _sum);\
93 #define REFILL_SANITY_START(sc)
94 #define REFILL_SANITY_CHECK(sc, budget)
95 #define REFILL_SANITY_END(sc)
99 static UNUSED ticks_t refill_sum(sched_context_t *sc)
101     ticks_t sum = refill_head(sc)->rAmount;
102     word_t current = sc->scRefillHead;
104     while (current != sc->scRefillTail) {
105         current = refill_next(sc, current);
106         sum += refill_index(sc, current)->rAmount;
113 static inline refill_t refill_pop_head(sched_context_t *sc)
116     assert(!refill_single(sc));
118     UNUSED word_t prev_size = refill_size(sc);
119     refill_t refill = *refill_head(sc);
120     sc->scRefillHead = refill_next(sc, sc->scRefillHead);
123     assert(prev_size == (refill_size(sc) + 1));
124     assert(sc->scRefillHead < sc->scRefillMax);
129 static inline void refill_add_tail(sched_context_t *sc, refill_t refill)
132     assert(refill_size(sc) < sc->scRefillMax);
134     word_t new_tail = refill_next(sc, sc->scRefillTail);
135     sc->scRefillTail = new_tail;
136     *refill_tail(sc) = refill;
139     assert(new_tail < sc->scRefillMax);
142 static inline void maybe_add_empty_tail(sched_context_t *sc)
144     if (isRoundRobin(sc)) {
147         refill_add_tail(sc, empty_tail);
148         assert(refill_size(sc) == MIN_REFILLS);
153 void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period, word_t core)
155 void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period)
158     sc->scPeriod = period;
159     sc->scRefillHead = 0;
160     sc->scRefillTail = 0;
161     sc->scRefillMax = max_refills;
164     refill_head(sc)->rAmount = budget;
166     refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, core);
167     maybe_add_empty_tail(sc);
168     REFILL_SANITY_CHECK(sc, budget);
171 void refill_update(sched_context_t *sc, ticks_t new_period, ticks_t new_budget, word_t new_max_refills)
175     assert(sc->scRefillMax > 0);
183     *refill_index(sc, 0) = *refill_head(sc);
184     sc->scRefillHead = 0;
186     sc->scRefillTail = sc->scRefillHead;
188     sc->scRefillMax = new_max_refills;
190     sc->scPeriod = new_period;
192     if (refill_ready(sc)) {
193         refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, sc->scCore);
196     if (refill_head(sc)->rAmount >= new_budget) {
198         refill_head(sc)->rAmount = new_budget;
199         maybe_add_empty_tail(sc);
202         refill_t new = { .rAmount = (new_budget - refill_head(sc)->rAmount),
203                          .rTime = refill_head(sc)->rTime + new_period
205         refill_add_tail(sc, new);
208     REFILL_SANITY_CHECK(sc, new_budget);
211 static inline void schedule_used(sched_context_t *sc, refill_t new)
214     if (new.rAmount < MIN_BUDGET && !refill_single(sc)) {
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;
221         refill_add_tail(sc, new);
225 static inline void ensure_sufficient_head(sched_context_t *sc)
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;
239     sched_context_t *sc = NODE_STATE(ksCurSC);
240     /* this function should only be called when the sc is out of budget */
242     assert(capacity < MIN_BUDGET || refill_full(sc));
243     assert(sc->scPeriod > 0);
244     REFILL_SANITY_START(sc);
247         while (refill_head(sc)->rAmount <= usage) {
249             usage -= refill_head(sc)->rAmount;
250             if (refill_single(sc)) {
252                 refill_head(sc)->rTime += sc->scPeriod;
254                 refill_t old_head = refill_pop_head(sc);
255                 old_head.rTime = old_head.rTime + sc->scPeriod;
256                 schedule_used(sc, old_head);
264             refill_head(sc)->rTime += usage;
266             if (!refill_single(sc) &&
267                 refill_head(sc)->rTime + refill_head(sc)->rAmount >=
268                 refill_index(sc, refill_next(sc, sc->scRefillHead))->rTime) {
270                 refill_t refill = refill_pop_head(sc);
271                 refill_head(sc)->rAmount += refill.rAmount;
272                 refill_head(sc)->rTime = refill.rTime;
277     capacity = refill_capacity(sc, usage);
278     if (capacity > 0 && refill_ready(sc)) {
282     ensure_sufficient_head(sc);
284     REFILL_SANITY_END(sc);
289     sched_context_t *sc = NODE_STATE(ksCurSC);
290     /* invalid to call this on a NULL sc */
291     assert(sc != NULL);
295     assert(usage <= refill_head(sc)->rAmount);
296     assert(sc->scPeriod > 0);
298     REFILL_SANITY_START(sc);
301     ticks_t remnant = refill_head(sc)->rAmount - usage;
305         .rAmount = usage, .rTime = refill_head(sc)->rTime + sc->scPeriod
308     if (refill_size(sc) == sc->scRefillMax || remnant < MIN_BUDGET) {
311         if (refill_single(sc)) {
314             *refill_head(sc) = new;
316             refill_pop_head(sc);
317             refill_head(sc)->rAmount += remnant;
318             schedule_used(sc, new);
319             ensure_sufficient_head(sc);
321         assert(refill_ordered(sc));
326         refill_head(sc)->rAmount = remnant;
327         schedule_used(sc, new);
330     REFILL_SANITY_END(sc);
334 static bool_t refill_unblock_check_mergable(sched_context_t *sc)
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;
342 void refill_unblock_check(sched_context_t *sc)
345     if (isRoundRobin(sc)) {
351     REFILL_SANITY_START(sc);
352     if (refill_ready(sc)) {
353         refill_head(sc)->rTime = NODE_STATE_ON_CORE(ksCurTime, sc->scCore);
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);
364         assert(refill_sufficient(sc, 0));
366     REFILL_SANITY_END(sc);