5

We have a shell script that builds a long piped command chain in a variable and executes it with eval (the following code is simplified to the essential):

 cmd="cat /some/files | grep -v \"this\" | grep -v \"that\""
 cmd="$cmd | grep -v \"much more dynamical filter with variables\""
 ...
 result=`eval $cmd`

All worked fine so far but now it seems that the content of the cmd variable exceeds a limit. When it exceeds about 95970 bytes I will receive the error (although syntax is correct):

eval: line ...: syntax error near unexpected token `|'

I did some research, but I didn't get a clue (getconf ARG_MAX echoes 2621440, ulimit -a doesn't helped me, too).

Could someone please explain which limit this could be and maybe how to increase the limit or what is the best way to avoid it?


EDIT: I have tested it now on three different servers (centos) with a designated script. On all servers I ended up reaching 3333 pipes in one command with eval.

And I have found another page where someone experienced the same but without eval. So it seems to be just a limit of pipes.

Knowing that the limitation is probably caused by the number of pipes will help me to workaround the problem. So this is not the question anymore.

But I am still interested in how this limit is set or at least how to detect the value of the limit (probably not on every system 3333) without running a script for that.

It can be reproduced with:

yes cat | head -n 3334 | paste -sd '|' - | bash
  • 1
    Why do it through eval? Is there are some objection to do it directly result=$(grep -v "this" /some/files | grep -v "that") or through function cmd(){......}? – Costas Feb 20 '15 at 13:53
  • You can shorten grep -v this | grep -v that to grep -v 'this\|that'. – choroba Feb 20 '15 at 14:13
  • @Costas: The command has to be build dynamically with external data. Therfore I have to collect the different grep commands in a variable. The example above is extremely simplified. – hellcode Feb 20 '15 at 14:32
  • 4
    @hellcode - that has got to be the ugliest idea I've ever heard. You've got to come up with something else - you need some organizational process (I'd use sed) to parse all of that into something sensible. You don't just toss 3000 greps in the process pool for this and that. – mikeserv Feb 20 '15 at 15:15
  • 1
    @hellcode: are all the grep commands really grep -v "some pattern"? If so, you can use grep -v -e "some pattern" -e "some other pattern" -e "yet another pattern", and that grep command could be built up using an array instead of eval, which would require less quoting. – rici Feb 21 '15 at 4:47
10

The problem here is actually an issue with the bash parser. There is no workaround other than editing and recompiling bash, and the 3333 limit is likely to be the same on all platforms.

The bash parser is generated with yacc (or, typically, with bison but in yacc mode). yacc parsers are bottom-up parsers, using the LALR(1) algorithm which builds a finite state machine with a pushdown stack. Loosely speaking, the stack contains all not-yet-reduced symbols, along with enough information to decide which productions to use to reduce the symbols.

Such parsers are optimized for left-recursive grammar rules. In the context of an expression grammar, a left-recursive rule applies to a left-associative operator, such as ab in ordinary mathematics. That's left associative because the expression abc groups ("associates") to the left, making it equal to (ab)−c rather than a−(bc). By contrast, exponentiation is right-associative, so that abc is by convention evaluated as a(bc) rather than (ab)c.

bash operators are process operators, rather than arithmetic operators; these include short-circuit booleans (&& and ||) and pipes (| and |&), as well as sequencing operators ; and &. Like mathematical operators, most of these associate to the left, but the pipe operators associate to the right, so that cmd1 | cmd2 | cmd3 is parsed as though it were cmd1 | { cmd2 | cmd3 ; } as opposed to { cmd1 | cmd2 ; } | cmd3. (Most of the time the difference is not important, but it is observable. [See Note 1])

To parse an expression which is a sequence of left associative operators, you only need a small parser stack. Every time you hit an operator, you can reduce (parenthesize, if you like) the expression to the left of it. By contrast, parsing an expression which is a sequence of right associative operators requires that you put all of the symbols onto the parser stack until you reach the end of the expression, because only then can you start reducing (inserting parentheses). (That explanation involves quite a bit of hand-waving, since it was intended to be non-technical, but it is based on the working of the real algorithm.)

Yacc parsers will resize their parser stack at runtime, but there is a compile-time maximum stack size, which by default is 10000 slots. If the stack reaches the maximum size, any attempt to expand it will trigger an out-of-memory error. Because | is right associative, an expression of the form:

statement | statement | ... | statement 

will eventually trigger this error. If it were parsed in the obvious way, that would happen after 5,000 pipe symbols (with 5,000 statements). But because of the way the bash parser handles newlines, the actual grammar used is (roughly):

pipeline: command '|' optional_newlines pipeline

with the consequence that there is an optional_newlines grammar symbol after every |, so each pipe occupies three stack slots. Hence, the out-of-memory error is generated after 3,333 pipe symbols.

The yacc parser detects and signals the stack overflow, which it signals by calling yyerror("memory exhausted"). However, the bash implementation of yyerror tosses away the provided error message, and substitutes a message like "syntax error detected near unexpected token...". That's a bit confusing in this case.


Notes

  1. The difference in associativity is most easily observed using the |& operator, which pipes both stderr and stdout. (Or, more accurately, duplicates stdout into stderr after establishing the pipe.) For a simple example, suppose that the file foo does not exist in the current directory. Then

    # There is a race condition in this example. But it's not relevant.
    $ ls foo | ls foo |& tr n-za-m a-z
    ls: cannot access foo: No such file or directory
    yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
    # Associated to the left:
    $ { ls foo | ls foo ; } |& tr n-za-m a-z
    yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
    yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
    # Associated to the right:
    $ ls foo | { ls foo |& tr n-za-m a-z ; }
    ls: cannot access foo: No such file or directory
    yf: pnaabg npprff sbb: Nb fhpu svyr be qverpgbel
    
| improve this answer | |
  • Can the same limitation be expected in other shells? Fantastic answer, by the way? – mikeserv Feb 23 '15 at 22:35
  • 2
    @mikeserv: not necessarily. I don't know my way around the source code of other shells as well as bash; I do know that zsh uses a hand-built parser which probably does not have the same limitation. Any parser will run out of memory eventually if given a sufficiently complex input; the only real question is how it manifests the problem (and, if it is controlled, at what point.) – rici Feb 23 '15 at 23:05
  • 1
    Great answer. Same issue with yes 1 | head -n 5000 | paste -sd '^' | bc or gawk "$(yes 1 | head -n 5000 | paste -sd '^')" – Stéphane Chazelas Feb 24 '15 at 10:04
  • 1
    @StéphaneChazelas: Worth noting that, unlike bash, both bc and gawk display the "memory exhausted" message produced by the bison-generated parser. One might prefer "parser stack overflow", but it's still more informative than a generic "syntax error". – rici Feb 24 '15 at 15:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.