Merge quagga mainline into the google ISIS code.

The steps were:

  $ git checkout google-is-is
  $ git merge quagga
  $ git checkout google-is-is -- isisd

  # Resolve conflicts in the following:
  lib/md5.h
  zebra/rt_netlink.c
  zebra/zebra_rib.c
  zebra/zserv.c

Note that the content in the isisd directory is left unchanged in the
merge. As a result, changes made to isisd as part of the following
commits on the quagga mainline are dropped.

  # 8ced4e82 is the merge base, e96b3121 is the current quagga master
  $ git log --oneline --reverse 8ced4e82..e96b3121 -- isisd
  5574999 isisd: fix crash on "no router isis" (BZ#536)
  8998075 isisd: raise hello rate for DIS (BZ#539)
  306ca83 isisd: include hash.h, not hash.c
  b82cdeb delete CVS keywords
  2f65867 isisd: indent longopts array
  b511468 quagga: option "-z" ("--socket <path>") added
  05e54ee build: delete .cvsignore files
  b4e45f6 fix zebra protocol after MP-BGP changes
  7fd6cd8 isisd: fix circuit state machine
  907fd95 isisd: send proper LSP after DIS election
  d034aa0 isisd: fix wrong next-hops from SPF
  c25eaff isisd: unexpected kernel routing table (BZ#544)
  e6b03b7 isisd: implement MD5 circuit authentication

1 files changed, 330 insertions, 0 deletions

diff --git a/babeld/resend.c b/babeld/resend.c
new file mode 100644
index 00000000..1cc6290e
--- /dev/null
+++ b/babeld/resend.c
@@ -0,0 +1,330 @@
+/*  
+ *  This file is free software: you may copy, redistribute and/or modify it  
+ *  under the terms of the GNU General Public License as published by the  
+ *  Free Software Foundation, either version 2 of the License, or (at your  
+ *  option) any later version.  
+ *  
+ *  This file is distributed in the hope that it will be useful, but  
+ *  WITHOUT ANY WARRANTY; without even the implied warranty of  
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU  
+ *  General Public License for more details.  
+ *  
+ *  You should have received a copy of the GNU General Public License  
+ *  along with this program.  If not, see <http://www.gnu.org/licenses/>.  
+ *  
+ * This file incorporates work covered by the following copyright and  
+ * permission notice:  
+ *  
+Copyright (c) 2007, 2008 by Juliusz Chroboczek
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+*/
+
+#include <sys/time.h>
+#include <time.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include <zebra.h>
+#include "if.h"
+
+#include "babel_main.h"
+#include "babeld.h"
+#include "util.h"
+#include "neighbour.h"
+#include "resend.h"
+#include "message.h"
+#include "babel_interface.h"
+
+struct timeval resend_time = {0, 0};
+struct resend *to_resend = NULL;
+
+static int
+resend_match(struct resend *resend,
+             int kind, const unsigned char *prefix, unsigned char plen)
+{
+    return (resend->kind == kind &&
+            resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0);
+}
+
+/* This is called by neigh.c when a neighbour is flushed */
+
+void
+flush_resends(struct neighbour *neigh)
+{
+    /* Nothing for now */
+}
+
+static struct resend *
+find_resend(int kind, const unsigned char *prefix, unsigned char plen,
+             struct resend **previous_return)
+{
+    struct resend *current, *previous;
+
+    previous = NULL;
+    current = to_resend;
+    while(current) {
+        if(resend_match(current, kind, prefix, plen)) {
+            if(previous_return)
+                *previous_return = previous;
+            return current;
+        }
+        previous = current;
+        current = current->next;
+    }
+
+    return NULL;
+}
+
+struct resend *
+find_request(const unsigned char *prefix, unsigned char plen,
+             struct resend **previous_return)
+{
+    return find_resend(RESEND_REQUEST, prefix, plen, previous_return);
+}
+
+int
+record_resend(int kind, const unsigned char *prefix, unsigned char plen,
+              unsigned short seqno, const unsigned char *id,
+              struct interface *ifp, int delay)
+{
+    struct resend *resend;
+    unsigned int ifindex = ifp ? ifp->ifindex : 0;
+
+    if((kind == RESEND_REQUEST &&
+        input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) ||
+       (kind == RESEND_UPDATE &&
+        output_filter(NULL, prefix, plen, ifindex) >= INFINITY))
+        return 0;
+
+    if(delay >= 0xFFFF)
+        delay = 0xFFFF;
+
+    resend = find_resend(kind, prefix, plen, NULL);
+    if(resend) {
+        if(resend->delay && delay)
+            resend->delay = MIN(resend->delay, delay);
+        else if(delay)
+            resend->delay = delay;
+        resend->time = babel_now;
+        resend->max = RESEND_MAX;
+        if(id && memcmp(resend->id, id, 8) == 0 &&
+           seqno_compare(resend->seqno, seqno) > 0) {
+            return 0;
+        }
+        if(id)
+            memcpy(resend->id, id, 8);
+        else
+            memset(resend->id, 0, 8);
+        resend->seqno = seqno;
+        if(resend->ifp != ifp)
+            resend->ifp = NULL;
+    } else {
+        resend = malloc(sizeof(struct resend));
+        if(resend == NULL)
+            return -1;
+        resend->kind = kind;
+        resend->max = RESEND_MAX;
+        resend->delay = delay;
+        memcpy(resend->prefix, prefix, 16);
+        resend->plen = plen;
+        resend->seqno = seqno;
+        if(id)
+            memcpy(resend->id, id, 8);
+        else
+            memset(resend->id, 0, 8);
+        resend->ifp = ifp;
+        resend->time = babel_now;
+        resend->next = to_resend;
+        to_resend = resend;
+    }
+
+    if(resend->delay) {
+        struct timeval timeout;
+        timeval_add_msec(&timeout, &resend->time, resend->delay);
+        timeval_min(&resend_time, &timeout);
+    }
+    return 1;
+}
+
+static int
+resend_expired(struct resend *resend)
+{
+    switch(resend->kind) {
+    case RESEND_REQUEST:
+        return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT;
+    default:
+        return resend->max <= 0;
+    }
+}
+
+int
+unsatisfied_request(const unsigned char *prefix, unsigned char plen,
+                    unsigned short seqno, const unsigned char *id)
+{
+    struct resend *request;
+
+    request = find_request(prefix, plen, NULL);
+    if(request == NULL || resend_expired(request))
+        return 0;
+
+    if(memcmp(request->id, id, 8) != 0 ||
+       seqno_compare(request->seqno, seqno) <= 0)
+        return 1;
+
+    return 0;
+}
+
+/* Determine whether a given request should be forwarded. */
+int
+request_redundant(struct interface *ifp,
+                  const unsigned char *prefix, unsigned char plen,
+                  unsigned short seqno, const unsigned char *id)
+{
+    struct resend *request;
+
+    request = find_request(prefix, plen, NULL);
+    if(request == NULL || resend_expired(request))
+        return 0;
+
+    if(memcmp(request->id, id, 8) == 0 &&
+       seqno_compare(request->seqno, seqno) > 0)
+        return 0;
+
+    if(request->ifp != NULL && request->ifp != ifp)
+        return 0;
+
+    if(request->max > 0)
+        /* Will be resent. */
+        return 1;
+
+    if(timeval_minus_msec(&babel_now, &request->time) <
+       (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000))
+        /* Fairly recent. */
+        return 1;
+
+    return 0;
+}
+
+int
+satisfy_request(const unsigned char *prefix, unsigned char plen,
+                unsigned short seqno, const unsigned char *id,
+                struct interface *ifp)
+{
+    struct resend *request, *previous;
+
+    request = find_request(prefix, plen, &previous);
+    if(request == NULL)
+        return 0;
+
+    if(ifp != NULL && request->ifp != ifp)
+        return 0;
+
+    if(memcmp(request->id, id, 8) != 0 ||
+       seqno_compare(request->seqno, seqno) <= 0) {
+        /* We cannot remove the request, as we may be walking the list right
+           now.  Mark it as expired, so that expire_resend will remove it. */
+        request->max = 0;
+        request->time.tv_sec = 0;
+        recompute_resend_time();
+        return 1;
+    }
+
+    return 0;
+}
+
+void
+expire_resend()
+{
+    struct resend *current, *previous;
+    int recompute = 0;
+
+    previous = NULL;
+    current = to_resend;
+    while(current) {
+        if(resend_expired(current)) {
+            if(previous == NULL) {
+                to_resend = current->next;
+                free(current);
+                current = to_resend;
+            } else {
+                previous->next = current->next;
+                free(current);
+                current = previous->next;
+            }
+            recompute = 1;
+        } else {
+            previous = current;
+            current = current->next;
+        }
+    }
+    if(recompute)
+        recompute_resend_time();
+}
+
+void
+recompute_resend_time()
+{
+    struct resend *request;
+    struct timeval resend = {0, 0};
+
+    request = to_resend;
+    while(request) {
+        if(!resend_expired(request) && request->delay > 0 && request->max > 0) {
+            struct timeval timeout;
+            timeval_add_msec(&timeout, &request->time, request->delay);
+            timeval_min(&resend, &timeout);
+        }
+        request = request->next;
+    }
+
+    resend_time = resend;
+}
+
+void
+do_resend()
+{
+    struct resend *resend;
+
+    resend = to_resend;
+    while(resend) {
+        if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) {
+            struct timeval timeout;
+            timeval_add_msec(&timeout, &resend->time, resend->delay);
+            if(timeval_compare(&babel_now, &timeout) >= 0) {
+                switch(resend->kind) {
+                case RESEND_REQUEST:
+                    send_multihop_request(resend->ifp,
+                                          resend->prefix, resend->plen,
+                                          resend->seqno, resend->id, 127);
+                    break;
+                case RESEND_UPDATE:
+                    send_update(resend->ifp, 1,
+                                resend->prefix, resend->plen);
+                    break;
+                default: abort();
+                }
+                resend->delay = MIN(0xFFFF, resend->delay * 2);
+                resend->max--;
+            }
+        }
+        resend = resend->next;
+    }
+    recompute_resend_time();
+}