[Glibc 源码分析] 1. 深度解析 memmove 函数

作者 Shilei Tian 日期 2017-04-06
C
[Glibc 源码分析] 1. 深度解析 memmove 函数

上次去某公司面试,被问到如何实现一个 strncpy 函数,并且还被问到要考虑哪些特殊情况。面试结束后回来上网查询了一下库函数是如何实现的,顿时被库函数那些简洁高效的实现方式吸引,所以打算将研读一些经典函数的实现。标准库函数的实现参考的是 glibc 的实现。

第一篇文章就从底层内存操作开始讲起,分析一下函数 memmove(dst, src, len) 的实现方法。该函数从 src 指向的位置复制 len字符dst 指向的位置。注意:需要复制的对象都会被当作 unsigned char 来进行处理。

那么我们先来想一下,实现这样的一个函数需要考虑哪些因素。首先就要考虑的是效率问题,所以我们一会就会看到库函数是如何竭尽所能的来提高效率,所以简单的 byte-by-byte 这种方式的复制肯定不可取。其次需要考虑的就是边界条件,从代码中我们可以看出,这里需要考虑的边界情况就是内存的交叠。因为如果 src + len > dst,如下图所示:

Memory Overlap

这样当我们移动需要复制的最后一个位置时,dst 原先指向位置的数据就会被覆盖。上图所示的情况,dst 指向的位置应该存放和 src 一样的内容。

我们通常在操作指针的时候,首先都要检查指针是否为 NULL,那这里我们需要考虑这种情况吗?库函数的实现中是没有考虑空指针这种情况的,这也就是为什么我们调用这些库函数的时候,如果传入的是空指针,程序直接就崩溃掉的原因。那究竟要不要考虑呢?我想,应该是不需要的。库函数并不是一个面向消费者的一款软件,它无需为一些情况考虑并提供交互式的反馈。但是库函数的运行一定要保证能够得到正确的结果,空指针这种情况,库函数直接就会崩溃,并不会运行得到不正确的结果,而内存交叠这种情况却是要考虑的,否则很有可能函数正常运行但得到不正确的结果。

那我们看一下具体的实现,在这里我替换掉了一些很显然的宏,使得代码更具有可读性,并为了节省空间,删掉了多余的空行。

#include <string.h>
#include <memcopy.h>
void* memmove(const void *dest, const void *src, size_t len) {
unsigned long int dstp = (long int) dest;
unsigned long int srcp = (long int) src;
/* This test makes the forward copying code be used whenever possible.
Reduces the working set. */
if (dstp - srcp >= len) /* *Unsigned* compare! */
{
/* Copy from the beginning to the end. */
#if MEMCPY_OK_FOR_FWD_MEMMOVE
dest = memcpy (dest, src, len);
#else
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES) {
/* Copy just a few bytes to make DSTP aligned. */
len -= (-dstp) % OPSIZ;
BYTE_COPY_FWD (dstp, srcp, (-dstp) % OPSIZ);
/* Copy whole pages from SRCP to DSTP by virtual address
manipulation, as much as possible. */
PAGE_COPY_FWD_MAYBE (dstp, srcp, len, len);
/* Copy from SRCP to DSTP taking advantage of the known
alignment of DSTP. Number of bytes remaining is put
in the third argument, i.e. in LEN. This number may
vary from machine to machine. */
WORD_COPY_FWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_FWD (dstp, srcp, len);
#endif /* MEMCPY_OK_FOR_FWD_MEMMOVE */
} else {
/* Copy from the end to the beginning. */
srcp += len;
dstp += len;
/* If there not too few bytes to copy, use word copy. */
if (len >= OP_T_THRES) {
/* Copy just a few bytes to make DSTP aligned. */
len -= dstp % OPSIZ;
BYTE_COPY_BWD (dstp, srcp, dstp % OPSIZ);
/* Copy from SRCP to DSTP taking advantage of the known
alignment of DSTP. Number of bytes remaining is put
in the third argument, i.e. in LEN. This number may
vary from machine to machine. */
WORD_COPY_BWD (dstp, srcp, len, len);
/* Fall out and copy the tail. */
}
/* There are just a few bytes to copy. Use byte memory operations. */
BYTE_COPY_BWD (dstp, srcp, len);
}
return dest;
}

