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 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::convert::TryInto;
18
use core::fmt;
19
use scheduler::CoreId;
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
101
102
103
104
105
106
		Self {
			id: id,
			priority: priority,
			core_id: core_id,
		}
	}

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
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
197
198
		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);
			}
		}
	}
}

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;
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
294
			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());
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 FPU state before a context switch to another task using the FPU
	pub last_fpu_state: arch::processor::FPUState,
375
	/// ID of the core this task is running on
376
	pub core_id: CoreId,
377
	/// Stack of the task
378
	pub stacks: TaskStacks,
379
	/// next task in queue
380
	pub next: Option<Rc<RefCell<Task>>>,
381
	/// previous task in queue
382
	pub prev: Option<Rc<RefCell<Task>>>,
383
	/// Task Thread-Local-Storage (TLS)
384
	pub tls: Option<TaskTLS>,
385
386
	/// Reason why wakeup() has been called the last time
	pub last_wakeup_reason: WakeupReason,
387
388
389
	/// lwIP error code for this task
	#[cfg(feature = "newlib")]
	pub lwip_errno: i32,
390
391
392
393
394
395
396
397
}

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

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

424
	pub fn new_idle(tid: TaskId, core_id: CoreId) -> Task {
425
		debug!("Creating idle task {}", tid);
426

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

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

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

465
466
467
468
469
470
/*impl Drop for Task {
	fn drop(&mut self) {
		debug!("Drop task {}", self.id);
	}
}*/

471
472
struct BlockedTask {
	task: Rc<RefCell<Task>>,
473
	wakeup_time: Option<u64>,
474
475
}

476
pub struct BlockedTaskQueue {
477
	list: DoublyLinkedList<BlockedTask>,
478
479
480
481
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
482
483
484
		Self {
			list: DoublyLinkedList::new(),
		}
485
486
487
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
488
		{
489
			let mut borrowed = task.borrow_mut();
490
491
492
493
494
			debug!(
				"Waking up task {} on core {}",
				borrowed.id, borrowed.core_id
			);

495
496
497
498
499
500
501
502
			assert!(
				borrowed.core_id == core_id(),
				"Try to wake up task {} on the wrong core {} != {}",
				borrowed.id,
				borrowed.core_id,
				core_id()
			);

503
504
505
506
507
			assert!(
				borrowed.status == TaskStatus::TaskBlocked,
				"Trying to wake up task {} which is not blocked",
				borrowed.id
			);
508
509
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;
510
		}
511

512
		// Add the task to the ready queue.
513
		core_scheduler().ready_queue.push(task);
514
515
	}

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

523
524
525
526
527
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
528
529
			borrowed.status = TaskStatus::TaskBlocked;
		}
530

531
532
533
534
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
535

536
537
538
539
540
541
542
543
544
		// 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);
545

546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
					// 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.
570
	pub fn custom_wakeup(&mut self, task: TaskHandle) {
571
572
573
574
575
		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() {
576
			if node.borrow().value.task.borrow().id == task.get_id() {
577
578
				// Remove it from the list of blocked tasks and wake it up.
				self.list.remove(node.clone());
579
				Self::wakeup_task(node.borrow().value.task.clone(), WakeupReason::Custom);
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601

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

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