// SPDX-License-Identifier: GPL-2.0-or-later
/*
 *      Linux INET6 implementation
 *      FIB front-end.
 *
 *      Authors:
 *      Pedro Roque             <roque@di.fc.ul.pt>
 */

/*      Changes:
 *
 *      YOSHIFUJI Hideaki @USAGI
 *              reworked default router selection.
 *              - respect outgoing interface
 *              - select from (probably) reachable routers (i.e.
 *              routers in REACHABLE, STALE, DELAY or PROBE states).
 *              - always select the same router if it is (probably)
 *              reachable.  otherwise, round-robin the list.
 *      Ville Nuorvala
 *              Fixed routing subtrees.
 */

#define pr_fmt(fmt) "IPv6: " fmt

#include <linux/capability.h>
#include <linux/errno.h>
#include <linux/export.h>
#include <linux/types.h>
#include <linux/times.h>
#include <linux/socket.h>
#include <linux/sockios.h>
#include <linux/net.h>
#include <linux/route.h>
#include <linux/netdevice.h>
#include <linux/in6.h>
#include <linux/mroute6.h>
#include <linux/init.h>
#include <linux/if_arp.h>
#include <linux/proc_fs.h>
#include <linux/seq_file.h>
#include <linux/nsproxy.h>
#include <linux/slab.h>
#include <linux/jhash.h>
#include <net/net_namespace.h>
#include <net/snmp.h>
#include <net/ipv6.h>
#include <net/ip6_fib.h>
#include <net/ip6_route.h>
#include <net/ndisc.h>
#include <net/addrconf.h>
#include <net/tcp.h>
#include <linux/rtnetlink.h>
#include <net/dst.h>
#include <net/dst_metadata.h>
#include <net/xfrm.h>
#include <net/netevent.h>
#include <net/netlink.h>
#include <net/rtnh.h>
#include <net/lwtunnel.h>
#include <net/ip_tunnels.h>
#include <net/l3mdev.h>
#include <net/ip.h>
#include <linux/uaccess.h>

#ifdef CONFIG_SYSCTL
#include <linux/sysctl.h>
#endif

static int ip6_rt_type_to_error(u8 fib6_type);

#define CREATE_TRACE_POINTS
#include <trace/events/fib6.h>
EXPORT_TRACEPOINT_SYMBOL_GPL(fib6_table_lookup);
#undef CREATE_TRACE_POINTS

enum rt6_nud_state {
        RT6_NUD_FAIL_HARD = -3,
        RT6_NUD_FAIL_PROBE = -2,
        RT6_NUD_FAIL_DO_RR = -1,
        RT6_NUD_SUCCEED = 1
};

static struct dst_entry *ip6_dst_check(struct dst_entry *dst, u32 cookie);
static unsigned int      ip6_default_advmss(const struct dst_entry *dst);
static unsigned int      ip6_mtu(const struct dst_entry *dst);
static struct dst_entry *ip6_negative_advice(struct dst_entry *);
static void             ip6_dst_destroy(struct dst_entry *);
static void             ip6_dst_ifdown(struct dst_entry *,
                                       struct net_device *dev, int how);
static int               ip6_dst_gc(struct dst_ops *ops);

static int              ip6_pkt_discard(struct sk_buff *skb);
static int              ip6_pkt_discard_out(struct net *net, struct sock *sk, struct sk_buff *skb);
static int              ip6_pkt_prohibit(struct sk_buff *skb);
static int              ip6_pkt_prohibit_out(struct net *net, struct sock *sk, struct sk_buff *skb);
static void             ip6_link_failure(struct sk_buff *skb);
static void             ip6_rt_update_pmtu(struct dst_entry *dst, struct sock *sk,
                                           struct sk_buff *skb, u32 mtu);
static void             rt6_do_redirect(struct dst_entry *dst, struct sock *sk,
                                        struct sk_buff *skb);
static int rt6_score_route(const struct fib6_nh *nh, u32 fib6_flags, int oif,
                           int strict);
static size_t rt6_nlmsg_size(struct fib6_info *f6i);
static int rt6_fill_node(struct net *net, struct sk_buff *skb,
                         struct fib6_info *rt, struct dst_entry *dst,
                         struct in6_addr *dest, struct in6_addr *src,
                         int iif, int type, u32 portid, u32 seq,
                         unsigned int flags);
static struct rt6_info *rt6_find_cached_rt(const struct fib6_result *res,
                                           const struct in6_addr *daddr,
                                           const struct in6_addr *saddr);

#ifdef CONFIG_IPV6_ROUTE_INFO
static struct fib6_info *rt6_add_route_info(struct net *net,
                                           const struct in6_addr *prefix, int prefixlen,
                                           const struct in6_addr *gwaddr,
                                           struct net_device *dev,
                                           unsigned int pref);
static struct fib6_info *rt6_get_route_info(struct net *net,
                                           const struct in6_addr *prefix, int prefixlen,
                                           const struct in6_addr *gwaddr,
                                           struct net_device *dev);
#endif

struct uncached_list {
        spinlock_t              lock;
        struct list_head        head;
};

static DEFINE_PER_CPU_ALIGNED(struct uncached_list, rt6_uncached_list);

void rt6_uncached_list_add(struct rt6_info *rt)
{
        struct uncached_list *ul = raw_cpu_ptr(&rt6_uncached_list);

        rt->rt6i_uncached_list = ul;

        spin_lock_bh(&ul->lock);
        list_add_tail(&rt->rt6i_uncached, &ul->head);
        spin_unlock_bh(&ul->lock);
}

void rt6_uncached_list_del(struct rt6_info *rt)
{
        if (!list_empty(&rt->rt6i_uncached)) {
                struct uncached_list *ul = rt->rt6i_uncached_list;
                struct net *net = dev_net(rt->dst.dev);

                spin_lock_bh(&ul->lock);
                list_del(&rt->rt6i_uncached);
                atomic_dec(&net->ipv6.rt6_stats->fib_rt_uncache);
                spin_unlock_bh(&ul->lock);
        }
}

static void rt6_uncached_list_flush_dev(struct net *net, struct net_device *dev)
{
        struct net_device *loopback_dev = net->loopback_dev;
        int cpu;

        if (dev == loopback_dev)
                return;

        for_each_possible_cpu(cpu) {
                struct uncached_list *ul = per_cpu_ptr(&rt6_uncached_list, cpu);
                struct rt6_info *rt;

                spin_lock_bh(&ul->lock);
                list_for_each_entry(rt, &ul->head, rt6i_uncached) {
                        struct inet6_dev *rt_idev = rt->rt6i_idev;
                        struct net_device *rt_dev = rt->dst.dev;

                        if (rt_idev->dev == dev) {
                                rt->rt6i_idev = in6_dev_get(loopback_dev);
                                in6_dev_put(rt_idev);
                        }

                        if (rt_dev == dev) {
                                rt->dst.dev = blackhole_netdev;
                                dev_hold(rt->dst.dev);
                                dev_put(rt_dev);
                        }
                }
                spin_unlock_bh(&ul->lock);
        }
}

static inline const void *choose_neigh_daddr(const struct in6_addr *p,
                                             struct sk_buff *skb,
                                             const void *daddr)
{
        if (!ipv6_addr_any(p))
                return (const void *) p;
        else if (skb)
                return &ipv6_hdr(skb)->daddr;
        return daddr;
}

struct neighbour *ip6_neigh_lookup(const struct in6_addr *gw,
                                   struct net_device *dev,
                                   struct sk_buff *skb,
                                   const void *daddr)
{
        struct neighbour *n;

        daddr = choose_neigh_daddr(gw, skb, daddr);
        n = __ipv6_neigh_lookup(dev, daddr);
        if (n)
                return n;

        n = neigh_create(&nd_tbl, daddr, dev);
        return IS_ERR(n) ? NULL : n;
}

static struct neighbour *ip6_dst_neigh_lookup(const struct dst_entry *dst,
                                              struct sk_buff *skb,
                                              const void *daddr)
{
        const struct rt6_info *rt = container_of(dst, struct rt6_info, dst);

        return ip6_neigh_lookup(rt6_nexthop(rt, &in6addr_any),
                                dst->dev, skb, daddr);
}

static void ip6_confirm_neigh(const struct dst_entry *dst, const void *daddr)
{
        struct net_device *dev = dst->dev;
        struct rt6_info *rt = (struct rt6_info *)dst;

        daddr = choose_neigh_daddr(rt6_nexthop(rt, &in6addr_any), NULL, daddr);
        if (!daddr)
                return;
        if (dev->flags & (IFF_NOARP | IFF_LOOPBACK))
                return;
        if (ipv6_addr_is_multicast((const struct in6_addr *)daddr))
                return;
        __ipv6_confirm_neigh(dev, daddr);
}

static struct dst_ops ip6_dst_ops_template = {
        .family                 =       AF_INET6,
        .gc                     =       ip6_dst_gc,
        .gc_thresh              =       1024,
        .check                  =       ip6_dst_check,
        .default_advmss         =       ip6_default_advmss,
        .mtu                    =       ip6_mtu,
        .cow_metrics            =       dst_cow_metrics_generic,
        .destroy                =       ip6_dst_destroy,
        .ifdown                 =       ip6_dst_ifdown,
        .negative_advice        =       ip6_negative_advice,
        .link_failure           =       ip6_link_failure,
        .update_pmtu            =       ip6_rt_update_pmtu,
        .redirect               =       rt6_do_redirect,
        .local_out              =       __ip6_local_out,
        .neigh_lookup           =       ip6_dst_neigh_lookup,
        .confirm_neigh          =       ip6_confirm_neigh,
};

static unsigned int ip6_blackhole_mtu(const struct dst_entry *dst)
{
        unsigned int mtu = dst_metric_raw(dst, RTAX_MTU);

        return mtu ? : dst->dev->mtu;
}

static void ip6_rt_blackhole_update_pmtu(struct dst_entry *dst, struct sock *sk,
                                         struct sk_buff *skb, u32 mtu)
{
}

static void ip6_rt_blackhole_redirect(struct dst_entry *dst, struct sock *sk,
                                      struct sk_buff *skb)
{
}

static struct dst_ops ip6_dst_blackhole_ops = {
        .family                 =       AF_INET6,
        .destroy                =       ip6_dst_destroy,
        .check                  =       ip6_dst_check,
        .mtu                    =       ip6_blackhole_mtu,
        .default_advmss         =       ip6_default_advmss,
        .update_pmtu            =       ip6_rt_blackhole_update_pmtu,
        .redirect               =       ip6_rt_blackhole_redirect,
        .cow_metrics            =       dst_cow_metrics_generic,
        .neigh_lookup           =       ip6_dst_neigh_lookup,
};

static const u32 ip6_template_metrics[RTAX_MAX] = {
        [RTAX_HOPLIMIT - 1] = 0,
};

static const struct fib6_info fib6_null_entry_template = {
        .fib6_flags     = (RTF_REJECT | RTF_NONEXTHOP),
        .fib6_protocol  = RTPROT_KERNEL,
        .fib6_metric    = ~(u32)0,
        .fib6_ref       = REFCOUNT_INIT(1),
        .fib6_type      = RTN_UNREACHABLE,
        .fib6_metrics   = (struct dst_metrics *)&dst_default_metrics,
};

static const struct rt6_info ip6_null_entry_template = {
        .dst = {
                .__refcnt       = ATOMIC_INIT(1),
                .__use          = 1,
                .obsolete       = DST_OBSOLETE_FORCE_CHK,
                .error          = -ENETUNREACH,
                .input          = ip6_pkt_discard,
                .output         = ip6_pkt_discard_out,
        },
        .rt6i_flags     = (RTF_REJECT | RTF_NONEXTHOP),
};

#ifdef CONFIG_IPV6_MULTIPLE_TABLES

static const struct rt6_info ip6_prohibit_entry_template = {
        .dst = {
                .__refcnt       = ATOMIC_INIT(1),
                .__use          = 1,
                .obsolete       = DST_OBSOLETE_FORCE_CHK,
                .error          = -EACCES,
                .input          = ip6_pkt_prohibit,
                .output         = ip6_pkt_prohibit_out,
        },
        .rt6i_flags     = (RTF_REJECT | RTF_NONEXTHOP),
};

static const struct rt6_info ip6_blk_hole_entry_template = {
        .dst = {
                .__refcnt       = ATOMIC_INIT(1),
                .__use          = 1,
                .obsolete       = DST_OBSOLETE_FORCE_CHK,
                .error          = -EINVAL,
                .input          = dst_discard,
                .output         = dst_discard_out,
        },
        .rt6i_flags     = (RTF_REJECT | RTF_NONEXTHOP),
};

#endif

static void rt6_info_init(struct rt6_info *rt)
{
        struct dst_entry *dst = &rt->dst;

        memset(dst + 1, 0, sizeof(*rt) - sizeof(*dst));
        INIT_LIST_HEAD(&rt->rt6i_uncached);
}