下面我们一行一行的来解析这段代码。前两行包含头文件,这些头文件包含函数的声明和下面用到一些宏。第三行是函数的声明,我们可以看到 memmove 接受 3 个参数:两个指向源位置和目标位置的指针 dstsrc 以及需要复制的字节数。

接下来将两个指针转换成 unsigned long int 类型,这是因为内存的地址其实就是一个 unsigned long int 类型的数字,在 32 位操作系统中是 4 字节,64 位操作系统是 8 字节。

8 行对两个地址进行差运算,来判断两个地址之间的距离是否大于 len 来判断两块儿内存区域之间是否有交叠。注意看后面的注释:这是无符号判断。从表面意思来看,似乎是 dst 指向的地址应该大于 src 指向的地址,那万一 src 指向的地址大于 dst 指向的地址怎么办,是不是这个判断就失效了?并不是失效了,而是这种情况的交叠不会影响结果。我们把上图中 srcdst 交换一下,就得到下图情况:

Not a memory overlap

当进行内存移动的时候,dst 最后一个字节将会覆盖 src 指向的那个字节,但此时 src 指向的字节早已经完成了移动,并且我们这里需要完成的是移动,相当于原来那一块儿内存我们即将要释放掉,所以这个字节是否被覆盖将不会影响程序的结果。如果需要的是拷贝内存的话,那就应该调用 memcpy 这个函数了。

所以,当 src 指向的地址大于 dst 指向的地址时,由于是两个 unsigned 类型的数字进行运算,最终的结果会变成 LONG_MAX - (src - dst),这个值肯定会大于等于 len 的,否则 src + len > LONG_MAX,即这一块儿内存空间超出了地址空间,这显然是不可能的。

我们先来看没有交叠发生的情况,11 行判断此时安全的 memcpy 函数是否可用,如果可用的话,就直接调用现成的函数。宏 MEMCPY_OK_FOR_FWD_MEMMOVE 定义在头文件 memcopy.h 中,内容如下:

/* Set to 1 if memcpy is safe to use for forward-copying memmove with
overlapping addresses. This is 0 by default because memcpy implementations
are generally not safe for overlapping addresses. */
#define MEMCPY_OK_FOR_FWD_MEMMOVE 0

它说这个值通常会被定义成 0,因为 memcpy 的实现没有考虑内存的交叠情况,只有当前向拷贝安全时,才会被设置为 1。鉴于它就是被定义成了 0,这就相当于这里永远都不会调用现成的 memcpy 函数了。所以我们就忽略它。

从第 15 行开始就开始执行拷贝。第 14 行的注释告诉我们,当需要拷贝的字节数不是特别小的话,我们就用字拷贝(word copy),效率比字节复制(byte copy)更高,从这里可以体现出库函数的设计者对于性能方面的考虑。那如何判断是不是特别小呢?它判断的是字节数与 OP_T_THRES 的关系,OP_T_THRES 定义在头文件 memorycpy.h 中:

/* Threshold value for when to enter the unrolled loops. */
#define OP_T_THRES 16

这个值在不同的平台下定义不同,比如上面的这个 16 是出自 generic 版本的 memorycpy.h,在 i386 版本中对应的是 8

8 行对两个地址进行差运算,来判断两个地址之间的距离是否大于 len 来判断两块儿内存区域之间是否有交叠。注意看后面的注释:这是无符号判断。从表面意思来看,似乎是 dst 指向的地址应该大于 src 指向的地址,那万一 src 指向的地址大于 dst 指向的地址怎么办,是不是这个判断就失效了?并不是失效了,而是这种情况的交叠不会影响结果。我们把上图中 srcdst 交换一下,就得到下图情况:

Not a memory overlap

