1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
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

//! The scheduler that coordinates the execution of threads
#![allow(unused)]

use core::cell::UnsafeCell;
use core::ptr;
use core::sync::atomic::AtomicUsize;
use core::sync::atomic::Ordering::Relaxed;

use arraydeque::ArrayDeque;

use super::Thread;
use crate::arch::cpu;
use crate::MAX_CPUS;

pub const APPS: usize = 10;

static mut THREAD_STACKS: [[u32; 0x4000]; APPS] = [[0; 0x4000]; APPS];

/// The scheduler plans the threads' execution order and, from this,
/// selects the next thread to be running.
///
/// The scheduler manages the ready queue,
/// that is the list of threads that are ready to execute. The scheduler
/// arranges threads in a FIFO order, that is, when a thread is set ready, it
/// will be appended to the end of the queue, while threads to be executed are
/// taken from the front of the queue.
pub struct Scheduler {
    /// Ready queue
    ready: ArrayDeque<usize, APPS>,
    /// Contains all threads
    ///
    /// Note: the idle threads have the id and index of their corresponding CPU
    threads: [Option<Thread>; APPS],
    /// Next thread id
    next_id: AtomicUsize,
    /// Per-CPU data
    local: UnsafeCell<[Local; MAX_CPUS]>,
}

/// Private, CPU-local data
#[repr(align(64))]
struct Local {
    /// Active thread (per core)
    active: Option<usize>,
    /// Thread to be removed after dispatch
    exited: Option<usize>,
}

impl Scheduler {
    /// Construct the scheduler.
    pub const fn new() -> Self {
        Self {
            ready: ArrayDeque::new(),
            threads: [const { None }; APPS],
            next_id: AtomicUsize::new(MAX_CPUS),
            local: UnsafeCell::new(
                [const {
                    Local {
                        active: None,
                        exited: None,
                    }
                }; MAX_CPUS],
            ),
        }
    }

    /// Access local data for the current CPU.
    fn local(&self) -> &mut Local {
        // TODO: You better check if this is safe! So when can this be accessed?
        &mut (unsafe { &mut *self.local.get() })[cpu::id()]
    }

    /// Add and ready a new thread to the scheduler.
    pub fn add(&mut self, mut _thread: Thread) -> usize {
        let id = self.next_id.fetch_add(1, Relaxed);
        // TODO: BSB A4 - Initialize thread
        id
    }

    /// Include a thread in scheduling decisions.
    ///
    /// This method will register a thread for scheduling. It will be appended
    /// to the ready queue and dispatched once its time has come.
    ///
    /// Note: New threads have to be added first with [Scheduler::add].
    pub fn ready(&mut self, thread: usize) {
        assert!(self.threads[thread].is_some());

        todo!("BSB A4")
    }

    /// Returns the thread that currently runs on this CPU.
    pub fn active(&self) -> Option<usize> {
        self.local().active
    }

    /// Returns the CPU where the thread is currently running.
    pub fn is_active(&self, thread: usize) -> Option<usize> {
        let locals = unsafe { &*self.local.get() };
        cpu::iter().find(|&cpu| locals[cpu].active == Some(thread))
    }

    /// Returns a reference to the thread with the given id.
    pub fn thread(&self, thread: usize) -> Option<&Thread> {
        self.threads[thread].as_ref()
    }
    /// Returns a reference to the thread with the given id.
    pub fn thread_mut(&mut self, thread: usize) -> Option<&mut Thread> {
        self.threads[thread].as_mut()
    }

    /// Start the scheduling.
    /// This function does not return.
    pub fn schedule(&mut self) -> ! {
        todo!("BSB A4")

        // TODO: BSB A6 - Initialize own idle thread
    }

    /// Initiates a thread switch.
    /// This function returns then in the context of the next thread.
    ///
    /// If `ready`, the currently running thread is added back to the ready list.
    pub fn resume(&mut self, ready: bool) {
        todo!("BSB A4")
    }

    /// Terminates the currently running thread, directly continue with the next one.
    pub fn exit(&mut self) -> ! {
        todo!("BSB A4")
    }

    /// Terminates `t`, which might be running on another CPU.
    pub fn kill(&mut self, thread: usize) -> bool {
        todo!("BSB A5")
    }

    /// Updates the life pointer to next and issues a thread change from
    /// the old to the new life pointer.
    fn dispatch(&mut self, next: usize) {
        let previous = if let Some(previous) = self.local().active.replace(next) {
            // Usually we cannot have two mutable references, but I'm sure its ok here
            // -> Lifetime hack: cast it into a pointer and dereference it again
            Some(unsafe { &mut *ptr::from_mut(self.thread_mut(previous).unwrap()) })
        } else {
            None
        };

        todo!("BSB A4")
    }

    /// Helper to retrieve next Thread.
    fn next(&mut self) -> usize {
        todo!("BSB A4")
    }

    /// Action of the idle thread.
    pub extern "C" fn idle_action() -> ! {
        todo!("BSB A6")
    }
}