/* allocate dst with ip6_dst_ops */
struct rt6_info *ip6_dst_alloc(struct net *net, struct net_device *dev,
                               int flags)
{
        struct rt6_info *rt = dst_alloc(&net->ipv6.ip6_dst_ops, dev,
                                        1, DST_OBSOLETE_FORCE_CHK, flags);

        if (rt) {
                rt6_info_init(rt);
                atomic_inc(&net->ipv6.rt6_stats->fib_rt_alloc);
        }

        return rt;
}
EXPORT_SYMBOL(ip6_dst_alloc);

static void ip6_dst_destroy(struct dst_entry *dst)
{
        struct rt6_info *rt = (struct rt6_info *)dst;
        struct fib6_info *from;
        struct inet6_dev *idev;

        ip_dst_metrics_put(dst);
        rt6_uncached_list_del(rt);

        idev = rt->rt6i_idev;
        if (idev) {
                rt->rt6i_idev = NULL;
                in6_dev_put(idev);
        }

        from = xchg((__force struct fib6_info **)&rt->from, NULL);
        fib6_info_release(from);
}

static void ip6_dst_ifdown(struct dst_entry *dst, struct net_device *dev,
                           int how)
{
        struct rt6_info *rt = (struct rt6_info *)dst;
        struct inet6_dev *idev = rt->rt6i_idev;
        struct net_device *loopback_dev =
                dev_net(dev)->loopback_dev;

        if (idev && idev->dev != loopback_dev) {
                struct inet6_dev *loopback_idev = in6_dev_get(loopback_dev);
                if (loopback_idev) {
                        rt->rt6i_idev = loopback_idev;
                        in6_dev_put(idev);
                }
        }
}

static bool __rt6_check_expired(const struct rt6_info *rt)
{
        if (rt->rt6i_flags & RTF_EXPIRES)
                return time_after(jiffies, rt->dst.expires);
        else
                return false;
}

static bool rt6_check_expired(const struct rt6_info *rt)
{
        struct fib6_info *from;

        from = rcu_dereference(rt->from);

        if (rt->rt6i_flags & RTF_EXPIRES) {
                if (time_after(jiffies, rt->dst.expires))
                        return true;
        } else if (from) {
                return rt->dst.obsolete != DST_OBSOLETE_FORCE_CHK ||
                        fib6_check_expired(from);
        }
        return false;
}

void fib6_select_path(const struct net *net, struct fib6_result *res,
                      struct flowi6 *fl6, int oif, bool have_oif_match,
                      const struct sk_buff *skb, int strict)
{
        struct fib6_info *sibling, *next_sibling;
        struct fib6_info *match = res->f6i;

        if ((!match->fib6_nsiblings && !match->nh) || have_oif_match)
                goto out;

        /* We might have already computed the hash for ICMPv6 errors. In such
         * case it will always be non-zero. Otherwise now is the time to do it.
         */
        if (!fl6->mp_hash &&
            (!match->nh || nexthop_is_multipath(match->nh)))
                fl6->mp_hash = rt6_multipath_hash(net, fl6, skb, NULL);

        if (unlikely(match->nh)) {
                nexthop_path_fib6_result(res, fl6->mp_hash);
                return;
        }

        if (fl6->mp_hash <= atomic_read(&match->fib6_nh->fib_nh_upper_bound))
                goto out;

        list_for_each_entry_safe(sibling, next_sibling, &match->fib6_siblings,
                                 fib6_siblings) {
                const struct fib6_nh *nh = sibling->fib6_nh;
                int nh_upper_bound;

                nh_upper_bound = atomic_read(&nh->fib_nh_upper_bound);
                if (fl6->mp_hash > nh_upper_bound)
                        continue;
                if (rt6_score_route(nh, sibling->fib6_flags, oif, strict) < 0)
                        break;
                match = sibling;
                break;
        }

out:
        res->f6i = match;
        res->nh = match->fib6_nh;
}

/*
 *      Route lookup. rcu_read_lock() should be held.
 */

static bool __rt6_device_match(struct net *net, const struct fib6_nh *nh,
                               const struct in6_addr *saddr, int oif, int flags)
{
        const struct net_device *dev;

        if (nh->fib_nh_flags & RTNH_F_DEAD)
                return false;

        dev = nh->fib_nh_dev;
        if (oif) {
                if (dev->ifindex == oif)
                        return true;
        } else {
                if (ipv6_chk_addr(net, saddr, dev,
                                  flags & RT6_LOOKUP_F_IFACE))
                        return true;
        }

        return false;
}

struct fib6_nh_dm_arg {
        struct net              *net;
        const struct in6_addr   *saddr;
        int                     oif;
        int                     flags;
        struct fib6_nh          *nh;
};

static int __rt6_nh_dev_match(struct fib6_nh *nh, void *_arg)
{
        struct fib6_nh_dm_arg *arg = _arg;

        arg->nh = nh;
        return __rt6_device_match(arg->net, nh, arg->saddr, arg->oif,
                                  arg->flags);
}

/* returns fib6_nh from nexthop or NULL */
static struct fib6_nh *rt6_nh_dev_match(struct net *net, struct nexthop *nh,
                                        struct fib6_result *res,
                                        const struct in6_addr *saddr,
                                        int oif, int flags)
{
        struct fib6_nh_dm_arg arg = {
                .net   = net,
                .saddr = saddr,
                .oif   = oif,
                .flags = flags,
        };

        if (nexthop_is_blackhole(nh))
                return NULL;

        if (nexthop_for_each_fib6_nh(nh, __rt6_nh_dev_match, &arg))
                return arg.nh;

        return NULL;
}

static void rt6_device_match(struct net *net, struct fib6_result *res,
                             const struct in6_addr *saddr, int oif, int flags)
{
        struct fib6_info *f6i = res->f6i;
        struct fib6_info *spf6i;
        struct fib6_nh *nh;

        if (!oif && ipv6_addr_any(saddr)) {
                if (unlikely(f6i->nh)) {
                        nh = nexthop_fib6_nh(f6i->nh);
                        if (nexthop_is_blackhole(f6i->nh))
                                goto out_blackhole;
                } else {
                        nh = f6i->fib6_nh;
                }
                if (!(nh->fib_nh_flags & RTNH_F_DEAD))
                        goto out;
        }

        for (spf6i = f6i; spf6i; spf6i = rcu_dereference(spf6i->fib6_next)) {
                bool matched = false;

                if (unlikely(spf6i->nh)) {
                        nh = rt6_nh_dev_match(net, spf6i->nh, res, saddr,
                                              oif, flags);
                        if (nh)
                                matched = true;
                } else {
                        nh = spf6i->fib6_nh;
                        if (__rt6_device_match(net, nh, saddr, oif, flags))
                                matched = true;
                }
                if (matched) {
                        res->f6i = spf6i;
                        goto out;
                }
        }

        if (oif && flags & RT6_LOOKUP_F_IFACE) {
                res->f6i = net->ipv6.fib6_null_entry;
                nh = res->f6i->fib6_nh;
                goto out;
        }

        if (unlikely(f6i->nh)) {
                nh = nexthop_fib6_nh(f6i->nh);
                if (nexthop_is_blackhole(f6i->nh))
                        goto out_blackhole;
        } else {
                nh = f6i->fib6_nh;
        }

        if (nh->fib_nh_flags & RTNH_F_DEAD) {
                res->f6i = net->ipv6.fib6_null_entry;
                nh = res->f6i->fib6_nh;
        }
out:
        res->nh = nh;
        res->fib6_type = res->f6i->fib6_type;
        res->fib6_flags = res->f6i->fib6_flags;
        return;

out_blackhole:
        res->fib6_flags |= RTF_REJECT;
        res->fib6_type = RTN_BLACKHOLE;
        res->nh = nh;
}

#ifdef CONFIG_IPV6_ROUTER_PREF
struct __rt6_probe_work {
        struct work_struct work;
        struct in6_addr target;
        struct net_device *dev;
};

static void rt6_probe_deferred(struct work_struct *w)
{
        struct in6_addr mcaddr;
        struct __rt6_probe_work *work =
                container_of(w, struct __rt6_probe_work, work);

        addrconf_addr_solict_mult(&work->target, &mcaddr);
        ndisc_send_ns(work->dev, &work->target, &mcaddr, NULL, 0);
        dev_put(work->dev);
        kfree(work);
}

static void rt6_probe(struct fib6_nh *fib6_nh)
{
        struct __rt6_probe_work *work = NULL;
        const struct in6_addr *nh_gw;
        unsigned long last_probe;
        struct neighbour *neigh;
        struct net_device *dev;
        struct inet6_dev *idev;

        /*
         * Okay, this does not seem to be appropriate
         * for now, however, we need to check if it
         * is really so; aka Router Reachability Probing.
         *
         * Router Reachability Probe MUST be rate-limited
         * to no more than one per minute.
         */
        if (!fib6_nh->fib_nh_gw_family)
                return;

        nh_gw = &fib6_nh->fib_nh_gw6;
        dev = fib6_nh->fib_nh_dev;
        rcu_read_lock_bh();
        last_probe = READ_ONCE(fib6_nh->last_probe);
        idev = __in6_dev_get(dev);
        neigh = __ipv6_neigh_lookup_noref(dev, nh_gw);
        if (neigh) {
                if (neigh->nud_state & NUD_VALID)
                        goto out;

                write_lock(&neigh->lock);
                if (!(neigh->nud_state & NUD_VALID) &&
                    time_after(jiffies,
                               neigh->updated + idev->cnf.rtr_probe_interval)) {
                        work = kmalloc(sizeof(*work), GFP_ATOMIC);
                        if (work)
                                __neigh_set_probe_once(neigh);
                }
                write_unlock(&neigh->lock);
        } else if (time_after(jiffies, last_probe +
                                       idev->cnf.rtr_probe_interval)) {
                work = kmalloc(sizeof(*work), GFP_ATOMIC);
        }

        if (!work || cmpxchg(&fib6_nh->last_probe,
                             last_probe, jiffies) != last_probe) {
                kfree(work);
        } else {
                INIT_WORK(&work->work, rt6_probe_deferred);
                work->target = *nh_gw;
                dev_hold(dev);
                work->dev = dev;
                schedule_work(&work->work);
        }

out:
        rcu_read_unlock_bh();
}
#else
static inline void rt6_probe(struct fib6_nh *fib6_nh)
{
}
#endif

/*
 * Default Router Selection (RFC 2461 6.3.6)
 */
static enum rt6_nud_state rt6_check_neigh(const struct fib6_nh *fib6_nh)
{
        enum rt6_nud_state ret = RT6_NUD_FAIL_HARD;
        struct neighbour *neigh;

        rcu_read_lock_bh();
        neigh = __ipv6_neigh_lookup_noref(fib6_nh->fib_nh_dev,
                                          &fib6_nh->fib_nh_gw6);
        if (neigh) {
                read_lock(&neigh->lock);
                if (neigh->nud_state & NUD_VALID)
                        ret = RT6_NUD_SUCCEED;
#ifdef CONFIG_IPV6_ROUTER_PREF
                else if (!(neigh->nud_state & NUD_FAILED))
                        ret = RT6_NUD_SUCCEED;
                else
                        ret = RT6_NUD_FAIL_PROBE;
#endif
                read_unlock(&neigh->lock);
        } else {
                ret = IS_ENABLED(CONFIG_IPV6_ROUTER_PREF) ?
                      RT6_NUD_SUCCEED : RT6_NUD_FAIL_DO_RR;
        }
        rcu_read_unlock_bh();

        return ret;
}

static int rt6_score_route(const struct fib6_nh *nh, u32 fib6_flags, int oif,
                           int strict)
{
        int m = 0;

        if (!oif || nh->fib_nh_dev->ifindex == oif)
                m = 2;

        if (!m && (strict & RT6_LOOKUP_F_IFACE))
                return RT6_NUD_FAIL_HARD;
#ifdef CONFIG_IPV6_ROUTER_PREF
        m |= IPV6_DECODE_PREF(IPV6_EXTRACT_PREF(fib6_flags)) << 2;
#endif
        if ((strict & RT6_LOOKUP_F_REACHABLE) &&
            !(fib6_flags & RTF_NONEXTHOP) && nh->fib_nh_gw_family) {
                int n = rt6_check_neigh(nh);
                if (n < 0)
                        return n;
        }
        return m;
}

