task.rs 14.7 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
10
11
12
13
14
use crate::arch;
use crate::arch::percore::*;
use crate::arch::processor::msb;
use crate::arch::scheduler::{TaskStacks, TaskTLS};
use crate::collections::{DoublyLinkedList, Node};
use crate::scheduler::CoreId;
15
use alloc::collections::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
363
364
365
366
367
368
369
370
371
372
}

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

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

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

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

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

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

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

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

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

481
pub struct BlockedTaskQueue {
482
	list: DoublyLinkedList<BlockedTask>,
483
484
485
486
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
487
488
489
		Self {
			list: DoublyLinkedList::new(),
		}
490
491
492
	}

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

500
501
502
503
504
505
506
507
			assert!(
				borrowed.core_id == core_id(),
				"Try to wake up task {} on the wrong core {} != {}",
				borrowed.id,
				borrowed.core_id,
				core_id()
			);

508
509
510
511
512
			assert!(
				borrowed.status == TaskStatus::TaskBlocked,
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
513
514
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;
515
		}
516

517
		// Add the task to the ready queue.
518
		core_scheduler().ready_queue.push(task);
519
520
	}

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

528
529
530
			assert_eq!(
				borrowed.status,
				TaskStatus::TaskRunning,
531
532
533
				"Trying to block task {} which is not running",
				borrowed.id
			);
534
535
			borrowed.status = TaskStatus::TaskBlocked;
		}
536

537
		let new_node = Node::new(BlockedTask { task, wakeup_time });
538

539
540
541
542
543
544
545
546
547
		// Shall the task automatically be woken up after a certain time?
		if let Some(wt) = wakeup_time {
			let mut first_task = true;

			// Yes, then insert it at the right position into the list sorted by wakeup time.
			for node in self.list.iter() {
				let node_wakeup_time = node.borrow().value.wakeup_time;
				if node_wakeup_time.is_none() || wt < node_wakeup_time.unwrap() {
					self.list.insert_before(new_node, node);
548

549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
					// If this 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);
					}

					return;
				}

				first_task = false;
			}

			// The right position is at the end of the list or the list is empty.
			self.list.push(new_node);
			if first_task {
				arch::set_oneshot_timer(wakeup_time);
			}
		} else {
			// No, then just insert it at the end of the list.
			self.list.push(new_node);
		}
	}

	/// Manually wake up a blocked task.
573
	pub fn custom_wakeup(&mut self, task: TaskHandle) {
574
575
576
577
578
		let mut first_task = true;
		let mut iter = self.list.iter();

		// Loop through all blocked tasks to find it.
		while let Some(node) = iter.next() {
579
			if node.borrow().value.task.borrow().id == task.get_id() {
580
581
				// Remove it from the list of blocked tasks and wake it up.
				self.list.remove(node.clone());
582
				Self::wakeup_task(node.borrow().value.task.clone(), WakeupReason::Custom);
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604

				// 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 {
					if let Some(next_node) = iter.next() {
						arch::set_oneshot_timer(next_node.borrow().value.wakeup_time);
					}
				}

				break;
			}

			first_task = false;
		}
	}

	/// 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.
605
		let time = arch::processor::get_timer_ticks();
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623

		// Loop through all blocked tasks.
		for node in self.list.iter() {
			// Get the wakeup time of this task and check if we have reached the first task
			// that hasn't elapsed yet or waits indefinitely.
			let node_wakeup_time = node.borrow().value.wakeup_time;
			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.
			self.list.remove(node.clone());
			Self::wakeup_task(node.borrow().value.task.clone(), WakeupReason::Timer);
		}
	}
624
}