xref: /packages/modules/Connectivity/Tethering/src/com/android/networkstack/tethering/PrivateAddressCoordinator.java

/*
 * Copyright (C) 2020 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.android.networkstack.tethering;

import static android.net.NetworkCapabilities.TRANSPORT_VPN;
import static android.net.TetheringManager.CONNECTIVITY_SCOPE_GLOBAL;
import static android.net.TetheringManager.CONNECTIVITY_SCOPE_LOCAL;
import static android.net.TetheringManager.TETHERING_BLUETOOTH;
import static android.net.TetheringManager.TETHERING_WIFI_P2P;

import static com.android.net.module.util.Inet4AddressUtils.inet4AddressToIntHTH;
import static com.android.net.module.util.Inet4AddressUtils.intToInet4AddressHTH;
import static com.android.net.module.util.Inet4AddressUtils.prefixLengthToV4NetmaskIntHTH;
import static com.android.networkstack.tethering.util.PrefixUtils.asIpPrefix;

import static java.util.Arrays.asList;

import android.content.Context;
import android.net.ConnectivityManager;
import android.net.IpPrefix;
import android.net.LinkAddress;
import android.net.Network;
import android.net.ip.IpServer;
import android.util.ArrayMap;
import android.util.ArraySet;

import androidx.annotation.NonNull;
import androidx.annotation.Nullable;

import com.android.internal.annotations.VisibleForTesting;
import com.android.internal.util.IndentingPrintWriter;

import java.net.Inet4Address;
import java.net.InetAddress;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

/**
 * This class coordinate IP addresses conflict problem.
 *
 * Tethering downstream IP addresses may conflict with network assigned addresses. This
 * coordinator is responsible for recording all of network assigned addresses and dispatched
 * free address to downstream interfaces.
 *
 * This class is not thread-safe and should be accessed on the same tethering internal thread.
 * @hide
 */
public class PrivateAddressCoordinator {
    public static final int PREFIX_LENGTH = 24;

    // Upstream monitor would be stopped when tethering is down. When tethering restart, downstream
    // address may be requested before coordinator get current upstream notification. To ensure
    // coordinator do not select conflict downstream prefix, mUpstreamPrefixMap would not be cleared
    // when tethering is down. Instead tethering would remove all deprecated upstreams from
    // mUpstreamPrefixMap when tethering is starting. See #maybeRemoveDeprecatedUpstreams().
    private final ArrayMap<Network, List<IpPrefix>> mUpstreamPrefixMap;
    private final ArraySet<IpServer> mDownstreams;
    private static final String LEGACY_WIFI_P2P_IFACE_ADDRESS = "192.168.49.1/24";
    private static final String LEGACY_BLUETOOTH_IFACE_ADDRESS = "192.168.44.1/24";
    private final List<IpPrefix> mTetheringPrefixes;
    private final ConnectivityManager mConnectivityMgr;
    private final TetheringConfiguration mConfig;
    // keyed by downstream type(TetheringManager.TETHERING_*).
    private final ArrayMap<AddressKey, LinkAddress> mCachedAddresses;
    private final Random mRandom;

    public PrivateAddressCoordinator(Context context, TetheringConfiguration config) {
        mDownstreams = new ArraySet<>();
        mUpstreamPrefixMap = new ArrayMap<>();
        mConnectivityMgr = (ConnectivityManager) context.getSystemService(
                Context.CONNECTIVITY_SERVICE);
        mConfig = config;
        mCachedAddresses = new ArrayMap<AddressKey, LinkAddress>();
        // Reserved static addresses for bluetooth and wifi p2p.
        mCachedAddresses.put(new AddressKey(TETHERING_BLUETOOTH, CONNECTIVITY_SCOPE_GLOBAL),
                new LinkAddress(LEGACY_BLUETOOTH_IFACE_ADDRESS));
        mCachedAddresses.put(new AddressKey(TETHERING_WIFI_P2P, CONNECTIVITY_SCOPE_LOCAL),
                new LinkAddress(LEGACY_WIFI_P2P_IFACE_ADDRESS));

        mTetheringPrefixes = new ArrayList<>(Arrays.asList(new IpPrefix("192.168.0.0/16"),
            new IpPrefix("172.16.0.0/12"), new IpPrefix("10.0.0.0/8")));
        mRandom = new Random();
    }

