From 5734509c0545ebd95a5b8e3f22a911c1a39ffa1b Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Sun, 25 Dec 2011 17:52:09 +0100 Subject: babeld: Initial import, for Babel routing protocol. * Initial import of the Babel routing protocol, ported to Quagga. * LICENCE: Update the original LICENCE file to include all known potentially applicable copyright claims. Ask that any future contributors to babeld/ grant MIT/X11 licence to their work. * *.{c,h}: Add GPL headers, in according with the SFLC guidance on dealing with potentially mixed GPL/other licensed work, at: https://www.softwarefreedom.org/resources/2007/gpl-non-gpl-collaboration.html --- babeld/source.c | 159 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 159 insertions(+) create mode 100644 babeld/source.c (limited to 'babeld/source.c') diff --git a/babeld/source.c b/babeld/source.c new file mode 100644 index 00000000..cc4ed445 --- /dev/null +++ b/babeld/source.c @@ -0,0 +1,159 @@ +/* + * 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 . + * + * 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 +#include +#include +#include + +#include "babel_main.h" +#include "babeld.h" +#include "util.h" +#include "source.h" +#include "babel_interface.h" +#include "route.h" + +struct source *srcs = NULL; + +struct source* +find_source(const unsigned char *id, const unsigned char *p, unsigned char plen, + int create, unsigned short seqno) +{ + struct source *src; + + for(src = srcs; src; src = src->next) { + /* This should really be a hash table. For now, check the + last byte first. */ + if(src->id[7] != id[7]) + continue; + if(memcmp(src->id, id, 8) != 0) + continue; + if(source_match(src, p, plen)) + return src; + } + + if(!create) + return NULL; + + src = malloc(sizeof(struct source)); + if(src == NULL) { + zlog_err("malloc(source): %s", safe_strerror(errno)); + return NULL; + } + + memcpy(src->id, id, 8); + memcpy(src->prefix, p, 16); + src->plen = plen; + src->seqno = seqno; + src->metric = INFINITY; + src->time = babel_now.tv_sec; + src->next = srcs; + srcs = src; + return src; +} + +int +flush_source(struct source *src) +{ + /* This is absolutely horrible -- it makes expire_sources quadratic. + But it's not called very often. */ + + if (babel_route_get_by_source(src) != NULL) + return 0; + + if(srcs == src) { + srcs = src->next; + } else { + struct source *previous = srcs; + while(previous->next != src) + previous = previous->next; + previous->next = src->next; + } + + free(src); + return 1; +} + +int +source_match(struct source *src, + const unsigned char *p, unsigned char plen) +{ + if(src->plen != plen) + return 0; + if(src->prefix[15] != p[15]) + return 0; + if(memcmp(src->prefix, p, 16) != 0) + return 0; + return 1; +} + +void +update_source(struct source *src, + unsigned short seqno, unsigned short metric) +{ + if(metric >= INFINITY) + return; + + if(src->time < babel_now.tv_sec - SOURCE_GC_TIME || + seqno_compare(src->seqno, seqno) < 0 || + (src->seqno == seqno && src->metric > metric)) { + src->seqno = seqno; + src->metric = metric; + } + src->time = babel_now.tv_sec; +} + +void +expire_sources() +{ + struct source *src; + + src = srcs; + while(src) { + if(src->time > babel_now.tv_sec) + /* clock stepped */ + src->time = babel_now.tv_sec; + if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) { + struct source *old = src; + src = src->next; + flush_source(old); + continue; + } + src = src->next; + } +} -- cgit v1.2.1 From c35fafdf887aa32c5be6ad738d3a3b0140cea6e8 Mon Sep 17 00:00:00 2001 From: Matthieu Boutier Date: Mon, 23 Jan 2012 23:46:32 +0100 Subject: babeld: babelz merge. Babelz is the last version of the stand-alone babel daemon. In particular, it use multiple channels to diminuate interferences. Please refer to this one for more details. --- babeld/source.c | 59 ++++++++++++++++++++++++++++++++++++++------------------- 1 file changed, 40 insertions(+), 19 deletions(-) (limited to 'babeld/source.c') diff --git a/babeld/source.c b/babeld/source.c index cc4ed445..772112d4 100644 --- a/babeld/source.c +++ b/babeld/source.c @@ -63,8 +63,10 @@ find_source(const unsigned char *id, const unsigned char *p, unsigned char plen, continue; if(memcmp(src->id, id, 8) != 0) continue; - if(source_match(src, p, plen)) - return src; + if(src->plen != plen) + continue; + if(memcmp(src->prefix, p, 16) == 0) + return src; } if(!create) @@ -82,18 +84,32 @@ find_source(const unsigned char *id, const unsigned char *p, unsigned char plen, src->seqno = seqno; src->metric = INFINITY; src->time = babel_now.tv_sec; + src->route_count = 0; src->next = srcs; srcs = src; return src; } +struct source * +retain_source(struct source *src) +{ + assert(src->route_count < 0xffff); + src->route_count++; + return src; +} + +void +release_source(struct source *src) +{ + assert(src->route_count > 0); + src->route_count--; +} + int flush_source(struct source *src) { - /* This is absolutely horrible -- it makes expire_sources quadratic. - But it's not called very often. */ - - if (babel_route_get_by_source(src) != NULL) + if(src->route_count > 0) + /* The source is in use by a route. */ return 0; if(srcs == src) { @@ -109,19 +125,6 @@ flush_source(struct source *src) return 1; } -int -source_match(struct source *src, - const unsigned char *p, unsigned char plen) -{ - if(src->plen != plen) - return 0; - if(src->prefix[15] != p[15]) - return 0; - if(memcmp(src->prefix, p, 16) != 0) - return 0; - return 1; -} - void update_source(struct source *src, unsigned short seqno, unsigned short metric) @@ -129,6 +132,10 @@ update_source(struct source *src, if(metric >= INFINITY) return; + /* If a source is expired, pretend that it doesn't exist and update + it unconditionally. This makes ensures that old data will + eventually be overridden, and prevents us from getting stuck if + a router loses its sequence number. */ if(src->time < babel_now.tv_sec - SOURCE_GC_TIME || seqno_compare(src->seqno, seqno) < 0 || (src->seqno == seqno && src->metric > metric)) { @@ -157,3 +164,17 @@ expire_sources() src = src->next; } } + +void +check_sources_released(void) +{ + struct source *src; + + for(src = srcs; src; src = src->next) { + if(src->route_count != 0) + fprintf(stderr, "Warning: source %s %s has refcount %d.\n", + format_eui64(src->id), + format_prefix(src->prefix, src->plen), + (int)src->route_count); + } +} -- cgit v1.2.1