path: root/src/android/net/dhcp/DhcpLeaseRepository.java

/*
 * Copyright (C) 2018 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 android.net.dhcp;

import static android.net.dhcp.DhcpLease.EXPIRATION_NEVER;
import static android.net.dhcp.DhcpLease.inet4AddrToString;
import static android.net.shared.Inet4AddressUtils.inet4AddressToIntHTH;
import static android.net.shared.Inet4AddressUtils.intToInet4AddressHTH;
import static android.net.shared.Inet4AddressUtils.prefixLengthToV4NetmaskIntHTH;

import static com.android.server.util.NetworkStackConstants.IPV4_ADDR_ANY;
import static com.android.server.util.NetworkStackConstants.IPV4_ADDR_BITS;

import static java.lang.Math.min;

import android.annotation.NonNull;
import android.annotation.Nullable;
import android.net.IpPrefix;
import android.net.MacAddress;
import android.net.dhcp.DhcpServer.Clock;
import android.net.util.SharedLog;
import android.util.ArrayMap;

import java.net.Inet4Address;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
import java.util.function.Function;

/**
 * A repository managing IPv4 address assignments through DHCPv4.
 *
 * <p>This class is not thread-safe. All public methods should be called on a common thread or
 * use some synchronization mechanism.
 *
 * <p>Methods are optimized for a small number of allocated leases, assuming that most of the time
 * only 2~10 addresses will be allocated, which is the common case. Managing a large number of
 * addresses is supported but will be slower: some operations have complexity in O(num_leases).
 * @hide
 */
class DhcpLeaseRepository {
    public static final byte[] CLIENTID_UNSPEC = null;
    public static final Inet4Address INETADDR_UNSPEC = null;

    @NonNull
    private final SharedLog mLog;
    @NonNull
    private final Clock mClock;

    @NonNull
    private IpPrefix mPrefix;
    @NonNull
    private Set<Inet4Address> mReservedAddrs;
    private int mSubnetAddr;
    private int mSubnetMask;
    private int mNumAddresses;
    private long mLeaseTimeMs;

    /**
     * Next timestamp when committed or declined leases should be checked for expired ones. This
     * will always be lower than or equal to the time for the first lease to expire: it's OK not to
     * update this when removing entries, but it must always be updated when adding/updating.
     */
    private long mNextExpirationCheck = EXPIRATION_NEVER;

    static class DhcpLeaseException extends Exception {
        DhcpLeaseException(String message) {
            super(message);
        }
    }

    static class OutOfAddressesException extends DhcpLeaseException {
        OutOfAddressesException(String message) {
            super(message);
        }
    }

    static class InvalidAddressException extends DhcpLeaseException {
        InvalidAddressException(String message) {
            super(message);
        }
    }

    static class InvalidSubnetException extends DhcpLeaseException {
        InvalidSubnetException(String message) {
            super(message);
        }
    }

    /**
     * Leases by IP address
     */
    private final ArrayMap<Inet4Address, DhcpLease> mCommittedLeases = new ArrayMap<>();

    /**
     * Map address -> expiration timestamp in ms. Addresses are guaranteed to be valid as defined
     * by {@link #isValidAddress(Inet4Address)}, but are not necessarily otherwise available for
     * assignment.
     */
    private final LinkedHashMap<Inet4Address, Long> mDeclinedAddrs = new LinkedHashMap<>();

    DhcpLeaseRepository(@NonNull IpPrefix prefix, @NonNull Set<Inet4Address> reservedAddrs,
            long leaseTimeMs, @NonNull SharedLog log, @NonNull Clock clock) {
        updateParams(prefix, reservedAddrs, leaseTimeMs);
        mLog = log;
        mClock = clock;
    }

    public void updateParams(@NonNull IpPrefix prefix, @NonNull Set<Inet4Address> reservedAddrs,
            long leaseTimeMs) {
        mPrefix = prefix;
        mReservedAddrs = Collections.unmodifiableSet(new HashSet<>(reservedAddrs));
        mSubnetMask = prefixLengthToV4NetmaskIntHTH(prefix.getPrefixLength());
        mSubnetAddr = inet4AddressToIntHTH((Inet4Address) prefix.getAddress()) & mSubnetMask;
        mNumAddresses = 1 << (IPV4_ADDR_BITS - prefix.getPrefixLength());
        mLeaseTimeMs = leaseTimeMs;

        cleanMap(mCommittedLeases);
        cleanMap(mDeclinedAddrs);
    }

