rcore-os Blog
0%

Posted on

第一阶段

参加训练营让我了解到有 rust 这门语言，以前写c/c++习惯了指针的自由操作，刚开始非常不适应，但随着之后的学习越来越爱。
Rust 兼顾安全与性能，Rust的所有权机制让内存管理变得十分高效且安全, 减少了很多的内存问题, Rust的所有权、借用和生命周期模型可以在编译期防止常见的内存错误（如悬空指针、双重释放等），无需依赖垃圾回收器。Rust 编程思维不同于传统的面向对象，我认为更像是面向数据。

第二阶段

训练营给了我交流与实践的平台，通过参加此次训练营我学到了很多关于操作系统的知识，也让我了解到了在操作系统领域最新的研究与技术。
从裸机运行到单道批处理系统，学习了如何通过操作系统将程序与硬件隔离，提高安全性和资源利用率。rCore通过硬件的运行特权级划分和系统调用来实现多程序批处理，将程序编译链接成bin文件，加载到内存中的约定地址执行。进一步地探索了进程调度的机制，理解了时间片和CPU利用率的关系，以及如何通过TCB（任务控制块）来维护程序的关键信息，实现程序的切换和调度。
在内存管理方面，学习了从物理地址到虚拟地址的转变，以及MMU（内存管理单元）的重要性。rCore采用SV39内存管理策略，通过页机制和多级页表提高了内存的灵活性和安全性。对外存的管理，我了解了文件系统如何抽象和管理系统资源，以及rCore如何通过文件描述符（fd）框架来统一管理文件和设备。
线程与进程的学习让我认识到了操作系统调度的复杂性。RCore通过线程的引入提高了响应速度和调度效率，同时使用信号量和互斥机制来解决线程间的冲突问题。
总的来说，RCore的学习不仅加深了我对操作系统的理解，也锻炼了我的系统编程能力。通过实践，我对操作系统的许多概念有了更实际的认识。

Posted on

Rustlings 练习总结

作为一名前端全栈开发者，刚开始学习Rust时，给我的感觉是没想象中的难度那么高，学起来还挺轻松…
然而，还是太年轻了，当我开始真的用起来之后，我发现，编译器成为了我前进的“恶梦”，它无时无刻不在教我做人，总是会在不经意间鞭挞我：“你，还很菜呢！”
所以，慢慢的，我开始放弃了保守的学习方式：“先将文档中的内容都大致学会，并记下来”，它让我一直停留在学习的舒适区，对学习Rust来说是很低效的。
Rustlings 其实就是一种很好的学习语言的方式，通过大量的几乎全覆盖式的Rust练习，在练习中不断遇到问题，并解决问题，就像打怪升级，心理上会不断的得到激励感，并不断的做下去。
通过Rustlings的110道题目的练习，其实也让我意识到了，自己以为的会使用Rust了，只是井底之蛙吧了。
练习的内容虽然都在文档中，只看文档学习的化，其实有时候会忽略这些知识的真实用途是什么，也就无法在实际项目中灵活的去使用了。
通过这段时间的练习，不一定让我在Rust的熟练成都有很大的提升，但是让我看到了一个Rust用法的大纲，这已经是一个很好的开始了。
希望在接下来的开发里，不断精进对Rust使用，当然，也不能只专注在语法本身，对操作系统本身知识的学习，会更重要，非常期待！

Posted on

title: 2024春夏季开源操作系统训练营第一阶段总结报告-fengtdi
date: 2024-04-24 21:38:58
tags:
- author:zlh20040308

2024春夏季开源操作系统训练营第一阶段总结报告

前言

了解到这个训练营源自一次机缘巧合，刚学完操作系统的鄙人在b站刷课时无意刷到了前训练营的导学部分，并在评论区看到了up主留下的链接，点进去一看正好都是我很感兴趣的方向，而且学习资源和github页面都整理得很完善，于是果断加入了

Rust编程基础

初探

第一阶段的的主要任务是学习Rust语言，刚接触这门语言时候的第一感觉就是概念十分的多，有些概念甚至看起来匪夷所思，如生命周期标注，我十分不理解为什么Rust要这么设计，但是秉持着能跑就行的原则，还是硬着头皮和编译器作斗争

初窥门径

