From owner-freebsd-hackers@FreeBSD.ORG  Thu Oct  6 16:58:55 2011
Return-Path: <owner-freebsd-hackers@FreeBSD.ORG>
Delivered-To: hackers@FreeBSD.org
Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34])
	by hub.freebsd.org (Postfix) with ESMTP id 66E191065670;
	Thu,  6 Oct 2011 16:58:55 +0000 (UTC) (envelope-from avg@FreeBSD.org)
Received: from citadel.icyb.net.ua (citadel.icyb.net.ua [212.40.38.140])
	by mx1.freebsd.org (Postfix) with ESMTP id 7BE808FC14;
	Thu,  6 Oct 2011 16:58:54 +0000 (UTC)
Received: from odyssey.starpoint.kiev.ua (alpha-e.starpoint.kiev.ua
	[212.40.38.101])
	by citadel.icyb.net.ua (8.8.8p3/ICyb-2.3exp) with ESMTP id TAA06513;
	Thu, 06 Oct 2011 19:58:52 +0300 (EEST)
	(envelope-from avg@FreeBSD.org)
Message-ID: <4E8DDE4B.4040608@FreeBSD.org>
Date: Thu, 06 Oct 2011 19:58:51 +0300
From: Andriy Gapon <avg@FreeBSD.org>
User-Agent: Mozilla/5.0 (X11; FreeBSD amd64;
	rv:7.0.1) Gecko/20111003 Thunderbird/7.0.1
MIME-Version: 1.0
To: lev@FreeBSD.org
References: <1034127827.20111006205103@serebryakov.spb.ru>
In-Reply-To: <1034127827.20111006205103@serebryakov.spb.ru>
X-Enigmail-Version: undefined
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Cc: hackers@FreeBSD.org
Subject: Re: how to debug RB_TREE for memory corruption?
X-BeenThere: freebsd-hackers@freebsd.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: Technical Discussions relating to FreeBSD
	<freebsd-hackers.freebsd.org>
List-Unsubscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>, 
	<mailto:freebsd-hackers-request@freebsd.org?subject=unsubscribe>
List-Archive: <http://lists.freebsd.org/pipermail/freebsd-hackers>
List-Post: <mailto:freebsd-hackers@freebsd.org>
List-Help: <mailto:freebsd-hackers-request@freebsd.org?subject=help>
List-Subscribe: <http://lists.freebsd.org/mailman/listinfo/freebsd-hackers>,
	<mailto:freebsd-hackers-request@freebsd.org?subject=subscribe>
X-List-Received-Date: Thu, 06 Oct 2011 16:58:55 -0000

on 06/10/2011 19:51 Lev Serebryakov said the following:
> Hello, Hackers.
> 
>   I'm writing some code, which uses RB_TREE from <sys/tree.h>. At some
> momoent, it crashes within REMOVE method with "elm" 0xa5a5a5a5 (I have
> malloc() debug options turned on).
>   So, it seems, that free()ed element presents somewhere in the tree,
> am I right?
>   Ok, I add printing of whole tree BEFORE removal call with simple
> recursive function. It doesn't crash and doesn't print any invalid pointers!
> 
>   How could it happen!? Tree is perfectly valid at line BEFORE
> RB_DELETE() call and crashes with bad pointer in this method!
> 
>   I could (theoretically!) belive, that my code forget to delete node
> from tree in some situations. But in such case tree printing function
> will crash (or print "0xa5a5a5a5" pointer) before RB_DELETE crash!
> 
>   Any hints how to debug such strange situation?

A trivial check first - does the element on which you call RB_DELETE actually
belong to the tree in question?


-- 
Andriy Gapon