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