From 2d76e87f32131574081c2c25b3f3bb48bf1338b8 Mon Sep 17 00:00:00 2001 From: Arne Schwabe Date: Mon, 17 Feb 2014 23:34:08 +0100 Subject: Further optimization of route calculation --- .../java/de/blinkt/openvpn/core/NetworkSpace.java | 62 +++++++++++++--------- .../de/blinkt/openvpn/core/OpenVpnService.java | 20 +++++-- 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 generateIPList() { - TreeSet ipsSorted = new TreeSet(mIpAddresses); - Iterator it = ipsSorted.iterator(); - ipAddress currentNet = null; - if (it.hasNext()) - currentNet = it.next(); - while (it.hasNext()) { + PriorityQueue networks = new PriorityQueue(mIpAddresses); + + TreeSet ipsDone = new TreeSet(); + + 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 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 positiveIPv4Routes = mRoutes.getPositiveIPList(); + Collection 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()); -- cgit v1.2.3