带着以上这些问题，我找到了斯坦福大学CS110L这门课，这门课并不是教学生如何进行Rust编程，而是希望通过Rust的视角反映出当今两种主流内存分配机制——手动管理（malloc&free）和垃圾回收（GC）——的不足，在其三节课就主要讨论了它们所会遇到的问题：

  • 手动管理（C/C++）

    C/C++的类型系统对内存所有权的表达能力是十分有限的，以至于工程师在设计函数接口时会显得十分臃肿，还必须附上大量的注释来告知调用者去担负起管理内存的责任，也就是说内存的管理取决于程序员的自觉性，这就导致程序员经常会忘记之前申请过释放内存，而且随着工程的不断壮大，这种错误会不可避免地发生

  • 垃圾回收（Java）

    Java通过某种类似于引用计数的方式来自动回收内存，但这种设计会带来性能上的损耗（回收机制过于复杂）

而Rust便带来了属于它的第三种方案，那就是所有权机制，在这种机制下，内存管理会变得高效且安全，这得益于它强大的静态检测机制，能够在编译时期就规避掉很多内存泄露的隐患

但这也是有代价的，既然要求在编译时期就能发现错误，那么Rust编译器就会要求程序员在编码时附带足够多的信息供它推断，也就出现了类似于生命周期标注这些语法

牛刀小试

在初步过完几轮Rust基础并完成了rustlings之后，便开始着手用Rust复刻了一些之前写过的小项目（当然，还有那令Rust新手望而生畏的链表），在这段过程中越发能感受到Rust的一些设计理念在影响着我的编码习惯，也引起了我对与内存安全的思考

总结

在经历了这一阶段的学习后，虽然我到现在也不认为我是一个Rust程序员，但是也多多少少能用Rust去进行一些有效编码了

十分感谢第一阶段中为我答疑解惑的老师和同学，同时更要感谢开源操作系统训练营提供了这么一个平台把大家聚集在了一起，我十分喜欢这里的学习氛围，大家一起交流着学习上的疑惑并提出自己的见解，这开源的理念也使我收益颇丰

Posted on

第一阶段学习总结-ZhongkaiXu

写在前面

这是第二次写rustlings，两个月前应实习要求第一次学习rust和rcore，这次和上次相比稍微熟练了一些，从最开始的一头雾水，到现在已经对rust的简洁性佩服得五体投地。接下来要一些smmu相关的开发，借着这个机会再熟悉了一下rust。以下是一些学习心得。

学习心得

我认为的rust的核心思想

我觉得rust里最重要的是所有权机制，一个value只能对应一个所有者，即使是函数传参也是一样，虽然刚开始有些不习惯，但是慢慢发现对于锻炼系统软件开发者的思维很有效。

文档

在做题的时候我会同时打开rust文档，因为太多东西记不住了，需要随用随查，抛开水平不够，感觉这还算是一个不错的习惯，开了一个好头，毕竟后面几个阶段的学习必须依赖riscv/arm的手册。

最有挑战性的

我觉得在使用rust开发过程中，最难的地方在于如何把程序写的“rust”，比如对于寄存器的访问，rust中有一些优秀的宏如 registers_struct! ，第一次看到这个东西之前还一直停留在c风格的编程思想，包括写的一些算法题也是没有完全发挥出rust的语言特性，希望在后面学习的过程中多参考一些优秀代码，养成好的习惯。

未来展望

马上进入二阶段的学习，临近6月也要做很多其他的工作，希望能做到WLB吧，把握和优秀的同学们交流的机会，学到更多东西。

第二阶段学习总结-ZhongkaiXu

写在前面

终于在最后一天完成了五道题。

这是第二次写rCore的课后练习题了，之前偷的懒也还回来了。前三个练习之前写过，就还算顺利，后两个卡了蛮长的时间。

学习心得

模仿

其实练习里面需要自己构思代码的部分不多，大部分都是在原有代码的基础上添加一些辅助的功能，只要能设计好思路，剩下的就是模仿已经实现的代码。

比如mmap的实现，我最开始想用现成的 insert_framed_area，然后还写了一大堆判断是否重复映射的函数，结果在munmap的时候又要整个考虑释放area的部分页，写的自己都懵了。后来回头看原有代码的实现，发现其实mmap就是一个 insert_framed_area 的删减版，不需要area那么大的粒度，直接模仿area里面的btreemap设计一个容器，再重用 insert_framed_area 的代码就行了..

再比如发现自己还是没法摆脱c的风格，for能套个好几层，不过好在能想到rust里面应该不用这么麻烦，然后回头翻原有代码，看看其他地方怎么用迭代器的。

大胆写 反正有rust_analyzer 反正可以rollback

现在写rust没有那么提心吊胆怕和编译器同归于尽了，还是自动补全的功劳，很多地方分不清要不要解引用、分不清数据类型，不过rust_analyzer会搞定的。

有些时候乱写一通，最后发现内核挂掉了，只好rollback了，也在群里问过把仓库污染了怎么从头开始，不过大胆写也好过不写，经过n次rollback总算能上手敲代码了。