static bool find_match(struct fib6_nh *nh, u32 fib6_flags,
                       int oif, int strict, int *mpri, bool *do_rr)
{
        bool match_do_rr = false;
        bool rc = false;
        int m;

        if (nh->fib_nh_flags & RTNH_F_DEAD)
                goto out;

        if (ip6_ignore_linkdown(nh->fib_nh_dev) &&
            nh->fib_nh_flags & RTNH_F_LINKDOWN &&
            !(strict & RT6_LOOKUP_F_IGNORE_LINKSTATE))
                goto out;

        m = rt6_score_route(nh, fib6_flags, oif, strict);
        if (m == RT6_NUD_FAIL_DO_RR) {
                match_do_rr = true;
                m = 0; /* lowest valid score */
        } else if (m == RT6_NUD_FAIL_HARD) {
                goto out;
        }

        if (strict & RT6_LOOKUP_F_REACHABLE)
                rt6_probe(nh);

        /* note that m can be RT6_NUD_FAIL_PROBE at this point */
        if (m > *mpri) {
                *do_rr = match_do_rr;
                *mpri = m;
                rc = true;
        }
out:
        return rc;
}

struct fib6_nh_frl_arg {
        u32             flags;
        int             oif;
        int             strict;
        int             *mpri;
        bool            *do_rr;
        struct fib6_nh  *nh;
};

static int rt6_nh_find_match(struct fib6_nh *nh, void *_arg)
{
        struct fib6_nh_frl_arg *arg = _arg;

        arg->nh = nh;
        return find_match(nh, arg->flags, arg->oif, arg->strict,
                          arg->mpri, arg->do_rr);
}

static void __find_rr_leaf(struct fib6_info *f6i_start,
                           struct fib6_info *nomatch, u32 metric,
                           struct fib6_result *res, struct fib6_info **cont,
                           int oif, int strict, bool *do_rr, int *mpri)
{
        struct fib6_info *f6i;

        for (f6i = f6i_start;
             f6i && f6i != nomatch;
             f6i = rcu_dereference(f6i->fib6_next)) {
                bool matched = false;
                struct fib6_nh *nh;

                if (cont && f6i->fib6_metric != metric) {
                        *cont = f6i;
                        return;
                }

                if (fib6_check_expired(f6i))
                        continue;

                if (unlikely(f6i->nh)) {
                        struct fib6_nh_frl_arg arg = {
                                .flags  = f6i->fib6_flags,
                                .oif    = oif,
                                .strict = strict,
                                .mpri   = mpri,
                                .do_rr  = do_rr
                        };

                        if (nexthop_is_blackhole(f6i->nh)) {
                                res->fib6_flags = RTF_REJECT;
                                res->fib6_type = RTN_BLACKHOLE;
                                res->f6i = f6i;
                                res->nh = nexthop_fib6_nh(f6i->nh);
                                return;
                        }
                        if (nexthop_for_each_fib6_nh(f6i->nh, rt6_nh_find_match,
                                                     &arg)) {
                                matched = true;
                                nh = arg.nh;
                        }
                } else {
                        nh = f6i->fib6_nh;
                        if (find_match(nh, f6i->fib6_flags, oif, strict,
                                       mpri, do_rr))
                                matched = true;
                }
                if (matched) {
                        res->f6i = f6i;
                        res->nh = nh;
                        res->fib6_flags = f6i->fib6_flags;
                        res->fib6_type = f6i->fib6_type;
                }
        }
}

static void find_rr_leaf(struct fib6_node *fn, struct fib6_info *leaf,
                         struct fib6_info *rr_head, int oif, int strict,
                         bool *do_rr, struct fib6_result *res)
{
        u32 metric = rr_head->fib6_metric;
        struct fib6_info *cont = NULL;
        int mpri = -1;

        __find_rr_leaf(rr_head, NULL, metric, res, &cont,
                       oif, strict, do_rr, &mpri);

        __find_rr_leaf(leaf, rr_head, metric, res, &cont,
                       oif, strict, do_rr, &mpri);

        if (res->f6i || !cont)
                return;

        __find_rr_leaf(cont, NULL, metric, res, NULL,
                       oif, strict, do_rr, &mpri);
}

static void rt6_select(struct net *net, struct fib6_node *fn, int oif,
                       struct fib6_result *res, int strict)
{
        struct fib6_info *leaf = rcu_dereference(fn->leaf);
        struct fib6_info *rt0;
        bool do_rr = false;
        int key_plen;

        /* make sure this function or its helpers sets f6i */
        res->f6i = NULL;

        if (!leaf || leaf == net->ipv6.fib6_null_entry)
                goto out;

        rt0 = rcu_dereference(fn->rr_ptr);
        if (!rt0)
                rt0 = leaf;

        /* Double check to make sure fn is not an intermediate node
         * and fn->leaf does not points to its child's leaf
         * (This might happen if all routes under fn are deleted from
         * the tree and fib6_repair_tree() is called on the node.)
         */
        key_plen = rt0->fib6_dst.plen;
#ifdef CONFIG_IPV6_SUBTREES
        if (rt0->fib6_src.plen)
                key_plen = rt0->fib6_src.plen;
#endif
        if (fn->fn_bit != key_plen)
                goto out;

        find_rr_leaf(fn, leaf, rt0, oif, strict, &do_rr, res);
        if (do_rr) {
                struct fib6_info *next = rcu_dereference(rt0->fib6_next);

                /* no entries matched; do round-robin */
                if (!next || next->fib6_metric != rt0->fib6_metric)
                        next = leaf;

                if (next != rt0) {
                        spin_lock_bh(&leaf->fib6_table->tb6_lock);
                        /* make sure next is not being deleted from the tree */
                        if (next->fib6_node)
                                rcu_assign_pointer(fn->rr_ptr, next);
                        spin_unlock_bh(&leaf->fib6_table->tb6_lock);
                }
        }

out:
        if (!res->f6i) {
                res->f6i = net->ipv6.fib6_null_entry;
                res->nh = res->f6i->fib6_nh;
                res->fib6_flags = res->f6i->fib6_flags;
                res->fib6_type = res->f6i->fib6_type;
        }
}

static bool rt6_is_gw_or_nonexthop(const struct fib6_result *res)
{
        return (res->f6i->fib6_flags & RTF_NONEXTHOP) ||
               res->nh->fib_nh_gw_family;
}

#ifdef CONFIG_IPV6_ROUTE_INFO
int rt6_route_rcv(struct net_device *dev, u8 *opt, int len,
                  const struct in6_addr *gwaddr)
{
        struct net *net = dev_net(dev);
        struct route_info *rinfo = (struct route_info *) opt;
        struct in6_addr prefix_buf, *prefix;
        unsigned int pref;
        unsigned long lifetime;
        struct fib6_info *rt;

        if (len < sizeof(struct route_info)) {
                return -EINVAL;
        }

        /* Sanity check for prefix_len and length */
        if (rinfo->length > 3) {
                return -EINVAL;
        } else if (rinfo->prefix_len > 128) {
                return -EINVAL;
        } else if (rinfo->prefix_len > 64) {
                if (rinfo->length < 2) {
                        return -EINVAL;
                }
        } else if (rinfo->prefix_len > 0) {
                if (rinfo->length < 1) {
                        return -EINVAL;
                }
        }

        pref = rinfo->route_pref;
        if (pref == ICMPV6_ROUTER_PREF_INVALID)
                return -EINVAL;

        lifetime = addrconf_timeout_fixup(ntohl(rinfo->lifetime), HZ);

        if (rinfo->length == 3)
                prefix = (struct in6_addr *)rinfo->prefix;
        else {
                /* this function is safe */
                ipv6_addr_prefix(&prefix_buf,
                                 (struct in6_addr *)rinfo->prefix,
                                 rinfo->prefix_len);
                prefix = &prefix_buf;
        }

        if (rinfo->prefix_len == 0)
                rt = rt6_get_dflt_router(net, gwaddr, dev);
        else
                rt = rt6_get_route_info(net, prefix, rinfo->prefix_len,
                                        gwaddr, dev);

        if (rt && !lifetime) {
                ip6_del_rt(net, rt);
                rt = NULL;
        }

        if (!rt && lifetime)
                rt = rt6_add_route_info(net, prefix, rinfo->prefix_len, gwaddr,
                                        dev, pref);
        else if (rt)
                rt->fib6_flags = RTF_ROUTEINFO |
                                 (rt->fib6_flags & ~RTF_PREF_MASK) | RTF_PREF(pref);

        if (rt) {
                if (!addrconf_finite_timeout(lifetime))
                        fib6_clean_expires(rt);
                else
                        fib6_set_expires(rt, jiffies + HZ * lifetime);

                fib6_info_release(rt);
        }
        return 0;
}
#endif

/*
 *      Misc support functions
 */

/* called with rcu_lock held */
static struct net_device *ip6_rt_get_dev_rcu(const struct fib6_result *res)
{
        struct net_device *dev = res->nh->fib_nh_dev;

        if (res->fib6_flags & (RTF_LOCAL | RTF_ANYCAST)) {
                /* for copies of local routes, dst->dev needs to be the
                 * device if it is a master device, the master device if
                 * device is enslaved, and the loopback as the default
                 */
                if (netif_is_l3_slave(dev) &&
                    !rt6_need_strict(&res->f6i->fib6_dst.addr))
                        dev = l3mdev_master_dev_rcu(dev);
                else if (!netif_is_l3_master(dev))
                        dev = dev_net(dev)->loopback_dev;
                /* last case is netif_is_l3_master(dev) is true in which
                 * case we want dev returned to be dev
                 */
        }

        return dev;
}

static const int fib6_prop[RTN_MAX + 1] = {
        [RTN_UNSPEC]    = 0,
        [RTN_UNICAST]   = 0,
        [RTN_LOCAL]     = 0,
        [RTN_BROADCAST] = 0,
        [RTN_ANYCAST]   = 0,
        [RTN_MULTICAST] = 0,
        [RTN_BLACKHOLE] = -EINVAL,
        [RTN_UNREACHABLE] = -EHOSTUNREACH,
        [RTN_PROHIBIT]  = -EACCES,
        [RTN_THROW]     = -EAGAIN,
        [RTN_NAT]       = -EINVAL,
        [RTN_XRESOLVE]  = -EINVAL,
};

static int ip6_rt_type_to_error(u8 fib6_type)
{
        return fib6_prop[fib6_type];
}

static unsigned short fib6_info_dst_flags(struct fib6_info *rt)
{
        unsigned short flags = 0;

        if (rt->dst_nocount)
                flags |= DST_NOCOUNT;
        if (rt->dst_nopolicy)
                flags |= DST_NOPOLICY;
        if (rt->dst_host)
                flags |= DST_HOST;

        return flags;
}

static void ip6_rt_init_dst_reject(struct rt6_info *rt, u8 fib6_type)
{
        rt->dst.error = ip6_rt_type_to_error(fib6_type);

        switch (fib6_type) {
        case RTN_BLACKHOLE:
                rt->dst.output = dst_discard_out;
                rt->dst.input = dst_discard;
                break;
        case RTN_PROHIBIT:
                rt->dst.output = ip6_pkt_prohibit_out;
                rt->dst.input = ip6_pkt_prohibit;
                break;
        case RTN_THROW:
        case RTN_UNREACHABLE:
        default:
                rt->dst.output = ip6_pkt_discard_out;
                rt->dst.input = ip6_pkt_discard;
                break;
        }
}

static void ip6_rt_init_dst(struct rt6_info *rt, const struct fib6_result *res)
{
        struct fib6_info *f6i = res->f6i;

        if (res->fib6_flags & RTF_REJECT) {
                ip6_rt_init_dst_reject(rt, res->fib6_type);
                return;
        }

        rt->dst.error = 0;
        rt->dst.output = ip6_output;

        if (res->fib6_type == RTN_LOCAL || res->fib6_type == RTN_ANYCAST) {
                rt->dst.input = ip6_input;
        } else if (ipv6_addr_type(&f6i->fib6_dst.addr) & IPV6_ADDR_MULTICAST) {
                rt->dst.input = ip6_mc_input;
        } else {
                rt->dst.input = ip6_forward;
        }

        if (res->nh->fib_nh_lws) {
                rt->dst.lwtstate = lwtstate_get(res->nh->fib_nh_lws);
                lwtunnel_set_redirect(&rt->dst);
        }

        rt->dst.lastuse = jiffies;
}

/* Caller must already hold reference to @from */
static void rt6_set_from(struct rt6_info *rt, struct fib6_info *from)
{
        rt->rt6i_flags &= ~RTF_EXPIRES;
        rcu_assign_pointer(rt->from, from);
        ip_dst_init_metrics(&rt->dst, from->fib6_metrics);
}

