Proposed attempt to address item 3 of the 'enhancements wanted' announcement

[Moura, Dr Alessandro P. S. (Physics)]

Hi,

Here is an idea for implementing an extra option in xargs to make it calculate 
the maximum length
of the arguments it will pass on to the command, without relying on ARG_MAX.

The idea is simply to repeatedly fork-exec a do-nothing command giving it a 
very long generated string and
monitoring its exit status to see if it failed due to a too-long argument. It 
starts with a string of (very large)
length N and, through a bisection method akin to binary search, N is reduced if 
the command failed, or increased
if it succeeded, until we zoom into the actual value of N (or to within a 
prescribed vicinity of it). The number
of iterations it takes to find the final value increases only logarithmically 
with N, and in just 20 or so steps it will
converge. On top of that, only one string allocation (and deallocation) is 
needed: N can be varied by just
inserting null characters in an existing string.

I implemented this method as a proof-of-concept, in the form of the little 
program listed below.
I have not integrated this in the findutils source tree, because I wanted to 
discuss this here and get your views on
this design, and whether it makes sense.

Here is the program:

------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <sys/wait.h>

char *build_big_str (int N)
{
  int i;
  char *bigstr = (char *) malloc (N);

  if (!bigstr) {
    printf ("Error: no memory!\n");
    return 0;
  }

  for (i=0; i<N-1; i++)
    bigstr[i] = 'a';
  bigstr[N-1] = 0;

  return bigstr;
}

int args_too_big (char **args)
{
  int status;
  pid_t fk;

  fk = fork ();

  if (fk == 0) {        /* child */
    int res = execv ("/bin/true", args);

    if (res == -1) {
      perror (0);
      exit (1);
    }
    exit (0);
  }
  /* parent */
  wait (&status);
  if (WIFEXITED (status)) {
    return WEXITSTATUS(status);
  }
  /* not able to execute the command for some reason */
  return 2;
}


int bisect_str (int N, int nbytes)
{
  int right, left, midpoint;
  int ecode = 0;
  char **arg = (char **) malloc (2*sizeof(char *));

  arg[0] = build_big_str (N);
  if (arg[0] == 0)
    return -1;
  arg[1] = 0;

  left = 0;
  midpoint = right = N-1;

  if (! args_too_big (arg))
    return N;
  printf ("r=%d  l=%d   m=%d\n", right, left, midpoint);

  while (abs(right-left) > 2*nbytes || ecode == 1) {
    midpoint = (right + left)/2;
    arg[0][midpoint] = 0;

    ecode = args_too_big (arg);
    if (ecode == 2) {  /* execution of outside command failed */
      return -1;
    }
    if (ecode) {
      right = midpoint;
    } else {
      arg[0][midpoint] = 'a';
      left = midpoint;
    }
    printf ("r=%d  l=%d   m=%d\n", right, left, midpoint);
  }

  free (arg[0]);
  free (arg);
  return midpoint + 1;
}


int main ()
{
  char *arg[2];
  int result = bisect_str (1000000, 1);

  if (result < 0) {
    printf ("\nExecution of command failed!\n");
    return 1;
  }
  printf ("\nFinished.  Result: %d\n", result);
  printf ("Checking:\n");

  arg[0] = build_big_str (result);
  if (arg[0] == 0)
    return -1;
  arg[1] = 0;

  if (args_too_big (arg)) {
    printf ("Oops: could not execute command!\n");
    return 2;
  }

  printf ("Ok\n");

  return 0;
}
----------------------------------------

Here is the output:

++++++++++++++++++++++++++++
address@hidden:~$ time ./argsz
Argument list too long
r=999999  l=0   m=999999
Argument list too long
r=499999  l=0   m=499999
Argument list too long
r=249999  l=0   m=249999
r=249999  l=124999   m=124999
Argument list too long
r=187499  l=124999   m=187499
Argument list too long
r=156249  l=124999   m=156249
Argument list too long
r=140624  l=124999   m=140624
Argument list too long
r=132811  l=124999   m=132811
r=132811  l=128905   m=128905
r=132811  l=130858   m=130858
Argument list too long
r=131834  l=130858   m=131834
Argument list too long
r=131346  l=130858   m=131346
Argument list too long
r=131102  l=130858   m=131102
r=131102  l=130980   m=130980
r=131102  l=131041   m=131041
r=131102  l=131071   m=131071
Argument list too long
r=131086  l=131071   m=131086
Argument list too long
r=131078  l=131071   m=131078
Argument list too long
r=131074  l=131071   m=131074
Argument list too long
r=131072  l=131071   m=131072
r=131072  l=131071   m=131071

Finished.  Result: 131072
Checking:
Ok

real    0m0.058s
user    0m0.012s
sys     0m0.020s
+++++++++++++++++++++++++++++

I wait for your feedback.

Cheers,

  Alessandro.


The University of Aberdeen is a charity registered in Scotland, No SC013683.