task.rs 14.9 KB
Newer Older
1
2
3
// Copyright (c) 2017 Stefan Lankes, RWTH Aachen University
//               2018 Colin Finck, RWTH Aachen University
//
4
5
6
7
// Licensed under the Apache License, Version 2.0, <LICENSE-APACHE or
// http://apache.org/licenses/LICENSE-2.0> or the MIT license <LICENSE-MIT or
// http://opensource.org/licenses/MIT>, at your option. This file may not be
// copied, modified, or distributed except according to those terms.
8

9
use crate::arch;
10
use crate::arch::mm::VirtAddr;
11
12
13
use crate::arch::percore::*;
use crate::arch::scheduler::{TaskStacks, TaskTLS};
use crate::scheduler::CoreId;
14
use alloc::collections::{LinkedList, VecDeque};
15
16
use alloc::rc::Rc;
use core::cell::RefCell;
17
use core::cmp::Ordering;
18
use core::convert::TryInto;
19
use core::fmt;
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
use core::num::NonZeroU64;

/// Returns the most significant bit.
///
/// # Examples
///
/// ```
/// assert_eq!(msb(0), None);
/// assert_eq!(msb(1), 0);
/// assert_eq!(msb(u64::MAX), 63);
/// ```
#[inline]
fn msb(n: u64) -> Option<u32> {
	NonZeroU64::new(n).map(|n| u64::BITS - 1 - n.leading_zeros())
}
35
36
37
38

/// The status of the task - used for scheduling
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum TaskStatus {
39
40
41
42
43
44
	Invalid,
	Ready,
	Running,
	Blocked,
	Finished,
	Idle,
45
46
}

47
48
49
50
51
52
53
/// Reason why wakeup() has been called on a task.
#[derive(Clone, Copy, PartialEq)]
pub enum WakeupReason {
	Custom,
	Timer,
}

54
55
/// Unique identifier for a task (i.e. `pid`).
#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy)]
Colin Finck's avatar
Colin Finck committed
56
pub struct TaskId(u32);
57
58

impl TaskId {
Colin Finck's avatar
Colin Finck committed
59
	pub const fn into(self) -> u32 {
60
61
62
		self.0
	}

Colin Finck's avatar
Colin Finck committed
63
	pub const fn from(x: u32) -> Self {
64
65
66
67
68
		TaskId(x)
	}
}

impl fmt::Display for TaskId {
69
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
		write!(f, "{}", self.0)
	}
}

/// Priority of a task
#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy)]
pub struct Priority(u8);

impl Priority {
	pub const fn into(self) -> u8 {
		self.0
	}

	pub const fn from(x: u8) -> Self {
		Priority(x)
	}
}

impl fmt::Display for Priority {
89
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
90
91
92
93
		write!(f, "{}", self.0)
	}
}

Stefan Lankes's avatar
Stefan Lankes committed
94
#[allow(dead_code)]
95
96
pub const HIGH_PRIO: Priority = Priority::from(3);
pub const NORMAL_PRIO: Priority = Priority::from(2);
Stefan Lankes's avatar
Stefan Lankes committed
97
#[allow(dead_code)]
98
99
100
101
pub const LOW_PRIO: Priority = Priority::from(1);
pub const IDLE_PRIO: Priority = Priority::from(0);

/// Maximum number of priorities
102
pub const NO_PRIORITIES: usize = 31;
103

104
105
106
107
#[derive(Copy, Clone, Debug)]
pub struct TaskHandle {
	id: TaskId,
	priority: Priority,
108
	core_id: CoreId,
109
110
111
}

impl TaskHandle {
112
	pub fn new(id: TaskId, priority: Priority, core_id: CoreId) -> Self {
113
		Self {
114
115
116
			id,
			priority,
			core_id,
117
118
119
		}
	}

120
	pub fn get_core_id(&self) -> CoreId {
121
122
123
124
125
126
127
128
129
130
131
132
		self.core_id
	}

	pub fn get_id(&self) -> TaskId {
		self.id
	}

