IPv6 source address selection

[Stig Venaas <Stig.Venaas@xxxxxxxxxx>]

Hi

I think Linux needs better IPv6 source address selection. When there are
several global non-deprecated addresses, the current code (2.3.99-pre6)
simply picks the first it finds, while I would like to choose one with
longest common prefix compared to the destination address. This is
described in draft-ietf-ipngwg-default-addr-select-00.txt paragraph 4
rule 6, and seems to be what for instance Solaris 8 does.

This is generally useful when one has several global IPv6 addresses
(multihomed). An important special case is when one of the addresses
is a 6to4 address (starting with 2002::/16). If the destination address
is 6to4 the source address must also be 6to4. If the destionation is
some other global address (3ffe or something) it must not be used.

The following patch against 2.3.99-pre6 seems to work for me:

------8<-------
--- addrconf-2.3.99-pre6.c      Wed May  3 21:21:40 2000
+++ addrconf.c  Wed May  3 21:26:00 2000
@@ -434,12 +434,53 @@
 }
 
 /*
+ *      find the first different bit between two addresses
+ *      length of address must be a multiple of 32bits
+ *
+ *      Copied from ip6_fib.c
+ */
+static __inline__ int addr_diff(void *token1, void *token2, int addrlen)
+{
+        __u32 *a1 = token1;
+       __u32 *a2 = token2;
+       int i;
+
+       addrlen >>= 2;
+
+       for (i = 0; i < addrlen; i++) {
+               __u32 xb;
+
+               xb = a1[i] ^ a2[i];
+
+               if (xb) {
+                       int j = 31;
+
+                       xb = ntohl(xb);
+
+                       while (test_bit(j, &xb) == 0)
+                               j--;
+
+                       return (i * 32 + 31 - j);
+               }
+       }
+
+       /*
+        *      we should *never* get to this point since that 
+        *      would mean the addrs are equal
+        */
+       
+       return addrlen<<5;
+}
+
+/*
  *     Choose an apropriate source address
  *     should do:
  *     i)      get an address with an apropriate scope
  *     ii)     see if there is a specific route for the destination and use
  *             an address of the attached interface 
  *     iii)    don't use deprecated addresses
+ *     iv)     if several valid addresses, use one with longest common prefix
+ *             with destination address
  */
 int ipv6_get_saddr(struct dst_entry *dst,
                   struct in6_addr *daddr, struct in6_addr *saddr)
@@ -447,10 +488,13 @@
        int scope;
        struct inet6_ifaddr *ifp = NULL;
        struct inet6_ifaddr *match = NULL;
+       struct inet6_ifaddr *best = NULL;
        struct net_device *dev = NULL;
        struct inet6_dev *idev;
        struct rt6_info *rt;
        int err;
+       int common_len;
+       int max_common_len = -1;
 
        rt = (struct rt6_info *) dst;
        if (rt)
@@ -481,10 +525,14 @@
                        for (ifp=idev->addr_list; ifp; ifp=ifp->if_next) {
                                if (ifp->scope == scope) {
                                        if (!(ifp->flags & 
(IFA_F_DEPRECATED|IFA_F_TENTATIVE))) {
-                                               in6_ifa_hold(ifp);
-                                               read_unlock_bh(&idev->lock);
-                                               read_unlock(&addrconf_lock);
-                                               goto out;
+                                               common_len = addr_diff(daddr, 
&ifp->addr, 16);
+                                               if (common_len > 
max_common_len) {
+                                                       in6_ifa_hold(ifp);
+                                                       if (best)
+                                                         in6_ifa_put(best);
+                                                       best = ifp;
+                                                       max_common_len = 
common_len;
+                                               }
                                        }
 
                                        if (!match && !(ifp->flags & 
IFA_F_TENTATIVE)) {
@@ -496,6 +544,10 @@
                        read_unlock_bh(&idev->lock);
                }
                read_unlock(&addrconf_lock);
+               if (best) {
+                       ifp = best;
+                       goto out;
+               }
        }
 
        if (scope == IFA_LINK)
------8<-------

Note that I did not write the addr_diff routine, I simply copied it from
ip6_fib.c. If the patch looks good I guess one should reorganize the code
a bit so that addr_diff isn't duplicated.

What do you think? Is this something that can go into 2.4? If necessary I
can try to explain better why it's important.

Stig

-- 
Stig Venaas
UNINETT