task.rs 14.1 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
365
366
367
368
369
}

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

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
			last_stack_pointer: 0,
378
			last_fpu_state: arch::processor::FPUState::new(),
379
			core_id: core_id,
380
			stacks: TaskStacks::new(),
381
382
			next: None,
			prev: None,
383
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
384
			tls: None,
385
			last_wakeup_reason: WakeupReason::Custom,
386
387
388
		}
	}

389
390
	pub fn new_idle(tid: TaskId, core_id: usize) -> Task {
		debug!("Creating idle task {}", tid);
391

392
393
394
		Task {
			id: tid,
			status: TaskStatus::TaskIdle,
395
			prio: IDLE_PRIO,
396
			last_stack_pointer: 0,
397
			last_fpu_state: arch::processor::FPUState::new(),
398
			core_id: core_id,
399
			stacks: TaskStacks::from_boot_stacks(),
400
401
			next: None,
			prev: None,
402
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
403
			tls: None,
404
			last_wakeup_reason: WakeupReason::Custom,
405
406
		}
	}
407

408
409
	pub fn clone(tid: TaskId, core_id: usize, task: &Task) -> Task {
		debug!("Cloning task {} from task {}", tid, task.id);
410
411
412
413
414
415
416
417

		Task {
			id: tid,
			status: TaskStatus::TaskReady,
			prio: task.prio,
			last_stack_pointer: 0,
			last_fpu_state: arch::processor::FPUState::new(),
			core_id: core_id,
418
			stacks: TaskStacks::new(),
419
420
			next: None,
			prev: None,
421
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
422
			tls: task.tls.clone(),
423
			last_wakeup_reason: task.last_wakeup_reason,
424
425
		}
	}
426
427
}

428
429
struct BlockedTask {
	task: Rc<RefCell<Task>>,
430
	wakeup_time: Option<u64>,
431
432
}

433
pub struct BlockedTaskQueue {
434
	list: DoublyLinkedList<BlockedTask>,
435
436
437
438
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
439
440
441
		Self {
			list: DoublyLinkedList::new(),
		}
442
443
444
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
445
446
		// Get the Core ID of the task to wake up.
		let core_id = {
447
			let mut borrowed = task.borrow_mut();
448
449
450
451
452
453
454
455
456
457
			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
			);
458
459
460
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;

461
			borrowed.core_id
462
463
		};

464
		// Get the scheduler of that core.
465
466
		let core_scheduler = scheduler::get_scheduler(core_id);

467
468
		// Add the task to the ready queue.
		let mut state_locked = core_scheduler.state.lock();
469
		state_locked.ready_queue.push(task);
470
471
472

		// Wake up the CPU if needed.
		if state_locked.is_halted {
473
			arch::wakeup_core(core_id);
474
475
476
		}
	}

477
	/// Blocks the given task for `wakeup_time` ticks, or indefinitely if None is given.
478
	pub fn add(&mut self, task: Rc<RefCell<Task>>, wakeup_time: Option<u64>) {
479
480
481
		{
			// Set the task status to Blocked.
			let mut borrowed = task.borrow_mut();
482
			debug!("Blocking task {}", borrowed.id);
483

484
485
486
487
488
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
489
490
			borrowed.status = TaskStatus::TaskBlocked;
		}
491

492
493
494
495
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
496

497
498
499
500
501
502
503
504
505
		// 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);
506

507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
					// 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);
		}
	}

530
531
532
	/// Wakeup all blocked tasks
	pub fn wakeup_all(&mut self) {
		// Loop through all blocked tasks to find it.
533
		for node in self.list.iter() {
534
535
536
537
538
539
			// 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);
		}
	}

540
541
542
543
544
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
570
571
572
	/// 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.
573
		let time = arch::processor::get_timer_ticks();
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591

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