    /**
     * Record a new upstream IpPrefix which may conflict with tethering downstreams.
     * The downstreams will be notified if a conflict is found. When updateUpstreamPrefix is called,
     * UpstreamNetworkState must have an already populated LinkProperties.
     */
    public void updateUpstreamPrefix(final UpstreamNetworkState ns) {
        // Do not support VPN as upstream. Normally, networkCapabilities is not expected to be null,
        // but just checking to be sure.
        if (ns.networkCapabilities != null && ns.networkCapabilities.hasTransport(TRANSPORT_VPN)) {
            removeUpstreamPrefix(ns.network);
            return;
        }

        final ArrayList<IpPrefix> ipv4Prefixes = getIpv4Prefixes(
                ns.linkProperties.getAllLinkAddresses());
        if (ipv4Prefixes.isEmpty()) {
            removeUpstreamPrefix(ns.network);
            return;
        }

        mUpstreamPrefixMap.put(ns.network, ipv4Prefixes);
        handleMaybePrefixConflict(ipv4Prefixes);
    }

    private ArrayList<IpPrefix> getIpv4Prefixes(final List<LinkAddress> linkAddresses) {
        final ArrayList<IpPrefix> list = new ArrayList<>();
        for (LinkAddress address : linkAddresses) {
            if (!address.isIpv4()) continue;

            list.add(asIpPrefix(address));
        }

        return list;
    }

    private void handleMaybePrefixConflict(final List<IpPrefix> prefixes) {
        for (IpServer downstream : mDownstreams) {
            final IpPrefix target = getDownstreamPrefix(downstream);

            for (IpPrefix source : prefixes) {
                if (isConflictPrefix(source, target)) {
                    downstream.sendMessage(IpServer.CMD_NOTIFY_PREFIX_CONFLICT);
                    break;
                }
            }
        }
    }

    /** Remove IpPrefix records corresponding to input network. */
    public void removeUpstreamPrefix(final Network network) {
        mUpstreamPrefixMap.remove(network);
    }

    /**
     * Maybe remove deprecated upstream records, this would be called once tethering started without
     * any exiting tethered downstream.
     */
    public void maybeRemoveDeprecatedUpstreams() {
        if (mUpstreamPrefixMap.isEmpty()) return;

        // Remove all upstreams that are no longer valid networks
        final Set<Network> toBeRemoved = new HashSet<>(mUpstreamPrefixMap.keySet());
        toBeRemoved.removeAll(asList(mConnectivityMgr.getAllNetworks()));

        mUpstreamPrefixMap.removeAll(toBeRemoved);
    }

    /**
     * Pick a random available address and mark its prefix as in use for the provided IpServer,
     * returns null if there is no available address.
     */
    @Nullable
    public LinkAddress requestDownstreamAddress(final IpServer ipServer, final int scope,
            boolean useLastAddress) {
        if (mConfig.shouldEnableWifiP2pDedicatedIp()
                && ipServer.interfaceType() == TETHERING_WIFI_P2P) {
            return new LinkAddress(LEGACY_WIFI_P2P_IFACE_ADDRESS);
        }

        final AddressKey addrKey = new AddressKey(ipServer.interfaceType(), scope);
        // This ensures that tethering isn't started on 2 different interfaces with the same type.
        // Once tethering could support multiple interface with the same type,
        // TetheringSoftApCallback would need to handle it among others.
        final LinkAddress cachedAddress = mCachedAddresses.get(addrKey);
        if (useLastAddress && cachedAddress != null
                && !isConflictWithUpstream(asIpPrefix(cachedAddress))) {
            mDownstreams.add(ipServer);
            return cachedAddress;
        }

        final int prefixIndex = getStartedPrefixIndex();
        for (int i = 0; i < mTetheringPrefixes.size(); i++) {
            final IpPrefix prefixRange = mTetheringPrefixes.get(
                    (prefixIndex + i) % mTetheringPrefixes.size());
            final LinkAddress newAddress = chooseDownstreamAddress(prefixRange);
            if (newAddress != null) {
                mDownstreams.add(ipServer);
                mCachedAddresses.put(addrKey, newAddress);
                return newAddress;
            }
        }

        // No available address.
        return null;
    }

