task.rs 14.6 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::convert::TryInto;
18
use core::fmt;
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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())
}
34
35
36
37

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

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

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

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

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

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

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

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

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

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

119
	pub fn get_core_id(&self) -> CoreId {
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
		self.core_id
	}

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

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

/// 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);

156
		self.prio_bitmap |= (1 << i) as u64;
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
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
		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);
			}
		}
	}
}

211
212
213
214
215
216
217
struct QueueHead {
	head: Option<Rc<RefCell<Task>>>,
	tail: Option<Rc<RefCell<Task>>>,
}

impl QueueHead {
	pub const fn new() -> Self {
218
		Self {
219
			head: None,
220
			tail: None,
221
222
223
224
225
226
		}
	}
}

impl Default for QueueHead {
	fn default() -> Self {
227
228
229
230
		Self {
			head: None,
			tail: None,
		}
231
232
233
	}
}

234
235
/// Realize a priority queue for tasks
pub struct PriorityTaskQueue {
236
	queues: [QueueHead; NO_PRIORITIES],
237
	prio_bitmap: u64,
238
239
240
241
}

impl PriorityTaskQueue {
	/// Creates an empty priority queue for tasks
242
	pub const fn new() -> PriorityTaskQueue {
243
		const QUEUE_HEAD: QueueHead = QueueHead::new();
244
		PriorityTaskQueue {
245
			queues: [QUEUE_HEAD; NO_PRIORITIES],
246
			prio_bitmap: 0,
247
248
249
		}
	}

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

255
		self.prio_bitmap |= (1 << i) as u64;
256
257
258
259
260
261
		match self.queues[i].tail {
			None => {
				// first element in the queue
				self.queues[i].head = Some(task.clone());

				let mut borrow = task.borrow_mut();
262
				borrow.next = None;
263
				borrow.prev = None;
264
			}
265
266
267
268
269
270
271
272
273
274
			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());
			}
		}

275
		self.queues[i].tail = Some(task);
276
277
	}

278
	fn pop_from_queue(&mut self, queue_index: usize) -> Option<Rc<RefCell<Task>>> {
279
280
281
		let (new_head, task) = {
			let head = self.queues[queue_index].head.as_mut()?;
			let mut borrow = head.borrow_mut();
282

283
284
			if let Some(ref mut nhead) = borrow.next {
				nhead.borrow_mut().prev = None;
285
			}
286

287
288
289
			let new_head = borrow.next.clone();
			borrow.next = None;
			borrow.prev = None;
290

291
			let task = head.clone();
292

293
294
			(new_head, task)
		};
295

296
297
298
299
300
301
302
		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)
303
304
305
306
	}

	/// Pop the task with the highest priority from the queue
	pub fn pop(&mut self) -> Option<Rc<RefCell<Task>>> {
307
308
309
310
311
		if let Some(i) = msb(self.prio_bitmap) {
			return self.pop_from_queue(i as usize);
		}

		None
312
313
314
315
	}

	/// 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>>> {
316
		if let Some(i) = msb(self.prio_bitmap) {
317
			if i >= prio.into().try_into().unwrap() {
318
319
				return self.pop_from_queue(i as usize);
			}
320
		}
321
322

		None
323
	}
324
325
326
327
328
329
330
331
332

	/// 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
		}
	}
333
334
335
}

/// A task control block, which identifies either a process or a thread
336
337
338
339
340
#[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))
)]
341
342
343
344
345
346
347
348
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
349
	pub last_stack_pointer: VirtAddr,
350
	/// Last stack pointer on the user stack before jumping to kernel space
351
	pub user_stack_pointer: VirtAddr,
352
353
	/// Last FPU state before a context switch to another task using the FPU
	pub last_fpu_state: arch::processor::FPUState,
354
	/// ID of the core this task is running on
355
	pub core_id: CoreId,
356
	/// Stack of the task
357
	pub stacks: TaskStacks,
358
	/// next task in queue
359
	pub next: Option<Rc<RefCell<Task>>>,
360
	/// previous task in queue
361
	pub prev: Option<Rc<RefCell<Task>>>,
362
	/// Task Thread-Local-Storage (TLS)
363
	pub tls: Option<TaskTLS>,
364
365
	/// Reason why wakeup() has been called the last time
	pub last_wakeup_reason: WakeupReason,
366
367
368
	/// lwIP error code for this task
	#[cfg(feature = "newlib")]
	pub lwip_errno: i32,
369
370
371
372
373
374
375
376
}

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 {
377
378
379
380
381
382
383
	pub fn new(
		tid: TaskId,
		core_id: CoreId,
		task_status: TaskStatus,
		task_prio: Priority,
		stack_size: usize,
	) -> Task {
384
		debug!("Creating new task {} on core {}", tid, core_id);
385
386
387
388
389

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
390
391
			last_stack_pointer: VirtAddr(0u64),
			user_stack_pointer: VirtAddr(0u64),
392
			last_fpu_state: arch::processor::FPUState::new(),
393
			core_id,
394
			stacks: TaskStacks::new(stack_size),
395
396
			next: None,
			prev: None,
397
			tls: None,
398
			last_wakeup_reason: WakeupReason::Custom,
399
400
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
401
402
403
		}
	}