当进行内存移动的时候,dst 最后一个字节将会覆盖 src 指向的那个字节,但此时 src 指向的字节早已经完成了移动,并且我们这里需要完成的是移动,相当于原来那一块儿内存我们即将要释放掉,所以这个字节是否被覆盖将不会影响程序的结果。如果需要的是拷贝内存的话,那就应该调用 memcpy 这个函数了。

所以,当 src 指向的地址大于 dst 指向的地址时,由于是两个 unsigned 类型的数字进行运算,最终的结果会变成 LONG_MAX - (src - dst),这个值肯定会大于等于 len 的,否则 src + len > LONG_MAX,即这一块儿内存空间超出了地址空间,这显然是不可能的。

我们先来看没有交叠发生的情况,11 行判断此时安全的 memcpy 函数是否可用,如果可用的话,就直接调用现成的函数。宏 MEMCPY_OK_FOR_FWD_MEMMOVE 定义在头文件 memcopy.h 中,内容如下:

/* Set to 1 if memcpy is safe to use for forward-copying memmove with
overlapping addresses. This is 0 by default because memcpy implementations
are generally not safe for overlapping addresses. */
#define MEMCPY_OK_FOR_FWD_MEMMOVE 0

它说这个值通常会被定义成 0,因为 memcpy 的实现没有考虑内存的交叠情况,只有当前向拷贝安全时,才会被设置为 1。鉴于它就是被定义成了 0,这就相当于这里永远都不会调用现成的 memcpy 函数了。所以我们就忽略它。

从第 15 行开始就开始执行拷贝。第 14 行的注释告诉我们,当需要拷贝的字节数不是特别小的话,我们就用字拷贝(word copy),效率比字节拷贝(byte copy)更高,从这里可以体现出库函数的设计者对于性能方面的考虑。那如何判断是不是特别小呢?它判断的是字节数与 OP_T_THRES 的关系,OP_T_THRES定义在头文件 memorycpy.h 中:

/* Threshold value for when to enter the unrolled loops. */
#define OP_T_THRES 16

这个值在不同的平台下定义不同,比如上面的这个 16 是出自 generic 版本的 memorycpy.h,在 i386版本中对应的是 8

我们先看可以用字拷贝的情况,在 18 行的地方先进行了一次字节拷贝,这是为什么呢?16 行的注释给出了答案:内存对齐!由于字拷贝需要在自然边界上进行(出于性能的考虑,为了访问未对齐的内存,处理器需要作两次内存访问;而对齐的内存访问仅需要一次访问),所以我们需要先将没有对齐的这一段补齐。第 17 行先对需要补齐的字节数进行运算:(-dstp) % OPSIZ。第一次看到这个的时候,我在想,这是什么鬼?我可以想到的是,比如我们的对齐数是 16,现在有内存地址 9,那么我需要补齐的字节数是 15 + 1 - 9 = 7。但现在问题来了,如何得到下一个对齐的内存地址? 也就是如何知道我需要向谁对齐?可能你会想到,通过 (9 / 16 + 1) * 16 就可以得到,但是这样做效率较低,先需要做一个除法运算,再做一个加法运算,最后做一个乘法运算,这还没完,还需要减去之前的那个内存地址才能得到需要补齐的字节数。所以,库函数的实现者用了上面的式子,我们看一下为什么这个式子成立。由于 dstp 是一个 unsigned 类型的,因此它不会有负数,-dstp 实际上就等于 LONG_MAX + 1 - dstp,这个数和 OPSIZ 取模后得到的就是我们想要的字节数。我们可以考虑用 8 位二进制数来模拟一下。假设我们现在有一个 16×16 的格子,我们需要做的是填充所有这 256 个格子,现在我们已经填充了从024 号共计 25 个格子了,我们抽取其中第 1 行(从第 0 行开始计数),如下图所示:

Memory Aligned

