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 spin::RwLock;
20
use synch::spinlock::SpinlockIrqSave;
21
22
23
24
25
26
27
28
29

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

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

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

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

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

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

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
86
87
88
pub const LOW_PRIO: Priority = Priority::from(1);
pub const IDLE_PRIO: Priority = Priority::from(0);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

		None
231
232
233
234
	}

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

		None
242
	}
243
244
245
246

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

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

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

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

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

						break;
					}

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

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

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

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

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

pub struct TaskHeap {
	pub start: usize,
	pub end: usize,
}

308
309
310
311
312
313
314
315
316
317
318
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 {
319
			address: mm::allocate(memory_size, true),
320
			size: memory_size,
321
322
323
324
325
326
327
328
329
		}
	}

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

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

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

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 {
376
377
378
379
380
381
382
	pub fn new(
		tid: TaskId,
		core_id: usize,
		task_status: TaskStatus,
		task_prio: Priority,
		heap_start: Option<usize>,
	) -> Task {
383
		debug!("Creating new task {}", tid);
384
385
386
387
388
389

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
			last_stack_pointer: 0,
390
			last_fpu_state: arch::processor::FPUState::new(),
391
			core_id: core_id,
392
			stacks: TaskStacks::new(),
393
394
			next: None,
			prev: None,
395
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
396
397
398
399
400
401
			heap: heap_start.map(|start| {
				Rc::new(RefCell::new(RwLock::new(TaskHeap {
					start: start,
					end: start,
				})))
			}),
402
			tls: None,
403
			last_wakeup_reason: WakeupReason::Custom,
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
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
421
			heap: None,
422
			tls: None,
423
			last_wakeup_reason: WakeupReason::Custom,
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
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
441
442
			heap: task.heap.clone(),
			tls: task.tls.clone(),
443
			last_wakeup_reason: task.last_wakeup_reason,
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
		// Get the Core ID of the task to wake up.
		let core_id = {
467
			let mut borrowed = task.borrow_mut();
468
469
470
471
472
473
474
475
476
477
			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
			);
478
479
480
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;

481
			borrowed.core_id
482
483
		};

484
		// Get the scheduler of that core.
485
486
		let core_scheduler = scheduler::get_scheduler(core_id);

487
488
		// Add the task to the ready queue.
		let mut state_locked = core_scheduler.state.lock();
489
		state_locked.ready_queue.push(task);
490
491
492

		// Wake up the CPU if needed.
		if state_locked.is_halted {
493
			arch::wakeup_core(core_id);
494
495
496
		}
	}

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

504
505
506
507
508
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
509
510
			borrowed.status = TaskStatus::TaskBlocked;
		}
511

512
513
514
515
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
516

517
518
519
520
521
522
523
524
525
		// 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);
526

527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
					// 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);
		}
	}

550
551
552
	/// Wakeup all blocked tasks
	pub fn wakeup_all(&mut self) {
		// Loop through all blocked tasks to find it.
553
		for node in self.list.iter() {
554
555
556
557
558
559
			// 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);
		}
	}

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
591
592
	/// 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.
593
		let time = arch::processor::get_timer_ticks();
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611

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