Further optimization of route calculation

2 files changed, 51 insertions, 31 deletions

diff --git a/main/src/main/java/de/blinkt/openvpn/core/NetworkSpace.java b/main/src/main/java/de/blinkt/openvpn/core/NetworkSpace.java
index 54470962..6e27c0cb 100644
--- a/main/src/main/java/de/blinkt/openvpn/core/NetworkSpace.java
+++ b/main/src/main/java/de/blinkt/openvpn/core/NetworkSpace.java
@@ -32,8 +32,6 @@ public class NetworkSpace {
                 return 0;
             else
                 return 1;
-
-
         }
 
         public ipAddress(CIDRIP ip, boolean include) {
@@ -171,70 +169,82 @@ public class NetworkSpace {
     }
 
     TreeSet<ipAddress> generateIPList() {
-        TreeSet<ipAddress> ipsSorted = new TreeSet<ipAddress>(mIpAddresses);
-        Iterator<ipAddress> it = ipsSorted.iterator();
 
-        ipAddress currentNet = null;
-        if (it.hasNext())
-            currentNet = it.next();
-        while (it.hasNext()) {
+        PriorityQueue<ipAddress> networks = new PriorityQueue<ipAddress>(mIpAddresses);
+
+        TreeSet<ipAddress> ipsDone = new TreeSet<ipAddress>();
+
+        ipAddress currentNet =  networks.poll();
+        if (currentNet==null)
+            return ipsDone;
+
+        while (currentNet!=null) {
             // Check if it and the next of it are compatbile
-            ipAddress nextNet = it.next();
+            ipAddress nextNet = networks.poll();
 
             assert currentNet != null;
-            if (currentNet.getLastAddress().compareTo(nextNet.getFirstAddress()) == -1) {
+            if (nextNet== null || currentNet.getLastAddress().compareTo(nextNet.getFirstAddress()) == -1) {
                 // Everything good, no overlapping nothing to do
+                ipsDone.add(currentNet);
+
                 currentNet = nextNet;
             } else {
                 // This network is smaller or equal to the next but has the same base address
                 if (currentNet.getFirstAddress().equals(nextNet.getFirstAddress()) && currentNet.networkMask >= nextNet.networkMask) {
                     if (currentNet.included == nextNet.included) {
-                        ipsSorted.remove(currentNet);
+                        // Included in the next next and same type
+                        // Simply forget our current network
+                        currentNet=nextNet;
                     } else {
-
-                        // our currentnet is included in next and nextnet needs to be split
-                        ipsSorted.remove(nextNet);
+                        // our currentnet is included in next and types differ. Need to split the next network
                         ipAddress[] newNets = nextNet.split();
 
+                        // First add the second half to keep the order in networks
+                        networks.add(newNets[1]);
+
                         if (newNets[0].getLastAddress().equals(currentNet.getLastAddress())) {
                             assert (newNets[0].networkMask == currentNet.networkMask);
                             // Don't add the lower half that would conflict with currentNet
                         } else {
-                            ipsSorted.add(newNets[0]);
+                            networks.add(newNets[0]);
                         }
-
-                        ipsSorted.add(newNets[1]);
+                        // Keep currentNet as is
                     }
                 } else {
                     assert (currentNet.networkMask < nextNet.networkMask);
                     assert (nextNet.getFirstAddress().compareTo(currentNet.getFirstAddress()) == 1);
-                    // This network is bigger than the next and last ip of current >= next
                     assert (currentNet.getLastAddress().compareTo(nextNet.getLastAddress()) != -1);
 
+                    // This network is bigger than the next and last ip of current >= next
+
                     if (currentNet.included == nextNet.included) {
-                        ipsSorted.remove(nextNet);
+                        // Next network is in included in our network with the same type,
+                        // simply ignore the next and move on
                     } else {
-                        ipsSorted.remove(currentNet);
+                        // We need to split our network
                         ipAddress[] newNets = currentNet.split();
 
-                        ipsSorted.add(newNets[0]);
 
                         if (newNets[1].networkMask == nextNet.networkMask) {
                             assert (newNets[1].getFirstAddress().equals(nextNet.getFirstAddress()));
                             assert (newNets[1].getLastAddress().equals(currentNet.getLastAddress()));
+                            // Splitted second equal the next network, do not add it
+
+                            networks.add(nextNet);
                         } else {
-                            ipsSorted.add(newNets[1]);
+                            // Add the smaller network first
+                            networks.add(newNets[1]);
+                            networks.add(nextNet);
                         }
+                        currentNet = newNets[0];
+
                     }
                 }
-                // Reset iterator
-                it = ipsSorted.iterator();
-                currentNet = it.next();
             }
 
         }
 
-        return ipsSorted;
+        return ipsDone;
     }
 
     Collection<ipAddress> getPositiveIPList() {
diff --git a/main/src/main/java/de/blinkt/openvpn/core/OpenVpnService.java b/main/src/main/java/de/blinkt/openvpn/core/OpenVpnService.java
index 9d6f767e..1e9e14f1 100644
--- a/main/src/main/java/de/blinkt/openvpn/core/OpenVpnService.java
+++ b/main/src/main/java/de/blinkt/openvpn/core/OpenVpnService.java
@@ -29,6 +29,7 @@ import java.net.Inet4Address;
 import java.net.Inet6Address;
 import java.net.InetAddress;
 import java.net.UnknownHostException;
+import java.util.Collection;
 import java.util.HashMap;
 import java.util.Locale;
 import java.util.Vector;
@@ -419,8 +420,14 @@ public class OpenVpnService extends VpnService implements StateListener, Callbac
     }
 
     public ParcelFileDescriptor openTun() {
+
+        //Debug.startMethodTracing(getExternalFilesDir(null).toString() + "/opentun.trace", 40* 1024 * 1024);
+
         Builder builder = new Builder();
 
+        VpnStatus.logInfo(R.string.last_openvpn_tun_config);
+
+
         if (mLocalIP == null && mLocalIPv6 == null) {
             VpnStatus.logError(getString(R.string.opentun_no_ipaddr));
             return null;
@@ -458,8 +465,10 @@ public class OpenVpnService extends VpnService implements StateListener, Callbac
 
         builder.setMtu(mMtu);
 
+        Collection<ipAddress> positiveIPv4Routes = mRoutes.getPositiveIPList();
+        Collection<ipAddress> positiveIPv6Routes = mRoutesv6.getPositiveIPList();
 
-        for (NetworkSpace.ipAddress route : mRoutes.getPositiveIPList()) {
+        for (NetworkSpace.ipAddress route : positiveIPv4Routes) {
             try {
                 builder.addRoute(route.getIPv4Address(), route.networkMask);
             } catch (IllegalArgumentException ia) {
@@ -467,7 +476,7 @@ public class OpenVpnService extends VpnService implements StateListener, Callbac
             }
         }
 
-        for (NetworkSpace.ipAddress route6 : mRoutesv6.getPositiveIPList()) {
+        for (NetworkSpace.ipAddress route6 : positiveIPv6Routes) {
             try {
                 builder.addRoute(route6.getIPv6Address(), route6.networkMask);
             } catch (IllegalArgumentException ia) {
@@ -478,12 +487,11 @@ public class OpenVpnService extends VpnService implements StateListener, Callbac
         if (mDomain != null)
             builder.addSearchDomain(mDomain);
 
-        VpnStatus.logInfo(R.string.last_openvpn_tun_config);
         VpnStatus.logInfo(R.string.local_ip_info, mLocalIP.mIp, mLocalIP.len, mLocalIPv6, mMtu);
         VpnStatus.logInfo(R.string.dns_server_info, TextUtils.join(", ", mDnslist), mDomain);
         VpnStatus.logInfo(R.string.routes_info_incl, TextUtils.join(", ", mRoutes.getNetworks(true)), TextUtils.join(", ", mRoutesv6.getNetworks(true)));
         VpnStatus.logInfo(R.string.routes_info_excl, TextUtils.join(", ", mRoutes.getNetworks(false)),TextUtils.join(", ", mRoutesv6.getNetworks(false)));
-        VpnStatus.logDebug(R.string.routes_debug, TextUtils.join(", ", mRoutes.getPositiveIPList()), TextUtils.join(", ", mRoutesv6.getPositiveIPList()));
+        VpnStatus.logDebug(R.string.routes_debug, TextUtils.join(", ", positiveIPv4Routes), TextUtils.join(", ", positiveIPv6Routes));
 
         String session = mProfile.mName;
         if (mLocalIP != null && mLocalIPv6 != null)
@@ -510,7 +518,9 @@ public class OpenVpnService extends VpnService implements StateListener, Callbac
         builder.setConfigureIntent(getLogPendingIntent());
 
         try {
-            return builder.establish();
+            ParcelFileDescriptor tun = builder.establish();
+            //Debug.stopMethodTracing();
+            return tun;
         } catch (Exception e) {
             VpnStatus.logError(R.string.tun_open_error);
             VpnStatus.logError(getString(R.string.error) + e.getLocalizedMessage());