25 号格子是我们接下来要填充的,此时 dstp = 25。在 8unsigned char 情况下,-dstp = 231,这个数字实际上就等于我们还未完成的格子数,也就是从上图中灰色部分开始数一直到第 15 行结束(这里我们只列了这个非整行,剩下的都是整行的)。我们想要做的,就是求出上图中灰色的格子数。231 由上面黑色格子加上下面所有整行整行的灰色格子,因此,让 23116 取余,我们就可以得到这多出来的不成整行的格子数,也就是我们想要的!这个运算特别快!对了,还没有说明 OPSIZ 是多少:

/* Type to use for aligned memory operations.
This should normally be the biggest type supported by a single load
and store. */
#define op_t unsigned long int
#define OPSIZ (sizeof(op_t))

注释告诉我们,它通常等于单个存取指令可以操作的最长的数字。

有了需要对齐的字节数后,补全没有对齐的字节,并更新 len 为剩下还未拷贝的字节数后就调用 BYTE_COPY_FWD 进行字节拷贝。BYTE_COPY_FWD 是一个宏,定义为:

/* Type to use for unaligned operations. */
typedef unsigned char byte;
/* Copy exactly NBYTES bytes from SRC_BP to DST_BP,
without any assumptions about alignment of the pointers. */
#define BYTE_COPY_FWD(dst_bp, src_bp, nbytes) \
do { \
size_t __nbytes = (nbytes); \
while (__nbytes > 0) { \
byte __x = ((byte *) src_bp)[0]; \
src_bp += 1; \
__nbytes -= 1; \
((byte *) dst_bp)[0] = __x; \
dst_bp += 1; \
} \
} while (0)

byte 类型被定义为 unsigned char 类型,每次先用一个临时变量 __x 保存 src_bp 指向的值,然后对 src_bp 进行自增,对计数变量进行自减,然后将临时变量 __x 的值赋给 dst_bp 所指向的内存,然后对 dst_bp 进行自增,直到计数结束。这里对于指针的解引用是通过取第 0 个元素进行的,我觉得也可以写成这种形式:*((byte*)dst_bp) = __x。这个宏就是实现一个字节一个字节的拷贝,不需要任何对齐的假设。宏里面的 FWD 关键字表示 forward,也就是向前复制。在 memorycpy.h 中还定义了一个 BWD 版本。

好了,下面我们就要看看高效地字拷贝是如何实现的了。第 21 行调用 PAGE_COPY_FWD_MAYBE,注释说通过操作虚拟内存,从 srcp 指向的位置复制尽可能多的页到 dstp 指向的位置。这个是怎么实现的呢?这个宏的定义如下:

/* The macro PAGE_COPY_FWD_MAYBE (dstp, srcp, nbytes_left, nbytes) is invoked
like WORD_COPY_FWD et al. The pointers should be at least word aligned.
This will check if virtual copying by pages can and should be done and do it
if so. The pointers will be aligned to PAGE_SIZE bytes. The macro requires
that pagecopy.h defines at least PAGE_COPY_THRESHOLD to 0. If
PAGE_COPY_THRESHOLD is non-zero, the header must also define PAGE_COPY_FWD
and PAGE_SIZE.
*/
#if PAGE_COPY_THRESHOLD
# define PAGE_COPY_FWD_MAYBE(dstp, srcp, nbytes_left, nbytes) \
do { \
if ((nbytes) >= PAGE_COPY_THRESHOLD && \
PAGE_OFFSET ((dstp) - (srcp)) == 0) { \
/* The amount to copy is past the threshold for copying \
pages virtually with kernel VM operations, and the \
source and destination addresses have the same alignment. */ \
size_t nbytes_before = PAGE_OFFSET (-(dstp)); \
if (nbytes_before != 0) { \
/* First copy the words before the first page boundary. */ \
WORD_COPY_FWD (dstp, srcp, nbytes_left, nbytes_before); \
assert (nbytes_left == 0); \
nbytes -= nbytes_before; \
} \
PAGE_COPY_FWD (dstp, srcp, nbytes_left, nbytes); \
} \
} while (0)
/* The page size is always a power of two, so we can avoid modulo division. */
# define PAGE_OFFSET(n) ((n) & (PAGE_SIZE - 1))
#else
# define PAGE_COPY_FWD_MAYBE(dstp, srcp, nbytes_left, nbytes) /* nada */
#endif

