From d245350adb5c3c687159409dcecc24fd1e7098d0 Mon Sep 17 00:00:00 2001 Message-Id: From: Mark Wooding Date: Mon, 17 Sep 2012 14:31:08 +0100 Subject: [PATCH] pathmtu/pathmtu.c: Fix search algorithm. Organization: Straylight/Edgeware From: Mark Wooding Turns out I can't write a binary search algorithm. Fiddle with it so that it doesn't get stuck sometimes. Some of the bounds management is a little tricky, so add some documentation and assertions to make sure that everything is as expected. --- pathmtu/pathmtu.c | 26 +++++++++++++++++++++++--- 1 file changed, 23 insertions(+), 3 deletions(-) diff --git a/pathmtu/pathmtu.c b/pathmtu/pathmtu.c index d347b0dd..8dac7b11 100644 --- a/pathmtu/pathmtu.c +++ b/pathmtu/pathmtu.c @@ -32,6 +32,7 @@ #include "config.h" +#include #include #include #include @@ -238,6 +239,8 @@ static int pathmtu(const struct param *pp) * try to hug that initially. */ for (;;) { + assert(lo <= mtu && mtu <= hi); + if (pp->f & F_VERBOSE) moan("probe: %d <= %d <= %d", lo, mtu, hi); rc = probe(&ps, st, mtu); switch (rc) { @@ -295,19 +298,36 @@ static int pathmtu(const struct param *pp) if (pp->f & F_VERBOSE) moan("probe returned: found correct MTU"); goto done; } - if (pp->f & F_VERBOSE) moan("probe returned: guessing higher"); lo = mtu; + + /* Now we must make a new guess, between lo and hi. We know that lo + * is good; but we're not so sure about hi here. We know that hi > + * lo, so this will find an approximate midpoint, greater than lo and + * no more than hi. + */ + if (pp->f & F_VERBOSE) moan("probe returned: guessing higher"); mtu += (hi - lo + 1)/2; break; case RC_LOWER: lower: - if (mtu == lo) { + /* If this didn't work, and we're already at the bottom of our + * possible range, then something has gone horribly wrong. + */ + assert(lo < mtu); + hi = mtu - 1; + if (lo == hi) { if (pp->f & F_VERBOSE) moan("error returned: found correct MTU"); + mtu = lo; goto done; } + + /* We must make a new guess, between lo and hi. We're probably + * fairly sure that lo will succeed, since either it's the minimum + * MTU or we've tested it already; but we're not quite sure about hi, + * so we want to aim high. + */ if (pp->f & F_VERBOSE) moan("error returned: guessing lower"); - hi = mtu - 1; mtu -= (hi - lo + 1)/2; break; -- [mdw]