Date: Sun, 21 Sep 1997 19:35:04 +0200 (MET DST) From: Eivind Eklund <perhaps@yes.no> To: Terry Lambert <tlambert@primenet.com> Cc: nate@mt.sri.com, phk@critter.freebsd.dk, nate@mt.sri.com, gram@cdsec.com, hackers@FreeBSD.ORG Subject: Re: Bug in malloc/free (was: Memory leak in getservbyXXX?) Message-ID: <199709211735.TAA20824@bitbox.follo.net> In-Reply-To: Terry Lambert's message of Thu, 18 Sep 1997 21:40:26 %2B0000 (GMT) References: <199709181912.NAA13699@rocky.mt.sri.com> <199709182140.OAA15537@usr03.primenet.com>
next in thread | previous in thread | raw e-mail | index | archive | help
>
> > > Anyway, if you think so: do like so many others have done, look at the
> > > source for phkmalloc.c and try to spot the error. I can't.
> >
> > I know, and I don't expect you to find any. But, it doesn't mean there
> > isn't one. :)
> >
> > [ 'hangs' in malloc due to memory over-write causing circular lists ]
>
> Actually, I was thinking of this, too.
>
> You could determine that a list is circular by maintaining a count of
> the number of objects that are supposed to be on the freelist. Then
> you count the number of "next" traversals which occur, and when it
> excceeds the count of how many are supposed to be there, then you
> know you have a problem.
Why make it this hard, and subject to trashing of the list count? The
following code will check for a circular loop (no knowledge of length
required) for a single-linked list:
/* Traverse with single and half-speed pointers. If the
single-speed pointer intercept the half-speed pointer, we
have a loop. */
struct node *p1;
struct node *p2;
p1 = p2 = list;
while (p1) {
p1 = p1->next;
if (p1 == p2)
abort()
p1 = p1->next;
if (p1 == p2)
abort();
p2 = p2->next;
if (p1 == p2)
abort();
}
I believe either the last or the middle check can be dropped, but I've
never taken the time to actually work this out. Checking for loops is
something I only do in debug-conditionalized code, anyway. To find
the more info on the loop, follow your (Terry's) suggestions.
For a double-linked list it is even more trivial - just check that the
back-links always are correct. (I've got code to find just how a list
is corrupted, if that is of interest. It is based on having a head
and a tail pointer and a special list format (head, NULL, tail - the
head and tail nodes have a NULL next and prev pointer, and are not
part of the list proper) but that should be readily modifiable)
Eivind.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709211735.TAA20824>