hermit/scheduler/
task.rs

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/// Returns the most significant bit.
30///
31/// # Examples
32///
33/// ```
34/// assert_eq!(msb(0), None);
35/// assert_eq!(msb(1), 0);
36/// assert_eq!(msb(u64::MAX), 63);
37/// ```
38#[inline]
39fn msb(n: u64) -> Option<u32> {
40	NonZeroU64::new(n).map(|n| u64::BITS - 1 - n.leading_zeros())
41}
42
43/// The status of the task - used for scheduling
44#[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/// Unique identifier for a task (i.e. `pid`).
55#[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/// Priority of a task
75#[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
101/// Maximum number of priorities
102pub 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/// Realize a priority queue for task handles
157#[derive(Default)]
158pub(crate) struct TaskHandlePriorityQueue {
159	queues: [Option<VecDeque<TaskHandle>>; NO_PRIORITIES],
160	prio_bitmap: CachePadded<u64>,
161}
162
163impl TaskHandlePriorityQueue {
164	/// Creates an empty priority queue for tasks
165	pub const fn new() -> Self {
166		Self {
167			queues: [const { None }; NO_PRIORITIES],
168			prio_bitmap: CachePadded::new(0),
169		}
170	}
171
172	/// Checks if the queue is empty.
173	pub fn is_empty(&self) -> bool {
174		self.prio_bitmap.into_inner() == 0
175	}
176
177	/// Checks if the given task is in the queue. Returns `true` if the task
178	/// was found.
179	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	/// Add a task handle by its priority to the queue
185	pub fn push(&mut self, task: TaskHandle) {
186		let i = task.priority.into() as usize;
187		//assert!(i < NO_PRIORITIES, "Priority {} is too high", i);
188
189		*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	/// Pop the task handle with the highest priority from the queue
214	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	/// Remove a specific task handle from the priority queue. Returns `true` if
223	/// the handle was in the queue.
224	pub fn remove(&mut self, task: TaskHandle) -> bool {
225		let queue_index = task.priority.into() as usize;
226		//assert!(queue_index < NO_PRIORITIES, "Priority {} is too high", queue_index);
227
228		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
249/// Realize a priority queue for tasks
250pub(crate) struct PriorityTaskQueue {
251	queues: [LinkedList<Rc<RefCell<Task>>>; NO_PRIORITIES],
252	prio_bitmap: u64,
253}
254
255impl PriorityTaskQueue {
256	/// Creates an empty priority queue for tasks
257	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	/// Add a task by its priority to the queue
266	pub fn push(&mut self, task: Rc<RefCell<Task>>) {
267		let i = task.borrow().prio.into() as usize;
268		//assert!(i < NO_PRIORITIES, "Priority {} is too high", i);
269
270		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	/// Remove the task at index from the queue and return that task,
285	/// or None if the index is out of range or the list is empty.
286	fn remove_from_queue(
287		&mut self,
288		task_index: usize,
289		queue_index: usize,
290	) -> Option<Rc<RefCell<Task>>> {
291		//assert!(prio < NO_PRIORITIES, "Priority {} is too high", prio);
292
293		let queue = &mut self.queues[queue_index];
294		if task_index <= queue.len() {
295			// Calling remove is unstable: https://github.com/rust-lang/rust/issues/69210
296			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	/// Returns true if the queue is empty.
309	pub fn is_empty(&self) -> bool {
310		self.prio_bitmap == 0
311	}
312
313	/// Returns reference to prio_bitmap
314	#[allow(dead_code)]
315	#[inline]
316	pub fn get_priority_bitmap(&self) -> &u64 {
317		&self.prio_bitmap
318	}
319
320	/// Pop the task with the highest priority from the queue
321	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	/// Pop the next task, which has a higher or the same priority as `prio`
330	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	/// Returns the highest priority of all available task
341	#[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	/// Change priority of specific task
351	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/// A task control block, which identifies either a process or a thread
370#[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	/// The ID of this context
377	pub id: TaskId,
378	/// Status of a task, e.g. if the task is ready or blocked
379	pub status: TaskStatus,
380	/// Task priority,
381	pub prio: Priority,
382	/// Last stack pointer before a context switch to another task
383	pub last_stack_pointer: VirtAddr,
384	/// Last stack pointer on the user stack before jumping to kernel space
385	pub user_stack_pointer: VirtAddr,
386	/// Last FPU state before a context switch to another task using the FPU
387	pub last_fpu_state: arch::processor::FPUState,
388	/// ID of the core this task is running on
389	pub core_id: CoreId,
390	/// Stack of the task
391	pub stacks: TaskStacks,
392	/// Mapping between file descriptor and the referenced IO interface
393	pub object_map: Arc<RwSpinLock<HashMap<FileDescriptor, Arc<dyn ObjectInterface>, RandomState>>>,
394	/// Task Thread-Local-Storage (TLS)
395	#[cfg(not(feature = "common-os"))]
396	pub tls: Option<Box<TaskTLS>>,
397	// Physical address of the 1st level page table
398	#[cfg(all(target_arch = "x86_64", feature = "common-os"))]
399	pub root_page_table: usize,
400}
401
402pub(crate) trait TaskFrame {
403	/// Create the initial stack frame for a new task
404	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		/// All cores use the same mapping between file descriptor and the referenced object
439		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
500/*impl Drop for Task {
501	fn drop(&mut self) {
502		debug!("Drop task {}", self.id);
503	}
504}*/
505
506struct 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	/// Blocks the given task for `wakeup_time` ticks, or indefinitely if None is given.
570	pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
571		{
572			// Set the task status to Blocked.
573			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		// Shall the task automatically be woken up after a certain time?
588		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	/// Manually wake up a blocked task.
625	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		// Loop through all blocked tasks to find it.
637		while let Some(node) = cursor.current() {
638			if node.task.borrow().id == task.get_id() {
639				// Remove it from the list of blocked tasks.
640				let task_ref = node.task.clone();
641				cursor.remove_current();
642
643				// If this is the first task, adjust the One-Shot Timer to fire at the
644				// next task's wakeup time (if any).
645				#[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				// Wake it up.
671				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	/// Wakes up all tasks whose wakeup time has elapsed.
684	///
685	/// Should be called by the One-Shot Timer interrupt handler when the wakeup time for
686	/// at least one task has elapsed.
687	pub fn handle_waiting_tasks(&mut self, ready_queue: &mut PriorityTaskQueue) {
688		// Get the current time.
689		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		// Get the wakeup time of this task and check if we have reached the first task
701		// that hasn't elapsed yet or waits indefinitely.
702		// This iterator has to be consumed to actually remove the elements.
703		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}