[QUICK] talloc bugs

ronnie sahlberg ronniesahlberg at gmail.com
Mon Jun 29 06:58:48 MDT 2009


On Mon, Jun 29, 2009 at 9:49 PM, <tridge at samba.org> wrote:
> Hi Rusty,
>
>  > I'd like to see a simple example of where talloc_reference is required, so we
>  > can get less abstract in this discussion.
>
> yep, I've found the abstractness of the discussion unhelpful.
>

Please see this pseudo example of single linked list. Using a
talloc_reference() for describing each object to object->next
pointer/reference in the list.

I think this is not a too constructed example of where a graph, or
parent-less relations between objects are mapping better to the
problemspace than a tree.
Lets look at single linked lists instead of double linked lists, which
DLINK_ADD/REMOVE handles, but which for a single llinked list would
require a traversal of the list due to the relations between objects
in a single linked list can not adequately be described in a tree.



Single linked list.
We have a graph with n vertices, one vertive for each node in the list
and (n-1) edged connecting the vertivces.
Each vertice except the first and the last is connected by two edges.
One edge as the incoming edge, where a different vertice has an edge
coming to the local vertice and a second vertice that
originates in the local vertice and points to the next one in the list.
The exceptions are the very first vertice and the very last vertice
that has only one (or zero) edges attached.

Looking at two consequtive nodes in the list :

    +-----+       +-----+
... |  A  | ----> |  B  | ...
    +-----+       +-----+

A is one node, B is the next node, pointed to by A.
A here has a reference ( talloc_reference(A, B) ) to track that A is
referring to B and needs to do "stuff" if B is removed/freed.



Case 1, add a new node to the list after A but before B to create :

    +-----+       +-----+       +-----+
... |  A  | ----> |  C  | ----> |  B  | ...
    +-----+       +-----+       +-----+

When this happens, after we create C we do
    talloc_reference(C,B)
    talloc_reference(A,C)
    talloc_unreference(A,B)
and of course all the pointer dance for *next pointer updates.

We also do
    talloc_set_unreference_callback(A, B, NULL)
    talloc_set_unreference_callback(A, C, callback)
    talloc_set_unreference_callback(C, B, callback)
which defines a callback to call when the object we reference dissapears.


callback would look something like this :

/* "that" dissapeared, "this" needs to update the linkage to reflect this */
int callback(void *this, void *that)
{
    struct list_node *this_node = talloc_get_type(this, struct list_node)
    struct list_node *that_node = talloc_get_type(that, struct list_node)

    /* create a new reference from this node to the node beyond the
one we just deleted */
    talloc_reference(this_node, that_node->next)
    talloc_set_unreference_callback(this_node, that_node->next, callback)

    /* remove the callback for the next node since it is destroyed.
       this implicitely also removes the callback we registered
earlier for this_node->that_node */
    talloc_unreference(this_node, that_node)
    talloc_set_unreference_callback(this, that, NULL)   /* redundant */

    /* update the pointer */
    this->next = that->next
    return 0
}

This trivial callback above traps when a node we link to in the linked
list is removed
and fixes the list up.
For inserts like this it is dubious of its runtime value since you
still have to traverse the list sequentially anyway to find the object
to insert behind.
But it makes the concept/api cleaner.



Deletes are much more interesting and shows why a graph here is better
mapped to the space of linked lists than a tree.

Case 2, remove node C

    +-----+       +-----+       +-----+
... |  A  | ----> |  C  | ----> |  B  | ...
    +-----+       +-----+       +-----+

Application performs a talloc_destroy(C). I.e. remove all references
to C and the free it (and all its child objects).
The only object that has a reference to C here is A, and it hads the
callback from above registered for this edge/reference.
Talloc destroy(C) walks all referense removal callbacks one by one and
once it gets to the one for the relation between A->C the callback is
invoked and the callback.
At this stage there is only one reference that points to C and it is
the one from A->C we registered above with "callback" when we inserted
C betwene A and B.
That callback knows how to rebuild the graph. In this case it just
switches the reference and the callbacks to the next object in the
list.


Which leads back to
    +-----+       +-----+
... |  A  | ----> |  B  | ...
    +-----+       +-----+
without a need to re-walk the list just because the reference model
here more closely maps to the data structure than a tree does.

In case 2, we never needed to walk the linked list from head to
"object prior to the one we want to delete". We just deleted the
object and the list and the "unreference destructors" fixed it all up
automagically.
We did NOT have to re-walk the list again here for exactly the reason
we had a reference model that matched the use model in a list.

The reason that a linked list in talloc today requires that you do
walk the list when you need to fix up the dangling reference is
because of talloc being a tree structure and certain data models like
linked lists are not tree structured but graphs.


More information about the samba-technical mailing list