June 29, 2022
布隆过滤器由一个初值都为 0 的 bit 数组和 N 个哈希函数组成，可以用来快速判断某个数据是否存在。其基本原理是什么？
当我们想标记某个数据存在时（例如，数据已被写入数据库），布隆过滤器会通过三个操作完成标记：
如果数据不存在（例如，数据库里没有写入数据），我们也就没有用布隆过滤器标记过数据，那么，bit 数组对应 bit 位的值仍然为 0。
June 29, 2022
June 29, 2022
June 29, 2022
June 29, 2022
June 29, 2022
链接器的工作流程也主要分为两步：
第一步是，链接器需要对编译器生成的多个目标（.o) 文件进行合并，一般采取的策略是相似段的合并，最终生成共享文件 (.so) 或者可执行文件。
这个阶段中，链接器对输入的各个目标文件进行扫描，获取各个段的大小，并且同时会收集所有的符号定义以及引用信息，构建一个全局的符号表。当链接器构造好了最终的文件布局以及虚拟内存布局后，我们根据符号表，也就能确定了每个符号的虚拟地址了。
第二步是，链接器会对整个文件再进行第二遍扫描，这一阶段，会利用第一遍扫描得到的符号表信息，依次对文件中每个符号引用的地方进行地址替换。也就是对符号的解析以及重定位过程。
这就是链接器常用的两步链接 (Two-pass linking) 的步骤。简单来讲就是进行两遍扫描：第一遍扫描完成文件合并、虚拟内存布局的分配以及符号信息收集；第二遍扫描则是完成了符号的重定位过程。
June 28, 2022
June 28, 2022
June 28, 2022
内核态和用户态的切换依赖栈的切换。操作系统内核在运行的时候，也是需要栈的，这个栈称为内核栈，它与用户应用程序使用的用户态栈是不同的。只有高权限的内核代码才能访问它。而内核态与用户态的相互切换，其中最重要的一个步骤就是两个栈的切换。
中断发生时，CPU 根据需要跳转的特权级，去一个特定的结构中（不同的 CPU 会有所不同，比如 i386 就存在 TSS 中，但不管是什么 CPU，一定会有一个类似的结构），取得目标特权级所对应的 stack 段选择子和栈顶指针，并分别送入 ss 寄存器和 rsp 寄存器，这就完成了一次栈的切换。
然后，IP 寄存器跳入中断服务程序开始执行，中断服务程序会把当前 CPU 中的所有寄存器，也就是程序的上下文都保存到栈上，这就意味着用户态的 CPU 状态其实是由中断服务程序在系统栈上进行维护的。如图所示：
一般来说，当程序因为 call 指令或者 int 指令进行跳转的时候，只需要把下一条指令的地址放到栈上，供被调用者执行 ret 指令使用，这样可以便于返回到调用函数中继续执行。但上图中的内核态栈里有一点特殊之处，就是 CPU 自动地将用户态栈的段选择子 ss3，和栈顶指针 rsp3 都放到内核态栈里了。这里的数字 3 代表了 CPU 特权级，内核态是 0，用户态是 3。
当中断结束时，中断服务程序会从内核栈里将 CPU 寄存器的值全部恢复，最后再执行"iret"指令（注意不是 ret，而是 iret，这表示是从中断服务程序中返回）。而 iret 指令就会将 ss3/rsp3 都弹出栈，并且将这个值分别送到 ss 和 rsp 寄存器中。这样就完成了从内核栈到用户栈的一次切换。同时，内核栈的 ss0 和 rsp0 也会被保存到前文所说的一个特定的结构中，以供下次切换时使用。
June 27, 2022