From owner-freebsd-hackers  Thu Sep 18 14:48:09 1997
Return-Path: <owner-freebsd-hackers>
Received: (from root@localhost)
          by hub.freebsd.org (8.8.7/8.8.7) id OAA09309
          for hackers-outgoing; Thu, 18 Sep 1997 14:48:09 -0700 (PDT)
Received: from ns.mt.sri.com (SRI-56K-FR.mt.net [206.127.65.42])
          by hub.freebsd.org (8.8.7/8.8.7) with ESMTP id OAA09285
          for <hackers@freebsd.org>; Thu, 18 Sep 1997 14:48:03 -0700 (PDT)
Received: from rocky.mt.sri.com (rocky.mt.sri.com [206.127.76.100])
	by ns.mt.sri.com (8.8.7/8.8.7) with ESMTP id PAA10068;
	Thu, 18 Sep 1997 15:46:21 -0600 (MDT)
Received: (from nate@localhost) by rocky.mt.sri.com (8.7.5/8.7.3) id PAA14637; Thu, 18 Sep 1997 15:46:19 -0600 (MDT)
Date: Thu, 18 Sep 1997 15:46:19 -0600 (MDT)
Message-Id: <199709182146.PAA14637@rocky.mt.sri.com>
From: Nate Williams <nate@mt.sri.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: Terry Lambert <tlambert@primenet.com>
Cc: nate@mt.sri.com (Nate Williams), phk@critter.freebsd.dk, gram@cdsec.com,
        hackers@freebsd.org
Subject: Re: Bug in malloc/free (was: Memory leak in getservbyXXX?)
In-Reply-To: <199709182140.OAA15537@usr03.primenet.com>
References: <199709181912.NAA13699@rocky.mt.sri.com>
	<199709182140.OAA15537@usr03.primenet.com>
X-Mailer: VM 6.29 under 19.15 XEmacs Lucid
Sender: owner-freebsd-hackers@freebsd.org
X-Loop: FreeBSD.org
Precedence: bulk

> > 
> > [ 'hangs' in malloc due to memory over-write causing circular lists ]
> 
> 
> 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.

Easy enough.

> Now you must find the length of the loop.  You save the current
> pointer, and traverse until you see it again, counting.  This count
> is the length of the loop.

Naw, you keep track of how many objects are on the list by
incrementing/decrementing when you add/remove objects on the list.
Otherwise, it's much too slow, and adding/subtracting one is a very
minor hit.  And, your solution assumes that the loop is indeed circular,
which it may/may not be.

> If the pointer traverses to itself, this is a simpler case

In my solution, it's still found, since you have *one* element, and if
yo traverse twice, you're in a circular loop.

[ Overly complicated solution deleted ]

Why make it hard when it can be easy?


Nate