    private int getStartedPrefixIndex() {
        if (!mConfig.isRandomPrefixBaseEnabled()) return 0;

        final int random = getRandomInt() & 0xffffff;
        // This is to select the starting prefix range (/8, /12, or /16) instead of the actual
        // LinkAddress. To avoid complex operations in the selection logic and make the selected
        // rate approximate consistency with that /8 is around 2^4 times of /12 and /12 is around
        // 2^4 times of /16, we simply define a map between the value and the prefix value like
        // this:
        //
        // Value 0 ~ 0xffff (65536/16777216 = 0.39%) -> 192.168.0.0/16
        // Value 0x10000 ~ 0xfffff (983040/16777216 = 5.86%) -> 172.16.0.0/12
        // Value 0x100000 ~ 0xffffff (15728640/16777216 = 93.7%) -> 10.0.0.0/8
        if (random > 0xfffff) {
            return 2;
        } else if (random > 0xffff) {
            return 1;
        } else {
            return 0;
        }
    }

    private int getPrefixBaseAddress(final IpPrefix prefix) {
        return inet4AddressToIntHTH((Inet4Address) prefix.getAddress());
    }

    /**
     * Check whether input prefix conflict with upstream prefixes or in-use downstream prefixes.
     * If yes, return one of them.
     */
    private IpPrefix getConflictPrefix(final IpPrefix prefix) {
        final IpPrefix upstream = getConflictWithUpstream(prefix);
        if (upstream != null) return upstream;

        return getInUseDownstreamPrefix(prefix);
    }

    // Get the next non-conflict sub prefix. E.g: To get next sub prefix from 10.0.0.0/8, if the
    // previously selected prefix is 10.20.42.0/24(subPrefix: 0.20.42.0) and the conflicting prefix
    // is 10.16.0.0/20 (10.16.0.0 ~ 10.16.15.255), then the max address under subPrefix is
    // 0.16.15.255 and the next subPrefix is 0.16.16.255/24 (0.16.15.255 + 0.0.1.0).
    // Note: the sub address 0.0.0.255 here is fine to be any value that it will be replaced as
    // selected random sub address later.
    private int getNextSubPrefix(final IpPrefix conflictPrefix, final int prefixRangeMask) {
        final int suffixMask = ~prefixLengthToV4NetmaskIntHTH(conflictPrefix.getPrefixLength());
        // The largest offset within the prefix assignment block that still conflicts with
        // conflictPrefix.
        final int maxConflict =
                (getPrefixBaseAddress(conflictPrefix) | suffixMask) & ~prefixRangeMask;

        final int prefixMask = prefixLengthToV4NetmaskIntHTH(PREFIX_LENGTH);
        // Pick a sub prefix a full prefix (1 << (32 - PREFIX_LENGTH) addresses) greater than
        // maxConflict. This ensures that the selected prefix never overlaps with conflictPrefix.
        // There is no need to mask the result with PREFIX_LENGTH bits because this is done by
        // findAvailablePrefixFromRange when it constructs the prefix.
        return maxConflict + (1 << (32 - PREFIX_LENGTH));
    }

