C

NOTE: 以下讨论使用的平台为 x86-64，使用的编译器为 gcc，以下提供的伪汇编码 采用 intel 格式。 文章中提到的代码，可以在 Code 找到。 一些重要的寄存器和指令 函数调用过程中，比较重要的寄存器主要有三个 rip rbp rsp。 rip 寄存器存放的为下一条要执行指令的地址，Instruction Pointer。 rbp 为基寄存器，存放的为前一个 rbp 的值，Base Pointer。 rsp 为栈寄存器，一直指向函数调用栈的底部，Stack Pointer。 比较重要的指令有 call push pop leave ret。 call addr 指令会首先将 call 返回之后要执行的地址压入栈中(返回地址)，设置 rip 的值为 addr，然后跳转的这个位置去执行，大致可以等效于一下指令。 # 假设当执行到 call 指令时 CPU 就会自动设置 rip 寄存器为下一条要执行的指令 push rip mov rip, addr # 按理设置了 rip 寄存器，CPU 就会去执行 rip 地址的指令，这里写 jmp 只是想要更清晰的表示 call 的流程 jmp addr push rbp 指令会将 rsp 寄存器下移一个 word 的长度，rbp 中的内容移动到 rsp 寄存器所指向的地址中。 ...

Linux 核心代码中，对链表的排序算法是一种归并排序的变种。采用的排序方式为自下而上 的排序，这种方式可以避免 cache thrashing。 合并时机 Linux 中的对归并排序的改进主要是改变了两个链表的合并时机。该算法会有一个 pending 链表用来记录排序好的子链表，且保证每个子链表的长度都为 $2^k$。当 pending 中 即将出现第三个 $2^k$ 长度的链表时，就会合并已存在的两个 $2^k$ 长度的链表使其 变为一个 $2^{k+1}$ 长度的链表，所以在 pending 链表中永远不会存在超过 2 个 长度为 $2^k$ 的链表。 使用一个变量 count 来追踪 pending 中 $2^k$ 长度链表的个数，可以通过 count 中 k+1 k k-1 这 3 个 bits 来确定 pending 中 $2^k$ 长度链表的个数。下表 中的 3 个 bits 分别表示 k+1 k k-1，当 k 为 0 时，认为 -1 bit 为 1。 count $2^k$ 长度链表个数 …000… 0 …001… 0 …010… 0 …011… 1 …100… 1 …101… 2 源码分析 __attribute__((nonnull(2,3))) void list_sort(void *priv, struct list_head *head, list_cmp_func_t cmp) { struct list_head *list = head->next, *pending = NULL; size_t count = 0; /* Count of pending */ if (list == head->prev) /* Zero or one elements */ return; /* Convert to a null-terminated singly-linked list. */ head->prev->next = NULL; // .... } 函数的参数： ...

如何求一个正整数的平方根，最直接的方法就是 int i_sqrt(int N) { int res = 1; while (res * res <= N) { res++; } return res - 1; } 但上面的计算方法非常的低效，而对于求正整数的平方根，已经有非常多的算法。 下面介绍一个常用的正整数开平方根的算法。 Digit by digit calculation Digit by digit calculation 假设 $x = \sqrt{N}$ 则 $x^2 = N$ 以二进制表示 $x$，则 $x^2$ 为 $$ x^2 = (000b_0b_1b_2 \cdots b_{n-1}b_n)^2 \tag{1} $$ 其中，$b_0$ 为 $x$ 的二进制表示中第一个为 1 的二进制位。但要注意 $b_1 \cdots b_n$ 并不一定全为 1。我们可以将公式 (1) 改为加法形式。$a_n$ 对应的为 $b_0$。 $$ x^2 = (a_n + a_{n-1} + \cdots + a_1 + a_0)^2 \tag{2} $$ 其中，$a_m = 2^m$ 或 $a_m = 0$，取决于对应二进制位的值为 1 还是 0。将其展开可以得到 ...

文中代码 对于如下代码: int array[] = { 0, 1, 2, 3, 4 }; printf("%p\n", &array); printf("%p\n", array); 可以看到输出的地址是相同的. 而对于如下代码: int **array = (int **)malloc(sizeof(int *) * 5); for (int i = 0; i < 5; i++) array[i] = (int *)malloc(sizeof(int)); printf("%p\n", &array); printf("%p\n", array); 可以看到输出的地址是不同的. 其实对于这一段代码是没有任何疑问的, 可以很轻松的 明白为什么输出的地址不同. 那么编译器是如何处理第一部分代码，使输出的地址相同的。 可以通过gdb调试可以很清晰的看到编译器是如何处理这种情况的。 int array[] = { 0, 1, 2, 3, 4 }; void *a1 = (void *)&array, *a2 = (void *)array; 可以看到void这一行的汇编代码为: 0x565561e4 <main+71>: lea 0x8(%esp),%eax 0x565561e8 <main+75>: mov %eax,(%esp) 0x565561eb <main+78>: lea 0x8(%esp),%eax 0x565561ef <main+82>: mov %eax,0x4(%esp) 0x565561f3 <main+86>: mov $0x0,%eax 可以看到不管是 array 还是 &array 的操作都是使用的 lea 操作将 0x8(%esp) 移动到 %eax 中然后在 mov 操作赋值到相关变量中. 而对于另一段代码: int **array = (int **)malloc(sizeof(int *) * 5); for (int i = 0; i < 5; i++) array[i] = (int *)malloc(sizeof(int)); void *a1 = (void *)&array, *a2 = (void *)array; 0x56556214 <main+103>: lea -0x2c(%ebp),%eax 0x56556217 <main+106>: mov %eax,-0x24(%ebp) 0x5655621a <main+109>: mov -0x2c(%ebp),%eax 0x5655621d <main+112>: mov %eax,-0x20(%ebp) 0x56556220 <main+115>: mov $0x0,%eax 可以看到在为 a2 赋值是使用的是 mov 指令而不是 lea 指令. ...

开始 下面提到的变量均是在 main 函数中申请的变量。 文中代码 1. 二维数组 首先讨论二维数组, 他在内存中的布局是最简单的, 考虑如下变量 char str[][5] = { "jiao", "_shi", "_jie", }; 可以通过如下代码打印各个部分的地址 printf("str addr: %p\n\n", &str); for (int i = 0; i < 3; i++) { printf("str[%d] addr: %p\t", i, &str[i]); } printf("\n\n"); for (int i = 0; i < 3; i++) { for (int j = 0; j < 5; j++) { printf("str[%d][%d] addr: %p\n", i, j, &str[i][j]); } printf("\n"); } 可以看到地址从str[0][0]开始到结束是从低到高连续的。因为是在main函数中申请的 这个二维数组，因此它被存储在栈空间中(栈空间地址是高地址到低地址走的)，存储布局 大致如下： 2. 指针的指针 使用如下代码申请指针的指针的空间: char **d_ptr = (char **)malloc(sizeof(char *) * 3); for (int i = 0; i < 3; i++) { d_ptr[i] = (char *)malloc(sizeof(char) * 5); } memcpy(d_ptr[0], "jiao", 5); memcpy(d_ptr[1], "_shi", 5); memcpy(d_ptr[2], "_jie", 5); 使用如下代码输出各个部分的地址: printf("d_ptr addr: %p\n\n", &d_ptr); for (int i = 0; i < 3; i++) { printf("d_ptr[%d] addr: %p\n", i, &d_ptr[i]); } printf("\n\n"); for (int i = 0; i < 3; i++) { for (int j = 0; j < 5; j++) { printf("d_ptr[%d][%d] addr: %p\n", i, j, &d_ptr[i][j]); } printf("\n"); } 可以看到只有d_ptr的地址是在栈空间中的, 其余部分均是在堆空间中. ...