    /**
     * From a map keyed by {@link Inet4Address}, remove entries where the key is invalid (as
     * specified by {@link #isValidAddress(Inet4Address)}), or is a reserved address.
     */
    private <T> void cleanMap(Map<Inet4Address, T> map) {
        final Iterator<Entry<Inet4Address, T>> it = map.entrySet().iterator();
        while (it.hasNext()) {
            final Inet4Address addr = it.next().getKey();
            if (!isValidAddress(addr) || mReservedAddrs.contains(addr)) {
                it.remove();
            }
        }
    }

    /**
     * Get a DHCP offer, to reply to a DHCPDISCOVER. Follows RFC2131 #4.3.1.
     *
     * @param clientId Client identifier option if specified, or {@link #CLIENTID_UNSPEC}
     * @param relayAddr Internet address of the relay (giaddr), can be {@link Inet4Address#ANY}
     * @param reqAddr Requested address by the client (option 50), or {@link #INETADDR_UNSPEC}
     * @param hostname Client-provided hostname, or {@link DhcpLease#HOSTNAME_NONE}
     * @throws OutOfAddressesException The server does not have any available address
     * @throws InvalidSubnetException The lease was requested from an unsupported subnet
     */
    @NonNull
    public DhcpLease getOffer(@Nullable byte[] clientId, @NonNull MacAddress hwAddr,
            @NonNull Inet4Address relayAddr, @Nullable Inet4Address reqAddr,
            @Nullable String hostname) throws OutOfAddressesException, InvalidSubnetException {
        final long currentTime = mClock.elapsedRealtime();
        final long expTime = currentTime + mLeaseTimeMs;

        removeExpiredLeases(currentTime);
        checkValidRelayAddr(relayAddr);

        final DhcpLease currentLease = findByClient(clientId, hwAddr);
        final DhcpLease newLease;
        if (currentLease != null) {
            newLease = currentLease.renewedLease(expTime, hostname);
            mLog.log("Offering extended lease " + newLease);
            // Do not update lease time in the map: the offer is not committed yet.
        } else if (reqAddr != null && isValidAddress(reqAddr) && isAvailable(reqAddr)) {
            newLease = new DhcpLease(clientId, hwAddr, reqAddr, expTime, hostname);
            mLog.log("Offering requested lease " + newLease);
        } else {
            newLease = makeNewOffer(clientId, hwAddr, expTime, hostname);
            mLog.log("Offering new generated lease " + newLease);
        }
        return newLease;
    }

    private void checkValidRelayAddr(@Nullable Inet4Address relayAddr)
            throws InvalidSubnetException {
        // As per #4.3.1, addresses are assigned based on the relay address if present. This
        // implementation only assigns addresses if the relayAddr is inside our configured subnet.
        // This also applies when the client requested a specific address for consistency between
        // requests, and with older behavior.
        if (isIpAddrOutsidePrefix(mPrefix, relayAddr)) {
            throw new InvalidSubnetException("Lease requested by relay from outside of subnet");
        }
    }

    private static boolean isIpAddrOutsidePrefix(@NonNull IpPrefix prefix,
            @Nullable Inet4Address addr) {
        return addr != null && !addr.equals(IPV4_ADDR_ANY) && !prefix.contains(addr);
    }

    @Nullable
    private DhcpLease findByClient(@Nullable byte[] clientId, @NonNull MacAddress hwAddr) {
        for (DhcpLease lease : mCommittedLeases.values()) {
            if (lease.matchesClient(clientId, hwAddr)) {
                return lease;
            }
        }

        // Note this differs from dnsmasq behavior, which would match by hwAddr if clientId was
        // given but no lease keyed on clientId matched. This would prevent one interface from
        // obtaining multiple leases with different clientId.
        return null;
    }

