你们好，我是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已经很难了，题目若再有压力，我会直接躺平。我承认我很脆弱。
话虽这么说，我还是来了。尽管我很晚才开始了解挑战的细节，而到那时，已经有人发掘出了非正常方式。
那时我的反应与群里一位的想法几乎一致：这不就彻底没意思了吗？
但当我亲自上手这个题目时，想法还是逐渐发生了变化。哎真香
纵使前期有些不愉快，最终还是收获了不少快乐与知识。
但倘若你问我，还想不想再玩一次这样的挑战题目的话……
我的回答是否定的。