sys/net/if_llatbl.c

   1 /*-
   2  * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
   3  *
   4  * Copyright (c) 2004 Luigi Rizzo, Alessandro Cerri. All rights reserved.
   5  * Copyright (c) 2004-2008 Qing Li. All rights reserved.
   6  * Copyright (c) 2008 Kip Macy. All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29 #include <sys/cdefs.h>
  30 __FBSDID("$FreeBSD$");
  31
  32 #include "opt_ddb.h"
  33 #include "opt_inet.h"
  34 #include "opt_inet6.h"
  35
  36 #include <sys/param.h>
  37 #include <sys/systm.h>
  38 #include <sys/eventhandler.h>
  39 #include <sys/malloc.h>
  40 #include <sys/mbuf.h>
  41 #include <sys/syslog.h>
  42 #include <sys/sysctl.h>
  43 #include <sys/socket.h>
  44 #include <sys/kernel.h>
  45 #include <sys/lock.h>
  46 #include <sys/mutex.h>
  47 #include <sys/rwlock.h>
  48
  49 #ifdef DDB
  50 #include <ddb/ddb.h>
  51 #endif
  52
  53 #include <vm/uma.h>
  54
  55 #include <netinet/in.h>
  56 #include <net/if_llatbl.h>
  57 #include <net/if.h>
  58 #include <net/if_dl.h>
  59 #include <net/if_var.h>
  60 #include <net/route.h>
  61 #include <net/route/route_ctl.h>
  62 #include <net/route/route_debug.h>
  63 #include <net/vnet.h>
  64 #include <netinet/if_ether.h>
  65 #include <netinet6/in6_var.h>
  66 #include <netinet6/nd6.h>
  67
  68 MALLOC_DEFINE(M_LLTABLE, "lltable", "link level address tables");
  69
  70 VNET_DEFINE_STATIC(SLIST_HEAD(, lltable), lltables) =
  71     SLIST_HEAD_INITIALIZER(lltables);
  72 #define V_lltables      VNET(lltables)
  73
  74 static struct rwlock lltable_list_lock;
  75 RW_SYSINIT(lltable_list_lock, &lltable_list_lock, "lltable_list_lock");
  76 #define LLTABLE_LIST_RLOCK()            rw_rlock(&lltable_list_lock)
  77 #define LLTABLE_LIST_RUNLOCK()          rw_runlock(&lltable_list_lock)
  78 #define LLTABLE_LIST_WLOCK()            rw_wlock(&lltable_list_lock)
  79 #define LLTABLE_LIST_WUNLOCK()          rw_wunlock(&lltable_list_lock)
  80 #define LLTABLE_LIST_LOCK_ASSERT()      rw_assert(&lltable_list_lock, RA_LOCKED)
  81
  82 static void lltable_unlink(struct lltable *llt);
  83 static void llentries_unlink(struct lltable *llt, struct llentries *head);
  84
  85 /*
  86  * Dump lle state for a specific address family.
  87  */
  88 static int
  89 lltable_dump_af(struct lltable *llt, struct sysctl_req *wr)
  90 {
  91         struct epoch_tracker et;
  92         int error;
  93
  94         LLTABLE_LIST_LOCK_ASSERT();
  95
  96         if (llt->llt_ifp->if_flags & IFF_LOOPBACK)
  97                 return (0);
  98         error = 0;
  99
 100         NET_EPOCH_ENTER(et);
 101         error = lltable_foreach_lle(llt,
 102             (llt_foreach_cb_t *)llt->llt_dump_entry, wr);
 103         NET_EPOCH_EXIT(et);
 104
 105         return (error);
 106 }
 107
 108 /*
 109  * Dump arp state for a specific address family.
 110  */
 111 int
 112 lltable_sysctl_dumparp(int af, struct sysctl_req *wr)
 113 {
 114         struct lltable *llt;
 115         int error = 0;
 116
 117         LLTABLE_LIST_RLOCK();
 118         SLIST_FOREACH(llt, &V_lltables, llt_link) {
 119                 if (llt->llt_af == af) {
 120                         error = lltable_dump_af(llt, wr);
 121                         if (error != 0)
 122                                 goto done;
 123                 }
 124         }
 125 done:
 126         LLTABLE_LIST_RUNLOCK();
 127         return (error);
 128 }
 129
 130 /*
 131  * Adds a mbuf to hold queue. Drops old packets if the queue is full.
 132  *
 133  * Returns the number of held packets that were dropped.
 134  */
 135 size_t
 136 lltable_append_entry_queue(struct llentry *lle, struct mbuf *m,
 137     size_t maxheld)
 138 {
 139         size_t pkts_dropped = 0;
 140
 141         LLE_WLOCK_ASSERT(lle);
 142
 143         while (lle->la_numheld >= maxheld && lle->la_hold != NULL) {
 144                 struct mbuf *next = lle->la_hold->m_nextpkt;
 145                 m_freem(lle->la_hold);
 146                 lle->la_hold = next;
 147                 lle->la_numheld--;
 148                 pkts_dropped++;
 149         }
 150
 151         if (lle->la_hold != NULL) {
 152                 struct mbuf *curr = lle->la_hold;
 153                 while (curr->m_nextpkt != NULL)
 154                         curr = curr->m_nextpkt;
 155                 curr->m_nextpkt = m;
 156         } else
 157                 lle->la_hold = m;
 158
 159         lle->la_numheld++;
 160
 161         return pkts_dropped;
 162 }
 163
 164
 165 /*
 166  * Common function helpers for chained hash table.
 167  */
 168
 169 /*
 170  * Runs specified callback for each entry in @llt.
 171  * Caller does the locking.
 172  *
 173  */
 174 static int
 175 htable_foreach_lle(struct lltable *llt, llt_foreach_cb_t *f, void *farg)
 176 {
 177         struct llentry *lle, *next;
 178         int i, error;
 179
 180         error = 0;
 181
 182         for (i = 0; i < llt->llt_hsize; i++) {
 183                 CK_LIST_FOREACH_SAFE(lle, &llt->lle_head[i], lle_next, next) {
 184                         error = f(llt, lle, farg);
 185                         if (error != 0)
 186                                 break;
 187                 }
 188         }
 189
 190         return (error);
 191 }
 192
 193 /*
 194  * The htable_[un]link_entry() functions return:
 195  * 0 if the entry was (un)linked already and nothing changed,
 196  * 1 if the entry was added/removed to/from the table, and
 197  * -1 on error (e.g., not being able to add the entry due to limits reached).
 198  * While the "unlink" operation should never error, callers of
 199  * lltable_link_entry() need to check for errors and handle them.
 200  */
 201 static int
 202 htable_link_entry(struct lltable *llt, struct llentry *lle)
 203 {
 204         struct llentries *lleh;
 205         uint32_t hashidx;
 206
 207         if ((lle->la_flags & LLE_LINKED) != 0)
 208                 return (0);
 209
 210         IF_AFDATA_WLOCK_ASSERT(llt->llt_ifp);
 211
 212         if (llt->llt_maxentries > 0 &&
 213             llt->llt_entries >= llt->llt_maxentries)
 214                 return (-1);
 215
 216         hashidx = llt->llt_hash(lle, llt->llt_hsize);
 217         lleh = &llt->lle_head[hashidx];
 218
 219         lle->lle_tbl  = llt;
 220         lle->lle_head = lleh;
 221         lle->la_flags |= LLE_LINKED;
 222         CK_LIST_INSERT_HEAD(lleh, lle, lle_next);
 223         llt->llt_entries++;
 224
 225         return (1);
 226 }
 227
 228 static int
 229 htable_unlink_entry(struct llentry *lle)
 230 {
 231         struct lltable *llt;
 232
 233         if ((lle->la_flags & LLE_LINKED) == 0)
 234                 return (0);
 235
 236         llt = lle->lle_tbl;
 237         IF_AFDATA_WLOCK_ASSERT(llt->llt_ifp);
 238         KASSERT(llt->llt_entries > 0, ("%s: lltable %p (%s) entries %d <= 0",
 239             __func__, llt, if_name(llt->llt_ifp), llt->llt_entries));
 240
 241         CK_LIST_REMOVE(lle, lle_next);
 242         lle->la_flags &= ~(LLE_VALID | LLE_LINKED);
 243 #if 0
 244         lle->lle_tbl = NULL;
 245         lle->lle_head = NULL;
 246 #endif
 247         llt->llt_entries--;
 248
 249         return (1);
 250 }
 251
 252 struct prefix_match_data {
 253         const struct sockaddr *addr;
 254         const struct sockaddr *mask;
 255         struct llentries dchain;
 256         u_int flags;
 257 };
 258
 259 static int
 260 htable_prefix_free_cb(struct lltable *llt, struct llentry *lle, void *farg)
 261 {
 262         struct prefix_match_data *pmd;
 263
 264         pmd = (struct prefix_match_data *)farg;
 265
 266         if (llt->llt_match_prefix(pmd->addr, pmd->mask, pmd->flags, lle)) {
 267                 LLE_WLOCK(lle);
 268                 CK_LIST_INSERT_HEAD(&pmd->dchain, lle, lle_chain);
 269         }
 270
 271         return (0);
 272 }
 273
 274 static void
 275 htable_prefix_free(struct lltable *llt, const struct sockaddr *addr,
 276     const struct sockaddr *mask, u_int flags)
 277 {
 278         struct llentry *lle, *next;
 279         struct prefix_match_data pmd;
 280
 281         bzero(&pmd, sizeof(pmd));
 282         pmd.addr = addr;
 283         pmd.mask = mask;
 284         pmd.flags = flags;
 285         CK_LIST_INIT(&pmd.dchain);
 286
 287         IF_AFDATA_WLOCK(llt->llt_ifp);
 288         /* Push matching lles to chain */
 289         lltable_foreach_lle(llt, htable_prefix_free_cb, &pmd);
 290
 291         llentries_unlink(llt, &pmd.dchain);
 292         IF_AFDATA_WUNLOCK(llt->llt_ifp);
 293
 294         CK_LIST_FOREACH_SAFE(lle, &pmd.dchain, lle_chain, next)
 295                 lltable_free_entry(llt, lle);
 296 }
 297
 298 static void
 299 htable_free_tbl(struct lltable *llt)
 300 {
 301
 302         free(llt->lle_head, M_LLTABLE);
 303         free(llt, M_LLTABLE);
 304 }
 305
 306 static void
 307 llentries_unlink(struct lltable *llt, struct llentries *head)
 308 {
 309         struct llentry *lle, *next;
 310
 311         CK_LIST_FOREACH_SAFE(lle, head, lle_chain, next)
 312                 llt->llt_unlink_entry(lle);
 313 }
 314
 315 /*
 316  * Helper function used to drop all mbufs in hold queue.
 317  *
 318  * Returns the number of held packets, if any, that were dropped.
 319  */
 320 size_t
 321 lltable_drop_entry_queue(struct llentry *lle)
 322 {
 323         size_t pkts_dropped = 0;
 324
 325         LLE_WLOCK_ASSERT(lle);
 326
 327         while (lle->la_hold != NULL) {
 328                 struct mbuf *next = lle->la_hold->m_nextpkt;
 329                 m_freem(lle->la_hold);
 330                 lle->la_hold = next;
 331                 lle->la_numheld--;
 332                 pkts_dropped++;
 333         }
 334
 335         KASSERT(lle->la_numheld == 0,
 336                 ("%s: la_numheld %d > 0, pkts_dropped %zd", __func__,
 337                  lle->la_numheld, pkts_dropped));
 338
 339         return (pkts_dropped);
 340 }
 341
 342 void
 343 lltable_set_entry_addr(struct ifnet *ifp, struct llentry *lle,
 344     const char *linkhdr, size_t linkhdrsize, int lladdr_off)
 345 {
 346
 347         memcpy(lle->r_linkdata, linkhdr, linkhdrsize);
 348         lle->r_hdrlen = linkhdrsize;
 349         lle->ll_addr = &lle->r_linkdata[lladdr_off];
 350         lle->la_flags |= LLE_VALID;
 351         lle->r_flags |= RLLE_VALID;
 352 }
 353
 354 /*
 355  * Acquires lltable write lock.
 356  *
 357  * Returns true on success, with both lltable and lle lock held.
 358  * On failure, false is returned and lle wlock is still held.
 359  */
 360 bool
 361 lltable_acquire_wlock(struct ifnet *ifp, struct llentry *lle)
 362 {
 363         NET_EPOCH_ASSERT();
 364
 365         /* Perform real LLE update */
 366         /* use afdata WLOCK to update fields */
 367         LLE_WUNLOCK(lle);
 368         IF_AFDATA_WLOCK(ifp);
 369         LLE_WLOCK(lle);
 370
 371         /*
 372          * Since we droppped LLE lock, other thread might have deleted
 373          * this lle. Check and return
 374          */
 375         if ((lle->la_flags & LLE_DELETED) != 0) {
 376                 IF_AFDATA_WUNLOCK(ifp);
 377                 return (false);
 378         }
 379
 380         return (true);
 381 }
 382
 383 /*
 384  * Tries to update @lle link-level address.
 385  * Since update requires AFDATA WLOCK, function
 386  * drops @lle lock, acquires AFDATA lock and then acquires
 387  * @lle lock to maintain lock order.
 388  *
 389  * Returns 1 on success.
 390  */
 391 int
 392 lltable_try_set_entry_addr(struct ifnet *ifp, struct llentry *lle,
 393     const char *linkhdr, size_t linkhdrsize, int lladdr_off)
 394 {
 395
 396         if (!lltable_acquire_wlock(ifp, lle))
 397                 return (0);
 398
 399         /* Update data */
 400         lltable_set_entry_addr(ifp, lle, linkhdr, linkhdrsize, lladdr_off);
 401
 402         IF_AFDATA_WUNLOCK(ifp);
 403
 404         return (1);
 405 }
 406
 407  /*
 408  * Helper function used to pre-compute full/partial link-layer
 409  * header data suitable for feeding into if_output().
 410  */
 411 int
 412 lltable_calc_llheader(struct ifnet *ifp, int family, char *lladdr,
 413     char *buf, size_t *bufsize, int *lladdr_off)
 414 {
 415         struct if_encap_req ereq;
 416         int error;
 417
 418         bzero(buf, *bufsize);
 419         bzero(&ereq, sizeof(ereq));
 420         ereq.buf = buf;
 421         ereq.bufsize = *bufsize;
 422         ereq.rtype = IFENCAP_LL;
 423         ereq.family = family;
 424         ereq.lladdr = lladdr;
 425         ereq.lladdr_len = ifp->if_addrlen;
 426         error = ifp->if_requestencap(ifp, &ereq);
 427         if (error == 0) {
 428                 *bufsize = ereq.bufsize;
 429                 *lladdr_off = ereq.lladdr_off;
 430         }
 431
 432         return (error);
 433 }
 434
 435 /*
 436  * Searches for the child entry matching @family inside @lle.
 437  * Returns the entry or NULL.
 438  */
 439 struct llentry *
 440 llentry_lookup_family(struct llentry *lle, int family)
 441 {
 442         struct llentry *child_lle;
 443
 444         if (lle == NULL)
 445                 return (NULL);
 446
 447         CK_SLIST_FOREACH(child_lle, &lle->lle_children, lle_child_next) {
 448                 if (child_lle->r_family == family)
 449                         return (child_lle);
 450         }
 451
 452         return (NULL);
 453 }
 454
 455 /*
 456  * Retrieves upper protocol family for the llentry.
 457  * By default, all "normal" (e.g. upper_family == transport_family)
 458  * llentries have r_family set to 0.
 459  * Thus, use @default_family in that regard, otherwise use r_family.
 460  *
 461  * Returns upper protocol family
 462  */
 463 int
 464 llentry_get_upper_family(const struct llentry *lle, int default_family)
 465 {
 466         return (lle->r_family == 0 ? default_family : lle->r_family);
 467 }
 468
 469 /*
 470  * Prints llentry @lle data into provided buffer.
 471  * Example: lle/inet/valid/em0/1.2.3.4
 472  *
 473  * Returns @buf.
 474  */
 475 char *
 476 llentry_print_buf(const struct llentry *lle, struct ifnet *ifp, int family,
 477     char *buf, size_t bufsize)
 478 {
 479 #if defined(INET) || defined(INET6)
 480         char abuf[INET6_ADDRSTRLEN];
 481 #endif
 482
 483         const char *valid = (lle->r_flags & RLLE_VALID) ? "valid" : "no_l2";
 484         const char *upper_str = rib_print_family(llentry_get_upper_family(lle, family));
 485
 486         switch (family) {
 487 #ifdef INET
 488         case AF_INET:
 489                 inet_ntop(AF_INET, &lle->r_l3addr.addr4, abuf, sizeof(abuf));
 490                 snprintf(buf, bufsize, "lle/%s/%s/%s/%s", upper_str,
 491                     valid, if_name(ifp), abuf);
 492                 break;
 493 #endif
 494 #ifdef INET6
 495         case AF_INET6:
 496                 inet_ntop(AF_INET6, &lle->r_l3addr.addr6, abuf, sizeof(abuf));
 497                 snprintf(buf, bufsize, "lle/%s/%s/%s/%s", upper_str,
 498                     valid, if_name(ifp), abuf);
 499                 break;
 500 #endif
 501         default:
 502                 snprintf(buf, bufsize, "lle/%s/%s/%s/????", upper_str,
 503                     valid, if_name(ifp));
 504                 break;
 505         }
 506
 507         return (buf);
 508 }
 509
 510 char *
 511 llentry_print_buf_lltable(const struct llentry *lle, char *buf, size_t bufsize)
 512 {
 513         struct lltable *tbl = lle->lle_tbl;
 514
 515         return (llentry_print_buf(lle, lltable_get_ifp(tbl), lltable_get_af(tbl), buf, bufsize));
 516 }
 517
 518 /*
 519  * Requests feedback from the datapath.
 520  * First packet using @lle should result in
 521  * setting r_skip_req back to 0 and updating
 522  * lle_hittime to the current time_uptime.
 523  */
 524 void
 525 llentry_request_feedback(struct llentry *lle)
 526 {
 527         struct llentry *child_lle;
 528
 529         LLE_REQ_LOCK(lle);
 530         lle->r_skip_req = 1;
 531         LLE_REQ_UNLOCK(lle);
 532
 533         CK_SLIST_FOREACH(child_lle, &lle->lle_children, lle_child_next) {
 534                 LLE_REQ_LOCK(child_lle);
 535                 child_lle->r_skip_req = 1;
 536                 LLE_REQ_UNLOCK(child_lle);
 537         }
 538 }
 539
 540 /*
 541  * Updates the lle state to mark it has been used
 542  * and record the time.
 543  * Used by the llentry_provide_feedback() wrapper.
 544  */
 545 void
 546 llentry_mark_used(struct llentry *lle)
 547 {
 548         LLE_REQ_LOCK(lle);
 549         lle->r_skip_req = 0;
 550         lle->lle_hittime = time_uptime;
 551         LLE_REQ_UNLOCK(lle);
 552 }
 553
 554 /*
 555  * Fetches the time when lle was used.
 556  * Return 0 if the entry was not used, relevant time_uptime
 557  *  otherwise.
 558  */
 559 static time_t
 560 llentry_get_hittime_raw(struct llentry *lle)
 561 {
 562         time_t lle_hittime = 0;
 563
 564         LLE_REQ_LOCK(lle);
 565         if ((lle->r_skip_req == 0) && (lle_hittime < lle->lle_hittime))
 566                 lle_hittime = lle->lle_hittime;
 567         LLE_REQ_UNLOCK(lle);
 568
 569         return (lle_hittime);
 570 }
 571
 572 time_t
 573 llentry_get_hittime(struct llentry *lle)
 574 {
 575         time_t lle_hittime = 0;
 576         struct llentry *child_lle;
 577
 578         lle_hittime = llentry_get_hittime_raw(lle);
 579
 580         CK_SLIST_FOREACH(child_lle, &lle->lle_children, lle_child_next) {
 581                 time_t hittime = llentry_get_hittime_raw(child_lle);
 582                 if (hittime > lle_hittime)
 583                         lle_hittime = hittime;
 584         }
 585
 586         return (lle_hittime);
 587 }
 588
 589 /*
 590  * Update link-layer header for given @lle after
 591  * interface lladdr was changed.
 592  */
 593 static int
 594 llentry_update_ifaddr(struct lltable *llt, struct llentry *lle, void *farg)
 595 {
 596         struct ifnet *ifp;
 597         u_char linkhdr[LLE_MAX_LINKHDR];
 598         size_t linkhdrsize;
 599         u_char *lladdr;
 600         int lladdr_off;
 601
 602         ifp = (struct ifnet *)farg;
 603
 604         lladdr = lle->ll_addr;
 605
 606         LLE_WLOCK(lle);
 607         if ((lle->la_flags & LLE_VALID) == 0) {
 608                 LLE_WUNLOCK(lle);
 609                 return (0);
 610         }
 611
 612         if ((lle->la_flags & LLE_IFADDR) != 0)
 613                 lladdr = IF_LLADDR(ifp);
 614
 615         linkhdrsize = sizeof(linkhdr);
 616         lltable_calc_llheader(ifp, llt->llt_af, lladdr, linkhdr, &linkhdrsize,
 617             &lladdr_off);
 618         memcpy(lle->r_linkdata, linkhdr, linkhdrsize);
 619         LLE_WUNLOCK(lle);
 620
 621         return (0);
 622 }
 623
 624 /*
 625  * Update all calculated headers for given @llt
 626  */
 627 void
 628 lltable_update_ifaddr(struct lltable *llt)
 629 {
 630
 631         if (llt->llt_ifp->if_flags & IFF_LOOPBACK)
 632                 return;
 633
 634         IF_AFDATA_WLOCK(llt->llt_ifp);
 635         lltable_foreach_lle(llt, llentry_update_ifaddr, llt->llt_ifp);
 636         IF_AFDATA_WUNLOCK(llt->llt_ifp);
 637 }
 638
 639 /*
 640  *
 641  * Performs generic cleanup routines and frees lle.
 642  *
 643  * Called for non-linked entries, with callouts and
 644  * other AF-specific cleanups performed.
 645  *
 646  * @lle must be passed WLOCK'ed
 647  *
 648  * Returns the number of held packets, if any, that were dropped.
 649  */
 650 size_t
 651 llentry_free(struct llentry *lle)
 652 {
 653         size_t pkts_dropped;
 654
 655         LLE_WLOCK_ASSERT(lle);
 656
 657         KASSERT((lle->la_flags & LLE_LINKED) == 0, ("freeing linked lle"));
 658
 659         pkts_dropped = lltable_drop_entry_queue(lle);
 660
 661         /* cancel timer */
 662         if (callout_stop(&lle->lle_timer) > 0)
 663                 LLE_REMREF(lle);
 664         LLE_FREE_LOCKED(lle);
 665
 666         return (pkts_dropped);
 667 }
 668
 669 /*
 670  * Free all entries from given table and free itself.
 671  */
 672
 673 static int
 674 lltable_free_cb(struct lltable *llt, struct llentry *lle, void *farg)
 675 {
 676         struct llentries *dchain;
 677
 678         dchain = (struct llentries *)farg;
 679
 680         LLE_WLOCK(lle);
 681         CK_LIST_INSERT_HEAD(dchain, lle, lle_chain);
 682
 683         return (0);
 684 }
 685
 686 /*
 687  * Free all entries from given table and free itself.
 688  */
 689 void
 690 lltable_free(struct lltable *llt)
 691 {
 692         struct llentry *lle, *next;
 693         struct llentries dchain;
 694
 695         KASSERT(llt != NULL, ("%s: llt is NULL", __func__));
 696
 697         lltable_unlink(llt);
 698
 699         CK_LIST_INIT(&dchain);
 700         IF_AFDATA_WLOCK(llt->llt_ifp);
 701         /* Push all lles to @dchain */
 702         lltable_foreach_lle(llt, lltable_free_cb, &dchain);
 703         llentries_unlink(llt, &dchain);
 704         IF_AFDATA_WUNLOCK(llt->llt_ifp);
 705
 706         CK_LIST_FOREACH_SAFE(lle, &dchain, lle_chain, next) {
 707                 llentry_free(lle);
 708         }
 709
 710         KASSERT(llt->llt_entries == 0, ("%s: lltable %p (%s) entires not 0: %d",
 711             __func__, llt, llt->llt_ifp->if_xname, llt->llt_entries));
 712
 713         llt->llt_free_tbl(llt);
 714 }
 715
 716 /*
 717  * Deletes an address from given lltable.
 718  * Used for userland interaction to remove
 719  * individual entries. Skips entries added by OS.
 720  */
 721 int
 722 lltable_delete_addr(struct lltable *llt, u_int flags,
 723     const struct sockaddr *l3addr)
 724 {
 725         struct llentry *lle;
 726         struct ifnet *ifp;
 727
 728         ifp = llt->llt_ifp;
 729         IF_AFDATA_WLOCK(ifp);
 730         lle = lla_lookup(llt, LLE_SF(l3addr->sa_family, LLE_EXCLUSIVE), l3addr);
 731
 732         if (lle == NULL) {
 733                 IF_AFDATA_WUNLOCK(ifp);
 734                 return (ENOENT);
 735         }
 736         if ((lle->la_flags & LLE_IFADDR) != 0 && (flags & LLE_IFADDR) == 0) {
 737                 IF_AFDATA_WUNLOCK(ifp);
 738                 LLE_WUNLOCK(lle);
 739                 return (EPERM);
 740         }
 741
 742         lltable_unlink_entry(llt, lle);
 743         IF_AFDATA_WUNLOCK(ifp);
 744
 745         llt->llt_delete_entry(llt, lle);
 746
 747         return (0);
 748 }
 749
 750 void
 751 lltable_prefix_free(int af, struct sockaddr *addr, struct sockaddr *mask,
 752     u_int flags)
 753 {
 754         struct lltable *llt;
 755
 756         LLTABLE_LIST_RLOCK();
 757         SLIST_FOREACH(llt, &V_lltables, llt_link) {
 758                 if (llt->llt_af != af)
 759                         continue;
 760
 761                 llt->llt_prefix_free(llt, addr, mask, flags);
 762         }
 763         LLTABLE_LIST_RUNLOCK();
 764 }
 765
 766 /*
 767  * Delete llentries that func() returns true.
 768  */
 769 struct lle_match_data {
 770         struct llentries dchain;
 771         llt_match_cb_t *func;
 772         void *farg;
 773 };
 774
 775 static int
 776 lltable_delete_conditional_cb(struct lltable *llt, struct llentry *lle,
 777     void *farg)
 778 {
 779         struct lle_match_data *lmd;
 780
 781         lmd = (struct lle_match_data *)farg;
 782         if (lmd->func(llt, lle, lmd->farg)) {
 783                 LLE_WLOCK(lle);
 784                 CK_LIST_INSERT_HEAD(&lmd->dchain, lle, lle_chain);
 785         }
 786
 787         return (0);
 788 }
 789
 790 void
 791 lltable_delete_conditional(struct lltable *llt, llt_match_cb_t *func,
 792     void *farg)
 793 {
 794         struct llentry *lle, *next;
 795         struct lle_match_data lmd;
 796
 797         bzero(&lmd, sizeof(lmd));
 798         CK_LIST_INIT(&lmd.dchain);
 799         lmd.func = func;
 800         lmd.farg = farg;
 801
 802         IF_AFDATA_WLOCK(llt->llt_ifp);
 803         lltable_foreach_lle(llt, lltable_delete_conditional_cb, &lmd);
 804         llentries_unlink(llt, &lmd.dchain);
 805         IF_AFDATA_WUNLOCK(llt->llt_ifp);
 806
 807         CK_LIST_FOREACH_SAFE(lle, &lmd.dchain, lle_chain, next)
 808                 llt->llt_delete_entry(llt, lle);
 809 }
 810
 811 struct lltable *
 812 lltable_allocate_htbl(uint32_t hsize)
 813 {
 814         struct lltable *llt;
 815         int i;
 816
 817         llt = malloc(sizeof(struct lltable), M_LLTABLE, M_WAITOK | M_ZERO);
 818         llt->llt_hsize = hsize;
 819         llt->lle_head = malloc(sizeof(struct llentries) * hsize,
 820             M_LLTABLE, M_WAITOK | M_ZERO);
 821
 822         for (i = 0; i < llt->llt_hsize; i++)
 823                 CK_LIST_INIT(&llt->lle_head[i]);
 824
 825         /* Set some default callbacks */
 826         llt->llt_link_entry = htable_link_entry;
 827         llt->llt_unlink_entry = htable_unlink_entry;
 828         llt->llt_prefix_free = htable_prefix_free;
 829         llt->llt_foreach_entry = htable_foreach_lle;
 830         llt->llt_free_tbl = htable_free_tbl;
 831
 832         return (llt);
 833 }
 834
 835 /*
 836  * Links lltable to global llt list.
 837  */
 838 void
 839 lltable_link(struct lltable *llt)
 840 {
 841
 842         LLTABLE_LIST_WLOCK();
 843         SLIST_INSERT_HEAD(&V_lltables, llt, llt_link);
 844         LLTABLE_LIST_WUNLOCK();
 845 }
 846
 847 static void
 848 lltable_unlink(struct lltable *llt)
 849 {
 850
 851         LLTABLE_LIST_WLOCK();
 852         SLIST_REMOVE(&V_lltables, llt, lltable, llt_link);
 853         LLTABLE_LIST_WUNLOCK();
 854
 855 }
 856
 857 /*
 858  * Gets interface @ifp lltable for the specified @family
 859  */
 860 struct lltable *
 861 lltable_get(struct ifnet *ifp, int family)
 862 {
 863         switch (family) {
 864 #ifdef INET
 865         case AF_INET:
 866                 return (in_lltable_get(ifp));
 867 #endif
 868 #ifdef INET6
 869         case AF_INET6:
 870                 return (in6_lltable_get(ifp));
 871 #endif
 872         }
 873
 874         return (NULL);
 875 }
 876
 877 /*
 878  * External methods used by lltable consumers
 879  */
 880
 881 int
 882 lltable_foreach_lle(struct lltable *llt, llt_foreach_cb_t *f, void *farg)
 883 {
 884
 885         return (llt->llt_foreach_entry(llt, f, farg));
 886 }
 887
 888 struct llentry *
 889 lltable_alloc_entry(struct lltable *llt, u_int flags,
 890     const struct sockaddr *l3addr)
 891 {
 892
 893         return (llt->llt_alloc_entry(llt, flags, l3addr));
 894 }
 895
 896 void
 897 lltable_free_entry(struct lltable *llt, struct llentry *lle)
 898 {
 899
 900         llt->llt_free_entry(llt, lle);
 901 }
 902
 903 int
 904 lltable_link_entry(struct lltable *llt, struct llentry *lle)
 905 {
 906
 907         return (llt->llt_link_entry(llt, lle));
 908 }
 909
 910 void
 911 lltable_link_child_entry(struct llentry *lle, struct llentry *child_lle)
 912 {
 913         child_lle->lle_parent = lle;
 914         child_lle->lle_tbl = lle->lle_tbl;
 915         child_lle->la_flags |= LLE_LINKED;
 916         CK_SLIST_INSERT_HEAD(&lle->lle_children, child_lle, lle_child_next);
 917 }
 918
 919 void
 920 lltable_unlink_child_entry(struct llentry *child_lle)
 921 {
 922         struct llentry *lle = child_lle->lle_parent;
 923
 924         child_lle->la_flags &= ~LLE_LINKED;
 925         child_lle->lle_parent = NULL;
 926         CK_SLIST_REMOVE(&lle->lle_children, child_lle, llentry, lle_child_next);
 927 }
 928
 929 int
 930 lltable_unlink_entry(struct lltable *llt, struct llentry *lle)
 931 {
 932
 933         return (llt->llt_unlink_entry(lle));
 934 }
 935
 936 void
 937 lltable_fill_sa_entry(const struct llentry *lle, struct sockaddr *sa)
 938 {
 939         struct lltable *llt;
 940
 941         llt = lle->lle_tbl;
 942         llt->llt_fill_sa_entry(lle, sa);
 943 }
 944
 945 struct ifnet *
 946 lltable_get_ifp(const struct lltable *llt)
 947 {
 948
 949         return (llt->llt_ifp);
 950 }
 951
 952 int
 953 lltable_get_af(const struct lltable *llt)
 954 {
 955
 956         return (llt->llt_af);
 957 }
 958
 959 /*
 960  * Called in route_output when rtm_flags contains RTF_LLDATA.
 961  */
 962 int
 963 lla_rt_output(struct rt_msghdr *rtm, struct rt_addrinfo *info)
 964 {
 965         struct sockaddr_dl *dl =
 966             (struct sockaddr_dl *)info->rti_info[RTAX_GATEWAY];
 967         struct sockaddr *dst = (struct sockaddr *)info->rti_info[RTAX_DST];
 968         struct ifnet *ifp;
 969         struct lltable *llt;
 970         struct llentry *lle, *lle_tmp;
 971         uint8_t linkhdr[LLE_MAX_LINKHDR];
 972         size_t linkhdrsize;
 973         int lladdr_off;
 974         u_int laflags = 0;
 975         int error;
 976
 977         if (dl == NULL || dl->sdl_family != AF_LINK)
 978                 return (EINVAL);
 979
 980         /* XXX: should be ntohs() */
 981         ifp = ifnet_byindex(dl->sdl_index);
 982         if (ifp == NULL) {
 983                 log(LOG_INFO, "%s: invalid ifp (sdl_index %d)\n",
 984                     __func__, dl->sdl_index);
 985                 return EINVAL;
 986         }
 987
 988         llt = lltable_get(ifp, dst->sa_family);
 989
 990         if (llt == NULL)
 991                 return (ESRCH);
 992
 993         error = 0;
 994
 995         switch (rtm->rtm_type) {
 996         case RTM_ADD:
 997                 /* Add static LLE */
 998                 laflags = 0;
 999                 if (rtm->rtm_rmx.rmx_expire == 0)
1000                         laflags = LLE_STATIC;
1001                 lle = lltable_alloc_entry(llt, laflags, dst);
1002                 if (lle == NULL)
1003                         return (ENOMEM);
1004
1005                 linkhdrsize = sizeof(linkhdr);
1006                 if (lltable_calc_llheader(ifp, dst->sa_family, LLADDR(dl),
1007                     linkhdr, &linkhdrsize, &lladdr_off) != 0) {
1008                         lltable_free_entry(llt, lle);
1009                         return (EINVAL);
1010                 }
1011                 lltable_set_entry_addr(ifp, lle, linkhdr, linkhdrsize,
1012                     lladdr_off);
1013                 if ((rtm->rtm_flags & RTF_ANNOUNCE))
1014                         lle->la_flags |= LLE_PUB;
1015                 lle->la_expire = rtm->rtm_rmx.rmx_expire;
1016
1017                 laflags = lle->la_flags;
1018
1019                 /* Try to link new entry */
1020                 lle_tmp = NULL;
1021                 IF_AFDATA_WLOCK(ifp);
1022                 LLE_WLOCK(lle);
1023                 lle_tmp = lla_lookup(llt, LLE_EXCLUSIVE, dst);
1024                 if (lle_tmp != NULL) {
1025                         /* Check if we are trying to replace immutable entry */
1026                         if ((lle_tmp->la_flags & LLE_IFADDR) != 0) {
1027                                 IF_AFDATA_WUNLOCK(ifp);
1028                                 LLE_WUNLOCK(lle_tmp);
1029                                 lltable_free_entry(llt, lle);
1030                                 return (EPERM);
1031                         }
1032                         /* Unlink existing entry from table */
1033                         lltable_unlink_entry(llt, lle_tmp);
1034                 }
1035                 lltable_link_entry(llt, lle);
1036                 if ((lle->la_flags & LLE_PUB) != 0 &&
1037                     (llt->llt_flags & LLT_ADDEDPROXY) == 0)
1038                         llt->llt_flags |= LLT_ADDEDPROXY;
1039                 IF_AFDATA_WUNLOCK(ifp);
1040
1041                 if (lle_tmp != NULL) {
1042                         EVENTHANDLER_INVOKE(lle_event, lle_tmp,LLENTRY_EXPIRED);
1043                         lltable_free_entry(llt, lle_tmp);
1044                 }
1045
1046                 /*
1047                  * By invoking LLE handler here we might get
1048                  * two events on static LLE entry insertion
1049                  * in routing socket. However, since we might have
1050                  * other subscribers we need to generate this event.
1051                  */
1052                 EVENTHANDLER_INVOKE(lle_event, lle, LLENTRY_RESOLVED);
1053                 LLE_WUNLOCK(lle);
1054                 llt->llt_post_resolved(llt, lle);
1055                 break;
1056
1057         case RTM_DELETE:
1058                 return (lltable_delete_addr(llt, 0, dst));
1059
1060         default:
1061                 error = EINVAL;
1062         }
1063
1064         return (error);
1065 }
1066
1067 #ifdef DDB
1068 struct llentry_sa {
1069         struct llentry          base;
1070         struct sockaddr         l3_addr;
1071 };
1072
1073 static void
1074 llatbl_lle_show(struct llentry_sa *la)
1075 {
1076         struct llentry *lle;
1077         uint8_t octet[6];
1078
1079         lle = &la->base;
1080         db_printf("lle=%p\n", lle);
1081         db_printf(" lle_next=%p\n", lle->lle_next.cle_next);
1082         db_printf(" lle_lock=%p\n", &lle->lle_lock);
1083         db_printf(" lle_tbl=%p\n", lle->lle_tbl);
1084         db_printf(" lle_head=%p\n", lle->lle_head);
1085         db_printf(" la_hold=%p\n", lle->la_hold);
1086         db_printf(" la_numheld=%d\n", lle->la_numheld);
1087         db_printf(" la_expire=%ju\n", (uintmax_t)lle->la_expire);
1088         db_printf(" la_flags=0x%04x\n", lle->la_flags);
1089         db_printf(" la_asked=%u\n", lle->la_asked);
1090         db_printf(" la_preempt=%u\n", lle->la_preempt);
1091         db_printf(" ln_state=%d\n", lle->ln_state);
1092         db_printf(" ln_router=%u\n", lle->ln_router);
1093         db_printf(" ln_ntick=%ju\n", (uintmax_t)lle->ln_ntick);
1094         db_printf(" lle_refcnt=%d\n", lle->lle_refcnt);
1095         bcopy(lle->ll_addr, octet, sizeof(octet));
1096         db_printf(" ll_addr=%02x:%02x:%02x:%02x:%02x:%02x\n",
1097             octet[0], octet[1], octet[2], octet[3], octet[4], octet[5]);
1098         db_printf(" lle_timer=%p\n", &lle->lle_timer);
1099
1100         switch (la->l3_addr.sa_family) {
1101 #ifdef INET
1102         case AF_INET:
1103         {
1104                 struct sockaddr_in *sin;
1105                 char l3s[INET_ADDRSTRLEN];
1106
1107                 sin = (struct sockaddr_in *)&la->l3_addr;
1108                 inet_ntoa_r(sin->sin_addr, l3s);
1109                 db_printf(" l3_addr=%s\n", l3s);
1110                 break;
1111         }
1112 #endif
1113 #ifdef INET6
1114         case AF_INET6:
1115         {
1116                 struct sockaddr_in6 *sin6;
1117                 char l3s[INET6_ADDRSTRLEN];
1118
1119                 sin6 = (struct sockaddr_in6 *)&la->l3_addr;
1120                 ip6_sprintf(l3s, &sin6->sin6_addr);
1121                 db_printf(" l3_addr=%s\n", l3s);
1122                 break;
1123         }
1124 #endif
1125         default:
1126                 db_printf(" l3_addr=N/A (af=%d)\n", la->l3_addr.sa_family);
1127                 break;
1128         }
1129 }
1130
1131 DB_SHOW_COMMAND(llentry, db_show_llentry)
1132 {
1133
1134         if (!have_addr) {
1135                 db_printf("usage: show llentry <struct llentry *>\n");
1136                 return;
1137         }
1138
1139         llatbl_lle_show((struct llentry_sa *)addr);
1140 }
1141
1142 static void
1143 llatbl_llt_show(struct lltable *llt)
1144 {
1145         int i;
1146         struct llentry *lle;
1147
1148         db_printf("llt=%p llt_af=%d llt_ifp=%p\n",
1149             llt, llt->llt_af, llt->llt_ifp);
1150
1151         for (i = 0; i < llt->llt_hsize; i++) {
1152                 CK_LIST_FOREACH(lle, &llt->lle_head[i], lle_next) {
1153                         llatbl_lle_show((struct llentry_sa *)lle);
1154                         if (db_pager_quit)
1155                                 return;
1156                 }
1157         }
1158 }
1159
1160 DB_SHOW_COMMAND(lltable, db_show_lltable)
1161 {
1162
1163         if (!have_addr) {
1164                 db_printf("usage: show lltable <struct lltable *>\n");
1165                 return;
1166         }
1167
1168         llatbl_llt_show((struct lltable *)addr);
1169 }
1170
1171 DB_SHOW_ALL_COMMAND(lltables, db_show_all_lltables)
1172 {
1173         VNET_ITERATOR_DECL(vnet_iter);
1174         struct lltable *llt;
1175
1176         VNET_FOREACH(vnet_iter) {
1177                 CURVNET_SET_QUIET(vnet_iter);
1178 #ifdef VIMAGE
1179                 db_printf("vnet=%p\n", curvnet);
1180 #endif
1181                 SLIST_FOREACH(llt, &V_lltables, llt_link) {
1182                         db_printf("llt=%p llt_af=%d llt_ifp=%p(%s)\n",
1183                             llt, llt->llt_af, llt->llt_ifp,
1184                             (llt->llt_ifp != NULL) ?
1185                                 llt->llt_ifp->if_xname : "?");
1186                         if (have_addr && addr != 0) /* verbose */
1187                                 llatbl_llt_show(llt);
1188                         if (db_pager_quit) {
1189                                 CURVNET_RESTORE();
1190                                 return;
1191                         }
1192                 }
1193                 CURVNET_RESTORE();
1194         }
1195 }
1196 #endif