    /**
     * Make a lease conformant to a client DHCPREQUEST or renew the client's existing lease,
     * commit it to the repository and return it.
     *
     * <p>This method always succeeds and commits the lease if it does not throw, and has no side
     * effects if it throws.
     *
     * @param clientId Client identifier option if specified, or {@link #CLIENTID_UNSPEC}
     * @param reqAddr Requested address by the client (option 50), or {@link #INETADDR_UNSPEC}
     * @param sidSet Whether the server identifier was set in the request
     * @return The newly created or renewed lease
     * @throws InvalidAddressException The client provided an address that conflicts with its
     *                                 current configuration, or other committed/reserved leases.
     */
    @NonNull
    public DhcpLease requestLease(@Nullable byte[] clientId, @NonNull MacAddress hwAddr,
            @NonNull Inet4Address clientAddr, @NonNull Inet4Address relayAddr,
            @Nullable Inet4Address reqAddr, boolean sidSet, @Nullable String hostname)
            throws InvalidAddressException, InvalidSubnetException {
        final long currentTime = mClock.elapsedRealtime();
        removeExpiredLeases(currentTime);
        checkValidRelayAddr(relayAddr);
        final DhcpLease assignedLease = findByClient(clientId, hwAddr);

        final Inet4Address leaseAddr = reqAddr != null ? reqAddr : clientAddr;
        if (assignedLease != null) {
            if (sidSet && reqAddr != null) {
                // Client in SELECTING state; remove any current lease before creating a new one.
                mCommittedLeases.remove(assignedLease.getNetAddr());
            } else if (!assignedLease.getNetAddr().equals(leaseAddr)) {
                // reqAddr null (RENEWING/REBINDING): client renewing its own lease for clientAddr.
                // reqAddr set with sid not set (INIT-REBOOT): client verifying configuration.
                // In both cases, throw if clientAddr or reqAddr does not match the known lease.
                throw new InvalidAddressException("Incorrect address for client in "
                        + (reqAddr != null ? "INIT-REBOOT" : "RENEWING/REBINDING"));
            }
        }

        // In the init-reboot case, RFC2131 #4.3.2 says that the server must not reply if
        // assignedLease == null, but dnsmasq will let the client use the requested address if
        // available, when configured with --dhcp-authoritative. This is preferable to avoid issues
        // if the server lost the lease DB: the client would not get a reply because the server
        // does not know their lease.
        // Similarly in RENEWING/REBINDING state, create a lease when possible if the
        // client-provided lease is unknown.
        final DhcpLease lease =
                checkClientAndMakeLease(clientId, hwAddr, leaseAddr, hostname, currentTime);
        mLog.logf("DHCPREQUEST assignedLease %s, reqAddr=%s, sidSet=%s: created/renewed lease %s",
                assignedLease, inet4AddrToString(reqAddr), sidSet, lease);
        return lease;
    }

    /**
     * Check that the client can request the specified address, make or renew the lease if yes, and
     * commit it.
     *
     * <p>This method always succeeds and returns the lease if it does not throw, and has no
     * side-effect if it throws.
     *
     * @return The newly created or renewed, committed lease
     * @throws InvalidAddressException The client provided an address that conflicts with its
     *                                 current configuration, or other committed/reserved leases.
     */
    private DhcpLease checkClientAndMakeLease(@Nullable byte[] clientId, @NonNull MacAddress hwAddr,
            @NonNull Inet4Address addr, @Nullable String hostname, long currentTime)
            throws InvalidAddressException {
        final long expTime = currentTime + mLeaseTimeMs;
        final DhcpLease currentLease = mCommittedLeases.getOrDefault(addr, null);
        if (currentLease != null && !currentLease.matchesClient(clientId, hwAddr)) {
            throw new InvalidAddressException("Address in use");
        }

        final DhcpLease lease;
        if (currentLease == null) {
            if (isValidAddress(addr) && !mReservedAddrs.contains(addr)) {
                lease = new DhcpLease(clientId, hwAddr, addr, expTime, hostname);
            } else {
                throw new InvalidAddressException("Lease not found and address unavailable");
            }
        } else {
            lease = currentLease.renewedLease(expTime, hostname);
        }
        commitLease(lease);
        return lease;
    }

    private void commitLease(@NonNull DhcpLease lease) {
        mCommittedLeases.put(lease.getNetAddr(), lease);
        maybeUpdateEarliestExpiration(lease.getExpTime());
    }

    /**
     * Delete a committed lease from the repository.
     *
     * @return true if a lease matching parameters was found.
     */
    public boolean releaseLease(@Nullable byte[] clientId, @NonNull MacAddress hwAddr,
            @NonNull Inet4Address addr) {
        final DhcpLease currentLease = mCommittedLeases.getOrDefault(addr, null);
        if (currentLease == null) {
            mLog.w("Could not release unknown lease for " + inet4AddrToString(addr));
            return false;
        }
        if (currentLease.matchesClient(clientId, hwAddr)) {
            mCommittedLeases.remove(addr);
            mLog.log("Released lease " + currentLease);
            return true;
        }
        mLog.w(String.format("Not releasing lease %s: does not match client (cid %s, hwAddr %s)",
                currentLease, DhcpLease.clientIdToString(clientId), hwAddr));
        return false;
    }

