source: doc/theses/mike_brooks_MMath/benchmarks/list/tailq-bug.c@ 38093ae

/*

There is a right way and a wrong way to remove the last element of a tailq.
The right way does it in two steps.
This fact is undocumented anywhere and never asked on SO.

When the TAILQ_REMOVE is in an intermediate state of removal, it proceeds with a subsequent step starting from its "remove this guy" argument.
So "remove this guy" must be fully evaluated to a concrete node (call by value).
If you try to do it with nested expressions, this subsequent call of "from which guy again?" performs an evaluation of TAILQ_LAST in the intermediate state (call by name), which gives the wrong value.
Everything then gets trashed.

The actual/expected annotations are for the symptom that led me to the test.
  actual means without -DFIXIT
  expected obtains with -DFIXIT
Other outputs are unannotated, but we can easily see things getting trashed in them too.

*/


#include <sys/queue.h>
#include <stdio.h>

#ifdef FIXIT
#define MY_TAILQ_REMOVE_LAST(headp, TYPE, HEADNAME, NAME) ({\
    struct TYPE * last = TAILQ_LAST(headp, HEADNAME); \
    TAILQ_REMOVE(headp, last, NAME); \
})
#else
#define MY_TAILQ_REMOVE_LAST(headp, TYPE, HEADNAME, NAME) \
    TAILQ_REMOVE(headp, TAILQ_LAST(headp, HEADNAME), NAME)
#endif

int main () {

struct req {
  int pri, rqr;
  TAILQ_ENTRY(req) x;
};

TAILQ_HEAD(reql, req);

struct reql reqs = TAILQ_HEAD_INITIALIZER(reqs);
TAILQ_INIT(&reqs);

struct req
  r1 = {1, 42},
  r2 = {2, 42};

struct req *cur;
/*
  (Irrelevant to the bug, not a problem:)
  You can't navigate next/prev for unlisted elements (it crashes).
  So I only show them for listed ones.
*/

printf("r1@%p, r2@%p\n", &r1, &r2);

printf("reqs.first = %p\n", TAILQ_FIRST(&reqs));
printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql));
printf("reqs =");
TAILQ_FOREACH(cur, &reqs, x)
    printf(" %p", cur);
printf("\n");


TAILQ_INSERT_TAIL(&reqs, &r1, x);

printf("-\n");
printf("r1.next=%p\n", TAILQ_NEXT(&r1, x));             // a&e: (nil)   is last
printf("r1.prev=%p\n", TAILQ_PREV(&r1, reql, x));       // a&e: (nil)   is first

printf("reqs.first = %p\n", TAILQ_FIRST(&reqs));
printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql));
printf("reqs =");
TAILQ_FOREACH(cur, &reqs, x)
    printf(" %p", cur);
printf("\n");

TAILQ_INSERT_TAIL(&reqs, &r2, x);

printf("-\n");
printf("r1.next=%p\n", TAILQ_NEXT(&r1, x));             // a&e: @r2     has succ
printf("r1.prev=%p\n", TAILQ_PREV(&r1, reql, x));       // a&e: (nil)   is first
printf("r2.next=%p\n", TAILQ_NEXT(&r2, x));             // a&e: (nil)   is last
printf("r2.prev=%p\n", TAILQ_PREV(&r2, reql, x));       // a&e: @r1     has pred

printf("reqs.first = %p\n", TAILQ_FIRST(&reqs));
printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql));
printf("reqs =");
TAILQ_FOREACH(cur, &reqs, x)
    printf(" %p", cur);
printf("\n");

MY_TAILQ_REMOVE_LAST(&reqs, req, reql, x);

printf("-\n");
printf("r1.next=%p\n", TAILQ_NEXT(&r1, x));             //   e: (nil)   is last;   a: @r2
printf("r1.prev=%p\n", TAILQ_PREV(&r1, reql, x));       //   e: (nil)   is first;  a: @r2

printf("reqs.first = %p\n", TAILQ_FIRST(&reqs));
printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql));
printf("reqs =");
TAILQ_FOREACH(cur, &reqs, x)
    printf(" %p", cur);
printf("\n");

MY_TAILQ_REMOVE_LAST(&reqs, req, reql, x);

printf("-\n");

printf("reqs.first = %p\n", TAILQ_FIRST(&reqs));
printf("reqs.last = %p\n", TAILQ_LAST(&reqs, reql));
printf("reqs =");                                       //   e: (none);  a: @
TAILQ_FOREACH(cur, &reqs, x)
    printf(" %p", cur);
printf("\n");

}