potential bug in David Brownell's zcip code

--Boundary-00=_tOYyBLuh63sjBg3
Content-Type: multipart/signed;
  boundary="nextPart6137151.QDFUCVXP1Q";
  protocol="application/pgp-signature";
  micalg=pgp-sha1
Content-Transfer-Encoding: 7bit

--nextPart6137151.QDFUCVXP1Q
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline

Hi,

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

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 +=3D (timeout % 1000) * 1000;
		if (tv1.tv_usec > 1000000) {
			tv1.tv_usec -=3D 1000000;
			tv1.tv_sec++;
		}
		tv1.tv_sec +=3D timeout / 1000;
	} else if (timeout =3D=3D 0) {
		timeout =3D ms_rdelay(PROBE_WAIT);

'tv1' seems to be the timeout for the subsequent call to 'poll()' as=20
"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 =3D -1;
			} else {
				timersub(&tv1, &tv2, &tv1);
				timeout =3D 1000 * tv1.tv_sec
						+ tv1.tv_usec / 1000;
			}
		}

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

There are two problems with this:

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

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


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


I have fixed the problem by replacing 'poll()' with 'select()' and by=20
simplifying the timeout recalculation (which is an obvious consequence of=20
using 'select()'. 'select()' returns with the timeout parameter containing=
=20
the remaining timeout value when it is woken up by a packet before the=20
timeout has elapsed. This value can directly be used for re-invoking=20
'select()'. Please note that this behavior is only implemented in Linux, bu=
t=20
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=20
zeroconf-workers from 26/10/04, is attached.


Any comments???


Michael


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

--nextPart6137151.QDFUCVXP1Q
Content-Type: application/pgp-signature

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.5 (GNU/Linux)

iD8DBQBByYOtQxcxBvLsRaoRAg7uAJ9EAYeO/snEatrCDawe/51/gfhjBwCg23M8
jr3DTFjBR+R9YkY4iIrxcNQ=
=705B
-----END PGP SIGNATURE-----

--nextPart6137151.QDFUCVXP1Q--

--Boundary-00=_tOYyBLuh63sjBg3
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=_tOYyBLuh63sjBg3--


-------------------------------------------------------
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/