为什么glibc的strlen需要这么复杂才能快速运行? [英] Why does glibc's strlen need to be so complicated to run quickly?

问题描述

我正在查看 strlen 代码 这里 我想知道代码中使用的优化是否真的需要?例如，为什么像下面这样的东西不能同样好或更好?

unsigned long strlen(char s[]) {无符号长我;for (i = 0; s[i] != ''; i++)继续;返回我；}

更简单的代码不是更好和/或更容易让编译器优化吗?

链接后面页面的strlen代码如下:

<块引用>

/* 版权所有 (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.该文件是 GNU C 库的一部分.由 Torbjorn Granlund ([e-mail]) 撰写，在 Dan Sahlin ([e-mail]) 的帮助下；Jim Blandy ([e-mail]) 的评论.GNU C 库是免费软件；您可以重新分发它和/或根据 GNU Lesser General Public 的条款修改它由自由软件基金会发布的许可证；任何一个许可证的 2.1 版，或(由您选择)任何更高版本.发布 GNU C 库是希望它有用，但没有任何保证；甚至没有暗示的保证特定用途的适销性或适用性.见 GNU较小的通用公共许可证以获取更多详细信息.你应该已经收到一份 GNU Lesser General Public许可证以及 GNU C 库；如果没有，请写信给免费Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA02111-1307 美国.*/#include #include #undef strlen/* 返回空终止字符串 STR 的长度.扫一扫通过一次测试四个字节来快速找到空终止符.*/尺寸_t斯特伦 (str)const char *str;{const char *char_ptr;const unsigned long int *longword_ptr;unsigned long int longword、magic_bits、himagic、lomagic；/* 通过一次读取一个字符来处理前几个字符.这样做直到 CHAR_PTR 在长字边界上对齐.*/for (char_ptr = str; ((unsigned long int) char_ptr&(sizeof (longword) - 1)) != 0;++char_ptr)如果 (*char_ptr == '')返回 char_ptr - str;/* 所有这些说明性的注释都是指 4 字节长字，但该理论同样适用于 8 字节长字.*/longword_ptr = (unsigned long int *) char_ptr;/* 该数字的第 31、24、16 和 8 位为零.调用这些位洞".注意左边有个洞每个字节，最后有一个额外的:位:01111110 11111110 11111110 11111111字节:AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD1 位确保进位传播到下一个 0 位.0 位为进位提供孔.*/魔法位 = 0x7efefeffL；魔幻 = 0x80808080L；逻辑 = 0x01010101L；if (sizeof (longword) > 4){/* 64 位版本的魔法.*//* 如果 long 有 32 位，则分两步进行移位以避免警告.*/magic_bits = ((0x7efefefeL << 16) << 16) |0xfefefeffL；hemagic = ((himagic << 16) << 16) |魔幻的；lomagic = ((lomagic <<16) <<16) |逻辑性的；}if (sizeof (longword) > 8)中止()；/* 而不是测试每个字符的传统循环，我们将一次测试一个长字.棘手的部分是测试如果所讨论的长字中的*四个*字节中的任何一个为零.*/为了 (;;){/* 如果将 MAGIC_BITS 添加到，我们暂时退出循环LONGWORD 无法更改 LONGWORD 的任何空位.1)这安全吗?它会捕获所有零字节吗?假设有一个全为零的字节.任何进位从它的左边传播将落入它的洞中最低有效位并停止.既然不会有从其最高有效位进位，即 LSB左边的字节将保持不变，零将是检测到.2)这值得吗?它会忽略一切，除了零字节?假设 LONGWORD 的每个字节都设置了一个位某处.将进位到第 8 位.如果第 8 位被设置，这将进入第 16 位.如果第 8 位清零，必须设置位 9-15 之一，因此会有进位进入第 16 位.同样，将进位进位24. 如果第 24-30 位之一被设置，则会有一个进位进入位 31，所以所有的空位都将被改变.当第 24-30 位清除且位31 已设置；在这种情况下，第 31 位的孔不是改变了.如果我们可以访问处理器进位标志，我们可以通过放第四个洞来堵住这个漏洞在第 32 位！因此，当它们对齐时，它会忽略除 128 之外的所有内容适当地.*/longword = *longword_ptr++;如果 (#如果 0/* 添加 MAGIC_BITS 到 LONGWORD.*/(((长字+magic_bits)/* 设置那些被加法改变的位.*/^ ~长字)/* 只看孔位.如果有任何孔位不变，很可能其中一个字节是零.*/&~magic_bits)#别的((longword - lomagic) & hemagic)#万一!= 0){/* 哪个字节是零?如果他们都不是，那就是失火；继续搜索.*/const char *cp = (const char *) (longword_ptr - 1);如果(cp[0] == 0)返回cp-str；如果(cp[1] == 0)返回 cp - str + 1;如果(cp[2] == 0)返回 cp - str + 2;如果(cp[3] == 0)返回 cp - str + 3;if (sizeof (longword) > 4){如果(cp[4] == 0)返回 cp - str + 4;如果(cp[5] == 0)返回 cp - str + 5;如果(cp[6] == 0)返回 cp - str + 6;如果(cp[7] == 0)返回 cp - str + 7;}}}}libc_hidden_​​builtin_def (strlen)