    public void markLeaseDeclined(@NonNull Inet4Address addr) {
        if (mDeclinedAddrs.containsKey(addr) || !isValidAddress(addr)) {
            mLog.logf("Not marking %s as declined: already declined or not assignable",
                    inet4AddrToString(addr));
            return;
        }
        final long expTime = mClock.elapsedRealtime() + mLeaseTimeMs;
        mDeclinedAddrs.put(addr, expTime);
        mLog.logf("Marked %s as declined expiring %d", inet4AddrToString(addr), expTime);
        maybeUpdateEarliestExpiration(expTime);
    }

    /**
     * Get the list of currently valid committed leases in the repository.
     */
    @NonNull
    public List<DhcpLease> getCommittedLeases() {
        removeExpiredLeases(mClock.elapsedRealtime());
        return new ArrayList<>(mCommittedLeases.values());
    }

    /**
     * Get the set of addresses that have been marked as declined in the repository.
     */
    @NonNull
    public Set<Inet4Address> getDeclinedAddresses() {
        removeExpiredLeases(mClock.elapsedRealtime());
        return new HashSet<>(mDeclinedAddrs.keySet());
    }

    /**
     * Given the expiration time of a new committed lease or declined address, update
     * {@link #mNextExpirationCheck} so it stays lower than or equal to the time for the first lease
     * to expire.
     */
    private void maybeUpdateEarliestExpiration(long expTime) {
        if (expTime < mNextExpirationCheck) {
            mNextExpirationCheck = expTime;
        }
    }

    /**
     * Remove expired entries from a map keyed by {@link Inet4Address}.
     *
     * @param tag Type of lease in the map, for logging
     * @param getExpTime Functor returning the expiration time for an object in the map.
     *                   Must not return null.
     * @return The lowest expiration time among entries remaining in the map
     */
    private <T> long removeExpired(long currentTime, @NonNull Map<Inet4Address, T> map,
            @NonNull String tag, @NonNull Function<T, Long> getExpTime) {
        final Iterator<Entry<Inet4Address, T>> it = map.entrySet().iterator();
        long firstExpiration = EXPIRATION_NEVER;
        while (it.hasNext()) {
            final Entry<Inet4Address, T> lease = it.next();
            final long expTime = getExpTime.apply(lease.getValue());
            if (expTime <= currentTime) {
                mLog.logf("Removing expired %s lease for %s (expTime=%s, currentTime=%s)",
                        tag, lease.getKey(), expTime, currentTime);
                it.remove();
            } else {
                firstExpiration = min(firstExpiration, expTime);
            }
        }
        return firstExpiration;
    }

    /**
     * Go through committed and declined leases and remove the expired ones.
     */
    private void removeExpiredLeases(long currentTime) {
        if (currentTime < mNextExpirationCheck) {
            return;
        }

        final long commExp = removeExpired(
                currentTime, mCommittedLeases, "committed", DhcpLease::getExpTime);
        final long declExp = removeExpired(
                currentTime, mDeclinedAddrs, "declined", Function.identity());

        mNextExpirationCheck = min(commExp, declExp);
    }

    private boolean isAvailable(@NonNull Inet4Address addr) {
        return !mReservedAddrs.contains(addr) && !mCommittedLeases.containsKey(addr);
    }

    /**
     * Get the 0-based index of an address in the subnet.
     *
     * <p>Given ordering of addresses 5.6.7.8 < 5.6.7.9 < 5.6.8.0, the index on a subnet is defined
     * so that the first address is 0, the second 1, etc. For example on a /16, 192.168.0.0 -> 0,
     * 192.168.0.1 -> 1, 192.168.1.0 -> 256
     *
     */
    private int getAddrIndex(int addr) {
        return addr & ~mSubnetMask;
    }

    private int getAddrByIndex(int index) {
        return mSubnetAddr | index;
    }

