Где реализация strlen () в GCC? - PullRequest
Новая
       11

Где реализация strlen () в GCC?

18 голосов
/ 14 ноября 2009

Может кто-нибудь указать мне определение strlen() в GCC? Я работаю с выпуском 4.4.2 около получаса (хотя Googling как сумасшедший), и я не могу найти, где на самом деле реализован strlen().

Ответы [ 10 ]

30 голосов
/ 14 ноября 2009

Вы должны искать в glibc, а не в GCC - похоже, он определен в strlen.c - вот ссылка на strlen.c для glibc версии 2.7 ... А вот ссылка в онлайн-хранилище glibc SVN для strlen.c .

Причина, по которой вы должны смотреть на glibc , а не на gcc:

Библиотека GNU C используется как библиотека C в системе GNU и большинстве систем с ядром Linux.

11 голосов
/ 10 ноября 2013

Я понимаю, что этому вопросу 4 года, но gcc часто будет включать собственную копию strlen, если вы не #include <string.h> и ни один из ответов (включая принятый ответ) не объясняет это. Если вы забудете, вы получите предупреждение:

file_name:line_number: warning: incompatible implicit declaration of built-in function 'strlen'

и gcc вставит свою копию, которая на x86 является вариантом repnz scasb asm, если вы не передадите -Werror или -fno-builtin. Файлы, связанные с этим, находятся в gcc/config/<platform>/<platform>.{c,md}

Он также контролируется gcc / builtins.c. В случае, если вам интересно, был ли оптимизирован strlen () и стал ли он постоянным, смотрите функцию, определенную как tree c_strlen(tree src, int only_value) в этом файле. Он также контролирует, как strlen (среди прочего) разворачивается и складывается (на основе ранее упомянутой конфигурации / платформы)

7 голосов
/ 14 ноября 2009

Вот реализация bsd 

size_t
strlen(const char *str)
{
        const char *s;

        for (s = str; *s; ++s)
                ;
        return (s - str);
}
4 голосов
/ 25 апреля 2018

определено в glibc / string / strlen.c 

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

#undef strlen

#ifndef STRLEN
# define STRLEN strlen
#endif

