Comment by jcranmer | Hacker News Reader

Comment by jcranmer | Hacker News Reader

Parent Full thread

There's arguments to be made on both sides, but I think the problem with Linus's solution here is that it doesn't quite clearly establish the assumption being made, which gives it a bit too much of the 'cleverness' flavor that you allude to. A better implementation would be one that does establish why the use of pointers make sense:

   void remove_entry(node_t *entry) {
     // curr_ref is the address of the link pointing to curr
     node_t **curr_ref = &head;
     node_t *curr = *curr_ref;
     while (curr != NULL && curr != entry) {
       // Advance curr_ref and curr
       curr_ref = &curr->next;
       curr = *curr_ref;
     }
     if (curr) { *curr_ref = curr->next; }
   }

Choosing names somewhat more rationally, and making it clear that "curr" always points to the current node, and that "curr_ref" is the address of whatever pointer we followed to arrive at curr, makes it easier to establish the invariant that updating curr_ref is sufficient to insert or remove curr into a list, no matter if it's referring to the head link of a list or the next link of the prior node.

That does make it a bit clearer, but I do hope the compiler optimizes away the redundant curr variable.

Now, on a different note, I am a bit puzzled because I don’t see a free(*ptr) call in Linus’ or anyone else’s code. The code, as-is, would cause a memory leak.

There’s a need to capture the curr_ref before it’s overwritten, and free it after it’s overwritten.

At the end of the function curr == entry, so the caller already has a separate reference to the object. Also, removing a node from a list does not necessarily mean that you want to delete it. For example, you might want to put it in a different list.

The assembly code produced by my variant and Linus's variant is exactly equivalent, assuming you write the guards the same way. This effectively means that both curr_ref and curr will be live, although the compiler will note that it can substitute entry for curr and short curr's lifetime to only exist within the loop body in the form written here.

Usually those lists are intrusive -- their nodes are meant to be part of larger objects. They will be freed in other contexts, e.g. if protected by RCU, memory reclamation is postponed until all threads have quiesced. Or the nodes are allocated by one amongst many allocators (i.e. for performance, or better concurrence), so it is best for the structure itself not to make any assumption about where the memory should be returned to.

So generally, list implementations in C will not free the node, only remove references to it and return it.

The Linux kernel uses intrusively linked lists a whole lot - that means memory management is a separate concern from managing the list links.

Reply on news.ycombinator.com