task.rs 13.8 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

use alloc::rc::Rc;
use arch;
11
use arch::processor::msb;
12
use arch::scheduler::{TaskStacks, TaskTLS};
13
use collections::{DoublyLinkedList, Node};
14
use core::cell::RefCell;
15
use core::fmt;
16
use scheduler;
17
use synch::spinlock::SpinlockIrqSave;
18
19
20
21
22
23
24
25
26

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

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

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

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

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

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

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

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

90
91
92
93
94
95
96
97
98
struct QueueHead {
	head: Option<Rc<RefCell<Task>>>,
	tail: Option<Rc<RefCell<Task>>>,
}

impl QueueHead {
	pub const fn new() -> Self {
		QueueHead {
			head: None,
99
			tail: None,
100
101
102
103
104
105
		}
	}
}

impl Default for QueueHead {
	fn default() -> Self {
106
107
108
109
		Self {
			head: None,
			tail: None,
		}
110
111
112
	}
}

113
114
/// Realize a priority queue for tasks
pub struct PriorityTaskQueue {
115
	queues: [QueueHead; NO_PRIORITIES],
116
	prio_bitmap: u64,
117
118
119
120
}

impl PriorityTaskQueue {
	/// Creates an empty priority queue for tasks
121
	pub const fn new() -> PriorityTaskQueue {
122
		PriorityTaskQueue {
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
156
			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,
157
158
159
		}
	}

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

		self.prio_bitmap |= 1 << i;
166
167
168
169
170
171
		match self.queues[i].tail {
			None => {
				// first element in the queue
				self.queues[i].head = Some(task.clone());

				let mut borrow = task.borrow_mut();
172
				borrow.next = None;
173
				borrow.prev = None;
174
			}
175
176
177
178
179
180
181
182
183
184
185
			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());
			}
		}

		self.queues[i].tail = Some(task.clone());
186
187
	}

188
	fn pop_from_queue(&mut self, queue_index: usize) -> Option<Rc<RefCell<Task>>> {
189
190
191
192
		let new_head;
		let task;

		match self.queues[queue_index].head {
193
194
195
			None => {
				return None;
			}
196
197
			Some(ref mut head) => {
				let mut borrow = head.borrow_mut();
198

199
				match borrow.next {
200
201
202
					Some(ref mut nhead) => {
						nhead.borrow_mut().prev = None;
					}
203
204
205
206
207
208
209
210
					None => {}
				}

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

				task = head.clone();
211
			}
212
		}
213

214
215
216
217
218
219
220
		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)
221
222
223
224
	}

	/// Pop the task with the highest priority from the queue
	pub fn pop(&mut self) -> Option<Rc<RefCell<Task>>> {
225
226
227
228
229
		if let Some(i) = msb(self.prio_bitmap) {
			return self.pop_from_queue(i as usize);
		}

		None
230
231
232
233
	}

	/// 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>>> {
234
		if let Some(i) = msb(self.prio_bitmap) {
235
			if i >= u64::from(prio.into()) {
236
237
				return self.pop_from_queue(i as usize);
			}
238
		}
239
240

		None
241
	}
242
243
244
245

	/// Remove a specific task from the priority queue.
	pub fn remove(&mut self, task: Rc<RefCell<Task>>) {
		let i = task.borrow().prio.into() as usize;
246
247
248
249
250
251
252
		//assert!(i < NO_PRIORITIES, "Priority {} is too high", i);

		let mut curr = self.queues[i].head.clone();
		let mut next_curr;

		loop {
			match curr {
253
254
255
				None => {
					break;
				}
256
257
258
				Some(ref curr_task) => {
					if Rc::ptr_eq(&curr_task, &task) {
						let (mut prev, mut next) = {
259
							let borrowed = curr_task.borrow_mut();
260
261
262
263
							(borrowed.prev.clone(), borrowed.next.clone())
						};

						match prev {
264
265
266
							Some(ref mut t) => {
								t.borrow_mut().next = next.clone();
							}
267
268
269
270
							None => {}
						};

						match next {
271
272
273
							Some(ref mut t) => {
								t.borrow_mut().prev = prev.clone();
							}
274
275
276
277
278
279
280
281
282
							None => {}
						};

						break;
					}

					next_curr = curr_task.borrow().next.clone();
				}
			}
283

284
285
			curr = next_curr.clone();
		}
286

287
		let new_head = match self.queues[i].head {
288
			Some(ref curr_task) => Rc::ptr_eq(&curr_task, &task),
289
			None => false,
290
		};
291

292
		if new_head {
293
			self.queues[i].head = task.borrow().next.clone();
294

295
			if self.queues[i].head.is_none() {
296
				self.queues[i].tail = None;
297
298
				self.prio_bitmap &= !(1 << i as u64);
			}
299
300
		}
	}
301
302
303
304
305
306
307
308
309
310
311
312
313
}

/// 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,
314
315
	/// Last FPU state before a context switch to another task using the FPU
	pub last_fpu_state: arch::processor::FPUState,
316
	/// ID of the core this task is running on
317
	pub core_id: usize,
318
	/// Stack of the task
319
	pub stacks: TaskStacks,
320
	/// next task in queue
321
	pub next: Option<Rc<RefCell<Task>>>,
