task.rs 15 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
14
use crate::arch::percore::*;
use crate::arch::processor::msb;
use crate::arch::scheduler::{TaskStacks, TaskTLS};
use crate::scheduler::CoreId;
15
use alloc::collections::{LinkedList, VecDeque};
16
17
use alloc::rc::Rc;
use core::cell::RefCell;
18
use core::convert::TryInto;
19
use core::fmt;
20
21
22
23
24
25
26
27
28

/// The status of the task - used for scheduling
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum TaskStatus {
	TaskInvalid,
	TaskReady,
	TaskRunning,
	TaskBlocked,
	TaskFinished,
29
	TaskIdle,
30
31
}

32
33
34
35
36
37
38
/// Reason why wakeup() has been called on a task.
#[derive(Clone, Copy, PartialEq)]
pub enum WakeupReason {
	Custom,
	Timer,
}

39
40
/// Unique identifier for a task (i.e. `pid`).
#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Clone, Copy)]
Colin Finck's avatar
Colin Finck committed
41
pub struct TaskId(u32);
42
43

impl TaskId {
Colin Finck's avatar
Colin Finck committed
44
	pub const fn into(self) -> u32 {
45
46
47
		self.0
	}

Colin Finck's avatar
Colin Finck committed
48
	pub const fn from(x: u32) -> Self {
49
50
51
52
53
		TaskId(x)
	}
}

impl fmt::Display for TaskId {
54
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
		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 {
74
	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
75
76
77
78
		write!(f, "{}", self.0)
	}
}

Stefan Lankes's avatar
Stefan Lankes committed
79
#[allow(dead_code)]
80
pub const HIGH_PRIO: Priority = Priority::from(3);
Stefan Lankes's avatar
Stefan Lankes committed
81
#[allow(dead_code)]
82
pub const NORMAL_PRIO: Priority = Priority::from(2);
Stefan Lankes's avatar
Stefan Lankes committed
83
#[allow(dead_code)]
84
pub const LOW_PRIO: Priority = Priority::from(1);
Stefan Lankes's avatar
Stefan Lankes committed
85
#[allow(dead_code)]
86
87
88
pub const IDLE_PRIO: Priority = Priority::from(0);

/// Maximum number of priorities
89
pub const NO_PRIORITIES: usize = 31;
90

91
92
93
94
#[derive(Copy, Clone, Debug)]
pub struct TaskHandle {
	id: TaskId,
	priority: Priority,
95
	core_id: CoreId,
96
97
98
}

impl TaskHandle {
99
	pub fn new(id: TaskId, priority: Priority, core_id: CoreId) -> Self {
100
		Self {
101
102
103
			id,
			priority,
			core_id,
104
105
106
		}
	}

107
	pub fn get_core_id(&self) -> CoreId {
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
		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);

144
		self.prio_bitmap |= (1 << i) as u64;
145
146
147
148
149
150
151
152
153
154
155
156
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
		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);
			}
		}
	}
}

199
200
201
202
203
204
205
struct QueueHead {
	head: Option<Rc<RefCell<Task>>>,
	tail: Option<Rc<RefCell<Task>>>,
}

impl QueueHead {
	pub const fn new() -> Self {
206
		Self {
207
			head: None,
208
			tail: None,
209
210
211
212
213
214
		}
	}
}

impl Default for QueueHead {
	fn default() -> Self {
215
216
217
218
		Self {
			head: None,
			tail: None,
		}
219
220
221
	}
}

222
223
/// Realize a priority queue for tasks
pub struct PriorityTaskQueue {
224
	queues: [QueueHead; NO_PRIORITIES],
225
	prio_bitmap: u64,
226
227
228
229
}

impl PriorityTaskQueue {
	/// Creates an empty priority queue for tasks
230
	pub const fn new() -> PriorityTaskQueue {
231
		PriorityTaskQueue {
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
			queues: [
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
				QueueHead::new(),
			],
			prio_bitmap: 0,
266
267
268
		}
	}

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

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

				let mut borrow = task.borrow_mut();
281
				borrow.next = None;
282
				borrow.prev = None;
283
			}
284
285
286
287
288
289
290
291
292
293
			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());
			}
		}

294
		self.queues[i].tail = Some(task);
295
296
	}

297
	fn pop_from_queue(&mut self, queue_index: usize) -> Option<Rc<RefCell<Task>>> {
298
299
300
301
		let new_head;
		let task;

		match self.queues[queue_index].head {
302
303
304
			None => {
				return None;
			}
305
306
			Some(ref mut head) => {
				let mut borrow = head.borrow_mut();
307

308
				match borrow.next {
309
310
311
					Some(ref mut nhead) => {
						nhead.borrow_mut().prev = None;
					}
312
313
314
315
316
317
318
319
					None => {}
				}

				new_head = borrow.next.clone();
				borrow.next = None;
				borrow.prev = None;

				task = head.clone();
320
			}
321
		}
322

323
324
325
326
327
328
329
		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)
