Re: [PATCH 1/25] Remove nested functions: crypt/md5-crypt.c

[Konstantin Serebryany <konstantin dot s dot serebryany at gmail dot com>]

2014-05-20  Kostya Serebryany  <konstantin.s.serebryany@gmail.com>

        * crypt/md5-crypt.c (__md5_crypt_r): Remove a nested function.
        (b64_from_24bit): New function.

On Tue, May 20, 2014 at 5:13 PM, Siddhesh Poyarekar <siddhesh@redhat.com> wrote:
> On Tue, May 20, 2014 at 04:56:27PM +0400, Konstantin Serebryany wrote:
>> Hi,
>>
>> This patch is the first in the series of patches that remove nested
>> functions from glibc.
>> Rationale: nested functions is a non-standard language feature;
>> removing nested functions
>> will allow to compile glibc with compilers other than GCC and thus
>> benefit from other compilers
>> and code analysis tools.
>> Discussed previously here:
>> https://sourceware.org/ml/libc-alpha/2014-05/msg00400.html
>> No functionality change intended.
>>
>> (If approved, this will be my first commit to glibc, so some more
>> actions may be required)
>
> I believe initially you'll need one of us to commit for you, which we
> will do once the patch is found suitable.  You may want to review the
> contribution checklist as well:
>
> http://sourceware.org/glibc/wiki/Contribution%20checklist
>
>>
>> 2014-05-20 Kostya Serebryany <konstantin.s.serebryany@gmail.com>
>
> Two spaces between the date and name, and name and email.  An extra
> newline between the ChangeLog content and header.
>
>>         * crypt/md5-crypt.c (__md5_crypt_r): Remove a nested function.
>>         (b64_from_24bit): New function.
>>
>>
>> diff --git a/crypt/md5-crypt.c b/crypt/md5-crypt.c
>> index d1b92d7..29f66ce 100644
>> --- a/crypt/md5-crypt.c
>> +++ b/crypt/md5-crypt.c
>> @@ -88,6 +88,19 @@ extern char *__md5_crypt_r (const char *key, const
>> char *salt,
>>                             char *buffer, int buflen);
>>  extern char *__md5_crypt (const char *key, const char *salt);
>>
>> +static void b64_from_24bit (char **cp, int *buflen,
>
> 'static void' should be on a separate line on its own.

done

>
>> +                            unsigned int b2, unsigned int b1, unsigned int b0,
>> +                            int n)
>> +{
>> +  unsigned int w = (b2 << 16) | (b1 << 8) | b0;
>> +  while (n-- > 0 && *buflen > 0)
>> +    {
>> +      *(*cp)++ = b64t[w & 0x3f];
>> +      --*buflen;
>> +      w >>= 6;
>> +    }
>> +}
>> +
>>
>>  /* This entry point is equivalent to the `crypt' function in Unix
>>     libcs.  */
>> @@ -268,24 +281,18 @@ __md5_crypt_r (key, salt, buffer, buflen)
>>        --buflen;
>>      }
>>
>> -  void b64_from_24bit (unsigned int b2, unsigned int b1, unsigned int b0,
>> -                      int n)
>> -  {
>> -    unsigned int w = (b2 << 16) | (b1 << 8) | b0;
>> -    while (n-- > 0 && buflen > 0)
>> -      {
>> -       *cp++ = b64t[w & 0x3f];
>> -       --buflen;
>> -       w >>= 6;
>> -      }
>> -  }
>> -
>> -  b64_from_24bit (alt_result[0], alt_result[6], alt_result[12], 4);
>> -  b64_from_24bit (alt_result[1], alt_result[7], alt_result[13], 4);
>> -  b64_from_24bit (alt_result[2], alt_result[8], alt_result[14], 4);
>> -  b64_from_24bit (alt_result[3], alt_result[9], alt_result[15], 4);
>> -  b64_from_24bit (alt_result[4], alt_result[10], alt_result[5], 4);
>> -  b64_from_24bit (0, 0, alt_result[11], 2);
>> +  b64_from_24bit (&cp, &buflen,
>> +                  alt_result[0], alt_result[6], alt_result[12], 4);
>> +  b64_from_24bit (&cp, &buflen,
>> +                  alt_result[1], alt_result[7], alt_result[13], 4);
>> +  b64_from_24bit (&cp, &buflen,
>> +                  alt_result[2], alt_result[8], alt_result[14], 4);
>> +  b64_from_24bit (&cp, &buflen,
>> +                  alt_result[3], alt_result[9], alt_result[15], 4);
>> +  b64_from_24bit (&cp, &buflen,
>> +                  alt_result[4], alt_result[10], alt_result[5], 4);
>> +  b64_from_24bit (&cp, &buflen,
>> +                  0, 0, alt_result[11], 2);
>>    if (buflen <= 0)
>>      {
>>        __set_errno (ERANGE);
>
> It would be useful if you could post some kind of performance analysis
> of the crypt or crypt_r to show that making this change does not cause
> a significant drop in performance.  In fact, I'd be really interested
> in having a microbenchmark added for this function in benchtests.
> Instructions in benchtests/README should be useful but if not, please
> feel free to reach out to me for help.

Do you think such a benchmarks is possible at all?
I've made a simple test (attached) and profiled it with "perf":
    85.26%    a.out  libcrypt-2.15.so   [.] _ufc_doit_r
     6.13%    a.out  libcrypt-2.15.so   [.] _ufc_mk_keytab_r
     2.40%    a.out  libcrypt-2.15.so   [.] _ufc_setup_salt_r
     1.56%    a.out  libcrypt-2.15.so   [.] __crypt_r
     1.51%    a.out  libcrypt-2.15.so   [.] _ufc_output_conversion_r
     1.35%    a.out  libcrypt-2.15.so   [.] crypt

As you can see, crypt_r itself takes a tiny fraction of time,
most of it is spent in _ufc_* which are defined in another module.
Any changes in crypt itself (unless you do something insane) will not
be observable in profile.

Updated patch:

diff --git a/crypt/md5-crypt.c b/crypt/md5-crypt.c
index d1b92d7..5d5fc55 100644
--- a/crypt/md5-crypt.c
+++ b/crypt/md5-crypt.c
@@ -88,6 +88,20 @@ extern char *__md5_crypt_r (const char *key, const
char *salt,
                            char *buffer, int buflen);
 extern char *__md5_crypt (const char *key, const char *salt);

+static void
+b64_from_24bit (char **cp, int *buflen,
+                unsigned int b2, unsigned int b1, unsigned int b0,
+                int n)
+{
+  unsigned int w = (b2 << 16) | (b1 << 8) | b0;
+  while (n-- > 0 && *buflen > 0)
+    {
+      *(*cp)++ = b64t[w & 0x3f];
+      --*buflen;
+      w >>= 6;
+    }
+}
+

 /* This entry point is equivalent to the `crypt' function in Unix
    libcs.  */
@@ -268,24 +282,18 @@ __md5_crypt_r (key, salt, buffer, buflen)
       --buflen;
     }

