1#![allow(clippy::type_complexity)]
2
3#[cfg(not(feature = "common-os"))]
4use alloc::boxed::Box;
5use alloc::collections::{LinkedList, VecDeque};
6use alloc::rc::Rc;
7use alloc::sync::Arc;
8use core::cell::RefCell;
9use core::num::NonZeroU64;
10use core::{cmp, fmt};
11
12use ahash::RandomState;
13use crossbeam_utils::CachePadded;
14use hashbrown::HashMap;
15use hermit_sync::{OnceCell, RwSpinLock};
16use memory_addresses::VirtAddr;
17
18use crate::arch::core_local::*;
19use crate::arch::scheduler::TaskStacks;
20#[cfg(not(feature = "common-os"))]
21use crate::arch::scheduler::TaskTLS;
22use crate::errno::Errno;
23use crate::executor::poll_on;
24use crate::fd::stdio::*;
25use crate::fd::{FileDescriptor, ObjectInterface, STDERR_FILENO, STDIN_FILENO, STDOUT_FILENO};
26use crate::scheduler::CoreId;
27use crate::{arch, env};
28
29#[inline]
39fn msb(n: u64) -> Option<u32> {
40 NonZeroU64::new(n).map(|n| u64::BITS - 1 - n.leading_zeros())
41}
42
43#[derive(Copy, Clone, Debug, Eq, PartialEq)]
45pub(crate) enum TaskStatus {
46 Invalid,
47 Ready,
48 Running,
49 Blocked,
50 Finished,
51 Idle,
52}
53
54#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy)]
56pub struct TaskId(i32);
57
58impl TaskId {
59 pub const fn into(self) -> i32 {
60 self.0
61 }
62
63 pub const fn from(x: i32) -> Self {
64 TaskId(x)
65 }
66}
67
68impl fmt::Display for TaskId {
69 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70 write!(f, "{}", self.0)
71 }
72}
73
74#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy)]
76pub struct Priority(u8);
77
78impl Priority {
79 pub const fn into(self) -> u8 {
80 self.0
81 }
82
83 pub const fn from(x: u8) -> Self {
84 Priority(x)
85 }
86}
87
88impl fmt::Display for Priority {
89 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
90 write!(f, "{}", self.0)
91 }
92}
93
94#[allow(dead_code)]
95pub const HIGH_PRIO: Priority = Priority::from(3);
96pub const NORMAL_PRIO: Priority = Priority::from(2);
97#[allow(dead_code)]
98pub const LOW_PRIO: Priority = Priority::from(1);
99pub const IDLE_PRIO: Priority = Priority::from(0);
100
101pub const NO_PRIORITIES: usize = 31;
103
104#[derive(Copy, Clone, Debug)]
105pub(crate) struct TaskHandle {
106 id: TaskId,
107 priority: Priority,
108 #[cfg(feature = "smp")]
109 core_id: CoreId,
110}
111
112impl TaskHandle {
113 pub fn new(id: TaskId, priority: Priority, #[cfg(feature = "smp")] core_id: CoreId) -> Self {
114 Self {
115 id,
116 priority,
117 #[cfg(feature = "smp")]
118 core_id,
119 }
120 }
121
122 #[cfg(feature = "smp")]
123 pub fn get_core_id(&self) -> CoreId {
124 self.core_id
125 }
126
127 pub fn get_id(&self) -> TaskId {
128 self.id
129 }
130
131 pub fn get_priority(&self) -> Priority {
132 self.priority
133 }
134}
135
136impl Ord for TaskHandle {
137 fn cmp(&self, other: &Self) -> cmp::Ordering {
138 self.id.cmp(&other.id)
139 }
140}
141
142impl PartialOrd for TaskHandle {
143 fn partial_cmp(&self, other: &Self) -> Option<cmp::Ordering> {
144 Some(self.cmp(other))
145 }
146}
147
148impl PartialEq for TaskHandle {
149 fn eq(&self, other: &Self) -> bool {
150 self.id == other.id
151 }
152}
153
154impl Eq for TaskHandle {}
155
156#[derive(Default)]
158pub(crate) struct TaskHandlePriorityQueue {
159 queues: [Option<VecDeque<TaskHandle>>; NO_PRIORITIES],
160 prio_bitmap: CachePadded<u64>,
161}
162
163impl TaskHandlePriorityQueue {
164 pub const fn new() -> Self {
166 Self {
167 queues: [const { None }; NO_PRIORITIES],
168 prio_bitmap: CachePadded::new(0),
169 }
170 }
171
172 pub fn is_empty(&self) -> bool {
174 self.prio_bitmap.into_inner() == 0
175 }
176
177 pub fn contains(&self, task: TaskHandle) -> bool {
180 matches!(self.queues[task.priority.into() as usize]
181 .as_ref(), Some(queue) if queue.iter().any(|queued| queued.id == task.id))
182 }
183
184 pub fn push(&mut self, task: TaskHandle) {
186 let i = task.priority.into() as usize;
187 *self.prio_bitmap |= (1 << i) as u64;
190 if let Some(queue) = &mut self.queues[i] {
191 queue.push_back(task);
192 } else {
193 let mut queue = VecDeque::new();
194 queue.push_back(task);
195 self.queues[i] = Some(queue);
196 }
197 }
198
199 fn pop_from_queue(&mut self, queue_index: usize) -> Option<TaskHandle> {
200 if let Some(queue) = &mut self.queues[queue_index] {
201 let task = queue.pop_front();
202
203 if queue.is_empty() {
204 *self.prio_bitmap &= !(1 << queue_index as u64);
205 }
206
207 task
208 } else {
209 None
210 }
211 }
212
213 pub fn pop(&mut self) -> Option<TaskHandle> {
215 if let Some(i) = msb(self.prio_bitmap.into_inner()) {
216 return self.pop_from_queue(i as usize);
217 }
218
219 None
220 }
221
222 pub fn remove(&mut self, task: TaskHandle) -> bool {
225 let queue_index = task.priority.into() as usize;
226 let mut success = false;
229 if let Some(queue) = &mut self.queues[queue_index] {
230 let mut i = 0;
231 while i != queue.len() {
232 if queue[i].id == task.id {
233 queue.remove(i);
234 success = true;
235 } else {
236 i += 1;
237 }
238 }
239
240 if queue.is_empty() {
241 *self.prio_bitmap &= !(1 << queue_index as u64);
242 }
243 }
244
245 success
246 }
247}
248
249pub(crate) struct PriorityTaskQueue {
251 queues: [LinkedList<Rc<RefCell<Task>>>; NO_PRIORITIES],
252 prio_bitmap: u64,
253}
254
255impl PriorityTaskQueue {
256 pub const fn new() -> PriorityTaskQueue {
258 const EMPTY_LIST: LinkedList<Rc<RefCell<Task>>> = LinkedList::new();
259 PriorityTaskQueue {
260 queues: [EMPTY_LIST; NO_PRIORITIES],
261 prio_bitmap: 0,
262 }
263 }
264
265 pub fn push(&mut self, task: Rc<RefCell<Task>>) {
267 let i = task.borrow().prio.into() as usize;
268 self.prio_bitmap |= (1 << i) as u64;
271 let queue = &mut self.queues[i];
272 queue.push_back(task);
273 }
274
275 fn pop_from_queue(&mut self, queue_index: usize) -> Option<Rc<RefCell<Task>>> {
276 let task = self.queues[queue_index].pop_front();
277 if self.queues[queue_index].is_empty() {
278 self.prio_bitmap &= !(1 << queue_index as u64);
279 }
280
281 task
282 }
283
284 fn remove_from_queue(
287 &mut self,
288 task_index: usize,
289 queue_index: usize,
290 ) -> Option<Rc<RefCell<Task>>> {
291 let queue = &mut self.queues[queue_index];
294 if task_index <= queue.len() {
295 let mut split_list = queue.split_off(task_index);
297 let element = split_list.pop_front();
298 queue.append(&mut split_list);
299 if queue.is_empty() {
300 self.prio_bitmap &= !(1 << queue_index as u64);
301 }
302 element
303 } else {
304 None
305 }
306 }
307
308 pub fn is_empty(&self) -> bool {
310 self.prio_bitmap == 0
311 }
312
313 #[allow(dead_code)]
315 #[inline]
316 pub fn get_priority_bitmap(&self) -> &u64 {
317 &self.prio_bitmap
318 }
319
320 pub fn pop(&mut self) -> Option<Rc<RefCell<Task>>> {
322 if let Some(i) = msb(self.prio_bitmap) {
323 return self.pop_from_queue(i as usize);
324 }
325
326 None
327 }
328
329 pub fn pop_with_prio(&mut self, prio: Priority) -> Option<Rc<RefCell<Task>>> {
331 if let Some(i) = msb(self.prio_bitmap)
332 && i >= u32::from(prio.into())
333 {
334 return self.pop_from_queue(i as usize);
335 }
336
337 None
338 }
339
340 #[cfg(all(any(target_arch = "x86_64", target_arch = "riscv64"), feature = "smp"))]
342 pub fn get_highest_priority(&self) -> Priority {
343 if let Some(i) = msb(self.prio_bitmap) {
344 Priority::from(i.try_into().unwrap())
345 } else {
346 IDLE_PRIO
347 }
348 }
349
350 pub fn set_priority(&mut self, handle: TaskHandle, prio: Priority) -> Result<(), ()> {
352 let old_priority = handle.get_priority().into() as usize;
353 if let Some(index) = self.queues[old_priority]
354 .iter()
355 .position(|current_task| current_task.borrow().id == handle.id)
356 {
357 let Some(task) = self.remove_from_queue(index, old_priority) else {
358 return Err(());
359 };
360 task.borrow_mut().prio = prio;
361 self.push(task);
362 return Ok(());
363 }
364
365 Err(())
366 }
367}
368
369#[cfg_attr(any(target_arch = "x86_64", target_arch = "aarch64"), repr(align(128)))]
371#[cfg_attr(
372 not(any(target_arch = "x86_64", target_arch = "aarch64")),
373 repr(align(64))
374)]
375pub(crate) struct Task {
376 pub id: TaskId,
378 pub status: TaskStatus,
380 pub prio: Priority,
382 pub last_stack_pointer: VirtAddr,
384 pub user_stack_pointer: VirtAddr,
386 pub last_fpu_state: arch::processor::FPUState,
388 pub core_id: CoreId,
390 pub stacks: TaskStacks,
392 pub object_map: Arc<RwSpinLock<HashMap<FileDescriptor, Arc<dyn ObjectInterface>, RandomState>>>,
394 #[cfg(not(feature = "common-os"))]
396 pub tls: Option<Box<TaskTLS>>,
397 #[cfg(all(target_arch = "x86_64", feature = "common-os"))]
399 pub root_page_table: usize,
400}
401
402pub(crate) trait TaskFrame {
403 fn create_stack_frame(&mut self, func: unsafe extern "C" fn(usize), arg: usize);
405}
406
407impl Task {
408 pub fn new(
409 tid: TaskId,
410 core_id: CoreId,
411 task_status: TaskStatus,
412 task_prio: Priority,
413 stacks: TaskStacks,
414 object_map: Arc<RwSpinLock<HashMap<FileDescriptor, Arc<dyn ObjectInterface>, RandomState>>>,
415 ) -> Task {
416 debug!("Creating new task {tid} on core {core_id}");
417
418 Task {
419 id: tid,
420 status: task_status,
421 prio: task_prio,
422 last_stack_pointer: VirtAddr::zero(),
423 user_stack_pointer: VirtAddr::zero(),
424 last_fpu_state: arch::processor::FPUState::new(),
425 core_id,
426 stacks,
427 object_map,
428 #[cfg(not(feature = "common-os"))]
429 tls: None,
430 #[cfg(all(target_arch = "x86_64", feature = "common-os"))]
431 root_page_table: arch::create_new_root_page_table(),
432 }
433 }
434
435 pub fn new_idle(tid: TaskId, core_id: CoreId) -> Task {
436 debug!("Creating idle task {tid}");
437
438 static OBJECT_MAP: OnceCell<
440 Arc<RwSpinLock<HashMap<FileDescriptor, Arc<dyn ObjectInterface>, RandomState>>>,
441 > = OnceCell::new();
442
443 if core_id == 0 {
444 OBJECT_MAP
445 .set(Arc::new(RwSpinLock::new(HashMap::<
446 FileDescriptor,
447 Arc<dyn ObjectInterface>,
448 RandomState,
449 >::with_hasher(
450 RandomState::with_seeds(0, 0, 0, 0),
451 ))))
452 .unwrap();
453 let objmap = OBJECT_MAP.get().unwrap().clone();
454 let _ = poll_on(async {
455 let mut guard = objmap.write();
456 if env::is_uhyve() {
457 guard
458 .try_insert(STDIN_FILENO, Arc::new(UhyveStdin::new()))
459 .map_err(|_| Errno::Io)?;
460 guard
461 .try_insert(STDOUT_FILENO, Arc::new(UhyveStdout::new()))
462 .map_err(|_| Errno::Io)?;
463 guard
464 .try_insert(STDERR_FILENO, Arc::new(UhyveStderr::new()))
465 .map_err(|_| Errno::Io)?;
466 } else {
467 guard
468 .try_insert(STDIN_FILENO, Arc::new(GenericStdin::new()))
469 .map_err(|_| Errno::Io)?;
470 guard
471 .try_insert(STDOUT_FILENO, Arc::new(GenericStdout::new()))
472 .map_err(|_| Errno::Io)?;
473 guard
474 .try_insert(STDERR_FILENO, Arc::new(GenericStderr::new()))
475 .map_err(|_| Errno::Io)?;
476 }
477
478 Ok(())
479 });
480 }
481
482 Task {
483 id: tid,
484 status: TaskStatus::Idle,
485 prio: IDLE_PRIO,
486 last_stack_pointer: VirtAddr::zero(),
487 user_stack_pointer: VirtAddr::zero(),
488 last_fpu_state: arch::processor::FPUState::new(),
489 core_id,
490 stacks: TaskStacks::from_boot_stacks(),
491 object_map: OBJECT_MAP.get().unwrap().clone(),
492 #[cfg(not(feature = "common-os"))]
493 tls: None,
494 #[cfg(all(target_arch = "x86_64", feature = "common-os"))]
495 root_page_table: *crate::scheduler::BOOT_ROOT_PAGE_TABLE.get().unwrap(),
496 }
497 }
498}
499
500struct BlockedTask {
507 task: Rc<RefCell<Task>>,
508 wakeup_time: Option<u64>,
509}
510
511impl BlockedTask {
512 pub fn new(task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) -> Self {
513 Self { task, wakeup_time }
514 }
515}
516
517pub(crate) struct BlockedTaskQueue {
518 list: LinkedList<BlockedTask>,
519 #[cfg(any(feature = "tcp", feature = "udp"))]
520 network_wakeup_time: Option<u64>,
521}
522
523impl BlockedTaskQueue {
524 pub const fn new() -> Self {
525 Self {
526 list: LinkedList::new(),
527 #[cfg(any(feature = "tcp", feature = "udp"))]
528 network_wakeup_time: None,
529 }
530 }
531
532 fn mark_ready(task: &RefCell<Task>) {
533 let mut borrowed = task.borrow_mut();
534 debug!(
535 "Waking up task {} on core {}",
536 borrowed.id, borrowed.core_id
537 );
538
539 assert!(
540 borrowed.core_id == core_id(),
541 "Try to wake up task {} on the wrong core {} != {}",
542 borrowed.id,
543 borrowed.core_id,
544 core_id()
545 );
546
547 assert!(
548 borrowed.status == TaskStatus::Blocked,
549 "Trying to wake up task {} which is not blocked",
550 borrowed.id
551 );
552 borrowed.status = TaskStatus::Ready;
553 }
554
555 #[cfg(any(feature = "tcp", feature = "udp"))]
556 pub fn add_network_timer(&mut self, wakeup_time: Option<u64>) {
557 self.network_wakeup_time = wakeup_time;
558
559 let next = self.list.front().and_then(|t| t.wakeup_time);
560
561 let time = match (wakeup_time, next) {
562 (Some(a), Some(b)) => Some(a.min(b)),
563 (a, b) => a.or(b),
564 };
565
566 arch::set_oneshot_timer(time);
567 }
568
569 pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
571 {
572 let mut borrowed = task.borrow_mut();
574 debug!("Blocking task {}", borrowed.id);
575
576 assert_eq!(
577 borrowed.status,
578 TaskStatus::Running,
579 "Trying to block task {} which is not running",
580 borrowed.id
581 );
582 borrowed.status = TaskStatus::Blocked;
583 }
584
585 let new_node = BlockedTask::new(task, wakeup_time);
586
587 if let Some(wt) = wakeup_time {
589 let mut cursor = self.list.cursor_front_mut();
590 let set_oneshot_timer = || {
591 #[cfg(not(any(feature = "tcp", feature = "udp")))]
592 arch::set_oneshot_timer(wakeup_time);
593 #[cfg(any(feature = "tcp", feature = "udp"))]
594 match self.network_wakeup_time {
595 Some(time) => {
596 if time > wt {
597 arch::set_oneshot_timer(wakeup_time);
598 } else {
599 arch::set_oneshot_timer(self.network_wakeup_time);
600 }
601 }
602 _ => arch::set_oneshot_timer(wakeup_time),
603 }
604 };
605
606 while let Some(node) = cursor.current() {
607 let node_wakeup_time = node.wakeup_time;
608 if node_wakeup_time.is_none() || wt < node_wakeup_time.unwrap() {
609 cursor.insert_before(new_node);
610
611 set_oneshot_timer();
612 return;
613 }
614
615 cursor.move_next();
616 }
617
618 set_oneshot_timer();
619 }
620
621 self.list.push_back(new_node);
622 }
623
624 pub fn custom_wakeup(&mut self, task: TaskHandle) -> Rc<RefCell<Task>> {
626 let mut first_task = true;
627 let mut cursor = self.list.cursor_front_mut();
628
629 #[cfg(any(feature = "tcp", feature = "udp"))]
630 if let Some(wakeup_time) = self.network_wakeup_time
631 && wakeup_time <= arch::processor::get_timer_ticks()
632 {
633 self.network_wakeup_time = None;
634 }
635
636 while let Some(node) = cursor.current() {
638 if node.task.borrow().id == task.get_id() {
639 let task_ref = node.task.clone();
641 cursor.remove_current();
642
643 #[cfg(any(feature = "tcp", feature = "udp"))]
646 if first_task {
647 arch::set_oneshot_timer(cursor.current().map_or_else(
648 || self.network_wakeup_time,
649 |node| match node.wakeup_time {
650 Some(wt) => {
651 if let Some(timer) = self.network_wakeup_time {
652 if wt < timer { Some(wt) } else { Some(timer) }
653 } else {
654 Some(wt)
655 }
656 }
657 None => self.network_wakeup_time,
658 },
659 ));
660 }
661 #[cfg(not(any(feature = "tcp", feature = "udp")))]
662 if first_task {
663 arch::set_oneshot_timer(
664 cursor
665 .current()
666 .map_or_else(|| None, |node| node.wakeup_time),
667 );
668 }
669
670 Self::mark_ready(&task_ref);
672
673 return task_ref;
674 }
675
676 first_task = false;
677 cursor.move_next();
678 }
679
680 unreachable!();
681 }
682
683 pub fn handle_waiting_tasks(&mut self, ready_queue: &mut PriorityTaskQueue) {
688 let time = arch::processor::get_timer_ticks();
690
691 #[cfg(any(feature = "tcp", feature = "udp"))]
692 if let Some(mut guard) = crate::executor::network::NIC.try_lock()
693 && let crate::executor::network::NetworkState::Initialized(nic) = &mut *guard
694 {
695 let now = crate::executor::network::now();
696 nic.poll_common(now);
697 self.network_wakeup_time = nic.poll_delay(now).map(|d| d.total_micros() + time);
698 }
699
700 let newly_ready_tasks = self.list.extract_if(|blocked_task| {
704 blocked_task
705 .wakeup_time
706 .is_some_and(|wakeup_time| wakeup_time < time)
707 });
708
709 for task in newly_ready_tasks {
710 Self::mark_ready(&task.task);
711 ready_queue.push(task.task);
712 }
713
714 let new_task_wakeup_time = self.list.front().and_then(|task| task.wakeup_time);
715 cfg_if::cfg_if! {
716 if #[cfg(any(feature = "tcp", feature = "udp"))] {
717 let network_wakeup_time = self.network_wakeup_time;
718 } else {
719 let network_wakeup_time = None;
720 }
721 };
722 let timer_wakeup_time = match (new_task_wakeup_time, network_wakeup_time) {
723 (None, None) => None,
724 (None, Some(network_wt)) => Some(network_wt),
725 (Some(task_wt), None) => Some(task_wt),
726 (Some(task_wt), Some(network_wt)) => Some(u64::min(task_wt, network_wt)),
727 };
728
729 arch::set_oneshot_timer(timer_wakeup_time);
730 }
731}