From 3171dbf96c53a68745dd09c44b94ffd51aaef9a6 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Fri, 24 Jun 2022 17:30:40 +0000 Subject: LockSettingsStorage: fix user prefetching The user prefetching logic doesn't work as intended, for two reasons: - The key that Cache.setFetched() sets differs from the key that Cache.isFetched() looks for, so Cache.isFetched() always returns false. So, LockSettingsStorage.prefetchUser() always runs for a user when called, rather than just once per boot as intended. Fix this by making Cache.setFetched() use the same key as Cache.isFetched(). - Since Cache.putIfUnchanged() increments Cache.mVersion, only the first call to it within LockSettingsStorage.prefetchUser() has any effect. So only the first key-value pair for the user is prefetched, not all of them as intended. Fix this by making Cache.putIfUnchanged() *not* increment mVersion, as the backing storage isn't being modified. Found by code review; these bugs aren't known to have been causing any real-world problems. Test: atest --iterations 50 LockSettingsStorageTests Change-Id: Ife97ba855d014d8e291d46f6a702a41b28bd5707 --- .../server/locksettings/LockSettingsStorage.java | 47 +++++++++++++++------- .../locksettings/LockSettingsStorageTests.java | 14 ++++++- 2 files changed, 44 insertions(+), 17 deletions(-) diff --git a/services/core/java/com/android/server/locksettings/LockSettingsStorage.java b/services/core/java/com/android/server/locksettings/LockSettingsStorage.java index 9ddf1efbaef2..a77cc5d8d5fd 100644 --- a/services/core/java/com/android/server/locksettings/LockSettingsStorage.java +++ b/services/core/java/com/android/server/locksettings/LockSettingsStorage.java @@ -201,6 +201,16 @@ class LockSettingsStorage extends WatchableImpl { return result == DEFAULT ? defaultValue : (String) result; } + @VisibleForTesting + boolean isKeyValueCached(String key, int userId) { + return mCache.hasKeyValue(key, userId); + } + + @VisibleForTesting + boolean isUserPrefetched(int userId) { + return mCache.isFetched(userId); + } + @VisibleForTesting public void removeKey(String key, int userId) { removeKey(mOpenHelper.getWritableDatabase(), key, userId); @@ -762,19 +772,24 @@ class LockSettingsStorage extends WatchableImpl { } } - /** - * Cache consistency model: - * - Writes to storage write directly to the cache, but this MUST happen within the atomic - * section either provided by the database transaction or mWriteLock, such that writes to the - * cache and writes to the backing storage are guaranteed to occur in the same order + /* + * A cache for the following types of data: * - * - Reads can populate the cache, but because they are no strong ordering guarantees with - * respect to writes this precaution is taken: - * - The cache is assigned a version number that increases every time the cache is modified. - * Reads from backing storage can only populate the cache if the backing storage - * has not changed since the load operation has begun. - * This guarantees that no read operation can shadow a write to the cache that happens - * after it had begun. + * - Key-value entries from the locksettings database, where the key is the combination of a + * userId and a string key, and the value is a string. + * - File paths to file contents. + * - The per-user "prefetched" flag. + * + * Cache consistency model: + * - Writes to storage write directly to the cache, but this MUST happen within an atomic + * section either provided by the database transaction or mFileWriteLock, such that writes to + * the cache and writes to the backing storage are guaranteed to occur in the same order. + * - Reads can populate the cache, but because there are no strong ordering guarantees with + * respect to writes the following precaution is taken: The cache is assigned a version + * number that increases every time the backing storage is modified. Reads from backing + * storage can only populate the cache if the backing storage has not changed since the load + * operation has begun. This guarantees that a read operation can't clobber a different value + * that was written to the cache by a concurrent write operation. */ private static class Cache { private final ArrayMap mCache = new ArrayMap<>(); @@ -819,7 +834,7 @@ class LockSettingsStorage extends WatchableImpl { } void setFetched(int userId) { - put(CacheKey.TYPE_FETCHED, "isFetched", "true", userId); + put(CacheKey.TYPE_FETCHED, "", "true", userId); } boolean isFetched(int userId) { @@ -831,7 +846,7 @@ class LockSettingsStorage extends WatchableImpl { } private synchronized void put(int type, String key, Object value, int userId) { - // Create a new CachKey here because it may be saved in the map if the key is absent. + // Create a new CacheKey here because it may be saved in the map if the key is absent. mCache.put(new CacheKey().set(type, key, userId), value); mVersion++; } @@ -839,7 +854,9 @@ class LockSettingsStorage extends WatchableImpl { private synchronized void putIfUnchanged(int type, String key, Object value, int userId, int version) { if (!contains(type, key, userId) && mVersion == version) { - put(type, key, value, userId); + mCache.put(new CacheKey().set(type, key, userId), value); + // Don't increment mVersion, as this method should only be called in cases where the + // backing storage isn't being modified. } } diff --git a/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java b/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java index 609c05c040c2..15bbb10c6a1e 100644 --- a/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java +++ b/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java @@ -232,12 +232,22 @@ public class LockSettingsStorageTests { @Test public void testPrefetch() { - mStorage.writeKeyValue("key", "toBeFetched", 0); + mStorage.writeKeyValue("key1", "value1", 0); + mStorage.writeKeyValue("key2", "value2", 0); mStorage.clearCache(); + + assertFalse(mStorage.isUserPrefetched(0)); + assertFalse(mStorage.isKeyValueCached("key1", 0)); + assertFalse(mStorage.isKeyValueCached("key2", 0)); + mStorage.prefetchUser(0); - assertEquals("toBeFetched", mStorage.readKeyValue("key", "default", 0)); + assertTrue(mStorage.isUserPrefetched(0)); + assertTrue(mStorage.isKeyValueCached("key1", 0)); + assertTrue(mStorage.isKeyValueCached("key2", 0)); + assertEquals("value1", mStorage.readKeyValue("key1", "default", 0)); + assertEquals("value2", mStorage.readKeyValue("key2", "default", 0)); } @Test -- cgit v1.2.3-59-g8ed1b From 1826b3e94d11da55e6c6984565dcc59dd2c2c400 Mon Sep 17 00:00:00 2001 From: Eric Biggers Date: Fri, 24 Jun 2022 17:31:51 +0000 Subject: LockSettingsStorage: fix concurrent read clobbering a removal Since Cache.remove() doesn't increment mVersion, the key removal can be clobbered by a concurrent read that loads the key into the cache. Fix this by making Cache.remove() increment mVersion, indicating that the backing storage has been modified. Found by code review; this bug isn't known to have been causing any real-world problems. Add a best-effort test for this, though due to the very tight race needed, it didn't reproduce the bug in 2000 iterations. However, it reproduced the bug in just a few iterations if a 1 millisecond sleep is added in the right place (just before the call to Cache.putKeyValueIfUnchanged() in LockSettingsStorage.readKeyValue()). Test: atest --iterations 50 LockSettingsStorageTests Change-Id: I960cc386ecd040af7517d3d62a3eefe57a518620 --- .../server/locksettings/LockSettingsStorage.java | 1 + .../locksettings/LockSettingsStorageTests.java | 56 ++++++++++++++++++++-- 2 files changed, 54 insertions(+), 3 deletions(-) diff --git a/services/core/java/com/android/server/locksettings/LockSettingsStorage.java b/services/core/java/com/android/server/locksettings/LockSettingsStorage.java index a77cc5d8d5fd..8161503652ff 100644 --- a/services/core/java/com/android/server/locksettings/LockSettingsStorage.java +++ b/services/core/java/com/android/server/locksettings/LockSettingsStorage.java @@ -843,6 +843,7 @@ class LockSettingsStorage extends WatchableImpl { private synchronized void remove(int type, String key, int userId) { mCache.remove(mCacheKey.set(type, key, userId)); + mVersion++; } private synchronized void put(int type, String key, Object value, int userId) { diff --git a/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java b/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java index 15bbb10c6a1e..c4df05149d4b 100644 --- a/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java +++ b/services/tests/servicestests/src/com/android/server/locksettings/LockSettingsStorageTests.java @@ -19,6 +19,7 @@ package com.android.server.locksettings; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertNotNull; +import static org.junit.Assert.assertNull; import static org.junit.Assert.assertSame; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; @@ -60,7 +61,10 @@ import java.io.File; import java.util.ArrayList; import java.util.Arrays; import java.util.List; +import java.util.concurrent.BrokenBarrierException; import java.util.concurrent.CountDownLatch; +import java.util.concurrent.CyclicBarrier; +import java.util.concurrent.atomic.AtomicReference; /** * atest FrameworksServicesTests:LockSettingsStorageTests @@ -137,12 +141,12 @@ public class LockSettingsStorageTests { } @Test - public void testKeyValue_Concurrency() { + public void testKeyValue_ReadWriteConcurrency() { final CountDownLatch latch = new CountDownLatch(1); List threads = new ArrayList<>(); for (int i = 0; i < 100; i++) { final int threadId = i; - threads.add(new Thread("testKeyValue_Concurrency_" + i) { + threads.add(new Thread("testKeyValue_ReadWriteConcurrency_" + i) { @Override public void run() { try { @@ -164,7 +168,7 @@ public class LockSettingsStorageTests { }); threads.get(i).start(); } - mStorage.writeKeyValue("key", "initalValue", 0); + mStorage.writeKeyValue("key", "initialValue", 0); latch.countDown(); joinAll(threads, 10000); assertEquals('5', mStorage.readKeyValue("key", "default", 0).charAt(0)); @@ -172,6 +176,52 @@ public class LockSettingsStorageTests { assertEquals('5', mStorage.readKeyValue("key", "default", 0).charAt(0)); } + // Test that readKeyValue() doesn't pollute the cache when run concurrently with removeKey(). + @Test + @SuppressWarnings("AssertionFailureIgnored") // intentional try-catch of AssertionError + public void testKeyValue_ReadRemoveConcurrency() { + final int numThreads = 2; + final int numIterations = 50; + final CyclicBarrier barrier = new CyclicBarrier(numThreads); + final List threads = new ArrayList<>(); + final AtomicReference failure = new AtomicReference<>(); + for (int threadId = 0; threadId < numThreads; threadId++) { + final boolean isWriter = (threadId == 0); + threads.add(new Thread("testKeyValue_ReadRemoveConcurrency_" + threadId) { + @Override + public void run() { + try { + for (int iter = 0; iter < numIterations; iter++) { + if (isWriter) { + mStorage.writeKeyValue("key", "value", 0); + mStorage.clearCache(); + } + barrier.await(); + if (isWriter) { + mStorage.removeKey("key", 0); + } else { + mStorage.readKeyValue("key", "default", 0); + } + barrier.await(); + try { + assertEquals("default", mStorage.readKeyValue("key", "default", 0)); + } catch (AssertionError e) { + failure.compareAndSet(null, e); + } + barrier.await(); + } + } catch (InterruptedException | BrokenBarrierException e) { + failure.compareAndSet(null, e); + return; + } + } + }); + threads.get(threadId).start(); + } + joinAll(threads, 60000); + assertNull(failure.get()); + } + @Test public void testKeyValue_CacheStarvedWriter() { final CountDownLatch latch = new CountDownLatch(1); -- cgit v1.2.3-59-g8ed1b