Linux内核已经合入了EEVDF调度器（这该怎么翻译啊？）用于替代任职多年的CFS调度器。我对调度这种宏观且复杂的算法一直感到敬畏，还是先了解一下基本思路吧。 论文全名及链接：Earliest Eligible Virtual Deadline First : A Flexible and Accurate Mechanism for Proportional Share Resource Allocation。 TL;DR 一句话总结就是：调度资源只会分配给 具有合格的（eligible）最早虚拟截止时间 调度请求 的任务。 引出问题 这部分和EEVDF基本无关，但这是作者...

布谷鸟过滤器（cuckoo filter）的实现挺有意思，花点时间看下论文是值得的。 为什么需要它？ 布谷鸟过滤器解决了布隆过滤器（bloom filter）不支持删除操作的问题，同时具有低误报率、高空间利用率和缓存友好的特性。 Cuckoo hashing 开始之前先介绍下布谷鸟哈希（cuckoo hashing）算法。这个算法先说疗效：在不需要完美哈希的前提下，也可以做到最坏\(O(1)\)时间复杂度的查找操作。对比之下，常规哈希算法是期望\(O(1)\)，最坏\(O(n)\)的时间复杂度。因此这个特性对于高频读操作的场景来说是相当合适。 当然，这是有代价的，布谷...

