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 com.android.networkstack.tethering; 18 19 import static android.system.OsConstants.ETH_P_IPV6; 20 21 import static com.android.networkstack.tethering.util.TetheringUtils.getTetheringJniLibraryName; 22 23 import static org.junit.Assert.assertEquals; 24 import static org.junit.Assert.assertFalse; 25 import static org.junit.Assert.assertNotEquals; 26 import static org.junit.Assert.assertNotNull; 27 import static org.junit.Assert.assertNull; 28 import static org.junit.Assert.assertThrows; 29 import static org.junit.Assert.assertTrue; 30 import static org.junit.Assert.fail; 31 import static org.junit.Assume.assumeTrue; 32 33 import android.net.MacAddress; 34 import android.os.Build; 35 import android.os.SystemClock; 36 import android.system.ErrnoException; 37 import android.system.Os; 38 import android.system.OsConstants; 39 import android.util.ArrayMap; 40 41 import com.android.net.module.util.BpfMap; 42 import com.android.net.module.util.SingleWriterBpfMap; 43 import com.android.testutils.DevSdkIgnoreRule.IgnoreUpTo; 44 import com.android.testutils.DevSdkIgnoreRunner; 45 46 import org.junit.Before; 47 import org.junit.BeforeClass; 48 import org.junit.Test; 49 import org.junit.runner.RunWith; 50 import org.junit.runners.Parameterized; 51 52 import java.io.File; 53 import java.net.InetAddress; 54 import java.nio.file.Files; 55 import java.nio.file.Path; 56 import java.util.Arrays; 57 import java.util.Collection; 58 import java.util.NoSuchElementException; 59 import java.util.Random; 60 import java.util.concurrent.CompletableFuture; 61 import java.util.concurrent.TimeUnit; 62 import java.util.concurrent.atomic.AtomicInteger; 63 64 65 @RunWith(DevSdkIgnoreRunner.class) 66 @IgnoreUpTo(Build.VERSION_CODES.R) 67 public final class BpfMapTest { 68 // Sync from packages/modules/Connectivity/bpf_progs/offload.c. 69 private static final int TEST_MAP_SIZE = 16; 70 private static final String TETHER_DOWNSTREAM6_FS_PATH = 71 "/sys/fs/bpf/tethering/map_test_tether_downstream6_map"; 72 private static final String TETHER2_DOWNSTREAM6_FS_PATH = 73 "/sys/fs/bpf/tethering/map_test_tether2_downstream6_map"; 74 private static final String TETHER3_DOWNSTREAM6_FS_PATH = 75 "/sys/fs/bpf/tethering/map_test_tether3_downstream6_map"; 76 77 private ArrayMap<TetherDownstream6Key, Tether6Value> mTestData; 78 79 private BpfMap<TetherDownstream6Key, Tether6Value> mTestMap; 80 81 private final boolean mShouldTestSingleWriterMap; 82 83 @Parameterized.Parameters shouldTestSingleWriterMap()84 public static Collection<Boolean> shouldTestSingleWriterMap() { 85 return Arrays.asList(true, false); 86 } 87 BpfMapTest(boolean shouldTestSingleWriterMap)88 public BpfMapTest(boolean shouldTestSingleWriterMap) { 89 mShouldTestSingleWriterMap = shouldTestSingleWriterMap; 90 } 91 92 @BeforeClass setupOnce()93 public static void setupOnce() { 94 System.loadLibrary(getTetheringJniLibraryName()); 95 } 96 97 @Before setUp()98 public void setUp() throws Exception { 99 mTestData = new ArrayMap<>(); 100 mTestData.put(createTetherDownstream6Key(101, "00:00:00:00:00:aa", "2001:db8::1"), 101 createTether6Value(11, "00:00:00:00:00:0a", "11:11:11:00:00:0b", 102 ETH_P_IPV6, 1280)); 103 mTestData.put(createTetherDownstream6Key(102, "00:00:00:00:00:bb", "2001:db8::2"), 104 createTether6Value(22, "00:00:00:00:00:0c", "22:22:22:00:00:0d", 105 ETH_P_IPV6, 1400)); 106 mTestData.put(createTetherDownstream6Key(103, "00:00:00:00:00:cc", "2001:db8::3"), 107 createTether6Value(33, "00:00:00:00:00:0e", "33:33:33:00:00:0f", 108 ETH_P_IPV6, 1500)); 109 110 initTestMap(); 111 } 112 openTestMap()113 private BpfMap<TetherDownstream6Key, Tether6Value> openTestMap() throws Exception { 114 return mShouldTestSingleWriterMap 115 ? SingleWriterBpfMap.getSingleton(TETHER2_DOWNSTREAM6_FS_PATH, 116 TetherDownstream6Key.class, Tether6Value.class) 117 : new BpfMap<>(TETHER_DOWNSTREAM6_FS_PATH, TetherDownstream6Key.class, 118 Tether6Value.class); 119 } 120 initTestMap()121 private void initTestMap() throws Exception { 122 mTestMap = openTestMap(); 123 mTestMap.forEach((key, value) -> { 124 try { 125 assertTrue(mTestMap.deleteEntry(key)); 126 } catch (ErrnoException e) { 127 fail("Fail to delete the key " + key + ": " + e); 128 } 129 }); 130 assertNull(mTestMap.getFirstKey()); 131 assertTrue(mTestMap.isEmpty()); 132 } 133 createTetherDownstream6Key(int iif, String mac, String address)134 private TetherDownstream6Key createTetherDownstream6Key(int iif, String mac, 135 String address) throws Exception { 136 final MacAddress dstMac = MacAddress.fromString(mac); 137 final InetAddress ipv6Address = InetAddress.getByName(address); 138 139 return new TetherDownstream6Key(iif, dstMac, ipv6Address.getAddress()); 140 } 141 createTether6Value(int oif, String src, String dst, int proto, int pmtu)142 private Tether6Value createTether6Value(int oif, String src, String dst, int proto, int pmtu) { 143 final MacAddress srcMac = MacAddress.fromString(src); 144 final MacAddress dstMac = MacAddress.fromString(dst); 145 146 return new Tether6Value(oif, dstMac, srcMac, proto, pmtu); 147 } 148 149 @Test testGetFd()150 public void testGetFd() throws Exception { 151 try (BpfMap readOnlyMap = new BpfMap<>(TETHER_DOWNSTREAM6_FS_PATH, BpfMap.BPF_F_RDONLY, 152 TetherDownstream6Key.class, Tether6Value.class)) { 153 assertNotNull(readOnlyMap); 154 try { 155 readOnlyMap.insertEntry(mTestData.keyAt(0), mTestData.valueAt(0)); 156 fail("Writing RO map should throw ErrnoException"); 157 } catch (ErrnoException expected) { 158 assertEquals(OsConstants.EPERM, expected.errno); 159 } 160 } 161 try (BpfMap writeOnlyMap = new BpfMap<>(TETHER3_DOWNSTREAM6_FS_PATH, BpfMap.BPF_F_WRONLY, 162 TetherDownstream6Key.class, Tether6Value.class)) { 163 assertNotNull(writeOnlyMap); 164 try { 165 writeOnlyMap.getFirstKey(); 166 fail("Reading WO map should throw ErrnoException"); 167 } catch (ErrnoException expected) { 168 assertEquals(OsConstants.EPERM, expected.errno); 169 } 170 } 171 try (BpfMap readWriteMap = new BpfMap<>(TETHER_DOWNSTREAM6_FS_PATH, 172 TetherDownstream6Key.class, Tether6Value.class)) { 173 assertNotNull(readWriteMap); 174 } 175 } 176 177 @Test testIsEmpty()178 public void testIsEmpty() throws Exception { 179 assertNull(mTestMap.getFirstKey()); 180 assertTrue(mTestMap.isEmpty()); 181 182 mTestMap.insertEntry(mTestData.keyAt(0), mTestData.valueAt(0)); 183 assertFalse(mTestMap.isEmpty()); 184 185 mTestMap.deleteEntry((mTestData.keyAt(0))); 186 assertTrue(mTestMap.isEmpty()); 187 } 188 189 @Test testGetFirstKey()190 public void testGetFirstKey() throws Exception { 191 // getFirstKey on an empty map returns null. 192 assertFalse(mTestMap.containsKey(mTestData.keyAt(0))); 193 assertNull(mTestMap.getFirstKey()); 194 assertNull(mTestMap.getValue(mTestData.keyAt(0))); 195 196 // getFirstKey on a non-empty map returns the first key. 197 mTestMap.insertEntry(mTestData.keyAt(0), mTestData.valueAt(0)); 198 assertEquals(mTestData.keyAt(0), mTestMap.getFirstKey()); 199 } 200 201 @Test testGetNextKey()202 public void testGetNextKey() throws Exception { 203 // [1] If the passed-in key is not found on empty map, return null. 204 final TetherDownstream6Key nonexistentKey = 205 createTetherDownstream6Key(1234, "00:00:00:00:00:01", "2001:db8::10"); 206 assertNull(mTestMap.getNextKey(nonexistentKey)); 207 208 // [2] If the passed-in key is null on empty map, throw NullPointerException. 209 try { 210 mTestMap.getNextKey(null); 211 fail("Getting next key with null key should throw NullPointerException"); 212 } catch (NullPointerException expected) { } 213 214 // The BPF map has one entry now. 215 final ArrayMap<TetherDownstream6Key, Tether6Value> resultMap = 216 new ArrayMap<>(); 217 mTestMap.insertEntry(mTestData.keyAt(0), mTestData.valueAt(0)); 218 resultMap.put(mTestData.keyAt(0), mTestData.valueAt(0)); 219 220 // [3] If the passed-in key is the last key, return null. 221 // Because there is only one entry in the map, the first key equals the last key. 222 final TetherDownstream6Key lastKey = mTestMap.getFirstKey(); 223 assertNull(mTestMap.getNextKey(lastKey)); 224 225 // The BPF map has two entries now. 226 mTestMap.insertEntry(mTestData.keyAt(1), mTestData.valueAt(1)); 227 resultMap.put(mTestData.keyAt(1), mTestData.valueAt(1)); 228 229 // [4] If the passed-in key is found, return the next key. 230 TetherDownstream6Key nextKey = mTestMap.getFirstKey(); 231 while (nextKey != null) { 232 if (resultMap.remove(nextKey).equals(nextKey)) { 233 fail("Unexpected result: " + nextKey); 234 } 235 nextKey = mTestMap.getNextKey(nextKey); 236 } 237 assertTrue(resultMap.isEmpty()); 238 239 // [5] If the passed-in key is not found on non-empty map, return the first key. 240 assertEquals(mTestMap.getFirstKey(), mTestMap.getNextKey(nonexistentKey)); 241 242 // [6] If the passed-in key is null on non-empty map, throw NullPointerException. 243 try { 244 mTestMap.getNextKey(null); 245 fail("Getting next key with null key should throw NullPointerException"); 246 } catch (NullPointerException expected) { } 247 } 248 249 @Test testUpdateEntry()250 public void testUpdateEntry() throws Exception { 251 final TetherDownstream6Key key = mTestData.keyAt(0); 252 final Tether6Value value = mTestData.valueAt(0); 253 final Tether6Value value2 = mTestData.valueAt(1); 254 assertFalse(mTestMap.deleteEntry(key)); 255 256 // updateEntry will create an entry if it does not exist already. 257 mTestMap.updateEntry(key, value); 258 assertTrue(mTestMap.containsKey(key)); 259 final Tether6Value result = mTestMap.getValue(key); 260 assertEquals(value, result); 261 262 // updateEntry will update an entry that already exists. 263 mTestMap.updateEntry(key, value2); 264 assertTrue(mTestMap.containsKey(key)); 265 final Tether6Value result2 = mTestMap.getValue(key); 266 assertEquals(value2, result2); 267 268 assertTrue(mTestMap.deleteEntry(key)); 269 assertFalse(mTestMap.containsKey(key)); 270 } 271 272 @Test testInsertOrReplaceEntry()273 public void testInsertOrReplaceEntry() throws Exception { 274 final TetherDownstream6Key key = mTestData.keyAt(0); 275 final Tether6Value value = mTestData.valueAt(0); 276 final Tether6Value value2 = mTestData.valueAt(1); 277 assertFalse(mTestMap.deleteEntry(key)); 278 279 // insertOrReplaceEntry will create an entry if it does not exist already. 280 assertTrue(mTestMap.insertOrReplaceEntry(key, value)); 281 assertTrue(mTestMap.containsKey(key)); 282 final Tether6Value result = mTestMap.getValue(key); 283 assertEquals(value, result); 284 285 // updateEntry will update an entry that already exists. 286 assertFalse(mTestMap.insertOrReplaceEntry(key, value2)); 287 assertTrue(mTestMap.containsKey(key)); 288 final Tether6Value result2 = mTestMap.getValue(key); 289 assertEquals(value2, result2); 290 291 assertTrue(mTestMap.deleteEntry(key)); 292 assertFalse(mTestMap.containsKey(key)); 293 } 294 295 @Test testInsertReplaceEntry()296 public void testInsertReplaceEntry() throws Exception { 297 final TetherDownstream6Key key = mTestData.keyAt(0); 298 final Tether6Value value = mTestData.valueAt(0); 299 final Tether6Value value2 = mTestData.valueAt(1); 300 301 try { 302 mTestMap.replaceEntry(key, value); 303 fail("Replacing non-existent key " + key + " should throw NoSuchElementException"); 304 } catch (NoSuchElementException expected) { } 305 assertFalse(mTestMap.containsKey(key)); 306 307 mTestMap.insertEntry(key, value); 308 assertTrue(mTestMap.containsKey(key)); 309 final Tether6Value result = mTestMap.getValue(key); 310 assertEquals(value, result); 311 try { 312 mTestMap.insertEntry(key, value); 313 fail("Inserting existing key " + key + " should throw IllegalStateException"); 314 } catch (IllegalStateException expected) { } 315 316 mTestMap.replaceEntry(key, value2); 317 assertTrue(mTestMap.containsKey(key)); 318 final Tether6Value result2 = mTestMap.getValue(key); 319 assertEquals(value2, result2); 320 } 321 322 @Test testIterateBpfMap()323 public void testIterateBpfMap() throws Exception { 324 final ArrayMap<TetherDownstream6Key, Tether6Value> resultMap = 325 new ArrayMap<>(mTestData); 326 327 for (int i = 0; i < resultMap.size(); i++) { 328 mTestMap.insertEntry(resultMap.keyAt(i), resultMap.valueAt(i)); 329 } 330 331 mTestMap.forEach((key, value) -> { 332 if (!value.equals(resultMap.remove(key))) { 333 fail("Unexpected result: " + key + ", value: " + value); 334 } 335 }); 336 assertTrue(resultMap.isEmpty()); 337 } 338 339 @Test testIterateEmptyMap()340 public void testIterateEmptyMap() throws Exception { 341 // Can't use an int because variables used in a lambda must be final. 342 final AtomicInteger count = new AtomicInteger(); 343 mTestMap.forEach((key, value) -> count.incrementAndGet()); 344 // Expect that the consumer was never called. 345 assertEquals(0, count.get()); 346 } 347 348 @Test testIterateDeletion()349 public void testIterateDeletion() throws Exception { 350 final ArrayMap<TetherDownstream6Key, Tether6Value> resultMap = 351 new ArrayMap<>(mTestData); 352 353 for (int i = 0; i < resultMap.size(); i++) { 354 mTestMap.insertEntry(resultMap.keyAt(i), resultMap.valueAt(i)); 355 } 356 357 // Can't use an int because variables used in a lambda must be final. 358 final AtomicInteger count = new AtomicInteger(); 359 mTestMap.forEach((key, value) -> { 360 try { 361 assertTrue(mTestMap.deleteEntry(key)); 362 } catch (ErrnoException e) { 363 fail("Fail to delete key " + key + ": " + e); 364 } 365 if (!value.equals(resultMap.remove(key))) { 366 fail("Unexpected result: " + key + ", value: " + value); 367 } 368 count.incrementAndGet(); 369 }); 370 assertEquals(3, count.get()); 371 assertTrue(resultMap.isEmpty()); 372 assertNull(mTestMap.getFirstKey()); 373 } 374 375 @Test testClear()376 public void testClear() throws Exception { 377 // Clear an empty map. 378 assertTrue(mTestMap.isEmpty()); 379 mTestMap.clear(); 380 381 // Clear a map with some data in it. 382 final ArrayMap<TetherDownstream6Key, Tether6Value> resultMap = 383 new ArrayMap<>(mTestData); 384 for (int i = 0; i < resultMap.size(); i++) { 385 mTestMap.insertEntry(resultMap.keyAt(i), resultMap.valueAt(i)); 386 } 387 assertFalse(mTestMap.isEmpty()); 388 mTestMap.clear(); 389 assertTrue(mTestMap.isEmpty()); 390 } 391 392 @Test testMapContentsCorrectOnOpen()393 public void testMapContentsCorrectOnOpen() throws Exception { 394 final BpfMap<TetherDownstream6Key, Tether6Value> map1, map2; 395 396 map1 = openTestMap(); 397 map1.clear(); 398 for (int i = 0; i < mTestData.size(); i++) { 399 map1.insertEntry(mTestData.keyAt(i), mTestData.valueAt(i)); 400 } 401 402 // We can't close and reopen map1, because close does nothing. Open another map instead. 403 map2 = openTestMap(); 404 for (int i = 0; i < mTestData.size(); i++) { 405 assertEquals(mTestData.valueAt(i), map2.getValue(mTestData.keyAt(i))); 406 } 407 408 map1.clear(); 409 } 410 411 @Test testInsertOverflow()412 public void testInsertOverflow() throws Exception { 413 final ArrayMap<TetherDownstream6Key, Tether6Value> testData = 414 new ArrayMap<>(); 415 416 // Build test data for TEST_MAP_SIZE + 1 entries. 417 for (int i = 1; i <= TEST_MAP_SIZE + 1; i++) { 418 testData.put( 419 createTetherDownstream6Key(i, "00:00:00:00:00:01", "2001:db8::1"), 420 createTether6Value(100, "de:ad:be:ef:00:01", "de:ad:be:ef:00:02", 421 ETH_P_IPV6, 1500)); 422 } 423 424 // Insert #TEST_MAP_SIZE test entries to the map. The map has reached the limit. 425 for (int i = 0; i < TEST_MAP_SIZE; i++) { 426 mTestMap.insertEntry(testData.keyAt(i), testData.valueAt(i)); 427 } 428 429 // The map won't allow inserting any more entries. 430 try { 431 mTestMap.insertEntry(testData.keyAt(TEST_MAP_SIZE), testData.valueAt(TEST_MAP_SIZE)); 432 fail("Writing too many entries should throw ErrnoException"); 433 } catch (ErrnoException expected) { 434 // Expect that can't insert the entry anymore because the number of elements in the 435 // map reached the limit. See man-pages/bpf. 436 assertEquals(OsConstants.E2BIG, expected.errno); 437 } 438 } 439 440 @Test testOpenNonexistentMap()441 public void testOpenNonexistentMap() throws Exception { 442 try { 443 final BpfMap<TetherDownstream6Key, Tether6Value> nonexistentMap = new BpfMap<>( 444 "/sys/fs/bpf/tethering/nonexistent", 445 TetherDownstream6Key.class, Tether6Value.class); 446 } catch (ErrnoException expected) { 447 assertEquals(OsConstants.ENOENT, expected.errno); 448 } 449 } 450 getNumOpenBpfMapFds()451 private static int getNumOpenBpfMapFds() throws Exception { 452 int numFds = 0; 453 File[] openFiles = new File("/proc/self/fd").listFiles(); 454 for (int i = 0; i < openFiles.length; i++) { 455 final Path path = openFiles[i].toPath(); 456 if (!Files.isSymbolicLink(path)) continue; 457 if ("anon_inode:bpf-map".equals(Files.readSymbolicLink(path).toString())) { 458 numFds++; 459 } 460 } 461 assertNotEquals("Couldn't find any BPF map fds opened by this process", 0, numFds); 462 return numFds; 463 } 464 465 @Test testNoFdLeaks()466 public void testNoFdLeaks() throws Exception { 467 // Due to #setUp has called #initTestMap to open map and BpfMap is using persistent fd 468 // cache, expect that the fd amount is not increased in the iterations. 469 // See the comment of BpfMap#close. 470 final int iterations = 1000; 471 final int before = getNumOpenBpfMapFds(); 472 for (int i = 0; i < iterations; i++) { 473 try (BpfMap<TetherDownstream6Key, Tether6Value> map = new BpfMap<>( 474 TETHER_DOWNSTREAM6_FS_PATH, 475 TetherDownstream6Key.class, Tether6Value.class)) { 476 // do nothing 477 } 478 } 479 final int after = getNumOpenBpfMapFds(); 480 481 // Check that the number of open fds is the same as before. 482 assertEquals("Fd leak after " + iterations + " iterations: ", before, after); 483 } 484 485 @Test testNullKey()486 public void testNullKey() { 487 assertThrows(NullPointerException.class, () -> 488 mTestMap.insertOrReplaceEntry(null, mTestData.valueAt(0))); 489 } 490 runBenchmarkThread(BpfMap<TetherDownstream6Key, Tether6Value> map, CompletableFuture<Integer> future, int runtimeMs)491 private void runBenchmarkThread(BpfMap<TetherDownstream6Key, Tether6Value> map, 492 CompletableFuture<Integer> future, int runtimeMs) { 493 int numReads = 0; 494 final Random r = new Random(); 495 final long start = SystemClock.elapsedRealtime(); 496 final long stop = start + runtimeMs; 497 while (SystemClock.elapsedRealtime() < stop) { 498 try { 499 final Tether6Value v = map.getValue(mTestData.keyAt(r.nextInt(mTestData.size()))); 500 assertNotNull(v); 501 numReads++; 502 } catch (Exception e) { 503 future.completeExceptionally(e); 504 return; 505 } 506 } 507 future.complete(numReads); 508 } 509 510 @Test testSingleWriterCacheEffectiveness()511 public void testSingleWriterCacheEffectiveness() throws Exception { 512 assumeTrue(mShouldTestSingleWriterMap); 513 // Benchmark parameters. 514 final int timeoutMs = 5_000; // Only hit if threads don't complete. 515 final int benchmarkTimeMs = 2_000; 516 final int minReads = 50; 517 // Local testing on cuttlefish suggests that caching is ~10x faster. 518 // Only require 3x to reduce test flakiness. 519 final int expectedSpeedup = 3; 520 521 final BpfMap cachedMap = SingleWriterBpfMap.getSingleton(TETHER2_DOWNSTREAM6_FS_PATH, 522 TetherDownstream6Key.class, Tether6Value.class); 523 final BpfMap uncachedMap = new BpfMap(TETHER_DOWNSTREAM6_FS_PATH, 524 TetherDownstream6Key.class, Tether6Value.class); 525 526 // Ensure the maps are not empty. 527 for (int i = 0; i < mTestData.size(); i++) { 528 cachedMap.insertEntry(mTestData.keyAt(i), mTestData.valueAt(i)); 529 uncachedMap.insertEntry(mTestData.keyAt(i), mTestData.valueAt(i)); 530 } 531 532 final CompletableFuture<Integer> cachedResult = new CompletableFuture<>(); 533 final CompletableFuture<Integer> uncachedResult = new CompletableFuture<>(); 534 535 new Thread(() -> runBenchmarkThread(uncachedMap, uncachedResult, benchmarkTimeMs)).start(); 536 new Thread(() -> runBenchmarkThread(cachedMap, cachedResult, benchmarkTimeMs)).start(); 537 538 final int cached = cachedResult.get(timeoutMs, TimeUnit.MILLISECONDS); 539 final int uncached = uncachedResult.get(timeoutMs, TimeUnit.MILLISECONDS); 540 541 // Uncomment to see benchmark results. 542 // fail("Cached " + cached + ", uncached " + uncached + ": " + cached / uncached +"x"); 543 544 assertTrue("Less than " + minReads + "cached reads observed", cached > minReads); 545 assertTrue("Less than " + minReads + "uncached reads observed", uncached > minReads); 546 assertTrue("Cached map not at least " + expectedSpeedup + "x faster", 547 cached > expectedSpeedup * uncached); 548 } 549 } 550