	pub fn get_priority(&self) -> Priority {
		self.priority
	}
}

133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
impl Ord for TaskHandle {
	fn cmp(&self, other: &Self) -> Ordering {
		self.id.cmp(&other.id)
	}
}

impl PartialOrd for TaskHandle {
	fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
		Some(self.cmp(other))
	}
}

impl PartialEq for TaskHandle {
	fn eq(&self, other: &Self) -> bool {
		self.id == other.id
	}
}

impl Eq for TaskHandle {}

153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/// Realize a priority queue for task handles
pub struct TaskHandlePriorityQueue {
	queues: [Option<VecDeque<TaskHandle>>; NO_PRIORITIES],
	prio_bitmap: u64,
}

impl TaskHandlePriorityQueue {
	/// Creates an empty priority queue for tasks
	pub const fn new() -> Self {
		Self {
			queues: [
				None, None, None, None, None, None, None, None, None, None, None, None, None, None,
				None, None, None, None, None, None, None, None, None, None, None, None, None, None,
				None, None, None,
			],
			prio_bitmap: 0,
		}
	}

	/// Add a task handle by its priority to the queue
	pub fn push(&mut self, task: TaskHandle) {
		let i = task.priority.into() as usize;
		//assert!(i < NO_PRIORITIES, "Priority {} is too high", i);

177
		self.prio_bitmap |= (1 << i) as u64;
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
		if let Some(queue) = &mut self.queues[i] {
			queue.push_back(task);
		} else {
			let mut queue = VecDeque::new();
			queue.push_back(task);
			self.queues[i] = Some(queue);
		}
	}

	fn pop_from_queue(&mut self, queue_index: usize) -> Option<TaskHandle> {
		if let Some(queue) = &mut self.queues[queue_index] {
			let task = queue.pop_front();

			if queue.is_empty() {
				self.prio_bitmap &= !(1 << queue_index as u64);
			}

			task
		} else {
			None
		}
	}

	/// Pop the task handle with the highest priority from the queue
	pub fn pop(&mut self) -> Option<TaskHandle> {
		if let Some(i) = msb(self.prio_bitmap) {
			return self.pop_from_queue(i as usize);
		}

		None
	}

	/// Remove a specific task handle from the priority queue.
	pub fn remove(&mut self, task: TaskHandle) {
		let queue_index = task.priority.into() as usize;
		//assert!(queue_index < NO_PRIORITIES, "Priority {} is too high", queue_index);

		if let Some(queue) = &mut self.queues[queue_index] {
			let mut i = 0;
			while i != queue.len() {
				if queue[i].id == task.id {
					queue.remove(i);
				} else {
					i += 1;
				}
			}

			if queue.is_empty() {
				self.prio_bitmap &= !(1 << queue_index as u64);
			}
		}
	}
}

232
233
234
235
236
237
238
struct QueueHead {
	head: Option<Rc<RefCell<Task>>>,
	tail: Option<Rc<RefCell<Task>>>,
}

impl QueueHead {
	pub const fn new() -> Self {
239
		Self {
240
			head: None,
241
			tail: None,
242
243
244
245
246
247
		}
	}
}

impl Default for QueueHead {
	fn default() -> Self {
248
249
250
251
		Self {
			head: None,
			tail: None,
		}
252
253
254
	}
}

255
256
/// Realize a priority queue for tasks
pub struct PriorityTaskQueue {
257
	queues: [QueueHead; NO_PRIORITIES],
258
	prio_bitmap: u64,
259
260
261
262
}

