文章

UNIX环境高级编程（APUE） TCP-IP详解卷2：实现 TCP&IP网络编程

思路 被这个实验折磨了两天，可能是2024新出的一个实验内容，网上资料少，参考了一篇仅有的博客，吭哧吭哧分析出来了个大概吧…在此记录一下，以便帮助有需要的人。 attack xv6的ans只有几行代码，根据实验描述，大概能猜到是secret程序结束之后，attack程序复用了它的物理内存，然后读取之前写入内存中的密码。难点在于我们如何定位到那段内存。 在开始之前直接先给出ans，可以看到代码是很简单的： #include "kernel/types.h" #include "kernel/fcntl.h" #include "user/user.h" #include "kernel/riscv.h" int main(int argc, char *argv[]) { // your code here. you should write the secret to fd 2 using write // (e.g., write(2, secret, 8) char *end = sbrk(17*PGSIZE); end += 16 * PGSIZE; write(2, end+32, 8); exit(1); } 下面说说实验思路，实验目的是找到被复用的物理内存，而内核的物理内存使用栈式链表管理（kalloc.c），secret程序通过kalloc从栈顶取内存页来使用，程序结束后通过kfree将这些内存页放回栈顶。到attack运行的时候同样使用kalloc从栈顶取内存页，因此就给了attack复用物理内存的机会。 值得注意的是，secret分配内存时这些页的出栈顺序，不一定与attack分配内存时的出栈顺序相同，比如secret分配页的顺序为1,2,3，归还的顺序为2,3,1，那么此时栈顶到栈底的页分别为1,3,2，当attack来分配的时候，拿到页的顺序就是1,3,2。因此核心在于分析程序运行时物理内存页的分配以及回收顺序，才能知道attack应该到哪块内存中获取密码。 fork secret 我们从attacktest中的第一个fork开始分析。 fork调用了allocproc来创建proc，allocproc中首次使用了kalloc为p->trapframe分配一页物理页。 接着allocproc调用proc_pagetable创建页表，其中，先调用uvmcreate使用kalloc为根页表分配一页： 然后为trampoline和p->trapframe建立映射，这两页在最虚拟内存的最高地址处，处于同一个三级页目录（xv6使用sv39，即三级页表），因此又kalloc了两页，分别对应一页二级页表、一页三级页表： 因此allocproc一共创建了4页（trapframe、三级页表）。 回到fork中，由于此时xv6的fork还没实现copy on write特性，因此需要把父进程用户内存中的内容（用户内存即stack、heap这些低地址内存，不包括trapframe、trampoline）使用uvmcopy全部复制到子进程中。此时父进程用户内存占用此时为4页，因此子进程也复制了这4页进来，由于这4页位于虚拟内存中的低地址，其二级三级页表与trapframe/trampoline的都不一样，所以还会创建两页分别用于二级三级页表，一共kalloc了4+2=6页（为什么是4页具体原因在后面分析exec时会揭晓）。 综上，fork一共分配了4+6=10页。 exec secret 然后就是执行exec： 在exec的实现中，会使用proc_pagetable创建新的页表来替换旧页表（这个也好理解，因为exec目的就是替换整个程序镜像，相当于从头开始执行一个新的程序，之前程序的相关内容全部丢弃）。根据之前的分析，proc_pagetable会分配3页。 接着，exec遍历elf文件的program header，将所有LOAD段加载进内存中。具体是通过uvmalloc分配物理内存，loadseg将段加载进内存。xv6程序的elf文件包含两个LOAD段，data段和text段，可以通过readelf看一下： ...

primes 比较容易想到的是递归的做法：主进程生产2 ~ 280这些自然数通过管道传输给子进程，子进程读取并将第一个数作为素数输出，剩下的数用该素数作为筛子来筛选，没有被筛除的数就输入管道，输入给下一个子进程，下一个子进程重复上述步骤。 #include "kernel/types.h" #include "user/user.h" void sieve(int in_fds[2]) __attribute__((noreturn)); int main(int argc, char *argv[]) { int fds[2]; pipe(fds); if (!fork()) { sieve(fds); } close(fds[0]); for (int i = 2; i <= 280; i++) { write(fds[1], &i, sizeof(int)); } close(fds[1]); wait(0); exit(0); } void sieve(int in_fds[2]) { close(in_fds[1]); int p, num; int fds[2]; // read base if (!read(in_fds[0], &p, sizeof(int))) { exit(0); } // create next sieve printf("prime %d\n", p); pipe(fds); if (!fork()) { sieve(fds); } // output to next sieve close(fds[0]); while (read(in_fds[0], &num, sizeof(int))) { if (num % p == 0) continue; write(fds[1], &num, sizeof(int)); } close(in_fds[0]); close(fds[1]); wait(0); exit(0); } 但是我这边输出显示乱码： 调试发现是sieve中创建管道的时候失败，进一步发现是将文件描述符消耗完了（xv6中限制文件描述符最大大概为14、15这样）。为什么会消耗完呢： ...

前言 题目出自leetcode 204，本质上是为了筛选出小于n的所有质数。三种方法： 暴力枚举 埃氏筛 欧拉筛（线性筛） 枚举法 枚举法中我们只需要从 2 到 n 判断每个数是否质数即可。对于第 i 个数来说判断是否质数，只需要看其能否被 2 到 i-1 整除，如果有可以整除的则为合数，不能整除则为质数。 进一步优化，考虑到如果 y 是 x 的因数，那么 x/y 也必然是 x 的因数，因此我们只要校验 y 或者 x/y 即可。而如果我们每次选择校验两者中的较小数，则不难发现较小数一定落在 [2, sqrt(x)] 的区间中，因此我们只需要枚举 [2, sqrt(x)] 中的所有数即可。 时间复杂度：O(n*sqrt(n)) 空间复杂度：O(1) 埃氏筛 Sieve of Eratosthenes 考虑质数 x，那么 x 的倍数一定是合数，因此可以将 2x、3x….这些 x 的倍数都标记为合数，如此一来，之后遇到这些数的时候就直接知道他们是合数，直接跳过即可。 进一步优化，不用从 2x 开始标记，而是从 x*x 开始标记，因为 2x 之前已经被 2 标记过，3x 已经被 3 标记过… 时间复杂度：O(n * logn * logn) 空间复杂度：O(n) 欧拉筛（线性筛） 在埃氏筛当中，许多合数会被重复标记，比如 6 会被 2 和 3 标记，15 会被 3 和 5 标记。由于一个合数很可能会被分解成多个不相同的质数的乘积，如 42 = 2 * 3 * 7，那么 42 就会被标记三次，造成时间复杂度上的浪费。 ...

Note 基于nsq v1.3.0 简介 NSQ是类似kafka、rabbitmq那样的消息队列系统，关于他怎么高性能，怎么好上手这些都不必多说，都是吹逼。这篇主要介绍一下nsq的整个大致架构，建立一个概念，方便后续的源码分析有迹可循。 架构 NSQ由三个守护进程组成： ...