From owner-freebsd-hackers  Sun Sep 21 10:35:22 1997
Return-Path: <owner-freebsd-hackers>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id KAA09020
          for hackers-outgoing; Sun, 21 Sep 1997 10:35:22 -0700 (PDT)
Received: from bitbox.follo.net (bitbox.follo.net [194.198.43.36])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id KAA09011
          for <hackers@FreeBSD.ORG>; Sun, 21 Sep 1997 10:35:14 -0700 (PDT)
Received: (from eivind@localhost)
	by bitbox.follo.net (8.8.6/8.8.6) id TAA20824;
	Sun, 21 Sep 1997 19:35:04 +0200 (MET DST)
Date: Sun, 21 Sep 1997 19:35:04 +0200 (MET DST)
Message-Id: <199709211735.TAA20824@bitbox.follo.net>
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
In-reply-to: Terry Lambert's message of Thu, 18 Sep 1997 21:40:26 +0000 (GMT)
Subject: Re: Bug in malloc/free (was: Memory leak in getservbyXXX?)
References: <199709181912.NAA13699@rocky.mt.sri.com>
	<199709182140.OAA15537@usr03.primenet.com>
Sender: owner-freebsd-hackers@FreeBSD.ORG
X-Loop: FreeBSD.org
Precedence: bulk

> 
> > > 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.