impl PriorityTaskQueue {
	/// Creates an empty priority queue for tasks
263
	pub const fn new() -> PriorityTaskQueue {
264
		const QUEUE_HEAD: QueueHead = QueueHead::new();
265
		PriorityTaskQueue {
266
			queues: [QUEUE_HEAD; NO_PRIORITIES],
267
			prio_bitmap: 0,
268
269
270
		}
	}

271
	/// Add a task by its priority to the queue
272
273
	pub fn push(&mut self, task: Rc<RefCell<Task>>) {
		let i = task.borrow().prio.into() as usize;
274
		//assert!(i < NO_PRIORITIES, "Priority {} is too high", i);
275

276
		self.prio_bitmap |= (1 << i) as u64;
277
278
279
280
281
282
		match self.queues[i].tail {
			None => {
				// first element in the queue
				self.queues[i].head = Some(task.clone());

				let mut borrow = task.borrow_mut();
283
				borrow.next = None;
284
				borrow.prev = None;
285
			}
286
287
288
289
290
291
292
293
294
295
			Some(ref mut tail) => {
				// add task at the end of the node
				tail.borrow_mut().next = Some(task.clone());

				let mut borrow = task.borrow_mut();
				borrow.next = None;
				borrow.prev = Some(tail.clone());
			}
		}

296
		self.queues[i].tail = Some(task);
297
298
	}

299
	fn pop_from_queue(&mut self, queue_index: usize) -> Option<Rc<RefCell<Task>>> {
300
301
302
		let (new_head, task) = {
			let head = self.queues[queue_index].head.as_mut()?;
			let mut borrow = head.borrow_mut();
303

304
305
			if let Some(ref mut nhead) = borrow.next {
				nhead.borrow_mut().prev = None;
306
			}
307

308
309
310
			let new_head = borrow.next.clone();
			borrow.next = None;
			borrow.prev = None;
311

312
			let task = head.clone();
313

314
315
			(new_head, task)
		};
316

317
318
319
320
321
322
323
		self.queues[queue_index].head = new_head;
		if self.queues[queue_index].head.is_none() {
			self.queues[queue_index].tail = None;
			self.prio_bitmap &= !(1 << queue_index as u64);
		}

		Some(task)
324
325
326
327
	}

	/// Pop the task with the highest priority from the queue
	pub fn pop(&mut self) -> Option<Rc<RefCell<Task>>> {
328
329
330
331
332
		if let Some(i) = msb(self.prio_bitmap) {
			return self.pop_from_queue(i as usize);
		}

		None
333
334
335
336
	}

	/// Pop the next task, which has a higher or the same priority as `prio`
	pub fn pop_with_prio(&mut self, prio: Priority) -> Option<Rc<RefCell<Task>>> {
337
		if let Some(i) = msb(self.prio_bitmap) {
338
			if i >= prio.into().try_into().unwrap() {
339
340
				return self.pop_from_queue(i as usize);
			}
341
		}
342
343

		None
344
	}
345
346
347
348
349
350
351
352
353

	/// Returns the highest priority of all available task
	pub fn get_highest_priority(&self) -> Priority {
		if let Some(i) = msb(self.prio_bitmap) {
			Priority::from(i.try_into().unwrap())
		} else {
			IDLE_PRIO
		}
	}
354
355
356
}

/// A task control block, which identifies either a process or a thread
357
358
359
360
361
#[cfg_attr(any(target_arch = "x86_64", target_arch = "aarch64"), repr(align(128)))]
#[cfg_attr(
	not(any(target_arch = "x86_64", target_arch = "aarch64")),
	repr(align(64))
)]
362
363
364
365
366
367
368
369
pub struct Task {
	/// The ID of this context
	pub id: TaskId,
	/// Status of a task, e.g. if the task is ready or blocked
	pub status: TaskStatus,
	/// Task priority,
	pub prio: Priority,
	/// Last stack pointer before a context switch to another task
370
	pub last_stack_pointer: VirtAddr,
371
	/// Last stack pointer on the user stack before jumping to kernel space
372
	pub user_stack_pointer: VirtAddr,
373
374
	/// Last FPU state before a context switch to another task using the FPU
	pub last_fpu_state: arch::processor::FPUState,
375
	/// ID of the core this task is running on
376
	pub core_id: CoreId,
377
	/// Stack of the task
378
	pub stacks: TaskStacks,
379
	/// next task in queue
380
	pub next: Option<Rc<RefCell<Task>>>,
381
	/// previous task in queue
382
	pub prev: Option<Rc<RefCell<Task>>>,
383
	/// Task Thread-Local-Storage (TLS)
384
	pub tls: Option<TaskTLS>,
385
386
	/// Reason why wakeup() has been called the last time
	pub last_wakeup_reason: WakeupReason,
387
388
389
	/// lwIP error code for this task
	#[cfg(feature = "newlib")]
	pub lwip_errno: i32,
390
391
392
393
394
395
396
397
}

