1#include <bootstage.h>
2#include <log.h>
3#include <mem/address_range.h>
4#include <mem/alloc.h>
5#include <mem/pmm.h>
6#include <mem/slab.h>
7#include <mem/vas.h>
8#include <mem/vmm.h>
9#include <sch/periodic_work.h>
10#include <sch/sched.h>
11#include <smp/domain.h>
12#include <stdbool.h>
13#include <stddef.h>
14#include <string.h>
15#include <sync/rcu.h>
16#include <sync/turnstile.h>
17#include <thread/apc.h>
18#include <thread/reaper.h>
19#include <thread/thread.h>
20#include <thread/tid.h>
21#include <thread/workqueue.h>
22#include <time/timer.h>
23
24#include "sch/internal.h"
25
26#ifdef DEBUG_LOCK_CHK
27
28#include "sync/lock_chk_internal.h"
29
30static void thread_lock_chk_init(struct thread *thread) {
31 lock_chk_thread_init(thread);
32}
33
34static void thread_lock_chk_exit(struct thread *thread) {
35 lock_chk_thread_exit(thread);
36}
37
38#else
39
40static void thread_lock_chk_init(struct thread *thread) {
41 unused(thread);
42}
43
44static void thread_lock_chk_exit(struct thread *thread) {
45 unused(thread);
46}
47
48#endif
49
50SLAB_SIZE_REGISTER_FOR_STRUCT(thread, /*alignment*/ 32);
51
52#define THREAD_STACKS_HEAP_START 0xFFFFF10000000000ULL
53#define THREAD_STACKS_HEAP_END 0xFFFFF20000000000ULL
54
55ADDRESS_RANGE_DECLARE(thread_stacks, .name = "thread stacks",
56 .base = THREAD_STACKS_HEAP_START,
57 .size = THREAD_STACKS_HEAP_END - THREAD_STACKS_HEAP_START,
58 .flags = ADDRESS_RANGE_STATIC);
59
60/* lol */
61static struct tid_space *global_tid_space = NULL;
62static struct vas *stacks_space = NULL;
63
64void thread_init_thread_ids(void) {
65 stacks_space = vas_create(THREAD_STACKS_HEAP_START, THREAD_STACKS_HEAP_END);
66 global_tid_space = tid_space_init(UINT64_MAX);
67 locked_list_init(ll: &global.thread_list, LOCKED_LIST_INIT_IRQ_DISABLE);
68}
69
70APC_EVENT_CREATE(thread_exit_apc_event, "THREAD_EXIT");
71
72void thread_exit(void) {
73 thread_exit_with_status(status: 0);
74}
75
76void thread_exit_with_status(int status) {
77 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
78
79 struct thread *self = thread_get_current();
80 thread_lock_chk_exit(thread: self);
81
82 /* Can't be in a critical section when we exit */
83 kassert(atomic_load_explicit(&self->rcu_nesting, memory_order_relaxed) == 0,
84 "thread exited inside an RCU read section");
85
86 /* Public status and the ZOMBIE state under join_lock...
87 *
88 * Joiners either see ZOMBIE here are don't block, or are already
89 * parked on join_cv and gets the broadcast, no third outcome */
90 enum irql jirql = spin_lock(&self->join_lock);
91 self->exit_status = status;
92 thread_set_state(t: self, state: THREAD_STATE_ZOMBIE);
93 thread_or_flags(t: self, flags: THREAD_FLAG_DYING);
94 spin_unlock(&self->join_lock, jirql);
95
96 apc_rundown_thread(t: self);
97
98 /* Walk into thread_wake() and take runqueue locks, woken joiners
99 * can't free us, because our reference lives until the next thread drops */
100 condvar_broadcast(cv: &self->join_cv);
101
102 climb_thread_remove(t: self);
103 locked_list_del(ll: &global.thread_list, lh: &self->thread_list);
104 atomic_fetch_sub(&global.thread_count, 1);
105
106 irql_lower(old_level: irql);
107
108 scheduler_yield();
109}
110
111void thread_entry_wrapper(void) {
112 /* TODO: We might want to consider refactoring
113 * the switch_in so as to not gradually bloat up
114 * both places where the "gopher pops out of the ground",
115 * i.e. a thread entering */
116 scheduler_yield_nesting_reset(t: thread_get_current());
117
118 if (thread_get_current()->state != THREAD_STATE_IDLE_THREAD)
119 atomic_fetch_add(&global.thread_count, 1);
120
121 void (*entry)(void *);
122 asm volatile("mov %%r12, %0" : "=r"(entry));
123
124 void *arg;
125 asm volatile("mov %%r13, %0" : "=r"(arg));
126
127 scheduler_switch_in();
128
129 kassert(bootstage_get() < BOOTSTAGE_LATE ||
130 irql_get() == IRQL_DISPATCH_LEVEL,
131 "entered thread at %s, want %s", irql_to_str(irql_get()),
132 irql_to_str(IRQL_DISPATCH_LEVEL));
133
134 scheduler_mark_self_in_resched(false);
135
136 irql_lower(old_level: IRQL_PASSIVE_LEVEL);
137 kassert(entry);
138 entry(arg);
139 thread_exit();
140}
141
142void *thread_allocate_stack(size_t pages) {
143 size_t needed = (pages + 1) * PAGE_SIZE;
144 vaddr_t virt_base = vas_alloc(vas: stacks_space, size: needed, PAGE_SIZE);
145 if (!virt_base)
146 return NULL;
147
148 /* Leave the first page unmapped, protector page */
149 virt_base += PAGE_SIZE;
150 for (size_t i = 0; i < pages; i++) {
151 vaddr_t virt = virt_base + (i * PAGE_SIZE);
152 paddr_t phys = kassert(pmm_alloc_page());
153 vmm_map_page(virt, phys, PAGE_PRESENT | PAGE_WRITE | PAGE_XD,
154 VMM_FLAG_NONE);
155 }
156 return (void *) virt_base;
157}
158
159void thread_free_stack(struct thread *thread) {
160 vaddr_t stack_real_virt = (vaddr_t) thread->stack - PAGE_SIZE;
161 size_t pages = thread->stack_size / PAGE_SIZE;
162 for (size_t i = 0; i < pages; i++) {
163 vaddr_t virt = (vaddr_t) thread->stack + i * PAGE_SIZE;
164 paddr_t phys = vmm_get_phys(virt, VMM_FLAG_NONE);
165 kassert(phys != (paddr_t) -1);
166 vmm_unmap_page(virt);
167 pmm_free_page(addr: phys);
168 }
169 vas_free(vas: stacks_space, addr: stack_real_virt, size: (pages + 1) * PAGE_SIZE);
170}
171
172static void thread_init_event_reasons(
173 struct thread_event_reason reasons[THREAD_EVENT_RINGBUFFER_CAPACITY]) {
174 for (size_t i = 0; i < THREAD_EVENT_RINGBUFFER_CAPACITY; i++) {
175 reasons[i].associated_reason.reason = THREAD_EVENT_REASON_NONE;
176 reasons[i].associated_reason.cycle = 0;
177 reasons[i].reason = THREAD_EVENT_REASON_NONE;
178 reasons[i].cycle = 0;
179 reasons[i].timestamp = 0;
180 }
181}
182
183static void thread_init_activity_data(struct thread *thread) {
184 struct thread_activity_data *data = thread->activity_data;
185 data->block_reasons_head = 0;
186 data->sleep_reasons_head = 0;
187 data->wake_reasons_head = 0;
188 thread_init_event_reasons(reasons: thread->activity_data->block_reasons);
189 thread_init_event_reasons(reasons: thread->activity_data->wake_reasons);
190 thread_init_event_reasons(reasons: thread->activity_data->sleep_reasons);
191}
192
193static struct thread *thread_init(struct thread *thread,
194 void (*entry_point)(void *), void *arg,
195 void *stack, size_t stack_size) {
196 thread_init_activity_data(thread);
197 thread_lock_chk_init(thread);
198 memset(thread->activity_stats, 0, sizeof(struct thread_activity_stats));
199
200 uint64_t stack_top = (uint64_t) stack + stack_size;
201 thread->entry = entry_point;
202 thread->creation_time_ms = time_get_ms();
203 thread->stack_size = stack_size;
204 thread->regs.rsp = stack_top;
205 thread->migrate_to = -1;
206 thread->base_prio_class = THREAD_PRIO_CLASS_TIMESHARE;
207 thread->niceness = 0;
208 thread->perceived_prio_class = THREAD_PRIO_CLASS_TIMESHARE;
209 thread->state = THREAD_STATE_READY;
210 thread->regs.r12 = (uint64_t) entry_point;
211 thread->regs.r13 = (uint64_t) arg;
212 thread->regs.rip = (uint64_t) thread_entry_wrapper;
213 thread->stack = (void *) stack;
214 thread->flags = 0;
215 thread->curr_core = -1;
216 thread->rcu_nesting = 0;
217 thread->rcu_read_seq = 0;
218 thread->rcu_leaf = NULL;
219 thread->rcu_blocked_seq = 0;
220 thread->id = tid_alloc(ts: global_tid_space);
221 thread->refcount = 1;
222 thread->timeslice_length_raw_ms = THREAD_DEFAULT_TIMESLICE;
223 thread->wait_type = THREAD_WAIT_NONE;
224 thread->activity_class = THREAD_ACTIVITY_CLASS_UNKNOWN;
225 thread->exit_status = 0;
226 spinlock_init(&thread->lock);
227 spinlock_init(&thread->join_lock);
228
229 /* join_lock/join_cv are only ever touched from thread context, and
230 * thread_join_timeout() has to allocate a timer while holding the
231 * lock, which it could not do at IRQL_HIGH_LEVEL */
232 condvar_init(cv: &thread->join_cv, CONDVAR_INIT_NORMAL);
233 pairing_node_init(pn: &thread->wq_pairing_node);
234
235 turnstile_init(ts: thread->turnstile);
236
237 thread_update_effective_priority(t: thread);
238
239 climb_thread_init(t: thread);
240 INIT_LIST_HEAD(list: &thread->io_wait_tokens);
241 INIT_LIST_HEAD(list: &thread->thread_list);
242
243 for (size_t i = 0; i < APC_TYPE_COUNT; i++)
244 apc_queue_init(q: &thread->apc_head[i]);
245
246 apc_queue_init(q: &thread->event_apcs);
247 apc_queue_init(q: &thread->to_exec_event_apcs);
248
249 INIT_LIST_HEAD(list: &thread->rq_list_node);
250 INIT_LIST_HEAD(list: &thread->wq_list_node);
251 INIT_LIST_HEAD(list: &thread->rcu_list_node);
252 INIT_LIST_HEAD(list: &thread->reaper_list);
253 rbt_init_node(n: &thread->rq_tree_node);
254 rbt_init_node(n: &thread->wq_tree_node);
255 crash_perthread_init(t: thread);
256 locked_list_add(ll: &global.thread_list, lh: &thread->thread_list);
257
258 return thread;
259}
260
261struct thread *thread_create_internal(char *name, void (*entry_point)(void *),
262 void *arg, size_t stack_size,
263 va_list args) {
264 kassert(name);
265 struct thread *new_thread =
266 kmalloc(sizeof(struct thread), ALLOC_FLAGS_ZERO);
267 if (unlikely(!new_thread))
268 goto err;
269
270 void *stack = thread_allocate_stack(pages: stack_size / PAGE_SIZE);
271 if (unlikely(!stack))
272 goto err;
273
274 new_thread->activity_data =
275 kmalloc(sizeof(struct thread_activity_data), ALLOC_FLAGS_ZERO);
276 if (unlikely(!new_thread->activity_data))
277 goto err;
278
279 new_thread->turnstile = turnstile_create();
280 if (unlikely(!new_thread->turnstile))
281 goto err;
282
283 new_thread->activity_stats =
284 kmalloc(sizeof(struct thread_activity_stats), ALLOC_FLAGS_ZERO);
285 if (unlikely(!new_thread->activity_stats))
286 goto err;
287
288 if (unlikely(!cpu_mask_init(&new_thread->allowed_cpus, global.core_count)))
289 goto err;
290
291 cpu_mask_set_all(&new_thread->allowed_cpus);
292
293 va_list args_copy;
294 va_copy(args_copy, args);
295 size_t needed = vsnprintf(NULL, buffer_len: 0, format: name, args: args_copy) + 1;
296 va_end(args_copy);
297
298 new_thread->name = kmalloc(needed, ALLOC_FLAGS_ZERO);
299 if (!new_thread->name)
300 goto err;
301
302 struct log_site_options opts = {
303 .name = new_thread->name,
304 .dump_opts = LOG_DUMP_DEFAULT,
305 .capacity = 16,
306 .flags = LOG_SITE_DEFAULT,
307 .enabled_mask = LOG_SITE_ALL,
308 };
309
310 new_thread->log_site = log_site_create(opts);
311 if (!new_thread->log_site)
312 goto err;
313
314 new_thread->log_handle = LOG_HANDLE_DEFAULT;
315 va_copy(args_copy, args);
316 vsnprintf(buffer: new_thread->name, buffer_len: needed, format: name, args: args_copy);
317 va_end(args_copy);
318
319 return thread_init(thread: new_thread, entry_point, arg, stack, stack_size);
320
321err:
322 if (!new_thread)
323 return NULL;
324
325 kfree(new_thread->turnstile);
326 kfree(new_thread->name);
327 kfree(new_thread->activity_data);
328 kfree(new_thread->activity_stats);
329 thread_free_stack(thread: new_thread);
330 tid_free(ts: global_tid_space, id: new_thread->id);
331 kfree(new_thread);
332
333 return NULL;
334}
335
336struct thread *thread_create(char *name, void (*entry_point)(void *), void *arg,
337 ...) {
338 va_list args;
339 va_start(args, arg);
340 struct thread *ret =
341 thread_create_internal(name, entry_point, arg, THREAD_STACK_SIZE, args);
342 va_end(args);
343 return ret;
344}
345
346struct thread *thread_create_custom_stack(char *name,
347 void (*entry_point)(void *),
348 void *arg, size_t stack_size, ...) {
349 va_list args;
350 va_start(args, stack_size);
351 struct thread *ret =
352 thread_create_internal(name, entry_point, arg, stack_size, args);
353 va_end(args);
354 return ret;
355}
356
357void thread_free(struct thread *t) {
358 tid_free(ts: global_tid_space, id: t->id);
359 kfree(t->activity_data);
360 kfree(t->activity_stats);
361 kfree(t->name);
362 kfree(t->turnstile);
363 apc_rundown_thread(t);
364 thread_free_stack(thread: t);
365 log_site_put(site: t->log_site);
366 kfree(t);
367}
368
369static void thread_reap_rcu(struct rcu_cb *cb, void *arg) {
370 unused(cb);
371 reaper_enqueue(t: arg);
372}
373
374void thread_put(struct thread *t) {
375 if (!refcount_dec_and_test(rc: &t->refcount))
376 return;
377
378 if (thread_get_state(t) != THREAD_STATE_ZOMBIE)
379 panic("final ref dropped while thread not zombie");
380
381 rcu_defer(cb: &t->free_rcu, fn: thread_reap_rcu, arg: t);
382}
383
384void thread_queue_init(struct thread_queue *q) {
385 INIT_LIST_HEAD(list: &q->list);
386 spinlock_init(&q->lock);
387}
388
389void thread_queue_push_back(struct thread_queue *q, struct thread *t) {
390 enum irql irql = spin_lock_irq_disable(&q->lock);
391 list_add_tail(new: &t->wq_list_node, head: &q->list);
392 spin_unlock(&q->lock, irql);
393}
394
395bool thread_queue_remove(struct thread_queue *q, struct thread *t) {
396 enum irql irql = spin_lock_irq_disable(&q->lock);
397 struct list_head *pos;
398
399 list_for_each(pos, &q->list) {
400 struct thread *thread = thread_from_wq_list_node(pos);
401 if (thread == t) {
402 list_del_init(entry: &t->wq_list_node);
403 spin_unlock(&q->lock, irql);
404 return true;
405 }
406 }
407
408 spin_unlock(&q->lock, irql);
409 return false;
410}
411
412struct thread *thread_queue_pop_front(struct thread_queue *q) {
413 enum irql irql = spin_lock_irq_disable(&q->lock);
414 struct list_head *lhead = list_pop_front_init(head: &q->list);
415 spin_unlock(&q->lock, irql);
416 if (!lhead)
417 return NULL;
418
419 return thread_from_wq_list_node(lhead);
420}
421
422void thread_block_on(struct thread_queue *q, enum thread_wait_type type,
423 void *wake_src) {
424 struct thread *current = thread_get_current();
425
426 enum irql irql = spin_lock_irq_disable(&q->lock);
427 thread_prepare_to_block(t: current, r: THREAD_BLOCK_REASON_MANUAL, wait_type: type,
428 expect_wake_src: wake_src);
429 list_add_tail(new: &current->wq_list_node, head: &q->list);
430 spin_unlock(&q->lock, irql);
431}
432
433static void wake_thread_timer_cb(struct timer *timer) {
434 struct thread *t = timer->data;
435 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_TIMEOUT, prio: t->perceived_prio_class,
436 wake_src: t);
437}
438
439void thread_sleep_for_us(uint64_t us) {
440 if (us == 0) {
441 scheduler_yield();
442 return;
443 }
444
445 struct thread *curr = thread_get_current();
446 struct timer sleep_timer;
447 timer_init(timer: &sleep_timer, func: wake_thread_timer_cb, data: curr);
448
449 /* Publish the wait because shorter timers can fire before yield */
450 thread_prepare_to_sleep(t: curr, r: THREAD_SLEEP_REASON_MANUAL,
451 wait_type: THREAD_WAIT_UNINTERRUPTIBLE, expect_wake_src: curr);
452 timer_modify(timer: &sleep_timer, new: timer_delta_us(delta_us: us));
453
454 thread_yield_until_wake_match();
455 timer_delete_sync(timer: &sleep_timer);
456}
457
458void thread_sleep_for_ms(uint64_t ms) {
459 thread_sleep_for_us(MS_TO_US(ms));
460}
461
462void scheduler_wake_manual(struct thread *t, void *wake_src) {
463 enum thread_state s = thread_get_state(t);
464
465 if (s == THREAD_STATE_BLOCKED)
466 thread_wake(t, reason: THREAD_WAKE_REASON_BLOCKING_MANUAL,
467 prio: t->perceived_prio_class, wake_src);
468 else if (s == THREAD_STATE_SLEEPING)
469 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_MANUAL, prio: t->perceived_prio_class,
470 wake_src);
471}
472
473struct scheduler *thread_get_scheduler(struct thread *t, enum irql *sirql_out) {
474 do {
475 size_t gen1 = thread_get_migration_generation(t);
476 struct scheduler *sched = thread_get_scheduler_unsafe(t);
477 *sirql_out = spin_lock_irq_disable(&sched->lock);
478 size_t gen2 = thread_get_migration_generation(t);
479
480 if (gen1 == gen2 && !(gen1 & 1))
481 return sched;
482
483 spin_unlock(&sched->lock, *sirql_out);
484 } while (1);
485
486 panic("unreachable");
487}
488
489void thread_lock_two_runqueues(struct thread *a, struct thread *b,
490 struct scheduler **out_rq_a,
491 struct scheduler **out_rq_b, enum irql *irq_a,
492 enum irql *irq_b) {
493 size_t gen_a1 = 0;
494 size_t gen_a2 = 0;
495 size_t gen_b1 = 0;
496 size_t gen_b2 = 0;
497
498retry:
499 gen_a1 = thread_get_migration_generation(t: a);
500 gen_b1 = thread_get_migration_generation(t: b);
501
502 if ((gen_a1 | gen_b1) & 1)
503 goto retry;
504
505 struct scheduler *rq_a = thread_get_scheduler_unsafe(t: a);
506 struct scheduler *rq_b = thread_get_scheduler_unsafe(t: b);
507
508 gen_a2 = thread_get_migration_generation(t: a);
509 gen_b2 = thread_get_migration_generation(t: b);
510
511 /* Snapshot must be stable */
512 if (gen_a1 != gen_a2 || gen_b1 != gen_b2)
513 goto retry;
514
515 struct scheduler *first;
516 struct scheduler *second;
517
518 if (rq_a == rq_b) {
519 first = rq_a;
520 second = NULL;
521 } else if (rq_a < rq_b) {
522 first = rq_a;
523 second = rq_b;
524 } else {
525 first = rq_b;
526 second = rq_a;
527 }
528
529 *irq_a = spin_lock_irq_disable(&first->lock);
530
531 if (second)
532 *irq_b = spin_lock_irq_disable(&second->lock);
533
534 if (thread_get_migration_generation(t: a) != gen_a1 ||
535 thread_get_migration_generation(t: b) != gen_b1 ||
536 thread_get_scheduler_unsafe(t: a) != rq_a ||
537 thread_get_scheduler_unsafe(t: b) != rq_b) {
538
539 if (second)
540 spin_unlock(&second->lock, *irq_b);
541
542 spin_unlock(&first->lock, *irq_a);
543
544 goto retry;
545 }
546
547 *out_rq_a = rq_a;
548 *out_rq_b = rq_b;
549}
550
551void thread_lock_thread_and_rq(struct thread *t, struct scheduler *other_rq,
552 struct scheduler **out_thread_rq,
553 enum irql *irq_first, enum irql *irq_second) {
554 size_t gen1, gen2;
555
556retry:
557 gen1 = thread_get_migration_generation(t);
558
559 if (gen1 & 1)
560 goto retry;
561
562 struct scheduler *thread_rq = thread_get_scheduler_unsafe(t);
563
564 gen2 = thread_get_migration_generation(t);
565
566 if (gen1 != gen2)
567 goto retry;
568
569 struct scheduler *first;
570 struct scheduler *second;
571
572 if (thread_rq == other_rq) {
573 first = thread_rq;
574 second = NULL;
575 } else if (thread_rq < other_rq) {
576 first = thread_rq;
577 second = other_rq;
578 } else {
579 first = other_rq;
580 second = thread_rq;
581 }
582
583 *irq_first = spin_lock_irq_disable(&first->lock);
584
585 if (second)
586 *irq_second = spin_lock_irq_disable(&second->lock);
587
588 if (thread_get_migration_generation(t) != gen1 ||
589 thread_get_scheduler_unsafe(t) != thread_rq) {
590
591 if (second)
592 spin_unlock(&second->lock, *irq_second);
593
594 spin_unlock(&first->lock, *irq_first);
595 goto retry;
596 }
597
598 *out_thread_rq = thread_rq;
599}
600
601void thread_unlock_thread_and_rq(struct scheduler *thread_rq,
602 struct scheduler *other_rq,
603 enum irql irq_first, enum irql irq_second) {
604 struct scheduler *first;
605 struct scheduler *second;
606
607 if (thread_rq == other_rq) {
608 first = thread_rq;
609 second = NULL;
610 } else if (thread_rq < other_rq) {
611 first = thread_rq;
612 second = other_rq;
613 } else {
614 first = other_rq;
615 second = thread_rq;
616 }
617
618 if (second)
619 spin_unlock(&second->lock, irq_second);
620
621 spin_unlock(&first->lock, irq_first);
622}
623
624/* This is surprisngly tricky to implement */
625bool thread_in_context(void) {
626 if (global.current_bootstage < BOOTSTAGE_LATE)
627 return false;
628
629 if (irq_in_interrupt() || irq_in_nmi())
630 return false;
631
632 struct thread *self = thread_get_current();
633
634 return true;
635}
636