    private LinkAddress chooseDownstreamAddress(final IpPrefix prefixRange) {
        // The netmask of the prefix assignment block (e.g., 0xfff00000 for 172.16.0.0/12).
        final int prefixRangeMask = prefixLengthToV4NetmaskIntHTH(prefixRange.getPrefixLength());

        // The zero address in the block (e.g., 0xac100000 for 172.16.0.0/12).
        final int baseAddress = getPrefixBaseAddress(prefixRange);

        // The subnet mask corresponding to PREFIX_LENGTH.
        final int prefixMask = prefixLengthToV4NetmaskIntHTH(PREFIX_LENGTH);

        // The offset within prefixRange of a randomly-selected prefix of length PREFIX_LENGTH.
        // This may not be the prefix of the address returned by this method:
        // - If it is already in use, the method will return an address in another prefix.
        // - If all prefixes within prefixRange are in use, the method will return null. For
        // example, for a /24 prefix within 172.26.0.0/12, this will be a multiple of 256 in
        // [0, 1048576). In other words, a random 32-bit number with mask 0x000fff00.
        //
        // prefixRangeMask is required to ensure no wrapping. For example, consider:
        // - prefixRange 127.0.0.0/8
        // - randomPrefixStart 127.255.255.0
        // - A conflicting prefix of 127.255.254.0/23
        // In this case without prefixRangeMask, getNextSubPrefix would return 128.0.0.0, which
        // means the "start < end" check in findAvailablePrefixFromRange would not reject the prefix
        // because Java doesn't have unsigned integers, so 128.0.0.0 = 0x80000000 = -2147483648
        // is less than 127.0.0.0 = 0x7f000000 = 2130706432.
        //
        // Additionally, it makes debug output easier to read by making the numbers smaller.
        final int randomInt = getRandomInt();
        final int randomPrefixStart = randomInt & ~prefixRangeMask & prefixMask;

        // A random offset within the prefix. Used to determine the local address once the prefix
        // is selected. It does not result in an IPv4 address ending in .0, .1, or .255
        // For a PREFIX_LENGTH of 24, this is a number between 2 and 254.
        final int subAddress = getSanitizedSubAddr(randomInt, ~prefixMask);

        // Find a prefix length PREFIX_LENGTH between randomPrefixStart and the end of the block,
        // such that the prefix does not conflict with any upstream.
        IpPrefix downstreamPrefix = findAvailablePrefixFromRange(
                 randomPrefixStart, (~prefixRangeMask) + 1, baseAddress, prefixRangeMask);
        if (downstreamPrefix != null) return getLinkAddress(downstreamPrefix, subAddress);

        // If that failed, do the same, but between 0 and randomPrefixStart.
        downstreamPrefix = findAvailablePrefixFromRange(
                0, randomPrefixStart, baseAddress, prefixRangeMask);

        return getLinkAddress(downstreamPrefix, subAddress);
    }

    private LinkAddress getLinkAddress(final IpPrefix prefix, final int subAddress) {
        if (prefix == null) return null;

        final InetAddress address = intToInet4AddressHTH(getPrefixBaseAddress(prefix) | subAddress);
        return new LinkAddress(address, PREFIX_LENGTH);
    }

    private IpPrefix findAvailablePrefixFromRange(final int start, final int end,
            final int baseAddress, final int prefixRangeMask) {
        int newSubPrefix = start;
        while (newSubPrefix < end) {
            final InetAddress address = intToInet4AddressHTH(baseAddress | newSubPrefix);
            final IpPrefix prefix = new IpPrefix(address, PREFIX_LENGTH);

            final IpPrefix conflictPrefix = getConflictPrefix(prefix);

            if (conflictPrefix == null) return prefix;

            newSubPrefix = getNextSubPrefix(conflictPrefix, prefixRangeMask);
        }

        return null;
    }

    /** Get random int which could be used to generate random address. */
    @VisibleForTesting
    public int getRandomInt() {
        return mRandom.nextInt();
    }

    /** Get random subAddress and avoid selecting x.x.x.0, x.x.x.1 and x.x.x.255 address. */
    private int getSanitizedSubAddr(final int randomInt, final int subAddrMask) {
        final int randomSubAddr = randomInt & subAddrMask;
        // If prefix length > 30, the selecting speace would be less than 4 which may be hard to
        // avoid 3 consecutive address.
        if (PREFIX_LENGTH > 30) return randomSubAddr;

        // TODO: maybe it is not necessary to avoid .0, .1 and .255 address because tethering
        // address would not be conflicted. This code only works because PREFIX_LENGTH is not longer
        // than 24
        final int candidate = randomSubAddr & 0xff;
        if (candidate == 0 || candidate == 1 || candidate == 255) {
            return (randomSubAddr & 0xfffffffc) + 2;
        }

        return randomSubAddr;
    }