pub trait TaskFrame {
	/// Create the initial stack frame for a new task
	fn create_stack_frame(&mut self, func: extern "C" fn(usize), arg: usize);
}

impl Task {
398
399
400
401
402
403
404
	pub fn new(
		tid: TaskId,
		core_id: CoreId,
		task_status: TaskStatus,
		task_prio: Priority,
		stack_size: usize,
	) -> Task {
405
		debug!("Creating new task {} on core {}", tid, core_id);
406
407
408
409
410

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
411
412
			last_stack_pointer: VirtAddr(0u64),
			user_stack_pointer: VirtAddr(0u64),
413
			last_fpu_state: arch::processor::FPUState::new(),
414
			core_id,
415
			stacks: TaskStacks::new(stack_size),
416
417
			next: None,
			prev: None,
418
			tls: None,
419
			last_wakeup_reason: WakeupReason::Custom,
420
421
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
422
423
424
		}
	}

425
	pub fn new_idle(tid: TaskId, core_id: CoreId) -> Task {
426
		debug!("Creating idle task {}", tid);
427

428
429
		Task {
			id: tid,
430
			status: TaskStatus::Idle,
431
			prio: IDLE_PRIO,
432
433
			last_stack_pointer: VirtAddr(0u64),
			user_stack_pointer: VirtAddr(0u64),
434
			last_fpu_state: arch::processor::FPUState::new(),
435
			core_id,
436
			stacks: TaskStacks::from_boot_stacks(),
437
438
			next: None,
			prev: None,
439
			tls: None,
440
			last_wakeup_reason: WakeupReason::Custom,
441
442
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
443
444
		}
	}
445

446
	pub fn clone(tid: TaskId, core_id: CoreId, task: &Task) -> Task {
447
		debug!("Cloning task {} from task {}", tid, task.id);
448
449
450

		Task {
			id: tid,
451
			status: TaskStatus::Ready,
452
			prio: task.prio,
453
454
			last_stack_pointer: VirtAddr(0u64),
			user_stack_pointer: VirtAddr(0u64),
455
			last_fpu_state: arch::processor::FPUState::new(),
456
			core_id,
457
			stacks: task.stacks.clone(),
458
459
			next: None,
			prev: None,
460
			tls: task.tls.clone(),
461
			last_wakeup_reason: task.last_wakeup_reason,
462
463
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
464
465
		}
	}
466
467
}

468
/*impl Drop for Task {
469
470
471
	fn drop(&mut self) {
		debug!("Drop task {}", self.id);
	}
472
}*/
473

474
475
struct BlockedTask {
	task: Rc<RefCell<Task>>,
476
	wakeup_time: Option<u64>,
477
478
}

479
480
481
482
483
484
impl BlockedTask {
	pub fn new(task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) -> Self {
		Self { task, wakeup_time }
	}
}

