[PATCH] domain_codec: optimize dname_dec and convert_dname

Denys Vlasenko vda.linux at googlemail.com
Sun Jul 12 19:23:25 UTC 2020


Applied, thanks!

On Thu, Jul 9, 2020 at 2:47 PM Martin Lewis <martin.lewis.x84 at gmail.com> wrote:
>
> dname_dec: now iterates over the packet only once.
> convert_dname: remove redundant checks and code shrink.
>
> While testing I've noticed that some of the tests didn't compile
> properly, so I fixed them.
>
> function                                             old     new   delta
> dname_dec                                            286     267     -19
> dname_enc                                            166     143     -23
> ------------------------------------------------------------------------------
> (add/remove: 0/0 grow/shrink: 0/2 up/down: 0/-42)             Total: -42 bytes
>    text    data     bss     dec     hex filename
>  981645   16915    1872 1000432   f43f0 busybox_old
>  981603   16915    1872 1000390   f43c6 busybox_unstripped
>
> Signed-off-by: Martin Lewis <martin.lewis.x84 at gmail.com>
> ---
>  networking/udhcp/domain_codec.c | 157 ++++++++++++++++++++--------------------
>  1 file changed, 79 insertions(+), 78 deletions(-)
>
> diff --git a/networking/udhcp/domain_codec.c b/networking/udhcp/domain_codec.c
> index 752c0a863..092cd6661 100644
> --- a/networking/udhcp/domain_codec.c
> +++ b/networking/udhcp/domain_codec.c
> @@ -10,10 +10,14 @@
>  # define _GNU_SOURCE
>  # define FAST_FUNC /* nothing */
>  # define xmalloc malloc
> +# define xzalloc(s) calloc(s, 1)
> +# define xstrdup strdup
> +# define xrealloc realloc
>  # include <stdlib.h>
>  # include <stdint.h>
>  # include <string.h>
>  # include <stdio.h>
> +# include <ctype.h>
>  #else
>  # include "common.h"
>  #endif
> @@ -31,81 +35,72 @@
>   */
>  char* FAST_FUNC dname_dec(const uint8_t *cstr, int clen, const char *pre)
>  {
> -       char *ret = ret; /* for compiler */
> -       char *dst = NULL;
> +       char *ret, *end;
> +       unsigned len, crtpos, retpos, depth;
>
> -       /* We make two passes over the cstr string. First, we compute
> -        * how long the resulting string would be. Then we allocate a
> -        * new buffer of the required length, and fill it in with the
> -        * expanded content. The advantage of this approach is not
> -        * having to deal with requiring callers to supply their own
> -        * buffer, then having to check if it's sufficiently large, etc.
> -        */
> -       while (1) {
> -               /* note: "return NULL" below are leak-safe since
> -                * dst isn't allocated yet */
> +       crtpos = retpos = depth = 0;
> +       len = strlen(pre);
> +       end = ret = xstrdup(pre);
> +
> +       /* Scan the string once, allocating new memory as needed */
> +       while (crtpos < clen) {
>                 const uint8_t *c;
> -               unsigned crtpos, retpos, depth, len;
> +               c = cstr + crtpos;
>
> -               crtpos = retpos = depth = len = 0;
> -               while (crtpos < clen) {
> -                       c = cstr + crtpos;
> +               if ((*c & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
> +                       /* pointer */
> +                       if (crtpos + 2 > clen) /* no offset to jump to? abort */
> +                               goto error;
> +                       if (retpos == 0) /* toplevel? save return spot */
> +                               retpos = crtpos + 2;
> +                       depth++;
> +                       crtpos = ((c[0] << 8) | c[1]) & 0x3fff; /* jump */
> +               } else if (*c) {
> +                       unsigned label_len;
> +                       /* label */
> +                       if (crtpos + *c + 1 > clen) /* label too long? abort */
> +                               goto error;
> +                       ret = xrealloc(ret, len + *c + 1);
> +                       /* \3com ---> "com." */
> +                       end = (char *)mempcpy(ret + len, c + 1, *c);
> +                       end[0] = '.';
>
> -                       if ((*c & NS_CMPRSFLGS) == NS_CMPRSFLGS) {
> -                               /* pointer */
> -                               if (crtpos + 2 > clen) /* no offset to jump to? abort */
> -                                       return NULL;
> -                               if (retpos == 0) /* toplevel? save return spot */
> -                                       retpos = crtpos + 2;
> -                               depth++;
> -                               crtpos = ((c[0] & 0x3f) << 8) | c[1]; /* jump */
> -                       } else if (*c) {
> -                               /* label */
> -                               if (crtpos + *c + 1 > clen) /* label too long? abort */
> -                                       return NULL;
> -                               if (dst)
> -                                       /* \3com ---> "com." */
> -                                       ((char*)mempcpy(dst + len, c + 1, *c))[0] = '.';
> -                               len += *c + 1;
> -                               crtpos += *c + 1;
> +                       label_len = *c + 1;
> +                       len += label_len;
> +                       crtpos += label_len;
> +               } else {
> +                       /* NUL: end of current domain name */
> +                       if (retpos == 0) {
> +                               /* toplevel? keep going */
> +                               crtpos++;
>                         } else {
> -                               /* NUL: end of current domain name */
> -                               if (retpos == 0) {
> -                                       /* toplevel? keep going */
> -                                       crtpos++;
> -                               } else {
> -                                       /* return to toplevel saved spot */
> -                                       crtpos = retpos;
> -                                       retpos = depth = 0;
> -                               }
> -                               if (dst && len != 0)
> -                                       /* \4host\3com\0\4host and we are at \0:
> -                                        * \3com was converted to "com.", change dot to space.
> -                                        */
> -                                       dst[len - 1] = ' ';
> +                               /* return to toplevel saved spot */
> +                               crtpos = retpos;
> +                               retpos = depth = 0;
>                         }
>
> -                       if (depth > NS_MAXDNSRCH /* too many jumps? abort, it's a loop */
> -                        || len > NS_MAXDNAME * NS_MAXDNSRCH /* result too long? abort */
> -                       ) {
> -                               return NULL;
> +                       if (len != 0) {
> +                               /* \4host\3com\0\4host and we are at \0:
> +                                * \3com was converted to "com.", change dot to space.
> +                                */
> +                               ret[len - 1] = ' ';
>                         }
>                 }
>
> -               if (!len) /* expanded string has 0 length? abort */
> -                       return NULL;
> -
> -               if (!dst) { /* first pass? */
> -                       /* allocate dst buffer and copy pre */
> -                       unsigned plen = strlen(pre);
> -                       ret = xmalloc(plen + len);
> -                       dst = stpcpy(ret, pre);
> -               } else {
> -                       dst[len - 1] = '\0';
> -                       break;
> +               if (depth > NS_MAXDNSRCH /* too many jumps? abort, it's a loop */
> +                || len > NS_MAXDNAME * NS_MAXDNSRCH /* result too long? abort */
> +               ) {
> +                       goto error;
>                 }
>         }
>
> +       if (ret == end) { /* expanded string is empty? abort */
> +error:
> +               free(ret);
> +               return NULL;
> +       }
> +
> +       *end = '\0';
>         return ret;
>  }
>
> @@ -115,42 +110,40 @@ char* FAST_FUNC dname_dec(const uint8_t *cstr, int clen, const char *pre)
>   */
>  static uint8_t *convert_dname(const char *src, int *retlen)
>  {
> -       uint8_t c, *res, *lenptr, *dst;
> -       int len;
> +       uint8_t *res, *lenptr, *dst;
>
> -       res = xmalloc(strlen(src) + 2);
> +       res = xzalloc(strlen(src) + 2);
>         dst = lenptr = res;
>         dst++;
>
>         for (;;) {
> +               uint8_t c;
> +               int len;
> +
>                 c = (uint8_t)*src++;
>                 if (c == '.' || c == '\0') {  /* end of label */
>                         len = dst - lenptr - 1;
> -                       /* label too long, too short, or two '.'s in a row? abort */
> -                       if (len > NS_MAXLABEL || len == 0 || (c == '.' && *src == '.')) {
> -                               free(res);
> -                               *retlen = 0;
> -                               return NULL;
> -                       }
> +                       /* label too long, too short, or two '.'s in a row (len will be 0) */
> +                       if (len > NS_MAXLABEL || len == 0)
> +                               goto error;
> +
>                         *lenptr = len;
>                         if (c == '\0' || *src == '\0')  /* "" or ".": end of src */
>                                 break;
>                         lenptr = dst++;
> -                       continue;
> +               } else {
> +                       *dst++ = tolower(c);
>                 }
> -               if (c >= 'A' && c <= 'Z')  /* uppercase? convert to lower */
> -                       c += ('a' - 'A');
> -               *dst++ = c;
>         }
>
> -       if (dst - res >= NS_MAXCDNAME) {  /* dname too long? abort */
> +       *retlen = dst + 1 - res;
> +       if (*retlen > NS_MAXCDNAME) {  /* dname too long? abort */
> +error:
>                 free(res);
>                 *retlen = 0;
>                 return NULL;
>         }
>
> -       *dst++ = 0;
> -       *retlen = dst - res;
>         return res;
>  }
>
> @@ -245,6 +238,7 @@ int main(int argc, char **argv)
>         printf("test4:'%s'\n", DNAME_DEC("\4host\3com\0\xC0\5", ""));
>         printf("test5:'%s'\n", DNAME_DEC("\4host\3com\0\xC0\5\1z\xC0\xA", ""));
>
> +#if 0
>  #define DNAME_ENC(cache,source,lenp) dname_enc((uint8_t*)(cache), sizeof(cache), (source), (lenp))
>         encoded = dname_enc(NULL, 0, "test.net", &len);
>         printf("test6:'%s' len:%d\n", dname_dec(encoded, len, ""), len);
> @@ -252,6 +246,13 @@ int main(int argc, char **argv)
>         printf("test7:'%s' len:%d\n", dname_dec(encoded, len, ""), len);
>         encoded = DNAME_ENC("\4test\3net\0", "test.net", &len);
>         printf("test8:'%s' len:%d\n", dname_dec(encoded, len, ""), len);
> +#endif
> +
> +       encoded = dname_enc("test.net", &len);
> +       printf("test6:'%s' len:%d\n", dname_dec(encoded, len, ""), len);
> +       encoded = dname_enc("test.host.com", &len);
> +       printf("test7:'%s' len:%d\n", dname_dec(encoded, len, ""), len);
> +
>         return 0;
>  }
>  #endif
> --
> 2.11.0
>
> _______________________________________________
> busybox mailing list
> busybox at busybox.net
> http://lists.busybox.net/mailman/listinfo/busybox


More information about the busybox mailing list