diff options
Diffstat (limited to 'src/android/net/dhcp/DhcpLeaseRepository.java')
| -rw-r--r-- | src/android/net/dhcp/DhcpLeaseRepository.java | 545 |
1 files changed, 545 insertions, 0 deletions
diff --git a/src/android/net/dhcp/DhcpLeaseRepository.java b/src/android/net/dhcp/DhcpLeaseRepository.java new file mode 100644 index 0000000..0d298de --- /dev/null +++ b/src/android/net/dhcp/DhcpLeaseRepository.java @@ -0,0 +1,545 @@ +/* + * 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.NetworkUtils.inet4AddressToIntHTH; +import static android.net.NetworkUtils.intToInet4AddressHTH; +import static android.net.NetworkUtils.prefixLengthToV4NetmaskIntHTH; +import static android.net.dhcp.DhcpLease.EXPIRATION_NEVER; +import static android.net.dhcp.DhcpLease.inet4AddrToString; + +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(Inet4Address.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"); + } +} |