task.rs 14.2 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 alloc::collections::VecDeque;
10
11
use alloc::rc::Rc;
use arch;
12
use arch::percore::*;
13
use arch::processor::msb;
14
use arch::scheduler::{TaskStacks, TaskTLS};
15
use collections::{DoublyLinkedList, Node};
16
use core::cell::RefCell;
17
use core::fmt;
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
35
36
/// Reason why wakeup() has been called on a task.
#[derive(Clone, Copy, PartialEq)]
pub enum WakeupReason {
	Custom,
	Timer,
}

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

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

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

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

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

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

89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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
144
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
#[derive(Copy, Clone, Debug)]
pub struct TaskHandle {
	id: TaskId,
	priority: Priority,
	core_id: usize,
}

impl TaskHandle {
	pub fn new(id: TaskId, priority: Priority, core_id: usize) -> Self {
		Self {
			id: id,
			priority: priority,
			core_id: core_id,
		}
	}

	pub fn get_core_id(&self) -> usize {
		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);

		self.prio_bitmap |= 1 << i;
		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);
			}
		}
	}
}

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

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

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

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

impl PriorityTaskQueue {
	/// Creates an empty priority queue for tasks
228
	pub const fn new() -> PriorityTaskQueue {
229
		PriorityTaskQueue {
230
231
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
			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,
264
265
266
		}
	}

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

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

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

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

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

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

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

				task = head.clone();
318
			}
319
		}
320

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

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

		None
337
338
339
340
	}

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

		None
348
349
350
351
352
353
354
355
356
357
358
359
360
361
	}
}

/// 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,
362
363
	/// Last FPU state before a context switch to another task using the FPU
	pub last_fpu_state: arch::processor::FPUState,
364
	/// ID of the core this task is running on
365
	pub core_id: usize,
366
	/// Stack of the task
367
	pub stacks: TaskStacks,
368
	/// next task in queue
369
	pub next: Option<Rc<RefCell<Task>>>,
370
	/// previous task in queue
371
	pub prev: Option<Rc<RefCell<Task>>>,
372
	/// Task Thread-Local-Storage (TLS)
373
	pub tls: Option<TaskTLS>,
374
375
	/// Reason why wakeup() has been called the last time
	pub last_wakeup_reason: WakeupReason,
376
377
378
	/// lwIP error code for this task
	#[cfg(feature = "newlib")]
	pub lwip_errno: i32,
379
380
381
382
383
384
385
386
}

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 {
387
	pub fn new(tid: TaskId, core_id: usize, task_status: TaskStatus, task_prio: Priority) -> Task {
388
		debug!("Creating new task {}", tid);
389
390
391
392
393
394

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

407
408
	pub fn new_idle(tid: TaskId, core_id: usize) -> Task {
		debug!("Creating idle task {}", tid);
409

410
411
412
		Task {
			id: tid,
			status: TaskStatus::TaskIdle,
413
			prio: IDLE_PRIO,
414
			last_stack_pointer: 0,
415
			last_fpu_state: arch::processor::FPUState::new(),
416
			core_id: core_id,
417
			stacks: TaskStacks::from_boot_stacks(),
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
428
	pub fn clone(tid: TaskId, core_id: usize, task: &Task) -> Task {
		debug!("Cloning task {} from task {}", tid, task.id);
429
430
431
432
433
434
435
436

		Task {
			id: tid,
			status: TaskStatus::TaskReady,
			prio: task.prio,
			last_stack_pointer: 0,
			last_fpu_state: arch::processor::FPUState::new(),
			core_id: core_id,
437
			stacks: TaskStacks::new(),
438
439
			next: None,
			prev: None,
440
			tls: task.tls.clone(),
441
			last_wakeup_reason: task.last_wakeup_reason,
442
443
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
444
445
		}
	}
446
447
}

448
449
struct BlockedTask {
	task: Rc<RefCell<Task>>,
450
	wakeup_time: Option<u64>,
451
452
}

453
pub struct BlockedTaskQueue {
454
	list: DoublyLinkedList<BlockedTask>,
455
456
457
458
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
459
460
461
		Self {
			list: DoublyLinkedList::new(),
		}
462
463
464
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
465
		{
466
			let mut borrowed = task.borrow_mut();
467
468
469
470
471
			debug!(
				"Waking up task {} on core {}",
				borrowed.id, borrowed.core_id
			);

472
473
474
475
476
477
478
479
			assert!(
				borrowed.core_id == core_id(),
				"Try to wake up task {} on the wrong core {} != {}",
				borrowed.id,
				borrowed.core_id,
				core_id()
			);

480
481
482
483
484
			assert!(
				borrowed.status == TaskStatus::TaskBlocked,
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
485
486
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;
487
		}
488

489
		// Add the task to the ready queue.
490
		core_scheduler().ready_queue.push(task);
491
492
	}

493
	/// Blocks the given task for `wakeup_time` ticks, or indefinitely if None is given.
494
	pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
495
496
497
		{
			// Set the task status to Blocked.
			let mut borrowed = task.borrow_mut();
498
			debug!("Blocking task {}", borrowed.id);
499

500
501
502
503
504
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
505
506
			borrowed.status = TaskStatus::TaskBlocked;
		}
507

508
509
510
511
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
512

513
514
515
516
517
518
519
520
521
		// 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);
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
					// 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.
547
	pub fn custom_wakeup(&mut self, task: TaskHandle) {
548
549
550
551
552
		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() {
553
			if node.borrow().value.task.borrow().id == task.get_id() {
554
555
				// Remove it from the list of blocked tasks and wake it up.
				self.list.remove(node.clone());
556
				Self::wakeup_task(node.borrow().value.task.clone(), WakeupReason::Custom);
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578

				// 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.
579
		let time = arch::processor::get_timer_ticks();
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597

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