/* Caller must already hold reference to f6i in result */
static void ip6_rt_copy_init(struct rt6_info *rt, const struct fib6_result *res)
{
        const struct fib6_nh *nh = res->nh;
        const struct net_device *dev = nh->fib_nh_dev;
        struct fib6_info *f6i = res->f6i;

        ip6_rt_init_dst(rt, res);

        rt->rt6i_dst = f6i->fib6_dst;
        rt->rt6i_idev = dev ? in6_dev_get(dev) : NULL;
        rt->rt6i_flags = res->fib6_flags;
        if (nh->fib_nh_gw_family) {
                rt->rt6i_gateway = nh->fib_nh_gw6;
                rt->rt6i_flags |= RTF_GATEWAY;
        }
        rt6_set_from(rt, f6i);
#ifdef CONFIG_IPV6_SUBTREES
        rt->rt6i_src = f6i->fib6_src;
#endif
}

static struct fib6_node* fib6_backtrack(struct fib6_node *fn,
                                        struct in6_addr *saddr)
{
        struct fib6_node *pn, *sn;
        while (1) {
                if (fn->fn_flags & RTN_TL_ROOT)
                        return NULL;
                pn = rcu_dereference(fn->parent);
                sn = FIB6_SUBTREE(pn);
                if (sn && sn != fn)
                        fn = fib6_node_lookup(sn, NULL, saddr);
                else
                        fn = pn;
                if (fn->fn_flags & RTN_RTINFO)
                        return fn;
        }
}

static bool ip6_hold_safe(struct net *net, struct rt6_info **prt)
{
        struct rt6_info *rt = *prt;

        if (dst_hold_safe(&rt->dst))
                return true;
        if (net) {
                rt = net->ipv6.ip6_null_entry;
                dst_hold(&rt->dst);
        } else {
                rt = NULL;
        }
        *prt = rt;
        return false;
}

/* called with rcu_lock held */
static struct rt6_info *ip6_create_rt_rcu(const struct fib6_result *res)
{
        struct net_device *dev = res->nh->fib_nh_dev;
        struct fib6_info *f6i = res->f6i;
        unsigned short flags;
        struct rt6_info *nrt;

        if (!fib6_info_hold_safe(f6i))
                goto fallback;

        flags = fib6_info_dst_flags(f6i);
        nrt = ip6_dst_alloc(dev_net(dev), dev, flags);
        if (!nrt) {
                fib6_info_release(f6i);
                goto fallback;
        }

        ip6_rt_copy_init(nrt, res);
        return nrt;

fallback:
        nrt = dev_net(dev)->ipv6.ip6_null_entry;
        dst_hold(&nrt->dst);
        return nrt;
}

static struct rt6_info *ip6_pol_route_lookup(struct net *net,
                                             struct fib6_table *table,
                                             struct flowi6 *fl6,
                                             const struct sk_buff *skb,
                                             int flags)
{
        struct fib6_result res = {};
        struct fib6_node *fn;
        struct rt6_info *rt;

        if (fl6->flowi6_flags & FLOWI_FLAG_SKIP_NH_OIF)
                flags &= ~RT6_LOOKUP_F_IFACE;

        rcu_read_lock();
        fn = fib6_node_lookup(&table->tb6_root, &fl6->daddr, &fl6->saddr);
restart:
        res.f6i = rcu_dereference(fn->leaf);
        if (!res.f6i)
                res.f6i = net->ipv6.fib6_null_entry;
        else
                rt6_device_match(net, &res, &fl6->saddr, fl6->flowi6_oif,
                                 flags);

        if (res.f6i == net->ipv6.fib6_null_entry) {
                fn = fib6_backtrack(fn, &fl6->saddr);
                if (fn)
                        goto restart;

                rt = net->ipv6.ip6_null_entry;
                dst_hold(&rt->dst);
                goto out;
        } else if (res.fib6_flags & RTF_REJECT) {
                goto do_create;
        }

        fib6_select_path(net, &res, fl6, fl6->flowi6_oif,
                         fl6->flowi6_oif != 0, skb, flags);

        /* Search through exception table */
        rt = rt6_find_cached_rt(&res, &fl6->daddr, &fl6->saddr);
        if (rt) {
                if (ip6_hold_safe(net, &rt))
                        dst_use_noref(&rt->dst, jiffies);
        } else {
do_create:
                rt = ip6_create_rt_rcu(&res);
        }

out:
        trace_fib6_table_lookup(net, &res, table, fl6);

        rcu_read_unlock();

        return rt;
}

struct dst_entry *ip6_route_lookup(struct net *net, struct flowi6 *fl6,
                                   const struct sk_buff *skb, int flags)
{
        return fib6_rule_lookup(net, fl6, skb, flags, ip6_pol_route_lookup);
}
EXPORT_SYMBOL_GPL(ip6_route_lookup);

struct rt6_info *rt6_lookup(struct net *net, const struct in6_addr *daddr,
                            const struct in6_addr *saddr, int oif,
                            const struct sk_buff *skb, int strict)
{
        struct flowi6 fl6 = {
                .flowi6_oif = oif,
                .daddr = *daddr,
        };
        struct dst_entry *dst;
        int flags = strict ? RT6_LOOKUP_F_IFACE : 0;

        if (saddr) {
                memcpy(&fl6.saddr, saddr, sizeof(*saddr));
                flags |= RT6_LOOKUP_F_HAS_SADDR;
        }

        dst = fib6_rule_lookup(net, &fl6, skb, flags, ip6_pol_route_lookup);
        if (dst->error == 0)
                return (struct rt6_info *) dst;

        dst_release(dst);

        return NULL;
}
EXPORT_SYMBOL(rt6_lookup);

/* ip6_ins_rt is called with FREE table->tb6_lock.
 * It takes new route entry, the addition fails by any reason the
 * route is released.
 * Caller must hold dst before calling it.
 */

static int __ip6_ins_rt(struct fib6_info *rt, struct nl_info *info,
                        struct netlink_ext_ack *extack)
{
        int err;
        struct fib6_table *table;

        table = rt->fib6_table;
        spin_lock_bh(&table->tb6_lock);
        err = fib6_add(&table->tb6_root, rt, info, extack);
        spin_unlock_bh(&table->tb6_lock);

        return err;
}

int ip6_ins_rt(struct net *net, struct fib6_info *rt)
{
        struct nl_info info = { .nl_net = net, };

        return __ip6_ins_rt(rt, &info, NULL);
}

static struct rt6_info *ip6_rt_cache_alloc(const struct fib6_result *res,
                                           const struct in6_addr *daddr,
                                           const struct in6_addr *saddr)
{
        struct fib6_info *f6i = res->f6i;
        struct net_device *dev;
        struct rt6_info *rt;

        /*
         *      Clone the route.
         */

        if (!fib6_info_hold_safe(f6i))
                return NULL;

        dev = ip6_rt_get_dev_rcu(res);
        rt = ip6_dst_alloc(dev_net(dev), dev, 0);
        if (!rt) {
                fib6_info_release(f6i);
                return NULL;
        }

        ip6_rt_copy_init(rt, res);
        rt->rt6i_flags |= RTF_CACHE;
        rt->dst.flags |= DST_HOST;
        rt->rt6i_dst.addr = *daddr;
        rt->rt6i_dst.plen = 128;

        if (!rt6_is_gw_or_nonexthop(res)) {
                if (f6i->fib6_dst.plen != 128 &&
                    ipv6_addr_equal(&f6i->fib6_dst.addr, daddr))
                        rt->rt6i_flags |= RTF_ANYCAST;
#ifdef CONFIG_IPV6_SUBTREES
                if (rt->rt6i_src.plen && saddr) {
                        rt->rt6i_src.addr = *saddr;
                        rt->rt6i_src.plen = 128;
                }
#endif
        }

        return rt;
}

static struct rt6_info *ip6_rt_pcpu_alloc(const struct fib6_result *res)
{
        struct fib6_info *f6i = res->f6i;
        unsigned short flags = fib6_info_dst_flags(f6i);
        struct net_device *dev;
        struct rt6_info *pcpu_rt;

        if (!fib6_info_hold_safe(f6i))
                return NULL;

        rcu_read_lock();
        dev = ip6_rt_get_dev_rcu(res);
        pcpu_rt = ip6_dst_alloc(dev_net(dev), dev, flags);
        rcu_read_unlock();
        if (!pcpu_rt) {
                fib6_info_release(f6i);
                return NULL;
        }
        ip6_rt_copy_init(pcpu_rt, res);
        pcpu_rt->rt6i_flags |= RTF_PCPU;
        return pcpu_rt;
}

/* It should be called with rcu_read_lock() acquired */
static struct rt6_info *rt6_get_pcpu_route(const struct fib6_result *res)
{
        struct rt6_info *pcpu_rt;

        pcpu_rt = this_cpu_read(*res->nh->rt6i_pcpu);

        return pcpu_rt;
}

static struct rt6_info *rt6_make_pcpu_route(struct net *net,
                                            const struct fib6_result *res)
{
        struct rt6_info *pcpu_rt, *prev, **p;

        pcpu_rt = ip6_rt_pcpu_alloc(res);
        if (!pcpu_rt)
                return NULL;

        p = this_cpu_ptr(res->nh->rt6i_pcpu);
        prev = cmpxchg(p, NULL, pcpu_rt);
        BUG_ON(prev);

        if (res->f6i->fib6_destroying) {
                struct fib6_info *from;

                from = xchg((__force struct fib6_info **)&pcpu_rt->from, NULL);
                fib6_info_release(from);
        }

        return pcpu_rt;
}

/* exception hash table implementation
 */
static DEFINE_SPINLOCK(rt6_exception_lock);

/* Remove rt6_ex from hash table and free the memory
 * Caller must hold rt6_exception_lock
 */
static void rt6_remove_exception(struct rt6_exception_bucket *bucket,
                                 struct rt6_exception *rt6_ex)
{
        struct fib6_info *from;
        struct net *net;

        if (!bucket || !rt6_ex)
                return;

        net = dev_net(rt6_ex->rt6i->dst.dev);
        net->ipv6.rt6_stats->fib_rt_cache--;

        /* purge completely the exception to allow releasing the held resources:
         * some [sk] cache may keep the dst around for unlimited time
         */
        from = xchg((__force struct fib6_info **)&rt6_ex->rt6i->from, NULL);
        fib6_info_release(from);
        dst_dev_put(&rt6_ex->rt6i->dst);

        hlist_del_rcu(&rt6_ex->hlist);
        dst_release(&rt6_ex->rt6i->dst);
        kfree_rcu(rt6_ex, rcu);
        WARN_ON_ONCE(!bucket->depth);
        bucket->depth--;
}

/* Remove oldest rt6_ex in bucket and free the memory
 * Caller must hold rt6_exception_lock
 */
static void rt6_exception_remove_oldest(struct rt6_exception_bucket *bucket)
{
        struct rt6_exception *rt6_ex, *oldest = NULL;

        if (!bucket)
                return;

        hlist_for_each_entry(rt6_ex, &bucket->chain, hlist) {
                if (!oldest || time_before(rt6_ex->stamp, oldest->stamp))
                        oldest = rt6_ex;
        }
        rt6_remove_exception(bucket, oldest);
}

static u32 rt6_exception_hash(const struct in6_addr *dst,
                              const struct in6_addr *src)
{
        static u32 seed __read_mostly;
        u32 val;

        net_get_random_once(&seed, sizeof(seed));
        val = jhash(dst, sizeof(*dst), seed);

#ifdef CONFIG_IPV6_SUBTREES
        if (src)
                val = jhash(src, sizeof(*src), val);
#endif
        return hash_32(val, FIB6_EXCEPTION_BUCKET_SIZE_SHIFT);
}

/* Helper function to find the cached rt in the hash table
 * and update bucket pointer to point to the bucket for this
 * (daddr, saddr) pair
 * Caller must hold rt6_exception_lock
 */
static struct rt6_exception *
__rt6_find_exception_spinlock(struct rt6_exception_bucket **bucket,
                              const struct in6_addr *daddr,
                              const struct in6_addr *saddr)
{
        struct rt6_exception *rt6_ex;
        u32 hval;

        if (!(*bucket) || !daddr)
                return NULL;

        hval = rt6_exception_hash(daddr, saddr);
        *bucket += hval;

        hlist_for_each_entry(rt6_ex, &(*bucket)->chain, hlist) {
                struct rt6_info *rt6 = rt6_ex->rt6i;
                bool matched = ipv6_addr_equal(daddr, &rt6->rt6i_dst.addr);

#ifdef CONFIG_IPV6_SUBTREES
                if (matched && saddr)
                        matched = ipv6_addr_equal(saddr, &rt6->rt6i_src.addr);
#endif
                if (matched)
                        return rt6_ex;
        }
        return NULL;
}

/* Helper function to find the cached rt in the hash table
 * and update bucket pointer to point to the bucket for this
 * (daddr, saddr) pair
 * Caller must hold rcu_read_lock()
 */
