1#include <mem/alloc_or_die.h>
2#include <mem/slab.h>
3#include <sch/periodic_work.h>
4#include <sch/sched.h>
5#include <smp/percpu.h>
6
7#include "internal.h"
8#include <mem/alloc.h>
9
10static void scheduler_percpu_work_ctor(struct scheduler_periodic_work_percpu *,
11 cpu_id_t);
12
13SLAB_SIZE_REGISTER_FOR_STRUCT(scheduler_periodic_work, SLAB_OBJ_ALIGN_DEFAULT);
14PERCPU_DECLARE(periodic_percpu, struct scheduler_periodic_work_percpu,
15 scheduler_percpu_work_ctor);
16
17static int32_t work_cmp(struct pairing_node *a, struct pairing_node *b) {
18 struct scheduler_periodic_work *wa =
19 container_of(a, struct scheduler_periodic_work, pnode);
20 struct scheduler_periodic_work *wb =
21 container_of(b, struct scheduler_periodic_work, pnode);
22
23 if (wa->expected_next < wb->expected_next)
24 return -1;
25
26 if (wa->expected_next > wb->expected_next)
27 return 1;
28
29 return (uintptr_t) wa < (uintptr_t) wb ? -1 : 1;
30}
31
32static void
33scheduler_percpu_work_ctor(struct scheduler_periodic_work_percpu *pcpu,
34 cpu_id_t cpu) {
35 pcpu->cpu = cpu;
36 for (size_t i = 0; i < PERIODIC_WORK_MAX; i++) {
37 pairing_heap_init(h: &pcpu->period_based_works[i], cmp: work_cmp);
38 pairing_heap_init(h: &pcpu->time_based_works[i], cmp: work_cmp);
39 pcpu->limits.max_duration_per_call_ns = TIME_NS_MAX;
40 pcpu->limits.max_execs_per_call = SIZE_MAX;
41 }
42}
43
44static void
45linker_object_work_to_work(struct scheduler_periodic_work_linker_object *lobj,
46 struct scheduler_periodic_work *pw) {
47 pw->name = lobj->name;
48 pw->fn = lobj->fn;
49 pw->interval = lobj->interval;
50 pw->type = lobj->type;
51 pw->prio = lobj->prio;
52}
53
54static void
55attach_work_to_cpus(struct scheduler_periodic_work_linker_object *spwlo) {
56 for (size_t i = 0; i < global.core_count; i++) {
57 struct scheduler_periodic_work *w = alloc_or_die(
58 kmalloc(sizeof(struct scheduler_periodic_work), ALLOC_FLAGS_ZERO));
59
60 pairing_node_init(pn: &w->pnode);
61 linker_object_work_to_work(lobj: spwlo, pw: w);
62 struct scheduler_periodic_work_percpu *pcpu =
63 &PERCPU_READ_FOR_CPU(periodic_percpu, i);
64
65 if (w->type == PERIODIC_WORK_TIME_BASED) {
66 pairing_heap_insert(h: &pcpu->time_based_works[w->prio], node: &w->pnode);
67 pcpu->time_based_work_count[w->prio]++;
68 } else {
69 pairing_heap_insert(h: &pcpu->period_based_works[w->prio], node: &w->pnode);
70 pcpu->period_based_work_count[w->prio]++;
71 }
72 }
73}
74
75void scheduler_periodic_work_init(void) {
76 for (struct scheduler_periodic_work_linker_object *spw =
77 __skernel_sched_periodic_work;
78 spw < __ekernel_sched_periodic_work; spw++) {
79 attach_work_to_cpus(spwlo: spw);
80 }
81}
82
83static bool periodic_work_exec(uint64_t current,
84 struct scheduler_periodic_work *pw) {
85 if (current >= pw->expected_next) {
86 pw->fn();
87 pw->executed_times++;
88 pw->last_occurrence = current;
89 pw->expected_next += pw->interval;
90
91 if (current > pw->expected_next) {
92 size_t missed = (current - pw->expected_next) / pw->interval;
93 pw->interval_total_loss += missed * pw->interval;
94 }
95
96 pw->interval_latency = pw->interval_total_loss / pw->executed_times;
97
98 return true;
99 }
100
101 return false;
102}
103
104static bool passed_limit(time_ns_t initial_time, size_t executed,
105 struct scheduler_periodic_work_percpu *percpu) {
106 return !(time_get_us() * 1000 - initial_time <
107 percpu->limits.max_duration_per_call_ns &&
108 executed < percpu->limits.max_execs_per_call);
109}
110
111/* The IRQL guarantees that we will NEVER have to do locking on
112 * percpu state inside of these functions */
113void scheduler_periodic_work_execute(enum scheduler_periodic_work_type type) {
114 if (global.current_bootstage < BOOTSTAGE_LATE)
115 return;
116
117 kassert(irql_get() == IRQL_DISPATCH_LEVEL);
118 kassert(scheduler_preemption_disabled(TOPC_IRQL));
119 kassert(!scheduler_in_periodic_work());
120
121 struct scheduler_periodic_work_percpu *pcpu =
122 PERCPU_PTR(TOPC_IRQL, periodic_percpu);
123 pcpu->executing = true;
124
125 bool time_based = type == PERIODIC_WORK_TIME_BASED;
126 time_ns_t initial_time = time_get_us() * 1000;
127 size_t executed = 0;
128 size_t current_period = smp_core_scheduler()->current_period;
129 size_t starting_point = time_based ? initial_time : current_period;
130
131 for (size_t i = PERIODIC_WORK_HIGH; i <= PERIODIC_WORK_LOW; i++) {
132 struct pairing_heap *heap;
133
134 if (time_based) {
135 heap = &pcpu->time_based_works[i];
136 } else {
137 heap = &pcpu->period_based_works[i];
138 }
139
140 size_t size = time_based ? pcpu->time_based_work_count[i]
141 : pcpu->period_based_work_count[i];
142
143 size_t executed_in_this_heap = 0;
144
145 while (executed_in_this_heap < size) {
146 struct pairing_node *pn = pairing_heap_peek(h: heap);
147 if (!pn)
148 break;
149
150 struct scheduler_periodic_work *pw =
151 container_of(pn, struct scheduler_periodic_work, pnode);
152
153 if (!periodic_work_exec(current: starting_point, pw))
154 break;
155
156 executed_in_this_heap++;
157 executed++;
158
159 pairing_heap_pop(h: heap);
160 pairing_heap_insert(h: heap, node: &pw->pnode);
161
162 if (passed_limit(initial_time, executed, percpu: pcpu))
163 break;
164 }
165 }
166
167 pcpu->executing = false;
168}
169
170bool scheduler_in_periodic_work() {
171 return PERCPU_READ(TOPC_IRQL, periodic_percpu).executing;
172}
173