Date: Thu, 18 Sep 1997 21:40:26 +0000 (GMT) From: Terry Lambert <tlambert@primenet.com> To: nate@mt.sri.com (Nate Williams) Cc: 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: <199709182140.OAA15537@usr03.primenet.com> In-Reply-To: <199709181912.NAA13699@rocky.mt.sri.com> from "Nate Williams" at Sep 18, 97 01:12:18 pm
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. 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. If the pointer traverses to itself, this is a simpler case, and you can traverse from the top of the list to the pointer to indicate the address of the looped entry, and the address of the entry that points to it. If the pointer does not traverse to itself, your count is 2 or more. Now you bsearch for the start. You do this by: 1) Set N and M to pow(log2(expected members)+1,2)/2 2) Traverse from the top to N or the expected members, whichever is first (the algorithm is iterated, so it may be that N exceeds expeded members at some point) 3) Traverse the loop to find your N. If you find it before you find the loop "start" again then the loop starts at N or earlier; otherwise it starts after N. If the count is exactly the count, then you picked a start equal to the loop start and are done. 4) Set M to M/2. Add or subtract M to/from N, depending on #3. Goto #2. Display the address of the entry immediately before the loop, and the address of the entry for the first and second and last elements of the loop. Display as the user would see them, so the user's debugger can be used to locate the variables involved. > > No, all you have to do is to make each allocation have it's own set of > > pages, munmap them when free is called and never use those pages again. > > > > You run out of address space really fast, and it is slow, but it works. > > It's slow, but how would it cause malloc to hang? It wouldn't. He's describing an algorithm for 100% reliably detecting multiple frees, and use-after-free, not the existing phkmalloc algorithm. Regards, Terry Lambert terry@lambert.org --- Any opinions in this posting are my own and not those of my present or previous employers.
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?199709182140.OAA15537>