前言 本文介绍简化的C++内存模型，涉及到memory order，modification order和release sequence等概念。虽然内容对于C++标准有所删减，但我希望相比C++标准和cppreference都更易于理解。 问题 先给出一个问题：如果有2个线程并发执行以下代码，结果是否正确（断言assert是否为真）？ int val; bool flag {false}; void writer() { val = 1; flag = true; } void reader() { while(!flag); assert(...

粗略看了西半球最快内存分配器mimalloc的论文和源码，这里简单做点笔记。本文是论文阅读篇。 亮点 论文Mimalloc: Free List Sharding in Action提到mimalloc跑得快的设计要点有三处： 使用三种页级本地（完全无锁）链表并实现分片，提高局部性和避免竞争。 高度调优的快速路径，路径尽可能短且少分支。 可预测的周期性维护操作（temporal cadence），可以用于批量处理（比如延迟释放）。 这些策略使得mimalloc分别比高性能的tcmalloc和jemalloc还要快7%和14%。 设计动机 mimalloc当初是为...

这是去年NVIDIA stdexec作者Eric Niebler在油管上的live coding：一小时教你实现低配版std::execution。如果你想了解std::execution标准库的设计但是没耐心翻阅一百多页的P2300，那可以先看下这里。原视频：Working with Asynchrony Generally: From Zero to Sender/Receiver in ~60 Minutes What is it? 什么是std::execution？你可以理解为一个标准的异步编程模型，旨在让整个C++社区都使用这套方案来描述异步计算。这种模型可以让你...

前言 上文已经做了论文阅读以及mkfs.f2fs初始化调研，现在我们从内核的角度来看F2FS的运行时是怎样的：包括文件的创建和读写、GC以及崩溃恢复。如上文所述，使用的源码是早期commit，代码的稳定性相对于现在肯定是不足的，但这样更易于理解论文提到的若干特性 文章话题涉及比较宽泛，本人才疏学浅，如有错误还请指正 Initialization 上文分析过mkfs.f2fs的格式化行为，到了内核部分则通过mount()实现从VFS到具体文件系统的初始化，简单来说就是解析外存的数据结构。下面附上f2fs.txt对关键数据结构的简要说明： File System Metadata ...

前言 上文通过阅读论文的方式对F2FS进行了概括性的总结，本文进一步通过源码分析的方式来理解F2FS。一方面我们可以通过调研F2FS的早期commit来上路，另一方面也可以通过对应时期的mkfs.f2fs工具来了解一个文件系统的初始化状态。虽然这些代码的稳定性相对于现在肯定是不足的，但这样更易于理解论文提到的若干特性。这篇文章先了解一个格式化的F2FS的磁盘布局（即它的初始化状态），我们通过调试内核以外的mkfs.f2fs工具源码来展开细节 Overview: On-disk layout 上文提到F2FS的布局是分为6个area，如上图所示。那么它的初始化状态是怎样的？这里可...

前言 首先F2FS也不算新文件系统，迄今已超过10年了，但不妨碍它在闪存设备领域的流行 然后我其实没怎么看论文，而是听作者的演讲，也没人规定论文一定要看文字对吧 背景：为什么需要F2FS 主要是随机写对flash设备不利。随机写的性能低于顺序写是常识了，但还有一个原因是影响设备寿命，这是由flash的物理特性决定的弊端，需要FTL完成写前擦除操作，随机写就是放大弊端 进一步的考虑就是要做一个面向顺序写（具有磨损均衡特性）的文件系统，而这就是F2FS 设计思路与主要特性 Flash-friendly on-disk layout Cost-effective ind...

前言 内核bringup有些地方没看懂，也没打算看得有多懂。起码基本的语法要了解一下吧 基本背景 链接脚本（Linker Script）可用于定制链接过程，我认为最重要的还是它可以描述一个二进制程序的内存布局，这个二进制程序自然也包括内核映像（kernel image） ENTRY ENTRY描述一个程序的入口。在x86-64环境下，vmlinux.lds.S中定义入口为phys_startup_64 #ifdef CONFIG_X86_32 OUTPUT_ARCH(i386) ENTRY(phys_startup_32) #else OUTPUT_ARCH(i386:x86...

前言 本文覆盖三个话题： 通过RFC5681了解TCP拥塞控制算法做出的硬性要求 通过Congestion Avoidance and Control了解TCP Tahoe和TCP Reno的算法细节 通过Linux Kernel（版本v6.4.8）梳理TCP NewReno的具体实现 RFC5681 必要算法 RFC5681描述的拥塞控制就是经典的四个阶段： 慢启动 拥塞避免 快速重传 快速恢复 但该提案只要求一个拥塞控制算法必须实现慢启动和拥塞避免，其实现允许更加保守，却不能更加激进 变量维护 在慢启动和拥塞避免阶段中，实现算法需要为...

前言 RFC6298讨论重传定时器相关的算法。因为首次涉足内核协议栈实现时，注释里总是提到各种RFC，因此需要过一遍。对于文中提到的MUST，或者SHOULD，将会用颜色标注；其它仅强调的语气（MAY）会加粗处理 背景介绍 RFC1122指出，RTO的计算方式应当遵循Jac88 [Jac88] Jacobson, V., “Congestion Avoidance and Control”, Computer Communication Review, vol. 18, no. 4, pp. 314-329, Aug. 1988. 而RFC6298要求发送端使用这些算法...

前言 符号是讨论编译链接过程的中非常特殊的概念，随便写都能用，乱写却会引发血案。但麻烦在于并没有多少足够系统的资料去讨论这些问题，于是不得不花了一堆时间去整理这些支离破碎的知识 大纲 我还没想好具体怎么组织这篇文章（因为博客缺了一篇介绍ELF的文章，后面补上），讨论内容有： 符号本身的概念，比如binding和visibility ELF文件中的符号，重点关注它是怎么组织和寻址的 符号的解析和重定位，以及关于符号介入的关键特性说明 不同编译器下未初始化变量所生成的符号 （cppreference肯定不会说的）C++能控制的符号特性 内容本身虽然是技术细节，...

前言 保命声明：标题是原封不动从paper抄过来的，非本人立场 mmap和read/write谁更适合文件IO已经是个日经问题了，与其嘴炮不如看下别人的调研和求证，这样子嘴炮就可以更加有理有据了！ 这篇paper主要探讨的是mmap应用于DBMS中作为buffer pool是否合适的问题，但也指出了mmap的潜在问题，所以非DB选手（比如我）也是适合看的 先说结论 通过实验的方式，对比mmap和传统的文件IO方法在不同的访问模式和存储设备上的性能差异，发现mmap在大多数情况下没有优势 mmap的性能问题在IO本身之外 至少给出了2个mmap的不适用场景： ...

导读 本文首先从背景和架构上简单介绍blk-mq框架，随后会通过数据结构和具体流程去更加深入了解该机制的内部实现 背景 什么是blk-mq The Multi-Queue Block IO Queueing Mechanism is an API to enable fast storage devices to achieve a huge number of input/output operations per second (IOPS) through queueing and submitting IO requests to block devices simulta...

Repository 仓库地址：Legcay Executors Overview 东西不多，参考的是P0443R9，不是P2300这种复杂的库 总的来说就是完成三个模块： 实现require/query的非侵入定制点 以及lightweight executor和applicable property的交互 对持有相同property的executor做类型抹除以支持多态的polymorphic executor （其实还有一个赠品线程池，因为提案写了） 对于executor的property，库内已集成： property...

前前言 这是一篇翻新的旧文，自己回顾用。另外，标题风格只是neta某本CS经典书籍，没别的意思 前言 我并没有在搜索引擎上找到“内存的类型”这个关键字，有点困惑为什么前人不做点总结。或许是资料上比较零碎，因此打算自己写一篇。至于“自顶向下”，其实是指从简单的工具来展开这个话题。如果是自底向上，那关于内存的话题可能永远说不完了 工具 我们关心常用的工具：比如free / top / meminfo free 最简单的莫过于free，它提供的信息基本就是top上内存相关的信息 caturra@LAPTOP-RU7SB7FE:~$ free -tl ...

前言 为了提供最佳的用户体验，AOSP在user space层面上做了非常深入的定制及优化，进程管理也不例外 本文尝试从进程本身及其生命周期角度去描述AOSP众多的进程管理机制，包括：进程状态及其容器、oom adjuster、memory factor和userspace lowmemorykiller 文章话题涉及比较宽泛，本人才疏学浅，如有错误还请指正 进程的启动 先说明一点，Android本身大量使用server/client模型，并通过socket/binder等IPC机制进行通信。通常来说，用户使用的application就是client，而OS/framework...

前言 最近在翻asio内部有啥好东西，看到很有意思的代码就顺手做下笔记 这篇文章简单描述asio怎样实现一个无栈协程 switch-case基础 首先，switch-case语法应该是C语言中的基础；其次，goto语法也是C语言中的基础。goto后面衔接的是label，而switch语法中的case也是一种label 那意味着什么？意味着可以飞线 #include <iostream> using std::cin; using std::cout; using std::endl; int main() { int a; cin >&g...

TL;DR 在类设计含有多重继承的内存布局下，对象的this指针是存在编译器隐含的偏移修正行为 现象如下： 首个base class并不需要修正，因为内存布局与derived class是重叠共用的，无论有无vptr的介入 其它base class由编译器修正this指针，需要付出轻微的运行时成本（多一条加法指令） 如果derived class隐藏了base class的函数，那调用时无需修正（因为调用的是derived class实现的函数） 对于含有非首个base class且具有virtual函数的base class，函数调用时this指针将通过访问no...

实现一个xyz系列算是本博客的月指活了，这次写的是lockfree容器（硬核程度越来越高，以后咋低成本水文章啊）。 声明 不建议自己从零造lockfree轮子，至少需要有paper支撑，或者从已有的项目中改进，不然代码的正确性基本没有任何保证。为此本文参考了模板库boost::lockfree的实现以及MS Queue的paper（Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms）。 另外本文实现的容器只关注lockfree部分。因此，作为类设计就是不及格的，比如完全无...

前言 这篇文章会介绍CFS的基本原理并从源码上分析流程 文章的解说顺序是按照我看源码的顺序展开的 阅读理解的友好度应该还可以，毕竟我都能看懂 基本设计和公平调度 CFS的实现在文件fair.c中，毕竟全称是Completely Fair Scheduler 那怎么才算fair？你可以通过看作者对CFS的介绍（sched-design-CFS.txt）来了解，我在下面也做了点总结： 作者希望模拟一个理想硬件，即使是单cpu，task也是可以并行处理的（假设有2个task，那就同时刻均分50%的cpu计算能力） 而对比真实硬件，一个task在执行，另一个task就...

（诈尸氵一篇meminfo） 文章还处于work in progress状态，先直接从OneNote上复制过来吧 示例 meminfo的分类有： MemTotal: 16642364 kB MemFree: 9337232 kB Buffers: 34032 kB Cached: 188576 kB SwapCached: 0 kB Active: 167556 kB Inactive: 157876 kB Active(anon): ...

写了一个C++实现的raft，这里就简单做些记录 repo github/Caturra000/cxxraft 实现raft要用到一些基础库，当然也要自己写了： json库 日志库 协程库 RPC库 参考 参考资料主要看raft paper，前人踩过的坑我没有意识到，但其实paper里面都有提 raft paper不只是paper，还是非常好的实现参考手册。细节上的推敲比前司的代码注释还要靠谱多几倍，我以后写文档能有这水平该多好 测试是通过适配MIT-6.824的test_test.go文件来完成。但是由于它们是lab形式，改造成本那是相当大（后面实...

当你想造一个轮子时，你发现需要为这个轮子再造另一个轮子 曾经我抱怨前司的项目写个RPC要搞一堆IDL，因此在一年前就造了个RPC轮子sRPC作为一个想法上的验证。但是用着就觉得不好，于是又迭代了全新的RPC轮子tRPC。不过这个目的不一样，这是冲着造raft轮子来预热的，虽然raft估计还要过个半年一年才能挤出点时间看论文写测试 写的时间不多，就几天，因为基础库（协程、网络、json）都是我前面已经写好了的，轮子多了迭代也就快了。写都写完了就不介绍了，剩下的部分由github里的README补充吧，我copy过来了 TL;DR 一个RPC库，是对我以前造过的轮子sRPC的...

前段时间抱着玩票的性质搞了个协程库co 然后打算把它合并到鸽了一年的future网络库fluentNet 协程的适配 可这是2种不同的异步实现方式，说要适配协程，我也没啥好思路，不妨理一下： 网络库用到的promise / future本身仍是一个线程内event loop这种操作，它每一个控制流本身仍是函数 协程库没有做hook，就是协程原语resume / yield的实现，能把你的函数拆成多个控制流 这么看，不如把future内的回调从函数单体改为协程单体，在仔细想了一下，似乎只需要在loop的时候加点轻微的改动就好了 这样子，future内的控制流都可以...

这篇文章用来分享我早段时间随便搞出来的协程轮子，实现放在github了：co 我本不想写这篇文章，看代码(RTFSC)就很足够了 我认为技术分享不是问题，但是现在没啥好分享还非要我分享，我觉得这公司很有问题 写都写了，那还是无责任放出来吧，内容质量我不管 随便指的是轮子本身造的简单，而不是说我写bug很随便 什么是协程 可以认为是用户态的线程，但是上下文切换的时机是靠调用方自身去控制 其控制上下文的原语有：resume恢复和yield让出 从表面上来说，就好像一个函数的控制流可以随意分拆一样，既单个线程也能做到并发 void print1() { s...

前面的文章（已删除）提到一些语言抽象层面级别的并发接口 正如上文所说，语言层面就不应该看实现 但是特定体系下，就是需要看实现是怎么干的 如果要涉及到硬件实现，可能会脱口而出OOO乱序执行、store buffer、缓存一致性协议等关键字 不妨先理顺一下它们的关系 Q1. 缓存一致性协议影响并发吗？ TL;DR 只论MESI协议是没有影响的，因为该协议是强一致性的 当你在考虑并发时想到这个东西，那你的方向错了 Q2. store buffer和缓存一致性的关系？ TL;DR 前面提到，MESI缓存一致性协议是强一致性的，cache与cache间，cache与memor...

看memory management永远不知道水有多深 从哪里开始——内存探测 如果kernel不知道当前物理内存的信息，那么内存管理就无从谈起 可以通过BIOS探测得到物理内存的布局，这个内存探测模块称为E820 得到的内存可以是杂乱无章的信息，以三元组<start, length, memory type>的形式来记录每一段内存 E820所做的只有收集，其它不管，因此你得到的信息是杂乱无章的 总之你探测到的就是一堆三元组 初步的整理——memblock memblock / bootmem是启动初期的内存分配器，其实也只是简单整理上面E820给出的内存...

前言 本文贴一些ptmalloc（glibc2.31版本）简单的参数，以及用到的便利函数 有必要说明一下，作者对这些取值的解释基本都是in practice（也有少数是必要的设计），因此也不用过于纠结，见识一下吧 背景 这里就不介绍ptmalloc的完整设计了，一方面是自己也没时间全部分析，另一方面是网上挺多优质介绍的 我目前对ptmalloc里的数据结构做了一些简单RTFSC分析，和下面的内容强关联，感兴趣也可看看： malloc at master · Caturra000/RTFSC · GitHub 最小大小 /* The smallest size we c...

前言 这篇paper的主要价值就是设计一个无敌的分布式KV 注1：对你没看错，是memcache而不是memcached——memcache指facebook设计的分布式缓存层服务，而它只是底层选用了memcached实现（理论上，换成别的完全ok） 注2：虽然facebook已经换了名字，但是文章仍然采用facebook的称谓 读多写少的系统 通常互联网服务大多为读多写少的场合，facebook作为全球最大的社交网络也不例外 “全球最大”既包括当年论文发表时的时间点，也包括本文发表时的时间点 facebook给出的数据是：读请求相比写高出2个数量级...

CSAPP第7章就是用来讲解链接过程的，不算深入但了解全面，适合整理总结，因此做一遍笔记 什么是链接 如果了解目标文件的概念，那么链接过程就是从编译过程拿到的可重定位目标文件中生成出可执行目标文件 为什么需要链接 链接使得分离编译成为可能。如果平时写的是小项目，那你可认为是没有必要，杀鸡焉用牛刀；但是大型项目中，分离编译可以大量提高编译效率，充分利用并行性能。另外，模块化在现实世界中是客观存在的 为什么需要了解链接 以下理由： 避免踩坑 它会影响性能（轻微）和内存开销，你需要斟酌什么情况下使用 它有一些特殊的feature，比如hook，你可能会用到 ...

前言 Linux内核中的elevator layer就是IO调度层 之所以把IO视为电梯，是因为它的物理特性和生活上的电梯差不多： 消费者（电梯）远跟不上生产者（乘客等待上下楼）的速度 寻址方式说是随机访问（到哪都行），但其实条件苛刻（反方向哪怕只差一个楼层，也可能等半天） deadline是elevator层中提供的一种具体调度算法，它只需实现elevator通用框架提供的一些接口即可 选deadline作为本篇主角的原因是： 这个比较好懂（CFQ BFQ写的什么鬼） 知道IO优化面临的问题，和对应的解决方案 流程较短，顺便了解一下block ...

前言 好的设计适合用图描述，并且能做到「不言而喻，一目了然」，因此尝试用UML来描述libstdc++实现 一些注意点： 图比较大，文章用的是SVG格式，你可以通过链接看到高清原图 一些大家都知道的公有函数不一定会写上，因为这里填上函数名是为了方便跟踪用的 图要看，代码也要看，这才称得上是健全 源码和注释 请看这里：GitHub/Caturra000/RTFSC/libstdc++ shared_ptr 高清大图 TODO: 尚未添加weak_ptr和enable_shared_from_this的结构 从图中可以看到： 并发安全的处理，线程安全...

本来是想把整个Linux IO栈都大概整理一遍，限于工作繁忙，也只是把VFS往下一点的流程粗略翻了遍 下面会做一些简单的总结，由于说来话长，我不打算把每一处都说的特别详尽 毕竟（优质的）代码才是最好的文档 源码和注释 原始的记录都在这：RTFSC/linux/fs at master · Caturra000/RTFSC · GitHub 分类不一定很准确，像block mapping和elevator我也放到fs下了 mount 在mount前，内核其实已经注册好对应的文件系统信息file_system_type 因此给定一个字符串字面值fstype也可以在全局...

这是EP8剧中贝伦给出的推理游戏，整个流程非常短，有点意思，并且已经比主线中的文字游戏简化太多了，我就花了点时间摘抄下来 角色分类 可分为： Game master：贝伦 玩家：玩家战人和贝阿朵莉切 棋子：共计17人 堂兄妹4人：战人、让治、朱志香、真里亚 父母们7人：留弗夫和雾江（战人的父母）、秀吉和绘羽（让治的父母）、藏臼和夏妃（朱志香的父母）、楼座（真里亚的母亲） 医生1人：南条 佣人5人：源次、熊泽、乡田、纱音、嘉音 场景 游戏外的为上位世界，讨论方为Game master和...

性能优化的关键在于解决性能的瓶颈，而IO从来都是难以解决的瓶颈之一 这篇文章主要描述Linux Kernel对于读操作下的按需预读算法，包括流程和实现 基本的IO优化策略 在开始说预取算法前，还是要看一下常规的IO优化策略 避免IO，常见的缓存策略其实就是避免（外存）IO，不涉及IO就没有IO问题 顺序IO，显然，顺序访问比随机访问要快，如果多IO负载下无法完全顺序执行，那就增大IO的大小，减少寻道定位，提高吞吐量 异步IO，CPU和磁盘同时工作，把所需的数据提前载入内存 并行IO，通过RAID实现并行IO 然而，对于一个常规的应用来说，其IO行为是小且串...

前言 有一种类型叫pure virtual，不仅多态，而且强制要求Base类不做实现（子类必须override），只声明为接口，实现了接口语义 但有时候并不需要多余的多态，我就需要一个类做接口声明 C++作为追求zero overhead的语言，能不能做到完全不必承担virtual开销的接口语义？ 那当然可以，只要你能折腾 PS. 全文废话非常多（如果不愿意看这个东西是怎么来的），解决方案只在正文最后一段 期望 期望自然是做到接口语义，伪代码如下 class Interface { DEFINE int func(); DEFINE void func...

前言 使用位运算写flag是一种很直观优雅的做法 比如flag = flagA | flagB | flagC 这里flag是一个简单的bitmap，一般用unsigned int的简单类型表示 但这个问题在于： 类型限定，你只能是操作一些位，一般是整数类型或者布尔类型 范围限定，范围取决于flag的最大值，毕竟就是一个值 单一类型，能否把位运算用于不同类型，也就是说，允许任意多类型绑定 那这些问题能不能全部解决掉，实现一个动态类型的bitwise or？ 期望 已知C++标准库已经提供了std::tuple，期望实现代码如下 // 假设 typen...

需求 我本来只想写一个一两百行的简单的日志库用于辅助排查错误， 谁知道轮子越造越复杂 轮子 实现文档和使用说明都挂到github上了，基本思路就是模板元编程和双缓冲 我觉得代码实现上还挺有意思的，只是目测没人愿意看，本身可读性还是挺低的 github/caturra000/dlog 至于标题所吹嘘的性能，我在readme最后贴了个benchmark，和同期的glog和spdlog都比了一下 相关文档 dlog的设计 dlog的优化技巧 dlog的policy使用和定制 元编程在dlog的应用和实现 还能更快吗？ 虽然堆了不少优化上的小伎俩，但是也不一定比得过专...

由于日志库的需求，需要一个编译时排序来处理tag（模板的typename只能append!），所以尝试写了一版，工地C++选手头一回写这么一大串的template元编程 接口/目标 注意要实现的是基于类型的排序， 就是给定各个类型不同的优先级，然后给不同的类型排序，直观上就是一个key(type)和value完全倒置的排序 假设已知各个类型Ts...的优先级，期望的接口是 Sort<Ts...>::type返回一个排好序的Us... 由于type必须是指定某一个类型，因此我使用了std::tuple Sort<Ts...>::type = std:...