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