proto/ospf/lsupd.c

   1 /*
   2  *      BIRD -- OSPF
   3  *
   4  *      (c) 2000--2004 Ondrej Filip <feela@network.cz>
   5  *      (c) 2009--2014 Ondrej Zajicek <santiago@crfreenet.org>
   6  *      (c) 2009--2014 CZ.NIC z.s.p.o.
   7  *
   8  *      Can be freely distributed and used under the terms of the GNU GPL.
   9  */
  10
  11 #include "ospf.h"
  12
  13
  14 /*
  15 struct ospf_lsupd_packet
  16 {
  17   struct ospf_packet hdr;
  18   // union ospf_auth auth;
  19
  20   u32 lsa_count;
  21   void lsas[];
  22 };
  23 */
  24
  25
  26 void
  27 ospf_dump_lsahdr(struct ospf_proto *p, struct ospf_lsa_header *lsa_n)
  28 {
  29   struct ospf_lsa_header lsa;
  30   u32 lsa_etype;
  31
  32   lsa_ntoh_hdr(lsa_n, &lsa);
  33   lsa_etype = lsa_get_etype(&lsa, p);
  34
  35   log(L_TRACE "%s:     LSA      Type: %04x, Id: %R, Rt: %R, Age: %u, Seq: %08x, Sum: %04x",
  36       p->p.name, lsa_etype, lsa.id, lsa.rt, lsa.age, lsa.sn, lsa.checksum);
  37 }
  38
  39 void
  40 ospf_dump_common(struct ospf_proto *p, struct ospf_packet *pkt)
  41 {
  42   log(L_TRACE "%s:     length   %d", p->p.name, ntohs(pkt->length));
  43   log(L_TRACE "%s:     router   %R", p->p.name, ntohl(pkt->routerid));
  44 }
  45
  46 static inline uint
  47 ospf_lsupd_hdrlen(struct ospf_proto *p)
  48 {
  49   return ospf_pkt_hdrlen(p) + 4; /* + u32 lsa count field */
  50 }
  51
  52 static inline u32
  53 ospf_lsupd_get_lsa_count(struct ospf_packet *pkt, uint hdrlen)
  54 {
  55   u32 *c = ((void *) pkt) + hdrlen - 4;
  56   return ntohl(*c);
  57 }
  58
  59 static inline void
  60 ospf_lsupd_set_lsa_count(struct ospf_packet *pkt, uint hdrlen, u32 val)
  61 {
  62   u32 *c = ((void *) pkt) + hdrlen - 4;
  63   *c = htonl(val);
  64 }
  65
  66 static inline void
  67 ospf_lsupd_body(struct ospf_proto *p, struct ospf_packet *pkt,
  68                 uint *offset, uint *bound, uint *lsa_count)
  69 {
  70   uint hlen = ospf_lsupd_hdrlen(p);
  71   *offset = hlen;
  72   *bound = ntohs(pkt->length) - sizeof(struct ospf_lsa_header);
  73   *lsa_count = ospf_lsupd_get_lsa_count(pkt, hlen);
  74 }
  75
  76 static void
  77 ospf_dump_lsupd(struct ospf_proto *p, struct ospf_packet *pkt)
  78 {
  79   uint offset, bound, i, lsa_count, lsalen;
  80
  81   ASSERT(pkt->type == LSUPD_P);
  82   ospf_dump_common(p, pkt);
  83
  84   ospf_lsupd_body(p, pkt, &offset, &bound, &lsa_count);
  85   for (i = 0; i < lsa_count; i++)
  86   {
  87     if (offset > bound)
  88     {
  89       log(L_TRACE "%s:     LSA      invalid", p->p.name);
  90       return;
  91     }
  92
  93     struct ospf_lsa_header *lsa = ((void *) pkt) + offset;
  94     ospf_dump_lsahdr(p, lsa);
  95     lsalen = ntohs(lsa->length);
  96     offset += lsalen;
  97
  98     if (((lsalen % 4) != 0) || (lsalen <= sizeof(struct ospf_lsa_header)))
  99     {
 100       log(L_TRACE "%s:     LSA      invalid", p->p.name);
 101       return;
 102     }
 103   }
 104 }
 105
 106
 107 static inline void
 108 ospf_lsa_lsrt_up(struct top_hash_entry *en, struct ospf_neighbor *n)
 109 {
 110   struct top_hash_entry *ret = ospf_hash_get_entry(n->lsrth, en);
 111
 112   if (!SNODE_VALID(ret))
 113   {
 114     en->ret_count++;
 115     s_add_tail(&n->lsrtl, SNODE ret);
 116   }
 117
 118   memcpy(&ret->lsa, &en->lsa, sizeof(struct ospf_lsa_header));
 119 }
 120
 121 static inline int
 122 ospf_lsa_lsrt_down(struct top_hash_entry *en, struct ospf_neighbor *n)
 123 {
 124   struct top_hash_entry *ret = ospf_hash_find_entry(n->lsrth, en);
 125
 126   if (ret)
 127   {
 128     en->ret_count--;
 129     s_rem_node(SNODE ret);
 130     ospf_hash_delete(n->lsrth, ret);
 131     return 1;
 132   }
 133
 134   return 0;
 135 }
 136
 137
 138 static void ospf_lsupd_flood_ifa(struct ospf_proto *p, struct ospf_iface *ifa, struct top_hash_entry *en);
 139
 140
 141 /**
 142  * ospf_lsupd_flood - send received or generated LSA to the neighbors
 143  * @p: OSPF protocol
 144  * @en: LSA entry
 145  * @from: neighbor than sent this LSA (or NULL if LSA is local)
 146  *
 147  * return value - was the LSA flooded back?
 148  */
 149
 150 int
 151 ospf_lsupd_flood(struct ospf_proto *p, struct top_hash_entry *en, struct ospf_neighbor *from)
 152 {
 153   struct ospf_iface *ifa;
 154   struct ospf_neighbor *n;
 155
 156   int back = 0;
 157   WALK_LIST(ifa, p->iface_list)
 158   {
 159     if (ifa->stub)
 160       continue;
 161
 162     if (! lsa_flooding_allowed(en->lsa_type, en->domain, ifa))
 163       continue;
 164
 165     DBG("Wanted to flood LSA: Type: %u, ID: %R, RT: %R, SN: 0x%x, Age %u\n",
 166         hh->type, hh->id, hh->rt, hh->sn, hh->age);
 167
 168     int used = 0;
 169     WALK_LIST(n, ifa->neigh_list)
 170     {
 171       /* 13.3 (1a) */
 172       if (n->state < NEIGHBOR_EXCHANGE)
 173         continue;
 174
 175       /* 13.3 (1b) */
 176       if (n->state < NEIGHBOR_FULL)
 177       {
 178         struct top_hash_entry *req = ospf_hash_find_entry(n->lsrqh, en);
 179         if (req != NULL)
 180         {
 181           int cmp = lsa_comp(&en->lsa, &req->lsa);
 182
 183           /* If same or newer, remove LSA from the link state request list */
 184           if (cmp > CMP_OLDER)
 185           {
 186             s_rem_node(SNODE req);
 187             ospf_hash_delete(n->lsrqh, req);
 188             if ((EMPTY_SLIST(n->lsrql)) && (n->state == NEIGHBOR_LOADING))
 189               ospf_neigh_sm(n, INM_LOADDONE);
 190           }
 191
 192           /* If older or same, skip processing of this neighbor */
 193           if (cmp < CMP_NEWER)
 194             continue;
 195         }
 196       }
 197
 198       /* 13.3 (1c) */
 199       if (n == from)
 200         continue;
 201
 202       /* In OSPFv3, there should be check whether receiving router understand
 203          that type of LSA (for LSA types with U-bit == 0). But as we do not support
 204          any optional LSA types, this is not needed yet */
 205
 206       /* 13.3 (1d) - add LSA to the link state retransmission list */
 207       ospf_lsa_lsrt_up(en, n);
 208
 209       used = 1;
 210     }
 211
 212     /* 13.3 (2) */
 213     if (!used)
 214       continue;
 215
 216     if (from && (from->ifa == ifa))
 217     {
 218       /* 13.3 (3) */
 219       if ((from->rid == ifa->drid) || (from->rid == ifa->bdrid))
 220         continue;
 221
 222       /* 13.3 (4) */
 223       if (ifa->state == OSPF_IS_BACKUP)
 224         continue;
 225
 226       back = 1;
 227     }
 228
 229     /* 13.3 (5) - finally flood the packet */
 230     ospf_lsupd_flood_ifa(p, ifa, en);
 231   }
 232
 233   return back;
 234 }
 235
 236 static uint
 237 ospf_prepare_lsupd(struct ospf_proto *p, struct ospf_iface *ifa,
 238                    struct top_hash_entry **lsa_list, uint lsa_count)
 239 {
 240   struct ospf_packet *pkt;
 241   uint hlen, pos, i, maxsize;
 242
 243   pkt = ospf_tx_buffer(ifa);
 244   hlen = ospf_lsupd_hdrlen(p);
 245   maxsize = ospf_pkt_maxsize(ifa);
 246
 247   ospf_pkt_fill_hdr(ifa, pkt, LSUPD_P);
 248   pos = hlen;
 249
 250   for (i = 0; i < lsa_count; i++)
 251   {
 252     struct top_hash_entry *en = lsa_list[i];
 253     uint len = en->lsa.length;
 254
 255     if ((pos + len) > maxsize)
 256     {
 257       /* The packet if full, stop adding LSAs and sent it */
 258       if (i > 0)
 259         break;
 260
 261       /* LSA is larger than MTU, check buffer size */
 262       if (ospf_iface_assure_bufsize(ifa, pos + len) < 0)
 263       {
 264         /* Cannot fit in a tx buffer, skip that */
 265         log(L_ERR "%s: LSA too large to send on %s (Type: %04x, Id: %R, Rt: %R)",
 266             p->p.name, ifa->ifname, en->lsa_type, en->lsa.id, en->lsa.rt);
 267         break;
 268       }
 269
 270       /* TX buffer could be reallocated */
 271       pkt = ospf_tx_buffer(ifa);
 272     }
 273
 274     struct ospf_lsa_header *buf = ((void *) pkt) + pos;
 275     lsa_hton_hdr(&en->lsa, buf);
 276     lsa_hton_body(en->lsa_body, ((void *) buf) + sizeof(struct ospf_lsa_header),
 277                   len - sizeof(struct ospf_lsa_header));
 278     buf->age = htons(MIN(en->lsa.age + ifa->inftransdelay, LSA_MAXAGE));
 279
 280     pos += len;
 281   }
 282
 283   ospf_lsupd_set_lsa_count(pkt, hlen, i);
 284   pkt->length = htons(pos);
 285
 286   return i;
 287 }
 288
 289
 290 static void
 291 ospf_lsupd_flood_ifa(struct ospf_proto *p, struct ospf_iface *ifa, struct top_hash_entry *en)
 292 {
 293   uint c = ospf_prepare_lsupd(p, ifa, &en, 1);
 294
 295   if (!c)       /* Too large LSA */
 296     return;
 297
 298   OSPF_PACKET(ospf_dump_lsupd, ospf_tx_buffer(ifa),
 299               "LSUPD packet flooded via %s", ifa->ifname);
 300
 301   if (ifa->type == OSPF_IT_BCAST)
 302   {
 303     if ((ifa->state == OSPF_IS_DR) || (ifa->state == OSPF_IS_BACKUP))
 304       ospf_send_to_all(ifa);
 305     else
 306       ospf_send_to_des(ifa);
 307   }
 308   else
 309     ospf_send_to_agt(ifa, NEIGHBOR_EXCHANGE);
 310 }
 311
 312 int
 313 ospf_send_lsupd(struct ospf_proto *p, struct top_hash_entry **lsa_list, uint lsa_count, struct ospf_neighbor *n)
 314 {
 315   struct ospf_iface *ifa = n->ifa;
 316   uint i, c;
 317
 318   for (i = 0; i < lsa_count; i += c)
 319   {
 320     c = ospf_prepare_lsupd(p, ifa, lsa_list + i, lsa_count - i);
 321
 322     if (!c)     /* Too large LSA */
 323       { i++; continue; }
 324
 325     OSPF_PACKET(ospf_dump_lsupd, ospf_tx_buffer(ifa),
 326                 "LSUPD packet sent to %I via %s", n->ip, ifa->ifname);
 327
 328     ospf_send_to(ifa, n->ip);
 329   }
 330
 331   return lsa_count;
 332 }
 333
 334 void
 335 ospf_rxmt_lsupd(struct ospf_proto *p, struct ospf_neighbor *n)
 336 {
 337   const uint max = 128;
 338   struct top_hash_entry *entries[max];
 339   struct top_hash_entry *ret, *nxt, *en;
 340   uint i = 0;
 341
 342   WALK_SLIST_DELSAFE(ret, nxt, n->lsrtl)
 343   {
 344     if (i == max)
 345       break;
 346
 347     en = ospf_hash_find_entry(p->gr, ret);
 348     if (!en)
 349     {
 350       /* Probably flushed LSA, this should not happen */
 351       log(L_WARN "%s: LSA disappeared (Type: %04x, Id: %R, Rt: %R)",
 352           p->p.name, ret->lsa_type, ret->lsa.id, ret->lsa.rt);
 353
 354       s_rem_node(SNODE ret);
 355       ospf_hash_delete(n->lsrth, ret);
 356
 357       continue;
 358     }
 359
 360     entries[i] = en;
 361     i++;
 362   }
 363
 364   ospf_send_lsupd(p, entries, i, n);
 365 }
 366
 367
 368 static inline int
 369 ospf_addr_is_local(struct ospf_proto *p, struct ospf_area *oa, ip_addr ip)
 370 {
 371   struct ospf_iface *ifa;
 372   WALK_LIST(ifa, p->iface_list)
 373     if ((ifa->oa == oa) && ifa->addr && ipa_equal(ifa->addr->ip, ip))
 374       return 1;
 375
 376   return 0;
 377 }
 378
 379 void
 380 ospf_receive_lsupd(struct ospf_packet *pkt, struct ospf_iface *ifa,
 381                    struct ospf_neighbor *n)
 382 {
 383   struct ospf_proto *p = ifa->oa->po;
 384
 385   /* RFC 2328 13. */
 386
 387   int sendreq = 1;        /* XXXX: review sendreq */
 388
 389   uint plen = ntohs(pkt->length);
 390   if (plen < (ospf_lsupd_hdrlen(p) + sizeof(struct ospf_lsa_header)))
 391   {
 392     log(L_ERR "OSPF: Bad LSUPD packet from %I - too short (%u B)", n->ip, plen);
 393     return;
 394   }
 395
 396   OSPF_PACKET(ospf_dump_lsupd, pkt, "LSUPD packet received from %I via %s", n->ip, ifa->ifname);
 397
 398   if (n->state < NEIGHBOR_EXCHANGE)
 399   {
 400     OSPF_TRACE(D_PACKETS, "Received lsupd in lesser state than EXCHANGE from (%I)", n->ip);
 401     return;
 402   }
 403
 404   ospf_neigh_sm(n, INM_HELLOREC);       /* Questionable */
 405
 406   uint offset, bound, i, lsa_count;
 407   ospf_lsupd_body(p, pkt, &offset, &bound, &lsa_count);
 408
 409   for (i = 0; i < lsa_count; i++)
 410   {
 411     struct ospf_lsa_header lsa, *lsa_n;
 412     struct top_hash_entry *en;
 413     u32 lsa_len, lsa_type, lsa_domain;
 414
 415     if (offset > bound)
 416     {
 417       log(L_WARN "%s: Received LSUPD from %I is too short", p->p.name, n->ip);
 418       ospf_neigh_sm(n, INM_BADLSREQ);
 419       return;
 420     }
 421
 422     /* LSA header in network order */
 423     lsa_n = ((void *) pkt) + offset;
 424     lsa_len = ntohs(lsa_n->length);
 425     offset += lsa_len;
 426
 427     if ((offset > plen) || ((lsa_len % 4) != 0) ||
 428         (lsa_len <= sizeof(struct ospf_lsa_header)))
 429     {
 430       log(L_WARN "%s: Received LSA from %I with bad length", p->p.name, n->ip);
 431       ospf_neigh_sm(n, INM_BADLSREQ);
 432       return;
 433     }
 434
 435     /* RFC 2328 13. (1) - validate LSA checksum */
 436     u16 chsum = lsa_n->checksum;
 437     if (chsum != lsasum_check(lsa_n, NULL))
 438     {
 439       log(L_WARN "%s: Received LSA from %I with bad checskum: %x %x",
 440           p->p.name, n->ip, chsum, lsa_n->checksum);
 441       continue;
 442     }
 443
 444     /* LSA header in host order */
 445     lsa_ntoh_hdr(lsa_n, &lsa);
 446     lsa_get_type_domain(&lsa, ifa, &lsa_type, &lsa_domain);
 447
 448     DBG("Update Type: %04x, Id: %R, Rt: %R, Sn: 0x%08x, Age: %u, Sum: %u\n",
 449         lsa_type, lsa.id, lsa.rt, lsa.sn, lsa.age, lsa.checksum);
 450
 451     /* RFC 2328 13. (2) */
 452     if (!lsa_type)
 453     {
 454       log(L_WARN "%s: Received unknown LSA type from %I", p->p.name, n->ip);
 455       continue;
 456     }
 457
 458     /* RFC 5340 4.5.1 (2) and RFC 2328 13. (3) */
 459     if (!oa_is_ext(ifa->oa) && (LSA_SCOPE(lsa_type) == LSA_SCOPE_AS))
 460     {
 461       log(L_WARN "%s: Received LSA with AS scope in stub area from %I", p->p.name, n->ip);
 462       continue;
 463     }
 464
 465     /* Errata 3746 to RFC 2328 - rt-summary-LSAs forbidden in stub areas */
 466     if (!oa_is_ext(ifa->oa) && (lsa_type == LSA_T_SUM_RT))
 467     {
 468       log(L_WARN "%s: Received rt-summary-LSA in stub area from %I", p->p.name, n->ip);
 469       continue;
 470     }
 471
 472     /* RFC 5340 4.5.1 (3) */
 473     if (LSA_SCOPE(lsa_type) == LSA_SCOPE_RES)
 474     {
 475       log(L_WARN "%s: Received LSA with invalid scope from %I", p->p.name, n->ip);
 476       continue;
 477     }
 478
 479     /* Find local copy of LSA in link state database */
 480     en = ospf_hash_find(p->gr, lsa_domain, lsa.id, lsa.rt, lsa_type);
 481
 482 #ifdef LOCAL_DEBUG
 483     if (en)
 484       DBG("I have Type: %04x, Id: %R, Rt: %R, Sn: 0x%08x, Age: %u, Sum: %u\n",
 485           en->lsa_type, en->lsa.id, en->lsa.rt, en->lsa.sn, en->lsa.age, en->lsa.checksum);
 486 #endif
 487
 488     /* 13. (4) - ignore maxage LSA if i have no local copy */
 489     if ((lsa.age == LSA_MAXAGE) && !en && (p->padj == 0))
 490     {
 491       /* 13.5. - schedule ACKs (tbl 19, case 5) */
 492       ospf_enqueue_lsack(n, lsa_n, ACKL_DIRECT);
 493       continue;
 494     }
 495
 496     /* 13. (5) - received LSA is newer (or no local copy) */
 497     if (!en || (lsa_comp(&lsa, &en->lsa) == CMP_NEWER))
 498     {
 499       /* 13. (5a) - enforce minimum time between updates for received LSAs */
 500       /* We also use this to ratelimit reactions to received self-originated LSAs */
 501       if (en && ((now - en->inst_time) < MINLSARRIVAL))
 502       {
 503         OSPF_TRACE(D_EVENTS, "Skipping LSA received in less that MinLSArrival");
 504         sendreq = 0;
 505         continue;
 506       }
 507
 508       /* Copy and validate LSA body */
 509       int blen = lsa.length - sizeof(struct ospf_lsa_header);
 510       void *body = mb_alloc(p->p.pool, blen);
 511       lsa_ntoh_body(lsa_n + 1, body, blen);
 512
 513       if (lsa_validate(&lsa, lsa_type, ospf_is_v2(p), body) == 0)
 514       {
 515         log(L_WARN "%s: Received invalid LSA from %I", p->p.name, n->ip);
 516         mb_free(body);
 517         sendreq = 0;
 518         continue;
 519       }
 520
 521       /* 13. (5f) - handle self-originated LSAs, see also 13.4. */
 522       if ((lsa.rt == p->router_id) ||
 523           (ospf_is_v2(p) && (lsa_type == LSA_T_NET) && ospf_addr_is_local(p, ifa->oa, ipa_from_u32(lsa.id))))
 524       {
 525         OSPF_TRACE(D_EVENTS, "Received unexpected self-originated LSA");
 526         ospf_advance_lsa(p, en, &lsa, lsa_type, lsa_domain, body);
 527         continue;
 528       }
 529
 530       /* 13. (5c) - remove old LSA from all retransmission lists */
 531       /* Must be done before (5b), otherwise it also removes the new entries from (5b) */
 532
 533       if (en)
 534         ospf_lsa_lsrt_down(en, n);
 535
 536       /*
 537       {
 538         struct ospf_iface *ifi;
 539         struct ospf_neighbor *ni;
 540
 541         WALK_LIST(ifi, p->iface_list)
 542           WALK_LIST(ni, ifi->neigh_list)
 543             if (ni->state > NEIGHBOR_EXSTART)
 544               ospf_lsa_lsrt_down(en, ni);
 545       }
 546       */
 547
 548       /* 13. (5d) - install new LSA into database */
 549       en = ospf_install_lsa(p, &lsa, lsa_type, lsa_domain, body);
 550
 551       /* RFC 5340 4.4.3 Events 6+7 - new Link LSA received */
 552       if (lsa_type == LSA_T_LINK)
 553         ospf_notify_net_lsa(ifa);
 554
 555       /* 13. (5b) - flood new LSA */
 556       int flood_back = ospf_lsupd_flood(p, en, n);
 557
 558       /* 13.5. - schedule ACKs (tbl 19, cases 1+2) */
 559       if (! flood_back)
 560         if ((ifa->state != OSPF_IS_BACKUP) || (n->rid == ifa->drid))
 561           ospf_enqueue_lsack(n, lsa_n, ACKL_DELAY);
 562
 563       /* FIXME: remove LSA entry if it is LSA_MAXAGE and it is possible? */
 564
 565       continue;
 566     }
 567
 568     /* FIXME pg145 (6) */
 569
 570     /* 13. (7) - received LSA is same */
 571     if (lsa_comp(&lsa, &en->lsa) == CMP_SAME)
 572     {
 573       /* Duplicate LSA, treat as implicit ACK */
 574       int implicit_ack = ospf_lsa_lsrt_down(en, n);
 575
 576       /* 13.5. - schedule ACKs (tbl 19, cases 3+4) */
 577       if (implicit_ack)
 578       {
 579         if ((ifa->state == OSPF_IS_BACKUP) && (n->rid == ifa->drid))
 580           ospf_enqueue_lsack(n, lsa_n, ACKL_DELAY);
 581       }
 582       else
 583         ospf_enqueue_lsack(n, lsa_n, ACKL_DIRECT);
 584
 585       sendreq = 0;
 586       continue;
 587     }
 588
 589     /* 13. (8) - received LSA is older */
 590     {
 591       /* Seqnum is wrapping, wait until it is flushed */
 592       if ((en->lsa.age == LSA_MAXAGE) && (en->lsa.sn == LSA_MAXSEQNO))
 593         continue;
 594
 595       /* Send newer local copy back to neighbor */
 596       /* FIXME - check for MinLSArrival ? */
 597       ospf_send_lsupd(p, &en, 1, n);
 598     }
 599   }
 600
 601   /* Send direct LSAs */
 602   ospf_lsack_send(n, ACKL_DIRECT);
 603
 604   /* If loading, ask for another part of neighbor's database */
 605   if (sendreq && (n->state == NEIGHBOR_LOADING))
 606     ospf_send_lsreq(p, n);
 607 }
 608