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: &[u64; 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: u64) -> 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 `vm_phys_alloc_pages` on the Orbis for a reference.
101    ///
102    /// # Reference offsets
103    /// | Version | Offset |
104    /// |---------|--------|
105    /// |PS4 11.00|0x160520|
106    pub fn alloc_page(
107        &self,
108        pages: &[Arc<VmPage>],
109        vm: usize,
110        pool: usize,
111        order: usize,
112    ) -> Option<Arc<VmPage>> {
113        // TODO: There is an increasement on unknown variable here.
114        let mut flind = 0;
115
116        loop {
117            let mut l = self.lookup_lists[flind].lock();
118
119            if let Some(v) = self.alloc_freelist(pages, &mut l[vm], pool, order) {
120                return Some(v);
121            }
122
123            flind += 1;
124
125            if flind >= (self.nfree + 1) {
126                break;
127            }
128        }
129
130        None
131    }
132
133    /// See `vm_phys_alloc_freelist_pages` on the Orbis for a reference.
134    ///
135    /// # Reference offsets
136    /// | Version | Offset |
137    /// |---------|--------|
138    /// |PS4 11.00|0x1605D0|
139    fn alloc_freelist(
140        &self,
141        pages: &[Arc<VmPage>],
142        list: &mut [[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3],
143        pool: usize,
144        order: usize,
145    ) -> Option<Arc<VmPage>> {
146        // Beware for deadlock here since we currently own a lock to free queue.
147        if order >= 13 {
148            return None;
149        }
150
151        let mut i = 0;
152
153        loop {
154            match list[pool][order + i].first() {
155                Some(v) => v,
156                None => match (order + i) < 12 {
157                    true => {
158                        i += 1;
159                        continue;
160                    }
161                    false => break,
162                },
163            };
164
165            todo!()
166        }
167
168        let mut next = 11;
169
170        loop {
171            for f in list.iter_mut() {
172                let mut i = next + 1;
173
174                if let Some(p) = f[i].first().cloned() {
175                    let mut po = p.order().lock();
176
177                    f[i].shift_remove(&p);
178                    *po = VmPage::FREE_ORDER;
179
180                    // Set pool.
181                    let end = &pages[p.index() + (1 << i)];
182
183                    for p in &pages[p.index()..end.index()] {
184                        *p.pool().lock() = pool;
185                    }
186
187                    drop(po);
188
189                    while i > order {
190                        i -= 1;
191
192                        let buddy = &pages[p.index() + (1 << i)];
193                        let mut bo = buddy.order().lock();
194
195                        *bo = i;
196
197                        assert!(list[pool][i].shift_insert(0, buddy.clone()));
198                    }
199
200                    return Some(p);
201                }
202            }
203
204            if next < order || next == 0 {
205                break;
206            }
207
208            next -= 1;
209        }
210
211        None
212    }
213
214    /// See `vm_phys_create_seg` on the Orbis for a reference.
215    ///
216    /// # Reference offsets
217    /// | Version | Offset |
218    /// |---------|--------|
219    /// |PS4 11.00|0x15F8A0|
220    fn create_seg(
221        segs: &mut Vec<PhysSeg>,
222        ma: Option<&MemAffinity>,
223        queues: &[Arc<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>; 2],
224        start: u64,
225        end: u64,
226        flind: usize,
227    ) {
228        match ma {
229            Some(_) => todo!(),
230            None => {
231                let mut first_page = 0;
232
233                for s in segs.iter() {
234                    first_page += (s.end - s.start) >> PAGE_SHIFT;
235                }
236
237                segs.push(PhysSeg {
238                    start,
239                    end,
240                    first_page: first_page.try_into().unwrap(),
241                    free_queues: queues[flind].clone(),
242                });
243            }
244        }
245    }
246}
247
248/// Implementation of `vm_phys_seg` structure.
249pub struct PhysSeg {
250    pub start: u64,        // start
251    pub end: u64,          // end
252    pub first_page: usize, // first_page
253    pub free_queues: Arc<Mutex<[[[IndexSet<Arc<VmPage>, FxBuildHasher>; 13]; 3]; 2]>>, // free_queues
254}
obkrnl/vm/phys.rs

obkrnl/vm/
phys.rs
