lewis.moe
Nothing to see here, move along
1use lancer_core::intrusive_list::ListLinks;
2use lancer_core::run_queue::RunQueueTag;
3use lancer_core::slot_map::{SlotEntry, SlotMap};
4use lancer_core::timer_wheel::{TimerEntryStorage, TimerTag};
5
6use crate::mem::phys::BitmapFrameAllocator;
7use crate::types::{Generation, MAX_PIDS, Pid};
8
9use super::{NONE_SENTINEL, SchedEntity};
10
11const PID_SLOT_SIZE: usize = core::mem::size_of::<SlotEntry<SchedEntity>>();
12const PID_LEAF_ENTRIES: usize = 4096 / PID_SLOT_SIZE;
13const PID_MAX_LEAVES: usize = (MAX_PIDS + PID_LEAF_ENTRIES - 1) / PID_LEAF_ENTRIES;
14
15const _: () = assert!(PID_LEAF_ENTRIES >= 1);
16const _: () = assert!(PID_LEAF_ENTRIES * PID_SLOT_SIZE <= 4096);
17const _: () = assert!(PID_MAX_LEAVES * PID_LEAF_ENTRIES >= MAX_PIDS);
18
19pub struct PidTable {
20 slots: SlotMap<SchedEntity, PID_LEAF_ENTRIES, PID_MAX_LEAVES>,
21}
22
23const _: () = assert!(MAX_PIDS <= NONE_SENTINEL as usize);
24
25impl PidTable {
26 pub const fn empty() -> Self {
27 Self {
28 slots: SlotMap::new(),
29 }
30 }
31
32 pub fn init(&mut self) {
33 crate::kprintln!(
34 " PidTable: max={} pids, {}/leaf, {}/page waste, slot_entry={}B, sched_entity={}B",
35 MAX_PIDS,
36 PID_LEAF_ENTRIES,
37 4096 - PID_LEAF_ENTRIES * PID_SLOT_SIZE,
38 PID_SLOT_SIZE,
39 core::mem::size_of::<SchedEntity>(),
40 );
41 }
42
43 fn try_expand(&mut self, allocator: &BitmapFrameAllocator) -> bool {
44 match self.slots.leaf_count() as usize >= PID_MAX_LEAVES {
45 true => false,
46 false => {
47 let frame = match allocator.allocate_contiguous(1) {
48 Some(f) => f,
49 None => return false,
50 };
51 let virt = crate::mem::addr::phys_to_virt(frame);
52 unsafe {
53 core::ptr::write_bytes(virt.as_mut_ptr::<u8>(), 0, 4096);
54 let leaf = virt.as_mut_ptr::<[SlotEntry<SchedEntity>; PID_LEAF_ENTRIES]>();
55 self.slots.expand(leaf);
56 }
57 true
58 }
59 }
60 }
61
62 pub fn try_reclaim(&mut self) {
63 core::iter::from_fn(|| self.slots.try_reclaim_trailing())
64 .take(PID_MAX_LEAVES)
65 .for_each(|leaf_ptr| {
66 let virt = x86_64::VirtAddr::from_ptr(leaf_ptr);
67 let phys = crate::mem::addr::virt_to_phys(virt)
68 .expect("PidTable leaf not in HHDM");
69 BitmapFrameAllocator::free_frame_by_addr(phys);
70 });
71 }
72
73 pub fn allocate(
74 &mut self,
75 sched: SchedEntity,
76 allocator: &BitmapFrameAllocator,
77 ) -> Option<(Pid, Generation)> {
78 let state = sched.state;
79 let exec_phys = sched.exec_phys;
80 match self.slots.allocate(sched) {
81 Some(result) => self.finish_allocate(result),
82 None => {
83 self.try_expand(allocator);
84 let retry = SchedEntity {
85 state,
86 exec_phys,
87 ..SchedEntity::EMPTY
88 };
89 self.slots.allocate(retry).and_then(|r| self.finish_allocate(r))
90 }
91 }
92 }
93
94 fn finish_allocate(&mut self, (idx, generation): (u32, u32)) -> Option<(Pid, Generation)> {
95 let pid = Pid::try_new(idx)?;
96 let entry = self.slots.get_mut(idx)?;
97 entry.pid = pid;
98 entry.generation = Generation::new(generation);
99 Some((pid, Generation::new(generation)))
100 }
101
102 pub fn free(&mut self, pid: Pid) -> Result<Generation, crate::error::KernelError> {
103 let idx = pid.raw();
104 let generation = self
105 .slots
106 .generation_of(idx)
107 .ok_or(crate::error::KernelError::InvalidObject)?;
108 let freed = self.slots.free(idx, generation)?;
109 Ok(freed.generation)
110 }
111
112 #[cfg(lancer_test)]
113 pub fn count(&self) -> u32 {
114 self.slots.active_count()
115 }
116
117 pub fn get(&self, pid: Pid) -> Option<&SchedEntity> {
118 self.slots.get(pid.raw())
119 }
120
121 pub fn get_mut(&mut self, pid: Pid) -> Option<&mut SchedEntity> {
122 self.slots.get_mut(pid.raw())
123 }
124
125 fn entry(&self, id: u32) -> &SchedEntity {
126 self.slots
127 .get(id)
128 .expect("PidTable::entry: id not active")
129 }
130
131 fn entry_mut(&mut self, id: u32) -> &mut SchedEntity {
132 self.slots
133 .get_mut(id)
134 .expect("PidTable::entry_mut: id not active")
135 }
136
137 pub fn capacity(&self) -> u32 {
138 self.slots.capacity()
139 }
140
141 #[cfg(lancer_test)]
142 pub fn leaf_count(&self) -> u16 {
143 self.slots.leaf_count()
144 }
145}
146
147impl ListLinks<RunQueueTag> for PidTable {
148 fn link_next(&self, id: u32) -> u32 {
149 self.entry(id).run_next
150 }
151 fn link_prev(&self, id: u32) -> u32 {
152 self.entry(id).run_prev
153 }
154 fn set_link_next(&mut self, id: u32, next: u32) {
155 self.entry_mut(id).run_next = next;
156 }
157 fn set_link_prev(&mut self, id: u32, prev: u32) {
158 self.entry_mut(id).run_prev = prev;
159 }
160}
161
162impl ListLinks<TimerTag> for PidTable {
163 fn link_next(&self, id: u32) -> u32 {
164 self.entry(id).timer_next
165 }
166 fn link_prev(&self, id: u32) -> u32 {
167 self.entry(id).timer_prev
168 }
169 fn set_link_next(&mut self, id: u32, next: u32) {
170 self.entry_mut(id).timer_next = next;
171 }
172 fn set_link_prev(&mut self, id: u32, prev: u32) {
173 self.entry_mut(id).timer_prev = prev;
174 }
175}
176
177impl TimerEntryStorage for PidTable {
178 fn tw_slot(&self, id: u32) -> u16 {
179 self.entry(id).timer_slot
180 }
181 fn set_tw_slot(&mut self, id: u32, slot: u16) {
182 self.entry_mut(id).timer_slot = slot;
183 }
184 fn tw_deadline(&self, id: u32) -> u64 {
185 self.entry(id).timer_deadline
186 }
187 fn set_tw_deadline(&mut self, id: u32, deadline: u64) {
188 self.entry_mut(id).timer_deadline = deadline;
189 }
190}