404
	pub fn new_idle(tid: TaskId, core_id: CoreId) -> Task {
405
		debug!("Creating idle task {}", tid);
406

407
408
		Task {
			id: tid,
409
			status: TaskStatus::Idle,
410
			prio: IDLE_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::from_boot_stacks(),
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 clone(tid: TaskId, core_id: CoreId, task: &Task) -> Task {
426
		debug!("Cloning task {} from task {}", tid, task.id);
427
428
429

		Task {
			id: tid,
430
			status: TaskStatus::Ready,
431
			prio: task.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: task.stacks.clone(),
437
438
			next: None,
			prev: None,
439
			tls: task.tls.clone(),
440
			last_wakeup_reason: task.last_wakeup_reason,
441
442
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
443
444
		}
	}
445
446
}

447
/*impl Drop for Task {
448
449
450
	fn drop(&mut self) {
		debug!("Drop task {}", self.id);
	}
451
}*/
452

453
454
struct BlockedTask {
	task: Rc<RefCell<Task>>,
455
	wakeup_time: Option<u64>,
456
457
}

458
459
460
461
462
463
impl BlockedTask {
	pub fn new(task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) -> Self {
		Self { task, wakeup_time }
	}
}

464
pub struct BlockedTaskQueue {
465
	list: LinkedList<BlockedTask>,
466
467
468
469
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
470
		Self {
471
			list: LinkedList::new(),
472
		}
473
474
475
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
476
		{
477
			let mut borrowed = task.borrow_mut();
478
479
480
481
482
			debug!(
				"Waking up task {} on core {}",
				borrowed.id, borrowed.core_id
			);

483
484
485
486
487
488
489
490
			assert!(
				borrowed.core_id == core_id(),
				"Try to wake up task {} on the wrong core {} != {}",
				borrowed.id,
				borrowed.core_id,
				core_id()
			);

491
			assert!(
492
				borrowed.status == TaskStatus::Blocked,
493
494
495
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
496
			borrowed.status = TaskStatus::Ready;
497
			borrowed.last_wakeup_reason = reason;
498
		}
499

500
		// Add the task to the ready queue.
501
		core_scheduler().ready_queue.push(task);
502
503
	}

504
	/// Blocks the given task for `wakeup_time` ticks, or indefinitely if None is given.
505
	pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
506
507
508
		{
			// Set the task status to Blocked.
			let mut borrowed = task.borrow_mut();
509
			debug!("Blocking task {}", borrowed.id);
510

511
512
			assert_eq!(
				borrowed.status,
513
				TaskStatus::Running,
514
515
516
				"Trying to block task {} which is not running",
				borrowed.id
			);
517
			borrowed.status = TaskStatus::Blocked;
518
		}
519

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

522
523
		// 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
524
			let first_task = true;
525
			let mut cursor = self.list.cursor_front_mut();
526
527
528
529
530
531
532
			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);
				}
			});
533

534
535
			while let Some(node) = cursor.current() {
				let node_wakeup_time = node.wakeup_time;
536
				if node_wakeup_time.is_none() || wt < node_wakeup_time.unwrap() {
537
					cursor.insert_before(new_node);
538

539
540
541
					return;
				}

542
				cursor.move_next();
543
			}
544
545
546

			// No, then just insert it at the end of the list.
			self.list.push_back(new_node);
547
548
		} else {
			// No, then just insert it at the end of the list.
549
			self.list.push_back(new_node);
550
551
552
553
		}
	}

	/// Manually wake up a blocked task.
554
	pub fn custom_wakeup(&mut self, task: TaskHandle) {
555
		let mut first_task = true;
556
		let mut cursor = self.list.cursor_front_mut();
557
558

		// Loop through all blocked tasks to find it.
559
560
		while let Some(node) = cursor.current() {
			if node.task.borrow().id == task.get_id() {
561
				// Remove it from the list of blocked tasks and wake it up.
562
563
				Self::wakeup_task(node.task.clone(), WakeupReason::Custom);
				cursor.remove_current();
564
565
566
567

				// 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 {
568
569
					if let Some(next_node) = cursor.current() {
						arch::set_oneshot_timer(next_node.wakeup_time);
570
571
572
573
574
575
576
					}
				}

				break;
			}

			first_task = false;
577
			cursor.move_next();
578
579
580
581
582
583
584
585
586
		}
	}

	/// 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.
587
		let time = arch::processor::get_timer_ticks();
588
		let mut cursor = self.list.cursor_front_mut();
589
590

		// Loop through all blocked tasks.
591
		while let Some(node) = cursor.current() {
592
593
			// Get the wakeup time of this task and check if we have reached the first task
			// that hasn't elapsed yet or waits indefinitely.
594
			let node_wakeup_time = node.wakeup_time;
595
596
597
598
599
600
601
602
			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.
603
604
			Self::wakeup_task(node.task.clone(), WakeupReason::Timer);
			cursor.remove_current();
605
606
		}
	}
607
}