[OpenAFS-win32-devel] DELTA windows-head-tail-queue-removal-20060525

[Jeffrey Altman]

This is a cryptographically signed message in MIME format.

--------------ms040302030308020904000906
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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


--------------ms040302030308020904000906
Content-Type: application/x-pkcs7-signature; name="smime.p7s"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="smime.p7s"
Content-Description: S/MIME Cryptographic Signature

MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIJXzCC
AwowggJzoAMCAQICAw7NrTANBgkqhkiG9w0BAQQFADBiMQswCQYDVQQGEwJaQTElMCMGA1UE
ChMcVGhhd3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNv
bmFsIEZyZWVtYWlsIElzc3VpbmcgQ0EwHhcNMDUwNTI3MTc0NzU3WhcNMDYwNTI3MTc0NzU3
WjBzMQ8wDQYDVQQEEwZBbHRtYW4xFTATBgNVBCoTDEplZmZyZXkgRXJpYzEcMBoGA1UEAxMT
SmVmZnJleSBFcmljIEFsdG1hbjErMCkGCSqGSIb3DQEJARYcamFsdG1hbkBzZWN1cmUtZW5k
cG9pbnRzLmNvbTCCASIwDQYJKoZIhvcNAQEBBQADggEPADCCAQoCggEBAKjPyrF+rdjOUSK/
bWwZHdx5p1+y6iiCd4vvYEVDxouYFp5C/fZEWm5n45ubBUbMSUI1MAZN6ooEoH09UTj6BXhM
S8B987ls81dKOIUphTF2jOzq8gsFmeA15yHMRAD20LqUWeLyvYk8FCNQw+dsKMMhX+WdsxOm
RY/1jPkJL6oN8kEwoUFkOX9/OfWWh6oFnV6faiEHUKDMFubsb9X0KVD8iIeR7Cxz7i4kXqRX
wMlp2fyoxcDIJrBaTY8nA++g3p34IkWt1a5po6g683nIgSnGpwYIwuJheBqSEZfLYWa+1KdD
6Sn27Ud94GqUvPVG5jC6zVC5EJ2aWuoAu+nNuV8CAwEAAaM5MDcwJwYDVR0RBCAwHoEcamFs
dG1hbkBzZWN1cmUtZW5kcG9pbnRzLmNvbTAMBgNVHRMBAf8EAjAAMA0GCSqGSIb3DQEBBAUA
A4GBADtvO//tjiAV6VJGtoNtrl34mB5jGyGTiotzw8riB6zz0GvY11bcWDmp6JKif+pVG+8L
IySDosbuva13qu2HwYUxBmWc7CoNd2k9kRlcrfbDUTTrGOZK8qyqNqT3gQZTAa9ZnUI0su9G
y/n2o5bQcaYdqR3htNrpvdLSPOWhILOXMIIDCjCCAnOgAwIBAgIDDs2tMA0GCSqGSIb3DQEB
BAUAMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3dGUgQ29uc3VsdGluZyAoUHR5KSBM
dGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgSXNzdWluZyBDQTAeFw0w
NTA1MjcxNzQ3NTdaFw0wNjA1MjcxNzQ3NTdaMHMxDzANBgNVBAQTBkFsdG1hbjEVMBMGA1UE
KhMMSmVmZnJleSBFcmljMRwwGgYDVQQDExNKZWZmcmV5IEVyaWMgQWx0bWFuMSswKQYJKoZI
hvcNAQkBFhxqYWx0bWFuQHNlY3VyZS1lbmRwb2ludHMuY29tMIIBIjANBgkqhkiG9w0BAQEF
AAOCAQ8AMIIBCgKCAQEAqM/KsX6t2M5RIr9tbBkd3HmnX7LqKIJ3i+9gRUPGi5gWnkL99kRa
bmfjm5sFRsxJQjUwBk3qigSgfT1ROPoFeExLwH3zuWzzV0o4hSmFMXaM7OryCwWZ4DXnIcxE
APbQupRZ4vK9iTwUI1DD52wowyFf5Z2zE6ZFj/WM+Qkvqg3yQTChQWQ5f3859ZaHqgWdXp9q
IQdQoMwW5uxv1fQpUPyIh5HsLHPuLiRepFfAyWnZ/KjFwMgmsFpNjycD76DenfgiRa3Vrmmj
qDrzeciBKcanBgjC4mF4GpIRl8thZr7Up0PpKfbtR33gapS89UbmMLrNULkQnZpa6gC76c25
XwIDAQABozkwNzAnBgNVHREEIDAegRxqYWx0bWFuQHNlY3VyZS1lbmRwb2ludHMuY29tMAwG
A1UdEwEB/wQCMAAwDQYJKoZIhvcNAQEEBQADgYEAO287/+2OIBXpUka2g22uXfiYHmMbIZOK
i3PDyuIHrPPQa9jXVtxYOanokqJ/6lUb7wsjJIOixu69rXeq7YfBhTEGZZzsKg13aT2RGVyt
9sNRNOsY5kryrKo2pPeBBlMBr1mdQjSy70bL+fajltBxph2pHeG02um90tI85aEgs5cwggM/
MIICqKADAgECAgENMA0GCSqGSIb3DQEBBQUAMIHRMQswCQYDVQQGEwJaQTEVMBMGA1UECBMM
V2VzdGVybiBDYXBlMRIwEAYDVQQHEwlDYXBlIFRvd24xGjAYBgNVBAoTEVRoYXd0ZSBDb25z
dWx0aW5nMSgwJgYDVQQLEx9DZXJ0aWZpY2F0aW9uIFNlcnZpY2VzIERpdmlzaW9uMSQwIgYD
VQQDExtUaGF3dGUgUGVyc29uYWwgRnJlZW1haWwgQ0ExKzApBgkqhkiG9w0BCQEWHHBlcnNv
bmFsLWZyZWVtYWlsQHRoYXd0ZS5jb20wHhcNMDMwNzE3MDAwMDAwWhcNMTMwNzE2MjM1OTU5
WjBiMQswCQYDVQQGEwJaQTElMCMGA1UEChMcVGhhd3RlIENvbnN1bHRpbmcgKFB0eSkgTHRk
LjEsMCoGA1UEAxMjVGhhd3RlIFBlcnNvbmFsIEZyZWVtYWlsIElzc3VpbmcgQ0EwgZ8wDQYJ
KoZIhvcNAQEBBQADgY0AMIGJAoGBAMSmPFVzVftOucqZWh5owHUEcJ3f6f+jHuy9zfVb8hp2
vX8MOmHyv1HOAdTlUAow1wJjWiyJFXCO3cnwK4Vaqj9xVsuvPAsH5/EfkTYkKhPPK9Xzgnc9
A74r/rsYPge/QIACZNenprufZdHFKlSFD0gEf6e20TxhBEAeZBlyYLf7AgMBAAGjgZQwgZEw
EgYDVR0TAQH/BAgwBgEB/wIBADBDBgNVHR8EPDA6MDigNqA0hjJodHRwOi8vY3JsLnRoYXd0
ZS5jb20vVGhhd3RlUGVyc29uYWxGcmVlbWFpbENBLmNybDALBgNVHQ8EBAMCAQYwKQYDVR0R
BCIwIKQeMBwxGjAYBgNVBAMTEVByaXZhdGVMYWJlbDItMTM4MA0GCSqGSIb3DQEBBQUAA4GB
AEiM0VCD6gsuzA2jZqxnD3+vrL7CF6FDlpSdf0whuPg2H6otnzYvwPQcUCCTcDz9reFhYsPZ
Ohl+hLGZGwDFGguCdJ4lUJRix9sncVcljd2pnDmOjCBPZV+V2vf3h9bGCE6u9uo05RAaWzVN
d+NWIXiC3CEZNd4ksdMdRv9dX2VPMYIDOzCCAzcCAQEwaTBiMQswCQYDVQQGEwJaQTElMCMG
A1UEChMcVGhhd3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhhd3RlIFBl
cnNvbmFsIEZyZWVtYWlsIElzc3VpbmcgQ0ECAw7NrTAJBgUrDgMCGgUAoIIBpzAYBgkqhkiG
9w0BCQMxCwYJKoZIhvcNAQcBMBwGCSqGSIb3DQEJBTEPFw0wNjA1MjUyMTEyMTRaMCMGCSqG
SIb3DQEJBDEWBBRo79iwzqpVz74pS2QMSmOIMvJ2azBSBgkqhkiG9w0BCQ8xRTBDMAoGCCqG
SIb3DQMHMA4GCCqGSIb3DQMCAgIAgDANBggqhkiG9w0DAgIBQDAHBgUrDgMCBzANBggqhkiG
9w0DAgIBKDB4BgkrBgEEAYI3EAQxazBpMGIxCzAJBgNVBAYTAlpBMSUwIwYDVQQKExxUaGF3
dGUgQ29uc3VsdGluZyAoUHR5KSBMdGQuMSwwKgYDVQQDEyNUaGF3dGUgUGVyc29uYWwgRnJl
ZW1haWwgSXNzdWluZyBDQQIDDs2tMHoGCyqGSIb3DQEJEAILMWugaTBiMQswCQYDVQQGEwJa
QTElMCMGA1UEChMcVGhhd3RlIENvbnN1bHRpbmcgKFB0eSkgTHRkLjEsMCoGA1UEAxMjVGhh
d3RlIFBlcnNvbmFsIEZyZWVtYWlsIElzc3VpbmcgQ0ECAw7NrTANBgkqhkiG9w0BAQEFAASC
AQCVnuXHLn7ihUpLLvC5qWVqNs2f1Sy06iiFSxUvBqQATROUZECHS/86EGR1Qq4yGdTWqRSf
1np36eR46t7nGqFmnSnnL22dWdor4g++gvmtgE89+Ybz6kDP7fTul0I1Ph11RiLPqqj0+kRF
0ukFtRq8GMPa91wYb40iEvQYp0BKHXDxq1sxj7HqTpZGcb21uu29rAzswZi0hc93Inznj/GI
ypF6wU+CR+IMoxAZ4c6Rltytzy2DqJUhnUTRh3YISuF6icqFZNywrN1nFFcAUKeBsFC0W2wy
/lqxxlIQrXOQ6QDnBy/kjyQd+Mk0tyDRVs9X0++NPClKWl2p2+u582JNAAAAAAAA
--------------ms040302030308020904000906--