static struct rt6_exception *
__rt6_find_exception_rcu(struct rt6_exception_bucket **bucket,
                         const struct in6_addr *daddr,
                         const struct in6_addr *saddr)
{
        struct rt6_exception *rt6_ex;
        u32 hval;

        WARN_ON_ONCE(!rcu_read_lock_held());

        if (!(*bucket) || !daddr)
                return NULL;

        hval = rt6_exception_hash(daddr, saddr);
        *bucket += hval;

        hlist_for_each_entry_rcu(rt6_ex, &(*bucket)->chain, hlist) {
                struct rt6_info *rt6 = rt6_ex->rt6i;
                bool matched = ipv6_addr_equal(daddr, &rt6->rt6i_dst.addr);

#ifdef CONFIG_IPV6_SUBTREES
                if (matched && saddr)
                        matched = ipv6_addr_equal(saddr, &rt6->rt6i_src.addr);
#endif
                if (matched)
                        return rt6_ex;
        }
        return NULL;
}

static unsigned int fib6_mtu(const struct fib6_result *res)
{
        const struct fib6_nh *nh = res->nh;
        unsigned int mtu;

        if (res->f6i->fib6_pmtu) {
                mtu = res->f6i->fib6_pmtu;
        } else {
                struct net_device *dev = nh->fib_nh_dev;
                struct inet6_dev *idev;

                rcu_read_lock();
                idev = __in6_dev_get(dev);
                mtu = idev->cnf.mtu6;
                rcu_read_unlock();
        }

        mtu = min_t(unsigned int, mtu, IP6_MAX_MTU);

        return mtu - lwtunnel_headroom(nh->fib_nh_lws, mtu);
}

#define FIB6_EXCEPTION_BUCKET_FLUSHED  0x1UL

/* used when the flushed bit is not relevant, only access to the bucket
 * (ie., all bucket users except rt6_insert_exception);
 *
 * called under rcu lock; sometimes called with rt6_exception_lock held
 */
static
struct rt6_exception_bucket *fib6_nh_get_excptn_bucket(const struct fib6_nh *nh,
                                                       spinlock_t *lock)
{
        struct rt6_exception_bucket *bucket;

        if (lock)
                bucket = rcu_dereference_protected(nh->rt6i_exception_bucket,
                                                   lockdep_is_held(lock));
        else
                bucket = rcu_dereference(nh->rt6i_exception_bucket);

        /* remove bucket flushed bit if set */
        if (bucket) {
                unsigned long p = (unsigned long)bucket;

                p &= ~FIB6_EXCEPTION_BUCKET_FLUSHED;
                bucket = (struct rt6_exception_bucket *)p;
        }

        return bucket;
}

static bool fib6_nh_excptn_bucket_flushed(struct rt6_exception_bucket *bucket)
{
        unsigned long p = (unsigned long)bucket;

        return !!(p & FIB6_EXCEPTION_BUCKET_FLUSHED);
}

/* called with rt6_exception_lock held */
static void fib6_nh_excptn_bucket_set_flushed(struct fib6_nh *nh,
                                              spinlock_t *lock)
{
        struct rt6_exception_bucket *bucket;
        unsigned long p;

        bucket = rcu_dereference_protected(nh->rt6i_exception_bucket,
                                           lockdep_is_held(lock));

        p = (unsigned long)bucket;
        p |= FIB6_EXCEPTION_BUCKET_FLUSHED;
        bucket = (struct rt6_exception_bucket *)p;
        rcu_assign_pointer(nh->rt6i_exception_bucket, bucket);
}

static int rt6_insert_exception(struct rt6_info *nrt,
                                const struct fib6_result *res)
{
        struct net *net = dev_net(nrt->dst.dev);
        struct rt6_exception_bucket *bucket;
        struct fib6_info *f6i = res->f6i;
        struct in6_addr *src_key = NULL;
        struct rt6_exception *rt6_ex;
        struct fib6_nh *nh = res->nh;
        int err = 0;

        spin_lock_bh(&rt6_exception_lock);

        bucket = rcu_dereference_protected(nh->rt6i_exception_bucket,
                                          lockdep_is_held(&rt6_exception_lock));
        if (!bucket) {
                bucket = kcalloc(FIB6_EXCEPTION_BUCKET_SIZE, sizeof(*bucket),
                                 GFP_ATOMIC);
                if (!bucket) {
                        err = -ENOMEM;
                        goto out;
                }
                rcu_assign_pointer(nh->rt6i_exception_bucket, bucket);
        } else if (fib6_nh_excptn_bucket_flushed(bucket)) {
                err = -EINVAL;
                goto out;
        }

#ifdef CONFIG_IPV6_SUBTREES
        /* fib6_src.plen != 0 indicates f6i is in subtree
         * and exception table is indexed by a hash of
         * both fib6_dst and fib6_src.
         * Otherwise, the exception table is indexed by
         * a hash of only fib6_dst.
         */
        if (f6i->fib6_src.plen)
                src_key = &nrt->rt6i_src.addr;
#endif
        /* rt6_mtu_change() might lower mtu on f6i.
         * Only insert this exception route if its mtu
         * is less than f6i's mtu value.
         */
        if (dst_metric_raw(&nrt->dst, RTAX_MTU) >= fib6_mtu(res)) {
                err = -EINVAL;
                goto out;
        }

        rt6_ex = __rt6_find_exception_spinlock(&bucket, &nrt->rt6i_dst.addr,
                                               src_key);
        if (rt6_ex)
                rt6_remove_exception(bucket, rt6_ex);

        rt6_ex = kzalloc(sizeof(*rt6_ex), GFP_ATOMIC);
        if (!rt6_ex) {
                err = -ENOMEM;
                goto out;
        }
        rt6_ex->rt6i = nrt;
        rt6_ex->stamp = jiffies;
        hlist_add_head_rcu(&rt6_ex->hlist, &bucket->chain);
        bucket->depth++;
        net->ipv6.rt6_stats->fib_rt_cache++;

        if (bucket->depth > FIB6_MAX_DEPTH)
                rt6_exception_remove_oldest(bucket);

out:
        spin_unlock_bh(&rt6_exception_lock);

        /* Update fn->fn_sernum to invalidate all cached dst */
        if (!err) {
                spin_lock_bh(&f6i->fib6_table->tb6_lock);
                fib6_update_sernum(net, f6i);
                spin_unlock_bh(&f6i->fib6_table->tb6_lock);
                fib6_force_start_gc(net);
        }

        return err;
}

static void fib6_nh_flush_exceptions(struct fib6_nh *nh, struct fib6_info *from)
{
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;
        struct hlist_node *tmp;
        int i;

        spin_lock_bh(&rt6_exception_lock);

        bucket = fib6_nh_get_excptn_bucket(nh, &rt6_exception_lock);
        if (!bucket)
                goto out;

        /* Prevent rt6_insert_exception() to recreate the bucket list */
        if (!from)
                fib6_nh_excptn_bucket_set_flushed(nh, &rt6_exception_lock);

        for (i = 0; i < FIB6_EXCEPTION_BUCKET_SIZE; i++) {
                hlist_for_each_entry_safe(rt6_ex, tmp, &bucket->chain, hlist) {
                        if (!from ||
                            rcu_access_pointer(rt6_ex->rt6i->from) == from)
                                rt6_remove_exception(bucket, rt6_ex);
                }
                WARN_ON_ONCE(!from && bucket->depth);
                bucket++;
        }
out:
        spin_unlock_bh(&rt6_exception_lock);
}

static int rt6_nh_flush_exceptions(struct fib6_nh *nh, void *arg)
{
        struct fib6_info *f6i = arg;

        fib6_nh_flush_exceptions(nh, f6i);

        return 0;
}

void rt6_flush_exceptions(struct fib6_info *f6i)
{
        if (f6i->nh)
                nexthop_for_each_fib6_nh(f6i->nh, rt6_nh_flush_exceptions,
                                         f6i);
        else
                fib6_nh_flush_exceptions(f6i->fib6_nh, f6i);
}

/* Find cached rt in the hash table inside passed in rt
 * Caller has to hold rcu_read_lock()
 */
static struct rt6_info *rt6_find_cached_rt(const struct fib6_result *res,
                                           const struct in6_addr *daddr,
                                           const struct in6_addr *saddr)
{
        const struct in6_addr *src_key = NULL;
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;
        struct rt6_info *ret = NULL;

#ifdef CONFIG_IPV6_SUBTREES
        /* fib6i_src.plen != 0 indicates f6i is in subtree
         * and exception table is indexed by a hash of
         * both fib6_dst and fib6_src.
         * However, the src addr used to create the hash
         * might not be exactly the passed in saddr which
         * is a /128 addr from the flow.
         * So we need to use f6i->fib6_src to redo lookup
         * if the passed in saddr does not find anything.
         * (See the logic in ip6_rt_cache_alloc() on how
         * rt->rt6i_src is updated.)
         */
        if (res->f6i->fib6_src.plen)
                src_key = saddr;
find_ex:
#endif
        bucket = fib6_nh_get_excptn_bucket(res->nh, NULL);
        rt6_ex = __rt6_find_exception_rcu(&bucket, daddr, src_key);

        if (rt6_ex && !rt6_check_expired(rt6_ex->rt6i))
                ret = rt6_ex->rt6i;

#ifdef CONFIG_IPV6_SUBTREES
        /* Use fib6_src as src_key and redo lookup */
        if (!ret && src_key && src_key != &res->f6i->fib6_src.addr) {
                src_key = &res->f6i->fib6_src.addr;
                goto find_ex;
        }
#endif

        return ret;
}

/* Remove the passed in cached rt from the hash table that contains it */
static int fib6_nh_remove_exception(const struct fib6_nh *nh, int plen,
                                    const struct rt6_info *rt)
{
        const struct in6_addr *src_key = NULL;
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;
        int err;

        if (!rcu_access_pointer(nh->rt6i_exception_bucket))
                return -ENOENT;

        spin_lock_bh(&rt6_exception_lock);
        bucket = fib6_nh_get_excptn_bucket(nh, &rt6_exception_lock);

#ifdef CONFIG_IPV6_SUBTREES
        /* rt6i_src.plen != 0 indicates 'from' is in subtree
         * and exception table is indexed by a hash of
         * both rt6i_dst and rt6i_src.
         * Otherwise, the exception table is indexed by
         * a hash of only rt6i_dst.
         */
        if (plen)
                src_key = &rt->rt6i_src.addr;
#endif
        rt6_ex = __rt6_find_exception_spinlock(&bucket,
                                               &rt->rt6i_dst.addr,
                                               src_key);
        if (rt6_ex) {
                rt6_remove_exception(bucket, rt6_ex);
                err = 0;
        } else {
                err = -ENOENT;
        }

        spin_unlock_bh(&rt6_exception_lock);
        return err;
}

struct fib6_nh_excptn_arg {
        struct rt6_info *rt;
        int             plen;
};

static int rt6_nh_remove_exception_rt(struct fib6_nh *nh, void *_arg)
{
        struct fib6_nh_excptn_arg *arg = _arg;
        int err;

        err = fib6_nh_remove_exception(nh, arg->plen, arg->rt);
        if (err == 0)
                return 1;

        return 0;
}

static int rt6_remove_exception_rt(struct rt6_info *rt)
{
        struct fib6_info *from;

        from = rcu_dereference(rt->from);
        if (!from || !(rt->rt6i_flags & RTF_CACHE))
                return -EINVAL;

        if (from->nh) {
                struct fib6_nh_excptn_arg arg = {
                        .rt = rt,
                        .plen = from->fib6_src.plen
                };
                int rc;

                /* rc = 1 means an entry was found */
                rc = nexthop_for_each_fib6_nh(from->nh,
                                              rt6_nh_remove_exception_rt,
                                              &arg);
                return rc ? 0 : -ENOENT;
        }

        return fib6_nh_remove_exception(from->fib6_nh,
                                        from->fib6_src.plen, rt);
}

/* Find rt6_ex which contains the passed in rt cache and
 * refresh its stamp
 */
static void fib6_nh_update_exception(const struct fib6_nh *nh, int plen,
                                     const struct rt6_info *rt)
{
        const struct in6_addr *src_key = NULL;
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;

        bucket = fib6_nh_get_excptn_bucket(nh, NULL);
#ifdef CONFIG_IPV6_SUBTREES
        /* rt6i_src.plen != 0 indicates 'from' is in subtree
         * and exception table is indexed by a hash of
         * both rt6i_dst and rt6i_src.
         * Otherwise, the exception table is indexed by
         * a hash of only rt6i_dst.
         */
        if (plen)
                src_key = &rt->rt6i_src.addr;
#endif
        rt6_ex = __rt6_find_exception_rcu(&bucket, &rt->rt6i_dst.addr, src_key);
        if (rt6_ex)
                rt6_ex->stamp = jiffies;
}

struct fib6_nh_match_arg {
        const struct net_device *dev;
        const struct in6_addr   *gw;
        struct fib6_nh          *match;
};

