[1511] in SIPB_Linux_Development
rx.c superset memory management bug (patch included)
daemon@ATHENA.MIT.EDU (Greg Stark)
Sun Oct 27 00:47:09 1996
Date: Sun, 27 Oct 96 00:46 EDT
From: Greg Stark <gsstark@MIT.EDU>
To: lord@cygnus.com
Cc: linux-dev@MIT.EDU
Cc: linux-gcc@vger.rutgers.edu
Hello,
I think i've found a bug in rx.c that pertains to the memory management of
rx_superset structures. The reference counts are maintained fairly liberally,
allowing supersets to be unprotected for short durations. This usually works
as long as no intervening code causes any memory management operations.
So for example rx_superset_cons is frequently passed an unprotected superset
cdr argument which is eventually protected in the superset_allocator because
of the cdr link. However, this unprotected cdr link is in danger during
rx_hash_store and i repeatedly observed it getting put on the superset
freelist somewhere in that code. Presumably this happens if rx_hash_store
decides to allocate a new hash table and that causes a call to
really_free_superstate. If the unprotected cdr was referenced by exactly one
other link and that link was freed by really_free_superstate then that would
cause the unprotected cdr to be cleaned up.
What i repeatedly observed was the following state being reached:
#0 superset_allocator (rules=0x803df18, val=0xbfffeed8) at rx.c:3053
#1 0x801a61c in rx_hash_store (table=0x80ea2d0, hash=75521, value=0xbfffeed8,
rules=0x803df18) at rx.c:813
#2 0x801de88 in rx_superset_cons (rx=0xbffff60c, car=0x80fc294, cdr=0x80ee5b4)
at rx.c:3246
#3 0x801dfe1 in rx_superstate_eclosure_union (rx=0xbffff60c, set=0x809a53c,
ecl=0x80fd1dc) at rx.c:3301
...
with the val argument pointing to a superset with a bogus reference count. The
bogus reference count is really a link pointer for the freelist. Eventually
someone tries to protect this superset and corrupts the freelist and the
program later crashes. (Actually, much later, not until two more supersets are
allocated off the freelist.)
Here's a patch that seems to have fixed the problem here. I'm not completely
sure this is the best fix; possibly a better idea would be to adopt a more
rigorous reference count policy ensuring that even return values and arguments
be counted. This would entail requireing functions that discard return values
to release supersets themselves and requiring rx_hash_allocator to initialize
the reference count to 1. However, i haven't seen any problems since fixing
this particular leak so this appears to be unnecessary.
If you have any questions about my explanation of the behaviour or the fix,
just ask; I didn't just report how to reproduce the bug because it was
observed in a network application (Zephyr) and seems to affect people very
differently. It seems to me that it would affect any program that compiles
many regular expressions.
I would appreciate it if you could tell me the result of this patch because i
don't track the beta versions of H.J.'s libc but I would like to incorporate
the final form of this fix.
greg <gsstark@mit.edu>
*** rx.c.~3~ Sat Oct 26 17:25:55 1996
--- rx.c Sat Oct 26 21:55:20 1996
***************
*** 3243,3252 ****
--- 3243,3258 ----
template.car = car;
template.cdr = cdr;
template.id = car->id;
+ /* This seems like it might be a kludge, but while hash_store will
+ protect cdr itself it might first allocate hash tables and stuff
+ which might cause it to be garbage collected before it's protected
+ -- [gsstark:19961026.2155EST] */
+ rx_protect_superset (rx, cdr);
hit = rx_hash_store (&cache->superset_table,
(unsigned long)car ^ car->id ^ (unsigned long)cdr,
(void *)&template,
&cache->superset_hash_rules);
+ rx_release_superset (rx, cdr);
return (hit
? (struct rx_superset *)hit->data
: 0);
