Hacker News Reader

Comment by haberman | Hacker News Reader

There are so many to choose from. Here is one I just thought up:

    void free_circularly_linked_list(struct node *head) {
      struct node *tmp = head;
      do {
        struct node *next = tmp->next;
        free(tmp);
        tmp = next;
      } while (tmp != head);
    }

Can you spot the undefined behavior?

View on HN

This is a great example because if it wasn't presented as "spot the UB", I'd expect very few people would raise a concern.

I've written up a demo with your code, running it through several analysers:

https://gist.github.com/technion/1b12c9b4581e915241d9483c5c2...

The tl;dr here is that tis-interpreter is a fantastic new tool, as it correctly complains about this.

Edit: I also note a departure from yester-year, where every linting tool would only manage to complain about unchecked malloc() returns.

The `tmp != head` comparion is UB because `head` is a dangling pointer after the first loop iteration, right?

Yep! To do this properly requires something more like:

    void free_circularly_linked_list(struct node *head) {
      struct node *tmp = head->next;
      while (1) {
        if (tmp == head) {
          /* Has to be a separate case since even assigning
           * a dangling pointer is UB I believe? */
          free(tmp);
          break;
        } else {
          struct node *next = tmp->next;
          free(tmp);
          tmp = next;
        }
      }
    }

I'm not sure what you are trying to achieve by using the infinite loop. There's a more direct way.

    void free_circularly_linked_list(struct node *head)
    {
      struct node *a = head->next;
      while (a != head) {
        struct node *b = a->next;
        free(a);
        a = b;
      }
      free(head);
    }

Great example, by the way!

Why is it UB?

Let's say head value is "10" and the memory at "10" is {..., next: "10"}

After the first iteration we will have:

Head: "10" Next: "10" Temp: "10"

With "10" pointing to freed memory. But why do we care? We are not dereferencing it, are we?

(I think I am missing something very obvious)

I think you’re missing the fact that "There are a lot of rules you need to be aware of that are not naturally-occurring results of the fundamentals."

I was indeed. Thanks for the insight!

Because the standard says even comparing a dangling pointer is UB, which was haberman's point about the standard being non-intuitive.

Thanks. I wasn't aware of that. I stand corrected!!

Reply on news.ycombinator.com