I am using Coverity to check some code which uses TAILQ. It is complaining about several potential double-frees and use-after-frees which I don't really understand. The code is always similar to this:
#include <stdlib.h>
typedef struct data {
char file[64];
} data_t;
typedef struct dat {
TAILQ_ENTRY(dat) d_link;
data_t *data;
} dat_t;
TAILQ_HEAD(data_queue, dat);
struct data_queue dataq;
data_t* data_get_first(struct data_queue *q)
{
dat_t *d;
data_t *data;
d = TAILQ_FIRST(q);
if (d) {
data = d->data;
TAILQ_REMOVE(q, d, d_link);
free(d);
return data;
}
return NULL;
}
void loopq() {
data_t* data;
while((data = data_get_first(&dataq)) != NULL) {
...
}
}
Coverity is telling me, that during the while loop it could happen that tqh_first (so the first element of the queue) is freed and returned and on the next run this is freed again. Is my usage of TAILQ correct or do I need to somehow make sure that tqh_first is updated to be NULL after I remove the last element (so it is not freed again)? The removal code doesn't seem to do that (or at least it is not obvious to me where/how that happens):
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
#define TAILQ_REMOVE(head, elm, field) do { \
if ((TAILQ_NEXT((elm), field)) != NULL) \
TAILQ_NEXT((elm), field)->field.tqe_prev = \
(elm)->field.tqe_prev; \
else \
(head)->tqh_last = (elm)->field.tqe_prev; \
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
} while (0)
#define TAILQ_FIRST(head) ((head)->tqh_first)
#define TAILQ_HEAD(name, type) \
struct name { \
struct type *tqh_first; /* first element */ \
struct type **tqh_last; /* addr of last next element */ \
}
#define TAILQ_ENTRY(type) \
struct { \
struct type *tqe_next; /* next element */ \
struct type **tqe_prev; /* address of previous next element */ \
}
I modified the define to be a little bit more verbose for testing now:
#define TAILQ_REMOVE(head, elm, field) do { \
if ((TAILQ_NEXT((elm), field)) != NULL) { \
printf("Next != NULL\n"); \
printf("Setting next (0x%x) to prev (0x%x)\n", TAILQ_NEXT((elm), field)->field.tqe_prev, (elm)->field.tqe_prev); \
TAILQ_NEXT((elm), field)->field.tqe_prev = \
(elm)->field.tqe_prev; \
} else { \
printf("Next == NULL\n"); \
printf("Setting last (0x%x) to prev (0x%x), first is at 0x%x\n", (head)->tqh_last, (elm)->field.tqe_prev, (head)->tqh_first); \
(head)->tqh_last = (elm)->field.tqe_prev; \
} \
printf("Setting prev (0x%x) to next (0x%x)\n", *(elm)->field.tqe_prev, TAILQ_NEXT((elm), field)); \
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
} while (0)
and also printed what TAILQ_FIRST returned/what is assigned to d, the output is:
Got element 0x50e80260
Next == NULL
Setting last (0x50e80260) to prev (0x4f0ad020), first is at 0x50e80260
Setting prev (0x50e80260) to next (0x0)
Got element 0x0
So it looks like it is correctly updating the list and this is a false positive by Coverity?
Edit: Most of what I've said in the first section was early speculation and may not have held up after doing my full testing below. I think I was thrown a bit by the fact that some of the pointers were "double star". I've moved it to the bottom for reference.
I notice that you're doing:
struct data_queue dataq;
But, should that be:
struct data_queue dataq = TAILQ_HEAD_INITIALIZER(dataq);
Or, do you do the equivalent of that elsewhere?
Anyway, the definition is:
#define TAILQ_HEAD_INITIALIZER(head) \
{ NULL, &(head).tqh_first }
So, initially tqh_last is pointing to itself (e.g. tqh_first).
From your last debug run, per your comment:
I think I finally understand a little of what's going on. I updated the question with a little more debug output now. To me it looks like a false positive now. The crucial line seems to be
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field);which will set first to null when the last element is removed.
Yes, because at that point, tqe_prev is pointing to tqh_first, just as it does after the TAILQ_HEAD_INITIALIZER
So, ultimately, the code works. But, admittedly, this is a bit tricky. It would be easy enough for a static analyzer to be confused by this. That is, it doesn't recognize that tqe_prev can point to &q.tqh_first if the element is the first in the list.
You could try compiling with -fsanitize=address. That should tell you dynamically if there's an issue similar to what coverity is checking.
You didn't post the full code that processes the data_t struct, so it is possible that code has use after free or corruption.
Because of my erroneous speculation, I added a bunch of debug code to check for mismatches, UB, etc.
Although largely overkill, here it is:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stddef.h>
/*
* Tail queue definitions.
*/
// 1=add guard areas to structs
#ifndef GUARD
#define GUARD 1
#endif
// add debug print to macros (OP's debug printf)
#ifndef DEBUG
#define DEBUG 1
#endif
#if GUARD
#define HEAD_RSVP_MAX 4
#define HEAD_RSVP void *tqh_rsvp[HEAD_RSVP_MAX];
#define ELE_RSVP_MAX 2
#define ELE_RSVP void *tqe_rsvp[ELE_RSVP_MAX];
#else
#define HEAD_RSVP /**/
#define ELE_RSVP /**/
#endif
#define _TAILQ_HEAD(name, type, qual) \
struct name { \
qual type *tqh_first; /* first element */ \
qual type *qual *tqh_last; /* addr of last next element */ \
HEAD_RSVP \
}
#define TAILQ_HEAD(name, type) _TAILQ_HEAD(name, struct type,)
#define TAILQ_HEAD_INITIALIZER(head) \
{ NULL, &(head).tqh_first }
#define _TAILQ_ENTRY(type, qual) \
struct { \
ELE_RSVP \
qual type *tqe_next; /* next element */ \
qual type *qual *tqe_prev; /* address of previous next element */\
}
#define TAILQ_ENTRY(type) _TAILQ_ENTRY(struct type,)
/*
* Tail queue functions.
*/
#define TAILQ_INIT(head) do { \
(head)->tqh_first = NULL; \
(head)->tqh_last = &(head)->tqh_first; \
} while (/*CONSTCOND*/0)
#define TAILQ_INSERT_HEAD(head, elm, field) do { \
if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
(head)->tqh_first->field.tqe_prev = \
&(elm)->field.tqe_next; \
else \
(head)->tqh_last = &(elm)->field.tqe_next; \
(head)->tqh_first = (elm); \
(elm)->field.tqe_prev = &(head)->tqh_first; \
} while (/*CONSTCOND*/0)
#define TAILQ_INSERT_TAIL(head, elm, field) do { \
(elm)->field.tqe_next = NULL; \
(elm)->field.tqe_prev = (head)->tqh_last; \
*(head)->tqh_last = (elm); \
(head)->tqh_last = &(elm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
#define TAILQ_INSERT_AFTER(head, listelm, elm, field) do { \
if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
(elm)->field.tqe_next->field.tqe_prev = \
&(elm)->field.tqe_next; \
else \
(head)->tqh_last = &(elm)->field.tqe_next; \
(listelm)->field.tqe_next = (elm); \
(elm)->field.tqe_prev = &(listelm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
#define TAILQ_INSERT_BEFORE(listelm, elm, field) do { \
(elm)->field.tqe_prev = (listelm)->field.tqe_prev; \
(elm)->field.tqe_next = (listelm); \
*(listelm)->field.tqe_prev = (elm); \
(listelm)->field.tqe_prev = &(elm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
#if ! DEBUG
#define TAILQ_REMOVE(head, elm, field) do { \
if (((elm)->field.tqe_next) != NULL) \
(elm)->field.tqe_next->field.tqe_prev = \
(elm)->field.tqe_prev; \
else \
(head)->tqh_last = (elm)->field.tqe_prev; \
*(elm)->field.tqe_prev = (elm)->field.tqe_next; \
} while (/*CONSTCOND*/0)
#else
#define TAILQ_REMOVE(head, elm, field) do { \
if ((TAILQ_NEXT((elm), field)) != NULL) { \
printf("Next != NULL\n"); \
printf("Setting next=%p to prev=%p\n", \
TAILQ_NEXT((elm), field)->field.tqe_prev, \
(elm)->field.tqe_prev); \
printf("Setting next=%s to prev=%s\n", \
ptrshow2(TAILQ_NEXT((elm), field)->field.tqe_prev), \
ptrshow2((elm)->field.tqe_prev)); \
TAILQ_NEXT((elm), field)->field.tqe_prev = \
(elm)->field.tqe_prev; \
} else { \
printf("Next == NULL\n"); \
printf("Setting last=%s to prev=%s, first is at %s\n", \
ptrshow2((head)->tqh_last), ptrshow2((elm)->field.tqe_prev), \
ptrshow((head)->tqh_first)); \
(head)->tqh_last = (elm)->field.tqe_prev; \
} \
printf("Setting prev=%s to next=%s\n", \
ptrshow2((elm)->field.tqe_prev), ptrshow(TAILQ_NEXT((elm), field))); \
*(elm)->field.tqe_prev = TAILQ_NEXT((elm), field); \
} while (0)
#endif
#define TAILQ_FOREACH(var, head, field) \
for ((var) = ((head)->tqh_first); \
(var); \
(var) = ((var)->field.tqe_next))
#define TAILQ_FOREACH_REVERSE(var, head, headname, field) \
for ((var) = (*(((struct headname *)((head)->tqh_last))->tqh_last)); \
(var); \
(var) = (*(((struct headname *)((var)->field.tqe_prev))->tqh_last)))
#define TAILQ_CONCAT(head1, head2, field) do { \
if (!TAILQ_EMPTY(head2)) { \
*(head1)->tqh_last = (head2)->tqh_first; \
(head2)->tqh_first->field.tqe_prev = (head1)->tqh_last; \
(head1)->tqh_last = (head2)->tqh_last; \
TAILQ_INIT((head2)); \
} \
} while (/*CONSTCOND*/0)
/*
* Tail queue access methods.
*/
#define TAILQ_EMPTY(head) ((head)->tqh_first == NULL)
#define TAILQ_FIRST(head) ((head)->tqh_first)
#define TAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
#define TAILQ_LAST(head, headname) \
(*(((struct headname *)((head)->tqh_last))->tqh_last))
#define TAILQ_PREV(elm, headname, field) \
(*(((struct headname *)((elm)->field.tqe_prev))->tqh_last))
char *
strbuf(void)
{
static int idx = 0;
static char list[16][1000];
char *buf = list[idx];
++idx;
idx %= 16;
*buf = 0;
return buf;
}
typedef struct data {
char file[64];
int xid;
} data_t;
typedef struct dat {
#if GUARD
data_t *data;
void *ele_rsvp[ELE_RSVP_MAX];
TAILQ_ENTRY(dat) d_link;
#else
TAILQ_ENTRY(dat) d_link;
data_t *data;
#endif
int ele_xid; /* identifier */
} dat_t;
TAILQ_HEAD(data_queue, dat);
// NOTE/BUG(?): this was original code but where was it initialized?
#if 0
struct data_queue dataq;
#else
struct data_queue dataq = TAILQ_HEAD_INITIALIZER(dataq);
#endif
#define XMAGIC(_ptr,_item,_magic) \
((void *) (((uintptr_t) (_ptr)->_item) + (_magic)))
#define HMAGIC(_ptr,_item,_idx) \
XMAGIC(&_ptr[_idx],_item,0x01020304 + _idx)
#define EMAGIC(_ptr,_item,_idx) \
XMAGIC(&_ptr[idx],_item,0x01020304 + _idx)
#define HINIT(_ptr,_item,_idx) \
do { \
(_ptr)->_item[_idx] = HMAGIC(_ptr,_item,_idx); \
} while (0)
#define HCHECK(_ptr,_item,_idx) \
do { \
const void *exp = HMAGIC(_ptr,_item,_idx); \
const void *act = _ptr->_item[_idx]; \
printf("%s: HCHECK ptr=%p exp=%p act=%p idx=%d (%s)\n", \
who,_ptr,exp,act,_idx,#_item); \
if (exp != act) \
err = 1; \
} while (0)
char *
_ptrshow(char *bp,dat_t *ele)
{
bp += sprintf(bp,"ele=%p",ele);
do {
if (ele == NULL) {
bp += sprintf(bp," xid=NULL");
break;
}
#if 0
if (ele->data != NULL)
bp += sprintf(bp," xid=%d",ele->data->xid);
else
bp += sprintf(bp," xid=-1");
#else
bp += sprintf(bp," xid=%d",ele->ele_xid);
#endif
} while (0);
return bp;
}
char *
ptrshow(dat_t *ele)
{
char *buf = strbuf();
char *bp = buf;
bp += sprintf(bp,"(");
bp = _ptrshow(bp,ele);
bp += sprintf(bp,")");
return buf;
}
char *
ptrshow2(dat_t **elp)
{
char *buf = strbuf();
char *bp = buf;
do {
bp += sprintf(bp,"(elp=%p",elp);
if (*elp != NULL) {
bp += sprintf(bp," ");
bp = _ptrshow(bp,*elp);
}
bp += sprintf(bp,")");
} while (0);
return buf;
}
void
qshow(struct data_queue *list,const char *who)
{
dat_t *ele;
printf("qshow: ENTER (from %s)\n",who);
TAILQ_FOREACH(ele, &dataq, d_link)
printf("qshow: ELEMENT ele=%s\n",ptrshow(ele));
printf("qshow: EXIT\n");
}
void
init_head(struct data_queue *list)
{
#if GUARD
const char *who = "init_head";
for (int idx = 0; idx < HEAD_RSVP_MAX; ++idx)
HINIT(list,tqh_rsvp,idx);
int err = 0;
for (int idx = 0; idx < HEAD_RSVP_MAX; ++idx)
HCHECK(list,tqh_rsvp,idx);
if (err)
exit(1);
#endif
}
void
check_head(struct data_queue *list,const char *who)
{
#if GUARD
printf("%s: HCHECK tgh_first=%s tgh_last=%p\n",
who,ptrshow(list->tqh_first),list->tqh_last);
int err = 0;
for (int idx = 0; idx < HEAD_RSVP_MAX; ++idx)
HCHECK(list,tqh_rsvp,idx);
if (err)
exit(1);
#endif
}
data_t *
data_get_first(struct data_queue *q)
{
dat_t *d;
data_t *data = NULL;
printf("data_get_first: ENTER\n");
check_head(&dataq,"data_get_first/ENTER");
d = TAILQ_FIRST(q);
if (d) {
printf("data_get_first: FIRST d=%s\n",ptrshow(d));
qshow(q,"data_get_first/BEF");
data = d->data;
TAILQ_REMOVE(q, d, d_link);
free(d);
check_head(&dataq,"data_get_first/EXIT");
printf("data_get_first: FIRST tqh_first=%s\n",ptrshow(q->tqh_first));
qshow(q,"data_get_first/AFT");
}
printf("data_get_first: EXIT data=%d\n",(data != NULL) ? data->xid : -1);
return data;
}
int
main(void)
{
data_t *data;
dat_t *ele;
// initialize the guard areas in the queue head
init_head(&dataq);
printf("main: dataq=%p\n",&dataq);
printf("main: TQHBEFORE tqh_first=%s tqh_last=%s\n",
ptrshow(dataq.tqh_first),ptrshow2(dataq.tqh_last));
for (int idx = 1; idx <= 5; ++idx) {
data = calloc(1,sizeof(*data));
data->xid = idx;
ele = calloc(1,sizeof(*ele));
ele->data = data;
ele->ele_xid = idx;
printf("main: BEFORE ele=%s\n",ptrshow(ele));
TAILQ_INSERT_HEAD(&dataq,ele,d_link);
printf("main: TQEAFTER tqe_next=%s tqe_prev=%s\n",
ptrshow(ele->d_link.tqe_next),ptrshow2(ele->d_link.tqe_prev));
printf("main: TQHAFTER tqh_first=%s tqh_last=%s\n",
ptrshow(dataq.tqh_first),ptrshow2(dataq.tqh_last));
check_head(&dataq,"main/insert");
}
while ((data = data_get_first(&dataq)) != NULL) {
printf("loopq: DATAITEM xid=%d\n",data->xid);
// NOTE: here is where the "real" code goes ...
// release the data
free(data);
// define this to generate a use-after-free (which is caught by
// compiling with -fsanitize=address)
#ifdef USEFREE
data->xid += 1;
#endif
}
return 0;
}
Here is the program output I got (run through an indenter):
init_head: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
init_head: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
init_head: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
init_head: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
main: dataq=0x4050c0
main: TQHBEFORE tqh_first=(ele=(nil) xid=NULL) tqh_last=(elp=0x4050c0)
main: BEFORE ele=(ele=0x606000000080 xid=1)
main: TQEAFTER tqe_next=(ele=(nil) xid=NULL) tqe_prev=(elp=0x4050c0 ele=0x606000000080 xid=1)
main: TQHAFTER tqh_first=(ele=0x606000000080 xid=1) tqh_last=(elp=0x6060000000a8)
main/insert: HCHECK tgh_first=(ele=0x606000000080 xid=1) tgh_last=0x6060000000a8
main/insert: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
main: BEFORE ele=(ele=0x6060000000e0 xid=2)
main: TQEAFTER tqe_next=(ele=0x606000000080 xid=1) tqe_prev=(elp=0x4050c0 ele=0x6060000000e0 xid=2)
main: TQHAFTER tqh_first=(ele=0x6060000000e0 xid=2) tqh_last=(elp=0x6060000000a8)
main/insert: HCHECK tgh_first=(ele=0x6060000000e0 xid=2) tgh_last=0x6060000000a8
main/insert: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
main: BEFORE ele=(ele=0x606000000140 xid=3)
main: TQEAFTER tqe_next=(ele=0x6060000000e0 xid=2) tqe_prev=(elp=0x4050c0 ele=0x606000000140 xid=3)
main: TQHAFTER tqh_first=(ele=0x606000000140 xid=3) tqh_last=(elp=0x6060000000a8)
main/insert: HCHECK tgh_first=(ele=0x606000000140 xid=3) tgh_last=0x6060000000a8
main/insert: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
main: BEFORE ele=(ele=0x6060000001a0 xid=4)
main: TQEAFTER tqe_next=(ele=0x606000000140 xid=3) tqe_prev=(elp=0x4050c0 ele=0x6060000001a0 xid=4)
main: TQHAFTER tqh_first=(ele=0x6060000001a0 xid=4) tqh_last=(elp=0x6060000000a8)
main/insert: HCHECK tgh_first=(ele=0x6060000001a0 xid=4) tgh_last=0x6060000000a8
main/insert: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
main: BEFORE ele=(ele=0x606000000200 xid=5)
main: TQEAFTER tqe_next=(ele=0x6060000001a0 xid=4) tqe_prev=(elp=0x4050c0 ele=0x606000000200 xid=5)
main: TQHAFTER tqh_first=(ele=0x606000000200 xid=5) tqh_last=(elp=0x6060000000a8)
main/insert: HCHECK tgh_first=(ele=0x606000000200 xid=5) tgh_last=0x6060000000a8
main/insert: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
main/insert: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: ENTER
data_get_first/ENTER: HCHECK tgh_first=(ele=0x606000000200 xid=5) tgh_last=0x6060000000a8
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST d=(ele=0x606000000200 xid=5)
qshow: ENTER (from data_get_first/BEF)
qshow: ELEMENT ele=(ele=0x606000000200 xid=5)
qshow: ELEMENT ele=(ele=0x6060000001a0 xid=4)
qshow: ELEMENT ele=(ele=0x606000000140 xid=3)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
Next != NULL
Setting next=0x606000000228 to prev=0x4050c0
Setting next=(elp=0x606000000228 ele=0x6060000001a0 xid=4) to prev=(elp=0x4050c0 ele=0x606000000200 xid=5)
Setting prev=(elp=0x4050c0 ele=0x606000000200 xid=5) to next=(ele=0x6060000001a0 xid=4)
data_get_first/EXIT: HCHECK tgh_first=(ele=0x6060000001a0 xid=4) tgh_last=0x6060000000a8
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST tqh_first=(ele=0x6060000001a0 xid=4)
qshow: ENTER (from data_get_first/AFT)
qshow: ELEMENT ele=(ele=0x6060000001a0 xid=4)
qshow: ELEMENT ele=(ele=0x606000000140 xid=3)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
data_get_first: EXIT data=5
loopq: DATAITEM xid=5
data_get_first: ENTER
data_get_first/ENTER: HCHECK tgh_first=(ele=0x6060000001a0 xid=4) tgh_last=0x6060000000a8
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST d=(ele=0x6060000001a0 xid=4)
qshow: ENTER (from data_get_first/BEF)
qshow: ELEMENT ele=(ele=0x6060000001a0 xid=4)
qshow: ELEMENT ele=(ele=0x606000000140 xid=3)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
Next != NULL
Setting next=0x6060000001c8 to prev=0x4050c0
Setting next=(elp=0x6060000001c8 ele=0x606000000140 xid=3) to prev=(elp=0x4050c0 ele=0x6060000001a0 xid=4)
Setting prev=(elp=0x4050c0 ele=0x6060000001a0 xid=4) to next=(ele=0x606000000140 xid=3)
data_get_first/EXIT: HCHECK tgh_first=(ele=0x606000000140 xid=3) tgh_last=0x6060000000a8
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST tqh_first=(ele=0x606000000140 xid=3)
qshow: ENTER (from data_get_first/AFT)
qshow: ELEMENT ele=(ele=0x606000000140 xid=3)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
data_get_first: EXIT data=4
loopq: DATAITEM xid=4
data_get_first: ENTER
data_get_first/ENTER: HCHECK tgh_first=(ele=0x606000000140 xid=3) tgh_last=0x6060000000a8
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST d=(ele=0x606000000140 xid=3)
qshow: ENTER (from data_get_first/BEF)
qshow: ELEMENT ele=(ele=0x606000000140 xid=3)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
Next != NULL
Setting next=0x606000000168 to prev=0x4050c0
Setting next=(elp=0x606000000168 ele=0x6060000000e0 xid=2) to prev=(elp=0x4050c0 ele=0x606000000140 xid=3)
Setting prev=(elp=0x4050c0 ele=0x606000000140 xid=3) to next=(ele=0x6060000000e0 xid=2)
data_get_first/EXIT: HCHECK tgh_first=(ele=0x6060000000e0 xid=2) tgh_last=0x6060000000a8
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST tqh_first=(ele=0x6060000000e0 xid=2)
qshow: ENTER (from data_get_first/AFT)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
data_get_first: EXIT data=3
loopq: DATAITEM xid=3
data_get_first: ENTER
data_get_first/ENTER: HCHECK tgh_first=(ele=0x6060000000e0 xid=2) tgh_last=0x6060000000a8
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST d=(ele=0x6060000000e0 xid=2)
qshow: ENTER (from data_get_first/BEF)
qshow: ELEMENT ele=(ele=0x6060000000e0 xid=2)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
Next != NULL
Setting next=0x606000000108 to prev=0x4050c0
Setting next=(elp=0x606000000108 ele=0x606000000080 xid=1) to prev=(elp=0x4050c0 ele=0x6060000000e0 xid=2)
Setting prev=(elp=0x4050c0 ele=0x6060000000e0 xid=2) to next=(ele=0x606000000080 xid=1)
data_get_first/EXIT: HCHECK tgh_first=(ele=0x606000000080 xid=1) tgh_last=0x6060000000a8
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST tqh_first=(ele=0x606000000080 xid=1)
qshow: ENTER (from data_get_first/AFT)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
data_get_first: EXIT data=2
loopq: DATAITEM xid=2
data_get_first: ENTER
data_get_first/ENTER: HCHECK tgh_first=(ele=0x606000000080 xid=1) tgh_last=0x6060000000a8
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST d=(ele=0x606000000080 xid=1)
qshow: ENTER (from data_get_first/BEF)
qshow: ELEMENT ele=(ele=0x606000000080 xid=1)
qshow: EXIT
Next == NULL
Setting last=(elp=0x6060000000a8) to prev=(elp=0x4050c0 ele=0x606000000080 xid=1), first is at (ele=0x606000000080 xid=1)
Setting prev=(elp=0x4050c0 ele=0x606000000080 xid=1) to next=(ele=(nil) xid=NULL)
data_get_first/EXIT: HCHECK tgh_first=(ele=(nil) xid=NULL) tgh_last=0x4050c0
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/EXIT: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: FIRST tqh_first=(ele=(nil) xid=NULL)
qshow: ENTER (from data_get_first/AFT)
qshow: EXIT
data_get_first: EXIT data=1
loopq: DATAITEM xid=1
data_get_first: ENTER
data_get_first/ENTER: HCHECK tgh_first=(ele=(nil) xid=NULL) tgh_last=0x4050c0
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x14253d4 act=0x14253d4 idx=0 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425405 act=0x1425405 idx=1 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425436 act=0x1425436 idx=2 (tqh_rsvp)
data_get_first/ENTER: HCHECK ptr=0x4050c0 exp=0x1425467 act=0x1425467 idx=3 (tqh_rsvp)
data_get_first: EXIT data=-1
My early speculation ... Most of it is/was wrong ... Alas ... I've kept this is show just how wrong I could be but it did put me on the right track [eventually ;-)]
Ahh ... I think I know what is happening [and why], but to test my assumption(s), it would help to have the initialization code that gets the list into the initial state. I can synthesize this, but, to compare apples-to-apples, it might help to have your init code.
A hint: your last debug code (and comment) provides the clue. The field arg allows the links in the element to be at any offset, but an implicit assumption is that they are at offset 0.
The list and element/link structs use different names/types but they (offset-wise) are the same. That is, looking at TAILQ_HEAD and TAILQ_ENTRY, we have tqh_first and tqe_next at the same offset and tqh_last and tqe_prev at the same offset.
So, when the TAILQ_REMOVE macro changes tqe_next, it has to be modifying tqh_first to get the results you're seeing.
That is, the macro is assuming an equivalence of the two structs, which works in practice. But, it is modifying a list struct using element code. This is confusing to me, and I bet it confuses coverity as well.
The macros are old (from 1991), so the sort of "trickery" they employ would not be written as new code these days.
I bet if you reverse the order of your dat_t struct, things will break badly with UB because then the two structs are no longer equivalent.