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::rc::Rc;
10
use alloc::vec::Vec;
11
use arch;
12
use arch::mm::paging::{BasePageSize, PageSize};
13
use arch::processor::msb;
14
use arch::scheduler::TaskStacks;
15
use collections::{DoublyLinkedList, Node};
16
use core::cell::RefCell;
17
use core::fmt;
18
use mm;
19
use scheduler;
20
use spin::RwLock;
21
use synch::spinlock::SpinlockIrqSave;
22
23
24
25
26
27
28
29
30

/// The status of the task - used for scheduling
#[derive(Copy, Clone, Debug, Eq, PartialEq)]
pub enum TaskStatus {
	TaskInvalid,
	TaskReady,
	TaskRunning,
	TaskBlocked,
	TaskFinished,
31
	TaskIdle,
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
	All,
40
41
}

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

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

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

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

82
pub const HIGH_PRIO: Priority = Priority::from(3);
Stefan Lankes's avatar
Stefan Lankes committed
83
#[allow(dead_code)]
84
pub const NORMAL_PRIO: Priority = Priority::from(2);
Stefan Lankes's avatar
Stefan Lankes committed
85
#[allow(dead_code)]
86
87
88
89
pub const LOW_PRIO: Priority = Priority::from(1);
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
}

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

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

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

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

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

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

		Task {
			id: tid,
			status: task_status,
			prio: task_prio,
			last_stack_pointer: 0,
393
			last_fpu_state: arch::processor::FPUState::new(),
394
			core_id: core_id,
395
			stacks: TaskStacks::new(),
396
397
			next: None,
			prev: None,
398
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
399
400
401
402
403
404
			heap: heap_start.map(|start| {
				Rc::new(RefCell::new(RwLock::new(TaskHeap {
					start: start,
					end: start,
				})))
			}),
405
			tls: None,
406
			last_wakeup_reason: WakeupReason::Custom,
407
			dtor: Vec::new(),
408
409
410
		}
	}

411
412
	pub fn new_idle(tid: TaskId, core_id: usize) -> Task {
		debug!("Creating idle task {}", tid);
413

414
415
416
		Task {
			id: tid,
			status: TaskStatus::TaskIdle,
417
			prio: IDLE_PRIO,
418
			last_stack_pointer: 0,
419
			last_fpu_state: arch::processor::FPUState::new(),
420
			core_id: core_id,
421
			stacks: TaskStacks::from_boot_stacks(),
422
423
			next: None,
			prev: None,
424
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
425
			heap: None,
426
			tls: None,
427
			last_wakeup_reason: WakeupReason::Custom,
428
			dtor: Vec::new(),
429
430
		}
	}
431

432
433
	pub fn clone(tid: TaskId, core_id: usize, task: &Task) -> Task {
		debug!("Cloning task {} from task {}", tid, task.id);
434
435
436
437
438
439
440
441

		Task {
			id: tid,
			status: TaskStatus::TaskReady,
			prio: task.prio,
			last_stack_pointer: 0,
			last_fpu_state: arch::processor::FPUState::new(),
			core_id: core_id,
442
			stacks: TaskStacks::new(),
443
444
			next: None,
			prev: None,
445
			wakeup: SpinlockIrqSave::new(BlockedTaskQueue::new()),
446
447
			heap: task.heap.clone(),
			tls: task.tls.clone(),
448
			last_wakeup_reason: task.last_wakeup_reason,
449
			dtor: Vec::new(),
450
451
		}
	}
452
453
}

454
455
struct BlockedTask {
	task: Rc<RefCell<Task>>,
456
	wakeup_time: Option<u64>,
457
458
}

459
pub struct BlockedTaskQueue {
460
	list: DoublyLinkedList<BlockedTask>,
461
462
463
464
}

impl BlockedTaskQueue {
	pub const fn new() -> Self {
465
466
467
		Self {
			list: DoublyLinkedList::new(),
		}
468
469
470
	}

	fn wakeup_task(task: Rc<RefCell<Task>>, reason: WakeupReason) {
471
472
		// Get the Core ID of the task to wake up.
		let core_id = {
473
			let mut borrowed = task.borrow_mut();
474
475
476
477
478
479
480
481
482
483
			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
			);
484
485
486
			borrowed.status = TaskStatus::TaskReady;
			borrowed.last_wakeup_reason = reason;

487
			borrowed.core_id
488
489
		};

490
		// Get the scheduler of that core.
491
492
		let core_scheduler = scheduler::get_scheduler(core_id);

493
494
		// Add the task to the ready queue.
		let mut state_locked = core_scheduler.state.lock();
495
		state_locked.ready_queue.push(task);
496
497
498

		// Wake up the CPU if needed.
		if state_locked.is_halted {
499
			arch::wakeup_core(core_id);
500
501
502
		}
	}

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

510
511
512
513
514
			assert!(
				borrowed.status == TaskStatus::TaskRunning,
				"Trying to block task {} which is not running",
				borrowed.id
			);
515
516
			borrowed.status = TaskStatus::TaskBlocked;
		}
517

518
519
520
521
		let new_node = Node::new(BlockedTask {
			task: task,
			wakeup_time: wakeup_time,
		});
522

523
524
525
526
527
528
529
530
531
		// 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);
532

533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
					// 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);
		}
	}

556
557
558
	/// Wakeup all blocked tasks
	pub fn wakeup_all(&mut self) {
		// Loop through all blocked tasks to find it.
559
		for node in self.list.iter() {
560
561
562
563
564
565
			// 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);
		}
	}

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

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