未来展望

第三阶段hypervisor我来了！

Posted on

第一阶段练习总结

作为一名Cpper，我之前对Rust的了解可以说是毫无了解，这次受到朋友的邀请，第一次接触Rust，刚开始以为就是像C一样的过程语言。然而，当我真正开始深入学习和使用Rust时，我发现它远比我预想的要有趣和富有挑战性。特别是在进行Rustlings练习的过程中，我收获颇丰，也深刻体会到了Rust语言的强大和魅力。

Rustlings是一个设计精良的Rust语言练习项目，通过一系列由简到难的练习题，帮助开发者逐步掌握Rust的语法和特性。在练习的过程中，我遇到了许多看似简单但实则深奥的问题，这些问题让我不断思考和探索，也让我对Rust有了更深入的理解。

通过Rustlings的练习，我只能感叹面向编译器编程的魅力。

此外，Rustlings的练习还让我认识到了自己在编程思维方面的不足总的来说，Rustlings练习是我学习Rust过程中的一个重要环节。它不仅让我掌握了Rust的基本语法和特性，还锻炼了我的编程思维和解决问题的能力。我相信，在未来的学习和工作中，我会继续利用Rustlings等资源来深化对Rust的理解和应用，并不断提升自己的编程水平。同时，我也期待在未来的项目中能够充分发挥Rust的优势，写出更加健壮、高效的程序。

Posted on

阶段一-Rustlings

这个阶段主要是需要进行rust相关的学习.

其实早就有接触过rust,但是语法,尤其是所有权和生命周期这块,一直还比较生疏.

有关于所有权相关的内容主要是看了这个视频:如何一步一步推导出Rust所有权、借用规则、引用类型以及秒懂生命周期标注_哔哩哔哩_bilibili

其中关于rust作为无gc语言,大部分内存都是保存在栈上的,只有少部分是保存在栈里边.

‘a指出返回的引用与输入参数x、y之间有关联.

这个非常非常重要.

阶段二-OS内核实验

ch0-2

可以参见我之前复现rCore-Tutorial-Book-v3 3.6.0-alpha.1 文档的笔记,被公开在博客园上.

