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 cc_ignore(thread);
42}
43
44static void thread_lock_chk_exit(struct thread *thread) {
45 cc_ignore(thread);
46}
47
48#endif
49
50SLAB_SIZE_REGISTER_FOR_STRUCT(thread, /*alignment*/ 32);
51
52ADDRESS_RANGE_DEFINE(thread_stacks, .name = "thread stacks",
53 .base = THREAD_STACKS_HEAP_START,
54 .size = THREAD_STACKS_HEAP_END - THREAD_STACKS_HEAP_START,
55 .flags = ADDRESS_RANGE_STATIC);
56
57/* lol */
58static struct tid_space *global_tid_space = NULL;
59static struct vas *stacks_space = NULL;
60
61void thread_init_thread_ids(void) {
62 stacks_space = vas_create(THREAD_STACKS_HEAP_START, THREAD_STACKS_HEAP_END);
63 global_tid_space = tid_space_init(UINT64_MAX);
64 locked_list_init(ll: &global.thread_list, LOCKED_LIST_INIT_IRQ_DISABLE);
65}
66
67void thread_exit(void) {
68 thread_exit_with_status(status: 0);
69}
70
71void thread_exit_with_status(int status) {
72 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
73
74 struct thread *self = thread_get_current();
75 thread_lock_chk_exit(thread: self);
76
77 /* Can't be in a critical section when we exit */
78 enforce(self->rcu_nesting == 0, "thread exited inside an RCU read section");
79
80 /* Public status and the ZOMBIE state under join_lock...
81 *
82 * Joiners either see ZOMBIE here are don't block, or are already
83 * parked on join_cv and gets the broadcast, no third outcome */
84 enum irql jirql = spin_lock(&self->join_lock);
85 self->exit_status = status;
86 thread_set_state(t: self, state: THREAD_STATE_ZOMBIE);
87 thread_or_flags(t: self, flags: THREAD_FLAG_DYING);
88 spin_unlock(&self->join_lock, jirql);
89
90 apc_rundown_thread(t: self);
91
92 /* Resumed joiners can't free because our ref stays alive
93 * until dropped by the next thread */
94 condvar_broadcast(cv: &self->join_cv);
95
96 climb_thread_remove(t: self);
97 locked_list_del(ll: &global.thread_list, lh: &self->thread_list);
98 atomic_dec(&global.thread_count);
99
100 irql_lower(old_level: irql);
101
102 scheduler_yield();
103 ci_unreachable();
104}
105
106static void thread_entry_wrapper(void) TSA_NO_ANALYSIS {
107 /* TODO: We might want to consider refactoring
108 * the switch_in so as to not gradually bloat up
109 * both places where the "gopher pops out of the ground",
110 * i.e. a thread entering */
111 scheduler_yield_nesting_reset(t: thread_get_current());
112
113 if (atomic_load_rlx(&thread_get_current()->state) !=
114 THREAD_STATE_IDLE_THREAD)
115 atomic_inc(&global.thread_count);
116
117 void (*entry)(void *);
118 asm volatile("mov %%r12, %0" : "=r"(entry));
119
120 void *arg;
121 asm volatile("mov %%r13, %0" : "=r"(arg));
122
123 scheduler_switch_in();
124
125 enforce(bootstage_get() < BOOTSTAGE_LATE ||
126 irql_get() == IRQL_DISPATCH_LEVEL,
127 INVALID_CONTEXT, "entered thread at %s, want %s",
128 irql_to_str(irql_get()), irql_to_str(IRQL_DISPATCH_LEVEL));
129
130 scheduler_mark_self_in_resched(false);
131
132 irql_lower(old_level: IRQL_PASSIVE_LEVEL);
133 enforce(entry);
134 entry(arg);
135 thread_exit();
136}
137
138static void *thread_allocate_stack(size_t pages) {
139 size_t needed = (pages + 1) * PAGE_SIZE;
140 vaddr_t virt_base = vas_alloc(vas: stacks_space, size: needed, PAGE_SIZE);
141 if (!virt_base)
142 return NULL;
143
144 /* Leave the first page unmapped, protector page */
145 virt_base += PAGE_SIZE;
146 for (size_t i = 0; i < pages; i++) {
147 vaddr_t virt = virt_base + (i * PAGE_SIZE);
148 paddr_t phys = enforce(pmm_alloc_page(), OUT_OF_MEMORY);
149 vmm_map_page(virt, phys,
150 .page_flags = PAGE_PRESENT | PAGE_WRITE | PAGE_XD);
151 }
152 return (void *) virt_base;
153}
154
155static void thread_free_stack(struct thread *thread) {
156 vaddr_t stack_real_virt = (vaddr_t) thread->stack - PAGE_SIZE;
157 size_t pages = thread->stack_size / PAGE_SIZE;
158 for (size_t i = 0; i < pages; i++) {
159 vaddr_t virt = (vaddr_t) thread->stack + i * PAGE_SIZE;
160 paddr_t phys = vmm_get_phys(virt);
161 enforce(phys != (paddr_t) -1);
162 vmm_unmap_page(virt);
163 pmm_free_page(addr: phys);
164 }
165 vas_free(vas: stacks_space, addr: stack_real_virt, size: (pages + 1) * PAGE_SIZE);
166}
167
168static void thread_init_activity_data(struct thread *thread) {
169 struct thread_activity_data *data = &thread->activity_data;
170 data->wait_start_ms = 0;
171 data->head = 0;
172 data->active_wait_reason = THREAD_EVENT_REASON_NONE;
173 for (size_t i = 0; i < THREAD_EVENT_RINGBUFFER_CAPACITY; i++) {
174 data->events[i].duration_ms = 0;
175 data->events[i].wait_reason = THREAD_EVENT_REASON_NONE;
176 data->events[i].wake_reason = THREAD_EVENT_REASON_NONE;
177 }
178}
179
180static struct thread *thread_init(struct thread *thread,
181 thread_entry_fn_t entry,
182 struct thread_create_params *params) {
183 thread_init_activity_data(thread);
184 thread_lock_chk_init(thread);
185 memset(&thread->activity_stats, 0, sizeof(struct thread_activity_stats));
186
187 uint64_t stack_top =
188 (uint64_t) params->stack_internal + params->stack_pages * PAGE_SIZE;
189 thread->allowed_cpus = params->allowed_cpus;
190 thread->private = params->private;
191
192 thread->entry = entry;
193
194#ifdef DEBUG_THREAD
195 thread->creation_time_ms = time_get_ms();
196#endif
197
198 if (params->pinned)
199 atomic_init(&thread->pinned_depth, 1);
200
201 thread->stack_size = params->stack_pages * PAGE_SIZE;
202 thread->regs.rsp = stack_top;
203 atomic_init(&thread->migrate_to, -1);
204 thread->base_prio_class = params->base_prio_class;
205 thread->niceness = 0;
206 thread->perceived_prio_class = params->base_prio_class;
207 memset(thread->class_floors, 0, sizeof(thread->class_floors));
208 atomic_init(&thread->state, THREAD_STATE_READY);
209 thread->regs.r12 = (uint64_t) entry;
210 thread->regs.r13 = (uint64_t) params->arg;
211 thread->regs.rip = (uint64_t) thread_entry_wrapper;
212 thread->stack = (void *) params->stack_internal;
213 atomic_init(&thread->flags, params->flags);
214 thread->curr_core = -1;
215 thread->rcu_nesting = 0;
216 thread->rcu_read_seq = 0;
217 thread->rcu_leaf = NULL;
218 thread->rcu_blocked_seq = 0;
219 thread->id = tid_alloc(ts: global_tid_space);
220 refcount_init(rc: &thread->refcount, val: 1);
221 thread->timeslice_length_raw_ms = THREAD_DEFAULT_TIMESLICE;
222 atomic_init(&thread->wait_type, THREAD_WAIT_NONE);
223 thread->activity_class = THREAD_ACTIVITY_CLASS_UNKNOWN;
224 thread->exit_status = 0;
225 spinlock_init(&thread->lock);
226 thread_wait_init(thread);
227 spinlock_init(&thread->join_lock);
228 spinlock_init(&thread->pi_lock);
229
230 /* join_lock/join_cv are only ever touched from thread context, and
231 * thread_join_timeout() has to allocate a timer while holding the
232 * lock, which it could not do at IRQL_HIGH_LEVEL */
233 condvar_init(cv: &thread->join_cv);
234
235 turnstile_init(ts: thread->turnstile);
236
237 thread_update_effective_priority(t: thread);
238
239 climb_thread_init(t: thread);
240 list_head_init(h: &thread->io_wait_tokens);
241 list_node_init(n: &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 list_node_init(n: &thread->rq_list_node);
247 list_node_init(n: &thread->wq_list_node);
248 list_node_init(n: &thread->rcu_list_node);
249 list_node_init(n: &thread->reaper_list);
250 rbt_init_node(n: &thread->rq_tree_node);
251 rbt_init_node(n: &thread->wq_tree_node);
252 crash_thread_init(t: thread);
253 locked_list_add(ll: &global.thread_list, lh: &thread->thread_list);
254
255 return thread;
256}
257
258struct thread *thread_create_full(char *cc_nonnull_ptr name,
259 thread_entry_fn_t entry,
260 struct thread_create_params *params,
261 va_list args) {
262 enforce_precond(name, "thread name must be provided");
263 struct thread *new_thread = vnew(new_thread, ALLOC_ZERO);
264 if (cc_unlikely(!new_thread))
265 goto err;
266
267 void *stack = thread_allocate_stack(pages: params->stack_pages);
268 if (cc_unlikely(!stack))
269 goto err;
270
271 params->stack_internal = stack;
272
273 new_thread->turnstile = turnstile_create();
274 if (cc_unlikely(!new_thread->turnstile))
275 goto err;
276
277 cpu_mask_init(m: &new_thread->allowed_cpus, nbits: global.core_count);
278
279 cpu_mask_set_all(&new_thread->allowed_cpus);
280
281 va_list args_copy;
282 va_copy(args_copy, args);
283 size_t needed = vsnprintf(NULL, 0, name, args_copy) + 1;
284 va_end(args_copy);
285
286 new_thread->name = valloc(needed, ALLOC_ZERO);
287 if (!new_thread->name)
288 goto err;
289
290#ifdef DEBUG_THREAD
291 struct log_site_options opts = {
292 .name = new_thread->name,
293 .dump_opts = LOG_DUMP_DEFAULT,
294 .capacity = 16,
295 .flags = LOG_SITE_DEFAULT,
296 .enabled_mask = LOG_SITE_ALL,
297 };
298
299 new_thread->log_site = log_site_create(opts);
300 if (!new_thread->log_site)
301 goto err;
302
303 new_thread->log_handle = LOG_HANDLE_DEFAULT;
304#endif
305
306 va_copy(args_copy, args);
307 vsnprintf(new_thread->name, needed, name, args_copy);
308 va_end(args_copy);
309
310 return thread_init(thread: new_thread, entry, params);
311
312err:
313 if (!new_thread)
314 return NULL;
315
316 vfree(new_thread->turnstile);
317 vfree(new_thread->name);
318 thread_free_stack(thread: new_thread);
319 tid_free(ts: global_tid_space, id: new_thread->id);
320 vfree(new_thread);
321
322 return NULL;
323}
324
325/* TODO: This funny business is not needed with RCU */
326void thread_set_joinable(struct thread *t) {
327 enforce(!(thread_get_flags(t) & THREAD_FLAG_JOINABLE));
328 enforce(refcount_inc(&t->refcount), STALE_REFERENCE);
329 thread_set_flag(t, flag: THREAD_FLAG_JOINABLE);
330}
331
332struct thread *thread_create_internal(thread_entry_fn_t entry,
333 struct thread_create_params params,
334 char *fmt, ...) {
335 va_list args;
336 va_start(args, fmt);
337 struct thread *ret = thread_create_full(name: fmt, entry, params: &params, args);
338 va_end(args);
339 if (ret && params.joinable)
340 thread_set_joinable(t: ret);
341
342 return ret;
343}
344
345struct thread *thread_spawn_internal(thread_entry_fn_t entry,
346 struct thread_create_params params,
347 char *fmt, ...) {
348 va_list args;
349 va_start(args, fmt);
350 struct thread *t = thread_create_full(name: fmt, entry, params: &params, args);
351 va_end(args);
352
353 if (t && params.joinable)
354 thread_set_joinable(t);
355
356 if (t && params.on_cpu == CPU_ID_MAX) {
357 thread_enqueue(t);
358 } else if (t) {
359 thread_enqueue_on_core(t, core_id: params.on_cpu);
360 }
361
362 return t;
363}
364
365void thread_free(struct thread *t) {
366 tid_free(ts: global_tid_space, id: t->id);
367 vfree(t->name);
368 vfree(t->turnstile);
369 apc_rundown_thread(t);
370 thread_free_stack(thread: t);
371
372#ifdef DEBUG_THREAD
373 log_site_putref(t->log_site);
374#endif
375
376 vfree(t);
377}
378
379static void thread_reap_rcu(struct rcu_cb *cb) {
380 reaper_enqueue(container_of(cb, struct thread, free_rcu));
381}
382
383void thread_putref(struct thread *t) {
384 if (!refcount_dec_and_test(rc: &t->refcount))
385 return;
386
387 if (thread_get_state(t) != THREAD_STATE_ZOMBIE)
388 panic("final ref dropped while thread not zombie");
389
390 rcu_defer(cb: &t->free_rcu, func: thread_reap_rcu);
391}
392
393void thread_queue_init(struct thread_queue *q) {
394 list_head_init(h: &q->list);
395 spinlock_init(&q->lock);
396}
397
398void thread_queue_push_back(struct thread_queue *q, struct thread *t) {
399 enum irql irql = spin_lock_high(&q->lock);
400 list_head_push_back(h: &q->list, n: &t->wq_list_node);
401 spin_unlock(&q->lock, irql);
402}
403
404bool thread_queue_remove(struct thread_queue *q, struct thread *t) {
405 enum irql irql = spin_lock_high(&q->lock);
406 struct list_node *pos;
407
408 list_for_each(pos, &q->list) {
409 struct thread *thread = thread_from_wq_list_node(pos);
410 if (thread == t) {
411 list_node_delete_init(n: &t->wq_list_node);
412 spin_unlock(&q->lock, irql);
413 return true;
414 }
415 }
416
417 spin_unlock(&q->lock, irql);
418 return false;
419}
420
421struct thread *thread_queue_pop_front(struct thread_queue *q) {
422 enum irql irql = spin_lock_high(&q->lock);
423 struct list_node *lhead = list_head_pop_front_init(h: &q->list);
424 spin_unlock(&q->lock, irql);
425 if (!lhead)
426 return NULL;
427
428 return thread_from_wq_list_node(lhead);
429}
430
431static void wake_thread_timer_cb(struct timer *timer) {
432 struct thread_wait_header *wait = timer->data;
433 thread_wait_header_satisfy(hdr: wait, reason: THREAD_WAKE_REASON_SLEEP_TIMEOUT, NULL);
434}
435
436void thread_sleep_for_us(uint64_t us) {
437 if (us == 0) {
438 scheduler_yield();
439 return;
440 }
441
442 struct thread_wait_header wait;
443 thread_wait_header_init(header: &wait);
444 struct timer sleep_timer;
445 timer_init(timer: &sleep_timer, func: wake_thread_timer_cb, data: &wait);
446
447 thread_wait_prepare_to_sleep(header: &wait, object: &sleep_timer,
448 type: THREAD_WAIT_UNINTERRUPTIBLE);
449 timer_modify(timer: &sleep_timer, new: timer_delta_us(delta_us: us));
450
451 thread_wait_complete();
452 timer_delete_sync(timer: &sleep_timer);
453}
454
455void thread_sleep_for_ms(uint64_t ms) {
456 thread_sleep_for_us(MS_TO_US(ms));
457}
458
459enum irql thread_lock_scheduler(struct thread *t, struct scheduler **out_sched)
460 TSA_ACQUIRES_SPIN(&(*out_sched)->lock) TSA_NO_ANALYSIS {
461 do {
462 size_t gen1 = thread_get_migration_generation(t);
463 struct scheduler *sched = thread_get_scheduler_unsafe(t);
464 enum irql sirql = spin_lock_high(&sched->lock);
465 size_t gen2 = thread_get_migration_generation(t);
466
467 if (gen1 == gen2 && !(gen1 & 1)) {
468 *out_sched = sched;
469 return sirql;
470 }
471
472 spin_unlock(&sched->lock, sirql);
473 } while (true);
474
475 unreachable();
476}
477
478void thread_lock_two_runqueues(struct thread *a, struct thread *b,
479 struct scheduler **out_rq_a,
480 struct scheduler **out_rq_b, enum irql *irq_a,
481 enum irql *irq_b) TSA_NO_ANALYSIS {
482 size_t gen_a1 = 0;
483 size_t gen_a2 = 0;
484 size_t gen_b1 = 0;
485 size_t gen_b2 = 0;
486
487retry:
488 gen_a1 = thread_get_migration_generation(t: a);
489 gen_b1 = thread_get_migration_generation(t: b);
490
491 if ((gen_a1 | gen_b1) & 1)
492 goto retry;
493
494 struct scheduler *rq_a = thread_get_scheduler_unsafe(t: a);
495 struct scheduler *rq_b = thread_get_scheduler_unsafe(t: b);
496
497 gen_a2 = thread_get_migration_generation(t: a);
498 gen_b2 = thread_get_migration_generation(t: b);
499
500 /* Snapshot must be stable */
501 if (gen_a1 != gen_a2 || gen_b1 != gen_b2)
502 goto retry;
503
504 struct scheduler *first, *second;
505
506 if (rq_a == rq_b) {
507 first = rq_a;
508 second = NULL;
509 } else if (rq_a < rq_b) {
510 first = rq_a;
511 second = rq_b;
512 } else {
513 first = rq_b;
514 second = rq_a;
515 }
516
517 enum irql first_irql = spin_lock_high(&first->lock);
518 enum irql second_irql = first_irql;
519
520 if (second)
521 second_irql = spin_lock_high(&second->lock);
522
523 if (thread_get_migration_generation(t: a) != gen_a1 ||
524 thread_get_migration_generation(t: b) != gen_b1 ||
525 thread_get_scheduler_unsafe(t: a) != rq_a ||
526 thread_get_scheduler_unsafe(t: b) != rq_b) {
527
528 if (second)
529 spin_unlock(&second->lock, second_irql);
530
531 spin_unlock(&first->lock, first_irql);
532
533 goto retry;
534 }
535
536 *out_rq_a = rq_a;
537 *out_rq_b = rq_b;
538 *irq_a = rq_a == first ? first_irql : second_irql;
539 *irq_b = rq_b == first ? first_irql : second_irql;
540}
541
542void thread_lock_thread_and_rq(struct thread *t, struct scheduler *other_rq,
543 struct scheduler **out_thread_rq,
544 enum irql *irq_first,
545 enum irql *irq_second) TSA_NO_ANALYSIS {
546 size_t gen1, gen2;
547
548retry:
549 gen1 = thread_get_migration_generation(t);
550
551 if (gen1 & 1)
552 goto retry;
553
554 struct scheduler *thread_rq = thread_get_scheduler_unsafe(t);
555
556 gen2 = thread_get_migration_generation(t);
557
558 if (gen1 != gen2)
559 goto retry;
560
561 struct scheduler *first, *second;
562
563 if (thread_rq == other_rq) {
564 first = thread_rq;
565 second = NULL;
566 } else if (thread_rq < other_rq) {
567 first = thread_rq;
568 second = other_rq;
569 } else {
570 first = other_rq;
571 second = thread_rq;
572 }
573
574 *irq_first = spin_lock_high(&first->lock);
575
576 if (second)
577 *irq_second = spin_lock_high(&second->lock);
578
579 if (thread_get_migration_generation(t) != gen1 ||
580 thread_get_scheduler_unsafe(t) != thread_rq) {
581
582 if (second)
583 spin_unlock(&second->lock, *irq_second);
584
585 spin_unlock(&first->lock, *irq_first);
586 goto retry;
587 }
588
589 *out_thread_rq = thread_rq;
590}
591
592void thread_unlock_thread_and_rq(struct scheduler *thread_rq,
593 struct scheduler *other_rq,
594 enum irql irq_first,
595 enum irql irq_second) TSA_NO_ANALYSIS {
596 struct scheduler *first, *second;
597
598 if (thread_rq == other_rq) {
599 first = thread_rq;
600 second = NULL;
601 } else if (thread_rq < other_rq) {
602 first = thread_rq;
603 second = other_rq;
604 } else {
605 first = other_rq;
606 second = thread_rq;
607 }
608
609 if (second)
610 spin_unlock(&second->lock, irq_second);
611
612 spin_unlock(&first->lock, irq_first);
613}
614
615void thread_lock_two_pi_locks(struct thread *cc_nonnull_ptr a,
616 struct thread *cc_nonnull_ptr b, enum irql *irq_a,
617 enum irql *irq_b) TSA_NO_ANALYSIS {
618 enforce_precond(a && b && a != b);
619 if (a < b) {
620 *irq_a = spin_lock_high_subclass(&a->pi_lock, LOCK_SUBCLASS_LOWER);
621 *irq_b = spin_lock_high_subclass(&b->pi_lock, LOCK_SUBCLASS_HIGHER);
622 } else {
623 *irq_b = spin_lock_high_subclass(&b->pi_lock, LOCK_SUBCLASS_LOWER);
624 *irq_a = spin_lock_high_subclass(&a->pi_lock, LOCK_SUBCLASS_HIGHER);
625 }
626}
627
628void thread_unlock_two_pi_locks(struct thread *cc_nonnull_ptr a,
629 struct thread *cc_nonnull_ptr b,
630 enum irql *irq_a,
631 enum irql *irq_b) TSA_NO_ANALYSIS {
632 enforce_precond(a && b && a != b);
633 if (a < b) {
634 spin_unlock(&b->pi_lock, *irq_b);
635 spin_unlock(&a->pi_lock, *irq_a);
636 } else {
637 spin_unlock(&a->pi_lock, *irq_a);
638 spin_unlock(&b->pi_lock, *irq_b);
639 }
640}
641
642/* TODO: This is surprisngly tricky to implement, and the primary reason why
643 * is because of invocations during boundaries. */
644bool thread_in_context(void) {
645 if (global.current_bootstage < BOOTSTAGE_LATE)
646 return false;
647
648 if (irq_in_interrupt() || irq_in_nmi())
649 return false;
650
651 struct thread *self = thread_get_current();
652 if (thread_test_flag(t: self, flag: THREAD_FLAG_EXECUTING_APC))
653 return false;
654
655 return true;
656}
657