xref: /freebsd/sys/net/if_llatbl.c (revision e3aa18ad71782a73d3dd9dd3d526bbd2b607ca16) 
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_droped %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
1197