1/* @title: Threads */
2/* File defines thread structures and public APIs
3 * for boost and event recording + scoring */
4
5#pragma once
6#include <asm.h>
7#include <compiler.h>
8#include <mem/alloc.h>
9#include <mem/page.h>
10#include <sch/climb.h>
11#include <sch/rt_sched_types.h>
12#include <stdarg.h>
13#include <stdatomic.h>
14#include <stddef.h>
15#include <stdint.h>
16#include <structures/list.h>
17#include <structures/pairing_heap.h>
18#include <structures/rbt.h>
19#include <sync/condvar.h>
20#include <sync/spinlock.h>
21#include <thread/apc_types.h>
22#include <thread/thread_types.h>
23#include <time/time.h>
24#include <types/refcount.h>
25#include <types/types.h>
26
27#define THREAD_DEFAULT_TIMESLICE 15 /* 15 ms */
28
29#define THREAD_CLASS_WIDTH 1024
30#define THREAD_CLASS_HALF (THREAD_CLASS_WIDTH / 2)
31
32#define THREAD_BAND_MIN(avg) ((avg) - THREAD_CLASS_HALF)
33#define THREAD_BAND_MAX(avg) ((avg) + THREAD_CLASS_HALF)
34
35#define THREAD_ACT_INTERACTIVE_AVG 4000u
36#define THREAD_ACT_IO_BOUND_AVG 2500u
37#define THREAD_ACT_CPU_BOUND_AVG 1200u
38#define THREAD_ACT_SLEEPY_AVG 4500u
39
40#define THREAD_ACT_INTERACTIVE_MIN THREAD_BAND_MIN(THREAD_ACT_INTERACTIVE_AVG)
41#define THREAD_ACT_INTERACTIVE_MAX THREAD_BAND_MAX(THREAD_ACT_INTERACTIVE_AVG)
42
43#define THREAD_ACT_IO_BOUND_MIN THREAD_BAND_MIN(THREAD_ACT_IO_BOUND_AVG)
44#define THREAD_ACT_IO_BOUND_MAX THREAD_BAND_MAX(THREAD_ACT_IO_BOUND_AVG)
45
46#define THREAD_ACT_CPU_BOUND_MIN THREAD_BAND_MIN(THREAD_ACT_CPU_BOUND_AVG)
47#define THREAD_ACT_CPU_BOUND_MAX THREAD_BAND_MAX(THREAD_ACT_CPU_BOUND_AVG)
48
49#define THREAD_ACT_SLEEPY_MIN THREAD_BAND_MIN(THREAD_ACT_SLEEPY_AVG)
50#define THREAD_ACT_SLEEPY_MAX THREAD_BAND_MAX(THREAD_ACT_SLEEPY_AVG)
51
52#define THREAD_NICENESS_VALID(n) \
53 ((((nice_t) (n)) >= -19) && (((nice_t) (n)) <= 20))
54
55/* pluh */
56struct cpu_context {
57 uint64_t rbx;
58 uint64_t rbp;
59 uint64_t r12;
60 uint64_t r13;
61 uint64_t r14;
62 uint64_t r15;
63 uint64_t rsp;
64 uint64_t rip;
65};
66
67#define THREAD_EVENT_REASON_NONE 0xFF
68
69struct thread_event_association {
70 uint8_t reason;
71 uint64_t cycle; /* Cycle for the associated reason */
72};
73
74#define THREAD_ASSOCIATED_REASON_NONE 0xFF
75struct thread_event_reason {
76 uint8_t reason;
77 struct thread_event_association associated_reason;
78 time_t timestamp;
79 uint64_t cycle;
80};
81
82#define THREAD_PRIO_IS_TIMESHARING(prio) (prio == THREAD_PRIO_CLASS_TIMESHARE)
83
84/* Background threads share timeslices */
85#define THREAD_PRIO_HAS_TIMESLICE(prio) \
86 (THREAD_PRIO_IS_TIMESHARING(prio) || prio == THREAD_PRIO_CLASS_BACKGROUND)
87
88#define THREAD_ACTIVITY_BUCKET_COUNT 4
89#define THREAD_ACTIVITY_BUCKET_DURATION 1000 /* 1 second per bucket */
90
91static_assert(THREAD_ACTIVITY_BUCKET_COUNT < UINT16_MAX,
92 "Thread activity bucket granularity too large for a u16");
93
94#define THREAD_EVENT_RINGBUFFER_CAPACITY THREAD_ACTIVITY_BUCKET_COUNT
95#define TOTAL_BUCKET_DURATION \
96 (THREAD_ACTIVITY_BUCKET_COUNT * THREAD_ACTIVITY_BUCKET_DURATION)
97
98/* Buckets */
99struct thread_runtime_bucket {
100 uint16_t run_time_ms; /* can safely do a u16 since 2^16 > 1000 */
101 uint64_t wall_clock_sec;
102};
103
104struct thread_activity_bucket {
105 uint64_t cycle;
106
107 /* please do not block/sleep/wake more than 2^32 times a second */
108 uint32_t block_count;
109 uint32_t sleep_count;
110 uint32_t wake_count;
111
112 uint16_t block_duration;
113 uint16_t sleep_duration;
114};
115
116/* Fine grained, exact activity stats */
117struct thread_activity_stats {
118 struct thread_runtime_bucket rt_buckets[THREAD_ACTIVITY_BUCKET_COUNT];
119 struct thread_activity_bucket buckets[THREAD_ACTIVITY_BUCKET_COUNT];
120 time_t last_update_ms;
121 uint64_t current_cycle;
122 uint8_t current_bucket; /* idx of bucket representing 'now' */
123 uint8_t last_wake_index;
124};
125
126#define MAKE_THREAD_RINGBUFFER(name) \
127 struct thread_event_reason name[THREAD_EVENT_RINGBUFFER_CAPACITY]; \
128 uint8_t name##_head;
129
130struct thread_activity_data {
131 MAKE_THREAD_RINGBUFFER(wake_reasons);
132 MAKE_THREAD_RINGBUFFER(block_reasons);
133 MAKE_THREAD_RINGBUFFER(sleep_reasons);
134};
135
136/* Activity aggregations */
137enum thread_activity_class {
138 THREAD_ACTIVITY_CLASS_CPU_BOUND,
139 THREAD_ACTIVITY_CLASS_IO_BOUND,
140 THREAD_ACTIVITY_CLASS_INTERACTIVE,
141 THREAD_ACTIVITY_CLASS_SLEEPY,
142 THREAD_ACTIVITY_CLASS_UNKNOWN
143};
144
145struct thread_activity_metrics {
146 uint8_t run_ratio;
147 uint8_t block_ratio;
148 uint8_t sleep_ratio;
149 uint8_t wake_freq;
150};
151
152struct thread {
153 /* ========== Metadata ========== */
154 /* Unique ID allocated from global thread ID tree */
155 uint64_t id;
156 char *name;
157 void (*entry)(void *); /* For debug */
158
159 /* ========== Processor context data ========== */
160
161 /* Stack */
162 void *stack;
163 size_t stack_size;
164
165 /* Registers */
166 struct cpu_context regs;
167
168 /* ========== Transparent structure nodes ========== */
169
170 /* TODO: Use unions and combine these. Do make sure to keep
171 * in mind that all nodes get need to get
172 * reset if unions are to be used */
173
174 struct list_head reaper_list; /* reaper list */
175 struct list_head thread_list; /* global list of threads */
176
177 /* Runqueue nodes */
178
179 union {
180 struct rbt_node rq_tree_node; /* runqueue tree node */
181 struct rbt_node rt_tree_node; /* alias for rt scheduling */
182 };
183
184 union {
185 struct list_head rq_list_node; /* runqueue list node */
186 struct list_head rt_list_node; /* alias for rt scheduling */
187 };
188
189 /* Waitqueue nodes */
190 struct rbt_node wq_tree_node; /* waitqueue tree node */
191 struct list_head wq_list_node; /* waitqueue list node */
192 struct pairing_node wq_pairing_node; /* waitqueue pairing node */
193
194 struct list_head rcu_list_node; /* rcu list node */
195
196 /* ========== State ========== */
197
198 /* State */
199 _Atomic enum thread_state state;
200
201 /* Who is running us? */
202 cpu_id_t curr_core; /* -1 if not being ran */
203
204 cpu_id_t core_to_wake_on; /* When I run again, where should I be placed?
205 * -1 if the scheduler should select the most
206 * optimal core */
207
208 _Atomic(struct scheduler *) scheduler;
209
210 time_t run_start_time; /* When did we start running */
211
212 /* Who is allowed to run us? */
213 struct cpu_mask allowed_cpus;
214 _Atomic int64_t migrate_to; /* -1 if no migration target */
215
216 /* Flags */
217 enum rt_scheduler_capability accepted_rt_caps;
218 _Atomic(enum thread_flags) flags;
219 _Atomic size_t migration_generation;
220
221 /* ======== Raw priority + timeslice data ======== */
222
223 /* Priorities */
224 thread_prio_t activity_score;
225 int32_t dynamic_delta; /* Signed delta applied to base */
226 size_t weight;
227 nice_t niceness; /* -20 .. + 19 */
228
229 cpu_perf_t wanted_perf; /* This is the cpu_perf_t the thread's current
230 * CPU should try to match or do better than.
231 *
232 * If the current CPU's current wanted_perf
233 * does not satisfy the thread, we will try
234 * to either increase it for this CPU, or
235 * migrate the thread to another CPU. */
236
237 /* Class changes */
238 time_t last_class_change_ms;
239
240 size_t effective_priority;
241
242 /* Timeslice info and periods */
243 uint64_t completed_period;
244 time_t period_runtime_raw_ms; /* Raw MS time of runtime this period */
245 time_t budget_time_raw_ms; /* Raw MS time of budget */
246 time_t timeslice_length_raw_ms;
247
248 uint32_t virtual_period_runtime;
249 uint32_t virtual_budget;
250 uint32_t virtual_runtime_left;
251
252 /* ========== Thread activity stats ========== */
253
254 enum thread_activity_class activity_class;
255
256 enum thread_prio_class base_prio_class; /* for class boosts */
257 enum thread_prio_class perceived_prio_class;
258
259 /* Activity data */
260 struct thread_activity_data *activity_data;
261 struct thread_activity_stats *activity_stats;
262
263 /* "Overview" derived from data and stats */
264 struct thread_activity_metrics activity_metrics;
265
266 /* ========== Synchronization data ========== */
267
268 /* Lock + rc */
269 struct spinlock lock;
270 refcount_t refcount;
271
272 /* For condvar */
273 volatile enum wake_reason wake_reason;
274 size_t wait_cookie;
275
276 /* RCU */
277 _Atomic uint32_t rcu_nesting; /* incremented by this thread only */
278 _Atomic uint64_t rcu_start_gen;
279 _Atomic uint64_t rcu_quiescent_gen;
280
281 /* Block/sleep and wake sync. */
282 _Atomic enum thread_wait_type wait_type;
283 void *expected_wake_src;
284 uint64_t wait_token;
285
286 uint8_t last_action_reason;
287
288 /* used in wait_for_wake */
289 enum thread_state last_action;
290
291 _Atomic(void *) wake_src;
292 uint64_t wake_token;
293
294 uint64_t token_ctr;
295
296 struct condvar_with_cb cv_cb_object; /* wait object */
297 struct list_head io_wait_tokens; /* list of tokens */
298
299 struct turnstile *turnstile; /* my turnstile */
300 _Atomic(struct turnstile *) blocked_ts; /* what am I blocked on */
301
302 struct climb_thread_state climb_state;
303
304 /* ========== APC data ========== */
305 /* Standard APC queues */
306 struct apc_queue apc_head[APC_TYPE_COUNT];
307
308 /* Any APC pending */
309 _Atomic uint8_t apc_pending_mask; /* bitmask of APC_TYPE_* pending */
310
311 /* APC disable counts */
312 uint32_t special_apc_disable;
313 uint32_t kernel_apc_disable;
314
315 struct apc_queue event_apcs; /* yet to execute */
316 struct apc_queue to_exec_event_apcs; /* to be executed */
317
318 /* ========== Profiling data ========== */
319 struct log_site *log_site;
320 size_t context_switches; /* Total context switches */
321
322 size_t preemptions;
323
324 time_t creation_time_ms; /* When were we created? */
325
326 uint32_t boost_count;
327 uint32_t total_wake_count; /* Aggregate count of all wake events */
328 uint32_t total_block_count; /* Aggregate count of all block events */
329 uint32_t total_sleep_count; /* Aggregate count of all sleep events */
330 uint32_t total_apcs_ran; /* Total APCs executed on a given thread */
331
332 /* Misc. private field for whatever needs it */
333 void *private;
334};
335
336#define thread_from_rq_rbt_node(node) \
337 rbt_entry(node, struct thread, rq_tree_node)
338#define thread_from_rq_list_node(ln) \
339 (container_of(ln, struct thread, rq_list_node))
340
341#define thread_from_rcu_list_node(ln) \
342 (container_of(ln, struct thread, rcu_list_node))
343
344#define thread_from_wq_pairing_node(pn) \
345 (container_of(pn, struct thread, wq_pairing_node))
346#define thread_from_wq_list_node(ln) \
347 (container_of(ln, struct thread, wq_list_node))
348#define thread_from_wq_rbt_node(ln) \
349 (container_of(ln, struct thread, wq_tree_node))
350
351struct thread *thread_create_internal(char *name, void (*entry_point)(void *),
352 void *arg, size_t stack_size,
353 va_list args);
354
355struct thread *thread_create(char *name, void (*entry_point)(void *), void *arg,
356 ...);
357
358struct thread *thread_create_custom_stack(char *name,
359 void (*entry_point)(void *),
360 void *arg, size_t stack_size, ...);
361void thread_free(struct thread *t);
362
363void thread_init_thread_ids(void);
364void thread_sleep_for_ms(uint64_t ms);
365void thread_exit(void);
366void thread_print(const struct thread *t);
367
368void thread_update_activity_stats(struct thread *t, time_t time);
369void thread_classify_activity(struct thread *t, uint64_t now_ms);
370void thread_update_runtime_buckets(struct thread *thread, time_t time);
371void thread_apply_wake_boost(struct thread *t);
372void thread_update_effective_priority(struct thread *t);
373void thread_apply_cpu_penalty(struct thread *t);
374
375void thread_add_wake_reason(struct thread *t, uint8_t reason);
376void scheduler_wake_manual(struct thread *t, void *wake_src);
377void thread_calculate_activity_data(struct thread *t);
378
379void thread_add_block_reason(struct thread *t, uint8_t reason);
380void thread_add_sleep_reason(struct thread *t, uint8_t reason);
381
382/* these two functions return if the thread had `wake_matched`
383 * satisfied on return */
384void thread_prepare_to_block(struct thread *t, enum thread_block_reason r,
385 enum thread_wait_type wait_type,
386 void *expect_wake_src);
387void thread_prepare_to_sleep(struct thread *t, enum thread_sleep_reason r,
388 enum thread_wait_type wait_type,
389 void *expect_wake_src);
390
391/* Turnstile wants this */
392void thread_prepare_to_block_locked(struct thread *t,
393 enum thread_block_reason r,
394 enum thread_wait_type type,
395 void *expect_wake_src);
396
397void thread_set_timesharing(struct thread *t);
398void thread_set_background(struct thread *t);
399void thread_wake_unlocked(struct thread *t, enum thread_wake_reason r,
400 void *wake_src);
401void thread_migrate(struct thread *t, size_t dest_core);
402void thread_yield_until_wake_match();
403enum thread_prio_class thread_unboost_self();
404enum thread_prio_class thread_boost_self(enum thread_prio_class new);
405struct scheduler *thread_get_scheduler(struct thread *t, enum irql *sirql_out);
406
407struct thread_queue;
408void thread_block_on(struct thread_queue *q, enum thread_wait_type type,
409 void *wake_src);
410
411void thread_enqueue(struct thread *t);
412void thread_enqueue_on_core(struct thread *t, uint64_t core_id);
413
414bool thread_wake(struct thread *t, enum thread_wake_reason reason,
415 enum thread_prio_class prio, void *wake_src);
416void thread_wake_from_io_block(struct thread *t, void *wake_src);
417bool thread_inherit_priority(struct thread *boosted, struct thread *from,
418 enum thread_prio_class *old_class_out);
419
420void thread_uninherit_priority(enum thread_prio_class class);
421void thread_remove_boost();
422
423void thread_lock_two_runqueues(struct thread *a, struct thread *b,
424 struct scheduler **out_rq_a,
425 struct scheduler **out_rq_b, enum irql *irq_a,
426 enum irql *irq_b);
427
428void thread_lock_thread_and_rq(struct thread *t, struct scheduler *other_rq,
429 struct scheduler **out_thread_rq,
430 enum irql *irq_first, enum irql *irq_second);
431void thread_unlock_thread_and_rq(struct scheduler *thread_rq,
432 struct scheduler *other_rq,
433 enum irql irq_first, enum irql irq_second);
434
435static inline struct thread *thread_get_current() {
436 uintptr_t thread;
437 asm volatile("movq %%gs:%c1, %0"
438 : "=r"(thread)
439 : "i"(offsetof(struct core, current_thread)));
440 return (struct thread *) thread;
441}
442
443static inline int64_t thread_set_migration_target(struct thread *t,
444 int64_t new) {
445 return atomic_exchange(&t->migrate_to, new);
446}
447
448static inline enum thread_state thread_get_state(struct thread *t) {
449 return atomic_load(&t->state);
450}
451
452static inline void thread_set_state(struct thread *t, enum thread_state state) {
453 atomic_store(&t->state, state);
454}
455
456static inline enum thread_flags thread_get_flags(struct thread *t) {
457 return atomic_load(&t->flags);
458}
459
460static inline void thread_set_flags(struct thread *t, enum thread_flags new) {
461 atomic_store(&t->flags, new);
462}
463
464static inline bool thread_pin(struct thread *t) {
465 return atomic_fetch_or(&t->flags, THREAD_FLAG_PINNED) & THREAD_FLAG_PINNED;
466}
467
468static inline void thread_unpin(struct thread *t) {
469 atomic_fetch_and(&t->flags, ~THREAD_FLAG_PINNED);
470}
471
472static inline enum thread_flags thread_or_flags(struct thread *t,
473 enum thread_flags flags) {
474 return atomic_fetch_or(&t->flags, flags);
475}
476
477static inline enum thread_flags thread_and_flags(struct thread *t,
478 enum thread_flags flags) {
479 return atomic_fetch_and(&t->flags, flags);
480}
481
482static inline size_t thread_get_migration_generation(struct thread *t) {
483 return atomic_load_explicit(&t->migration_generation, memory_order_acquire);
484}
485
486static inline struct scheduler *thread_get_scheduler_unsafe(struct thread *t) {
487 return atomic_load_explicit(&t->scheduler, memory_order_acquire);
488}
489
490static inline void thread_set_runqueue(struct thread *t, struct scheduler *s) {
491 atomic_fetch_add_explicit(&t->migration_generation, 1,
492 memory_order_release);
493 atomic_store_explicit(&t->scheduler, s, memory_order_release);
494 atomic_fetch_add_explicit(&t->migration_generation, 1,
495 memory_order_release);
496}
497
498REFCOUNT_GENERATE_GET_FOR_STRUCT_WITH_FAILURE_COND(thread, refcount, flags,
499 &THREAD_FLAG_DYING);
500void reaper_enqueue(struct thread *t);
501static inline void thread_put(struct thread *t) {
502 if (refcount_dec_and_test(rc: &t->refcount)) {
503 if (thread_get_state(t) != THREAD_STATE_ZOMBIE)
504 panic("final ref dropped while thread not zombie");
505
506 reaper_enqueue(t);
507 }
508}
509
510static inline enum irql thread_acquire(struct thread *t, bool *success) {
511 if (!thread_get(obj: t)) {
512 if (success)
513 *success = false;
514 return IRQL_NONE;
515 }
516
517 if (success)
518 *success = true;
519 return spin_lock_irq_disable(lock: &t->lock);
520}
521
522static inline void thread_release(struct thread *t, enum irql irql) {
523 spin_unlock(lock: &t->lock, old: irql);
524 thread_put(t);
525}
526
527static inline bool thread_is_rt(struct thread *t) {
528 return t->perceived_prio_class == THREAD_PRIO_CLASS_URGENT ||
529 t->perceived_prio_class == THREAD_PRIO_CLASS_RT;
530}
531
532static inline void thread_clear_wake_data_raw(struct thread *t) {
533 atomic_store_explicit(&t->wake_src, NULL, memory_order_release);
534 thread_and_flags(t, flags: ~THREAD_FLAG_WAKE_MATCHED);
535 t->expected_wake_src = NULL;
536 t->wait_type = THREAD_WAIT_NONE;
537 t->last_action_reason = 0;
538 t->last_action = THREAD_STATE_READY;
539 t->wake_token = 0;
540}
541
542static inline void thread_clear_wake_data(struct thread *t) {
543 bool aok;
544 enum irql irql = thread_acquire(t, success: &aok);
545 kassert(aok);
546
547 thread_clear_wake_data_raw(t);
548
549 thread_release(t, irql);
550}
551
552static inline enum thread_wait_type thread_get_wait_type(struct thread *t) {
553 return atomic_load_explicit(&t->wait_type, memory_order_acquire);
554}
555
556static inline struct thread *thread_spawn(char *name, void (*entry)(void *),
557 void *arg, ...) {
558 va_list args;
559 va_start(args, arg);
560 struct thread *t =
561 thread_create_internal(name, entry_point: entry, arg, THREAD_STACK_SIZE, args);
562 va_end(args);
563 thread_enqueue(t);
564 return t;
565}
566
567static inline struct thread *thread_spawn_custom_stack(char *name,
568 void (*entry)(void *),
569 void *arg,
570 size_t stack_size, ...) {
571 va_list args;
572 va_start(args, stack_size);
573 struct thread *t =
574 thread_create_internal(name, entry_point: entry, arg, stack_size, args);
575 va_end(args);
576
577 thread_enqueue(t);
578 return t;
579}
580
581static inline struct thread *thread_spawn_on_core(char *name,
582 void (*entry)(void *),
583 void *arg, uint64_t core_id,
584 ...) {
585 va_list args;
586 va_start(args, core_id);
587 struct thread *t =
588 thread_create_internal(name, entry_point: entry, arg, THREAD_STACK_SIZE, args);
589 va_end(args);
590
591 thread_enqueue_on_core(t, core_id);
592 return t;
593}
594