Index: sys/netinet6/nd6.c
===================================================================
--- sys/netinet6/nd6.c
+++ sys/netinet6/nd6.c
@@ -1221,10 +1221,8 @@
 	struct nd_prefix *pr;
 	struct ifaddr *ifa;
 	struct rt_addrinfo info;
-	struct sockaddr_in6 rt_key;
+	struct sockaddr_dl gw;
 	const struct sockaddr *dst6;
-	uint64_t genid;
-	int error, fibnum;
 
 	/*
 	 * A link-local address is always a neighbor.
@@ -1249,9 +1247,8 @@
 			return (0);
 	}
 
-	bzero(&rt_key, sizeof(rt_key));
 	bzero(&info, sizeof(info));
-	info.rti_info[RTAX_DST] = (struct sockaddr *)&rt_key;
+	info.rti_info[RTAX_GATEWAY] = (struct sockaddr *)&gw;
 
 	/*
 	 * If the address matches one of our addresses,
@@ -1259,53 +1256,60 @@
 	 * If the address matches one of our on-link prefixes, it should be a
 	 * neighbor.
 	 */
-	ND6_RLOCK();
-restart:
-	LIST_FOREACH(pr, &V_nd_prefix, ndpr_entry) {
-		if (pr->ndpr_ifp != ifp)
-			continue;
 
-		if ((pr->ndpr_stateflags & NDPRF_ONLINK) == 0) {
-			dst6 = (const struct sockaddr *)&pr->ndpr_prefix;
+	/*
+	 * All on-link prefixes should be installed in the routing table for the
+	 * interface fib. Query routing table first to ensure deterministic
+	 * lookup time for the cases with large amount of on-link prefixes.
+	 */
+	dst6 = (const struct sockaddr *)addr;
+	if (rib_lookup_info(ifp->if_fib, dst6, 0, 0, &info) == 0) {
+		if (info.rti_ifp == ifp && (info.rti_flags & RTF_GATEWAY) == 0){
 
 			/*
-			 * We only need to check all FIBs if add_addr_allfibs
-			 * is unset. If set, checking any FIB will suffice.
+			 * Every prefix pointing to the right interface which
+			 *  does not contain gateway is eligible.
+			 * 
+			 * This covers both kernel-installed routes (RTF_PINNED)
+			 *  and user-installed routes (RTF_STATIC)
+			 *
+			 * Note that RTF_BLACKHOLE / RTF_REJECT would never point
+			 * to a non-loopback interface.
 			 */
-			fibnum = V_rt_add_addr_allfibs ? rt_numfibs - 1 : 0;
-			for (; fibnum < rt_numfibs; fibnum++) {
-				genid = V_nd6_list_genid;
-				ND6_RUNLOCK();
 
-				/*
-				 * Restore length field before
-				 * retrying lookup
-				 */
-				rt_key.sin6_len = sizeof(rt_key);
-				error = rib_lookup_info(fibnum, dst6, 0, 0,
-						        &info);
+			return (1);
+		}
 
-				ND6_RLOCK();
-				if (genid != V_nd6_list_genid)
-					goto restart;
-				if (error == 0)
-					break;
-			}
-			if (error != 0)
-				continue;
+		if (gw.sdl_family == AF_LINK && gw.sdl_index == ifp->if_index) {
 
 			/*
-			 * This is the case where multiple interfaces
-			 * have the same prefix, but only one is installed 
-			 * into the routing table and that prefix entry
-			 * is not the one being examined here. In the case
-			 * where RADIX_MPATH is enabled, multiple route
-			 * entries (of the same rt_key value) will be 
-			 * installed because the interface addresses all
-			 * differ.
+			 * Loopback route for the interface address from the
+			 * interface @ifp. Consider as a neighbor.
 			 */
-			if (!IN6_ARE_ADDR_EQUAL(&pr->ndpr_prefix.sin6_addr,
-			    &rt_key.sin6_addr))
+
+			return (1);
+		}
+	}
+
+	ND6_RLOCK();
+	LIST_FOREACH(pr, &V_nd_prefix, ndpr_entry) {
+		if (pr->ndpr_ifp != ifp)
+			continue;
+
+		if ((pr->ndpr_stateflags & NDPRF_ONLINK) == 0) {
+
+			/*
+			 * Prefix can be off-link either because
+			 * 1) it is not installed to the routing table
+			 *  because another prefix has been installed.
+			 * or
+			 * 2) prefix has expired but some addresses from
+			 *  this prefix are still in use.
+			 *
+			 * Consider prefix as valid if (2) is not the case.
+			 */
+			if (pr->ndpr_vltime != ND6_INFINITE_LIFETIME &&
+			    time_uptime >= pr->ndpr_lastupdate + pr->ndpr_vltime)
 				continue;
 		}
 
Index: tests/sys/netinet6/Makefile
===================================================================
--- tests/sys/netinet6/Makefile
+++ tests/sys/netinet6/Makefile
@@ -10,7 +10,8 @@
 				mld \
 				scapyi386 \
 				redirect \
-				divert
+				divert \
+				prefix_route_user
 
 ${PACKAGE}FILES+=		exthdr.py
 ${PACKAGE}FILES+=		mld.py
Index: tests/sys/netinet6/prefix_route_user.sh
===================================================================
--- /dev/null
+++ tests/sys/netinet6/prefix_route_user.sh
@@ -0,0 +1,97 @@
+#!/usr/bin/env atf-sh
+#-
+# SPDX-License-Identifier: BSD-2-Clause
+#
+# Copyright (c) 2020 Alexander V. Chernikov
+#
+# Redistribution and use in source and binary forms, with or without
+# modification, are permitted provided that the following conditions
+# are met:
+# 1. Redistributions of source code must retain the above copyright
+#    notice, this list of conditions and the following disclaimer.
+# 2. Redistributions in binary form must reproduce the above copyright
+#    notice, this list of conditions and the following disclaimer in the
+#    documentation and/or other materials provided with the distribution.
+#
+# THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
+# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+# ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
+# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+# SUCH DAMAGE.
+#
+# $FreeBSD
+#
+
+. $(atf_get_srcdir)/../common/vnet.subr
+
+atf_test_case "prefix_route_user" "cleanup"
+prefix_route_user_head() {
+
+	atf_set descr 'Test prefix route addition from userland'
+	atf_set require.user root
+}
+
+prefix_route_user_body() {
+
+	ids=65529
+	id=`printf "%x" ${ids}`
+	if [ $$ -gt 65535 ]; then
+		xl=`printf "%x" $(($$ - 65535))`
+		yl="1"
+	else
+		xl=`printf "%x" $$`
+		yl=""
+	fi
+
+	vnet_init
+
+	ip6a="2001:db8:6666:0000:${yl}:${id}:1:${xl}"
+	ip6b="2001:db8:6666:0000:${yl}:${id}:2:${xl}"
+
+	net6="2001:db8:6667::/64"
+	dst_addr6=`echo ${net6} | awk -F/ '{printf"%s4242", $1}'`
+
+	epair=$(vnet_mkepair)
+	ifconfig ${epair}a up
+	ifconfig ${epair}a inet6 ${ip6a}/64
+
+	jname="v6t-${id}-${yl}-${xl}"
+	vnet_mkjail ${jname} ${epair}b
+	jexec ${jname} ifconfig ${epair}b up
+	jexec ${jname} ifconfig ${epair}b inet6 ${ip6b}/64
+
+	# setup interface prefix
+	jexec ${jname} route add -6 -net ${net6} -iface ${epair}b
+
+	# wait for DAD to complete
+	while [ `jexec ${jname} ifconfig ${epair}b inet6 | grep -c tentative` -ne "0" ] ; do
+		sleep 0.2
+	done
+
+	# run ping6 to initiate ND entry creation
+	atf_check -s exit:2 -o ignore jexec ${jname} ping6 -c1 -X1 ${dst_addr6}
+
+	# Verify entry got created
+	count=`jexec ${jname} ndp -an | grep ${epair}b | grep -c ${dst_addr6}`
+	atf_check_equal "1" "${count}"
+}
+
+prefix_route_user_cleanup() {
+
+	vnet_cleanup
+}
+
+atf_init_test_cases()
+{
+
+	atf_add_test_case "prefix_route_user"
+}
+
+# end
+