Conzxy's blog

Kanon(二)：Reactor模式 概念Reactor直译为反应器/堆，之所以这么起名我想是因为Reactor模式是一个对触发事件反应的事件处理设计模式。Reactor通过事件解多路复用器获取多个准备就绪的输入源，然后根据每个输入源的请求（即触发的事件）分发到具体的事件处理器。因此Reactor模式的核心就是事件分发。 Reactor可以说是网络同步并发模型最广泛被使用的，比如libevent，redis均采用了该模型。与之相对的是”真正“异步的Proactor模式，这个被ASIO采用。对于Unix/Linux等Unix-like平台而言，更为偏爱Reactor，因为它们提供的多路复用API就是同步的，而对于Windows的IOCP而言，更适合于Proactor。 由于kanon暂时不考虑跨平台，所以采用Reactor不需要考虑如何兼容Windows的IOCP。 组件根据Wikipedia，Reactor模式由以下构成： Resources：提供输入或消费输出的资源，对应的是Socket fd。 Synchronous Event Demultiplexer：对应的是select ...

Kanon(一): 概述 kanon是个人编写的基于Reactor模式的事件驱动型网络库。kanon不是单纯的事件框架而是网络库，是因为它同时也管理读写缓冲，用户无需关心收发逻辑。由于这个特性，从用户的角度看待，事件处理是异步的。kanon暂时不支持跨平台，仅适用于linux和unix-like平台。同时，仅支持tcp（如需支持udp, kcp等协议可以扩展） 模块划分 Thread：封装了POSIX线程接口，抽象为：Thread, Condition, Mutex，同时在其上实现了其他常用同步设施：RWLock, CountdownLatch，以及线程池。 Log：日志包含时间戳，进程号，日志级别等，同时支持异步写入文件 String：提供字符流（lexical_stream和fmt_stream，以及字符串工具（StringView） Network：最为核心的模块，包含Reactor组件（Channel, (E)Poller, EventLoop），定时器，封装好的TcpServer和TcpClient等。 使用方式该库主要提供回调注册API来处理各种IO事件，基本上用户只需 ...

