obkrnl/vm/
phys.rs

1use super::{MemAffinity, VmPage};
2use crate::config::PAGE_SHIFT;
3use crate::lock::Mutex;
4use alloc::sync::Arc;
5use alloc::vec::Vec;
6use indexmap::IndexSet;
7use rustc_hash::FxBuildHasher;
8
9/// Provides methods to allocate physical memory.
10pub struct PhysAllocator {
11    segs: Vec<PhysSeg>, // vm_phys_segs + vm_phys_nsegs
12    nfree: usize,       // vm_nfreelists
13    lookup_lists: [Arc<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>; 2], // vm_phys_lookup_lists
14}
15
16impl PhysAllocator {
17    /// See `vm_phys_init` on the Orbis for a reference.
18    ///
19    /// # Reference offsets
20    /// | Version | Offset |
21    /// |---------|--------|
22    /// |PS4 11.00|0x15F410|
23    pub fn new(phys_avail: &[usize; 61], ma: Option<&MemAffinity>) -> Self {
24        // Populate vm_phys_free_queues. Do not use Clone to construct the array here since it will
25        // refer to the same object. The Orbis do this after segments creation but we do it before
26        // instead.
27        let free_queues = [
28            Arc::<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>::default(),
29            Arc::<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>::default(),
30        ];
31
32        // Create segments.
33        let mut segs = Vec::new();
34        let mut nfree = 0;
35
36        for i in (0..).step_by(2) {
37            // Check if end entry.
38            let mut addr = phys_avail[i];
39            let end = phys_avail[i + 1];
40
41            if end == 0 {
42                break;
43            }
44
45            // TODO: Why Orbis need to create 16MB segment here?
46            if addr < 16777216 {
47                let unk = end < 0x1000001;
48
49                if !unk {
50                    Self::create_seg(&mut segs, ma, &free_queues, addr, 0x1000000, 1);
51
52                    // The Orbis also update end address here but it seems like the value is always
53                    // the same as current value.
54                    addr = 0x1000000;
55                }
56
57                Self::create_seg(&mut segs, ma, &free_queues, addr, end, unk.into());
58
59                nfree = 1;
60            } else {
61                Self::create_seg(&mut segs, ma, &free_queues, addr, end, 0);
62            }
63        }
64
65        // Populate vm_phys_lookup_lists.
66        let lookup_lists = [free_queues[0].clone(), free_queues[1].clone()];
67
68        Self {
69            segs,
70            nfree,
71            lookup_lists,
72        }
73    }
74
75    /// # Panics
76    /// If `i` is not valid.
77    pub fn segment(&self, i: usize) -> &PhysSeg {
78        &self.segs[i]
79    }
80
81    /// See `vm_phys_paddr_to_segind` on the Orbis for a reference. Our implementation is a bit
82    /// differences here. Orbis will panic if segment not found but we return [None] instead.
83    ///
84    /// # Reference offsets
85    /// | Version | Offset |
86    /// |---------|--------|
87    /// |PS4 11.00|0x15FC40|
88    pub fn segment_index(&self, pa: usize) -> Option<usize> {
89        for (i, s) in self.segs.iter().enumerate() {
90            if pa < s.start || pa >= s.end {
91                continue;
92            }
93
94            return Some(i);
95        }
96
97        None
98    }
99
100    /// See `PHYS_TO_VM_PAGE` on the Orbis for a reference.
101    ///
102    /// # Reference offsets
103    /// | Version | Offset |
104    /// |---------|--------|
105    /// |PS4 11.00|0x15FBF0|
106    pub fn phys_to_page<'a>(&self, pages: &'a [Arc<VmPage>], pa: usize) -> Option<&'a Arc<VmPage>> {
107        for s in self.segs.iter() {
108            if pa < s.start || pa >= s.end {
109                continue;
110            }
111
112            return Some(&pages[s.first_page + ((pa - s.start) >> PAGE_SHIFT)]);
113        }
114
115        None
116    }
117
118    /// See `vm_phys_alloc_pages` on the Orbis for a reference.
119    ///
120    /// # Reference offsets
121    /// | Version | Offset |
122    /// |---------|--------|
123    /// |PS4 11.00|0x160520|
124    pub fn alloc_page(
125        &self,
126        pages: &[Arc<VmPage>],
127        vm: usize,
128        pool: usize,
129        order: usize,
130    ) -> Option<Arc<VmPage>> {
131        // TODO: There is an increasement on unknown variable here.
132        let mut flind = 0;
133
134        loop {
135            let mut l = self.lookup_lists[flind].lock();
136
137            if let Some(v) = Self::alloc_freelist(pages, &mut l[vm], pool, order) {
138                return Some(v);
139            }
140
141            flind += 1;
142
143            if flind >= (self.nfree + 1) {
144                break;
145            }
146        }
147
148        None
149    }
150
151    /// See `vm_phys_alloc_freelist_pages` on the Orbis for a reference.
152    ///
153    /// # Reference offsets
154    /// | Version | Offset |
155    /// |---------|--------|
156    /// |PS4 11.00|0x1605D0|
157    fn alloc_freelist(
158        pages: &[Arc<VmPage>],
159        list: &mut [[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3],
160        pool: usize,
161        order: usize,
162    ) -> Option<Arc<VmPage>> {
163        // Beware for deadlock here since we currently own a lock to free queue.
164        if order >= 13 {
165            return None;
166        }
167
168        // TODO: What is this?
169        let mut i = 0;
170
171        loop {
172            let p = match list[pool][order + i].first() {
173                Some(v) => v.clone(),
174                None => match (order + i) < 12 {
175                    true => {
176                        i += 1;
177                        continue;
178                    }
179                    false => break,
180                },
181            };
182
183            // Remove from queue.
184            let mut ps = p.state.lock();
185
186            list[pool][order + i].shift_remove(&p);
187
188            ps.order = VmPage::FREE_ORDER;
189
190            drop(ps);
191
192            // TODO: Verify if the inlined call here is actually vm_phys_split_pages.
193            Self::split_pages(pages, &mut list[pool], &p, order + i, order);
194
195            return Some(p);
196        }
197
198        // TODO: What is this?
199        let mut next = 11;
200
201        loop {
202            for f in list.iter_mut() {
203                let i = next + 1;
204
205                if let Some(p) = f[i].first().cloned() {
206                    // Remove from queue.
207                    let mut ps = p.state.lock();
208
209                    f[i].shift_remove(&p);
210
211                    ps.pool = pool;
212                    ps.order = VmPage::FREE_ORDER;
213
214                    drop(ps);
215
216                    // Set buddy pool.
217                    let end = &pages[p.index + (1 << i)];
218
219                    for p in &pages[(p.index + 1)..end.index] {
220                        p.state.lock().pool = pool;
221                    }
222
223                    Self::split_pages(pages, &mut list[pool], &p, i, order);
224
225                    return Some(p);
226                }
227            }
228
229            if next < order || next == 0 {
230                break;
231            }
232
233            next -= 1;
234        }
235
236        None
237    }
238
239    /// See `vm_phys_split_pages` on the Orbis for a reference.
240    ///
241    /// # Reference offsets
242    /// | Version | Offset |
243    /// |---------|--------|
244    /// |PS4 11.00|0x1607E5|
245    fn split_pages(
246        pages: &[Arc<VmPage>],
247        list: &mut [IndexSet<Arc<VmPage>, FxBuildHasher>; 13],
248        p: &VmPage,
249        mut i: usize,
250        order: usize,
251    ) {
252        while i > order {
253            i -= 1;
254
255            // TODO: What is this?
256            let buddy = &pages[p.index + (1 << i)];
257            let mut ps = buddy.state.lock();
258
259            ps.order = i;
260
261            assert!(list[i].shift_insert(0, buddy.clone()));
262        }
263    }
264
265    /// See `vm_phys_create_seg` on the Orbis for a reference.
266    ///
267    /// # Reference offsets
268    /// | Version | Offset |
269    /// |---------|--------|
270    /// |PS4 11.00|0x15F8A0|
271    fn create_seg(
272        segs: &mut Vec<PhysSeg>,
273        ma: Option<&MemAffinity>,
274        queues: &[Arc<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>; 2],
275        start: usize,
276        end: usize,
277        flind: usize,
278    ) {
279        match ma {
280            Some(_) => todo!(),
281            None => {
282                let mut first_page = 0;
283
284                for s in segs.iter() {
285                    first_page += (s.end - s.start) >> PAGE_SHIFT;
286                }
287
288                segs.push(PhysSeg {
289                    start,
290                    end,
291                    first_page,
292                    free_queues: queues[flind].clone(),
293                });
294            }
295        }
296    }
297}
298
299/// Implementation of `vm_phys_seg` structure.
300pub struct PhysSeg {
301    pub start: usize,      // start
302    pub end: usize,        // end
303    pub first_page: usize, // first_page
304    pub free_queues: Arc<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>, // free_queues
305}
obkrnl/vm/phys.rs

obkrnl/vm/
phys.rs