/* 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 (const char *str)
{
  const char *char_ptr;
  const unsigned long int *longword_ptr;
  unsigned long int longword, 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 == '\0')
      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.  */
  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.  */
      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 (;;)
    {
      longword = *longword_ptr++;

      if (((longword - lomagic) & ~longword & himagic) != 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)
3 голосов
/ 18 февраля 2012

Хотя оригинальный постер, возможно, не знал об этом или искал этого, gcc внутренне указывает на ряд так называемых «встроенных» функций c, которые он определяет самостоятельно, включая некоторые из функций mem * () и ( в зависимости от версии gcc) strlen. В таких случаях версия библиотеки по существу никогда не используется, и указывать человека на версию в glibc не совсем правильно. (Он делает это по соображениям производительности - в дополнение к улучшению, которое производит само встраивание, gcc «знает» некоторые вещи о функциях, когда предоставляет их, например, что strlen является чистой функцией и может таким образом оптимизировать несколько вызовов, или в случае функций mem * (), которые не имеют псевдонимов.)

Подробнее об этом см. http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

3 голосов
/ 14 ноября 2009

Поиск кода Google - хорошая отправная точка для подобных вопросов. Обычно они указывают на различные источники и реализации функции.

В вашем конкретном случае: GoogleCodeSearch (strlen)

Поиск кода Google был полностью закрыт в марте 2013 года

3 голосов
/ 14 ноября 2009

Это то, что вы ищете? strlen () source . Смотрите git репозиторий для получения дополнительной информации. Страница ресурсов glibc содержит ссылки на репозитории git, если вы хотите получить их, а не просматривать веб-страницу.

1 голос

glibc 2.26 имеет несколько реализаций сборки, оптимизированных вручную: strlen

По состоянию на glibc-2.26, быстрый: 

git ls-files | grep strlen.S

в дереве glibc показывает дюжину реализаций, оптимизированных вручную для всех основных архитектур и вариаций.

В частности, один x86_64 имеет 3 варианта: 

sysdeps/x86_64/multiarch/strlen-avx2.S
sysdeps/x86_64/multiarch/strlen-sse2.S
sysdeps/x86_64/strlen.S

Быстрый и грязный способ определить, какой из них используется, - пошаговая отладка тестовой программы: 

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

int main(void) {
    size_t size = 0x80000000, i, result;
    char *s = malloc(size);
    for (i = 0; i < size; ++i)
        s[i] = 'a';
    s[size - 1] = '\0';
    result = strlen(s);
    assert(result == size - 1);
    return EXIT_SUCCESS;
}

скомпилировано с: 

gcc -ggdb3 -std=c99 -O0 a.c

С бита: 

disass main

содержит: 

callq  0x555555554590 <strlen@plt>

поэтому вызывается версия libc.

После нескольких шагов si уровня команд GDB достигает: 

__strlen_avx2 () at ../sysdeps/x86_64/multiarch/strlen-avx2.S:52                                         
52      ../sysdeps/x86_64/multiarch/strlen-avx2.S: No such file or directory.

, который говорит мне, что strlen-avx2.S было использовано.

Затем я также подтверждаю: 

disass __strlen_avx2

и сравните разборку с источником glibc.

Неудивительно, что использовалась версия AVX2, так как у меня есть i7-7820HQ ЦП с датой запуска Q1 2017 и поддержкой AVX2, а AVX2 является самым передовым реализации сборки, с датой запуска Q2 2013, в то время как SSE2 намного более древний с 2004 года.

Вот откуда взялась большая часть хардкорности glibc: он имеет много оптимизированного для арки рукописного ассемблерного кода.

Протестировано в Ubuntu 17.10, gcc 7.2.0, glibc 2.26.

-O3

TODO: с -O3, gcc не использует glibc's strlen, он просто генерирует встроенную сборку, которая упоминается в: https://stackoverflow.com/a/19885891/895245

Это потому, что он может оптимизировать еще лучше? Но его вывод не содержит инструкций AVX2, поэтому я чувствую, что это не так.

https://www.gnu.org/software/gcc/projects/optimize.html упоминает:

Недостатки оптимизатора GCC

glibc имеет встроенные версии ассемблера различных строковых функций; GCC имеет несколько, но не обязательно одинаковых, на тех же архитектурах. Дополнительные записи optab, например, для ffs и strlen, могут быть предоставлены для нескольких дополнительных функций, включая memset, strchr, strcpy и strrchr.

Мои простые тесты показывают, что версия -O3 на самом деле быстрее, поэтому GCC сделала правильный выбор.

На вопрос: https://www.quora.com/unanswered/How-does-GCC-know-that-its-builtin-implementation-of-strlen-is-faster-than-glibcs-when-using-optimization-level-O3

1 голос
/ 28 сентября 2016

Я понимаю, что это старый вопрос, вы можете найти исходные коды ядра Linux на github здесь , а 32-битную реализацию strlen () можно найти в strlen_32.c на github. Упомянутый файл имеет эту реализацию. 

#include <linux/types.h>
#include <linux/string.h>
#include <linux/module.h>

size_t strlen(const char *s)
{
    /* Get an aligned pointer. */
    const uintptr_t s_int = (uintptr_t) s;
    const uint32_t *p = (const uint32_t *)(s_int & -4);

    /* Read the first word, but force bytes before the string to be nonzero.
     * This expression works because we know shift counts are taken mod 32.
     */
    uint32_t v = *p | ((1 << (s_int << 3)) - 1);

    uint32_t bits;
    while ((bits = __insn_seqb(v, 0)) == 0)
        v = *++p;

    return ((const char *)p) + (__insn_ctz(bits) >> 3) - s;
}
EXPORT_SYMBOL(strlen);
0 голосов
/ 24 февраля 2018

Вы можете использовать этот код, чем проще, тем лучше! 

size_t Strlen ( const char * _str )
{
    size_t i = 0;
    while(_str[i++]);
    return i;
}
...