[RFC] [PATCH] talloc: Look up parents in O(1) time instead of O(n).

tridge at samba.org tridge at samba.org
Sat Jun 26 18:51:11 MDT 2010

Hi Kenneth,

In Samba talloc_parent() is much less common than talloc_realloc(),
which is why I chose to make talloc_realloc() avoid the list traversal
and talloc_parent() to do it.

It may be that the patch is OK anyway, as talloc_realloc() is probably
called mostly on contexts with no children. Before we apply this patch
we'd need to instrument talloc_realloc() and see how often it is
called with large numbers of children in Samba.

I also think you may have missed some changes, although I haven't
looked at it really carefully. The check for tc->parent in
_talloc_free_internal() and the two places in _talloc_steal_internal()
both look like they would need changes to check that
(tc->parent->child==tc) before removing the tc from the parent->child
list. I'm a bit surprised the test suite didn't pick this one up. That
may indicate a problem in the test suite, or maybe it works anyway for
some reason I can't see right now.

Cheers, Tridge

More information about the samba-technical mailing list