Debian Bug report logs - #195719
grep uses too much memory

Toggle useless messages

Message #5 received at submit@bugs.debian.org (full text, mbox, reply):

From: KORN Andras <korn-debbugs@chardonnay.math.bme.hu>

To: Debian Bug Tracking System <submit@bugs.debian.org>

Subject: grep: memory leak?

Date: Sun, 1 Jun 2003 21:47:32 +0200

Package: grep
Version: 2.5.1-5
Severity: normal

Hi,

21936 webalize  19  19 2661m 808m  404 R 38.4 80.1 693:26.00 grep -haf /store/tmp/grepfile.21921

/store/tmp/grepfile.21921 is 17272 lines long; it contains patterns
like:

^yokiza.demon.nl

I.e. all lines begin with ^ and contain a hostname or IP address.

grep is invoked as:

zcat large-file1.gz [...] large-fileN.gz \
	| grep -haf /store/tmp/grepfile.21921 \
	| gzip -9 \
	> somefile.gz

The large-files are apache accesslogs in "combined" format.

I fail to see why this should need so much RAM. (Perhaps there is a
reason, but it isn't apparent.)

Andrew

-- System Information:
Debian Release: testing/unstable
Architecture: i386
Kernel: Linux stop 2.4.21-pre5-xfs-stop #1 Thu Feb 27 12:03:37 CET 2003 i686
Locale: LANG=C, LC_CTYPE=C

Versions of packages grep depends on:
ii  libc6                         2.3.1-17   GNU C Library: Shared libraries an

-- no debconf information

Message #10 received at 195719@bugs.debian.org (full text, mbox, reply):

From: Justin Pryzby <justinpryzby@users.sourceforge.net>

To: korn-debbugs@chardonnay.math.bme.hu

Cc: 195719@bugs.debian.org

Subject: grep bug: -f leaks memory

Date: Thu, 25 Nov 2004 14:04:59 -0500

Hi Andrew,

Last year, you reported a bug in with `grep -f `.  I'm trying to do
something similar, and I, too, believe that grep has a memory leak.
The memory use increases mostly-monotonically, and my grep is
eventually killed, after using 1.5GB of RAM+Swap.  My file is 8000
lines, with each line beginning with ^ and ending with $.  I have not
escaped some . characters.

Do you have any more information to report?

Thanks,
Justin

Message #15 received at 195719-quiet@bugs.debian.org (full text, mbox, reply):

From: Justin Pryzby <justinpryzby@users.sourceforge.net>

To: 195719-quiet@bugs.debian.org

Subject: compilation

Date: Thu, 25 Nov 2004 17:59:13 -0500

src/grep.c:main (*compile)(); uses a constant 82MB of RAM and takes 7
minutes.  That is acceptable, but maybe not right.  Afterwards, it
begins its linearly increasing mem usage.

Justin

Message #20 received at 195719@bugs.debian.org (full text, mbox, reply):

From: Justin Pryzby <justinpryzby@users.sourceforge.net>

To: 195719@bugs.debian.org, korn-debbugs@chardonnay.math.bme.hu

Subject: grep bug

Date: Thu, 25 Nov 2004 18:38:53 -0500

Hi,

I think I've found the solution to the problem that you and I have
seen.  However, I suspect that there is still a problem with grep.

Try grep -Fxvf.  F means it is a string, not a pattern; x means to
match the *whole* string (it is equivalent, I think, to using ^ and
$).  v inverts the match (I want it, maybe you don't).  And f reads
from the file.

Alternately, try replacing and bare . characters in the file with \.
(otherwise . will matching anything).  Then, use grep -Fvf.  This also
does what I want (nearly the same thing as grep -Fxvf unescaped,
above; this also yields some false positives if one line is a strict
superset of another line).

This explains why grep -f takes such a long time to compile; it is
probably building a character list for every possible match match;
that also explains the memory usage (though I don't know that this is
its algorithm, or if that algorithm can't be vastly improved):

8000 lines * 20 chars per line = 160000 chars
This would also be the size of each element of the list of possible
matching strings

2 metachar per line * 256 bytes per metachar = 512 bytes / line

512*160000= 81920000 bytes = 82MB, almost precisely what I observed
compilation to use.

What I don't understand and cannot explain is why memory usage begins
to climb linearly *after* the compilation.  It seems to me that it
should do the exact same thing once per input line, and that should
never require more memory (assuming input lines are about the same
length, which they are).  Thus I suspect some other problem.

Cheers,
Justin

Message #25 received at 195719@bugs.debian.org (full text, mbox, reply):

From: Andras Korn <korn-debbugs@chardonnay.math.bme.hu>

To: Justin Pryzby <justinpryzby@users.sourceforge.net>

Cc: 195719@bugs.debian.org

Subject: Re: grep bug

Date: Fri, 26 Nov 2004 01:48:28 +0100

On Thu, Nov 25, 2004 at 06:38:53PM -0500, Justin Pryzby wrote:

Hi,

> I think I've found the solution to the problem that you and I have
> seen.  However, I suspect that there is still a problem with grep.
> 
> Try grep -Fxvf.  F means it is a string, not a pattern; x means to
> match the *whole* string (it is equivalent, I think, to using ^ and
> $).  v inverts the match (I want it, maybe you don't).  And f reads
> from the file.
> 
> Alternately, try replacing and bare . characters in the file with \.
> (otherwise . will matching anything).  Then, use grep -Fvf.  This also
> does what I want (nearly the same thing as grep -Fxvf unescaped,
> above; this also yields some false positives if one line is a strict
> superset of another line).

I don't think this is a solution. What you suggest can only reduce the
memory requirement of reading the -f file. However, as you also have noted,
memory usage increases as input length increases. As I see it, this doesn't
have anything to do with how the patterns are organized; it's either a bug
or a misfeature (some data structures being kept around for efficiency,
maybe?).

> What I don't understand and cannot explain is why memory usage begins
> to climb linearly *after* the compilation.  It seems to me that it
> should do the exact same thing once per input line, and that should
> never require more memory (assuming input lines are about the same
> length, which they are).  Thus I suspect some other problem.

Exactly.

Andras

-- 
                 Andras Korn <korn at chardonnay.math.bme.hu>
                 <http://chardonnay.math.bme.hu/~korn/>	QOTD:
                    At least a toad can eat what bugs him.

Message #28 received at 195719-forwarded@bugs.debian.org (full text, mbox, reply):

From: Justin Pryzby <justinpryzby@users.sourceforge.net>

To: bug-gnu-utils@gnu.org

Cc: 195719-forwarded@bugs.debian.org

Subject: grep -f leaks large amount of memory

Date: Sat, 10 Dec 2005 20:08:28 -0500

Please see <http://bugs.debian.org/cgi-bin/bugreport.cgi?bug=195719>
where it is documented that grep -f uses large amounts of memory, and
it is suggested that it might be leaking memory, causing linearly
increasing mem usage.

You can test with:

  grep '^c...............' /usr/share/dict/words >/tmp/words
  grep -f /tmp/words /usr/share/dict/words

The culprit seems to be

   1024816 bytes in 2596 blocks are still reachable in loss record 18 of 18
   at 0x1B90459D: malloc (vg_replace_malloc.c:130)
   by 0x804C5EC: xmalloc (dfa.c:143)
   by 0x804E9BB: build_state (dfa.c:2330)
   by 0x804FC7E: dfaexec (dfa.c:2372)
   by 0x8054DE2: EGexecute (search.c:402)
   by 0x804A6C5: grepbuf (grep.c:732)
   by 0x804B1A5: grepfile (grep.c:851)
   by 0x804C39D: main (grep.c:1788)

(valgrind --leak-check=full --show-reachable=yes ./build-tree/grep-2.5.1/src/grep -f /tmp/words /usr/share/dict/words)

-- 
Clear skies,
Justin

Message #33 received at 195719@bugs.debian.org (full text, mbox, reply):

From: Touko Korpela <tkorpela@phnet.fi>

To: 195719@bugs.debian.org, 195719-submitter@bugs.debian.org

Subject: Please test if this bug is still present

Date: Wed, 19 Sep 2007 00:26:35 +0300

Is this bug still present with grep version 2.5.1.ds2-6 (etch) or 
2.5.3~dfsg-2 (sid/lenny)?

Message #41 received at 195719-quiet@bugs.debian.org (full text, mbox, reply):

From: Andras Korn <korn-debbugs@chardonnay.math.bme.hu>

To: Touko Korpela <tkorpela@phnet.fi>, 195719-quiet@bugs.debian.org

Subject: Re: Bug#195719: Please test if this bug is still present

Date: Tue, 18 Sep 2007 23:56:43 +0200

On Wed, Sep 19, 2007 at 12:26:35AM +0300, Touko Korpela wrote:

Hi,

> Is this bug still present with grep version 2.5.1.ds2-6 (etch) or 
> 2.5.3~dfsg-2 (sid/lenny)?

uh, yes, but it will take a while. I don't do that particular thing anymore,
so I'll need to approximate the scenario.

Andras

-- 
                 Andras Korn <korn at chardonnay.math.bme.hu>
                 <http://chardonnay.math.bme.hu/~korn/>	QOTD:
                         Assassins do it from behind.

Message #46 received at 195719@bugs.debian.org (full text, mbox, reply):

From: Nicolas François <nicolas.francois@centraliens.net>

To: 195719@bugs.debian.org, 358858@bugs.debian.org

Cc: Justin Pryzby <justinpryzby@users.sourceforge.net>, John Goerzen <jgoerzen@complete.org>, KORN Andras <korn-debbugs@chardonnay.math.bme.hu>

Subject: Re: Bug#195719/#358858: grep: Leaks memory

Date: Sat, 6 Oct 2007 12:26:23 +0200

forcemerge 195719 358858
thanks

Hello,

I investigated this memory leak, and did not find any evidence of a memory
leak (a large amount of memory is used, without leaking).

Thus I'm merging 195719 358858 which are both about grep leaking memory.
Consequently, the 358858's severity is downgraded from important to normal.

I also recommend to close these bugs or tag them as wontfix and changing
the title to "grep uses too much memory", or a wishlist --lowmem option
could be implemented.



I'm answering below to some of the comments of #195719 and #358858

grep uses a DFA algorithm to perform regexp matching. This DFA algorithm
is either implemented in grep, or in the libc (when re_search is used).
Which DFA algorithm is used depends on the version of grep and on the grep
options.

The DFA algorithm is a state machine and each time it is used, the
automaton which represents the regexp may use more memory because a new
transition is investigated.
The memory allocated for the automaton is not freed after each line is
parsed, but it is kept so that if a transition path is also used in a
later line, the processing will be faster.
Thus more and more memory is allocated.

This explains Justin concern in #195719:

On Thu, Nov 25, 2004 at 06:38:53PM -0500, Justin Pryzby wrote:
> 
> What I don't understand and cannot explain is why memory usage begins
> to climb linearly *after* the compilation.  It seems to me that it
> should do the exact same thing once per input line, and that should
> never require more memory (assuming input lines are about the same
> length, which they are).  Thus I suspect some other problem.

Also, in #195719:
On Thu, Dec 10, 2005 at 20:08:28 -0500, Justin Pryzby wrote:
>
> The culprit seems to be
> 
>    1024816 bytes in 2596 blocks are still reachable in loss record 18 of 18
>    at 0x1B90459D: malloc (vg_replace_malloc.c:130)
>    by 0x804C5EC: xmalloc (dfa.c:143)
>    by 0x804E9BB: build_state (dfa.c:2330)
>    by 0x804FC7E: dfaexec (dfa.c:2372)
>    by 0x8054DE2: EGexecute (search.c:402)
>    by 0x804A6C5: grepbuf (grep.c:732)
>    by 0x804B1A5: grepfile (grep.c:851)
>    by 0x804C39D: main (grep.c:1788)
> 
> (valgrind --leak-check=full --show-reachable=yes ./build-tree/grep-2.5.1/src/grep -f /tmp/words /usr/share/dict/words)

I could not reproduce exactly the same (the grep DFA algorithm was
used, and currently grep uses re_search from the libc, so the `leak' is
now in the libc)

Given that /tmp/words was composed of > 16 characters words, the DFA
algorithm had to build one automaton per lines in /tmp/words, each of
these automaton should have more than 16 states, if there are 150 lines in
/tmp/words, we are close to the number of blocks allocated by build_state.

As the automata are used up to the last line, the buffers are not freed by
grep, but this is not a bug.
Doing a regfree at the end of grep shows that this valgrind record is then
freed (hence the memory is not leaking).



In this use case, I would recommend to use the -F option, as Justin
mentioned in #195719. This will avoid using a automaton.

In #358858, the search pattern is an IP, but John used "1.2.3.4".
To match an IP, again, the -F option could (should?) be used, or at least
the regular expression should be tighten to "1\.2\.3\.4"
(The maximum number of transitions is 7*256 versus probably something like
256*256*256*256)

So I'm not really surprised by a 200M memory usage.

Kind Regards,
-- 
Nekral

Message #53 received at 195719@bugs.debian.org (full text, mbox, reply):

From: Justin Pryzby <jpryzby+d@quoininc.com>

To: Nicolas François <nicolas.francois@centraliens.net>

Cc: 195719@bugs.debian.org, 358858@bugs.debian.org, John Goerzen <jgoerzen@complete.org>, KORN Andras <korn-debbugs@chardonnay.math.bme.hu>

Subject: Re: Bug#195719/#358858: grep: Leaks memory

Date: Sat, 6 Oct 2007 13:56:28 -0400

On Sat, Oct 06, 2007 at 12:26:23PM +0200, Nicolas François wrote:
> forcemerge 195719 358858
> thanks
> 
> Hello,
> 
> I investigated this memory leak, and did not find any evidence of a memory
> leak (a large amount of memory is used, without leaking).
Thanks for looking into it.  I also tried to reproduce it, both on
current sid-ish versions and in an etch chroot.  Unfortunatley I was
unable to reproduce it even with my own test case (doh)..  I initially
came across the problem in a different context.  Perhaps I'll try to
dig this up.

> grep uses a DFA algorithm to perform regexp matching. This DFA algorithm
> is either implemented in grep, or in the libc (when re_search is used).
> Which DFA algorithm is used depends on the version of grep and on the grep
> options.
Neat; thanks for the explanation.  Is this configured at compiletime
or ???  What options have what effect?

Thanks
Justin

Message #60 received at 195719-done@bugs.debian.org (full text, mbox, reply):

From: Aníbal Monsalve Salazar <anibal@debian.org>

To: 358858-done@bugs.debian.org, 195719-done@bugs.debian.org

Subject: Re: Bug#195719: /#358858: grep: Leaks memory

Date: Sun, 29 Mar 2009 13:21:05 +1100

Version: 2.5.1.ds2-4

On Sat, Oct 06, 2007 at 12:26:23PM +0200, Nicolas François wrote:
>forcemerge 195719 358858
>thanks
>
>Hello,
>
>I investigated this memory leak, and did not find any evidence of a
>memory leak (a large amount of memory is used, without leaking).
>
>Thus I'm merging 195719 358858 which are both about grep leaking
>memory.  Consequently, the 358858's severity is downgraded from
>important to normal.
>
>I also recommend to close these bugs or tag them as wontfix and
>changing the title to "grep uses too much memory", or a wishlist
>--lowmem option could be implemented.
>
>I'm answering below to some of the comments of #195719 and #358858
>
>grep uses a DFA algorithm to perform regexp matching. This DFA
>algorithm is either implemented in grep, or in the libc (when re_search
>is used).  Which DFA algorithm is used depends on the version of grep
>and on the grep options.
>
>The DFA algorithm is a state machine and each time it is used, the
>automaton which represents the regexp may use more memory because a new
>transition is investigated.  The memory allocated for the automaton is
>not freed after each line is parsed, but it is kept so that if a
>transition path is also used in a later line, the processing will be
>faster.  Thus more and more memory is allocated.
>
>This explains Justin concern in #195719:
>
>On Thu, Nov 25, 2004 at 06:38:53PM -0500, Justin Pryzby wrote:
>>
>>What I don't understand and cannot explain is why memory usage begins
>>to climb linearly *after* the compilation.  It seems to me that it
>>should do the exact same thing once per input line, and that should
>>never require more memory (assuming input lines are about the same
>>length, which they are).  Thus I suspect some other problem.
>
>Also, in #195719:
>On Thu, Dec 10, 2005 at 20:08:28 -0500, Justin Pryzby wrote:
>>
>>The culprit seems to be
>>
>>   1024816 bytes in 2596 blocks are still reachable in loss record 18 of 18
>>   at 0x1B90459D: malloc (vg_replace_malloc.c:130)
>>   by 0x804C5EC: xmalloc (dfa.c:143)
>>   by 0x804E9BB: build_state (dfa.c:2330)
>>   by 0x804FC7E: dfaexec (dfa.c:2372)
>>   by 0x8054DE2: EGexecute (search.c:402)
>>   by 0x804A6C5: grepbuf (grep.c:732)
>>   by 0x804B1A5: grepfile (grep.c:851)
>>   by 0x804C39D: main (grep.c:1788)
>>
>>(valgrind --leak-check=full --show-reachable=yes ./build-tree/grep-2.5.1/src/grep -f /tmp/words /usr/share/dict/words)
>
>I could not reproduce exactly the same (the grep DFA algorithm was
>used, and currently grep uses re_search from the libc, so the `leak' is
>now in the libc)
>
>Given that /tmp/words was composed of > 16 characters words, the DFA
>algorithm had to build one automaton per lines in /tmp/words, each of
>these automaton should have more than 16 states, if there are 150 lines
>in /tmp/words, we are close to the number of blocks allocated by
>build_state.
>
>As the automata are used up to the last line, the buffers are not freed
>by grep, but this is not a bug.  Doing a regfree at the end of grep
>shows that this valgrind record is then freed (hence the memory is not
>leaking).
>
>In this use case, I would recommend to use the -F option, as Justin
>mentioned in #195719. This will avoid using a automaton.
>
>In #358858, the search pattern is an IP, but John used "1.2.3.4".  To
>match an IP, again, the -F option could (should?) be used, or at least
>the regular expression should be tighten to "1\.2\.3\.4" (The maximum
>number of transitions is 7*256 versus probably something like
>256*256*256*256)
>
>So I'm not really surprised by a 200M memory usage.
>
>Kind Regards,
>-- 
>Nekral

Send a report that this bug log contains spam.