又是一段比较长的代码,我们先从注释入手。第一行的注释告诉我们,对于宏 PAGE_COPY_FWD_MAYBE 的调用和 WORD_COPY_FWD 差不多,都需要指针已经对齐了,在进行页复制之前会进行检查。指针需要对齐到 PAGE_SIZE,并且这个宏还依赖于头文件 pagecopy.h 中定义的宏 PAGE_COPY_THRESHOLD。查看头文件 pagecopy.h,会发现整个头文件只有一行语句:#define PAGE_COPY_THRESHOLD 0。它上面的一大段注释很关键:

/* The macro PAGE_COPY_FWD_MAYBE defined in memcopy.h is used in memmove if the
PAGE_COPY_THRESHOLD macro is set to a non-zero value. The default is 0,
that is copying by pages is not implemented.
System-specific pagecopy.h files that want to support page copying should
define these macros:
PAGE_COPY_THRESHOLD
-- A non-zero minimum size for which virtual copying by pages is worthwhile.
PAGE_SIZE
-- Size of a page.
PAGE_COPY_FWD (dstp, srcp, nbytes_left, nbytes)
-- Macro to perform the virtual copy operation.
The pointers will be aligned to PAGE_SIZE bytes.
*/

PAGE_COPY_THRESHOLD 默认为 0,这说明该系统不支持页复制。但是如果某系统提供了页复制的实现,那么就需要在相应的头文件中定义三个宏:PAGE_COPY_THRESHOLDPAGE_SIZEPAGE_COPY_FWD

看完上面这些,我们可以得到的结论是,最高效的复制方法是页复制,但是该方法依赖于具体系统的实现。如果页复制没有实现的话,宏 PAGE_COPY_FWD_MAYBE 就被定义成了一个空的宏。所以,这个宏的名字里面才包含了一个 MAYBE!如果 PAGE_COPY_FWD_MAYBE 可以顺利执行,我们的 len 就变成 0 了,这样下面的 WORD_COPY_FWD 就不需要执行了。虽然我们不知道宏 PAGE_COPY_FWD 的具体实现,但是我们就将它当作是能够进行页复制的宏,所以我们可以继续研究一下 PAGE_COPY_FWD_MAYBE 是怎么实现的。

未完待续:PAGE_COPY_FWD_MAYBE 的实现后续补充。

但是看起来我们手头的这个实现并不能顺利执行 PAGE_COPY_FWD_MAYBE,因此具体的字复制工作还是需要依赖于 WORD_COPY_FWD,那我们再看看它又是如何实现的。

/* _wordcopy_fwd_aligned -- Copy block beginning at SRCP to
block beginning at DSTP with LEN `op_t' words (not LEN bytes!).
Both SRCP and DSTP should be aligned for memory operations on `op_t's. */
extern void _wordcopy_fwd_aligned (long int, long int, size_t) attribute_hidden __THROW;
/* _wordcopy_fwd_dest_aligned -- Copy block beginning at SRCP to
block beginning at DSTP with LEN `op_t' words (not LEN bytes!).
DSTP should be aligned for memory operations on `op_t's, but SRCP must
*not* be aligned. */
extern void _wordcopy_fwd_dest_aligned (long int, long int, size_t) attribute_hidden __THROW;
/* Copy *up to* NBYTES bytes from SRC_BP to DST_BP, with
the assumption that DST_BP is aligned on an OPSIZ multiple. If
not all bytes could be easily copied, store remaining number of bytes
in NBYTES_LEFT, otherwise store 0. */
#define WORD_COPY_FWD(dst_bp, src_bp, nbytes_left, nbytes) \
do { \
if (src_bp % OPSIZ == 0) \
_wordcopy_fwd_aligned (dst_bp, src_bp, (nbytes) / OPSIZ); \
else \
_wordcopy_fwd_dest_aligned (dst_bp, src_bp, (nbytes) / OPSIZ); \
src_bp += (nbytes) & -OPSIZ; \
dst_bp += (nbytes) & -OPSIZ; \
(nbytes_left) = (nbytes) % OPSIZ; \
} while (0)

