Bug 14950

Summary: queue(3) STAILQ_INSERT_TAIL is suprising when the queue is empty
Product: Base System Reporter: hgoldste <hgoldste>
Component: kernAssignee: GNATS administrator <gnats-admin>
Status: Closed FIXED    
Severity: Affects Only Me    
Priority: Normal    
Version: 3.3-STABLE   
Hardware: Any   
OS: Any   

Description Justin T. Gibbs freebsd_committer freebsd_triage 1999-11-17 15:18:37 UTC 
>>Synopsis:       queue(3) STAILQ_INSERT_TAIL is suprising when the queue is 
empty

...

>The handy STAILQ macro collection's STAILQ_INSERT_TAIL is broken
>for empty queue (fails to initialize the queue head's stqh_first field).
>If the code is not broken then the docs should probably point out
>the STAILQ_INSERT_TAIL's dependancy on !STAILQ_EMPTY

When an STAILQ is empty, head->stqh_last = &(head)->stqh_first.
Thus, STAILQ_INSERT_TAIL initializes head->stqh_first through the
stqh_last member:

#define STAILQ_INSERT_TAIL(head, elm, field) do {                       \
        (elm)->field.stqe_next = NULL;                                  \
        *(head)->stqh_last = (elm);                                     \
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^
        (head)->stqh_last = &(elm)->field.stqe_next;                    \
} while (0)

Of course if you fail to properly initialize an STAILQ, this assumption
will fail and the macro will not do the right thing. Do you have a
code example that displays a problem with the macros?  From inspection,
the macros look correct.

--
Justin
Comment 1 hgoldste 1999-11-17 16:10:00 UTC 

Fix: 

Work around:
if STAILQ_EMPTY
  Use STAILQ_INSERT_HEAD 
else
  Use STAILQ_INSERT_TAIL
How-To-Repeat: 
	
Create an empty tail queue with STAILQ_INIT.  Then use STAILQ_INSERT_TAIL
to add an entry to the queue.  Then test STAILQ_EMPTY which will report
empty.  Note that further use of _INSERT_TAIL on this queue will correctly
link the new records together except that the head node continues to point
to NULL
Comment 2 hgoldste 1999-11-17 19:29:31 UTC 
Justin T. Gibbs writes:
 > >>Synopsis:       queue(3) STAILQ_INSERT_TAIL is suprising when the queue is 
 > empty
...
 > Of course if you fail to properly initialize an STAILQ, this assumption
 > will fail and the macro will not do the right thing. Do you have a
 > code example that displays a problem with the macros?  From inspection,
 > the macros look correct.

Thank you Justin.  You're entirely correct on all counts.  Since you
took the trouble to verify queue.h you're at least entitled to a post
mortem on the problem (if you're interested).  If not interested,
please accept my thanks again and do feel free to close the PR out...

(prob: as you indicated, failure to initialize.  Not only was
_INSERT_TAIL called before it was _INITd but so was the state machine
(implementing the protocol to talk to a GPS board) that called
_INSERT_TAIL.  It's quite likely the unit'd state machine clobbered
other program data but in a way that wasn't apparent)
Comment 3 Justin T. Gibbs freebsd_committer freebsd_triage 1999-11-17 19:31:48 UTC 
State Changed
From-To: open->closed

Originator confirms that the bug was elsewhere in his code.