-  void b64_from_24bit (unsigned int b2, unsigned int b1, unsigned int b0,
-                      int n)
-  {
-    unsigned int w = (b2 << 16) | (b1 << 8) | b0;
-    while (n-- > 0 && buflen > 0)
-      {
-       *cp++ = b64t[w & 0x3f];
-       --buflen;
-       w >>= 6;
-      }
-  }
-
-  b64_from_24bit (alt_result[0], alt_result[6], alt_result[12], 4);
-  b64_from_24bit (alt_result[1], alt_result[7], alt_result[13], 4);
-  b64_from_24bit (alt_result[2], alt_result[8], alt_result[14], 4);
-  b64_from_24bit (alt_result[3], alt_result[9], alt_result[15], 4);
-  b64_from_24bit (alt_result[4], alt_result[10], alt_result[5], 4);
-  b64_from_24bit (0, 0, alt_result[11], 2);
+  b64_from_24bit (&cp, &buflen,
+                  alt_result[0], alt_result[6], alt_result[12], 4);
+  b64_from_24bit (&cp, &buflen,
+                  alt_result[1], alt_result[7], alt_result[13], 4);
+  b64_from_24bit (&cp, &buflen,
+                  alt_result[2], alt_result[8], alt_result[14], 4);
+  b64_from_24bit (&cp, &buflen,
+                  alt_result[3], alt_result[9], alt_result[15], 4);
+  b64_from_24bit (&cp, &buflen,
+                  alt_result[4], alt_result[10], alt_result[5], 4);
+  b64_from_24bit (&cp, &buflen,
+                  0, 0, alt_result[11], 2);
   if (buflen <= 0)
     {
       __set_errno (ERANGE);

#define _XOPEN_SOURCE
#include <assert.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static const int kNumKeys = 200;
static const int kNumSalts = 4096;

typedef char Key[100];
typedef char Salt[3];

static Key keys[kNumKeys];
static Salt salts[kNumSalts];

static void Init() {
  char chars64[] = "abcdefghijklmnopqrstuvwxyz"
      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
      "0123456789./";
  assert(strlen(chars64) == 64);
  for (int i = 0; i < 64; i++) {
    for (int j = 0; j < 64; j++) {
      Salt &s = salts[i * 64 + j];
      s[0] = chars64[i];
      s[1] = chars64[j];
      s[2] = 0;
    }
  }

  for (int k = 0; k < kNumKeys; k++) {
    int len = rand() % (sizeof(Key) - 1) + 1;
    assert(len > 0 && len < sizeof(Key));
    for (int i = 0; i < len; i++)
      keys[k][i] = chars64[rand() % 64];
    keys[k][len] = 0;
  }
}

void Bench(int num_iters) {
  for (int it = 0; it < num_iters; it++) {
    for (int s = 0; s < kNumSalts; s++) {
      for (int k = 0; k < kNumKeys; k++) {
        crypt(keys[k], salts[s]);
      }
    }
  }
}

int main() {
  srand(0);
  Init();
  Bench(1);
}