how to debug RB_TREE for memory corruption?

Andriy Gapon avg at
Thu Oct 6 16:58:55 UTC 2011

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

More information about the freebsd-hackers mailing list