diff --git a/sys/net/if_llatbl.h b/sys/net/if_llatbl.h
--- a/sys/net/if_llatbl.h
+++ b/sys/net/if_llatbl.h
@@ -238,6 +238,8 @@
 struct ifnet *lltable_get_ifp(const struct lltable *llt);
 int lltable_get_af(const struct lltable *llt);
 
+bool lltable_acquire_wlock(struct ifnet *ifp, struct llentry *lle);
+
 int lltable_foreach_lle(struct lltable *llt, llt_foreach_cb_t *f,
     void *farg);
 /*
diff --git a/sys/net/if_llatbl.c b/sys/net/if_llatbl.c
--- a/sys/net/if_llatbl.c
+++ b/sys/net/if_llatbl.c
@@ -318,22 +318,18 @@
 }
 
 /*
- * Tries to update @lle link-level address.
- * Since update requires AFDATA WLOCK, function
- * drops @lle lock, acquires AFDATA lock and then acquires
- * @lle lock to maintain lock order.
+ * Acquires lltable write lock.
  *
- * Returns 1 on success.
+ * Returns true on success, with both lltable and lle lock held.
+ * On failure, false is returned and lle wlock is still held.
  */
-int
-lltable_try_set_entry_addr(struct ifnet *ifp, struct llentry *lle,
-    const char *linkhdr, size_t linkhdrsize, int lladdr_off)
+bool
+lltable_acquire_wlock(struct ifnet *ifp, struct llentry *lle)
 {
+	NET_EPOCH_ASSERT();
 
 	/* Perform real LLE update */
 	/* use afdata WLOCK to update fields */
-	LLE_WLOCK_ASSERT(lle);
-	LLE_ADDREF(lle);
 	LLE_WUNLOCK(lle);
 	IF_AFDATA_WLOCK(ifp);
 	LLE_WLOCK(lle);
@@ -344,17 +340,33 @@
 	 */
 	if ((lle->la_flags & LLE_DELETED) != 0) {
 		IF_AFDATA_WUNLOCK(ifp);
-		LLE_FREE_LOCKED(lle);
-		return (0);
+		return (false);
 	}
 
+	return (true);
+}
+
+/*
+ * Tries to update @lle link-level address.
+ * Since update requires AFDATA WLOCK, function
+ * drops @lle lock, acquires AFDATA lock and then acquires
+ * @lle lock to maintain lock order.
+ *
+ * Returns 1 on success.
+ */
+int
+lltable_try_set_entry_addr(struct ifnet *ifp, struct llentry *lle,
+    const char *linkhdr, size_t linkhdrsize, int lladdr_off)
+{
+
+	if (!lltable_acquire_wlock(ifp, lle))
+		return (0);
+
 	/* Update data */
 	lltable_set_entry_addr(ifp, lle, linkhdr, linkhdrsize, lladdr_off);
 
 	IF_AFDATA_WUNLOCK(ifp);
 
-	LLE_REMREF(lle);
-
 	return (1);
 }
 
diff --git a/sys/netinet6/nd6.h b/sys/netinet6/nd6.h
--- a/sys/netinet6/nd6.h
+++ b/sys/netinet6/nd6.h
@@ -376,6 +376,7 @@
 int nd6_ioctl(u_long, caddr_t, struct ifnet *);
 void nd6_cache_lladdr(struct ifnet *, struct in6_addr *,
 	char *, int, int, int);
+bool nd6_try_set_entry_addr(struct ifnet *ifp, struct llentry *lle, char *lladdr);
 struct mbuf *nd6_grab_holdchain(struct llentry *);
 int nd6_flush_holdchain(struct ifnet *, struct llentry *, struct mbuf *);
 int nd6_add_ifa_lle(struct in6_ifaddr *);
diff --git a/sys/netinet6/nd6.c b/sys/netinet6/nd6.c
--- a/sys/netinet6/nd6.c
+++ b/sys/netinet6/nd6.c
@@ -1382,6 +1382,35 @@
 	return (rc);
 }
 
+/*
+ * Tries to update @lle address/prepend data with new @lladdr.
+ *
+ * Returns true on success.
+ * In any case, @lle is returned wlocked.
+ */
+bool
+nd6_try_set_entry_addr(struct ifnet *ifp, struct llentry *lle, char *lladdr)
+{
+	u_char linkhdr[LLE_MAX_LINKHDR];
+	size_t linkhdrsize;
+	int lladdr_off;
+
+	LLE_WLOCK_ASSERT(lle);
+
+	linkhdrsize = sizeof(linkhdr);
+	if (lltable_calc_llheader(ifp, AF_INET6, lladdr,
+	    linkhdr, &linkhdrsize, &lladdr_off) != 0) {
+		return (false);
+	}
+
+	if (!lltable_acquire_wlock(ifp, lle))
+		return (false);
+	lltable_set_entry_addr(ifp, lle, linkhdr, linkhdrsize, lladdr_off);
+	IF_AFDATA_WUNLOCK(ifp);
+
+	return (true);
+}
+
 /*
  * Free an nd6 llinfo entry.
  * Since the function would cause significant changes in the kernel, DO NOT
@@ -2027,14 +2056,9 @@
 		 * Record source link-layer address
 		 * XXX is it dependent to ifp->if_type?
 		 */
