1/* 2 * This file is free software: you may copy, redistribute and/or modify it 3 * under the terms of the GNU General Public License as published by the 4 * Free Software Foundation, either version 2 of the License, or (at your 5 * option) any later version. 6 * 7 * This file is distributed in the hope that it will be useful, but 8 * WITHOUT ANY WARRANTY; without even the implied warranty of 9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 10 * General Public License for more details. 11 * 12 * You should have received a copy of the GNU General Public License 13 * along with this program. If not, see <http://www.gnu.org/licenses/>. 14 * 15 * This file incorporates work covered by the following copyright and 16 * permission notice: 17 * 18Copyright (c) 2007, 2008 by Juliusz Chroboczek 19 20Permission is hereby granted, free of charge, to any person obtaining a copy 21of this software and associated documentation files (the "Software"), to deal 22in the Software without restriction, including without limitation the rights 23to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 24copies of the Software, and to permit persons to whom the Software is 25furnished to do so, subject to the following conditions: 26 27The above copyright notice and this permission notice shall be included in 28all copies or substantial portions of the Software. 29 30THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 31IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 32FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 33AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 34LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 35OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 36THE SOFTWARE. 37*/ 38 39#include <sys/time.h> 40#include <time.h> 41#include <string.h> 42#include <stdlib.h> 43 44#include <zebra.h> 45#include "if.h" 46 47#include "babel_main.h" 48#include "babeld.h" 49#include "util.h" 50#include "neighbour.h" 51#include "resend.h" 52#include "message.h" 53#include "babel_interface.h" 54 55struct timeval resend_time = {0, 0}; 56struct resend *to_resend = NULL; 57 58static int 59resend_match(struct resend *resend, 60 int kind, const unsigned char *prefix, unsigned char plen) 61{ 62 return (resend->kind == kind && 63 resend->plen == plen && memcmp(resend->prefix, prefix, 16) == 0); 64} 65 66/* This is called by neigh.c when a neighbour is flushed */ 67 68void 69flush_resends(struct neighbour *neigh) 70{ 71 /* Nothing for now */ 72} 73 74static struct resend * 75find_resend(int kind, const unsigned char *prefix, unsigned char plen, 76 struct resend **previous_return) 77{ 78 struct resend *current, *previous; 79 80 previous = NULL; 81 current = to_resend; 82 while(current) { 83 if(resend_match(current, kind, prefix, plen)) { 84 if(previous_return) 85 *previous_return = previous; 86 return current; 87 } 88 previous = current; 89 current = current->next; 90 } 91 92 return NULL; 93} 94 95struct resend * 96find_request(const unsigned char *prefix, unsigned char plen, 97 struct resend **previous_return) 98{ 99 return find_resend(RESEND_REQUEST, prefix, plen, previous_return); 100} 101 102int 103record_resend(int kind, const unsigned char *prefix, unsigned char plen, 104 unsigned short seqno, const unsigned char *id, 105 struct interface *ifp, int delay) 106{ 107 struct resend *resend; 108 unsigned int ifindex = ifp ? ifp->ifindex : 0; 109 110 if((kind == RESEND_REQUEST && 111 input_filter(NULL, prefix, plen, NULL, ifindex) >= INFINITY) || 112 (kind == RESEND_UPDATE && 113 output_filter(NULL, prefix, plen, ifindex) >= INFINITY)) 114 return 0; 115 116 if(delay >= 0xFFFF) 117 delay = 0xFFFF; 118 119 resend = find_resend(kind, prefix, plen, NULL); 120 if(resend) { 121 if(resend->delay && delay) 122 resend->delay = MIN(resend->delay, delay); 123 else if(delay) 124 resend->delay = delay; 125 resend->time = babel_now; 126 resend->max = RESEND_MAX; 127 if(id && memcmp(resend->id, id, 8) == 0 && 128 seqno_compare(resend->seqno, seqno) > 0) { 129 return 0; 130 } 131 if(id) 132 memcpy(resend->id, id, 8); 133 else 134 memset(resend->id, 0, 8); 135 resend->seqno = seqno; 136 if(resend->ifp != ifp) 137 resend->ifp = NULL; 138 } else { 139 resend = malloc(sizeof(struct resend)); 140 if(resend == NULL) 141 return -1; 142 resend->kind = kind; 143 resend->max = RESEND_MAX; 144 resend->delay = delay; 145 memcpy(resend->prefix, prefix, 16); 146 resend->plen = plen; 147 resend->seqno = seqno; 148 if(id) 149 memcpy(resend->id, id, 8); 150 else 151 memset(resend->id, 0, 8); 152 resend->ifp = ifp; 153 resend->time = babel_now; 154 resend->next = to_resend; 155 to_resend = resend; 156 } 157 158 if(resend->delay) { 159 struct timeval timeout; 160 timeval_add_msec(&timeout, &resend->time, resend->delay); 161 timeval_min(&resend_time, &timeout); 162 } 163 return 1; 164} 165 166static int 167resend_expired(struct resend *resend) 168{ 169 switch(resend->kind) { 170 case RESEND_REQUEST: 171 return timeval_minus_msec(&babel_now, &resend->time) >= REQUEST_TIMEOUT; 172 default: 173 return resend->max <= 0; 174 } 175} 176 177int 178unsatisfied_request(const unsigned char *prefix, unsigned char plen, 179 unsigned short seqno, const unsigned char *id) 180{ 181 struct resend *request; 182 183 request = find_request(prefix, plen, NULL); 184 if(request == NULL || resend_expired(request)) 185 return 0; 186 187 if(memcmp(request->id, id, 8) != 0 || 188 seqno_compare(request->seqno, seqno) <= 0) 189 return 1; 190 191 return 0; 192} 193 194/* Determine whether a given request should be forwarded. */ 195int 196request_redundant(struct interface *ifp, 197 const unsigned char *prefix, unsigned char plen, 198 unsigned short seqno, const unsigned char *id) 199{ 200 struct resend *request; 201 202 request = find_request(prefix, plen, NULL); 203 if(request == NULL || resend_expired(request)) 204 return 0; 205 206 if(memcmp(request->id, id, 8) == 0 && 207 seqno_compare(request->seqno, seqno) > 0) 208 return 0; 209 210 if(request->ifp != NULL && request->ifp != ifp) 211 return 0; 212 213 if(request->max > 0) 214 /* Will be resent. */ 215 return 1; 216 217 if(timeval_minus_msec(&babel_now, &request->time) < 218 (ifp ? MIN(babel_get_if_nfo(ifp)->hello_interval, 1000) : 1000)) 219 /* Fairly recent. */ 220 return 1; 221 222 return 0; 223} 224 225int 226satisfy_request(const unsigned char *prefix, unsigned char plen, 227 unsigned short seqno, const unsigned char *id, 228 struct interface *ifp) 229{ 230 struct resend *request, *previous; 231 232 request = find_request(prefix, plen, &previous); 233 if(request == NULL) 234 return 0; 235 236 if(ifp != NULL && request->ifp != ifp) 237 return 0; 238 239 if(memcmp(request->id, id, 8) != 0 || 240 seqno_compare(request->seqno, seqno) <= 0) { 241 /* We cannot remove the request, as we may be walking the list right 242 now. Mark it as expired, so that expire_resend will remove it. */ 243 request->max = 0; 244 request->time.tv_sec = 0; 245 recompute_resend_time(); 246 return 1; 247 } 248 249 return 0; 250} 251 252void 253expire_resend() 254{ 255 struct resend *current, *previous; 256 int recompute = 0; 257 258 previous = NULL; 259 current = to_resend; 260 while(current) { 261 if(resend_expired(current)) { 262 if(previous == NULL) { 263 to_resend = current->next; 264 free(current); 265 current = to_resend; 266 } else { 267 previous->next = current->next; 268 free(current); 269 current = previous->next; 270 } 271 recompute = 1; 272 } else { 273 previous = current; 274 current = current->next; 275 } 276 } 277 if(recompute) 278 recompute_resend_time(); 279} 280 281void 282recompute_resend_time() 283{ 284 struct resend *request; 285 struct timeval resend = {0, 0}; 286 287 request = to_resend; 288 while(request) { 289 if(!resend_expired(request) && request->delay > 0 && request->max > 0) { 290 struct timeval timeout; 291 timeval_add_msec(&timeout, &request->time, request->delay); 292 timeval_min(&resend, &timeout); 293 } 294 request = request->next; 295 } 296 297 resend_time = resend; 298} 299 300void 301do_resend() 302{ 303 struct resend *resend; 304 305 resend = to_resend; 306 while(resend) { 307 if(!resend_expired(resend) && resend->delay > 0 && resend->max > 0) { 308 struct timeval timeout; 309 timeval_add_msec(&timeout, &resend->time, resend->delay); 310 if(timeval_compare(&babel_now, &timeout) >= 0) { 311 switch(resend->kind) { 312 case RESEND_REQUEST: 313 send_multihop_request(resend->ifp, 314 resend->prefix, resend->plen, 315 resend->seqno, resend->id, 127); 316 break; 317 case RESEND_UPDATE: 318 send_update(resend->ifp, 1, 319 resend->prefix, resend->plen); 320 break; 321 default: abort(); 322 } 323 resend->delay = MIN(0xFFFF, resend->delay * 2); 324 resend->max--; 325 } 326 } 327 resend = resend->next; 328 } 329 recompute_resend_time(); 330} 331