    /** Release downstream record for IpServer. */
    public void releaseDownstream(final IpServer ipServer) {
        mDownstreams.remove(ipServer);
    }

    /** Clear current upstream prefixes records. */
    public void clearUpstreamPrefixes() {
        mUpstreamPrefixMap.clear();
    }

    private IpPrefix getConflictWithUpstream(final IpPrefix prefix) {
        for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
            final List<IpPrefix> list = mUpstreamPrefixMap.valueAt(i);
            for (IpPrefix upstream : list) {
                if (isConflictPrefix(prefix, upstream)) return upstream;
            }
        }
        return null;
    }

    private boolean isConflictWithUpstream(final IpPrefix prefix) {
        return getConflictWithUpstream(prefix) != null;
    }

    private boolean isConflictPrefix(final IpPrefix prefix1, final IpPrefix prefix2) {
        if (prefix2.getPrefixLength() < prefix1.getPrefixLength()) {
            return prefix2.contains(prefix1.getAddress());
        }

        return prefix1.contains(prefix2.getAddress());
    }

    // InUse Prefixes are prefixes of mCachedAddresses which are active downstream addresses, last
    // downstream addresses(reserved for next time) and static addresses(e.g. bluetooth, wifi p2p).
    private IpPrefix getInUseDownstreamPrefix(final IpPrefix prefix) {
        for (int i = 0; i < mCachedAddresses.size(); i++) {
            final IpPrefix downstream = asIpPrefix(mCachedAddresses.valueAt(i));
            if (isConflictPrefix(prefix, downstream)) return downstream;
        }

        // IpServer may use manually-defined address (mStaticIpv4ServerAddr) which does not include
        // in mCachedAddresses.
        for (IpServer downstream : mDownstreams) {
            final IpPrefix target = getDownstreamPrefix(downstream);

            if (isConflictPrefix(prefix, target)) return target;
        }

        return null;
    }

    @NonNull
    private IpPrefix getDownstreamPrefix(final IpServer downstream) {
        final LinkAddress address = downstream.getAddress();

        return asIpPrefix(address);
    }

    private static class AddressKey {
        private final int mTetheringType;
        private final int mScope;

        private AddressKey(int type, int scope) {
            mTetheringType = type;
            mScope = scope;
        }

        @Override
        public int hashCode() {
            return (mTetheringType << 16) + mScope;
        }

        @Override
        public boolean equals(@Nullable Object obj) {
            if (!(obj instanceof AddressKey)) return false;
            final AddressKey other = (AddressKey) obj;

            return mTetheringType == other.mTetheringType && mScope == other.mScope;
        }

        @Override
        public String toString() {
            return "AddressKey(" + mTetheringType + ", " + mScope + ")";
        }
    }

    void dump(final IndentingPrintWriter pw) {
        pw.println("mTetheringPrefixes:");
        pw.increaseIndent();
        for (IpPrefix prefix : mTetheringPrefixes) {
            pw.println(prefix);
        }
        pw.decreaseIndent();

        pw.println("mUpstreamPrefixMap:");
        pw.increaseIndent();
        for (int i = 0; i < mUpstreamPrefixMap.size(); i++) {
            pw.println(mUpstreamPrefixMap.keyAt(i) + " - " + mUpstreamPrefixMap.valueAt(i));
        }
        pw.decreaseIndent();

        pw.println("mDownstreams:");
        pw.increaseIndent();
        for (IpServer ipServer : mDownstreams) {
            pw.println(ipServer.interfaceType() + " - " + ipServer.getAddress());
        }
        pw.decreaseIndent();

        pw.println("mCachedAddresses:");
        pw.increaseIndent();
        for (int i = 0; i < mCachedAddresses.size(); i++) {
            pw.println(mCachedAddresses.keyAt(i) + " - " + mCachedAddresses.valueAt(i));
        }
        pw.decreaseIndent();
    }
}