potential bug in David Brownell's zcip code

--Boundary-00=_qxVyBhPIbZesI/R
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Hi,

Now that I'm seeing a bit clearer about the legal status of David Brownell's 
zcip code, I'd like to discuss a potential but I have discovered recently. 
The bug is about time measurement and time/timeout calculation and 
recalculation around the call to 'poll()'. 

But first, let me explain how I understand certain parts of the code:

1. meaning of 'tv1':

	if (timeout > 0) {
		gettimeofday(&tv1, NULL);
		tv1.tv_usec += (timeout % 1000) * 1000;
		if (tv1.tv_usec > 1000000) {
			tv1.tv_usec -= 1000000;
			tv1.tv_sec++;
		}
		tv1.tv_sec += timeout / 1000;
	} else if (timeout == 0) {
		timeout = ms_rdelay(PROBE_WAIT);

'tv1' seems to be the timeout for the subsequent call to 'poll()' as 
"absolute" time value for finite, non-zero timeouts.


2. interpretation of 'poll()' return codes:

	switch (poll(fds, 1, timeout)) {

	// timeouts trigger protocol transitions
	case 0:
	.
	.		/* this is the 'timeout' branch */
	.
	break;

	// packets arriving
	case 1:
	.
	.		/* this is the 'packet has arrived' branch */
	.
	break;

	default:
	.
	.		/* this is the 'error' branch */
	.


3. recalculation of timeout in 'packet has arrived' branch:

		// maybe adjust timeout
		if (timeout > 0) {
			struct timeval tv2;

			gettimeofday(&tv2, NULL);
			if (timercmp(&tv1, &tv2, <)) {
				timeout = -1;
			} else {
				timersub(&tv1, &tv2, &tv1);
				timeout = 1000 * tv1.tv_sec
						+ tv1.tv_usec / 1000;
			}
		}

'tv2' is the time when the protocol has returned from 'poll()'. Apparently, 
the code calculates the time difference between the expected, absolute expiry 
time ('tv1') and the current time ('tv2'). If the current time is greater, 
the code seems to assume that the timeout has elapsed. In this case, the code 
also assumes that the protocol negotiation phase (PROBE/ANNOUNCE) is over, 
and it may go into an infinte wait state where it would only defend the 
successfully acquired IP address if necessary. 

There are two problems with this:

a)
When the code is in the 'packet has arrived' branch, the timeout cannot have 
elapsed by definition of 'poll()'. Exceeding of the timeout leads into 
the 'timeout' branch.

b)
This code may erroneously assume that the timeout has elapsed, if an 
unexpected ARP packet arrives within the regular, finite timeout (still in 
the protocol negotiation phase), and the OS preempts the zcip code between 
the return of 'poll()' and the timeout recalculation above. When the code is 
reactivated by the scheduler, the timeout may indeed have elapsed, and 
'timercmp(&tv1, &tv2, <)' will hold true. In this case, the code will 
erroneously assume that the protocol negotiation phase is finished, and will 
set the subsequent timeout to -1 (infinite). zcip will seem to hang.


I can reproduce this problem here more or less consistently by executing zcip 
on more than one node concurrently, so that "unexpected" ARP request packets 
are received within the protocol negotiation phase.


I have fixed the problem by replacing 'poll()' with 'select()' and by 
simplifying the timeout recalculation (which is an obvious consequence of 
using 'select()'. 'select()# returns with the timeout parameter containing 
the remaining timeout value when it is woken up by a packet before the 
timeout has elapsed. This value can directly be used for re-invoking 
'select()'. Please note that this behavior is only implemented in Linux, but 
not in other Unices, so that my patch is not compatible with other Unices.

My patch, which applies to David Brownell's initial code posting on 
zeroconf-workers from 26/10/04, is attached.


Any comments???


Michael


-- 
============================================
Michael Schmidt
--------------------------------------------
Institute for Digital Communications Systems
University of Siegen, Germany
--------------------------------------------
http:   www.dcs.uni-siegen.de
e-mail: [email protected]
============================================

--Boundary-00=_qxVyBhPIbZesI/R
Content-Type: text/x-diff;
  charset="us-ascii";
  name="zcip.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="zcip.patch"

--- zcip.c.orig	2004-12-20 17:09:12.000000000 +0100
+++ zcip.c	2004-12-22 10:29:02.717064544 +0100
@@ -369,28 +369,28 @@
 	//  - use it
 	//  - defend it, within limits
 	while (1) {
-		struct pollfd fds[1];
-		struct timeval tv1;
+		fd_set rfds, efds;
+		struct timeval to, *pto;
 
-		fds[0].fd = fd;
-		fds[0].events = POLLIN | POLLERR;
-		fds[0].revents = 0;
+		FD_ZERO(&rfds);
+		FD_SET(fd, &rfds);
+		FD_ZERO(&efds);
+		FD_SET(fd, &efds);
 
 		// poll, being ready to adjust current timeout 
-		if (timeout > 0) {
-			gettimeofday(&tv1, NULL);
-			tv1.tv_usec += (timeout % 1000) * 1000;
-			if (tv1.tv_usec > 1000000) {
-				tv1.tv_usec -= 1000000;
-				tv1.tv_sec++;
-			}
-			tv1.tv_sec += timeout / 1000;
-		} else if (timeout == 0) {
+		if (timeout == 0) {
 			timeout = ms_rdelay(PROBE_WAIT);
 		}
 		VDBG("...wait %ld %s nprobes=%d, nclaims=%d\n",
 				timeout, intf, nprobes, nclaims);
-		switch (poll(fds, 1, timeout)) {
+		if (timeout == -1)
+			pto = NULL;
+		else {
+			to.tv_sec = timeout / 1000;
+			to.tv_usec = (timeout % 1000) * 1000;
+			pto = &to;
+		}
+		switch (select(fd + 1, &rfds, NULL, &efds, pto)) {
 
 		// timeouts trigger protocol transitions
 		case 0:
@@ -437,19 +437,10 @@
 		case 1:
 			// maybe adjust timeout
 			if (timeout > 0) {
-				struct timeval tv2;
-
-				gettimeofday(&tv2, NULL);
-				if (timercmp(&tv1, &tv2, <)) {
-					timeout = -1;
-				} else {
-					timersub(&tv1, &tv2, &tv1);
-					timeout = 1000 * tv1.tv_sec
-							+ tv1.tv_usec / 1000;
-				}
+				timeout = to.tv_sec * 1000 + to.tv_usec / 1000;
 			}
-			if ((fds[0].revents & POLLIN) == 0) {
-				if (fds[0].revents & POLLERR) {
+			if (FD_ISSET(fd, &rfds) == 0) {
+				if (FD_ISSET(fd, &efds) != 0) {
 					// FIXME: links routinely go down;
 					// this shouldn't necessarily exit.
 					fprintf(stderr, "%s %s: poll error\n",

--Boundary-00=_qxVyBhPIbZesI/R--


-------------------------------------------------------
SF email is sponsored by - The IT Product Guide
Read honest & candid reviews on hundreds of IT Products from real users.
Discover which products truly live up to the hype. Start reading now. 
http://productguide.itmanagersjournal.com/