[winddevil的笔记 - 博客园

这次学习主要是从ch3~ch8的学习,重点换做了解决通过测例,和一些自己的问题.

ch3

主要是讲的一个任务切换的流程,有了任务切换之后又通过定时器中断实现了抢占式调度.

替代文本|800

ch4

这一章主要解决的是一个虚拟地址转换为物理地址的过程,说是虚拟地址,我原来以为真的改变了地址,实际上每一次调用资源都还是使用了物理地址的,利用地址空间对所有的需要访问具体物理地址的对象进行操作.

替代文本|800

ch5

这一章同样是承接了上一章的知识,讲的主要是一个进程的概念,加入了很多新的结构体,后边我应该会有时间的时候更新一下图片.

进程中最巧妙的就是使用了fork这个复制一个任务的操作,有了进程,那么就可以实现编程的简洁性,倭只需要编写一个小任务,然后再进行组合,而不是调用fn,然后自己设计各种分支结构.

有了进程,相当于把调度的工作委托给了os.

ch6

在上一章的基础上,引入了块和文件系统.

这一部分的知识学的非常的不牢靠.

但是让我印象深刻的地方是,这一章基本实现了我对之前学习的时候发现windows是可以直接”点开”应用这个操作的好奇.

那么应用保存在哪里,为什么我用U盘拷贝了还是可以继续运行.

之前学习单片机的时候很少想到我可以通过什么东西对”可执行”的东西进行操作.

通过二进制文件进行加载然后运行的操作属实惊艳到了我.

ch7

这个和ch4更加相关.之前运行rtos的时候总是想着,那么这个变量可以直接以全局变量的方式进行传输为什么我要使用各种比如信号量比如邮箱的方式,现在就一目了然了.

因为地址空间的不同所以进程之间的通信需要通过管道,也就是需要经由操作系统这一层.

ch8

这一部分让我想起了之前进行单片机编程的时候的临界段保护操作,那时候是通过非常暴力的方法关掉了所有的中断以保证这次读取不会出现问题.

或者使用原子操作保证中断无法打断单一时钟下的操作.

这里并没有和硬件和中断打交道,而是选用了三种方式,加锁\条件变量\信号量的方式.

使用银行家算法进行了调度,算法不难,但是调用本身很麻烦,需要在每一次加锁的时候对题中的变量进行操作.并且每一次上锁的时候都需要detect,那么对上锁的程序也必须进行改造.

本次体验

越到后边越忙,如果有幸进入下一个阶段一定不能好高骛远多线程操作,一定要留足时间给自己.

Posted on

一阶段学习体会

早就听说过大名鼎鼎的 rustlings， 这次借着 oscamp 的机会来做一做。做的过程中发现 oscamp 的 rustlings 似乎比官方的 rustlings 加了很多私货，难度大了不少，
但是也的确把编写 很多有用的 rust 特性 和 os 过程中会用得到的一些 rust 的 feature 都涵盖了。在做的过程中，也学习到了很多以前自己没有注意或者使用过的 rust 特性。
更重要的是，通过一些题目的学习，能摆脱原来写 c++ 的思维，写出一些更 rust 风格的代码,比如返回值多用 Option 和 Result，更多的使用 match 和 if let， 而不是用原来 c++/c 风格的错误判断，
以及更多的用迭代器等方法。

一阶段学完之后，尤其是经历了大量和编译器的斗智斗勇之后，我对 rust 的理解加深很多，也对 rust 带来的相比 c++ 的很多优势有了更深的体会。相信 rust 和 c++ 的学习会互相促进。

二阶段学习体会

本科期间零零散散一致有学过 rust 和 rcore 的一些东西，由于各种各样的事情没能坚持下来。
读硕士之后刚好又系统学习了一下 rust ，正巧有同学来约我参加 oscamp ， 于是就来参加。

如今再做 rcore 感觉要比本科期间轻松了很多。在游刃有余之后，能从 rcore 中汲取的知识也就更多了。
文件系统的组织方式、并发的实现和管理等，这些本科期间令我头晕转向的知识点，现在都能比较轻松地理解。也能从中窥探出一个真实生产环境下的操作系统是如何设计的。

本次实验中，前四个实验都比较轻松，思路清晰地拿下了。最让我头晕转向的是第五个实验，也就是死锁检测的实现。
刚开始被银行家算法迷惑，感觉很难实现。后来又做了尝试做了环路检测来检测死锁。但是做的过程中发现环路检测可能比较难处理信号量。于是又回过头来思考银行家算法。
结合前面尝试做环路检测的过程，觉得只要实现一套类似银行家算法的检测机制就好了。于是把代码全部推翻，从头来过很快就拿下了。

这一次 rcore 学习体验不错，希望接下来的三阶段能学到一些有意思、更贴近实际场景的东西。

Posted on Edited on

你们好，我是catme0w，来分享一下我在内存分配器挑战中的经历。

也看看我在二阶段的文章吧：https://rcore-os.cn/blog/2024/11/10/2024%E7%A7%8B%E5%86%AC%E5%AD%A3%E5%BC%80%E6%BA%90%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F%E8%AE%AD%E7%BB%83%E8%90%A5%E7%AC%AC%E4%B8%80%E3%80%81%E4%BA%8C%E9%98%B6%E6%AE%B5%E6%80%BB%E7%BB%93-catme0w/

Round 1：更好的TLSF分配器

一开始拿到题目的时候，是想尝试一下改善“正常的分配器”的，也就是实现通用分配器，因为那时想着，毕竟在内核空间之中搞小动作太过容易，以非正常方式刷分数显得太cheaty了一点也不好玩。

粗略了解过后，认识到原来TLSF实现所使用的rlsf库已经是分配器算法的较优实现了：https://github.com/yvt/rlsf#measured-performance 。尝试调整了一下rlsf的参数（FLLEN和SLLEN），发现并没有什么变化，无法突破170。

认识到试图优化TLSF似乎是没有前途的；改善TLSF的路线，宣告失败。

Round 2：面向测例分配器

那么，我们不得不从头开始写我们自己的东西了。

要了解分数由什么决定，也就是什么决定了indicator数量的上限，进一步地，了解每一步中内存分配行为和内存碎片的变化。

不难看出，测例会释放掉偶数项的块，而保留奇数项。

由此，我们可以针对性地“攻击”这一点——研究测例的分配模式，追踪每一次分配是否是“不会被释放”的那一批，将其连续排列在一个特殊的区域中，使得内存碎片完全不会出现，利用率达到惊人的100%。

可当我准备动手时，意识到这个东西在现实世界里没有意义，它只能针对这个测例起效。至少在我看来，这已经和非正常方式没有太大差异了。

那么，要不……一不做二不休，干脆直接把非正常方式做到极致？

Round 3：假的分配器

从测例的行为可以了解到，它只会验证块的最后一个字节是否正确，那么思路就很简单了，追踪每次分配行为，如果是外层的Vec，就给它用真的分配器；如果是内层Vec，就只分配两个字节，然后返回伪造的内存地址！

可是，说的倒轻巧，思路是简单不假，可是究竟有什么方法精确地识别一个堆分配操作来自哪里呢？答案是没门！更不要提伪造内存地址会有多难做。

我确实尝试了一下，但是……很快放弃了。

值得一提的是，分配器的部分不直接在内核中，没有println可用，因而调试极其困难。

必须再换一个思路才行。

Round 4：他不体面你就帮他体面分配器

注意到：每次分配的内存大小由base+delta构成，base指数增长，从32开始，每次为之前的两倍，直到达到512 KB；delta为indicator数量。

释放的规律上文已提过，偶数项释放，奇数项保留。

那么，新的思路由此诞生：追踪indicator的数量，确定当前测例位于哪一“回合”，进而精确计算出哪些分配会被测例保留，记下它们的内存地址……

然后，从分配器的代码内，释放掉它们！

他不体面，你就帮他体面！

我最开始思路还要更简单些，只是记录下所有分配的内存地址，当遇到大于512 KB的释放时，就释放掉之前记录的所有地址。

但这样会有一个显而易见的问题：double free——测例本身还会释放一半呢。

由于测例很简单，我一开始不认为这是个问题，但在我无数次撞在LoadFault上之后，我投降了……

以下是我最终的详细思路：

具体不会被释放的块，长度为64+delta、256+delta、1024+delta……。

将其base值，也就是64、256、1024……维护在分配器内的一个Vec中。

当分配器命中这些值时，把它们的内存地址和大小保存在另一个Vec中。

当分配器命中下一“回合”的32+delta，也就是第一次分配时，标志前一“回合”结束，此时，将记录到的那些不会被测例释放的内存块释放掉。

由此，我们便消除了测例的“内存泄漏”，内存将永远无法被耗尽。

但没那么简单，这个“正确的思路”第一版实现仍然会停止在130，并且不是no memory，而是触发了LoadFault，内存越界了。

经观察，我所记录的那些“我要帮它体面”的内存块中，恰好有某项命中了外层Vec的扩张大小……

由于临近截止，我没有时间仔细去寻找它们到底命中哪个长度了，只能暂时绕过它。

在indicator足够大之前，每回合均不释放开头的两项。

一阵操作之后，我终于第一次看到了indicator数量超越170。

或者说，我终于得到了梦寐以求（？）的无尽indicator。

在何时停止好呢？来做一个114514吧，多有纪念意义啊。

只是，它在65536就停了下来，显示no memory。

何故呢？

原来，测例中负责释放的那部分（free_pass）所使用的delta长度是u8，只有负责分配的部分（alloc_pass）才是usize。65536是u8的上限，不是我的上限。

我的114514，梦碎了。

“这不可能！”

我大叫起来。

此时临截止不到一个小时了，我分明记得之前看到过有人把indicator刷到了六位数。

他们怎么绕过u8的上限的？

Round ？：一种基于kernel exploit的分配器

想要打破u8，那就得让free_pass不执行。

得发挥更强大的想象力，寻找更下作（？）的手段。

那么，这其中的花样可就多了……

此时的操作系统仍是unikernel，没有虚拟内存，不存在用户空间，所有的代码共用同一个（物理）地址空间。

你可以找到测例里alloc_pass那个循环下标的内存地址，然后直接把它改成114514……

或者，直接覆盖掉println……

甚至，还可以想办法在我们能允许修改的这一小块代码中弄出些use-after-free，来点缓冲区溢出，来点ROP……

但我想，已经刷到六位数的那些人用的并不是这样的方法。他们会怎么做呢？比赛结束之后再去看看吧。

100% Honest Review

在最开始，我对参与这项挑战的兴趣不大。我不喜欢这种有零和博弈味道的规则——早提交可能失去优化机会，晚提交可能因结果相同而落后。

ArceOS已经很难了，题目若再有压力，我会直接躺平。我承认我很脆弱。

话虽这么说，我还是来了。尽管我很晚才开始了解挑战的细节，而到那时，已经有人发掘出了非正常方式。

那时我的反应与群里一位的想法几乎一致：这不就彻底没意思了吗？

但当我亲自上手这个题目时，想法还是逐渐发生了变化。哎真香

纵使前期有些不愉快，最终还是收获了不少快乐与知识。

但倘若你问我，还想不想再玩一次这样的挑战题目的话……

我的回答是否定的。

Posted on Edited on In

内存分配器-字节分配器：Chaos 一点都不 Chaos

分析内存结构

堆中的 Vec<Vec<u8>> 结构数据

使用上述任意分配器，并在 alloc 和 dealloc 函数，中分别打印 Layout。在打印结果中可以看到一些比较特殊的内存大小分别为 96、192、384

这是什么呢？根据 lab1/src/main.rs 中的测例代码分析可得知 let mut items: Vec<Vec<u8>> = Vec::new(); 的内层 Vec 将存放在堆内存中。

而 Rust 中的堆数据结构 中的一张图片展示了 Vec 的内存结构为指针、长度和容量，每一部分各占 usize，在 64 位系统中，uszie 大小为 8 字节，即一个空数组内存占用为 24 字节，这与 96 字节仍有出入。

再观察分配情况，在 Indicator: 0 时，96 字节的 alloc 是在第一次 32 字节 alloc 后产生的，猜测是在 items.push 后进行了一次 扩容，alloc_pass 修改为如下代码进行验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fn alloc_pass(delta: usize) -> Vec<Vec<u8>> {
    let mut items = Vec::new();
    let mut base = 32;
    loop {
        let c = (delta % 256) as u8;
        let a = vec![c; base+delta];
        items.push(a);
        println!("Item Capacity: {}", items.capacity());
        if base >= 512*1024 {
            break;
        }
        base *= 2;
    }
    items
}

结果为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Running bumb tests...
Indicator: 0
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 4
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 8
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16
Item Capacity: 16

就对上了，24 * 4 = 96 24 * 8 = 192 24 * 16 = 384

同时，至少在这里来说，Vec 初始容量为 0，第一次扩容时为 4，扩容机制为每次容量翻倍。

存放数据的堆空间

再回到测例代码：

1
2
3
4
5
6
7
8
9
10
fn free_pass(items: &mut Vec<Vec<u8>>, delta: u8) {
    let total = items.len();
    for j in (0..total).rev() {
        if j % 2 == 0 {
            let ret = items.remove(j);
            assert_eq!(delta, ret[0]);
            assert_eq!(delta, ret[ret.len()-1]);
        }
    }
}

这段代码在检查是否为偶数项，偶数项数组才会被 free_pass 的 remove() 释放。

因此针对这段代码，可以在分配器中设置一个奇偶标志位，当标志位为奇数时将数据从内存的起始位置开始分配，偶数时分配在末尾位置且向起始位置增长。扩容时，不考虑内存扩容时传入的内存地址起始位置而只改变结尾位置时也无需多余操作。

Chaos 真的不 Chaos

整体结构

考虑：

  1. 堆中的 Vec<Vec<u8>> 数据结构，大小固定为 96 + 192 + 384 = 672 字节，位于可分配内存的起始位置
  2. 奇数项堆，动态增长，紧跟 672 字节
  3. 偶数项堆，动态增长，位于可分配内存的末尾位置

使用以下结构体来描述整个可分配内存区域

1
2
3
4
5
6
7
8
9
10
11
12
pub struct Chaos {
    pub vec_reserve: (usize, usize, usize),

    pub start: usize,
    pub end: usize,
    pub head: usize,
    pub tail: usize,
    pub is_even: bool,

    pub allocated: usize,
    pub total: usize,
}

内存结构如下：

memory

vec_reserve: (usize, usize, usize) 用作存储先前描述的三片特殊的堆中 Vec 元数据结构，vec_reserve 为固定长度：96 + 192 + 384 字节。

pub start: usize 和 pub end: usize 分别存储 init 或是 add_to_heap 时给定的可分配内存地址范围。

pub head: usize 和 pub tail: usize 分别存储当前奇数堆的末尾位置和偶数堆的起始位置，通过 head - start + vec_reserve 可以得出奇数堆大小，通过 end - tail 则可以得出偶数堆大小。

pub is_even: bool 用于记录上一次分配是奇数还是偶数，在分配的最后将其翻转。

实现

在开始之前，还要确定一个很重要的问题。目前的设计，并没有考虑扩容时分配在本程序堆内存前内存区域的地址，因此使用代码简单判断下：

1
2
3
4
5
6
7
8
pub fn add_to_heap(&mut self, start: usize, end: usize) {
    log::warn!("head: 0x{:x}, tail: 0x{:x}, start: 0x{:x}, end: 0x{:x}", self.head, self.tail, start, end);

    self.head = start;
    self.tail = end;

    panic!("add_to_heap");
}

从 add_to_heap 的输出：

1
2
3
4
5
6
Running bumb tests...
Indicator: 0
[  0.082919 0 lab_allocator::chaos:66] head, tail: 0xffffffc08026d2a0, 0xffffffc080275000
[  0.087323 0 lab_allocator::chaos:44] head: 0xffffffc08026d2a0, tail: 0xffffffc080275000, start: 0xffffffc080275000, end: 0xffffffc08027d000
[  0.091091 0 axruntime::lang_items:5] panicked at labs/lab_allocator/src/chaos.rs:49:9:
add_to_heap

可以看到后续追加的内存与当前程序的堆尾部是连续的，只需要更改 tail 字段扩容当前内存即可。

  1. 初始化以及扩容

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    pub unsafe fn init(&mut self, start: usize, size: usize) {
            self.vec_reserve = (start, start + 96, start + 96 + 192);
            
            self.start = start + 96 + 192 + 384;
            self.head = start + 96 + 192 + 384;

            self.end = start + size;
            self.tail = start + size;

            self.allocated = 96 + 192 + 384;
            self.total = self.end - self.start;
        }

        pub fn add_to_heap(&mut self, start: usize, end: usize) {
            self.end = end;
            self.tail = end;

            self.total += end - start;
        }

  2. 分配

    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
    pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> {
        let vec_reserve_ptr = match layout.size() {
            96 => Some(self.vec_reserve.0 as *const u8),
            192 => Some(self.vec_reserve.1 as *const u8),
            384 => Some(self.vec_reserve.2 as *const u8),
            _ => None,
        };

        if vec_reserve_ptr.is_some() {
            return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
        }

        // check if memory is overflow
        if self.tail - layout.size() <= self.head {
            return Err(());
        }
            
        let ptr = if self.is_even {
            let mem = self.tail - layout.size();
            self.tail = mem;

            NonNull::new(mem as *mut u8).unwrap()
        } else {
            let mem = self.head;
            self.head = mem + layout.size();

            NonNull::new(mem as *mut u8).unwrap()
        };

        self.is_even = !self.is_even;
        self.allocated += layout.size();

        Ok(ptr)
    }

  3. 释放

    1
    2
    3
    4
    5
    6
    7
    8
    pub fn dealloc(&mut self, pos: NonNull<u8>, layout: Layout) {
        if (pos.as_ptr() as usize) < self.start + 96 + 192 + 384 {
            return;
        }

        self.tail +=layout.size();
        self.allocated -= layout.size();
    }

越界访问

第 32 轮分配时发生了 Unhandled Supervisor Page Fault，本机的 panic 位置为 0xffffffc0802005fc，远在可分配的起始地址 0xffffffc08026d2a0 前，猜测本次的 panic 发生在栈区或是发生在从 tail 进行分配或释放时发生的。

说起来很好笑，let mut pool = Vec::new(); 和 items 一样，也会占用一些堆区内存，但因为其只写不读，即使内部全部都是无效的堆内存地址也没有问题。但这提醒到了一点：在分配用于 items: Vec<Vec<u8>> 的堆内存时，使用了一个特判：

1
2
3
4
5
6
let vec_reserve_ptr = match layout.size() {
    96 => Some(self.vec_reserve.0 as *const u8),
    192 => Some(self.vec_reserve.1 as *const u8),
    384 => Some(self.vec_reserve.2 as *const u8),
    _ => None,
};

这几个数字并没有问题，但先前我们忽略了 let a = vec![c; base+delta]; 的 base 总是从 32 开始，每次 alloc 翻倍，delta 则每轮增加 1。恰好， 第 32 轮的第二次 alloc 时那么不恰好的 base = 64 和 delta = 32，这不是 96 了嘛 uwu，所以到这时候，原本该分配给 items: Vec<Vec<u8>> 的地址被当作了 tail 堆的起始地址，又因为 tail 是 tail = tail - size 取得空闲地址，所以结果是越界了。

根据观察后，在 Layout 中存在字段 align，align 字段在 items: Vec<Vec<u8>> 分配中总是 8，而普通分配总是 1。

因此简单写个判断就可以解决了：

1
2
3
if vec_reserve_ptr.is_some() && layout.align() == 8 {
    return Ok(NonNull::new(vec_reserve_ptr.unwrap() as *mut u8).unwrap());
}

处理完这个问题后，算法成功跑到 152 轮。

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
Indicator: 152
[ 25.511024 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015be2, size=0xb8
[ 25.513985 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015b2a
[ 25.516487 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f352a8, tail=0xffffffc085015b2a, size=0xd8
[ 25.519232 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f352a8
[ 25.521127 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015b2a, size=0x118
[ 25.523938 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085015a12
[ 25.525770 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35380, tail=0xffffffc085015a12, size=0x198
[ 25.528492 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35380
[ 25.530458 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc085015a12, size=0x298
[ 25.533267 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08501577a
[ 25.535172 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f35518, 0xffffffc08501577a
[ 25.537270 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f000, size=0x60
[ 25.540115 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f35518, tail=0xffffffc08501577a, size=0x498
[ 25.542925 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f35518
[ 25.544869 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc08501577a, size=0x898
[ 25.547528 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085014ee2
[ 25.549466 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f359b0, tail=0xffffffc085014ee2, size=0x1098
[ 25.552112 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f359b0
[ 25.554013 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085014ee2, size=0x2098
[ 25.558305 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc085012e4a
[ 25.560458 0 lab_allocator::chaos:94] head, tail: 0xffffffc084f36a48, 0xffffffc085012e4a
[ 25.562665 0 lab_allocator::chaos:95] dealloc_memory: pos=0xffffffc08026f060, size=0xc0
[ 25.564900 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f36a48, tail=0xffffffc085012e4a, size=0x4098
[ 25.567790 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f36a48
[ 25.569725 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc085012e4a, size=0x8098
[ 25.572420 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc08500adb2
[ 25.575027 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f3aae0, tail=0xffffffc08500adb2, size=0x10098
[ 25.577664 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f3aae0
[ 25.579570 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc08500adb2, size=0x20098
[ 25.582385 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084fead1a
[ 25.584478 0 lab_allocator::chaos:71] alloc_memory: head=0xffffffc084f4ab78, tail=0xffffffc084fead1a, size=0x40098
[ 25.587429 0 lab_allocator::chaos:85] alloc_memory: ptr=0xffffffc084f4ab78
[ 25.591690 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

预分配：尽可能使用更多的内存

在观察 152 轮和 add_memory 的 log 时发现：

  1. 本轮的偶数区并没有得到释放。
  2. 内存从一开始分配起，每次扩容即为前一次空间 x2，最大为 32 MB。而 qemu 虚拟机分配的是 128MB，只分配到了 32MB，显然还不是极限。
1
pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> { Err(()) }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
Indicator: 0
[  0.088199 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080275000, end=0xffffffc08027d000 # 32768
[  0.090785 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08027d000, end=0xffffffc08028d000 # 65536
[  0.093210 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08028d000, end=0xffffffc0802ad000 # 131072
[  0.095720 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ad000, end=0xffffffc0802ed000 # 262144
[  0.098368 0 lab_allocator::chaos:46] add_memory: start=0xffffffc0802ed000, end=0xffffffc08036d000 # 524288
[  0.100928 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08036d000, end=0xffffffc08046d000 # 1048576
[  0.103497 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08046d000, end=0xffffffc08066d000 # 2097152
[  0.106127 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08066d000, end=0xffffffc080a6d000 # 4194304
[  0.108677 0 lab_allocator::chaos:46] add_memory: start=0xffffffc080a6d000, end=0xffffffc08126d000 # 8388608
[  0.111219 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08126d000, end=0xffffffc08226d000 # 16777216
[  0.114057 0 lab_allocator::chaos:46] add_memory: start=0xffffffc08226d000, end=0xffffffc08426d000 # 33554432 byte = 32MB
[  0.117634 0 axruntime::lang_items:5] panicked at modules/axalloc/src/lib.rs:124:31:
Bumb: NoMemory.

因此，我们可以打第一次 alloc 开始就强迫系统预分配一大堆内存给测例。比如在 pub fn alloc(&mut self, layout: Layout) -> Result<NonNull<u8>, ()> 的合理位置添加下面的代码：

1
2
3
4
// get as much memory as possible
if self.end <= 0xffffffc08426d000 {
    return Err(());
}

修改后，轮数为 189。此时，内存分配量到达了 64MB，这样下来仍有很多剩余空间。

再挤一挤，内存还是有的

看一眼 axalloc 中：

1
2
3
4
5
6
7
8
9
let old_size = balloc.total_bytes();
let expand_size = old_size
    .max(layout.size())
    .next_power_of_two()
    .max(PAGE_SIZE);
let heap_ptr = match self.alloc_pages(expand_size / PAGE_SIZE, PAGE_SIZE) {
    Ok(ptr) => ptr,
    Err(e) => panic!("Bumb: {:?}.", e),
};

不难发现 axalloc 是依赖于 total_bytes() 来判断该扩容多少内存。

简单一些处理，只需要修改原先的 total_bytes 代码，使得 total_bytes 永远返回 0。 

1
2
3
pub fn total_bytes(&self) -> usize {
    0
}

修改后的最终轮数为 245。

也许还会在 我的博客 更新，代码仓库可能会在后续删除，为了不再占用的过多空间，完整代码同样也附带在我的博客里