为什么这个版本跑得很快?

这不是做了很多不必要的工作吗?

解决方案

您不需要并且不应该编写这样的代码 - 特别是如果您不是 C 编译器/标准库供应商.它是用于实现 strlen 的代码，其中包含一些非常可疑的速度技巧和假设(未使用断言测试或在评论中提及):

• unsigned long 为 4 或 8 个字节
• 字节为 8 位
• 指针可以转换为unsigned long long 而不是uintptr_t
• 只需检查 2 或 3 个最低位是否为零即可对齐指针
• 可以像unsigned longs
那样访问字符串
• 可以在没有任何不良影响的情况下读取数组末尾.

更重要的是，一个好的编译器甚至可以替换写成的代码

size_t 愚蠢的strlen(const char s[]) {size_t i;for (i=0; s[i] != ''; i++);返回我；}

(注意它必须是一个与 size_t 兼容的类型)和编译器内置的内联版本 strlen，或者向量化代码；但编译器不太可能优化复杂版本.

---

strlen 函数由 描述C11 7.24.6.3 为:

<块引用>

说明

2. strlen 函数计算 s 指向的字符串的长度.

退货

3. strlen 函数返回终止空字符之前的字符数.

现在，如果 s 指向的字符串在一个长度刚好足以包含字符串和终止 NUL 的字符数组中，行为 将是 undefined 如果我们访问空终止符之后的字符串，例如在

char *str = "hello world";//或者字符数组[] =你好世界"；

因此，在完全可移植/符合标准的 C 中正确实施此的唯一方法就是在您的问题中编写它的方式，除了微不足道的转换 - 您可以通过展开循环等来假装更快，但它仍然需要一次一个字节.

(正如评论者所指出的，当严格的可移植性是一种负担时，利用合理或已知安全的假设并不总是一件坏事.尤其是在一部分的代码中具体的 C 实现.但是在知道如何/何时可以弯曲它们之前，您必须了解规则.)

---

链接的strlen 实现首先单独检查字节，直到指针指向unsigned long 的自然4 或8 字节对齐边界.C 标准说访问未正确对齐的指针具有未定义的行为，因此绝对必须这样做，以使下一个肮脏的技巧变得更加肮脏.(实际上，在 x86 以外的某些 CPU 架构上，未对齐的字或双字加载会出错.C 不是一种可移植的汇编语言，但此代码以这种方式使用它).这也使得读取对象的末尾成为可能，而不会在内存保护在对齐块(例如 4kiB 虚拟内存页面)中工作的实现中出现故障风险.

现在是脏部分:代码破坏承诺并一次读取 4 或 8 个 8 位字节(long int)，并使用一点使用无符号加法快速找出这 4 或 8 个字节中是否有 任何 零字节的技巧 - 它使用特制的数字来导致进位位更改位捕获的位面具.本质上，这将确定掩码中的 4 或 8 个字节中的任何一个是否为零，据说比循环遍历这些字节中的每一个更快.最后有一个循环来找出哪个字节是第一个零(如果有)，并返回结果.

最大的问题是，在 sizeof (unsigned long) - 1 次 sizeof (unsigned long) 的情况下，它将读取超过字符串的末尾 - 仅如果空字节在最后访问的字节中(即在little-endian中最重要，在big-endian中最不重要)，它是否不访问数组越界！

