1/* 2 * Copyright 2020, Data61, CSIRO (ABN 41 687 119 230) 3 * 4 * SPDX-License-Identifier: GPL-2.0-only 5 */ 6 7#pragma once 8/* This header presents the interface for sporadic servers, 9 * implemented according to Stankcovich et. al in 10 * "Defects of the POSIX Spoardic Server and How to correct them", 11 * although without the priority management. 12 * 13 * Briefly, a sporadic server is a period and a queue of refills. Each 14 * refill consists of an amount, and a period. No thread is allowed to consume 15 * more than amount ticks per period. 16 * 17 * The sum of all refill amounts in the refill queue is always the budget of the scheduling context - 18 * that is it should never change, unless it is being updated / configured. 19 * 20 * Every time budget is consumed, that amount of budget is scheduled 21 * for reuse in period time. If the refill queue is full (the queue's 22 * minimum size is 2, and can be configured by the user per scheduling context 23 * above this) the next refill is merged. 24 */ 25#include <config.h> 26#include <types.h> 27#include <util.h> 28#include <object/structures.h> 29#include <machine/timer.h> 30#include <model/statedata.h> 31 32/* To do an operation in the kernel, the thread must have 33 * at least this much budget - see comment on refill_sufficient */ 34#define MIN_BUDGET_US (2u * getKernelWcetUs() * CONFIG_KERNEL_WCET_SCALE) 35#define MIN_BUDGET (2u * getKernelWcetTicks() * CONFIG_KERNEL_WCET_SCALE) 36#if (CONFIG_KERNEL_STATIC_MAX_BUDGET_US) != 0 37#define MAX_BUDGET_US (CONFIG_KERNEL_STATIC_MAX_BUDGET_US) 38#else 39#define MAX_BUDGET_US getMaxUsToTicks() 40#endif /* CONFIG_KERNEL_STATIC_MAX_BUDGET_US != 0 */ 41 42/* Short hand for accessing refill queue items */ 43static inline refill_t *refill_index(sched_context_t *sc, word_t index) 44{ 45 return ((refill_t *)(SC_REF(sc) + sizeof(sched_context_t))) + index; 46} 47static inline refill_t *refill_head(sched_context_t *sc) 48{ 49 return refill_index(sc, sc->scRefillHead); 50} 51static inline refill_t *refill_tail(sched_context_t *sc) 52{ 53 return refill_index(sc, sc->scRefillTail); 54} 55 56 57/* Scheduling context objects consist of a sched_context_t at the start, followed by a 58 * circular buffer of refills. As scheduling context objects are of variable size, the 59 * amount of refill_ts that can fit into a scheduling context object is also variable. 60 * 61 * @return the maximum number of refill_t data structures that can fit into this 62 * specific scheduling context object. 63 */ 64static inline word_t refill_absolute_max(cap_t sc_cap) 65{ 66 return (BIT(cap_sched_context_cap_get_capSCSizeBits(sc_cap)) - sizeof(sched_context_t)) / sizeof(refill_t); 67} 68 69/* @return the current amount of empty slots in the refill buffer */ 70static inline word_t refill_size(sched_context_t *sc) 71{ 72 if (sc->scRefillHead <= sc->scRefillTail) { 73 return (sc->scRefillTail - sc->scRefillHead + 1u); 74 } 75 return sc->scRefillTail + 1u + (sc->scRefillMax - sc->scRefillHead); 76} 77 78/* @return true if the circular buffer of refills is current full (all slots in the 79 * buffer are currently being used */ 80static inline bool_t refill_full(sched_context_t *sc) 81{ 82 return refill_size(sc) == sc->scRefillMax; 83} 84 85/* @return true if the ciruclar buffer only contains 1 used slot */ 86static inline bool_t refill_single(sched_context_t *sc) 87{ 88 return sc->scRefillHead == sc->scRefillTail; 89} 90 91/* Return the amount of budget this scheduling context 92 * has available if usage is charged to it. */ 93static inline ticks_t refill_capacity(sched_context_t *sc, ticks_t usage) 94{ 95 if (unlikely(usage > refill_head(sc)->rAmount)) { 96 return 0; 97 } 98 99 return refill_head(sc)->rAmount - usage; 100} 101 102/* 103 * Return true if the head refill has sufficient capacity 104 * to enter and exit the kernel after usage is charged to it. 105 */ 106static inline bool_t refill_sufficient(sched_context_t *sc, ticks_t usage) 107{ 108 return refill_capacity(sc, usage) >= MIN_BUDGET; 109} 110 111/* 112 * Return true if the head refill is eligible to be used. 113 * This indicates if the thread bound to the sc can be placed 114 * into the scheduler, otherwise it needs to go into the release queue 115 * to wait. 116 */ 117static inline bool_t refill_ready(sched_context_t *sc) 118{ 119 return refill_head(sc)->rTime <= (NODE_STATE_ON_CORE(ksCurTime, sc->scCore) + getKernelWcetTicks()); 120} 121 122/* Create a new refill in a non-active sc */ 123#ifdef ENABLE_SMP_SUPPORT 124void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period, word_t core); 125#define REFILL_NEW(sc, max_refills, budget, period, core) refill_new(sc, max_refills, budget, period, core) 126#else 127void refill_new(sched_context_t *sc, word_t max_refills, ticks_t budget, ticks_t period); 128#define REFILL_NEW(sc, max_refills, budget, period, core) refill_new(sc, max_refills, budget, period) 129#endif 130 131/* Update refills in an active sc without violating bandwidth constraints */ 132void refill_update(sched_context_t *sc, ticks_t new_period, ticks_t new_budget, word_t new_max_refills); 133 134 135/* Charge `usage` to the current scheduling context. 136 * This function should only be called only when charging `used` will deplete 137 * the head refill, resulting in refill_sufficient failing. 138 * 139 * @param usage the amount of time to charge. 140 */ 141void refill_budget_check(ticks_t used); 142 143/* 144 * Charge a the current scheduling context `used` amount from its 145 * current refill. This will split the refill, leaving whatever is 146 * left over at the head of the refill. This is only called when charging 147 * `used` will not deplete the head refill. 148 */ 149void refill_split_check(ticks_t used); 150 151/* 152 * This is called when a thread is eligible to start running: it 153 * iterates through the refills queue and merges any 154 * refills that overlap. 155 */ 156void refill_unblock_check(sched_context_t *sc); 157 158