/* determine if fib6_nh has given device and gateway */
static int fib6_nh_find_match(struct fib6_nh *nh, void *_arg)
{
        struct fib6_nh_match_arg *arg = _arg;

        if (arg->dev != nh->fib_nh_dev ||
            (arg->gw && !nh->fib_nh_gw_family) ||
            (!arg->gw && nh->fib_nh_gw_family) ||
            (arg->gw && !ipv6_addr_equal(arg->gw, &nh->fib_nh_gw6)))
                return 0;

        arg->match = nh;

        /* found a match, break the loop */
        return 1;
}

static void rt6_update_exception_stamp_rt(struct rt6_info *rt)
{
        struct fib6_info *from;
        struct fib6_nh *fib6_nh;

        rcu_read_lock();

        from = rcu_dereference(rt->from);
        if (!from || !(rt->rt6i_flags & RTF_CACHE))
                goto unlock;

        if (from->nh) {
                struct fib6_nh_match_arg arg = {
                        .dev = rt->dst.dev,
                        .gw = &rt->rt6i_gateway,
                };

                nexthop_for_each_fib6_nh(from->nh, fib6_nh_find_match, &arg);

                if (!arg.match)
                        goto unlock;
                fib6_nh = arg.match;
        } else {
                fib6_nh = from->fib6_nh;
        }
        fib6_nh_update_exception(fib6_nh, from->fib6_src.plen, rt);
unlock:
        rcu_read_unlock();
}

static bool rt6_mtu_change_route_allowed(struct inet6_dev *idev,
                                         struct rt6_info *rt, int mtu)
{
        /* If the new MTU is lower than the route PMTU, this new MTU will be the
         * lowest MTU in the path: always allow updating the route PMTU to
         * reflect PMTU decreases.
         *
         * If the new MTU is higher, and the route PMTU is equal to the local
         * MTU, this means the old MTU is the lowest in the path, so allow
         * updating it: if other nodes now have lower MTUs, PMTU discovery will
         * handle this.
         */

        if (dst_mtu(&rt->dst) >= mtu)
                return true;

        if (dst_mtu(&rt->dst) == idev->cnf.mtu6)
                return true;

        return false;
}

static void rt6_exceptions_update_pmtu(struct inet6_dev *idev,
                                       const struct fib6_nh *nh, int mtu)
{
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;
        int i;

        bucket = fib6_nh_get_excptn_bucket(nh, &rt6_exception_lock);
        if (!bucket)
                return;

        for (i = 0; i < FIB6_EXCEPTION_BUCKET_SIZE; i++) {
                hlist_for_each_entry(rt6_ex, &bucket->chain, hlist) {
                        struct rt6_info *entry = rt6_ex->rt6i;

                        /* For RTF_CACHE with rt6i_pmtu == 0 (i.e. a redirected
                         * route), the metrics of its rt->from have already
                         * been updated.
                         */
                        if (dst_metric_raw(&entry->dst, RTAX_MTU) &&
                            rt6_mtu_change_route_allowed(idev, entry, mtu))
                                dst_metric_set(&entry->dst, RTAX_MTU, mtu);
                }
                bucket++;
        }
}

#define RTF_CACHE_GATEWAY       (RTF_GATEWAY | RTF_CACHE)

static void fib6_nh_exceptions_clean_tohost(const struct fib6_nh *nh,
                                            const struct in6_addr *gateway)
{
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;
        struct hlist_node *tmp;
        int i;

        if (!rcu_access_pointer(nh->rt6i_exception_bucket))
                return;

        spin_lock_bh(&rt6_exception_lock);
        bucket = fib6_nh_get_excptn_bucket(nh, &rt6_exception_lock);
        if (bucket) {
                for (i = 0; i < FIB6_EXCEPTION_BUCKET_SIZE; i++) {
                        hlist_for_each_entry_safe(rt6_ex, tmp,
                                                  &bucket->chain, hlist) {
                                struct rt6_info *entry = rt6_ex->rt6i;

                                if ((entry->rt6i_flags & RTF_CACHE_GATEWAY) ==
                                    RTF_CACHE_GATEWAY &&
                                    ipv6_addr_equal(gateway,
                                                    &entry->rt6i_gateway)) {
                                        rt6_remove_exception(bucket, rt6_ex);
                                }
                        }
                        bucket++;
                }
        }

        spin_unlock_bh(&rt6_exception_lock);
}

static void rt6_age_examine_exception(struct rt6_exception_bucket *bucket,
                                      struct rt6_exception *rt6_ex,
                                      struct fib6_gc_args *gc_args,
                                      unsigned long now)
{
        struct rt6_info *rt = rt6_ex->rt6i;

        /* we are pruning and obsoleting aged-out and non gateway exceptions
         * even if others have still references to them, so that on next
         * dst_check() such references can be dropped.
         * EXPIRES exceptions - e.g. pmtu-generated ones are pruned when
         * expired, independently from their aging, as per RFC 8201 section 4
         */
        if (!(rt->rt6i_flags & RTF_EXPIRES)) {
                if (time_after_eq(now, rt->dst.lastuse + gc_args->timeout)) {
                        RT6_TRACE("aging clone %p\n", rt);
                        rt6_remove_exception(bucket, rt6_ex);
                        return;
                }
        } else if (time_after(jiffies, rt->dst.expires)) {
                RT6_TRACE("purging expired route %p\n", rt);
                rt6_remove_exception(bucket, rt6_ex);
                return;
        }

        if (rt->rt6i_flags & RTF_GATEWAY) {
                struct neighbour *neigh;
                __u8 neigh_flags = 0;

                neigh = __ipv6_neigh_lookup_noref(rt->dst.dev, &rt->rt6i_gateway);
                if (neigh)
                        neigh_flags = neigh->flags;

                if (!(neigh_flags & NTF_ROUTER)) {
                        RT6_TRACE("purging route %p via non-router but gateway\n",
                                  rt);
                        rt6_remove_exception(bucket, rt6_ex);
                        return;
                }
        }

        gc_args->more++;
}

static void fib6_nh_age_exceptions(const struct fib6_nh *nh,
                                   struct fib6_gc_args *gc_args,
                                   unsigned long now)
{
        struct rt6_exception_bucket *bucket;
        struct rt6_exception *rt6_ex;
        struct hlist_node *tmp;
        int i;

        if (!rcu_access_pointer(nh->rt6i_exception_bucket))
                return;

        rcu_read_lock_bh();
        spin_lock(&rt6_exception_lock);
        bucket = fib6_nh_get_excptn_bucket(nh, &rt6_exception_lock);
        if (bucket) {
                for (i = 0; i < FIB6_EXCEPTION_BUCKET_SIZE; i++) {
                        hlist_for_each_entry_safe(rt6_ex, tmp,
                                                  &bucket->chain, hlist) {
                                rt6_age_examine_exception(bucket, rt6_ex,
                                                          gc_args, now);
                        }
                        bucket++;
                }
        }
        spin_unlock(&rt6_exception_lock);
        rcu_read_unlock_bh();
}

struct fib6_nh_age_excptn_arg {
        struct fib6_gc_args     *gc_args;
        unsigned long           now;
};

static int rt6_nh_age_exceptions(struct fib6_nh *nh, void *_arg)
{
        struct fib6_nh_age_excptn_arg *arg = _arg;

        fib6_nh_age_exceptions(nh, arg->gc_args, arg->now);
        return 0;
}

void rt6_age_exceptions(struct fib6_info *f6i,
                        struct fib6_gc_args *gc_args,
                        unsigned long now)
{
        if (f6i->nh) {
                struct fib6_nh_age_excptn_arg arg = {
                        .gc_args = gc_args,
                        .now = now
                };

                nexthop_for_each_fib6_nh(f6i->nh, rt6_nh_age_exceptions,
                                         &arg);
        } else {
                fib6_nh_age_exceptions(f6i->fib6_nh, gc_args, now);
        }
}

/* must be called with rcu lock held */
int fib6_table_lookup(struct net *net, struct fib6_table *table, int oif,
                      struct flowi6 *fl6, struct fib6_result *res, int strict)
{
        struct fib6_node *fn, *saved_fn;

        fn = fib6_node_lookup(&table->tb6_root, &fl6->daddr, &fl6->saddr);
        saved_fn = fn;

        if (fl6->flowi6_flags & FLOWI_FLAG_SKIP_NH_OIF)
                oif = 0;

redo_rt6_select:
        rt6_select(net, fn, oif, res, strict);
        if (res->f6i == net->ipv6.fib6_null_entry) {
                fn = fib6_backtrack(fn, &fl6->saddr);
                if (fn)
                        goto redo_rt6_select;
                else if (strict & RT6_LOOKUP_F_REACHABLE) {
                        /* also consider unreachable route */
                        strict &= ~RT6_LOOKUP_F_REACHABLE;
                        fn = saved_fn;
                        goto redo_rt6_select;
                }
        }

        trace_fib6_table_lookup(net, res, table, fl6);

        return 0;
}

struct rt6_info *ip6_pol_route(struct net *net, struct fib6_table *table,
                               int oif, struct flowi6 *fl6,
                               const struct sk_buff *skb, int flags)
{
        struct fib6_result res = {};
        struct rt6_info *rt = NULL;
        int strict = 0;

        WARN_ON_ONCE((flags & RT6_LOOKUP_F_DST_NOREF) &&
                     !rcu_read_lock_held());

        strict |= flags & RT6_LOOKUP_F_IFACE;
        strict |= flags & RT6_LOOKUP_F_IGNORE_LINKSTATE;
        if (net->ipv6.devconf_all->forwarding == 0)
                strict |= RT6_LOOKUP_F_REACHABLE;

        rcu_read_lock();

        fib6_table_lookup(net, table, oif, fl6, &res, strict);
        if (res.f6i == net->ipv6.fib6_null_entry)
                goto out;

        fib6_select_path(net, &res, fl6, oif, false, skb, strict);

        /*Search through exception table */
        rt = rt6_find_cached_rt(&res, &fl6->daddr, &fl6->saddr);
        if (rt) {
                goto out;
        } else if (unlikely((fl6->flowi6_flags & FLOWI_FLAG_KNOWN_NH) &&
                            !res.nh->fib_nh_gw_family)) {
                /* Create a RTF_CACHE clone which will not be
                 * owned by the fib6 tree.  It is for the special case where
                 * the daddr in the skb during the neighbor look-up is different
                 * from the fl6->daddr used to look-up route here.
                 */
                rt = ip6_rt_cache_alloc(&res, &fl6->daddr, NULL);

                if (rt) {
                        /* 1 refcnt is taken during ip6_rt_cache_alloc().
                         * As rt6_uncached_list_add() does not consume refcnt,
                         * this refcnt is always returned to the caller even
                         * if caller sets RT6_LOOKUP_F_DST_NOREF flag.
                         */
                        rt6_uncached_list_add(rt);
                        atomic_inc(&net->ipv6.rt6_stats->fib_rt_uncache);
                        rcu_read_unlock();

                        return rt;
                }
        } else {
                /* Get a percpu copy */
                local_bh_disable();
                rt = rt6_get_pcpu_route(&res);

                if (!rt)
                        rt = rt6_make_pcpu_route(net, &res);

                local_bh_enable();
        }
out:
        if (!rt)
                rt = net->ipv6.ip6_null_entry;
        if (!(flags & RT6_LOOKUP_F_DST_NOREF))
                ip6_hold_safe(net, &rt);
        rcu_read_unlock();

        return rt;
}
EXPORT_SYMBOL_GPL(ip6_pol_route);

static struct rt6_info *ip6_pol_route_input(struct net *net,
                                            struct fib6_table *table,
                                            struct flowi6 *fl6,
                                            const struct sk_buff *skb,
                                            int flags)
{
        return ip6_pol_route(net, table, fl6->flowi6_iif, fl6, skb, flags);
}

struct dst_entry *ip6_route_input_lookup(struct net *net,
                                         struct net_device *dev,
                                         struct flowi6 *fl6,
                                         const struct sk_buff *skb,
                                         int flags)
{
        if (rt6_need_strict(&fl6->daddr) && dev->type != ARPHRD_PIMREG)
                flags |= RT6_LOOKUP_F_IFACE;

        return fib6_rule_lookup(net, fl6, skb, flags, ip6_pol_route_input);
}
EXPORT_SYMBOL_GPL(ip6_route_input_lookup);

static void ip6_multipath_l3_keys(const struct sk_buff *skb,
                                  struct flow_keys *keys,
                                  struct flow_keys *flkeys)
{
        const struct ipv6hdr *outer_iph = ipv6_hdr(skb);
        const struct ipv6hdr *key_iph = outer_iph;
        struct flow_keys *_flkeys = flkeys;
        const struct ipv6hdr *inner_iph;
        const struct icmp6hdr *icmph;
        struct ipv6hdr _inner_iph;
        struct icmp6hdr _icmph;