-		linkhdrsize = sizeof(linkhdr);
-		if (lltable_calc_llheader(ifp, AF_INET6, lladdr,
-		    linkhdr, &linkhdrsize, &lladdr_off) != 0)
-			return;
-
-		if (lltable_try_set_entry_addr(ifp, ln, linkhdr, linkhdrsize,
-		    lladdr_off) == 0) {
+		if (!nd6_try_set_entry_addr(ifp, ln, lladdr)) {
 			/* Entry was deleted */
+			LLE_WUNLOCK(ln);
 			return;
 		}
 
@@ -2257,6 +2281,39 @@
 	return (nd6_resolve_slow(ifp, 0, m, dst6, desten, pflags, plle));
 }
 
+/*
+ * Finds or creates a new llentry for @addr.
+ * Returns wlocked llentry or NULL.
+ */
+static __noinline struct llentry *
+nd6_get_llentry(struct ifnet *ifp, const struct in6_addr *addr)
+{
+	struct llentry *lle, *lle_tmp;
+
+	lle = nd6_alloc(addr, 0, ifp);
+	if (lle == NULL) {
+		char ip6buf[INET6_ADDRSTRLEN];
+		log(LOG_DEBUG,
+		    "nd6_get_llentry: can't allocate llinfo for %s "
+		    "(ln=%p)\n",
+		    ip6_sprintf(ip6buf, addr), lle);
+		return (NULL);
+	}
+
+	IF_AFDATA_WLOCK(ifp);
+	LLE_WLOCK(lle);
+	/* Prefer any existing entry over newly-created one */
+	lle_tmp = nd6_lookup(addr, LLE_EXCLUSIVE, ifp);
+	if (lle_tmp == NULL)
+		lltable_link_entry(LLTABLE6(ifp), lle);
+	IF_AFDATA_WUNLOCK(ifp);
+	if (lle_tmp != NULL) {
+		lltable_free_entry(LLTABLE6(ifp), lle);
+		return (lle_tmp);
+	} else
+		return (lle);
+}
+
 /*
  * Do L2 address resolution for @sa_dst address. Stores found
  * address in @desten buffer. Copy of lle ln_flags can be also
@@ -2273,7 +2330,7 @@
     const struct sockaddr_in6 *dst, u_char *desten, uint32_t *pflags,
     struct llentry **plle)
 {
-	struct llentry *lle = NULL, *lle_tmp;
+	struct llentry *lle = NULL;
 	struct in6_addr *psrc, src;
 	int send_ns, ll_len;
 	char *lladdr;
@@ -2286,39 +2343,16 @@
 	 * At this point, the destination of the packet must be a unicast
 	 * or an anycast address(i.e. not a multicast).
 	 */
-	if (lle == NULL) {
-		lle = nd6_lookup(&dst->sin6_addr, LLE_EXCLUSIVE, ifp);
-		if ((lle == NULL) && nd6_is_addr_neighbor(dst, ifp))  {
-			/*
-			 * Since nd6_is_addr_neighbor() internally calls nd6_lookup(),
-			 * the condition below is not very efficient.  But we believe
-			 * it is tolerable, because this should be a rare case.
-			 */
-			lle = nd6_alloc(&dst->sin6_addr, 0, ifp);
-			if (lle == NULL) {
-				char ip6buf[INET6_ADDRSTRLEN];
-				log(LOG_DEBUG,
-				    "nd6_output: can't allocate llinfo for %s "
-				    "(ln=%p)\n",
-				    ip6_sprintf(ip6buf, &dst->sin6_addr), lle);
-				m_freem(m);
-				return (ENOBUFS);
-			}
+	lle = nd6_lookup(&dst->sin6_addr, LLE_EXCLUSIVE, ifp);
+	if ((lle == NULL) && nd6_is_addr_neighbor(dst, ifp))  {
+		/*
+		 * Since nd6_is_addr_neighbor() internally calls nd6_lookup(),
+		 * the condition below is not very efficient.  But we believe
+		 * it is tolerable, because this should be a rare case.
+		 */
+		lle = nd6_get_llentry(ifp, &dst->sin6_addr);
+	}
 
-			IF_AFDATA_WLOCK(ifp);
-			LLE_WLOCK(lle);
-			/* Prefer any existing entry over newly-created one */
-			lle_tmp = nd6_lookup(&dst->sin6_addr, LLE_EXCLUSIVE, ifp);
-			if (lle_tmp == NULL)
-				lltable_link_entry(LLTABLE6(ifp), lle);
-			IF_AFDATA_WUNLOCK(ifp);
-			if (lle_tmp != NULL) {
-				lltable_free_entry(LLTABLE6(ifp), lle);
-				lle = lle_tmp;
-				lle_tmp = NULL;
-			}
-		}
-	} 
 	if (lle == NULL) {
 		m_freem(m);
 		return (ENOBUFS);
diff --git a/sys/netinet6/nd6_nbr.c b/sys/netinet6/nd6_nbr.c
--- a/sys/netinet6/nd6_nbr.c
+++ b/sys/netinet6/nd6_nbr.c
@@ -770,16 +770,9 @@
 		/*
 		 * Record link-layer address, and update the state.
 		 */
-		linkhdrsize = sizeof(linkhdr);
-		if (lltable_calc_llheader(ifp, AF_INET6, lladdr,
-		    linkhdr, &linkhdrsize, &lladdr_off) != 0)
-			return;
-
-		if (lltable_try_set_entry_addr(ifp, ln, linkhdr, linkhdrsize,
-		    lladdr_off) == 0) {
-			ln = NULL;
+		if (!nd6_try_set_entry_addr(ifp, ln, lladdr))
 			goto freeit;
-		}
+
 		EVENTHANDLER_INVOKE(lle_event, ln, LLENTRY_RESOLVED);
 		if (is_solicited)
 			nd6_llinfo_setstate(ln, ND6_LLINFO_REACHABLE);