1#include <log.h>
2#include <mem/address_range.h>
3#include <mem/alloc.h>
4#include <mem/pmm.h>
5#include <mem/slab.h>
6#include <mem/vas.h>
7#include <mem/vmm.h>
8#include <sch/periodic_work.h>
9#include <sch/sched.h>
10#include <smp/domain.h>
11#include <stdbool.h>
12#include <stddef.h>
13#include <string.h>
14#include <sync/rcu.h>
15#include <sync/turnstile.h>
16#include <thread/apc.h>
17#include <thread/reaper.h>
18#include <thread/thread.h>
19#include <thread/tid.h>
20#include <thread/workqueue.h>
21
22#include "sch/internal.h"
23
24SLAB_SIZE_REGISTER_FOR_STRUCT(thread, /*alignment*/ 32);
25
26#define THREAD_STACKS_HEAP_START 0xFFFFF10000000000ULL
27#define THREAD_STACKS_HEAP_END 0xFFFFF20000000000ULL
28
29ADDRESS_RANGE_DECLARE(thread_stacks, .name = "thread stacks",
30 .base = THREAD_STACKS_HEAP_START,
31 .size = THREAD_STACKS_HEAP_END - THREAD_STACKS_HEAP_START,
32 .flags = ADDRESS_RANGE_STATIC);
33
34/* lol */
35static struct tid_space *global_tid_space = NULL;
36static struct vas *stacks_space = NULL;
37
38void thread_init_thread_ids(void) {
39 stacks_space = vas_create(THREAD_STACKS_HEAP_START, THREAD_STACKS_HEAP_END);
40 global_tid_space = tid_space_init(UINT64_MAX);
41 locked_list_init(ll: &global.thread_list, LOCKED_LIST_INIT_IRQ_DISABLE);
42}
43
44APC_EVENT_CREATE(thread_exit_apc_event, "THREAD_EXIT");
45void thread_exit() {
46 enum irql irql = irql_raise(new_level: IRQL_DISPATCH_LEVEL);
47
48 struct thread *self = thread_get_current();
49
50 thread_set_state(t: self, state: THREAD_STATE_ZOMBIE);
51 thread_or_flags(t: self, flags: THREAD_FLAG_DYING);
52
53 climb_thread_remove(t: self);
54
55 locked_list_del(ll: &global.thread_list, lh: &self->thread_list);
56
57 atomic_fetch_sub(&global.thread_count, 1);
58
59 irql_lower(old_level: irql);
60
61 scheduler_yield();
62}
63
64void thread_entry_wrapper(void) {
65 if (thread_get_current()->state != THREAD_STATE_IDLE_THREAD)
66 atomic_fetch_add(&global.thread_count, 1);
67
68 void (*entry)(void *);
69 asm volatile("mov %%r12, %0" : "=r"(entry));
70
71 void *arg;
72 asm volatile("mov %%r13, %0" : "=r"(arg));
73
74 scheduler_switch_in();
75
76 kassert(irql_get() < IRQL_HIGH_LEVEL);
77
78 scheduler_mark_self_in_resched(false);
79
80 irql_lower(old_level: IRQL_PASSIVE_LEVEL);
81 kassert(entry);
82 entry(arg);
83 thread_exit();
84}
85
86void *thread_allocate_stack(size_t pages) {
87 size_t needed = (pages + 1) * PAGE_SIZE;
88 vaddr_t virt_base = vas_alloc(vas: stacks_space, size: needed, PAGE_SIZE);
89
90 /* Leave the first page unmapped, protector page */
91 virt_base += PAGE_SIZE;
92 for (size_t i = 0; i < pages; i++) {
93 vaddr_t virt = virt_base + (i * PAGE_SIZE);
94 paddr_t phys = pmm_alloc_page();
95 kassert(phys);
96 vmm_map_page(virt, phys, PAGE_PRESENT | PAGE_WRITE | PAGE_XD,
97 VMM_FLAG_NONE);
98 }
99 return (void *) virt_base;
100}
101
102void thread_free_stack(struct thread *thread) {
103 vaddr_t stack_real_virt = (vaddr_t) thread->stack - PAGE_SIZE;
104 size_t pages = thread->stack_size / PAGE_SIZE;
105 for (size_t i = 0; i < pages; i++) {
106 vaddr_t virt = (vaddr_t) thread->stack + i * PAGE_SIZE;
107 paddr_t phys = vmm_get_phys(virt, VMM_FLAG_NONE);
108 kassert(phys != (paddr_t) -1);
109 vmm_unmap_page(virt);
110 pmm_free_page(addr: phys);
111 }
112 vas_free(vas: stacks_space, addr: stack_real_virt, size: thread->stack_size);
113}
114
115static void thread_init_event_reasons(
116 struct thread_event_reason reasons[THREAD_EVENT_RINGBUFFER_CAPACITY]) {
117 for (size_t i = 0; i < THREAD_EVENT_RINGBUFFER_CAPACITY; i++) {
118 reasons[i].associated_reason.reason = THREAD_EVENT_REASON_NONE;
119 reasons[i].associated_reason.cycle = 0;
120 reasons[i].reason = THREAD_EVENT_REASON_NONE;
121 reasons[i].cycle = 0;
122 reasons[i].timestamp = 0;
123 }
124}
125
126static void thread_init_activity_data(struct thread *thread) {
127 struct thread_activity_data *data = thread->activity_data;
128 data->block_reasons_head = 0;
129 data->sleep_reasons_head = 0;
130 data->wake_reasons_head = 0;
131 thread_init_event_reasons(reasons: thread->activity_data->block_reasons);
132 thread_init_event_reasons(reasons: thread->activity_data->wake_reasons);
133 thread_init_event_reasons(reasons: thread->activity_data->sleep_reasons);
134}
135
136static struct thread *thread_init(struct thread *thread,
137 void (*entry_point)(void *), void *arg,
138 void *stack, size_t stack_size) {
139 thread_init_activity_data(thread);
140 memset(thread->activity_stats, 0, sizeof(struct thread_activity_stats));
141
142 uint64_t stack_top = (uint64_t) stack + stack_size;
143 thread->entry = entry_point;
144 thread->creation_time_ms = time_get_ms();
145 thread->stack_size = stack_size;
146 thread->regs.rsp = stack_top;
147 thread->migrate_to = -1;
148 thread->base_prio_class = THREAD_PRIO_CLASS_TIMESHARE;
149 thread->niceness = 0;
150 thread->perceived_prio_class = THREAD_PRIO_CLASS_TIMESHARE;
151 thread->state = THREAD_STATE_READY;
152 thread->regs.r12 = (uint64_t) entry_point;
153 thread->regs.r13 = (uint64_t) arg;
154 thread->regs.rip = (uint64_t) thread_entry_wrapper;
155 thread->stack = (void *) stack;
156 thread->flags = 0;
157 thread->curr_core = -1;
158 thread->rcu_quiescent_gen = UINT64_MAX;
159 thread->id = tid_alloc(ts: global_tid_space);
160 thread->refcount = 1;
161 thread->timeslice_length_raw_ms = THREAD_DEFAULT_TIMESLICE;
162 thread->wait_type = THREAD_WAIT_NONE;
163 thread->activity_class = THREAD_ACTIVITY_CLASS_UNKNOWN;
164 spinlock_init(lock: &thread->lock);
165 pairing_node_init(pn: &thread->wq_pairing_node);
166
167 turnstile_init(ts: thread->turnstile);
168
169 thread_update_effective_priority(t: thread);
170
171 climb_thread_init(t: thread);
172 INIT_LIST_HEAD(list: &thread->io_wait_tokens);
173 INIT_LIST_HEAD(list: &thread->thread_list);
174
175 for (size_t i = 0; i < APC_TYPE_COUNT; i++)
176 apc_queue_init(q: &thread->apc_head[i]);
177
178 apc_queue_init(q: &thread->event_apcs);
179 apc_queue_init(q: &thread->to_exec_event_apcs);
180
181 INIT_LIST_HEAD(list: &thread->rq_list_node);
182 INIT_LIST_HEAD(list: &thread->wq_list_node);
183 INIT_LIST_HEAD(list: &thread->rcu_list_node);
184 INIT_LIST_HEAD(list: &thread->reaper_list);
185 rbt_init_node(n: &thread->rq_tree_node);
186 rbt_init_node(n: &thread->wq_tree_node);
187
188 locked_list_add(ll: &global.thread_list, lh: &thread->thread_list);
189
190 return thread;
191}
192
193struct thread *thread_create_internal(char *name, void (*entry_point)(void *),
194 void *arg, size_t stack_size,
195 va_list args) {
196 kassert(name);
197 struct thread *new_thread =
198 kmalloc(sizeof(struct thread), ALLOC_FLAGS_ZERO);
199 if (unlikely(!new_thread))
200 goto err;
201
202 void *stack = thread_allocate_stack(pages: stack_size / PAGE_SIZE);
203 if (unlikely(!stack))
204 goto err;
205
206 new_thread->activity_data =
207 kmalloc(sizeof(struct thread_activity_data), ALLOC_FLAGS_ZERO);
208 if (unlikely(!new_thread->activity_data))
209 goto err;
210
211 new_thread->turnstile = turnstile_create();
212 if (unlikely(!new_thread->turnstile))
213 goto err;
214
215 new_thread->activity_stats =
216 kmalloc(sizeof(struct thread_activity_stats), ALLOC_FLAGS_ZERO);
217 if (unlikely(!new_thread->activity_stats))
218 goto err;
219
220 if (unlikely(!cpu_mask_init(&new_thread->allowed_cpus, global.core_count)))
221 goto err;
222
223 cpu_mask_set_all(m: &new_thread->allowed_cpus);
224
225 va_list args_copy;
226 va_copy(args_copy, args);
227 size_t needed = vsnprintf(NULL, buffer_len: 0, format: name, args: args_copy) + 1;
228 va_end(args_copy);
229
230 new_thread->name = kmalloc(needed, ALLOC_FLAGS_ZERO);
231 if (!new_thread->name)
232 goto err;
233
234 struct log_site_options opts = {
235 .name = new_thread->name,
236 .dump_opts = LOG_DUMP_DEFAULT,
237 .capacity = 16,
238 .flags = LOG_SITE_DEFAULT,
239 .enabled_mask = LOG_SITE_ALL,
240 };
241
242 new_thread->log_site = log_site_create(opts);
243 if (!new_thread->log_site)
244 goto err;
245
246 va_copy(args_copy, args);
247 vsnprintf(buffer: new_thread->name, buffer_len: needed, format: name, args: args_copy);
248 va_end(args_copy);
249
250 return thread_init(thread: new_thread, entry_point, arg, stack, stack_size);
251
252err:
253 if (!new_thread)
254 return NULL;
255
256 kfree(new_thread->turnstile);
257 kfree(new_thread->name);
258 kfree(new_thread->activity_data);
259 kfree(new_thread->activity_stats);
260 thread_free_stack(thread: new_thread);
261 tid_free(ts: global_tid_space, id: new_thread->id);
262 kfree(new_thread);
263
264 return NULL;
265}
266
267struct thread *thread_create(char *name, void (*entry_point)(void *), void *arg,
268 ...) {
269 va_list args;
270 va_start(args, arg);
271 struct thread *ret =
272 thread_create_internal(name, entry_point, arg, THREAD_STACK_SIZE, args);
273 va_end(args);
274 return ret;
275}
276
277struct thread *thread_create_custom_stack(char *name,
278 void (*entry_point)(void *),
279 void *arg, size_t stack_size, ...) {
280 va_list args;
281 va_start(args, stack_size);
282 struct thread *ret =
283 thread_create_internal(name, entry_point, arg, stack_size, args);
284 va_end(args);
285 return ret;
286}
287
288void thread_free(struct thread *t) {
289 tid_free(ts: global_tid_space, id: t->id);
290 kfree(t->activity_data);
291 kfree(t->activity_stats);
292 kfree(t->name);
293 kfree(t->turnstile);
294 apc_free_on_thread(t);
295 thread_free_stack(thread: t);
296 log_site_put(site: t->log_site);
297 kfree(t);
298}
299
300void thread_queue_init(struct thread_queue *q) {
301 INIT_LIST_HEAD(list: &q->list);
302 spinlock_init(lock: &q->lock);
303}
304
305void thread_queue_push_back(struct thread_queue *q, struct thread *t) {
306 enum irql irql = spin_lock_irq_disable(lock: &q->lock);
307 list_add_tail(new: &t->wq_list_node, head: &q->list);
308 spin_unlock(lock: &q->lock, old: irql);
309}
310
311bool thread_queue_remove(struct thread_queue *q, struct thread *t) {
312 enum irql irql = spin_lock_irq_disable(lock: &q->lock);
313 struct list_head *pos;
314
315 list_for_each(pos, &q->list) {
316 struct thread *thread = thread_from_wq_list_node(pos);
317 if (thread == t) {
318 list_del_init(entry: &t->wq_list_node);
319 spin_unlock(lock: &q->lock, old: irql);
320 return true;
321 }
322 }
323
324 spin_unlock(lock: &q->lock, old: irql);
325 return false;
326}
327
328struct thread *thread_queue_pop_front(struct thread_queue *q) {
329 enum irql irql = spin_lock_irq_disable(lock: &q->lock);
330 struct list_head *lhead = list_pop_front_init(head: &q->list);
331 spin_unlock(lock: &q->lock, old: irql);
332 if (!lhead)
333 return NULL;
334
335 return thread_from_wq_list_node(lhead);
336}
337
338void thread_block_on(struct thread_queue *q, enum thread_wait_type type,
339 void *wake_src) {
340 struct thread *current = thread_get_current();
341
342 enum irql irql = spin_lock_irq_disable(lock: &q->lock);
343 thread_prepare_to_block(t: current, r: THREAD_BLOCK_REASON_MANUAL, wait_type: type,
344 expect_wake_src: wake_src);
345 list_add_tail(new: &current->wq_list_node, head: &q->list);
346 spin_unlock(lock: &q->lock, old: irql);
347}
348
349static void wake_thread(void *a, void *unused) {
350 (void) unused;
351 struct thread *t = a;
352 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_TIMEOUT, prio: t->perceived_prio_class,
353 wake_src: t);
354}
355
356void thread_sleep_for_ms(uint64_t ms) {
357 struct thread *curr = thread_get_current();
358 defer_enqueue(func: wake_thread, WORK_ARGS(curr, NULL), delay_ms: ms);
359 thread_prepare_to_sleep(t: curr, r: THREAD_SLEEP_REASON_MANUAL,
360 wait_type: THREAD_WAIT_UNINTERRUPTIBLE, expect_wake_src: curr);
361
362 thread_yield_until_wake_match();
363}
364
365void scheduler_wake_manual(struct thread *t, void *wake_src) {
366 enum thread_state s = thread_get_state(t);
367
368 if (s == THREAD_STATE_BLOCKED)
369 thread_wake(t, reason: THREAD_WAKE_REASON_BLOCKING_MANUAL,
370 prio: t->perceived_prio_class, wake_src);
371 else if (s == THREAD_STATE_SLEEPING)
372 thread_wake(t, reason: THREAD_WAKE_REASON_SLEEP_MANUAL, prio: t->perceived_prio_class,
373 wake_src);
374}
375
376struct scheduler *thread_get_scheduler(struct thread *t, enum irql *sirql_out) {
377 do {
378 size_t gen1 = thread_get_migration_generation(t);
379 struct scheduler *sched = thread_get_scheduler_unsafe(t);
380 *sirql_out = spin_lock_irq_disable(lock: &sched->lock);
381 size_t gen2 = thread_get_migration_generation(t);
382
383 if (gen1 == gen2 && !(gen1 & 1))
384 return sched;
385
386 spin_unlock(lock: &sched->lock, old: *sirql_out);
387 } while (1);
388
389 panic("unreachable");
390}
391
392void thread_lock_two_runqueues(struct thread *a, struct thread *b,
393 struct scheduler **out_rq_a,
394 struct scheduler **out_rq_b, enum irql *irq_a,
395 enum irql *irq_b) {
396 size_t gen_a1 = 0;
397 size_t gen_a2 = 0;
398 size_t gen_b1 = 0;
399 size_t gen_b2 = 0;
400
401retry:
402 gen_a1 = thread_get_migration_generation(t: a);
403 gen_b1 = thread_get_migration_generation(t: b);
404
405 if ((gen_a1 | gen_b1) & 1)
406 goto retry;
407
408 struct scheduler *rq_a = thread_get_scheduler_unsafe(t: a);
409 struct scheduler *rq_b = thread_get_scheduler_unsafe(t: b);
410
411 gen_a2 = thread_get_migration_generation(t: a);
412 gen_b2 = thread_get_migration_generation(t: b);
413
414 /* Snapshot must be stable */
415 if (gen_a1 != gen_a2 || gen_b1 != gen_b2)
416 goto retry;
417
418 struct scheduler *first;
419 struct scheduler *second;
420
421 if (rq_a == rq_b) {
422 first = rq_a;
423 second = NULL;
424 } else if (rq_a < rq_b) {
425 first = rq_a;
426 second = rq_b;
427 } else {
428 first = rq_b;
429 second = rq_a;
430 }
431
432 *irq_a = spin_lock_irq_disable(lock: &first->lock);
433
434 if (second)
435 *irq_b = spin_lock_irq_disable(lock: &second->lock);
436
437 if (thread_get_migration_generation(t: a) != gen_a1 ||
438 thread_get_migration_generation(t: b) != gen_b1 ||
439 thread_get_scheduler_unsafe(t: a) != rq_a ||
440 thread_get_scheduler_unsafe(t: b) != rq_b) {
441
442 if (second)
443 spin_unlock(lock: &second->lock, old: *irq_b);
444
445 spin_unlock(lock: &first->lock, old: *irq_a);
446
447 goto retry;
448 }
449
450 *out_rq_a = rq_a;
451 *out_rq_b = rq_b;
452}
453
454void thread_lock_thread_and_rq(struct thread *t, struct scheduler *other_rq,
455 struct scheduler **out_thread_rq,
456 enum irql *irq_first, enum irql *irq_second) {
457 size_t gen1, gen2;
458
459retry:
460 gen1 = thread_get_migration_generation(t);
461
462 if (gen1 & 1)
463 goto retry;
464
465 struct scheduler *thread_rq = thread_get_scheduler_unsafe(t);
466
467 gen2 = thread_get_migration_generation(t);
468
469 if (gen1 != gen2)
470 goto retry;
471
472 struct scheduler *first;
473 struct scheduler *second;
474
475 if (thread_rq == other_rq) {
476 first = thread_rq;
477 second = NULL;
478 } else if (thread_rq < other_rq) {
479 first = thread_rq;
480 second = other_rq;
481 } else {
482 first = other_rq;
483 second = thread_rq;
484 }
485
486 *irq_first = spin_lock_irq_disable(lock: &first->lock);
487
488 if (second)
489 *irq_second = spin_lock_irq_disable(lock: &second->lock);
490
491 if (thread_get_migration_generation(t) != gen1 ||
492 thread_get_scheduler_unsafe(t) != thread_rq) {
493
494 if (second)
495 spin_unlock(lock: &second->lock, old: *irq_second);
496
497 spin_unlock(lock: &first->lock, old: *irq_first);
498 goto retry;
499 }
500
501 *out_thread_rq = thread_rq;
502}
503
504void thread_unlock_thread_and_rq(struct scheduler *thread_rq,
505 struct scheduler *other_rq,
506 enum irql irq_first, enum irql irq_second) {
507 struct scheduler *first;
508 struct scheduler *second;
509
510 if (thread_rq == other_rq) {
511 first = thread_rq;
512 second = NULL;
513 } else if (thread_rq < other_rq) {
514 first = thread_rq;
515 second = other_rq;
516 } else {
517 first = other_rq;
518 second = thread_rq;
519 }
520
521 if (second)
522 spin_unlock(lock: &second->lock, old: irq_second);
523
524 spin_unlock(lock: &first->lock, old: irq_first);
525}
526