    /**
     * Get a valid address starting from the supplied one.
     *
     * <p>This only checks that the address is numerically valid for assignment, not whether it is
     * already in use. The return value is always inside the configured prefix, even if the supplied
     * address is not.
     *
     * <p>If the provided address is valid, it is returned as-is. Otherwise, the next valid
     * address (with the ordering in {@link #getAddrIndex(int)}) is returned.
     */
    private int getValidAddress(int addr) {
        final int lastByteMask = 0xff;
        int addrIndex = getAddrIndex(addr); // 0-based index of the address in the subnet

        // Some OSes do not handle addresses in .255 or .0 correctly: avoid those.
        final int lastByte = getAddrByIndex(addrIndex) & lastByteMask;
        if (lastByte == lastByteMask) {
            // Avoid .255 address, and .0 address that follows
            addrIndex = (addrIndex + 2) % mNumAddresses;
        } else if (lastByte == 0) {
            // Avoid .0 address
            addrIndex = (addrIndex + 1) % mNumAddresses;
        }

        // Do not use first or last address of range
        if (addrIndex == 0 || addrIndex == mNumAddresses - 1) {
            // Always valid and not end of range since prefixLength is at most 30 in serving params
            addrIndex = 1;
        }
        return getAddrByIndex(addrIndex);
    }

    /**
     * Returns whether the address is in the configured subnet and part of the assignable range.
     */
    private boolean isValidAddress(Inet4Address addr) {
        final int intAddr = inet4AddressToIntHTH(addr);
        return getValidAddress(intAddr) == intAddr;
    }

    private int getNextAddress(int addr) {
        final int addrIndex = getAddrIndex(addr);
        final int nextAddress = getAddrByIndex((addrIndex + 1) % mNumAddresses);
        return getValidAddress(nextAddress);
    }

    /**
     * Calculate a first candidate address for a client by hashing the hardware address.
     *
     * <p>This will be a valid address as checked by {@link #getValidAddress(int)}, but may be
     * in use.
     *
     * @return An IPv4 address encoded as 32-bit int
     */
    private int getFirstClientAddress(MacAddress hwAddr) {
        // This follows dnsmasq behavior. Advantages are: clients will often get the same
        // offers for different DISCOVER even if the lease was not yet accepted or has expired,
        // and address generation will generally not need to loop through many allocated addresses
        // until it finds a free one.
        int hash = 0;
        for (byte b : hwAddr.toByteArray()) {
            hash += b + (b << 8) + (b << 16);
        }
        // This implementation will not always result in the same IPs as dnsmasq would give out in
        // Android <= P, because it includes invalid and reserved addresses in mNumAddresses while
        // the configured ranges for dnsmasq did not.
        final int addrIndex = hash % mNumAddresses;
        return getValidAddress(getAddrByIndex(addrIndex));
    }

    /**
     * Create a lease that can be offered to respond to a client DISCOVER.
     *
     * <p>This method always succeeds and returns the lease if it does not throw. If no non-declined
     * address is available, it will try to offer the oldest declined address if valid.
     *
     * @throws OutOfAddressesException The server has no address left to offer
     */
    private DhcpLease makeNewOffer(@Nullable byte[] clientId, @NonNull MacAddress hwAddr,
            long expTime, @Nullable String hostname) throws OutOfAddressesException {
        int intAddr = getFirstClientAddress(hwAddr);
        // Loop until a free address is found, or there are no more addresses.
        // There is slightly less than this many usable addresses, but some extra looping is OK
        for (int i = 0; i < mNumAddresses; i++) {
            final Inet4Address addr = intToInet4AddressHTH(intAddr);
            if (isAvailable(addr) && !mDeclinedAddrs.containsKey(addr)) {
                return new DhcpLease(clientId, hwAddr, addr, expTime, hostname);
            }
            intAddr = getNextAddress(intAddr);
        }

        // Try freeing DECLINEd addresses if out of addresses.
        final Iterator<Inet4Address> it = mDeclinedAddrs.keySet().iterator();
        while (it.hasNext()) {
            final Inet4Address addr = it.next();
            it.remove();
            mLog.logf("Out of addresses in address pool: dropped declined addr %s",
                    inet4AddrToString(addr));
            // isValidAddress() is always verified for entries in mDeclinedAddrs.
            // However declined addresses may have been requested (typically by the machine that was
            // already using the address) after being declined.
            if (isAvailable(addr)) {
                return new DhcpLease(clientId, hwAddr, addr, expTime, hostname);
            }
        }

        throw new OutOfAddressesException("No address available for offer");
    }
}