---

即使用于在 C 标准库中实现 strlen 的代码也是坏代码.它有几个实现定义和未定义的方面，不应在任何地方代替系统提供的strlen使用-我将该函数重命名为the_strlen 并添加以下 main:

int main(void) {字符缓冲区[12];printf("%zu
", the_strlen(fgets(buf, 12, stdin)));}

缓冲区的大小经过仔细调整，以便它可以准确地保存 hello world 字符串和终止符.然而，在我的 64 位处理器上，unsigned long 是 8 个字节，因此对后面部分的访问将超过这个缓冲区.

如果我现在用 -fsanitize=undefined 和 -fsanitize=address 编译并运行结果程序，我得到:

% ./a.out你好世界====================================================================8355==错误:AddressSanitizer:堆栈缓冲区溢出地址 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340在 0x7ffffe63a3f8 线程 T0 处读取大小为 8#0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b)#1 0x55fbec46b139 在主 (.../a.out+0x2139)#2 0x7f4f0848fb96 在 __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)#3 0x55fbec46a949 在 _start (.../a.out+0x1949)地址 0x7ffffe63a3f8 位于线程 T0 的堆栈中，偏移量为 40 帧#0 0x55fbec46b07c 在主 (.../a.out+0x207c)此框架有 1 个对象:[32, 44) 'buf' <== 偏移量 40 处的内存访问部分溢出此变量提示:如果您的程序使用某些自定义堆栈展开机制或交换上下文，这可能是误报(longjmp 和 C++ 异常 * 支持 *)摘要:AddressSanitizer:the_strlen 中的堆栈缓冲区溢出(.../a.out+0x1b6b)错误地址周围的阴影字节:0x10007fcbf420:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf430:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf440:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf450:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf460:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00=>0x10007fcbf470:00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04]0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf490:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf4a0:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf4b0:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 000x10007fcbf4c0:00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00影子字节图例(一个影子字节代表 8 个应用程序字节):可寻址:00部分可寻址:01 02 03 04 05 06 07堆左红区:fa释放的堆区域:fd堆栈左红区:f1堆栈中间红区:f2堆栈右侧红区:f3返回后堆栈:f5作用域后的堆栈使用:f8全局红区:f9全局初始化命令:f6用户中毒:f7容器溢出:fc数组cookie:ac内部对象红区:bbASan 内部:fe左分配红区:ca右分配红区:cb==8355==正在中止

即坏事发生了.

I was looking through the strlen code here and I was wondering if the optimizations used in the code are really needed? For example, why wouldn't something like the following work equally good or better?

unsigned long strlen(char s[]) {
    unsigned long i;
    for (i = 0; s[i] != ''; i++)
        continue;
    return i;
}

Isn't simpler code better and/or easier for the compiler to optimize?

The code of strlen on the page behind the link looks like this:

/* Copyright (C) 1991, 1993, 1997, 2000, 2003 Free Software Foundation, Inc.
   This file is part of the GNU C Library.
   Written by Torbjorn Granlund ([e-mail]),
   with help from Dan Sahlin ([e-mail]);
   commentary by Jim Blandy ([e-mail]).

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

#include <string.h>
#include <stdlib.h>

#undef strlen

/* Return the length of the null-terminated string STR.  Scan for
   the null terminator quickly by testing four bytes at a time.  */
size_t
strlen (str)
     const char *str;
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, magic_bits, himagic, lomagic;

  /* Handle the first few characters by reading one character at a time.
     Do this until CHAR_PTR is aligned on a longword boundary.  */
  for (char_ptr = str; ((unsigned long int) char_ptr
            & (sizeof (longword) - 1)) != 0;
       ++char_ptr)
    if (*char_ptr == '')
      return char_ptr - str;

  /* All these elucidatory comments refer to 4-byte longwords,
     but the theory applies equally well to 8-byte longwords.  */

  longword_ptr = (unsigned long int *) char_ptr;

  /* Bits 31, 24, 16, and 8 of this number are zero.  Call these bits
     the "holes."  Note that there is a hole just to the left of
     each byte, with an extra at the end:

     bits:  01111110 11111110 11111110 11111111
     bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD

     The 1-bits make sure that carries propagate to the next 0-bit.
     The 0-bits provide holes for carries to fall into.  */
  magic_bits = 0x7efefeffL;
  himagic = 0x80808080L;
  lomagic = 0x01010101L;
  if (sizeof (longword) > 4)
    {
      /* 64-bit version of the magic.  */
      /* Do the shift in two steps to avoid a warning if long has 32 bits.  */
      magic_bits = ((0x7efefefeL << 16) << 16) | 0xfefefeffL;
      himagic = ((himagic << 16) << 16) | himagic;
      lomagic = ((lomagic << 16) << 16) | lomagic;
    }
  if (sizeof (longword) > 8)
    abort ();

  /* Instead of the traditional loop which tests each character,
     we will test a longword at a time.  The tricky part is testing
     if *any of the four* bytes in the longword in question are zero.  */
  for (;;)
    {
      /* We tentatively exit the loop if adding MAGIC_BITS to
     LONGWORD fails to change any of the hole bits of LONGWORD.

     1) Is this safe?  Will it catch all the zero bytes?
     Suppose there is a byte with all zeros.  Any carry bits
     propagating from its left will fall into the hole at its
     least significant bit and stop.  Since there will be no
     carry from its most significant bit, the LSB of the
     byte to the left will be unchanged, and the zero will be
     detected.

     2) Is this worthwhile?  Will it ignore everything except
     zero bytes?  Suppose every byte of LONGWORD has a bit set
     somewhere.  There will be a carry into bit 8.  If bit 8
     is set, this will carry into bit 16.  If bit 8 is clear,
     one of bits 9-15 must be set, so there will be a carry
     into bit 16.  Similarly, there will be a carry into bit
     24.  If one of bits 24-30 is set, there will be a carry
     into bit 31, so all of the hole bits will be changed.

     The one misfire occurs when bits 24-30 are clear and bit
     31 is set; in this case, the hole at bit 31 is not
     changed.  If we had access to the processor carry flag,
     we could close this loophole by putting the fourth hole
     at bit 32!

     So it ignores everything except 128's, when they're aligned
     properly.  */

      longword = *longword_ptr++;

      if (
#if 0
      /* Add MAGIC_BITS to LONGWORD.  */
      (((longword + magic_bits)

        /* Set those bits that were unchanged by the addition.  */
        ^ ~longword)

       /* Look at only the hole bits.  If any of the hole bits
          are unchanged, most likely one of the bytes was a
          zero.  */
       & ~magic_bits)
#else
      ((longword - lomagic) & himagic)
#endif
      != 0)
    {
      /* Which of the bytes was the zero?  If none of them were, it was
         a misfire; continue the search.  */

      const char *cp = (const char *) (longword_ptr - 1);

      if (cp[0] == 0)
        return cp - str;
      if (cp[1] == 0)
        return cp - str + 1;
      if (cp[2] == 0)
        return cp - str + 2;
      if (cp[3] == 0)
        return cp - str + 3;
      if (sizeof (longword) > 4)
        {
          if (cp[4] == 0)
        return cp - str + 4;
          if (cp[5] == 0)
        return cp - str + 5;
          if (cp[6] == 0)
        return cp - str + 6;
          if (cp[7] == 0)
        return cp - str + 7;
        }
    }
    }
}
libc_hidden_builtin_def (strlen)

Why does this version run quickly?

Isn't it doing a lot of unnecessary work?

解决方案

You don't need and you should never write code like that - especially if you're not a C compiler / standard library vendor. It is code used to implement strlen with some very questionable speed hacks and assumptions (that are not tested with assertions or mentioned in the comments):

• unsigned long is either 4 or 8 bytes
• bytes are 8 bits
• a pointer can be cast to unsigned long long and not uintptr_t
• one can align the pointer simply by checking that the 2 or 3 lowest order bits are zero
• one can access a string as unsigned longs
• one can read past the end of array without any ill effects.

What is more, a good compiler could even replace code written as

size_t stupid_strlen(const char s[]) {
    size_t i;
    for (i=0; s[i] != ''; i++)
        ;
    return i;
}

(notice that it has to be a type compatible with size_t) with an inlined version of the compiler builtin strlen, or vectorize the code; but a compiler would be unlikely to be able to optimize the complex version.

---

The strlen function is described by C11 7.24.6.3 as:

Description

2. The strlen function computes the length of the string pointed to by s.

Returns

3. The strlen function returns the number of characters that precede the terminating null character.

Now, if the string pointed to by s was in an array of characters just long enough to contain the string and the terminating NUL, the behaviour will be undefined if we access the string past the null terminator, for example in

char *str = "hello world";  // or
char array[] = "hello world";

So really the only way in fully portable / standards compliant C to implement this correctly is the way it is written in your question, except for trivial transformations - you can pretend to be faster by unrolling the loop etc, but it still needs to be done one byte at a time.

(As commenters have pointed out, when strict portability is too much of a burden, taking advantage of reasonable or known-safe assumptions is not always a bad thing. Especially in code that's part of one specific C implementation. But you have to understand the rules before knowing how/when you can bend them.)

---

The linked strlen implementation first checks the bytes individually until the pointer is pointing to the natural 4 or 8 byte alignment boundary of the unsigned long. The C standard says that accessing a pointer that is not properly aligned has undefined behaviour, so this absolutely has to be done for the next dirty trick to be even dirtier. (In practice on some CPU architecture other than x86, a misaligned word or doubleword load will fault. C is not a portable assembly language, but this code is using it that way). It's also what makes it possible to read past the end of an object without risk of faulting on implementations where memory protection works in aligned blocks (e.g. 4kiB virtual memory pages).

Now comes the dirty part: the code breaks the promise and reads 4 or 8 8-bit bytes at a time (a long int), and uses a bit trick with unsigned addition to quickly figure out if there were any zero bytes within those 4 or 8 bytes - it uses a specially crafted number to that would cause the carry bit to change bits that are caught by a bit mask. In essence this would then figure out if any of the 4 or 8 bytes in the mask are zeroes supposedly faster than looping through each of these bytes would. Finally there is a loop at the end to figure out which byte was the first zero, if any, and to return the result.

The biggest problem is that in sizeof (unsigned long) - 1 times out of sizeof (unsigned long) cases it will read past the end of the string - only if the null byte is in the last accessed byte (i.e. in little-endian the most significant, and in big-endian the least significant), does it not access the array out of bounds!

---

The code, even though used to implement strlen in a C standard library is bad code. It has several implementation-defined and undefined aspects in it and it should not be used anywhere instead of the system-provided strlen - I renamed the function to the_strlen here and added the following main:

int main(void) {
    char buf[12];
    printf("%zu
", the_strlen(fgets(buf, 12, stdin)));
}

The buffer is carefully sized so that it can hold exactly the hello world string and the terminator. However on my 64-bit processor the unsigned long is 8 bytes, so the access to the latter part would exceed this buffer.

If I now compile with -fsanitize=undefined and -fsanitize=address and run the resulting program, I get:

% ./a.out
hello world
=================================================================
==8355==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7ffffe63a3f8 at pc 0x55fbec46ab6c bp 0x7ffffe63a350 sp 0x7ffffe63a340
READ of size 8 at 0x7ffffe63a3f8 thread T0
    #0 0x55fbec46ab6b in the_strlen (.../a.out+0x1b6b)
    #1 0x55fbec46b139 in main (.../a.out+0x2139)
    #2 0x7f4f0848fb96 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x21b96)
    #3 0x55fbec46a949 in _start (.../a.out+0x1949)

Address 0x7ffffe63a3f8 is located in stack of thread T0 at offset 40 in frame
    #0 0x55fbec46b07c in main (.../a.out+0x207c)

  This frame has 1 object(s):
    [32, 44) 'buf' <== Memory access at offset 40 partially overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism or swapcontext
      (longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (.../a.out+0x1b6b) in the_strlen
Shadow bytes around the buggy address:
  0x10007fcbf420: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf430: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf440: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf450: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf460: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x10007fcbf470: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 00[04]
  0x10007fcbf480: f2 f2 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf490: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4a0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4b0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x10007fcbf4c0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
==8355==ABORTING

i.e. bad things happened.

这篇关于为什么glibc的strlen需要这么复杂才能快速运行?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！