322
	/// previous task in queue
323
	pub prev: Option<Rc<RefCell<Task>>>,
324
325
	/// list of waiting tasks
	pub wakeup: SpinlockIrqSave<BlockedTaskQueue>,
326
	/// Task Thread-Local-Storage (TLS)
327
	pub tls: Option<RefCell<TaskTLS>>,
328
329
	/// Reason why wakeup() has been called the last time
	pub last_wakeup_reason: WakeupReason,
330
331
332
	/// lwIP error code for this task
	#[cfg(feature = "newlib")]
	pub lwip_errno: i32,
333
334
335
336
337
338
339
340
}

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 {
341
	pub fn new(tid: TaskId, core_id: usize, task_status: TaskStatus, task_prio: Priority) -> Task {
342
		debug!("Creating new task {}", tid);
343
344
345
346
347
348

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
			last_stack_pointer: 0,
349
			last_fpu_state: arch::processor::FPUState::new(),
350
			core_id: core_id,
351
			stacks: TaskStacks::new(),
352
353
			next: None,
			prev: None,
354
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
355
			tls: None,
356
			last_wakeup_reason: WakeupReason::Custom,
357
358
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
359
360
361
		}
	}

362
363
	pub fn new_idle(tid: TaskId, core_id: usize) -> Task {
		debug!("Creating idle task {}", tid);
364

365
366
367
		Task {
			id: tid,
			status: TaskStatus::TaskIdle,
368
			prio: IDLE_PRIO,
369
			last_stack_pointer: 0,
370
			last_fpu_state: arch::processor::FPUState::new(),
371
			core_id: core_id,
372
			stacks: TaskStacks::from_boot_stacks(),
373
374
			next: None,
			prev: None,
375
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
376
			tls: None,
377
			last_wakeup_reason: WakeupReason::Custom,
378
379
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
380
381
		}
	}
382

383
384
	pub fn clone(tid: TaskId, core_id: usize, task: &Task) -> Task {
		debug!("Cloning task {} from task {}", tid, task.id);
385
386
387
388
389
390
391
392

		Task {
			id: tid,
			status: TaskStatus::TaskReady,
			prio: task.prio,
			last_stack_pointer: 0,
			last_fpu_state: arch::processor::FPUState::new(),
			core_id: core_id,
393
			stacks: TaskStacks::new(),
394
395
			next: None,
			prev: None,
396
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
397
			tls: task.tls.clone(),
398
			last_wakeup_reason: task.last_wakeup_reason,
399
400
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
401
402
		}
	}
403
404
}

405
406
struct BlockedTask {
	task: Rc<RefCell<Task>>,
407
	wakeup_time: Option<u64>,
408
409
}

410
pub struct BlockedTaskQueue {
411
	list: DoublyLinkedList<BlockedTask>,
412
413
414
415
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
416
417
418
		Self {
			list: DoublyLinkedList::new(),
		}
419
420
421
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
422
423
		// Get the Core ID of the task to wake up.
		let core_id = {
424
			let mut borrowed = task.borrow_mut();
425
426
427
428
429
430
431
432
433
434
			debug!(
				"Waking up task {} on core {}",
				borrowed.id, borrowed.core_id
			);

			assert!(
				borrowed.status == TaskStatus::TaskBlocked,
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
435
436
437
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;

438
			borrowed.core_id
439
440
		};

441
		// Get the scheduler of that core.
442
443
		let core_scheduler = scheduler::get_scheduler(core_id);

444
		// Add the task to the ready queue.
445
446
447
448
		let mut state_locked = core_scheduler.state.lock();
		state_locked.ready_queue.push(task);
		if state_locked.is_halted {
			// Wake up the CPU if needed.
449
			arch::wakeup_core(core_id);
450
451
452
		}
	}

453
	/// Blocks the given task for `wakeup_time` ticks, or indefinitely if None is given.
454
	pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
455
456
457
		{
			// Set the task status to Blocked.
			let mut borrowed = task.borrow_mut();
458
			debug!("Blocking task {}", borrowed.id);
459

460
461
462
463
464
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
465
466
			borrowed.status = TaskStatus::TaskBlocked;
		}
467

468
469
470
471
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
472

473
474
475
476
477
478
479
480
481
		// 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);
482

483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
					// 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);
		}
	}

506
	/// Wakeup all blocked tasks
507
508
509
510
511
	pub fn wakeup_all(&mut self) -> bool {
		if self.list.is_empty() {
			return false;
		}

512
		// Loop through all blocked tasks to find it.
513
		for node in self.list.iter() {
514
515
516
517
			// Remove it from the list of blocked tasks and wake it up.
			self.list.remove(node.clone());
			Self::wakeup_task(node.borrow().value.task.clone(), WakeupReason::All);
		}
518
519

		true
520
521
	}

522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
	/// Manually wake up a blocked task.
	pub fn custom_wakeup(&mut self, task: Rc<RefCell<Task>>) {
		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() {
			if Rc::ptr_eq(&node.borrow().value.task, &task) {
				// Remove it from the list of blocked tasks and wake it up.
				self.list.remove(node.clone());
				Self::wakeup_task(task, WakeupReason::Custom);

				// 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.
555
		let time = arch::processor::get_timer_ticks();
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573

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