Where is the implementation of strlen() in GCC?

Question

Can anyone point me to the definition of strlen() in GCC? I've been grepping release 4.4.2 for about a half hour now (while Googling like crazy) and I can't seem to find where strlen() is actually implemented.

Answer 1

You should be looking in glibc, not GCC -- it seems to be defined in strlen.c -- here's a link to strlen.c for glibc version 2.7... And here is a link to the glibc SVN repository online for strlen.c.

The reason you should be looking at glibc and not gcc is:

The GNU C library is used as the C library in the GNU system and most systems with the Linux kernel.

Answer 2

I realize this question is 4yrs old, but gcc will often include its own copy of strlen if you do not #include <string.h> and none of the answers (including the accepted answer) account for that. If you forget, you will get a warning:

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

and gcc will inline its copy which on x86 is the repnz scasb asm variant unless you pass -Werror or -fno-builtin. The files related to this are in gcc/config/<platform>/<platform>.{c,md}

It is also controlled by gcc/builtins.c. In case you wondered if and how a strlen() was optimized to a constant, see the function defined as tree c_strlen(tree src, int only_value) in this file. It also controls how strlen (amongst others) is expanded and folded (based on the previously mentioned config/platform)

Answer 3

Here's the bsd implementation

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

        for (s = str; *s; ++s)
                ;
        return (s - str);
}

Answer 4

defined in 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)

Answer 5

Is this what you are looking for? strlen() source. See the git repository for more information. The glibc resources page has links to the git repositories if you want to grab them rather than looking at the web view.

Answer 6

Although the original poster may not have known this or been looking for this, gcc internally inlines a number of so-called "builtin" c functions that it defines on its own, including some of the mem*() functions and (depending on the gcc version) strlen. In such cases, the library version is essentially never used, and pointing the person at the version in glibc is not strictly speaking correct. (It does this for performance reasons -- in addition to the improvement that inlining itself produces, gcc "knows" certain things about the functions when it provides them, such as, for example, that strlen is a pure function and that it can thus optimize away multiple calls, or in the case of the mem*() functions that no aliasing is taking place.)

For more information on this, see http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html

Answer 7

Google Code Search is a good starting point for questions like that. They usually point to various different sources and implementations of a function.

In your particular case: GoogleCodeSearch(strlen)

Google Code Search was completely shut down on March 2013

Answer 8

glibc 2.26 has several hand optimized assembly implementations of strlen

As of glibc-2.26, a quick:

git ls-files | grep strlen.S

in the glibc tree shows a dozen of assembly hand-optimized implementations for all major archs and variations.

In particular, x86_64 alone has 3 variations:

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

A quick and dirty way to determine which one is used, is to step debug a test program:

#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;
}

compiled with:

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

Off the bat:

disass main

contains:

callq  0x555555554590 <strlen@plt>

so the libc version is being called.

After a few si instruction level steps into that, GDB reaches:

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

which tells me that strlen-avx2.S was used.

Then, I further confirm with:

disass __strlen_avx2

and compare the disassembly with the glibc source.

It is not surprising that the AVX2 version was used, since I have an i7-7820HQ CPU with launch date Q1 2017 and AVX2 support, and AVX2 is the most advanced of the assembly implementations, with launch date Q2 2013, while SSE2 is much more ancient from 2004.

This is where a great part of the hardcoreness of glibc comes from: it has a lot of arch optimized hand written assembly code.

Tested in Ubuntu 17.10, gcc 7.2.0, glibc 2.26.

-O3

TODO: with -O3, gcc does not use glibc's strlen, it just generates inline assembly, which is mentioned at: https://stackoverflow.com/a/19885891/895245

Is it because it can optimize even better? But its output does not contain AVX2 instructions, so I feel that this is not the case.

https://www.gnu.org/software/gcc/projects/optimize.html mentions:

Deficiencies of GCC's optimizer

glibc has inline assembler versions of various string functions; GCC has some, but not necessarily the same ones on the same architectures. Additional optab entries, like the ones for ffs and strlen, could be provided for several more functions including memset, strchr, strcpy and strrchr.

My simple tests show that the -O3 version is actually faster, so GCC made the right choice.

Asked at: https://www.quora.com/unanswered/How-does-GCC-know-that-its-builtin-implementation-of-strlen-is-faster-than-glibcs-when-using-optimization-level-O3

Answer 9

I realize that this is old question, you can find the linux kernel sources at github here, and the 32 bit implementation for strlen() could be found in strlen_32.c on github. The mentioned file has this implementation.

#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);

Answer 10

You can use this code, the simpler the better !

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