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