lib/buildcmd.c

   1 /* buildcmd.c -- build command lines from a list of arguments.
   2    Copyright (C) 1990, 91, 92, 93, 94, 2000, 2003, 2005, 2006,
   3                  2007, 2008, 2010 Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation, either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17 */
  18
  19 #include <config.h>
  20
  21 #include <stdlib.h>
  22 #include <string.h>
  23 #include <wchar.h>
  24 #include <locale.h>
  25 #include <stdbool.h>
  26
  27 #if ENABLE_NLS
  28 # include <libintl.h>
  29 # define _(Text) gettext (Text)
  30 #else
  31 # define _(Text) Text
  32 #define textdomain(Domain)
  33 #define bindtextdomain(Package, Directory)
  34 #endif
  35 #ifdef gettext_noop
  36 # define N_(String) gettext_noop (String)
  37 #else
  38 /* See locate.c for explanation as to why not use (String) */
  39 # define N_(String) String
  40 #endif
  41
  42 #ifndef _POSIX_SOURCE
  43 #include <sys/param.h>
  44 #endif
  45
  46 #ifdef HAVE_LIMITS_H
  47 #include <limits.h>
  48 #endif
  49
  50 /* The presence of unistd.h is assumed by gnulib these days, so we
  51  * might as well assume it too.
  52  */
  53 /* for sysconf() */
  54 #include <unistd.h>
  55
  56 #include <assert.h>
  57
  58 /* COMPAT:  SYSV version defaults size (and has a max value of) to 470.
  59    We try to make it as large as possible.  See bc_get_arg_max() below. */
  60 #if !defined(ARG_MAX) && defined(NCARGS)
  61 #error "You have an unusual system.  Once you remove this error message from buildcmd.c, it should work, but please make sure that DejaGnu is installed on your system and that 'make check' passes before using the findutils programs"
  62 #define ARG_MAX NCARGS
  63 #endif
  64
  65
  66
  67 #include <xalloc.h>
  68 #include <errno.h>
  69 #include <error.h>
  70 #include <openat.h>
  71
  72 #include "xstrtol.h"
  73 #include "buildcmd.h"
  74 #include "arg-max.h"            /* must include after unistd.h. */
  75
  76
  77 extern char **environ;
  78
  79 static char *special_terminating_arg = "do_not_care";
  80
  81
  82
  83 /* Add a terminator to the argument list. */
  84 static void
  85 bc_args_complete (struct buildcmd_control *ctl,
  86                   struct buildcmd_state *state)
  87 {
  88   bc_push_arg (ctl, state, special_terminating_arg, 0, NULL, 0, 0);
  89 }
  90
  91
  92 /* Replace all instances of `replace_pat' in ARG with `linebuf',
  93    and add the resulting string to the list of arguments for the command
  94    to execute.
  95    ARGLEN is the length of ARG, not including the null.
  96    LBLEN is the length of LINEBUF, not including the null.
  97    PFXLEN is the length of PREFIX.  Substitution is not performed on
  98    the prefix.   The prefix is used if the argument contains replace_pat.
  99
 100    COMPAT: insertions on the SYSV version are limited to 255 chars per line,
 101    and a max of 5 occurrences of replace_pat in the initial-arguments.
 102    Those restrictions do not exist here.  */
 103
 104 void
 105 bc_do_insert (struct buildcmd_control *ctl,
 106               struct buildcmd_state *state,
 107               char *arg, size_t arglen,
 108               const char *prefix, size_t pfxlen,
 109               const char *linebuf, size_t lblen,
 110               int initial_args)
 111 {
 112   /* Temporary copy of each arg with the replace pattern replaced by the
 113      real arg.  */
 114   static char *insertbuf;
 115   char *p;
 116   size_t bytes_left = ctl->arg_max - 1;    /* Bytes left on the command line.  */
 117
 118   /* XXX: on systems lacking an upper limit for exec args, ctl->arg_max
 119    *      may have been set to LONG_MAX (see bc_get_arg_max()).  Hence
 120    *      this xmalloc call may be a bad idea, especially since we are
 121    *      adding 1 to it...
 122    */
 123   if (!insertbuf)
 124     insertbuf = xmalloc (ctl->arg_max + 1);
 125   p = insertbuf;
 126
 127   do
 128     {
 129       size_t len;               /* Length in ARG before `replace_pat'.  */
 130       char *s = mbsstr (arg, ctl->replace_pat);
 131       if (s)
 132         {
 133           len = s - arg;
 134         }
 135       else
 136         {
 137           len = arglen;
 138         }
 139
 140       if (bytes_left <= len)
 141         break;
 142       else
 143         bytes_left -= len;
 144
 145       strncpy (p, arg, len);
 146       p += len;
 147       arg += len;
 148       arglen -= len;
 149
 150       if (s)
 151         {
 152           if (bytes_left <= (lblen + pfxlen))
 153             break;
 154           else
 155             bytes_left -= (lblen + pfxlen);
 156
 157           if (prefix)
 158             {
 159               strcpy (p, prefix);
 160               p += pfxlen;
 161             }
 162           strcpy (p, linebuf);
 163           p += lblen;
 164
 165           arg += ctl->rplen;
 166           arglen -= ctl->rplen;
 167         }
 168     }
 169   while (*arg);
 170   if (*arg)
 171     error (EXIT_FAILURE, 0, _("command too long"));
 172   *p++ = '\0';
 173
 174   bc_push_arg (ctl, state,
 175                insertbuf, p - insertbuf,
 176                NULL, 0,
 177                initial_args);
 178 }
 179
 180
 181 /* Update our best guess as to how many arguments we should pass to the next
 182  * invocation of the command.
 183  */
 184 static size_t
 185 update_limit (struct buildcmd_control *ctl,
 186               struct buildcmd_state *state,
 187               bool success,
 188               size_t limit)
 189 {
 190   if (success)
 191     {
 192       if (limit > state->largest_successful_arg_count)
 193         state->largest_successful_arg_count = limit;
 194     }
 195   else
 196     {
 197       if (limit < state->smallest_failed_arg_count
 198           || (0 == state->smallest_failed_arg_count))
 199         state->smallest_failed_arg_count = limit;
 200     }
 201
 202   if (0 == (state->largest_successful_arg_count)
 203       || (state->smallest_failed_arg_count <= state->largest_successful_arg_count))
 204     {
 205       /* No success yet, or running on a system which has
 206          limits on total argv length, but not arg count. */
 207       if (success)
 208         {
 209           if (limit < SIZE_MAX)
 210             ++limit;
 211         }
 212       else
 213         {
 214           limit /= 2;
 215         }
 216     }
 217   else  /* We can use bisection. */
 218     {
 219       const size_t shift = (state->smallest_failed_arg_count
 220                           - state->largest_successful_arg_count) / 2;
 221       if (success)
 222         {
 223           if (shift)
 224             limit += shift;
 225           else
 226             ++limit;
 227         }
 228       else
 229         {
 230           if (shift)
 231             limit -= shift;
 232           else
 233             --limit;
 234         }
 235     }
 236
 237   /* Make sure the returned value is such that progress is
 238    * actually possible.
 239    */
 240   if (ctl->initial_argc && (limit <= ctl->initial_argc + 1u))
 241     limit = ctl->initial_argc + 1u;
 242   if (0 == limit)
 243     limit = 1u;
 244
 245   return limit;
 246 }
 247
 248
 249 /* Copy some of the program arguments into an argv list.   Copy all the
 250  * initial arguments, plus up to LIMIT additional arguments.
 251  */
 252 static size_t
 253 copy_args (struct buildcmd_control *ctl,
 254            struct buildcmd_state *state,
 255            char** working_args, size_t limit, size_t done)
 256 {
 257   size_t dst_pos = 0;
 258   size_t src_pos = 0;
 259
 260   while (src_pos < ctl->initial_argc)
 261     {
 262       working_args[dst_pos++] = state->cmd_argv[src_pos++];
 263     }
 264   src_pos += done;
 265   while (src_pos < state->cmd_argc && dst_pos < limit)
 266     {
 267       working_args[dst_pos++] = state->cmd_argv[src_pos++];
 268     }
 269   assert (dst_pos >= ctl->initial_argc);
 270   working_args[dst_pos] = NULL;
 271   return dst_pos;
 272 }
 273
 274
 275
 276
 277 /* Execute the program with the currently-built list of arguments. */
 278 void
 279 bc_do_exec (struct buildcmd_control *ctl,
 280             struct buildcmd_state *state)
 281 {
 282     char** working_args;
 283     size_t limit, done;
 284
 285     /* Terminate the args. */
 286     bc_args_complete (ctl, state);
 287     /* Verify that the argument list is terminated. */
 288     assert (state->cmd_argc > 0);
 289     assert (state->cmd_argv[state->cmd_argc-1] == NULL);
 290
 291     working_args = xmalloc ((1+state->cmd_argc) * sizeof (char*));
 292     done = 0;
 293     limit = state->cmd_argc;
 294
 295     do
 296       {
 297         const size_t dst_pos = copy_args (ctl, state, working_args,
 298                                           limit, done);
 299         if (ctl->exec_callback (ctl, state->usercontext, dst_pos, working_args))
 300           {
 301             limit = update_limit (ctl, state, true, limit);
 302             done += (dst_pos - ctl->initial_argc);
 303           }
 304         else  /* got E2BIG, adjust arguments */
 305           {
 306             if (limit <= ctl->initial_argc + 1)
 307               {
 308                 /* No room to reduce the length of the argument list.
 309                    Issue an error message and give up. */
 310                 error (EXIT_FAILURE, 0,
 311                        _("can't call exec() due to argument size restrictions"));
 312               }
 313             else
 314               {
 315                 /* Try fewer arguments. */
 316                 limit = update_limit (ctl, state, false, limit);
 317               }
 318           }
 319       }
 320     while ((done + 1) < (state->cmd_argc - ctl->initial_argc));
 321     /* (state->cmd_argc - ctl->initial_argc) includes the terminating NULL,
 322      * which is why we add 1 to done in the test above. */
 323
 324     free (working_args);
 325     bc_clear_args (ctl, state);
 326 }
 327
 328
 329 /* Return nonzero if there would not be enough room for an additional
 330  * argument.  We check the total number of arguments only, not the space
 331  * occupied by those arguments.
 332  *
 333  * If we return zero, there still may not be enough room for the next
 334  * argument, depending on its length.
 335  */
 336 static int
 337 bc_argc_limit_reached (int initial_args,
 338                        const struct buildcmd_control *ctl,
 339                        struct buildcmd_state *state)
 340 {
 341   /* Check to see if we about to exceed a limit set by xargs' -n option */
 342   if (!initial_args && ctl->args_per_exec &&
 343       ( (state->cmd_argc - ctl->initial_argc) == ctl->args_per_exec))
 344     return 1;
 345
 346   /* We deliberately use an equality test here rather than >= in order
 347    * to force a software failure if the code is modified in such a way
 348    * that it fails to call this function for every new argument.
 349    */
 350   return state->cmd_argc == ctl->max_arg_count;
 351 }
 352
 353
 354 /* Add ARG to the end of the list of arguments `cmd_argv' to pass
 355    to the command.
 356    LEN is the length of ARG, including the terminating null.
 357    If this brings the list up to its maximum size, execute the command.
 358 */
 359 void
 360 bc_push_arg (struct buildcmd_control *ctl,
 361              struct buildcmd_state *state,
 362              const char *arg, size_t len,
 363              const char *prefix, size_t pfxlen,
 364              int initial_args)
 365 {
 366   const int terminate = (arg == special_terminating_arg);
 367
 368   assert (arg != NULL);
 369
 370   if (!initial_args)
 371     {
 372       state->todo = 1;
 373     }
 374
 375   if (!terminate)
 376     {
 377       if (state->cmd_argv_chars + len > ctl->arg_max)
 378         {
 379           if (initial_args || state->cmd_argc == ctl->initial_argc)
 380             error (EXIT_FAILURE, 0,
 381                    _("cannot fit single argument within argument list size limit"));
 382
 383           /* xargs option -i (replace_pat) implies -x (exit_if_size_exceeded) */
 384           if (ctl->replace_pat
 385               || (ctl->exit_if_size_exceeded &&
 386                   (ctl->lines_per_exec || ctl->args_per_exec)))
 387             error (EXIT_FAILURE, 0, _("argument list too long"));
 388             bc_do_exec (ctl, state);
 389         }
 390       if (bc_argc_limit_reached (initial_args, ctl, state))
 391             bc_do_exec (ctl, state);
 392     }
 393
 394   if (state->cmd_argc >= state->cmd_argv_alloc)
 395     {
 396       /* XXX: we could use extendbuf() here. */
 397       if (!state->cmd_argv)
 398         {
 399           state->cmd_argv_alloc = 64;
 400           state->cmd_argv = xmalloc (sizeof (char *) * state->cmd_argv_alloc);
 401         }
 402       else
 403         {
 404           state->cmd_argv_alloc *= 2;
 405           state->cmd_argv = xrealloc (state->cmd_argv,
 406                                       sizeof (char *) * state->cmd_argv_alloc);
 407         }
 408     }
 409
 410   if (terminate)
 411     state->cmd_argv[state->cmd_argc++] = NULL;
 412   else
 413     {
 414       state->cmd_argv[state->cmd_argc++] = state->argbuf + state->cmd_argv_chars;
 415       if (prefix)
 416         {
 417           strcpy (state->argbuf + state->cmd_argv_chars, prefix);
 418           state->cmd_argv_chars += pfxlen;
 419         }
 420
 421       strcpy (state->argbuf + state->cmd_argv_chars, arg);
 422       state->cmd_argv_chars += len;
 423
 424       /* If we have now collected enough arguments,
 425        * do the exec immediately.
 426        */
 427       if (bc_argc_limit_reached (initial_args, ctl, state))
 428         {
 429           bc_do_exec (ctl, state);
 430         }
 431     }
 432
 433   /* If this is an initial argument, set the high-water mark. */
 434   if (initial_args)
 435     {
 436       state->cmd_initial_argv_chars = state->cmd_argv_chars;
 437     }
 438 }
 439
 440
 441 size_t
 442 bc_get_arg_max (void)
 443 {
 444   long val;
 445
 446   /* We may resort to using LONG_MAX, so check it fits. */
 447   /* XXX: better to do a compile-time check */
 448   assert ( (~(size_t)0) >= LONG_MAX);
 449
 450 #ifdef _SC_ARG_MAX
 451   val = sysconf (_SC_ARG_MAX);
 452 #else
 453   val = -1;
 454 #endif
 455
 456   if (val > 0)
 457     return val;
 458
 459   /* either _SC_ARG_MAX was not available or
 460    * there is no particular limit.
 461    */
 462 #ifdef ARG_MAX
 463   val = ARG_MAX;
 464 #endif
 465
 466   if (val > 0)
 467     return val;
 468
 469   /* The value returned by this function bounds the
 470    * value applied as the ceiling for the -s option.
 471    * Hence it the system won't tell us what its limit
 472    * is, we allow the user to specify more or less
 473    * whatever value they like.
 474    */
 475   return LONG_MAX;
 476 }
 477
 478
 479 static int
 480 cb_exec_noop (struct buildcmd_control * ctl,
 481               void *usercontext,
 482               int argc,
 483               char **argv)
 484 {
 485   /* does nothing. */
 486   (void) ctl;
 487   (void) usercontext;
 488   (void) argc;
 489   (void) argv;
 490
 491   return 0;
 492 }
 493
 494
 495 /* Return how much of ARG_MAX is used by the environment.  */
 496 size_t
 497 bc_size_of_environment (void)
 498 {
 499   size_t len = 0u;
 500   char **envp = environ;
 501
 502   while (*envp)
 503     len += strlen (*envp++) + 1;
 504
 505   return len;
 506 }
 507
 508
 509 enum BC_INIT_STATUS
 510 bc_init_controlinfo (struct buildcmd_control *ctl,
 511                      size_t headroom)
 512 {
 513   size_t size_of_environment = bc_size_of_environment ();
 514
 515   /* POSIX requires that _POSIX_ARG_MAX is 4096.  That is the lowest
 516    * possible value for ARG_MAX on a POSIX compliant system.  See
 517    * http://www.opengroup.org/onlinepubs/009695399/basedefs/limits.h.html
 518    */
 519   ctl->posix_arg_size_min = _POSIX_ARG_MAX;
 520   ctl->posix_arg_size_max = bc_get_arg_max ();
 521
 522   ctl->exit_if_size_exceeded = 0;
 523
 524   /* Take the size of the environment into account.  */
 525   if (size_of_environment > ctl->posix_arg_size_max)
 526     {
 527       return BC_INIT_ENV_TOO_BIG;
 528     }
 529   else if ((headroom + size_of_environment) >= ctl->posix_arg_size_max)
 530     {
 531       /* POSIX.2 requires xargs to subtract 2048, but ARG_MAX is
 532        * guaranteed to be at least 4096.  Although xargs could use an
 533        * assertion here, we use a runtime check which returns an error
 534        * code, because our caller may not be xargs.
 535        */
 536       return BC_INIT_CANNOT_ACCOMODATE_HEADROOM;
 537     }
 538   else
 539     {
 540       ctl->posix_arg_size_max -= size_of_environment;
 541       ctl->posix_arg_size_max -= headroom;
 542     }
 543
 544   /* need to subtract 2 on the following line - for Linux/PPC */
 545   ctl->max_arg_count = (ctl->posix_arg_size_max / sizeof (char*)) - 2u;
 546   assert (ctl->max_arg_count > 0);
 547   ctl->rplen = 0u;
 548   ctl->replace_pat = NULL;
 549   ctl->initial_argc = 0;
 550   ctl->exec_callback = cb_exec_noop;
 551   ctl->lines_per_exec = 0;
 552   ctl->args_per_exec = 0;
 553
 554   /* Set the initial value of arg_max to the largest value we can
 555    * tolerate.
 556    */
 557   ctl->arg_max = ctl->posix_arg_size_max;
 558
 559   return BC_INIT_OK;
 560 }
 561
 562 void
 563 bc_use_sensible_arg_max (struct buildcmd_control *ctl)
 564 {
 565 #ifdef DEFAULT_ARG_SIZE
 566   enum { arg_size = DEFAULT_ARG_SIZE };
 567 #else
 568   enum { arg_size = (128u * 1024u) };
 569 #endif
 570
 571   /* Check against the upper and lower limits. */
 572   if (arg_size > ctl->posix_arg_size_max)
 573     ctl->arg_max = ctl->posix_arg_size_max;
 574   else if (arg_size < ctl->posix_arg_size_min)
 575     ctl->arg_max = ctl->posix_arg_size_min;
 576   else
 577     ctl->arg_max = arg_size;
 578 }
 579
 580
 581
 582
 583 void
 584 bc_init_state (const struct buildcmd_control *ctl,
 585                struct buildcmd_state *state,
 586                void *context)
 587 {
 588   state->cmd_argc = 0;
 589   state->cmd_argv_chars = 0;
 590   state->cmd_argv = NULL;
 591   state->cmd_argv_alloc = 0;
 592   state->largest_successful_arg_count = 0;
 593   state->smallest_failed_arg_count = 0;
 594
 595   /* XXX: the following memory allocation is inadvisable on systems
 596    * with no ARG_MAX, because ctl->arg_max may actually be close to
 597    * LONG_MAX.   Adding one to it is safe though because earlier we
 598    * subtracted 2048.
 599    */
 600   assert (ctl->arg_max <= (LONG_MAX - 2048L));
 601   state->argbuf = xmalloc (ctl->arg_max + 1u);
 602
 603   state->cmd_argv_chars = state->cmd_initial_argv_chars = 0;
 604   state->todo = 0;
 605   state->dir_fd = -1;
 606   state->usercontext = context;
 607 }
 608
 609 void
 610 bc_clear_args (const struct buildcmd_control *ctl,
 611                struct buildcmd_state *state)
 612 {
 613   state->cmd_argc = ctl->initial_argc;
 614   state->cmd_argv_chars = state->cmd_initial_argv_chars;
 615   state->todo = 0;
 616   state->dir_fd = -1;
 617 }
 618
 619
 620 /* Return nonzero if the value stored in the environment variable ENV_VAR_NAME
 621  * exceeds QUANTITY.
 622  */
 623 static int
 624 exceeds (const char *env_var_name, size_t quantity)
 625 {
 626   const char *val = getenv (env_var_name);
 627   if (val)
 628     {
 629       char *tmp;
 630       unsigned long limit;
 631
 632       if (xstrtoul (val, &tmp, 10, &limit, NULL) == LONGINT_OK)
 633         {
 634           if (quantity > limit)
 635             return 1;
 636         }
 637       else
 638         {
 639           error (EXIT_FAILURE, errno,
 640                  _("Environment variable %s is not set to a "
 641                    "valid decimal number"),
 642                  env_var_name);
 643           return 0;
 644         }
 645     }
 646   return 0;
 647 }
 648
 649 /* Return nonzero if the indicated argument list exceeds a testing limit. */
 650 bool
 651 bc_args_exceed_testing_limit (const char **argv)
 652 {
 653   size_t chars, args;
 654
 655   for (chars=args=0; *argv; ++argv)
 656     {
 657       ++args;
 658       chars += strlen(*argv);
 659     }
 660
 661   return (exceeds ("__GNU_FINDUTILS_EXEC_ARG_COUNT_LIMIT", args) ||
 662           exceeds ("__GNU_FINDUTILS_EXEC_ARG_LENGTH_LIMIT", chars));
 663 }