std::enable_shared_from_this源码原理剖析声明：之前已经踩过一次坑了，也稍微了解了一下boost的实现机制，这次又踩了一次（主要是惯性），于是去翻了下gcc9的实现，思路相同，但是实现手法不一样，遂记录一下 源码版本我查看的是我的Ubuntu自带的版本：gcc9.3源码位置在/usr/include/c++/9，如果是使用Linux系统的话，应该差不太多。 通过memory可以知道关键代码在的头文件是bits目录下的shared_ptr.h和shared_ptr_base.h。 问题提出1234567891011121314class XXX : std::enable_shared_from_this<XXX> { XXX() = default; void f() { //... }};int main() XXX x{}; x.f(); // Ops! Throw std::bad_weak_ptr} std::enable_shared_from_thi ...

Hash Index声明：此为2021 CMU 15-445 Lab2，实验任务为完成Extendible Hash Table相关设施的编码 Extendible Hashing（以下统一译为“可扩展哈希”）静态哈希策略因为其桶数量是固定的，因此必须要用到溢出桶（overflow bucket），不能应对数据库文件大小的变化。可扩展哈希作为动态哈希策略，可以针对数据库文件的大小变化而进行桶（bucket）的分裂和合并，并且开销能够接受，理由下面解释。 基本构成可扩展哈希维护一个全局深度（global depth，以下简称为gd），并为每一个桶分配局部深度（local depth，以下简称为ld）。可扩展哈希表当前的桶数量为$2^{gd}$。如果此时存放记录的页（以下简称为页）和每个桶一一对应，这很符合认知。如果页的数量比桶的数量要少，那么必然有多个桶为指向同一个页，同时要让落到这些桶的记录的哈希值相同。可扩展哈希是通过将记录的哈希值的前缀与桶关联来达成这个目的。这样一来，哈希值是00前缀的都会指向同一个页，并且随着gd的变化也不会变化，也就是说在扩容的时候我们不需要处理它们的再分配（ ...

链接与库 最近复习了csapp第7章：链接的相关内容（主要是印象太浅了），加上最近在编译和链接库的时候遇到了一些问题，故还是记录一下。这章涉及到的关键概念不少, 包括但不限于： Symbol ELF（相信做过6.828的不会陌生） Symbol resolution Relocation static linking dynamic linking shared library interpositioning 链接csapp给出的定义是： 聚集和组合各个代码和数据到一个文件，该文件可以装载（loaded）到内存中并执行的过程而这个过程可以发生在： compile time（static linking） load time/run time（dynamic linking） 说到底之所以需要linking，是因为它使得开发软件可以将每个源文件分开，从而避免了将所有东西塞到同一个文件，导致可维护性极低（说白了就是XX）（我不知道其他语言如何，至少对于c/cpp是如此的）。即所谓的分离式编译（separate compilation）。 我不是很想谈及学这玩意有什么用，如果你 ...

关于noncopyable和STL容器的思考 cpp中的资源管理类，甚至绝大多数类都不应该允许拷贝，其理由有 拷贝是值语义，前后的对象是没有关联的，而我们往往打交道的是对象语义，为了保证语义不被破坏或滥用，我们应该禁止拷贝。 同时，因为编译器的默认拷贝实质上是(memberwise)的，也就是说并不是真的拷贝资源，而是让这两个类拥有相同的成员，如果成员是用户自定义类类型并且拷贝行为正确，会调用其对应的拷贝函数，问题不大，但是在C语言中有很多用内置类型表示资源（比如文件描述符和文件指针），还有就是结构体本身也是没有拷贝构造/复制函数的（这种情况表现为bitwise，即逐字节拷贝），这样就可能导致会出现资源释放两次这样的诡异现象存在，而这些你也不可能不与之打交道（实际这是绝大数cpp程序员都需要经历的）。 因此如果一个类真的需要拷贝语义，那么应当显式提供Copy()API，因为我们的目的就是禁止编译器的隐式行为，这点在google code style中也有提及。 12345678910111213141516171819202122232425262728293031// In C+ ...

关于读写锁粒度的思考 在写extendible hashtable的过程中，对于其并发控制中读写锁的粒度选择一事感到困惑。 在数据库事务并发控制中，有三种冲突需要避免（根据隔离级别，可以选择哪些也可以容忍）： unrepeated read（读 -> 写） overwrite（写 -> 写） dirty read（写 -> 读） 但是相比事务而言，数据结构的操作相当于只有一个操作的事务，因此第一种和第三种其实是可以容忍并由事务的并发控制去管理。 但是对于(写->写)这样的操作顺序，却很可能导致出现问题，破坏不变式 比如Insert()在读完direcotory的数据之后，将读锁释放，此时bucket是满的，调用SplitInsert()就需要上对应bucket的写锁（对于bucket都有一个读写锁以减少争用），但是如果上在directory的读锁释放后bucket的写锁前这个时间点就被切出线程到另一个线程也调用Insert()并且key是同一个bucket的，那么就会导致切回来bucket已经不是原来的bucket了（相关的断言也会触发），之后的处理也应视作 ...

Lab1: Booting a PC Part1 PC BootstrapGetting Started with x86 assembly整个实验使用的汇编语言都是x86，因此需要了解x86的语法和一些技巧。需要注意的是使用语法格式是AT&T风格而不是Intel风格，具体来说，一个显著的区别在于： 12mov src, dst # This is AT&T stylemov dst, src # This is Intel style Simulating the x86实现环境不采用实机而是通过QEMU模拟器，更为方便。QEMU可以提供远程调试模板，这个在之后的跟踪内核启动指令有用。 通过make生成内核映像（obj/kern/kernel.img)，它包含两部分：boot loader(obj/boot/boot)和kernel(obj/kernel)，然后通过QEMU加载该映像启动内核。 实现提供了一个Makefile文件，里面有准备好的命令，敲入make qemu就能启动PC了：退出方式：Ctrl+a x现在内核提供了一个显示器（Monitor），可以接受键盘 ...

ForwardList 实现事先声明：本人并未参考STL实现，仅根据cppreferece的描述进行编写，且增加了我个人觉得方便的API，我是因为觉得std::forward_list<>不好用才打算写一个自己的 设计首先，ForwardList是带哨兵（header）的单向不循环链表（循环对于单向没啥用），std::forward_list<>估计也是如此，因为有std::forward_list<>::before_begin()。 之所以带哨兵，原因数据结构也学过：简化操作，可以减少一些边界条件的判别 这里还有一个好处就是哨兵维护一些元数据（metadata）。 标准库为了遵循zero-overhead原则，没有维护总结点数，也没有维护header的前一节点（previous）。 你可以通过下面的代码验证： 12std::forward_list<int> list;static_assert(sizeof list == 8, ""); 可是在很多情况下，这两个元数据很有作用，若要自己维护，显得多余，而且pr ...

条件变量的问题&参考回答 Q1: Why need while() instead of if() when calling pthread_cond_wait() A1: 因为可能会导致假唤醒（spurious wakeup）。设想一种情景，比如生产者消费者问题，有多个消费线程在等待,当一个消费者（C1）将被唤醒时，此时另外一个消费者（C2）可能抢占（preempt）这个信号，而C2很可能消费了C1应消费的，从而导致C1可能出现UB行为（比如assert保证此时有资源可供消费），这种情景应该继续sleep，用while进行多次判断从而避免单次判断带来的假唤醒。 Q2: Why need mutex when calling pthead_cond_signal/wait() A2: 共享不强制要求互斥，但互斥需求是常有的，条件变量也不例外，其关联的变量往往也有互斥需求，需要保证其操作是原子的。设想如下情景：当调用wait()要sleep时，突然中断或异常发生，上下文切换到其他线程，并且调用signal()，然后再切换回原来的线程，那么这个线程很可能就没有其他线程可以唤 ...