        if (likely(outer_iph->nexthdr != IPPROTO_ICMPV6))
                goto out;

        icmph = skb_header_pointer(skb, skb_transport_offset(skb),
                                   sizeof(_icmph), &_icmph);
        if (!icmph)
                goto out;

        if (icmph->icmp6_type != ICMPV6_DEST_UNREACH &&
            icmph->icmp6_type != ICMPV6_PKT_TOOBIG &&
            icmph->icmp6_type != ICMPV6_TIME_EXCEED &&
            icmph->icmp6_type != ICMPV6_PARAMPROB)
                goto out;

        inner_iph = skb_header_pointer(skb,
                                       skb_transport_offset(skb) + sizeof(*icmph),
                                       sizeof(_inner_iph), &_inner_iph);
        if (!inner_iph)
                goto out;

        key_iph = inner_iph;
        _flkeys = NULL;
out:
        if (_flkeys) {
                keys->addrs.v6addrs.src = _flkeys->addrs.v6addrs.src;
                keys->addrs.v6addrs.dst = _flkeys->addrs.v6addrs.dst;
                keys->tags.flow_label = _flkeys->tags.flow_label;
                keys->basic.ip_proto = _flkeys->basic.ip_proto;
        } else {
                keys->addrs.v6addrs.src = key_iph->saddr;
                keys->addrs.v6addrs.dst = key_iph->daddr;
                keys->tags.flow_label = ip6_flowlabel(key_iph);
                keys->basic.ip_proto = key_iph->nexthdr;
        }
}

/* if skb is set it will be used and fl6 can be NULL */
u32 rt6_multipath_hash(const struct net *net, const struct flowi6 *fl6,
                       const struct sk_buff *skb, struct flow_keys *flkeys)
{
        struct flow_keys hash_keys;
        u32 mhash;

        switch (ip6_multipath_hash_policy(net)) {
        case 0:
                memset(&hash_keys, 0, sizeof(hash_keys));
                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                if (skb) {
                        ip6_multipath_l3_keys(skb, &hash_keys, flkeys);
                } else {
                        hash_keys.addrs.v6addrs.src = fl6->saddr;
                        hash_keys.addrs.v6addrs.dst = fl6->daddr;
                        hash_keys.tags.flow_label = (__force u32)flowi6_get_flowlabel(fl6);
                        hash_keys.basic.ip_proto = fl6->flowi6_proto;
                }
                break;
        case 1:
                if (skb) {
                        unsigned int flag = FLOW_DISSECTOR_F_STOP_AT_ENCAP;
                        struct flow_keys keys;

                        /* short-circuit if we already have L4 hash present */
                        if (skb->l4_hash)
                                return skb_get_hash_raw(skb) >> 1;

                        memset(&hash_keys, 0, sizeof(hash_keys));

                        if (!flkeys) {
                                skb_flow_dissect_flow_keys(skb, &keys, flag);
                                flkeys = &keys;
                        }
                        hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                        hash_keys.addrs.v6addrs.src = flkeys->addrs.v6addrs.src;
                        hash_keys.addrs.v6addrs.dst = flkeys->addrs.v6addrs.dst;
                        hash_keys.ports.src = flkeys->ports.src;
                        hash_keys.ports.dst = flkeys->ports.dst;
                        hash_keys.basic.ip_proto = flkeys->basic.ip_proto;
                } else {
                        memset(&hash_keys, 0, sizeof(hash_keys));
                        hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                        hash_keys.addrs.v6addrs.src = fl6->saddr;
                        hash_keys.addrs.v6addrs.dst = fl6->daddr;
                        hash_keys.ports.src = fl6->fl6_sport;
                        hash_keys.ports.dst = fl6->fl6_dport;
                        hash_keys.basic.ip_proto = fl6->flowi6_proto;
                }
                break;
        case 2:
                memset(&hash_keys, 0, sizeof(hash_keys));
                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                if (skb) {
                        struct flow_keys keys;

                        if (!flkeys) {
                                skb_flow_dissect_flow_keys(skb, &keys, 0);
                                flkeys = &keys;
                        }

                        /* Inner can be v4 or v6 */
                        if (flkeys->control.addr_type == FLOW_DISSECTOR_KEY_IPV4_ADDRS) {
                                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV4_ADDRS;
                                hash_keys.addrs.v4addrs.src = flkeys->addrs.v4addrs.src;
                                hash_keys.addrs.v4addrs.dst = flkeys->addrs.v4addrs.dst;
                        } else if (flkeys->control.addr_type == FLOW_DISSECTOR_KEY_IPV6_ADDRS) {
                                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                                hash_keys.addrs.v6addrs.src = flkeys->addrs.v6addrs.src;
                                hash_keys.addrs.v6addrs.dst = flkeys->addrs.v6addrs.dst;
                                hash_keys.tags.flow_label = flkeys->tags.flow_label;
                                hash_keys.basic.ip_proto = flkeys->basic.ip_proto;
                        } else {
                                /* Same as case 0 */
                                hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                                ip6_multipath_l3_keys(skb, &hash_keys, flkeys);
                        }
                } else {
                        /* Same as case 0 */
                        hash_keys.control.addr_type = FLOW_DISSECTOR_KEY_IPV6_ADDRS;
                        hash_keys.addrs.v6addrs.src = fl6->saddr;
                        hash_keys.addrs.v6addrs.dst = fl6->daddr;
                        hash_keys.tags.flow_label = (__force u32)flowi6_get_flowlabel(fl6);
                        hash_keys.basic.ip_proto = fl6->flowi6_proto;
                }
                break;
        }
        mhash = flow_hash_from_keys(&hash_keys);

        return mhash >> 1;
}

/* Called with rcu held */
void ip6_route_input(struct sk_buff *skb)
{
        const struct ipv6hdr *iph = ipv6_hdr(skb);
        struct net *net = dev_net(skb->dev);
        int flags = RT6_LOOKUP_F_HAS_SADDR | RT6_LOOKUP_F_DST_NOREF;
        struct ip_tunnel_info *tun_info;
        struct flowi6 fl6 = {
                .flowi6_iif = skb->dev->ifindex,
                .daddr = iph->daddr,
                .saddr = iph->saddr,
                .flowlabel = ip6_flowinfo(iph),
                .flowi6_mark = skb->mark,
                .flowi6_proto = iph->nexthdr,
        };
        struct flow_keys *flkeys = NULL, _flkeys;

        tun_info = skb_tunnel_info(skb);
        if (tun_info && !(tun_info->mode & IP_TUNNEL_INFO_TX))
                fl6.flowi6_tun_key.tun_id = tun_info->key.tun_id;

        if (fib6_rules_early_flow_dissect(net, skb, &fl6, &_flkeys))
                flkeys = &_flkeys;

        if (unlikely(fl6.flowi6_proto == IPPROTO_ICMPV6))
                fl6.mp_hash = rt6_multipath_hash(net, &fl6, skb, flkeys);
        skb_dst_drop(skb);
        skb_dst_set_noref(skb, ip6_route_input_lookup(net, skb->dev,
                                                      &fl6, skb, flags));
}

static struct rt6_info *ip6_pol_route_output(struct net *net,
                                             struct fib6_table *table,
                                             struct flowi6 *fl6,
                                             const struct sk_buff *skb,
                                             int flags)
{
        return ip6_pol_route(net, table, fl6->flowi6_oif, fl6, skb, flags);
}

struct dst_entry *ip6_route_output_flags_noref(struct net *net,
                                               const struct sock *sk,
                                               struct flowi6 *fl6, int flags)
{
        bool any_src;

        if (ipv6_addr_type(&fl6->daddr) &
            (IPV6_ADDR_MULTICAST | IPV6_ADDR_LINKLOCAL)) {
                struct dst_entry *dst;

                /* This function does not take refcnt on the dst */
                dst = l3mdev_link_scope_lookup(net, fl6);
                if (dst)
                        return dst;
        }

        fl6->flowi6_iif = LOOPBACK_IFINDEX;

        flags |= RT6_LOOKUP_F_DST_NOREF;
        any_src = ipv6_addr_any(&fl6->saddr);
        if ((sk && sk->sk_bound_dev_if) || rt6_need_strict(&fl6->daddr) ||
            (fl6->flowi6_oif && any_src))
                flags |= RT6_LOOKUP_F_IFACE;

        if (!any_src)
                flags |= RT6_LOOKUP_F_HAS_SADDR;
        else if (sk)
                flags |= rt6_srcprefs2flags(inet6_sk(sk)->srcprefs);

        return fib6_rule_lookup(net, fl6, NULL, flags, ip6_pol_route_output);
}
EXPORT_SYMBOL_GPL(ip6_route_output_flags_noref);

struct dst_entry *ip6_route_output_flags(struct net *net,
                                         const struct sock *sk,
                                         struct flowi6 *fl6,
                                         int flags)
{
        struct dst_entry *dst;
        struct rt6_info *rt6;

        rcu_read_lock();
        dst = ip6_route_output_flags_noref(net, sk, fl6, flags);
        rt6 = (struct rt6_info *)dst;
        /* For dst cached in uncached_list, refcnt is already taken. */
        if (list_empty(&rt6->rt6i_uncached) && !dst_hold_safe(dst)) {
                dst = &net->ipv6.ip6_null_entry->dst;
                dst_hold(dst);
        }
        rcu_read_unlock();

        return dst;
}
EXPORT_SYMBOL_GPL(ip6_route_output_flags);

struct dst_entry *ip6_blackhole_route(struct net *net, struct dst_entry *dst_orig)
{
        struct rt6_info *rt, *ort = (struct rt6_info *) dst_orig;
        struct net_device *loopback_dev = net->loopback_dev;
        struct dst_entry *new = NULL;

        rt = dst_alloc(&ip6_dst_blackhole_ops, loopback_dev, 1,
                       DST_OBSOLETE_DEAD, 0);
        if (rt) {
                rt6_info_init(rt);
                atomic_inc(&net->ipv6.rt6_stats->fib_rt_alloc);

                new = &rt->dst;
                new->__use = 1;
                new->input = dst_discard;
                new->output = dst_discard_out;

                dst_copy_metrics(new, &ort->dst);

                rt->rt6i_idev = in6_dev_get(loopback_dev);
                rt->rt6i_gateway = ort->rt6i_gateway;
                rt->rt6i_flags = ort->rt6i_flags & ~RTF_PCPU;

                memcpy(&rt->rt6i_dst, &ort->rt6i_dst, sizeof(struct rt6key));
#ifdef CONFIG_IPV6_SUBTREES
                memcpy(&rt->rt6i_src, &ort->rt6i_src, sizeof(struct rt6key));
#endif
        }

        dst_release(dst_orig);
        return new ? new : ERR_PTR(-ENOMEM);
}

/*
 *      Destination cache support functions
 */

static bool fib6_check(struct fib6_info *f6i, u32 cookie)
{
        u32 rt_cookie = 0;

        if (!fib6_get_cookie_safe(f6i, &rt_cookie) || rt_cookie != cookie)
                return false;

        if (fib6_check_expired(f6i))
                return false;

        return true;
}

static struct dst_entry *rt6_check(struct rt6_info *rt,
                                   struct fib6_info *from,
                                   u32 cookie)
{
        u32 rt_cookie = 0;

        if (!from || !fib6_get_cookie_safe(from, &rt_cookie) ||
            rt_cookie != cookie)
                return NULL;

        if (rt6_check_expired(rt))
                return NULL;

        return &rt->dst;
}

static struct dst_entry *rt6_dst_from_check(struct rt6_info *rt,
                                            struct fib6_info *from,
                                            u32 cookie)
{
        if (!__rt6_check_expired(rt) &&
            rt->dst.obsolete == DST_OBSOLETE_FORCE_CHK &&
            fib6_check(from, cookie))
                return &rt->dst;
        else
                return NULL;
}

static struct dst_entry *ip6_dst_check(struct dst_entry *dst, u32 cookie)
{
        struct dst_entry *dst_ret;
        struct fib6_info *from;
        struct rt6_info *rt;

        rt = container_of(dst, struct rt6_info, dst);

        rcu_read_lock();

        /* All IPV6 dsts are created with ->obsolete set to the value
         * DST_OBSOLETE_FORCE_CHK which forces validation calls down
         * into this function always.
         */

        from = rcu_dereference(rt->from);

        if (from && (rt->rt6i_flags & RTF_PCPU ||
            unlikely(!list_empty(&rt->rt6i_uncached))))
                dst_ret = rt6_dst_from_check(rt, from, cookie);
        else
                dst_ret = rt6_check(rt, from, cookie);

        rcu_read_unlock();

        return dst_ret;
}

static struct dst_entry *ip6_negative_advice(struct dst_entry *dst)
{
        struct rt6_info *rt = (struct rt6_info *) dst;

