lib/buildcmd.c

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