这个宏的注释告诉我们,它能从 src_p 指向的位置至多复制 nbytesdst_p 指向的位置,并且还假设 dst_p 指向的内存已经对齐。如果没有完全复制 nbytes 的话,就将剩下的长度存储在 nbytes_left 里面。所以,该宏先判断 src_bp 指向的那个内存地址是不是也是对齐好的,如果是的话,就调用函数_wordcopy_fwd_aligned。这里需要注意的是,前面所有的大写字母表示的类似函数的其实都是,因此它们在编译的时候都就展开了,这也是为什么我们可以一直用 srcpdstp,因为所有对它们进行的自增运算都不是通过调用函数实现的。我们继续回到 WORD_COPY_FWD 的实现上来。如果 src_bp 不是对齐的,那么就调用另一个函数 _wordcopy_fwd_dest_aligned 来完成复制。

上述两个函数是在外部定义在 wordcopy.c 这个文件里面,_wordcopy_fwd_dest_aligned 要求 dst_p 必须是对齐的,且 src_p 必须是不对齐的,我们来看一下它的实现。

#define op_t unsigned long int
void _wordcopy_fwd_aligned (long int dstp, long int srcp, size_t len) {
op_t a0, a1, a2, a3;
int sh_1, sh_2;
/* Calculate how to shift a word read at the memory operation
aligned srcp to make it aligned for copy. */
sh_1 = 8 * (srcp % OPSIZ);
sh_2 = 8 * OPSIZ - sh_1;
/* Make SRCP aligned by rounding it down to the beginning of the `op_t'
it points in the middle of. */
srcp &= -OPSIZ;
switch (len % 4) {
case 2:
a1 = ((op_t *) srcp)[0];
a2 = ((op_t *) srcp)[1];
srcp -= 1 * OPSIZ;
dstp -= 3 * OPSIZ;
len += 2;
goto do1;
case 3:
a0 = ((op_t *) srcp)[0];
a1 = ((op_t *) srcp)[1];
srcp -= 0 * OPSIZ;
dstp -= 2 * OPSIZ;
len += 1;
goto do2;
case 0:
if (OP_T_THRES <= 3 * OPSIZ && len == 0)
return;
a3 = ((op_t *) srcp)[0];
a0 = ((op_t *) srcp)[1];
srcp -=-1 * OPSIZ;
dstp -= 1 * OPSIZ;
len += 0;
goto do3;
case 1:
a2 = ((op_t *) srcp)[0];
a3 = ((op_t *) srcp)[1];
srcp -=-2 * OPSIZ;
dstp -= 0 * OPSIZ;
len -= 1;
if (OP_T_THRES <= 3 * OPSIZ && len == 0)
goto do0;
goto do4; /* No-op. */
}
do {
do4:
a0 = ((op_t *) srcp)[0];
((op_t *) dstp)[0] = MERGE (a2, sh_1, a3, sh_2);
do3:
a1 = ((op_t *) srcp)[1];
((op_t *) dstp)[1] = MERGE (a3, sh_1, a0, sh_2);
do2:
a2 = ((op_t *) srcp)[2];
((op_t *) dstp)[2] = MERGE (a0, sh_1, a1, sh_2);
do1:
a3 = ((op_t *) srcp)[3];
((op_t *) dstp)[3] = MERGE (a1, sh_1, a2, sh_2);
srcp += 4 * OPSIZ;
dstp += 4 * OPSIZ;
len -= 4;
} while (len != 0);
/* This is the right position for do0. Please don't move
it into the loop. */
do0:
((op_t *) dstp)[0] = MERGE (a2, sh_1, a3, sh_2);
}