DELTA windows-head-tail-queue-removal-20060525

Today I committed a significant patch to the OpenAFS for Windows source
code.  DELTA windows-head-tail-queue-removal-20060525.

http://www.openafs.org/cgi-bin/wdelta/windows-head-tail-queue-removal-20060525

This patch will address a serious problem that has plagued OpenAFS for
Windows since IBM contributed the code back in 2000.   IBM implemented
two kinds of lists that they refer to as queues:

 * a list with a pointer to the head in which all entries are either
   added or removed from the head.

 * a list with pointers to both the head and the tail in which entries
   are added to either the head or the tail but entries can only be
   removed from the head.

For years I have been trying to figure out how these lists have been
ending up corrupted in memory.   Every time I have looked I have missed
the answer which has been staring me in the face.   While IBM
implemented separate functions for adding entries to each type of list:

 * osi_QAdd(head, entry) for the first type

 * osi_QAddH(head, tail, entry) and osi_QAddT(head, tail, entry) for the
   second type

They only implemented one function for removing entries:

 * osi_QRemove(head, entry)

The side effect is that when removing an entry the tail pointer is never
updated.  This is not a problem if we never remove the last entry from
the list, but if we do, then the head points to NULL and the tail
continues to point to the last entry.  The next time an entry is added
the list will be inconsistent.

This fix will go into 1.4.2 and 1.5.2 when they are released.

Jeffrey Altman