1 /*
2  * Copyright (C) 2020 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package android.net.util;
18 
19 import static com.android.internal.annotations.VisibleForTesting.Visibility;
20 
21 import android.annotation.NonNull;
22 import android.net.IpPrefix;
23 
24 import com.android.internal.annotations.VisibleForTesting;
25 
26 import java.math.BigInteger;
27 import java.net.InetAddress;
28 import java.net.UnknownHostException;
29 import java.util.ArrayList;
30 import java.util.Arrays;
31 import java.util.LinkedList;
32 import java.util.List;
33 import java.util.Objects;
34 import java.util.Queue;
35 
36 /**
37  * This class represents an IP range, i.e., a contiguous block of IP addresses defined by a starting
38  * and ending IP address. These addresses may not be power-of-two aligned.
39  *
40  * <p>Conversion to prefixes are deterministic, and will always return the same set of {@link
41  * IpPrefix}(es). Ordering of IpPrefix instances is not guaranteed.
42  *
43  * @hide
44  */
45 public final class IpRange {
46     private static final int SIGNUM_POSITIVE = 1;
47 
48     private final byte[] mStartAddr;
49     private final byte[] mEndAddr;
50 
IpRange(@onNull InetAddress startAddr, @NonNull InetAddress endAddr)51     public IpRange(@NonNull InetAddress startAddr, @NonNull InetAddress endAddr) {
52         Objects.requireNonNull(startAddr, "startAddr must not be null");
53         Objects.requireNonNull(endAddr, "endAddr must not be null");
54 
55         if (!startAddr.getClass().equals(endAddr.getClass())) {
56             throw new IllegalArgumentException("Invalid range: Address family mismatch");
57         }
58         if (addrToBigInteger(startAddr.getAddress()).compareTo(
59                 addrToBigInteger(endAddr.getAddress())) >= 0) {
60             throw new IllegalArgumentException(
61                     "Invalid range; start address must be before end address");
62         }
63 
64         mStartAddr = startAddr.getAddress();
65         mEndAddr = endAddr.getAddress();
66     }
67 
68     @VisibleForTesting(visibility = Visibility.PRIVATE)
IpRange(@onNull IpPrefix prefix)69     public IpRange(@NonNull IpPrefix prefix) {
70         Objects.requireNonNull(prefix, "prefix must not be null");
71 
72         // Use masked address from IpPrefix to zero out lower order bits.
73         mStartAddr = prefix.getRawAddress();
74 
75         // Set all non-prefix bits to max.
76         mEndAddr = prefix.getRawAddress();
77         for (int bitIndex = prefix.getPrefixLength(); bitIndex < 8 * mEndAddr.length; ++bitIndex) {
78             mEndAddr[bitIndex / 8] |= (byte) (0x80 >> (bitIndex % 8));
79         }
80     }
81 
getAsInetAddress(byte[] address)82     private static InetAddress getAsInetAddress(byte[] address) {
83         try {
84             return InetAddress.getByAddress(address);
85         } catch (UnknownHostException e) {
86             // Cannot happen. InetAddress.getByAddress can only throw an exception if the byte
87             // array is the wrong length, but are always generated from InetAddress(es).
88             throw new IllegalArgumentException("Address is invalid");
89         }
90     }
91 
92     @VisibleForTesting(visibility = Visibility.PRIVATE)
getStartAddr()93     public InetAddress getStartAddr() {
94         return getAsInetAddress(mStartAddr);
95     }
96 
97     @VisibleForTesting(visibility = Visibility.PRIVATE)
getEndAddr()98     public InetAddress getEndAddr() {
99         return getAsInetAddress(mEndAddr);
100     }
101 
102     /**
103      * Converts this IP range to a list of IpPrefix instances.
104      *
105      * <p>This method outputs the IpPrefix instances for use in the routing architecture.
106      *
107      * <p>For example, the range 192.0.2.4 - 192.0.3.1 converts to the following prefixes:
108      *
109      * <ul>
110      *   <li>192.0.2.128/25
111      *   <li>192.0.2.64/26
112      *   <li>192.0.2.32/27
113      *   <li>192.0.2.16/28
114      *   <li>192.0.2.8/29
115      *   <li>192.0.2.4/30
116      *   <li>192.0.3.0/31
117      * </ul>
118      */
asIpPrefixes()119     public List<IpPrefix> asIpPrefixes() {
120         final boolean isIpv6 = (mStartAddr.length == 16);
121         final List<IpPrefix> result = new ArrayList<>();
122         final Queue<IpPrefix> workingSet = new LinkedList<>();
123 
124         // Start with the any-address. Inet4/6Address.ANY requires compiling against
125         // core-platform-api.
126         workingSet.add(new IpPrefix(isIpv6 ? getAsInetAddress(new byte[16]) /* IPv6_ANY */
127                 : getAsInetAddress(new byte[4]) /* IPv4_ANY */, 0));
128 
129         // While items are still in the queue, test and narrow to subsets.
130         while (!workingSet.isEmpty()) {
131             final IpPrefix workingPrefix = workingSet.poll();
132             final IpRange workingRange = new IpRange(workingPrefix);
133 
134             // If the other range is contained within, it's part of the output. Do not test subsets,
135             // or we will end up with duplicates.
136             if (containsRange(workingRange)) {
137                 result.add(workingPrefix);
138                 continue;
139             }
140 
141             // If there is any overlap, split the working range into it's two subsets, and
142             // reevaluate those.
143             if (overlapsRange(workingRange)) {
144                 workingSet.addAll(getSubsetPrefixes(workingPrefix));
145             }
146         }
147 
148         return result;
149     }
150 
151     /**
152      * Returns the two prefixes that comprise the given prefix.
153      *
154      * <p>For example, for the prefix 192.0.2.0/24, this will return the two prefixes that combined
155      * make up the current prefix:
156      *
157      * <ul>
158      *   <li>192.0.2.0/25
159      *   <li>192.0.2.128/25
160      * </ul>
161      */
getSubsetPrefixes(IpPrefix prefix)162     private static List<IpPrefix> getSubsetPrefixes(IpPrefix prefix) {
163         final List<IpPrefix> result = new ArrayList<>();
164 
165         final int currentPrefixLen = prefix.getPrefixLength();
166         result.add(new IpPrefix(prefix.getAddress(), currentPrefixLen + 1));
167 
168         final byte[] other = prefix.getRawAddress();
169         other[currentPrefixLen / 8] =
170                 (byte) (other[currentPrefixLen / 8] ^ (0x80 >> (currentPrefixLen % 8)));
171         result.add(new IpPrefix(getAsInetAddress(other), currentPrefixLen + 1));
172 
173         return result;
174     }
175 
176     /**
177      * Checks if the other IP range is contained within this one
178      *
179      * <p>Checks based on byte values. For other to be contained within this IP range, other's
180      * starting address must be greater or equal to the current IpRange's starting address, and the
181      * other's ending address must be less than or equal to the current IP range's ending address.
182      */
183     @VisibleForTesting(visibility = Visibility.PRIVATE)
containsRange(IpRange other)184     public boolean containsRange(IpRange other) {
185         return addrToBigInteger(mStartAddr).compareTo(addrToBigInteger(other.mStartAddr)) <= 0
186                 && addrToBigInteger(mEndAddr).compareTo(addrToBigInteger(other.mEndAddr)) >= 0;
187     }
188 
189     /**
190      * Checks if the other IP range overlaps with this one
191      *
192      * <p>Checks based on byte values. For there to be overlap, this IpRange's starting address must
193      * be less than the other's ending address, and vice versa.
194      */
195     @VisibleForTesting(visibility = Visibility.PRIVATE)
overlapsRange(IpRange other)196     public boolean overlapsRange(IpRange other) {
197         return addrToBigInteger(mStartAddr).compareTo(addrToBigInteger(other.mEndAddr)) <= 0
198                 && addrToBigInteger(other.mStartAddr).compareTo(addrToBigInteger(mEndAddr)) <= 0;
199     }
200 
201     @Override
hashCode()202     public int hashCode() {
203         return Objects.hash(mStartAddr, mEndAddr);
204     }
205 
206     @Override
equals(Object obj)207     public boolean equals(Object obj) {
208         if (!(obj instanceof IpRange)) {
209             return false;
210         }
211 
212         final IpRange other = (IpRange) obj;
213         return Arrays.equals(mStartAddr, other.mStartAddr)
214                 && Arrays.equals(mEndAddr, other.mEndAddr);
215     }
216 
217     /** Gets the InetAddress in BigInteger form */
addrToBigInteger(byte[] addr)218     private static BigInteger addrToBigInteger(byte[] addr) {
219         // Since addr.getAddress() returns network byte order (big-endian), it is compatible with
220         // the BigInteger constructor (which assumes big-endian).
221         return new BigInteger(SIGNUM_POSITIVE, addr);
222     }
223 }
224