330
331
332
333
	}

	/// Pop the task with the highest priority from the queue
	pub fn pop(&mut self) -> Option<Rc<RefCell<Task>>> {
334
335
336
337
338
		if let Some(i) = msb(self.prio_bitmap) {
			return self.pop_from_queue(i as usize);
		}

		None
339
340
341
342
	}

	/// 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>>> {
343
		if let Some(i) = msb(self.prio_bitmap) {
344
			if i >= u64::from(prio.into()) {
345
346
				return self.pop_from_queue(i as usize);
			}
347
		}
348
349

		None
350
	}
351
352
353
354
355
356
357
358
359

	/// 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
		}
	}
360
361
362
}

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

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 {
401
402
403
404
405
406
407
	pub fn new(
		tid: TaskId,
		core_id: CoreId,
		task_status: TaskStatus,
		task_prio: Priority,
		stack_size: usize,
	) -> Task {
408
		debug!("Creating new task {} on core {}", tid, core_id);
409
410
411
412
413

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

428
	pub fn new_idle(tid: TaskId, core_id: CoreId) -> Task {
429
		debug!("Creating idle task {}", tid);
430

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

449
	pub fn clone(tid: TaskId, core_id: CoreId, task: &Task) -> Task {
450
		debug!("Cloning task {} from task {}", tid, task.id);
451
452
453
454
455

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

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

477
478
struct BlockedTask {
	task: Rc<RefCell<Task>>,
479
	wakeup_time: Option<u64>,
480
481
}

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

488
pub struct BlockedTaskQueue {
489
	list: LinkedList<BlockedTask>,
490
491
492
493
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
494
		Self {
495
			list: LinkedList::new(),
496
		}
497
498
499
	}

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

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

515
516
517
518
519
			assert!(
				borrowed.status == TaskStatus::TaskBlocked,
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
520
521
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;
522
		}
523

524
		// Add the task to the ready queue.
525
		core_scheduler().ready_queue.push(task);
526
527
	}

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

535
536
537
			assert_eq!(
				borrowed.status,
				TaskStatus::TaskRunning,
538
539
540
				"Trying to block task {} which is not running",
				borrowed.id
			);
541
542
			borrowed.status = TaskStatus::TaskBlocked;
		}
543

544
		let new_node = BlockedTask::new(task.clone(), wakeup_time);
545

546
547
548
		// Shall the task automatically be woken up after a certain time?
		if let Some(wt) = wakeup_time {
			let mut first_task = true;
549
			let mut cursor = self.list.cursor_front_mut();
550
551
552
553
554
555
556
			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);
				}
			});
557

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

563
564
565
566
					return;
				}

				first_task = false;
567
				cursor.move_next();
568
			}
569
570
571

			// No, then just insert it at the end of the list.
			self.list.push_back(new_node);
572
573
		} else {
			// No, then just insert it at the end of the list.
574
			self.list.push_back(new_node);
575
576
577
578
		}
	}

	/// Manually wake up a blocked task.
579
	pub fn custom_wakeup(&mut self, task: TaskHandle) {
580
		let mut first_task = true;
581
		let mut cursor = self.list.cursor_front_mut();
582
583

		// Loop through all blocked tasks to find it.
584
585
		while let Some(node) = cursor.current() {
			if node.task.borrow().id == task.get_id() {
586
				// Remove it from the list of blocked tasks and wake it up.
587
588
				Self::wakeup_task(node.task.clone(), WakeupReason::Custom);
				cursor.remove_current();
589
590
591
592

				// 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 {
593
594
					if let Some(next_node) = cursor.current() {
						arch::set_oneshot_timer(next_node.wakeup_time);
595
596
597
598
599
600
601
					}
				}

				break;
			}

			first_task = false;
602
			cursor.move_next();
603
604
605
606
607
608
609
610
611
		}
	}

	/// 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.
612
		let time = arch::processor::get_timer_ticks();
613
		let mut cursor = self.list.cursor_front_mut();
614
615

		// Loop through all blocked tasks.
616
		while let Some(node) = cursor.current() {
617
618
			// Get the wakeup time of this task and check if we have reached the first task
			// that hasn't elapsed yet or waits indefinitely.
619
			let node_wakeup_time = node.wakeup_time;
620
621
622
623
624
625
626
627
			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.
628
629
			Self::wakeup_task(node.task.clone(), WakeupReason::Timer);
			cursor.remove_current();
630
631
		}
	}
632
}