485
pub struct BlockedTaskQueue {
486
	list: LinkedList<BlockedTask>,
487
488
489
490
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
491
		Self {
492
			list: LinkedList::new(),
493
		}
494
495
496
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
497
		{
498
			let mut borrowed = task.borrow_mut();
499
500
501
502
503
			debug!(
				"Waking up task {} on core {}",
				borrowed.id, borrowed.core_id
			);

504
505
506
507
508
509
510
511
			assert!(
				borrowed.core_id == core_id(),
				"Try to wake up task {} on the wrong core {} != {}",
				borrowed.id,
				borrowed.core_id,
				core_id()
			);

512
			assert!(
513
				borrowed.status == TaskStatus::Blocked,
514
515
516
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
517
			borrowed.status = TaskStatus::Ready;
518
			borrowed.last_wakeup_reason = reason;
519
		}
520

521
		// Add the task to the ready queue.
522
		core_scheduler().ready_queue.push(task);
523
524
	}

525
	/// Blocks the given task for `wakeup_time` ticks, or indefinitely if None is given.
526
	pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
527
528
529
		{
			// Set the task status to Blocked.
			let mut borrowed = task.borrow_mut();
530
			debug!("Blocking task {}", borrowed.id);
531

532
533
			assert_eq!(
				borrowed.status,
534
				TaskStatus::Running,
535
536
537
				"Trying to block task {} which is not running",
				borrowed.id
			);
538
			borrowed.status = TaskStatus::Blocked;
539
		}
540

Stefan Lankes's avatar
Stefan Lankes committed
541
		let new_node = BlockedTask::new(task, wakeup_time);
542

543
544
		// Shall the task automatically be woken up after a certain time?
		if let Some(wt) = wakeup_time {
Martin Kröning's avatar
Martin Kröning committed
545
			let first_task = true;
546
			let mut cursor = self.list.cursor_front_mut();
547
548
549
550
551
552
553
			let mut _guard = scopeguard::guard(first_task, |first_task| {
				// If the task is the new first task in the list, update the one-shot timer
				// to fire when this task shall be woken up.
				if first_task {
					arch::set_oneshot_timer(wakeup_time);
				}
			});
554

555
556
			while let Some(node) = cursor.current() {
				let node_wakeup_time = node.wakeup_time;
557
				if node_wakeup_time.is_none() || wt < node_wakeup_time.unwrap() {
558
					cursor.insert_before(new_node);
559

560
561
562
					return;
				}

563
				cursor.move_next();
564
565
			}
		}
566
567

		self.list.push_back(new_node);
568
569
570
	}

	/// Manually wake up a blocked task.
571
	pub fn custom_wakeup(&mut self, task: TaskHandle) {
572
		let mut first_task = true;
573
		let mut cursor = self.list.cursor_front_mut();
574
575

		// Loop through all blocked tasks to find it.
576
577
		while let Some(node) = cursor.current() {
			if node.task.borrow().id == task.get_id() {
578
				// Remove it from the list of blocked tasks and wake it up.
579
580
				Self::wakeup_task(node.task.clone(), WakeupReason::Custom);
				cursor.remove_current();
581
582
583
584

				// If this is the first task, adjust the One-Shot Timer to fire at the
				// next task's wakeup time (if any).
				if first_task {
585
586
					if let Some(next_node) = cursor.current() {
						arch::set_oneshot_timer(next_node.wakeup_time);
587
588
589
					} else {
						// if no task is available, we have to disable the timer
						arch::set_oneshot_timer(None);
590
591
592
593
594
595
596
					}
				}

				break;
			}

			first_task = false;
597
			cursor.move_next();
598
599
600
601
602
603
604
605
606
		}
	}

	/// Wakes up all tasks whose wakeup time has elapsed.
	///
	/// Should be called by the One-Shot Timer interrupt handler when the wakeup time for
	/// at least one task has elapsed.
	pub fn handle_waiting_tasks(&mut self) {
		// Get the current time.
607
		let time = arch::processor::get_timer_ticks();
608
		let mut cursor = self.list.cursor_front_mut();
609
610

		// Loop through all blocked tasks.
611
		while let Some(node) = cursor.current() {
612
613
			// Get the wakeup time of this task and check if we have reached the first task
			// that hasn't elapsed yet or waits indefinitely.
614
			let node_wakeup_time = node.wakeup_time;
615
616
617
618
619
620
621
622
			if node_wakeup_time.is_none() || time < node_wakeup_time.unwrap() {
				// Adjust the One-Shot Timer to fire at this task's wakeup time (if any)
				// and exit the loop.
				arch::set_oneshot_timer(node_wakeup_time);
				break;
			}

			// Otherwise, this task has elapsed, so remove it from the list and wake it up.
623
624
			Self::wakeup_task(node.task.clone(), WakeupReason::Timer);
			cursor.remove_current();
625
626
		}
	}
627
}