        if (rt) {
                if (rt->rt6i_flags & RTF_CACHE) {
                        rcu_read_lock();
                        if (rt6_check_expired(rt)) {
                                rt6_remove_exception_rt(rt);
                                dst = NULL;
                        }
                        rcu_read_unlock();
                } else {
                        dst_release(dst);
                        dst = NULL;
                }
        }
        return dst;
}

static void ip6_link_failure(struct sk_buff *skb)
{
        struct rt6_info *rt;

        icmpv6_send(skb, ICMPV6_DEST_UNREACH, ICMPV6_ADDR_UNREACH, 0);

        rt = (struct rt6_info *) skb_dst(skb);
        if (rt) {
                rcu_read_lock();
                if (rt->rt6i_flags & RTF_CACHE) {
                        rt6_remove_exception_rt(rt);
                } else {
                        struct fib6_info *from;
                        struct fib6_node *fn;

                        from = rcu_dereference(rt->from);
                        if (from) {
                                fn = rcu_dereference(from->fib6_node);
                                if (fn && (rt->rt6i_flags & RTF_DEFAULT))
                                        fn->fn_sernum = -1;
                        }
                }
                rcu_read_unlock();
        }
}

static void rt6_update_expires(struct rt6_info *rt0, int timeout)
{
        if (!(rt0->rt6i_flags & RTF_EXPIRES)) {
                struct fib6_info *from;

                rcu_read_lock();
                from = rcu_dereference(rt0->from);
                if (from)
                        rt0->dst.expires = from->expires;
                rcu_read_unlock();
        }

        dst_set_expires(&rt0->dst, timeout);
        rt0->rt6i_flags |= RTF_EXPIRES;
}

static void rt6_do_update_pmtu(struct rt6_info *rt, u32 mtu)
{
        struct net *net = dev_net(rt->dst.dev);

        dst_metric_set(&rt->dst, RTAX_MTU, mtu);
        rt->rt6i_flags |= RTF_MODIFIED;
        rt6_update_expires(rt, net->ipv6.sysctl.ip6_rt_mtu_expires);
}

static bool rt6_cache_allowed_for_pmtu(const struct rt6_info *rt)
{
        return !(rt->rt6i_flags & RTF_CACHE) &&
                (rt->rt6i_flags & RTF_PCPU || rcu_access_pointer(rt->from));
}

static void __ip6_rt_update_pmtu(struct dst_entry *dst, const struct sock *sk,
                                 const struct ipv6hdr *iph, u32 mtu)
{
        const struct in6_addr *daddr, *saddr;
        struct rt6_info *rt6 = (struct rt6_info *)dst;

        if (dst_metric_locked(dst, RTAX_MTU))
                return;

        if (iph) {
                daddr = &iph->daddr;
                saddr = &iph->saddr;
        } else if (sk) {
                daddr = &sk->sk_v6_daddr;
                saddr = &inet6_sk(sk)->saddr;
        } else {
                daddr = NULL;
                saddr = NULL;
        }
        dst_confirm_neigh(dst, daddr);
        mtu = max_t(u32, mtu, IPV6_MIN_MTU);
        if (mtu >= dst_mtu(dst))
                return;

        if (!rt6_cache_allowed_for_pmtu(rt6)) {
                rt6_do_update_pmtu(rt6, mtu);
                /* update rt6_ex->stamp for cache */
                if (rt6->rt6i_flags & RTF_CACHE)
                        rt6_update_exception_stamp_rt(rt6);
        } else if (daddr) {
                struct fib6_result res = {};
                struct rt6_info *nrt6;

                rcu_read_lock();
                res.f6i = rcu_dereference(rt6->from);
                if (!res.f6i)
                        goto out_unlock;

                res.fib6_flags = res.f6i->fib6_flags;
                res.fib6_type = res.f6i->fib6_type;

                if (res.f6i->nh) {
                        struct fib6_nh_match_arg arg = {
                                .dev = dst->dev,
                                .gw = &rt6->rt6i_gateway,
                        };

                        nexthop_for_each_fib6_nh(res.f6i->nh,
                                                 fib6_nh_find_match, &arg);

                        /* fib6_info uses a nexthop that does not have fib6_nh
                         * using the dst->dev + gw. Should be impossible.
                         */
                        if (!arg.match)
                                goto out_unlock;

                        res.nh = arg.match;
                } else {
                        res.nh = res.f6i->fib6_nh;
                }

                nrt6 = ip6_rt_cache_alloc(&res, daddr, saddr);
                if (nrt6) {
                        rt6_do_update_pmtu(nrt6, mtu);
                        if (rt6_insert_exception(nrt6, &res))
                                dst_release_immediate(&nrt6->dst);
                }
out_unlock:
                rcu_read_unlock();
        }
}

static void ip6_rt_update_pmtu(struct dst_entry *dst, struct sock *sk,
                               struct sk_buff *skb, u32 mtu)
{
        __ip6_rt_update_pmtu(dst, sk, skb ? ipv6_hdr(skb) : NULL, mtu);
}

void ip6_update_pmtu(struct sk_buff *skb, struct net *net, __be32 mtu,
                     int oif, u32 mark, kuid_t uid)
{
        const struct ipv6hdr *iph = (struct ipv6hdr *) skb->data;
        struct dst_entry *dst;
        struct flowi6 fl6 = {
                .flowi6_oif = oif,
                .flowi6_mark = mark ? mark : IP6_REPLY_MARK(net, skb->mark),
                .daddr = iph->daddr,
                .saddr = iph->saddr,
                .flowlabel = ip6_flowinfo(iph),
                .flowi6_uid = uid,
        };

        dst = ip6_route_output(net, NULL, &fl6);
        if (!dst->error)
                __ip6_rt_update_pmtu(dst, NULL, iph, ntohl(mtu));
        dst_release(dst);
}
EXPORT_SYMBOL_GPL(ip6_update_pmtu);

void ip6_sk_update_pmtu(struct sk_buff *skb, struct sock *sk, __be32 mtu)
{
        int oif = sk->sk_bound_dev_if;
        struct dst_entry *dst;

        if (!oif && skb->dev)
                oif = l3mdev_master_ifindex(skb->dev);

        ip6_update_pmtu(skb, sock_net(sk), mtu, oif, sk->sk_mark, sk->sk_uid);

        dst = __sk_dst_get(sk);
        if (!dst || !dst->obsolete ||
            dst->ops->check(dst, inet6_sk(sk)->dst_cookie))
                return;

        bh_lock_sock(sk);
        if (!sock_owned_by_user(sk) && !ipv6_addr_v4mapped(&sk->sk_v6_daddr))
                ip6_datagram_dst_update(sk, false);
        bh_unlock_sock(sk);
}
EXPORT_SYMBOL_GPL(ip6_sk_update_pmtu);

void ip6_sk_dst_store_flow(struct sock *sk, struct dst_entry *dst,
                           const struct flowi6 *fl6)
{
#ifdef CONFIG_IPV6_SUBTREES
        struct ipv6_pinfo *np = inet6_sk(sk);
#endif

        ip6_dst_store(sk, dst,
                      ipv6_addr_equal(&fl6->daddr, &sk->sk_v6_daddr) ?
                      &sk->sk_v6_daddr : NULL,
#ifdef CONFIG_IPV6_SUBTREES
                      ipv6_addr_equal(&fl6->saddr, &np->saddr) ?
                      &np->saddr :
#endif
                      NULL);
}

static bool ip6_redirect_nh_match(const struct fib6_result *res,
                                  struct flowi6 *fl6,
                                  const struct in6_addr *gw,
                                  struct rt6_info **ret)
{
        const struct fib6_nh *nh = res->nh;

        if (nh->fib_nh_flags & RTNH_F_DEAD || !nh->fib_nh_gw_family ||
            fl6->flowi6_oif != nh->fib_nh_dev->ifindex)
                return false;

        /* rt_cache's gateway might be different from its 'parent'
         * in the case of an ip redirect.
         * So we keep searching in the exception table if the gateway
         * is different.
         */
        if (!ipv6_addr_equal(gw, &nh->fib_nh_gw6)) {
                struct rt6_info *rt_cache;

                rt_cache = rt6_find_cached_rt(res, &fl6->daddr, &fl6->saddr);
                if (rt_cache &&
                    ipv6_addr_equal(gw, &rt_cache->rt6i_gateway)) {
                        *ret = rt_cache;
                        return true;
                }
                return false;
        }
        return true;
}

struct fib6_nh_rd_arg {
        struct fib6_result      *res;
        struct flowi6           *fl6;
        const struct in6_addr   *gw;
        struct rt6_info         **ret;
};

static int fib6_nh_redirect_match(struct fib6_nh *nh, void *_arg)
{
        struct fib6_nh_rd_arg *arg = _arg;

        arg->res->nh = nh;
        return ip6_redirect_nh_match(arg->res, arg->fl6, arg->gw, arg->ret);
}

/* Handle redirects */
struct ip6rd_flowi {
        struct flowi6 fl6;
        struct in6_addr gateway;
};

static struct rt6_info *__ip6_route_redirect(struct net *net,
                                             struct fib6_table *table,
                                             struct flowi6 *fl6,
                                             const struct sk_buff *skb,
                                             int flags)
{
        struct ip6rd_flowi *rdfl = (struct ip6rd_flowi *)fl6;
        struct rt6_info *ret = NULL;
        struct fib6_result res = {};
        struct fib6_nh_rd_arg arg = {
                .res = &res,
                .fl6 = fl6,
                .gw  = &rdfl->gateway,
                .ret = &ret
        };
        struct fib6_info *rt;
        struct fib6_node *fn;

        /* l3mdev_update_flow overrides oif if the device is enslaved; in
         * this case we must match on the real ingress device, so reset it
         */
        if (fl6->flowi6_flags & FLOWI_FLAG_SKIP_NH_OIF)
                fl6->flowi6_oif = skb->dev->ifindex;

        /* Get the "current" route for this destination and
         * check if the redirect has come from appropriate router.
         *
         * RFC 4861 specifies that redirects should only be
         * accepted if they come from the nexthop to the target.
         * Due to the way the routes are chosen, this notion
         * is a bit fuzzy and one might need to check all possible
         * routes.
         */

        rcu_read_lock();
        fn = fib6_node_lookup(&table->tb6_root, &fl6->daddr, &fl6->saddr);
restart:
        for_each_fib6_node_rt_rcu(fn) {
                res.f6i = rt;
                if (fib6_check_expired(rt))
                        continue;
                if (rt->fib6_flags & RTF_REJECT)
                        break;
                if (unlikely(rt->nh)) {
                        if (nexthop_is_blackhole(rt->nh))
                                continue;
                        /* on match, res->nh is filled in and potentially ret */
                        if (nexthop_for_each_fib6_nh(rt->nh,
                                                     fib6_nh_redirect_match,
                                                     &arg))
                                goto out;
                } else {
                        res.nh = rt->fib6_nh;
                        if (ip6_redirect_nh_match(&res, fl6, &rdfl->gateway,
                                                  &ret))
                                goto out;
                }
        }

        if (!rt)
                rt = net->ipv6.fib6_null_entry;
        else if (rt->fib6_flags & RTF_REJECT) {
                ret = net->ipv6.ip6_null_entry;
                goto out;
        }

        if (rt == net->ipv6.fib6_null_entry) {
                fn = fib6_backtrack(fn, &fl6->saddr);
                if (fn)
                        goto restart;
        }

        res.f6i = rt;
        res.nh = rt->fib6_nh;
out:
        if (ret) {
                ip6_hold_safe(net, &ret);
        } else {
                res.fib6_flags = res.f6i->fib6_flags;
                res.fib6_type = res.f6i->fib6_type;
                ret = ip6_create_rt_rcu(&res);
        }

        rcu_read_unlock();

        trace_fib6_table_lookup(net, &res, table, fl6);
        return ret;
};

static struct dst_entry *ip6_route_redirect(struct net *net,
                                            const struct flowi6 *fl6,
                                            const struct sk_buff *skb,
                                            const struct in6_addr *gateway)
{
        int flags = RT6_LOOKUP_F_HAS_SADDR;
        struct ip6rd_flowi rdfl;

        rdfl.fl6 = *fl6;
        rdfl.gateway = *gateway;

        return fib6_rule_lookup(net, &rdfl.fl6, skb,
                                flags, __ip6_route_redirect);
}

void ip6_redirect(struct sk_buff *skb, struct net *net, int oif, u32 mark,
                  kuid_t uid)
{
        const struct ipv6hdr *iph = (struct ipv6hdr *) skb->data;
        struct dst_entry *dst;
        struct flowi6 fl6 = {
                .flowi6_iif = LOOPBACK_IFINDEX,
                .flowi6_oif = oif,
                .flowi6_mark = mark,
                .daddr = iph->daddr,
                .saddr = iph->saddr,