xref: /DragonOS/kernel/src/mm/mmio_buddy.rs (revision 676b8ef62e1a0a1e52d65b40c53c1636a2954040)
1a7eb62a4Shoumkh use crate::libs::spinlock::{SpinLock, SpinLockGuard};
2*676b8ef6SMork use crate::syscall::SystemError;
3c2481452Shoumkh use crate::{
4c2481452Shoumkh     arch::asm::current::current_pcb,
5c2481452Shoumkh     include::bindings::bindings::{
6c2481452Shoumkh         initial_mm, mm_create_vma, mm_unmap, vm_area_del, vm_area_free, vm_area_struct, vm_flags_t,
7*676b8ef6SMork         vma_find, MMIO_BASE, MMIO_TOP, PAGE_1G_SHIFT, PAGE_1G_SIZE,
8c2481452Shoumkh         PAGE_2M_SIZE, PAGE_4K_SHIFT, PAGE_4K_SIZE, VM_DONTCOPY, VM_IO,
9c2481452Shoumkh     },
10c2481452Shoumkh     kdebug, kerror,
11c2481452Shoumkh };
12c2481452Shoumkh use alloc::{boxed::Box, collections::LinkedList, vec::Vec};
13c2481452Shoumkh use core::{mem, ptr::null_mut};
14c2481452Shoumkh 
15c2481452Shoumkh // 最大的伙伴块的幂
16c2481452Shoumkh const MMIO_BUDDY_MAX_EXP: u32 = PAGE_1G_SHIFT;
17c2481452Shoumkh // 最小的伙伴块的幂
18c2481452Shoumkh const MMIO_BUDDY_MIN_EXP: u32 = PAGE_4K_SHIFT;
19c2481452Shoumkh // 内存池数组的范围
20c2481452Shoumkh const MMIO_BUDDY_REGION_COUNT: u32 = MMIO_BUDDY_MAX_EXP - MMIO_BUDDY_MIN_EXP + 1;
21c2481452Shoumkh 
22c2481452Shoumkh lazy_static! {
23c2481452Shoumkh     pub static ref MMIO_POOL: MmioBuddyMemPool = MmioBuddyMemPool::new();
24c2481452Shoumkh }
25c2481452Shoumkh 
26c2481452Shoumkh pub enum MmioResult {
27c2481452Shoumkh     SUCCESS,
28c2481452Shoumkh     EINVAL,
29c2481452Shoumkh     ENOFOUND,
30c2481452Shoumkh     WRONGEXP,
31c2481452Shoumkh     ISEMPTY,
32c2481452Shoumkh }
33c2481452Shoumkh 
34c2481452Shoumkh /// @brief buddy内存池
35c2481452Shoumkh pub struct MmioBuddyMemPool {
36c2481452Shoumkh     pool_start_addr: u64,
37c2481452Shoumkh     pool_size: u64,
38c2481452Shoumkh     free_regions: [SpinLock<MmioFreeRegionList>; MMIO_BUDDY_REGION_COUNT as usize],
39c2481452Shoumkh }
40c2481452Shoumkh impl Default for MmioBuddyMemPool {
41c2481452Shoumkh     fn default() -> Self {
42c2481452Shoumkh         MmioBuddyMemPool {
43c2481452Shoumkh             pool_start_addr: MMIO_BASE as u64,
44c2481452Shoumkh             pool_size: (MMIO_TOP - MMIO_BASE) as u64,
45c2481452Shoumkh             free_regions: unsafe { mem::zeroed() },
46c2481452Shoumkh         }
47c2481452Shoumkh     }
48c2481452Shoumkh }
49c2481452Shoumkh impl MmioBuddyMemPool {
50c2481452Shoumkh     fn new() -> Self {
51c2481452Shoumkh         return MmioBuddyMemPool {
52c2481452Shoumkh             ..Default::default()
53c2481452Shoumkh         };
54c2481452Shoumkh     }
55c2481452Shoumkh 
56c2481452Shoumkh     /// @brief 创建新的地址区域结构体
57c2481452Shoumkh     ///
58c2481452Shoumkh     /// @param vaddr 虚拟地址
59c2481452Shoumkh     ///
60c2481452Shoumkh     /// @return 创建好的地址区域结构体
61a7eb62a4Shoumkh     fn create_region(&self, vaddr: u64) -> Box<MmioBuddyAddrRegion> {
62c2481452Shoumkh         let mut region: Box<MmioBuddyAddrRegion> = Box::new(MmioBuddyAddrRegion::new());
63c2481452Shoumkh         region.vaddr = vaddr;
64c2481452Shoumkh         return region;
65c2481452Shoumkh     }
66c2481452Shoumkh 
67c2481452Shoumkh     /// @brief 将内存块归还给buddy
68c2481452Shoumkh     ///
69c2481452Shoumkh     /// @param vaddr 虚拟地址
70c2481452Shoumkh     ///
71c2481452Shoumkh     /// @param exp 内存空间的大小(2^exp)
72c2481452Shoumkh     ///
73c2481452Shoumkh     /// @param list_guard 【exp】对应的链表
74c2481452Shoumkh     ///
75c2481452Shoumkh     /// @return Ok(i32) 返回0
76c2481452Shoumkh     ///
77*676b8ef6SMork     /// @return Err(SystemError) 返回错误码
78*676b8ef6SMork     fn give_back_block(&self, vaddr: u64, exp: u32) -> Result<i32, SystemError> {
79c2481452Shoumkh         // 确保内存对齐,低位都要为0
80c2481452Shoumkh         if (vaddr & ((1 << exp) - 1)) != 0 {
81*676b8ef6SMork             return Err(SystemError::EINVAL);
82c2481452Shoumkh         }
83a7eb62a4Shoumkh         let region: Box<MmioBuddyAddrRegion> = self.create_region(vaddr);
84c2481452Shoumkh         // 加入buddy
85c2481452Shoumkh         let list_guard: &mut SpinLockGuard<MmioFreeRegionList> =
86a7eb62a4Shoumkh             &mut self.free_regions[exp2index(exp)].lock();
87a7eb62a4Shoumkh         self.push_block(region, list_guard);
88c2481452Shoumkh         return Ok(0);
89c2481452Shoumkh     }
90c2481452Shoumkh 
91c2481452Shoumkh     /// @brief 将给定大小为2^{exp}的内存块一分为二,并插入内存块大小为2^{exp-1}的链表中
92c2481452Shoumkh     ///
93c2481452Shoumkh     /// @param region 要被分割的地址区域结构体(保证其已经从链表中取出)
94c2481452Shoumkh     ///
95c2481452Shoumkh     /// @param exp 要被分割的地址区域的大小的幂
96c2481452Shoumkh     ///
97c2481452Shoumkh     /// @param list_guard 【exp-1】对应的链表
98a7eb62a4Shoumkh     fn split_block(
99c2481452Shoumkh         &self,
100c2481452Shoumkh         region: Box<MmioBuddyAddrRegion>,
101c2481452Shoumkh         exp: u32,
102c2481452Shoumkh         low_list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
103c2481452Shoumkh     ) {
104a7eb62a4Shoumkh         let vaddr: u64 = self.calculate_block_vaddr(region.vaddr, exp - 1);
105a7eb62a4Shoumkh         let new_region: Box<MmioBuddyAddrRegion> = self.create_region(vaddr);
106a7eb62a4Shoumkh         self.push_block(region, low_list_guard);
107a7eb62a4Shoumkh         self.push_block(new_region, low_list_guard);
108c2481452Shoumkh     }
109c2481452Shoumkh 
110c2481452Shoumkh     /// @brief 从buddy中申请一块指定大小的内存区域
111c2481452Shoumkh     ///
112c2481452Shoumkh     /// @param exp 要申请的内存块的大小的幂(2^exp)
113c2481452Shoumkh     ///
114c2481452Shoumkh     /// @param list_guard exp对应的链表
115c2481452Shoumkh     ///
116c2481452Shoumkh     /// @return Ok(Box<MmioBuddyAddrRegion>) 符合要求的内存区域。
117c2481452Shoumkh     ///
118c2481452Shoumkh     /// @return Err(MmioResult)
119c2481452Shoumkh     /// - 没有满足要求的内存块时,返回ENOFOUND
120c2481452Shoumkh     /// - 申请的内存块大小超过合法范围,返回WRONGEXP
121c2481452Shoumkh     /// - 调用函数出错时,返回出错函数对应错误码
122a7eb62a4Shoumkh     fn query_addr_region(
123c2481452Shoumkh         &self,
124c2481452Shoumkh         exp: u32,
125c2481452Shoumkh         list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
126c2481452Shoumkh     ) -> Result<Box<MmioBuddyAddrRegion>, MmioResult> {
127c2481452Shoumkh         // 申请范围错误
128c2481452Shoumkh         if exp < MMIO_BUDDY_MIN_EXP || exp > MMIO_BUDDY_MAX_EXP {
129a7eb62a4Shoumkh             kdebug!("query_addr_region: exp wrong");
130c2481452Shoumkh             return Err(MmioResult::WRONGEXP);
131c2481452Shoumkh         }
132c2481452Shoumkh         // 没有恰好符合要求的内存块
133c2481452Shoumkh         // 注意:exp对应的链表list_guard已上锁【注意避免死锁问题】
134c2481452Shoumkh         if list_guard.num_free == 0 {
135c2481452Shoumkh             // 找到最小符合申请范围的内存块
136c2481452Shoumkh             // 将大的内存块依次分成小块内存,直到能够满足exp大小,即将exp+1分成两块exp
137c2481452Shoumkh             for e in exp + 1..MMIO_BUDDY_MAX_EXP + 1 {
138ef9f9732Shoumkh                 let pop_list: &mut SpinLockGuard<MmioFreeRegionList> =
139ef9f9732Shoumkh                     &mut self.free_regions[exp2index(e) as usize].lock();
140ef9f9732Shoumkh                 if pop_list.num_free == 0 {
141c2481452Shoumkh                     continue;
142c2481452Shoumkh                 }
143ef9f9732Shoumkh 
144c2481452Shoumkh                 for e2 in (exp + 1..e + 1).rev() {
145ef9f9732Shoumkh                     if e2 == e {
146ef9f9732Shoumkh                         match self.pop_block(pop_list) {
147ef9f9732Shoumkh                             Ok(region) => {
148ef9f9732Shoumkh                                 if e2 != exp + 1 {
149ef9f9732Shoumkh                                     // 要将分裂后的内存块插入到更小的链表中
150ef9f9732Shoumkh                                     let low_list_guard: &mut SpinLockGuard<MmioFreeRegionList> =
151ef9f9732Shoumkh                                         &mut self.free_regions[exp2index(e2 - 1) as usize].lock();
152ef9f9732Shoumkh                                     self.split_block(region, e2, low_list_guard);
153ef9f9732Shoumkh                                 } else {
154ef9f9732Shoumkh                                     // 由于exp对应的链表list_guard已经被锁住了 不能再加锁
155ef9f9732Shoumkh                                     // 所以直接将list_guard传入
156ef9f9732Shoumkh                                     self.split_block(region, e2, list_guard);
157ef9f9732Shoumkh                                 }
158ef9f9732Shoumkh                             }
159ef9f9732Shoumkh                             Err(err) => {
160ef9f9732Shoumkh                                 kdebug!("buddy_pop_region get wrong");
161ef9f9732Shoumkh                                 return Err(err);
162ef9f9732Shoumkh                             }
163ef9f9732Shoumkh                         }
164ef9f9732Shoumkh                     } else {
165ef9f9732Shoumkh                         match self.pop_block(&mut self.free_regions[exp2index(e2) as usize].lock())
166ef9f9732Shoumkh                         {
167c2481452Shoumkh                             Ok(region) => {
168c2481452Shoumkh                                 if e2 != exp + 1 {
169c2481452Shoumkh                                     // 要将分裂后的内存块插入到更小的链表中
170c2481452Shoumkh                                     let low_list_guard: &mut SpinLockGuard<MmioFreeRegionList> =
171a7eb62a4Shoumkh                                         &mut self.free_regions[exp2index(e2 - 1) as usize].lock();
172a7eb62a4Shoumkh                                     self.split_block(region, e2, low_list_guard);
173c2481452Shoumkh                                 } else {
174c2481452Shoumkh                                     // 由于exp对应的链表list_guard已经被锁住了 不能再加锁
175c2481452Shoumkh                                     // 所以直接将list_guard传入
176a7eb62a4Shoumkh                                     self.split_block(region, e2, list_guard);
177c2481452Shoumkh                                 }
178c2481452Shoumkh                             }
179c2481452Shoumkh                             Err(err) => {
180c2481452Shoumkh                                 kdebug!("buddy_pop_region get wrong");
181c2481452Shoumkh                                 return Err(err);
182c2481452Shoumkh                             }
183c2481452Shoumkh                         }
184c2481452Shoumkh                     }
185ef9f9732Shoumkh                 }
186c2481452Shoumkh                 break;
187c2481452Shoumkh             }
188c2481452Shoumkh             // 判断是否获得了exp大小的内存块
189c2481452Shoumkh             if list_guard.num_free > 0 {
190ef9f9732Shoumkh                 match self.pop_block(list_guard) {
191ef9f9732Shoumkh                     Ok(ret) => return Ok(ret),
192ef9f9732Shoumkh                     Err(err) => return Err(err),
193ef9f9732Shoumkh                 }
194c2481452Shoumkh             }
195c2481452Shoumkh             // 拆分大内存块无法获得exp大小内存块
196c2481452Shoumkh             // 尝试用小内存块合成
197c2481452Shoumkh             // 即将两块exp合成一块exp+1
198ef9f9732Shoumkh 
199ef9f9732Shoumkh             // TODO:修改下一个循环的冗余代码,请不要删除此处的注释
200ef9f9732Shoumkh             // let merge = |high_list_guard: &mut SpinLockGuard<MmioFreeRegionList>, exp: u32| {
201ef9f9732Shoumkh             //     if let Err(err) = self.merge_all_exp(
202ef9f9732Shoumkh             //         exp,
203ef9f9732Shoumkh             //         &mut self.free_regions[exp2index(exp) as usize].lock(),
204ef9f9732Shoumkh             //         high_list_guard,
205ef9f9732Shoumkh             //     ) {
206ef9f9732Shoumkh             //         return err;
207ef9f9732Shoumkh             //     } else {
208ef9f9732Shoumkh             //         return MmioResult::SUCCESS;
209ef9f9732Shoumkh             //     }
210ef9f9732Shoumkh             // };
211c2481452Shoumkh             for e in MMIO_BUDDY_MIN_EXP..exp {
212c2481452Shoumkh                 if e != exp - 1 {
213a7eb62a4Shoumkh                     match self.merge_all_exp(
214ef9f9732Shoumkh                         exp,
215ef9f9732Shoumkh                         &mut self.free_regions[exp2index(exp) as usize].lock(),
216ef9f9732Shoumkh                         &mut self.free_regions[exp2index(exp + 1)].lock(),
217c2481452Shoumkh                     ) {
218c2481452Shoumkh                         Ok(_) => continue,
219c2481452Shoumkh                         Err(err) => {
220ef9f9732Shoumkh                             kdebug!("merge_all_exp get wrong");
221c2481452Shoumkh                             return Err(err);
222c2481452Shoumkh                         }
223c2481452Shoumkh                     }
224c2481452Shoumkh                 } else {
225a7eb62a4Shoumkh                     match self.merge_all_exp(
226ef9f9732Shoumkh                         exp,
227ef9f9732Shoumkh                         &mut self.free_regions[exp2index(exp) as usize].lock(),
228c2481452Shoumkh                         list_guard,
229c2481452Shoumkh                     ) {
230c2481452Shoumkh                         Ok(_) => continue,
231c2481452Shoumkh                         Err(err) => {
232ef9f9732Shoumkh                             kdebug!("merge_all_exp get wrong");
233c2481452Shoumkh                             return Err(err);
234c2481452Shoumkh                         }
235c2481452Shoumkh                     }
236c2481452Shoumkh                 }
237c2481452Shoumkh             }
238c2481452Shoumkh 
239c2481452Shoumkh             //判断是否获得了exp大小的内存块
240c2481452Shoumkh             if list_guard.num_free > 0 {
241ef9f9732Shoumkh                 match self.pop_block(list_guard) {
242ef9f9732Shoumkh                     Ok(ret) => return Ok(ret),
243ef9f9732Shoumkh                     Err(err) => return Err(err),
244ef9f9732Shoumkh                 }
245c2481452Shoumkh             }
246c2481452Shoumkh             return Err(MmioResult::ENOFOUND);
247c2481452Shoumkh         } else {
248ef9f9732Shoumkh             match self.pop_block(list_guard) {
249ef9f9732Shoumkh                 Ok(ret) => return Ok(ret),
250ef9f9732Shoumkh                 Err(err) => return Err(err),
251ef9f9732Shoumkh             }
252c2481452Shoumkh         }
253c2481452Shoumkh     }
254c2481452Shoumkh 
255c2481452Shoumkh     /// @brief 对query_addr_region进行封装
256c2481452Shoumkh     ///
257c2481452Shoumkh     /// @param exp 内存区域的大小(2^exp)
258c2481452Shoumkh     ///
259c2481452Shoumkh     /// @return Ok(Box<MmioBuddyAddrRegion>)符合要求的内存块信息结构体。
260c2481452Shoumkh     /// @return Err(MmioResult) 没有满足要求的内存块时,返回__query_addr_region的错误码。
261c2481452Shoumkh     fn mmio_buddy_query_addr_region(
262c2481452Shoumkh         &self,
263c2481452Shoumkh         exp: u32,
264c2481452Shoumkh     ) -> Result<Box<MmioBuddyAddrRegion>, MmioResult> {
265c2481452Shoumkh         let list_guard: &mut SpinLockGuard<MmioFreeRegionList> =
266a7eb62a4Shoumkh             &mut self.free_regions[exp2index(exp)].lock();
267a7eb62a4Shoumkh         match self.query_addr_region(exp, list_guard) {
268c2481452Shoumkh             Ok(ret) => return Ok(ret),
269c2481452Shoumkh             Err(err) => {
270c2481452Shoumkh                 kdebug!("mmio_buddy_query_addr_region failed");
271c2481452Shoumkh                 return Err(err);
272c2481452Shoumkh             }
273c2481452Shoumkh         }
274c2481452Shoumkh     }
275c2481452Shoumkh     /// @brief 往指定的地址空间链表中添加一个地址区域
276c2481452Shoumkh     ///
277c2481452Shoumkh     /// @param region 要被添加的地址结构体
278c2481452Shoumkh     ///
279c2481452Shoumkh     /// @param list_guard 目标链表
280a7eb62a4Shoumkh     fn push_block(
281c2481452Shoumkh         &self,
282c2481452Shoumkh         region: Box<MmioBuddyAddrRegion>,
283c2481452Shoumkh         list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
284c2481452Shoumkh     ) {
285c2481452Shoumkh         list_guard.list.push_back(region);
286c2481452Shoumkh         list_guard.num_free += 1;
287c2481452Shoumkh     }
288c2481452Shoumkh 
289c2481452Shoumkh     /// @brief 根据地址和内存块大小,计算伙伴块虚拟内存的地址
290c2481452Shoumkh     #[inline(always)]
291a7eb62a4Shoumkh     fn calculate_block_vaddr(&self, vaddr: u64, exp: u32) -> u64 {
292c2481452Shoumkh         return vaddr ^ (1 << exp);
293c2481452Shoumkh     }
294c2481452Shoumkh 
295c2481452Shoumkh     /// @brief 寻找并弹出指定内存块的伙伴块
296c2481452Shoumkh     ///
297c2481452Shoumkh     /// @param region 对应内存块的信息
298c2481452Shoumkh     ///
299c2481452Shoumkh     /// @param exp 内存块大小
300c2481452Shoumkh     ///
301c2481452Shoumkh     /// @param list_guard 【exp】对应的链表
302c2481452Shoumkh     ///
303c2481452Shoumkh     /// @return Ok(Box<MmioBuddyAddrRegion) 返回伙伴块的引用
304c2481452Shoumkh     /// @return Err(MmioResult)
305c2481452Shoumkh     /// - 当链表为空,返回ISEMPTY
306c2481452Shoumkh     /// - 没有找到伙伴块,返回ENOFOUND
307a7eb62a4Shoumkh     fn pop_buddy_block(
308c2481452Shoumkh         &self,
309c2481452Shoumkh         vaddr: u64,
310c2481452Shoumkh         exp: u32,
311c2481452Shoumkh         list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
312c2481452Shoumkh     ) -> Result<Box<MmioBuddyAddrRegion>, MmioResult> {
313c2481452Shoumkh         if list_guard.list.len() == 0 {
314c2481452Shoumkh             return Err(MmioResult::ISEMPTY);
315c2481452Shoumkh         } else {
316c2481452Shoumkh             //计算伙伴块的地址
317a7eb62a4Shoumkh             let buddy_vaddr = self.calculate_block_vaddr(vaddr, exp);
318c2481452Shoumkh 
319c2481452Shoumkh             // element 只会有一个元素
320c2481452Shoumkh             let mut element: Vec<Box<MmioBuddyAddrRegion>> = list_guard
321c2481452Shoumkh                 .list
322c2481452Shoumkh                 .drain_filter(|x| x.vaddr == buddy_vaddr)
323c2481452Shoumkh                 .collect();
324c2481452Shoumkh             if element.len() == 1 {
325c2481452Shoumkh                 list_guard.num_free -= 1;
326c2481452Shoumkh                 return Ok(element.pop().unwrap());
327c2481452Shoumkh             }
328c2481452Shoumkh 
329c2481452Shoumkh             //没有找到对应的伙伴块
330c2481452Shoumkh             return Err(MmioResult::ENOFOUND);
331c2481452Shoumkh         }
332c2481452Shoumkh     }
333c2481452Shoumkh 
334c2481452Shoumkh     /// @brief 从指定空闲链表中取出内存区域
335c2481452Shoumkh     ///
336c2481452Shoumkh     /// @param list_guard 【exp】对应的链表
337c2481452Shoumkh     ///
338c2481452Shoumkh     /// @return Ok(Box<MmioBuddyAddrRegion>) 内存块信息结构体的引用。
339c2481452Shoumkh     ///
340c2481452Shoumkh     /// @return Err(MmioResult) 当链表为空,无法删除时,返回ISEMPTY
341a7eb62a4Shoumkh     fn pop_block(
342c2481452Shoumkh         &self,
343c2481452Shoumkh         list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
344c2481452Shoumkh     ) -> Result<Box<MmioBuddyAddrRegion>, MmioResult> {
345c2481452Shoumkh         if !list_guard.list.is_empty() {
346c2481452Shoumkh             list_guard.num_free -= 1;
347c2481452Shoumkh             return Ok(list_guard.list.pop_back().unwrap());
348c2481452Shoumkh         }
349c2481452Shoumkh         return Err(MmioResult::ISEMPTY);
350c2481452Shoumkh     }
351c2481452Shoumkh 
352c2481452Shoumkh     /// @brief 合并所有2^{exp}大小的内存块
353c2481452Shoumkh     ///
354c2481452Shoumkh     /// @param exp 内存块大小的幂(2^exp)
355c2481452Shoumkh     ///
356c2481452Shoumkh     /// @param list_guard exp对应的链表
357c2481452Shoumkh     ///
358c2481452Shoumkh     /// @param high_list_guard exp+1对应的链表
359c2481452Shoumkh     ///
360c2481452Shoumkh     /// @return Ok(MmioResult) 合并成功返回SUCCESS
361c2481452Shoumkh     /// @return Err(MmioResult)
362c2481452Shoumkh     /// - 内存块过少,无法合并,返回EINVAL
363a7eb62a4Shoumkh     /// - pop_buddy_block调用出错,返回其错误码
364a7eb62a4Shoumkh     /// - merge_blocks调用出错,返回其错误码
365a7eb62a4Shoumkh     fn merge_all_exp(
366c2481452Shoumkh         &self,
367c2481452Shoumkh         exp: u32,
368c2481452Shoumkh         list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
369c2481452Shoumkh         high_list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
370c2481452Shoumkh     ) -> Result<MmioResult, MmioResult> {
371c2481452Shoumkh         // 至少要两个内存块才能合并
372c2481452Shoumkh         if list_guard.num_free <= 1 {
373c2481452Shoumkh             return Err(MmioResult::EINVAL);
374c2481452Shoumkh         }
375c2481452Shoumkh         loop {
376c2481452Shoumkh             if list_guard.num_free <= 1 {
377c2481452Shoumkh                 break;
378c2481452Shoumkh             }
379c2481452Shoumkh             // 获取内存块
380c2481452Shoumkh             let vaddr: u64 = list_guard.list.back().unwrap().vaddr;
381c2481452Shoumkh             // 获取伙伴内存块
382a7eb62a4Shoumkh             match self.pop_buddy_block(vaddr, exp, list_guard) {
383c2481452Shoumkh                 Err(err) => {
384c2481452Shoumkh                     return Err(err);
385c2481452Shoumkh                 }
386c2481452Shoumkh                 Ok(buddy_region) => {
387c2481452Shoumkh                     let region: Box<MmioBuddyAddrRegion> = list_guard.list.pop_back().unwrap();
388c2481452Shoumkh                     let copy_region: Box<MmioBuddyAddrRegion> = Box::new(MmioBuddyAddrRegion {
389c2481452Shoumkh                         vaddr: region.vaddr,
390c2481452Shoumkh                     });
391c2481452Shoumkh                     // 在两块内存都被取出之后才进行合并
392a7eb62a4Shoumkh                     match self.merge_blocks(region, buddy_region, exp, high_list_guard) {
393c2481452Shoumkh                         Err(err) => {
394c2481452Shoumkh                             // 如果合并失败了要将取出来的元素放回去
395a7eb62a4Shoumkh                             self.push_block(copy_region, list_guard);
396a7eb62a4Shoumkh                             kdebug!("merge_all_exp: merge_blocks failed");
397c2481452Shoumkh                             return Err(err);
398c2481452Shoumkh                         }
399c2481452Shoumkh                         Ok(_) => continue,
400c2481452Shoumkh                     }
401c2481452Shoumkh                 }
402c2481452Shoumkh             }
403c2481452Shoumkh         }
404c2481452Shoumkh         return Ok(MmioResult::SUCCESS);
405c2481452Shoumkh     }
406c2481452Shoumkh 
407c2481452Shoumkh     /// @brief 合并两个【已经从链表中取出】的内存块
408c2481452Shoumkh     ///
409c2481452Shoumkh     /// @param region_1 第一个内存块
410c2481452Shoumkh     ///
411c2481452Shoumkh     /// @param region_2 第二个内存
412c2481452Shoumkh     ///
413c2481452Shoumkh     /// @return Ok(MmioResult) 成功返回SUCCESS
414c2481452Shoumkh     ///
415c2481452Shoumkh     /// @return Err(MmioResult) 两个内存块不是伙伴块,返回EINVAL
416a7eb62a4Shoumkh     fn merge_blocks(
417c2481452Shoumkh         &self,
418c2481452Shoumkh         region_1: Box<MmioBuddyAddrRegion>,
419c2481452Shoumkh         region_2: Box<MmioBuddyAddrRegion>,
420c2481452Shoumkh         exp: u32,
421c2481452Shoumkh         high_list_guard: &mut SpinLockGuard<MmioFreeRegionList>,
422c2481452Shoumkh     ) -> Result<MmioResult, MmioResult> {
423c2481452Shoumkh         // 判断是否为伙伴块
424a7eb62a4Shoumkh         if region_1.vaddr != self.calculate_block_vaddr(region_2.vaddr, exp) {
425c2481452Shoumkh             return Err(MmioResult::EINVAL);
426c2481452Shoumkh         }
427c2481452Shoumkh         // 将大的块放进下一级链表
428a7eb62a4Shoumkh         self.push_block(region_1, high_list_guard);
429c2481452Shoumkh         return Ok(MmioResult::SUCCESS);
430c2481452Shoumkh     }
431c2481452Shoumkh 
432c2481452Shoumkh     /// @brief 创建一块mmio区域,并将vma绑定到initial_mm
433c2481452Shoumkh     ///
434c2481452Shoumkh     /// @param size mmio区域的大小(字节)
435c2481452Shoumkh     ///
436c2481452Shoumkh     /// @param vm_flags 要把vma设置成的标志
437c2481452Shoumkh     ///
438c2481452Shoumkh     /// @param res_vaddr 返回值-分配得到的虚拟地址
439c2481452Shoumkh     ///
440c2481452Shoumkh     /// @param res_length 返回值-分配的虚拟地址空间长度
441c2481452Shoumkh     ///
442a7eb62a4Shoumkh     /// @return Ok(i32) 成功返回0
443a7eb62a4Shoumkh     ///
444*676b8ef6SMork     /// @return Err(SystemError) 失败返回错误码
445ef9f9732Shoumkh     pub fn create_mmio(
446a7eb62a4Shoumkh         &self,
447c2481452Shoumkh         size: u32,
448c2481452Shoumkh         vm_flags: vm_flags_t,
449c2481452Shoumkh         res_vaddr: *mut u64,
450c2481452Shoumkh         res_length: *mut u64,
451*676b8ef6SMork     ) -> Result<i32, SystemError> {
452c2481452Shoumkh         if size > PAGE_1G_SIZE || size == 0 {
453*676b8ef6SMork             return Err(SystemError::EPERM);
454c2481452Shoumkh         }
455c2481452Shoumkh         let mut retval: i32 = 0;
456c2481452Shoumkh         // 计算前导0
457c2481452Shoumkh         let mut size_exp: u32 = 31 - size.leading_zeros();
458c2481452Shoumkh         // 记录最终申请的空间大小
459c2481452Shoumkh         let mut new_size: u32 = size;
460c2481452Shoumkh         // 对齐要申请的空间大小
461c2481452Shoumkh         // 如果要申请的空间大小小于4k,则分配4k
462c2481452Shoumkh         if size_exp < PAGE_4K_SHIFT {
463c2481452Shoumkh             new_size = PAGE_4K_SIZE;
464c2481452Shoumkh             size_exp = PAGE_4K_SHIFT;
465c2481452Shoumkh         } else if (new_size & (!(1 << size_exp))) != 0 {
466c2481452Shoumkh             // 向左对齐空间大小
467c2481452Shoumkh             size_exp += 1;
468c2481452Shoumkh             new_size = 1 << size_exp;
469c2481452Shoumkh         }
470c2481452Shoumkh         match MMIO_POOL.mmio_buddy_query_addr_region(size_exp) {
471c2481452Shoumkh             Ok(region) => {
472c2481452Shoumkh                 unsafe {
473c2481452Shoumkh                     *res_vaddr = region.vaddr;
474c2481452Shoumkh                     *res_length = new_size as u64;
475c2481452Shoumkh                 }
476c2481452Shoumkh                 // 创建vma
477c2481452Shoumkh                 let flags: u64 = vm_flags | (VM_IO | VM_DONTCOPY) as u64;
478c2481452Shoumkh                 let len_4k: u64 = (new_size % PAGE_2M_SIZE) as u64;
479c2481452Shoumkh                 let len_2m: u64 = new_size as u64 - len_4k;
480c2481452Shoumkh                 let mut loop_i: u64 = 0;
481c2481452Shoumkh                 // 先分配2M的vma
482c2481452Shoumkh                 loop {
483c2481452Shoumkh                     if loop_i >= len_2m {
484c2481452Shoumkh                         break;
485c2481452Shoumkh                     }
486c2481452Shoumkh                     let vma: *mut *mut vm_area_struct = null_mut();
487c2481452Shoumkh                     retval = unsafe {
488c2481452Shoumkh                         mm_create_vma(
489c2481452Shoumkh                             &mut initial_mm,
490c2481452Shoumkh                             region.vaddr + loop_i,
491c2481452Shoumkh                             PAGE_2M_SIZE.into(),
492c2481452Shoumkh                             flags,
493c2481452Shoumkh                             null_mut(),
494c2481452Shoumkh                             vma,
495c2481452Shoumkh                         )
496c2481452Shoumkh                     };
497c2481452Shoumkh                     if retval != 0 {
498c2481452Shoumkh                         kdebug!(
499c2481452Shoumkh                             "failed to create mmio 2m vma. pid = {:?}",
500c2481452Shoumkh                             current_pcb().pid
501c2481452Shoumkh                         );
502c2481452Shoumkh                         unsafe {
503c2481452Shoumkh                             vm_area_del(*vma);
504c2481452Shoumkh                             vm_area_free(*vma);
505c2481452Shoumkh                         }
506*676b8ef6SMork                         return Err(SystemError::from_posix_errno(retval).unwrap());
507c2481452Shoumkh                     }
508c2481452Shoumkh                     loop_i += PAGE_2M_SIZE as u64;
509c2481452Shoumkh                 }
510c2481452Shoumkh                 // 分配4K的vma
511c2481452Shoumkh                 loop_i = len_2m;
512c2481452Shoumkh                 loop {
513c2481452Shoumkh                     if loop_i >= size as u64 {
514c2481452Shoumkh                         break;
515c2481452Shoumkh                     }
516c2481452Shoumkh                     let vma: *mut *mut vm_area_struct = null_mut();
517c2481452Shoumkh                     retval = unsafe {
518c2481452Shoumkh                         mm_create_vma(
519c2481452Shoumkh                             &mut initial_mm,
520c2481452Shoumkh                             region.vaddr + loop_i,
521c2481452Shoumkh                             PAGE_4K_SIZE.into(),
522c2481452Shoumkh                             flags,
523c2481452Shoumkh                             null_mut(),
524c2481452Shoumkh                             vma,
525c2481452Shoumkh                         )
526c2481452Shoumkh                     };
527c2481452Shoumkh                     if retval != 0 {
528c2481452Shoumkh                         kdebug!(
529c2481452Shoumkh                             "failed to create mmio 4k vma. pid = {:?}",
530c2481452Shoumkh                             current_pcb().pid
531c2481452Shoumkh                         );
532c2481452Shoumkh                         unsafe {
533c2481452Shoumkh                             vm_area_del(*vma);
534c2481452Shoumkh                             vm_area_free(*vma);
535c2481452Shoumkh                         }
536*676b8ef6SMork                         return Err(SystemError::from_posix_errno(retval).unwrap());
537c2481452Shoumkh                     }
538c2481452Shoumkh                     loop_i += PAGE_4K_SIZE as u64;
539c2481452Shoumkh                 }
540c2481452Shoumkh             }
541c2481452Shoumkh             Err(_) => {
542c2481452Shoumkh                 kdebug!("failed to create mmio vma.pid = {:?}", current_pcb().pid);
543*676b8ef6SMork                 return Err(SystemError::ENOMEM);
544c2481452Shoumkh             }
545c2481452Shoumkh         }
546a7eb62a4Shoumkh         return Ok(retval);
547c2481452Shoumkh     }
548c2481452Shoumkh 
549c2481452Shoumkh     /// @brief 取消mmio的映射并将地址空间归还到buddy中
550c2481452Shoumkh     ///
551c2481452Shoumkh     /// @param vaddr 起始的虚拟地址
552c2481452Shoumkh     ///
553c2481452Shoumkh     /// @param length 要归还的地址空间的长度
554c2481452Shoumkh     ///
555c2481452Shoumkh     /// @return Ok(i32) 成功返回0
556c2481452Shoumkh     ///
557*676b8ef6SMork     /// @return Err(SystemError) 失败返回错误码
558*676b8ef6SMork     pub fn release_mmio(&self, vaddr: u64, length: u64) -> Result<i32, SystemError> {
559c2481452Shoumkh         //先将要释放的空间取消映射
560c2481452Shoumkh         unsafe {
561c2481452Shoumkh             mm_unmap(&mut initial_mm, vaddr, length, false);
562c2481452Shoumkh         }
563c2481452Shoumkh         let mut loop_i: u64 = 0;
564c2481452Shoumkh         loop {
565c2481452Shoumkh             if loop_i >= length {
566c2481452Shoumkh                 break;
567c2481452Shoumkh             }
568c2481452Shoumkh             // 获取要释放的vma的结构体
569c2481452Shoumkh             let vma: *mut vm_area_struct = unsafe { vma_find(&mut initial_mm, vaddr + loop_i) };
570c2481452Shoumkh             if vma == null_mut() {
571c2481452Shoumkh                 kdebug!(
572c2481452Shoumkh                     "mmio_release failed: vma not found. At address: {:?}, pid = {:?}",
573c2481452Shoumkh                     vaddr + loop_i,
574c2481452Shoumkh                     current_pcb().pid
575c2481452Shoumkh                 );
576*676b8ef6SMork                 return Err(SystemError::EINVAL);
577c2481452Shoumkh             }
578c2481452Shoumkh             // 检查vma起始地址是否正确
579c2481452Shoumkh             if unsafe { (*vma).vm_start != (vaddr + loop_i) } {
580c2481452Shoumkh                 kdebug!(
581c2481452Shoumkh                     "mmio_release failed: addr_start is not equal to current: {:?}. pid = {:?}",
582c2481452Shoumkh                     vaddr + loop_i,
583c2481452Shoumkh                     current_pcb().pid
584c2481452Shoumkh                 );
585*676b8ef6SMork                 return Err(SystemError::EINVAL);
586c2481452Shoumkh             }
587c2481452Shoumkh             // 将vma对应空间归还
588a7eb62a4Shoumkh             match MMIO_POOL.give_back_block(unsafe { (*vma).vm_start }, unsafe {
589c2481452Shoumkh                 31 - ((*vma).vm_end - (*vma).vm_start).leading_zeros()
590c2481452Shoumkh             }) {
591c2481452Shoumkh                 Ok(_) => {
592c2481452Shoumkh                     loop_i += unsafe { (*vma).vm_end - (*vma).vm_start };
593c2481452Shoumkh                     unsafe {
594c2481452Shoumkh                         vm_area_del(vma);
595c2481452Shoumkh                         vm_area_free(vma);
596c2481452Shoumkh                     }
597c2481452Shoumkh                 }
598c2481452Shoumkh                 Err(err) => {
599c2481452Shoumkh                     // vma对应空间没有成功归还的话,就不删除vma
600c2481452Shoumkh                     kdebug!(
601c2481452Shoumkh                         "mmio_release give_back failed: pid = {:?}",
602c2481452Shoumkh                         current_pcb().pid
603c2481452Shoumkh                     );
604a7eb62a4Shoumkh                     return Err(err);
605a7eb62a4Shoumkh                 }
606a7eb62a4Shoumkh             }
607a7eb62a4Shoumkh         }
608a7eb62a4Shoumkh         return Ok(0);
609a7eb62a4Shoumkh     }
610a7eb62a4Shoumkh }
611a7eb62a4Shoumkh 
612a7eb62a4Shoumkh /// @brief mmio伙伴系统内部的地址区域结构体
613a7eb62a4Shoumkh pub struct MmioBuddyAddrRegion {
614a7eb62a4Shoumkh     vaddr: u64,
615a7eb62a4Shoumkh }
616a7eb62a4Shoumkh impl MmioBuddyAddrRegion {
617a7eb62a4Shoumkh     pub fn new() -> Self {
618a7eb62a4Shoumkh         return MmioBuddyAddrRegion {
619a7eb62a4Shoumkh             ..Default::default()
620a7eb62a4Shoumkh         };
621a7eb62a4Shoumkh     }
622a7eb62a4Shoumkh }
623a7eb62a4Shoumkh impl Default for MmioBuddyAddrRegion {
624a7eb62a4Shoumkh     fn default() -> Self {
625a7eb62a4Shoumkh         MmioBuddyAddrRegion {
626a7eb62a4Shoumkh             vaddr: Default::default(),
627a7eb62a4Shoumkh         }
628a7eb62a4Shoumkh     }
629a7eb62a4Shoumkh }
630a7eb62a4Shoumkh 
631a7eb62a4Shoumkh /// @brief 空闲页数组结构体
632a7eb62a4Shoumkh pub struct MmioFreeRegionList {
633a7eb62a4Shoumkh     /// 存储mmio_buddy的地址链表
634a7eb62a4Shoumkh     list: LinkedList<Box<MmioBuddyAddrRegion>>,
635a7eb62a4Shoumkh     /// 空闲块的数量
636a7eb62a4Shoumkh     num_free: i64,
637a7eb62a4Shoumkh }
638a7eb62a4Shoumkh impl MmioFreeRegionList {
63964aea4b3SGou Ngai     #[allow(dead_code)]
640a7eb62a4Shoumkh     fn new() -> Self {
641a7eb62a4Shoumkh         return MmioFreeRegionList {
642a7eb62a4Shoumkh             ..Default::default()
643a7eb62a4Shoumkh         };
644a7eb62a4Shoumkh     }
645a7eb62a4Shoumkh }
646a7eb62a4Shoumkh impl Default for MmioFreeRegionList {
647a7eb62a4Shoumkh     fn default() -> Self {
648a7eb62a4Shoumkh         MmioFreeRegionList {
649a7eb62a4Shoumkh             list: Default::default(),
650a7eb62a4Shoumkh             num_free: 0,
651a7eb62a4Shoumkh         }
652a7eb62a4Shoumkh     }
653a7eb62a4Shoumkh }
654a7eb62a4Shoumkh 
655a7eb62a4Shoumkh /// @brief 初始化mmio的伙伴系统
656a7eb62a4Shoumkh #[no_mangle]
657a7eb62a4Shoumkh pub extern "C" fn __mmio_buddy_init() {
658a7eb62a4Shoumkh     // 创建一堆1GB的地址块
659a7eb62a4Shoumkh     let cnt_1g_blocks: u32 = ((MMIO_TOP - MMIO_BASE) / PAGE_1G_SIZE as i64) as u32;
660a7eb62a4Shoumkh     let mut vaddr_base: u64 = MMIO_BASE as u64;
661a7eb62a4Shoumkh     for _ in 0..cnt_1g_blocks {
662a7eb62a4Shoumkh         match MMIO_POOL.give_back_block(vaddr_base, PAGE_1G_SHIFT) {
663a7eb62a4Shoumkh             Ok(_) => {
664a7eb62a4Shoumkh                 vaddr_base += PAGE_1G_SIZE as u64;
665a7eb62a4Shoumkh             }
666a7eb62a4Shoumkh             Err(_) => {
667a7eb62a4Shoumkh                 kerror!("__mmio_buddy_init failed");
668a7eb62a4Shoumkh                 return;
669a7eb62a4Shoumkh             }
670a7eb62a4Shoumkh         }
671a7eb62a4Shoumkh     }
672a7eb62a4Shoumkh }
673a7eb62a4Shoumkh 
674a7eb62a4Shoumkh /// @brief 将内存对象大小的幂转换成内存池中的数组的下标
675a7eb62a4Shoumkh ///
676a7eb62a4Shoumkh /// @param exp内存大小
677a7eb62a4Shoumkh ///
678a7eb62a4Shoumkh /// @return 内存池数组下标
679a7eb62a4Shoumkh #[inline(always)]
680a7eb62a4Shoumkh fn exp2index(exp: u32) -> usize {
681a7eb62a4Shoumkh     return (exp - 12) as usize;
682a7eb62a4Shoumkh }
683a7eb62a4Shoumkh 
684a7eb62a4Shoumkh /// @brief 创建一块mmio区域,并将vma绑定到initial_mm
685a7eb62a4Shoumkh ///
686a7eb62a4Shoumkh /// @param size mmio区域的大小(字节)
687a7eb62a4Shoumkh ///
688a7eb62a4Shoumkh /// @param vm_flags 要把vma设置成的标志
689a7eb62a4Shoumkh ///
690a7eb62a4Shoumkh /// @param res_vaddr 返回值-分配得到的虚拟地址
691a7eb62a4Shoumkh ///
692a7eb62a4Shoumkh /// @param res_length 返回值-分配的虚拟地址空间长度
693a7eb62a4Shoumkh ///
694a7eb62a4Shoumkh /// @return int 错误码
695a7eb62a4Shoumkh #[no_mangle]
696a7eb62a4Shoumkh pub extern "C" fn mmio_create(
697a7eb62a4Shoumkh     size: u32,
698a7eb62a4Shoumkh     vm_flags: vm_flags_t,
699a7eb62a4Shoumkh     res_vaddr: *mut u64,
700a7eb62a4Shoumkh     res_length: *mut u64,
701a7eb62a4Shoumkh ) -> i32 {
702a7eb62a4Shoumkh     if let Err(err) = MMIO_POOL.create_mmio(size, vm_flags, res_vaddr, res_length) {
703*676b8ef6SMork         return err.to_posix_errno();
704a7eb62a4Shoumkh     } else {
705c2481452Shoumkh         return 0;
706c2481452Shoumkh     }
707a7eb62a4Shoumkh }
708a7eb62a4Shoumkh 
709a7eb62a4Shoumkh /// @brief 取消mmio的映射并将地址空间归还到buddy中
710a7eb62a4Shoumkh ///
711a7eb62a4Shoumkh /// @param vaddr 起始的虚拟地址
712a7eb62a4Shoumkh ///
713a7eb62a4Shoumkh /// @param length 要归还的地址空间的长度
714a7eb62a4Shoumkh ///
715a7eb62a4Shoumkh /// @return Ok(i32) 成功返回0
716a7eb62a4Shoumkh ///
717a7eb62a4Shoumkh /// @return Err(i32) 失败返回错误码
718a7eb62a4Shoumkh #[no_mangle]
719a7eb62a4Shoumkh pub extern "C" fn mmio_release(vaddr: u64, length: u64) -> i32 {
720a7eb62a4Shoumkh     if let Err(err) = MMIO_POOL.release_mmio(vaddr, length) {
721*676b8ef6SMork         return err.to_posix_errno();
722a7eb62a4Shoumkh     } else {
723a7eb62a4Shoumkh         return 0;
724a7eb62a4Shoumkh     }
725a7eb62a4Shoumkh }
726