task.rs 14.5 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::mm::paging::{BasePageSize, PageSize};
12
use arch::processor::msb;
13
use arch::scheduler::TaskStacks;
14
use collections::{DoublyLinkedList, Node};
15
use core::cell::RefCell;
16
use core::fmt;
17
use mm;
18
use scheduler;
19
use synch::spinlock::SpinlockIrqSave;
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
/// Reason why wakeup() has been called on a task.
#[derive(Clone, Copy, PartialEq)]
pub enum WakeupReason {
	Custom,
	Timer,
37
	All,
38
39
}

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

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

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

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

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

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

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

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

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

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

impl PriorityTaskQueue {
	/// Creates an empty priority queue for tasks
123
	pub const fn new() -> PriorityTaskQueue {
124
		PriorityTaskQueue {
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
			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,
159
160
161
		}
	}

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

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

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

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

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

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

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

				task = head.clone();
213
			}
214
		}
215

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

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

		None
232
233
234
235
	}

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

		None
243
	}
244
245
246
247

	/// 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;
248
249
250
251
252
253
254
		//assert!(i < NO_PRIORITIES, "Priority {} is too high", i);

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

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

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

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

						break;
					}

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

286
287
			curr = next_curr.clone();
		}
288

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

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

297
298
299
			if self.queues[i].head.is_none() {
				self.prio_bitmap &= !(1 << i as u64);
			}
300
301
		}
	}
302
303
}

304
305
306
307
308
309
310
311
312
313
314
pub struct TaskTLS {
	address: usize,
	size: usize,
}

impl TaskTLS {
	pub fn new(size: usize) -> Self {
		// We allocate in BasePageSize granularity, so we don't have to manually impose an
		// additional alignment for TLS variables.
		let memory_size = align_up!(size, BasePageSize::SIZE);
		Self {
315
			address: mm::allocate(memory_size, true),
316
			size: memory_size,
317
318
319
320
321
322
323
324
325
		}
	}

	pub fn address(&self) -> usize {
		self.address
	}
}

impl Drop for TaskTLS {
326
	fn drop(&mut self) {
Stefan Lankes's avatar
Stefan Lankes committed
327
328
329
330
		debug!(
			"Deallocate TLS at 0x{:x} (size 0x{:x})",
			self.address, self.size
		);
331
332
333
334
		mm::deallocate(self.address, self.size);
	}
}

335
336
337
338
339
340
341
342
343
344
345
/// 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,
346
347
	/// Last FPU state before a context switch to another task using the FPU
	pub last_fpu_state: arch::processor::FPUState,
348
	/// ID of the core this task is running on
349
	pub core_id: usize,
350
	/// Stack of the task
351
	pub stacks: TaskStacks,
352
	/// next task in queue
353
	pub next: Option<Rc<RefCell<Task>>>,
354
	/// previous task in queue
355
	pub prev: Option<Rc<RefCell<Task>>>,
356
357
	/// list of waiting tasks
	pub wakeup: SpinlockIrqSave<BlockedTaskQueue>,
358
	/// Task Thread-Local-Storage (TLS)
359
360
361
	pub tls: Option<Rc<RefCell<TaskTLS>>>,
	/// Reason why wakeup() has been called the last time
	pub last_wakeup_reason: WakeupReason,
362
363
364
	/// lwIP error code for this task
	#[cfg(feature = "newlib")]
	pub lwip_errno: i32,
365
366
367
368
369
370
371
372
}

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 {
373
	pub fn new(tid: TaskId, core_id: usize, task_status: TaskStatus, task_prio: Priority) -> Task {
374
		debug!("Creating new task {}", tid);
375
376
377
378
379
380

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
			last_stack_pointer: 0,
381
			last_fpu_state: arch::processor::FPUState::new(),
382
			core_id: core_id,
383
			stacks: TaskStacks::new(),
384
385
			next: None,
			prev: None,
386
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
387
			tls: None,
388
			last_wakeup_reason: WakeupReason::Custom,
389
390
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
391
392
393
		}
	}

394
395
	pub fn new_idle(tid: TaskId, core_id: usize) -> Task {
		debug!("Creating idle task {}", tid);
396

397
398
399
		Task {
			id: tid,
			status: TaskStatus::TaskIdle,
400
			prio: IDLE_PRIO,
401
			last_stack_pointer: 0,
402
			last_fpu_state: arch::processor::FPUState::new(),
403
			core_id: core_id,
404
			stacks: TaskStacks::from_boot_stacks(),
405
406
			next: None,
			prev: None,
407
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
408
			tls: None,
409
			last_wakeup_reason: WakeupReason::Custom,
410
411
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
412
413
		}
	}
414

415
416
	pub fn clone(tid: TaskId, core_id: usize, task: &Task) -> Task {
		debug!("Cloning task {} from task {}", tid, task.id);
417
418
419
420
421
422
423
424

		Task {
			id: tid,
			status: TaskStatus::TaskReady,
			prio: task.prio,
			last_stack_pointer: 0,
			last_fpu_state: arch::processor::FPUState::new(),
			core_id: core_id,
425
			stacks: TaskStacks::new(),
426
427
			next: None,
			prev: None,
428
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
429
			tls: task.tls.clone(),
430
			last_wakeup_reason: task.last_wakeup_reason,
431
432
			#[cfg(feature = "newlib")]
			lwip_errno: 0,
433
434
		}
	}
435
436
}

437
438
struct BlockedTask {
	task: Rc<RefCell<Task>>,
439
	wakeup_time: Option<u64>,
440
441
}

442
pub struct BlockedTaskQueue {
443
	list: DoublyLinkedList<BlockedTask>,
444
445
446
447
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
448
449
450
		Self {
			list: DoublyLinkedList::new(),
		}
451
452
453
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
454
455
		// Get the Core ID of the task to wake up.
		let core_id = {
456
			let mut borrowed = task.borrow_mut();
457
458
459
460
461
462
463
464
465
466
			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
			);
467
468
469
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;

470
			borrowed.core_id
471
472
		};

473
		// Get the scheduler of that core.
474
475
		let core_scheduler = scheduler::get_scheduler(core_id);

476
		// Add the task to the ready queue.
477
478
479
480
481
		let is_halted = {
			let mut state_locked = core_scheduler.state.lock();
			state_locked.ready_queue.push(task);
			state_locked.is_halted
		};
482
483

		// Wake up the CPU if needed.
484
		if is_halted {
485
			arch::wakeup_core(core_id);
486
487
488
		}
	}

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

496
497
498
499
500
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
501
502
			borrowed.status = TaskStatus::TaskBlocked;
		}
503

504
505
506
507
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
508

509
510
511
512
513
514
515
516
517
		// 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);
518

519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
					// 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);
		}
	}

542
	/// Wakeup all blocked tasks
543
544
545
546
547
	pub fn wakeup_all(&mut self) -> bool {
		if self.list.is_empty() {
			return false;
		}

548
		// Loop through all blocked tasks to find it.
549
		for node in self.list.iter() {
550
551
552
553
			// 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);
		}
554
555

		true
556
557
	}

558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
	/// 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.
591
		let time = arch::processor::get_timer_ticks();
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609

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