kmemleak: use rbtree instead of prio tree
authorMichel Lespinasse <[email protected]>
Mon, 8 Oct 2012 23:31:27 +0000 (16:31 -0700)
committerLinus Torvalds <[email protected]>
Tue, 9 Oct 2012 07:22:39 +0000 (16:22 +0900)
commit85d3a316c714197f94e75c1e5b2d37607d66e5de
tree3a53a0ed058c1bb9647ea0f4da2d5e2fd97f68cc
parent6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08
kmemleak: use rbtree instead of prio tree

kmemleak uses a tree where each node represents an allocated memory object
in order to quickly find out what object a given address is part of.
However, the objects don't overlap, so rbtrees are a better choice than
prio tree for this use.  They are both faster and have lower memory
overhead.

Tested by booting a kernel with kmemleak enabled, loading the
kmemleak_test module, and looking for the expected messages.

Signed-off-by: Michel Lespinasse <[email protected]>
Cc: Rik van Riel <[email protected]>
Cc: Hillf Danton <[email protected]>
Cc: Peter Zijlstra <[email protected]>
Cc: Andrea Arcangeli <[email protected]>
Cc: David Woodhouse <[email protected]>
Acked-by: Catalin Marinas <[email protected]>
Tested-by: Catalin Marinas <[email protected]>
Signed-off-by: Andrew Morton <[email protected]>
Signed-off-by: Linus Torvalds <[email protected]>
mm/kmemleak.c