Revert "Revert "SettingsProvider enhanced cache""

This reverts commit b8d8b9332e94351e6d9e0b8ec713a17ba55ab8be.

Reason for revert: Reland with change

The change is to make all pre-defined settings cache-able regardless if
they exist or not. For example, if Launcher repeatedly queries a
predefined but unset setting like show_hidden_icon_apps_enabled, it
doesn't need to repeatedly do binder calls.

This also fixes the test failure that caused the first revert.

BUG: 228619157
Test: atest com.android.providers.settings.GenerationRegistryTest
Test: atest com.android.wm.shell.flicker.splitscreen.CopyContentInSplit
Change-Id: I83cf6177d1a05d0025f1392c39c76bbf58fdc8a3
diff --git a/core/java/android/provider/Settings.java b/core/java/android/provider/Settings.java
index 54e4909..7656332 100644
--- a/core/java/android/provider/Settings.java
+++ b/core/java/android/provider/Settings.java
@@ -116,6 +116,7 @@
 import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.Executor;
+import java.util.function.Consumer;
 
 /**
  * The Settings provider contains global system-level device preferences.
@@ -2978,19 +2979,22 @@
     }
 
     private static final class GenerationTracker {
-        private final MemoryIntArray mArray;
-        private final Runnable mErrorHandler;
+        @NonNull private final String mName;
+        @NonNull private final MemoryIntArray mArray;
+        @NonNull private final Consumer<String> mErrorHandler;
         private final int mIndex;
         private int mCurrentGeneration;
 
-        public GenerationTracker(@NonNull MemoryIntArray array, int index,
-                int generation, Runnable errorHandler) {
+        GenerationTracker(@NonNull String name, @NonNull MemoryIntArray array, int index,
+                int generation, Consumer<String> errorHandler) {
+            mName = name;
             mArray = array;
             mIndex = index;
             mErrorHandler = errorHandler;
             mCurrentGeneration = generation;
         }
 
+        // This method also updates the obsolete generation code stored locally
         public boolean isGenerationChanged() {
             final int currentGeneration = readCurrentGeneration();
             if (currentGeneration >= 0) {
@@ -3011,9 +3015,7 @@
                 return mArray.get(mIndex);
             } catch (IOException e) {
                 Log.e(TAG, "Error getting current generation", e);
-                if (mErrorHandler != null) {
-                    mErrorHandler.run();
-                }
+                mErrorHandler.accept(mName);
             }
             return -1;
         }
@@ -3023,9 +3025,6 @@
                 mArray.close();
             } catch (IOException e) {
                 Log.e(TAG, "Error closing backing array", e);
-                if (mErrorHandler != null) {
-                    mErrorHandler.run();
-                }
             }
         }
     }
@@ -3088,8 +3087,21 @@
         private final ArraySet<String> mAllFields;
         private final ArrayMap<String, Integer> mReadableFieldsWithMaxTargetSdk;
 
+        // Mapping from the name of a setting (or the prefix of a namespace) to a generation tracker
         @GuardedBy("this")
-        private GenerationTracker mGenerationTracker;
+        private ArrayMap<String, GenerationTracker> mGenerationTrackers = new ArrayMap<>();
+
+        private Consumer<String> mGenerationTrackerErrorHandler = (String name) -> {
+            synchronized (NameValueCache.this) {
+                Log.e(TAG, "Error accessing generation tracker - removing");
+                final GenerationTracker tracker = mGenerationTrackers.get(name);
+                if (tracker != null) {
+                    tracker.destroy();
+                    mGenerationTrackers.remove(name);
+                }
+                mValues.remove(name);
+            }
+        };
 
         <T extends NameValueTable> NameValueCache(Uri uri, String getCommand,
                 String setCommand, String deleteCommand, ContentProviderHolder providerHolder,
@@ -3178,6 +3190,43 @@
 
         @UnsupportedAppUsage
         public String getStringForUser(ContentResolver cr, String name, final int userHandle) {
+            final boolean isSelf = (userHandle == UserHandle.myUserId());
+            int currentGeneration = -1;
+            boolean needsGenerationTracker = false;
+
+            if (isSelf) {
+                synchronized (NameValueCache.this) {
+                    final GenerationTracker generationTracker = mGenerationTrackers.get(name);
+                    if (generationTracker != null) {
+                        if (generationTracker.isGenerationChanged()) {
+                            if (DEBUG) {
+                                Log.i(TAG, "Generation changed for setting:" + name
+                                        + " type:" + mUri.getPath()
+                                        + " in package:" + cr.getPackageName()
+                                        + " and user:" + userHandle);
+                            }
+                            mValues.remove(name);
+                        } else if (mValues.containsKey(name)) {
+                            if (DEBUG) {
+                                Log.i(TAG, "Cache hit for setting:" + name);
+                            }
+                            return mValues.get(name);
+                        }
+                        currentGeneration = generationTracker.getCurrentGeneration();
+                    } else {
+                        needsGenerationTracker = true;
+                    }
+                }
+            } else {
+                if (DEBUG || LOCAL_LOGV) {
+                    Log.v(TAG, "get setting for user " + userHandle
+                            + " by user " + UserHandle.myUserId() + " so skipping cache");
+                }
+            }
+            if (DEBUG) {
+                Log.i(TAG, "Cache miss for setting:" + name + " for user:" + userHandle);
+            }
+
             // Check if the target settings key is readable. Reject if the caller is not system and
             // is trying to access a settings key defined in the Settings.Secure, Settings.System or
             // Settings.Global and is not annotated as @Readable.
@@ -3211,31 +3260,6 @@
                 }
             }
 
-            final boolean isSelf = (userHandle == UserHandle.myUserId());
-            int currentGeneration = -1;
-            if (isSelf) {
-                synchronized (NameValueCache.this) {
-                    if (mGenerationTracker != null) {
-                        if (mGenerationTracker.isGenerationChanged()) {
-                            if (DEBUG) {
-                                Log.i(TAG, "Generation changed for type:"
-                                        + mUri.getPath() + " in package:"
-                                        + cr.getPackageName() +" and user:" + userHandle);
-                            }
-                            mValues.clear();
-                        } else if (mValues.containsKey(name)) {
-                            return mValues.get(name);
-                        }
-                        if (mGenerationTracker != null) {
-                            currentGeneration = mGenerationTracker.getCurrentGeneration();
-                        }
-                    }
-                }
-            } else {
-                if (LOCAL_LOGV) Log.v(TAG, "get setting for user " + userHandle
-                        + " by user " + UserHandle.myUserId() + " so skipping cache");
-            }
-
             IContentProvider cp = mProviderHolder.getProvider(cr);
 
             // Try the fast path first, not using query().  If this
@@ -3244,24 +3268,17 @@
             // interface.
             if (mCallGetCommand != null) {
                 try {
-                    Bundle args = null;
+                    Bundle args = new Bundle();
                     if (!isSelf) {
-                        args = new Bundle();
                         args.putInt(CALL_METHOD_USER_KEY, userHandle);
                     }
-                    boolean needsGenerationTracker = false;
-                    synchronized (NameValueCache.this) {
-                        if (isSelf && mGenerationTracker == null) {
-                            needsGenerationTracker = true;
-                            if (args == null) {
-                                args = new Bundle();
-                            }
-                            args.putString(CALL_METHOD_TRACK_GENERATION_KEY, null);
-                            if (DEBUG) {
-                                Log.i(TAG, "Requested generation tracker for type: "+ mUri.getPath()
-                                        + " in package:" + cr.getPackageName() +" and user:"
-                                        + userHandle);
-                            }
+                    if (needsGenerationTracker) {
+                        args.putString(CALL_METHOD_TRACK_GENERATION_KEY, null);
+                        if (DEBUG) {
+                            Log.i(TAG, "Requested generation tracker for setting:" + name
+                                    + " type:" + mUri.getPath()
+                                    + " in package:" + cr.getPackageName()
+                                    + " and user:" + userHandle);
                         }
                     }
                     Bundle b;
@@ -3298,33 +3315,24 @@
                                         final int generation = b.getInt(
                                                 CALL_METHOD_GENERATION_KEY, 0);
                                         if (DEBUG) {
-                                            Log.i(TAG, "Received generation tracker for type:"
-                                                    + mUri.getPath() + " in package:"
-                                                    + cr.getPackageName() + " and user:"
-                                                    + userHandle + " with index:" + index);
+                                            Log.i(TAG, "Received generation tracker for setting:"
+                                                    + name
+                                                    + " type:" + mUri.getPath()
+                                                    + " in package:" + cr.getPackageName()
+                                                    + " and user:" + userHandle
+                                                    + " with index:" + index);
                                         }
-                                        if (mGenerationTracker != null) {
-                                            mGenerationTracker.destroy();
-                                        }
-                                        mGenerationTracker = new GenerationTracker(array, index,
-                                                generation, () -> {
-                                            synchronized (NameValueCache.this) {
-                                                Log.e(TAG, "Error accessing generation"
-                                                        + " tracker - removing");
-                                                if (mGenerationTracker != null) {
-                                                    GenerationTracker generationTracker =
-                                                            mGenerationTracker;
-                                                    mGenerationTracker = null;
-                                                    generationTracker.destroy();
-                                                    mValues.clear();
-                                                }
-                                            }
-                                        });
+                                        mGenerationTrackers.put(name, new GenerationTracker(name,
+                                                array, index, generation,
+                                                mGenerationTrackerErrorHandler));
                                         currentGeneration = generation;
                                     }
                                 }
-                                if (mGenerationTracker != null && currentGeneration ==
-                                        mGenerationTracker.getCurrentGeneration()) {
+                                if (mGenerationTrackers.get(name) != null && currentGeneration
+                                        == mGenerationTrackers.get(name).getCurrentGeneration()) {
+                                    if (DEBUG) {
+                                        Log.i(TAG, "Updating cache for setting:" + name);
+                                    }
                                     mValues.put(name, value);
                                 }
                             }
@@ -3367,15 +3375,14 @@
 
                 String value = c.moveToNext() ? c.getString(0) : null;
                 synchronized (NameValueCache.this) {
-                    if (mGenerationTracker != null
-                            && currentGeneration == mGenerationTracker.getCurrentGeneration()) {
+                    if (mGenerationTrackers.get(name) != null && currentGeneration
+                            == mGenerationTrackers.get(name).getCurrentGeneration()) {
+                        if (DEBUG) {
+                            Log.i(TAG, "Updating cache for setting:" + name + " using query");
+                        }
                         mValues.put(name, value);
                     }
                 }
-                if (LOCAL_LOGV) {
-                    Log.v(TAG, "cache miss [" + mUri.getLastPathSegment() + "]: " +
-                            name + " = " + (value == null ? "(null)" : value));
-                }
                 return value;
             } catch (RemoteException e) {
                 Log.w(TAG, "Can't get key " + name + " from " + mUri, e);
@@ -3409,18 +3416,29 @@
             Config.enforceReadPermission(namespace);
             ArrayMap<String, String> keyValues = new ArrayMap<>();
             int currentGeneration = -1;
+            boolean needsGenerationTracker = false;
 
             synchronized (NameValueCache.this) {
-                if (mGenerationTracker != null) {
-                    if (mGenerationTracker.isGenerationChanged()) {
+                final GenerationTracker generationTracker = mGenerationTrackers.get(prefix);
+                if (generationTracker != null) {
+                    if (generationTracker.isGenerationChanged()) {
                         if (DEBUG) {
-                            Log.i(TAG, "Generation changed for type:" + mUri.getPath()
+                            Log.i(TAG, "Generation changed for prefix:" + prefix
+                                    + " type:" + mUri.getPath()
                                     + " in package:" + cr.getPackageName());
                         }
-                        mValues.clear();
+                        for (int i = 0; i < mValues.size(); ++i) {
+                            String key = mValues.keyAt(i);
+                            if (key.startsWith(prefix)) {
+                                mValues.remove(key);
+                            }
+                        }
                     } else {
                         boolean prefixCached = mValues.containsKey(prefix);
                         if (prefixCached) {
+                            if (DEBUG) {
+                                Log.i(TAG, "Cache hit for prefix:" + prefix);
+                            }
                             if (!names.isEmpty()) {
                                 for (String name : names) {
                                     if (mValues.containsKey(name)) {
@@ -3440,9 +3458,9 @@
                             return keyValues;
                         }
                     }
-                    if (mGenerationTracker != null) {
-                        currentGeneration = mGenerationTracker.getCurrentGeneration();
-                    }
+                    currentGeneration = generationTracker.getCurrentGeneration();
+                } else {
+                    needsGenerationTracker = true;
                 }
             }
 
@@ -3450,20 +3468,20 @@
                 // No list command specified, return empty map
                 return keyValues;
             }
+            if (DEBUG) {
+                Log.i(TAG, "Cache miss for prefix:" + prefix);
+            }
             IContentProvider cp = mProviderHolder.getProvider(cr);
 
             try {
                 Bundle args = new Bundle();
                 args.putString(Settings.CALL_METHOD_PREFIX_KEY, prefix);
-                boolean needsGenerationTracker = false;
-                synchronized (NameValueCache.this) {
-                    if (mGenerationTracker == null) {
-                        needsGenerationTracker = true;
-                        args.putString(CALL_METHOD_TRACK_GENERATION_KEY, null);
-                        if (DEBUG) {
-                            Log.i(TAG, "Requested generation tracker for type: "
-                                    + mUri.getPath() + " in package:" + cr.getPackageName());
-                        }
+                if (needsGenerationTracker) {
+                    args.putString(CALL_METHOD_TRACK_GENERATION_KEY, null);
+                    if (DEBUG) {
+                        Log.i(TAG, "Requested generation tracker for prefix:" + prefix
+                                + " type: " + mUri.getPath()
+                                + " in package:" + cr.getPackageName());
                     }
                 }
 
@@ -3516,32 +3534,22 @@
                             final int generation = b.getInt(
                                     CALL_METHOD_GENERATION_KEY, 0);
                             if (DEBUG) {
-                                Log.i(TAG, "Received generation tracker for type:"
-                                        + mUri.getPath() + " in package:"
-                                        + cr.getPackageName() + " with index:" + index);
+                                Log.i(TAG, "Received generation tracker for prefix:" + prefix
+                                        + " type:" + mUri.getPath()
+                                        + " in package:" + cr.getPackageName()
+                                        + " with index:" + index);
                             }
-                            if (mGenerationTracker != null) {
-                                mGenerationTracker.destroy();
-                            }
-                            mGenerationTracker = new GenerationTracker(array, index,
-                                    generation, () -> {
-                                synchronized (NameValueCache.this) {
-                                    Log.e(TAG, "Error accessing generation tracker"
-                                            + " - removing");
-                                    if (mGenerationTracker != null) {
-                                        GenerationTracker generationTracker =
-                                                mGenerationTracker;
-                                        mGenerationTracker = null;
-                                        generationTracker.destroy();
-                                        mValues.clear();
-                                    }
-                                }
-                            });
+                            mGenerationTrackers.put(prefix,
+                                    new GenerationTracker(prefix, array, index, generation,
+                                            mGenerationTrackerErrorHandler));
                             currentGeneration = generation;
                         }
                     }
-                    if (mGenerationTracker != null && currentGeneration
-                            == mGenerationTracker.getCurrentGeneration()) {
+                    if (mGenerationTrackers.get(prefix) != null && currentGeneration
+                            == mGenerationTrackers.get(prefix).getCurrentGeneration()) {
+                        if (DEBUG) {
+                            Log.i(TAG, "Updating cache for prefix:" + prefix);
+                        }
                         // cache the complete list of flags for the namespace
                         mValues.putAll(flagsToValues);
                         // Adding the prefix as a signal that the prefix is cached.
@@ -3557,11 +3565,11 @@
 
         public void clearGenerationTrackerForTest() {
             synchronized (NameValueCache.this) {
-                if (mGenerationTracker != null) {
-                    mGenerationTracker.destroy();
+                for (int i = 0; i < mGenerationTrackers.size(); i++) {
+                    mGenerationTrackers.valueAt(i).destroy();
                 }
+                mGenerationTrackers.clear();
                 mValues.clear();
-                mGenerationTracker = null;
             }
         }
     }
diff --git a/core/tests/coretests/src/android/provider/NameValueCacheTest.java b/core/tests/coretests/src/android/provider/NameValueCacheTest.java
index 2e31bb5..b6fc137 100644
--- a/core/tests/coretests/src/android/provider/NameValueCacheTest.java
+++ b/core/tests/coretests/src/android/provider/NameValueCacheTest.java
@@ -32,16 +32,18 @@
 import android.test.mock.MockContentResolver;
 import android.util.MemoryIntArray;
 
+import androidx.test.ext.junit.runners.AndroidJUnit4;
 import androidx.test.filters.SmallTest;
 import androidx.test.platform.app.InstrumentationRegistry;
-import androidx.test.runner.AndroidJUnit4;
 
+import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.runner.RunWith;
 import org.mockito.Mock;
 import org.mockito.MockitoAnnotations;
 
+import java.io.IOException;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.Map;
@@ -59,42 +61,63 @@
     private static final String NAMESPACE = "namespace";
     private static final String NAMESPACE2 = "namespace2";
 
+    private static final String SETTING = "test_setting";
+    private static final String SETTING2 = "test_setting2";
+
     @Mock
     private IContentProvider mMockIContentProvider;
     @Mock
     private ContentProvider mMockContentProvider;
     private MockContentResolver mMockContentResolver;
-    private MemoryIntArray mCacheGenerationStore;
-    private int mCurrentGeneration = 123;
+    private MemoryIntArray mConfigsCacheGenerationStore;
+    private MemoryIntArray mSettingsCacheGenerationStore;
 
-    private HashMap<String, HashMap<String, String>> mStorage;
+    private HashMap<String, HashMap<String, String>> mConfigsStorage;
+    private HashMap<String, String> mSettingsStorage;
+
 
     @Before
     public void setUp() throws Exception {
         Settings.Config.clearProviderForTest();
+        Settings.Secure.clearProviderForTest();
         MockitoAnnotations.initMocks(this);
         when(mMockContentProvider.getIContentProvider()).thenReturn(mMockIContentProvider);
-        mMockContentResolver = new MockContentResolver(InstrumentationRegistry
-                .getInstrumentation().getContext());
+        mMockContentResolver = new MockContentResolver(
+                InstrumentationRegistry.getInstrumentation().getContext());
         mMockContentResolver.addProvider(Settings.Config.CONTENT_URI.getAuthority(),
                 mMockContentProvider);
-        mCacheGenerationStore = new MemoryIntArray(1);
-        mStorage = new HashMap<>();
+        mMockContentResolver.addProvider(Settings.Secure.CONTENT_URI.getAuthority(),
+                mMockContentProvider);
+        mConfigsCacheGenerationStore = new MemoryIntArray(2);
+        mConfigsCacheGenerationStore.set(0, 123);
+        mConfigsCacheGenerationStore.set(1, 456);
+        mSettingsCacheGenerationStore = new MemoryIntArray(2);
+        mSettingsCacheGenerationStore.set(0, 234);
+        mSettingsCacheGenerationStore.set(1, 567);
+        mConfigsStorage = new HashMap<>();
+        mSettingsStorage = new HashMap<>();
 
         // Stores keyValues for a given prefix and increments the generation. (Note that this
         // increments the generation no matter what, it doesn't pay attention to if anything
         // actually changed).
         when(mMockIContentProvider.call(any(), eq(Settings.Config.CONTENT_URI.getAuthority()),
-                eq(Settings.CALL_METHOD_SET_ALL_CONFIG),
-                any(), any(Bundle.class))).thenAnswer(invocationOnMock -> {
+                eq(Settings.CALL_METHOD_SET_ALL_CONFIG), any(), any(Bundle.class))).thenAnswer(
+                invocationOnMock -> {
                     Bundle incomingBundle = invocationOnMock.getArgument(4);
                     HashMap<String, String> keyValues =
                             (HashMap<String, String>) incomingBundle.getSerializable(
-                                    Settings.CALL_METHOD_FLAGS_KEY);
+                                    Settings.CALL_METHOD_FLAGS_KEY, HashMap.class);
                     String prefix = incomingBundle.getString(Settings.CALL_METHOD_PREFIX_KEY);
-                    mStorage.put(prefix, keyValues);
-                    mCacheGenerationStore.set(0, ++mCurrentGeneration);
-
+                    mConfigsStorage.put(prefix, keyValues);
+                    int currentGeneration;
+                    // Different prefixes have different generation codes
+                    if (prefix.equals(NAMESPACE + "/")) {
+                        currentGeneration = mConfigsCacheGenerationStore.get(0);
+                        mConfigsCacheGenerationStore.set(0, ++currentGeneration);
+                    } else if (prefix.equals(NAMESPACE2 + "/")) {
+                        currentGeneration = mConfigsCacheGenerationStore.get(1);
+                        mConfigsCacheGenerationStore.set(1, ++currentGeneration);
+                    }
                     Bundle result = new Bundle();
                     result.putInt(Settings.KEY_CONFIG_SET_ALL_RETURN,
                             Settings.SET_ALL_RESULT_SUCCESS);
@@ -102,32 +125,87 @@
                 });
 
         // Returns the keyValues corresponding to a namespace, or an empty map if the namespace
-        // doesn't have anything stored for it. Returns the generation key if the caller asked
-        // for one.
+        // doesn't have anything stored for it. Returns the generation key if the map isn't empty
+        // and the caller asked for the generation key.
         when(mMockIContentProvider.call(any(), eq(Settings.Config.CONTENT_URI.getAuthority()),
-                eq(Settings.CALL_METHOD_LIST_CONFIG),
-                any(), any(Bundle.class))).thenAnswer(invocationOnMock -> {
+                eq(Settings.CALL_METHOD_LIST_CONFIG), any(), any(Bundle.class))).thenAnswer(
+                invocationOnMock -> {
                     Bundle incomingBundle = invocationOnMock.getArgument(4);
 
                     String prefix = incomingBundle.getString(Settings.CALL_METHOD_PREFIX_KEY);
 
-                    if (!mStorage.containsKey(prefix)) {
-                        mStorage.put(prefix, new HashMap<>());
+                    if (!mConfigsStorage.containsKey(prefix)) {
+                        mConfigsStorage.put(prefix, new HashMap<>());
                     }
-                    HashMap<String, String> keyValues = mStorage.get(prefix);
+                    HashMap<String, String> keyValues = mConfigsStorage.get(prefix);
 
                     Bundle bundle = new Bundle();
                     bundle.putSerializable(Settings.NameValueTable.VALUE, keyValues);
 
-                    if (incomingBundle.containsKey(Settings.CALL_METHOD_TRACK_GENERATION_KEY)) {
+                    if (!keyValues.isEmpty() && incomingBundle.containsKey(
+                            Settings.CALL_METHOD_TRACK_GENERATION_KEY)) {
+                        int index = prefix.equals(NAMESPACE + "/") ? 0 : 1;
                         bundle.putParcelable(Settings.CALL_METHOD_TRACK_GENERATION_KEY,
-                                mCacheGenerationStore);
-                        bundle.putInt(Settings.CALL_METHOD_GENERATION_INDEX_KEY, 0);
+                                mConfigsCacheGenerationStore);
+                        bundle.putInt(Settings.CALL_METHOD_GENERATION_INDEX_KEY, index);
                         bundle.putInt(Settings.CALL_METHOD_GENERATION_KEY,
-                                mCacheGenerationStore.get(0));
+                                mConfigsCacheGenerationStore.get(index));
                     }
                     return bundle;
                 });
+
+        // Stores value for a given setting's name and increments the generation. (Note that this
+        // increments the generation no matter what, it doesn't pay attention to if anything
+        // actually changed).
+        when(mMockIContentProvider.call(any(), eq(Settings.Secure.CONTENT_URI.getAuthority()),
+                eq(Settings.CALL_METHOD_PUT_SECURE), any(), any(Bundle.class))).thenAnswer(
+                invocationOnMock -> {
+                    Bundle incomingBundle = invocationOnMock.getArgument(4);
+                    String key = invocationOnMock.getArgument(3);
+                    String value = incomingBundle.getString(Settings.NameValueTable.VALUE);
+                    mSettingsStorage.put(key, value);
+                    int currentGeneration;
+                    // Different settings have different generation codes
+                    if (key.equals(SETTING)) {
+                        currentGeneration = mSettingsCacheGenerationStore.get(0);
+                        mSettingsCacheGenerationStore.set(0, ++currentGeneration);
+                    } else if (key.equals(SETTING2)) {
+                        currentGeneration = mSettingsCacheGenerationStore.get(1);
+                        mSettingsCacheGenerationStore.set(1, ++currentGeneration);
+                    }
+                    return null;
+                });
+
+        // Returns the value corresponding to a setting, or null if the setting
+        // doesn't have a value stored for it. Returns the generation key if the value isn't null
+        // and the caller asked for the generation key.
+        when(mMockIContentProvider.call(any(), eq(Settings.Secure.CONTENT_URI.getAuthority()),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class))).thenAnswer(
+                invocationOnMock -> {
+                    Bundle incomingBundle = invocationOnMock.getArgument(4);
+                    String key = invocationOnMock.getArgument(3);
+                    String value = mSettingsStorage.get(key);
+
+                    Bundle bundle = new Bundle();
+                    bundle.putSerializable(Settings.NameValueTable.VALUE, value);
+
+                    if (value != null && incomingBundle.containsKey(
+                            Settings.CALL_METHOD_TRACK_GENERATION_KEY)) {
+                        int index = key.equals(SETTING) ? 0 : 1;
+                        bundle.putParcelable(Settings.CALL_METHOD_TRACK_GENERATION_KEY,
+                                mSettingsCacheGenerationStore);
+                        bundle.putInt(Settings.CALL_METHOD_GENERATION_INDEX_KEY, index);
+                        bundle.putInt(Settings.CALL_METHOD_GENERATION_KEY,
+                                mSettingsCacheGenerationStore.get(index));
+                    }
+                    return bundle;
+                });
+    }
+
+    @After
+    public void cleanUp() throws IOException {
+        mConfigsStorage.clear();
+        mSettingsStorage.clear();
     }
 
     @Test
@@ -135,16 +213,13 @@
         HashMap<String, String> keyValues = new HashMap<>();
         keyValues.put("a", "b");
         Settings.Config.setStrings(mMockContentResolver, NAMESPACE, keyValues);
-        verify(mMockIContentProvider).call(any(), any(),
-                eq(Settings.CALL_METHOD_SET_ALL_CONFIG),
-                any(), any(Bundle.class));
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_SET_ALL_CONFIG), any(), any(Bundle.class));
 
         Map<String, String> returnedValues = Settings.Config.getStrings(mMockContentResolver,
-                NAMESPACE,
-                Collections.emptyList());
-        verify(mMockIContentProvider).call(any(), any(),
-                eq(Settings.CALL_METHOD_LIST_CONFIG),
-                any(), any(Bundle.class));
+                NAMESPACE, Collections.emptyList());
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_LIST_CONFIG), any(), any(Bundle.class));
         assertThat(returnedValues).containsExactlyEntriesIn(keyValues);
 
         Map<String, String> cachedKeyValues = Settings.Config.getStrings(mMockContentResolver,
@@ -156,14 +231,12 @@
         keyValues.put("a", "c");
         Settings.Config.setStrings(mMockContentResolver, NAMESPACE, keyValues);
         verify(mMockIContentProvider, times(2)).call(any(), any(),
-                eq(Settings.CALL_METHOD_SET_ALL_CONFIG),
-                any(), any(Bundle.class));
+                eq(Settings.CALL_METHOD_SET_ALL_CONFIG), any(), any(Bundle.class));
 
         Map<String, String> returnedValues2 = Settings.Config.getStrings(mMockContentResolver,
                 NAMESPACE, Collections.emptyList());
         verify(mMockIContentProvider, times(2)).call(any(), any(),
-                eq(Settings.CALL_METHOD_LIST_CONFIG),
-                any(), any(Bundle.class));
+                eq(Settings.CALL_METHOD_LIST_CONFIG), any(), any(Bundle.class));
         assertThat(returnedValues2).containsExactlyEntriesIn(keyValues);
 
         Map<String, String> cachedKeyValues2 = Settings.Config.getStrings(mMockContentResolver,
@@ -177,36 +250,31 @@
         HashMap<String, String> keyValues = new HashMap<>();
         keyValues.put("a", "b");
         Settings.Config.setStrings(mMockContentResolver, NAMESPACE, keyValues);
-        verify(mMockIContentProvider).call(any(), any(),
-                eq(Settings.CALL_METHOD_SET_ALL_CONFIG),
+        verify(mMockIContentProvider).call(any(), any(), eq(Settings.CALL_METHOD_SET_ALL_CONFIG),
                 any(), any(Bundle.class));
 
+        Map<String, String> returnedValues = Settings.Config.getStrings(mMockContentResolver,
+                NAMESPACE, Collections.emptyList());
+        verify(mMockIContentProvider).call(any(), any(), eq(Settings.CALL_METHOD_LIST_CONFIG),
+                any(), any(Bundle.class));
+        assertThat(returnedValues).containsExactlyEntriesIn(keyValues);
+
         HashMap<String, String> keyValues2 = new HashMap<>();
         keyValues2.put("c", "d");
         keyValues2.put("e", "f");
         Settings.Config.setStrings(mMockContentResolver, NAMESPACE2, keyValues2);
         verify(mMockIContentProvider, times(2)).call(any(), any(),
-                eq(Settings.CALL_METHOD_SET_ALL_CONFIG),
-                any(), any(Bundle.class));
-
-        Map<String, String> returnedValues = Settings.Config.getStrings(mMockContentResolver,
-                NAMESPACE,
-                Collections.emptyList());
-        verify(mMockIContentProvider).call(any(), any(),
-                eq(Settings.CALL_METHOD_LIST_CONFIG),
-                any(), any(Bundle.class));
-        assertThat(returnedValues).containsExactlyEntriesIn(keyValues);
+                eq(Settings.CALL_METHOD_SET_ALL_CONFIG), any(), any(Bundle.class));
 
         Map<String, String> returnedValues2 = Settings.Config.getStrings(mMockContentResolver,
-                NAMESPACE2,
-                Collections.emptyList());
+                NAMESPACE2, Collections.emptyList());
         verify(mMockIContentProvider, times(2)).call(any(), any(),
-                eq(Settings.CALL_METHOD_LIST_CONFIG),
-                any(), any(Bundle.class));
+                eq(Settings.CALL_METHOD_LIST_CONFIG), any(), any(Bundle.class));
         assertThat(returnedValues2).containsExactlyEntriesIn(keyValues2);
 
         Map<String, String> cachedKeyValues = Settings.Config.getStrings(mMockContentResolver,
                 NAMESPACE, Collections.emptyList());
+        // Modifying the second namespace doesn't affect the cache of the first namespace
         verifyNoMoreInteractions(mMockIContentProvider);
         assertThat(cachedKeyValues).containsExactlyEntriesIn(keyValues);
 
@@ -219,17 +287,90 @@
     @Test
     public void testCaching_emptyNamespace() throws Exception {
         Map<String, String> returnedValues = Settings.Config.getStrings(mMockContentResolver,
-                NAMESPACE,
-                Collections.emptyList());
-        verify(mMockIContentProvider).call(any(), any(),
-                eq(Settings.CALL_METHOD_LIST_CONFIG),
-                any(), any(Bundle.class));
+                NAMESPACE, Collections.emptyList());
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_LIST_CONFIG), any(), any(Bundle.class));
         assertThat(returnedValues).isEmpty();
 
         Map<String, String> cachedKeyValues = Settings.Config.getStrings(mMockContentResolver,
                 NAMESPACE, Collections.emptyList());
-        verifyNoMoreInteractions(mMockIContentProvider);
+        // Empty list won't be cached
+        verify(mMockIContentProvider, times(2)).call(any(), any(),
+                eq(Settings.CALL_METHOD_LIST_CONFIG), any(), any(Bundle.class));
         assertThat(cachedKeyValues).isEmpty();
     }
 
+    @Test
+    public void testCaching_singleSetting() throws Exception {
+        Settings.Secure.putString(mMockContentResolver, SETTING, "a");
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_PUT_SECURE), any(), any(Bundle.class));
+
+        String returnedValue = Settings.Secure.getString(mMockContentResolver, SETTING);
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class));
+        assertThat(returnedValue).isEqualTo("a");
+
+        String cachedValue = Settings.Secure.getString(mMockContentResolver, SETTING);
+        verifyNoMoreInteractions(mMockIContentProvider);
+        assertThat(cachedValue).isEqualTo("a");
+
+        // Modify the value to invalidate the cache.
+        Settings.Secure.putString(mMockContentResolver, SETTING, "b");
+        verify(mMockIContentProvider, times(2)).call(any(), any(),
+                eq(Settings.CALL_METHOD_PUT_SECURE), any(), any(Bundle.class));
+
+        String returnedValue2 = Settings.Secure.getString(mMockContentResolver, SETTING);
+        verify(mMockIContentProvider, times(2)).call(any(), any(),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class));
+        assertThat(returnedValue2).isEqualTo("b");
+
+        String cachedValue2 = Settings.Secure.getString(mMockContentResolver, SETTING);
+        verifyNoMoreInteractions(mMockIContentProvider);
+        assertThat(cachedValue2).isEqualTo("b");
+    }
+
+    @Test
+    public void testCaching_multipleSettings() throws Exception {
+        Settings.Secure.putString(mMockContentResolver, SETTING, "a");
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_PUT_SECURE), any(), any(Bundle.class));
+
+        String returnedValue = Settings.Secure.getString(mMockContentResolver, SETTING);
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class));
+        assertThat(returnedValue).isEqualTo("a");
+
+        Settings.Secure.putString(mMockContentResolver, SETTING2, "b");
+        verify(mMockIContentProvider, times(2)).call(any(), any(),
+                eq(Settings.CALL_METHOD_PUT_SECURE), any(), any(Bundle.class));
+
+        String returnedValue2 = Settings.Secure.getString(mMockContentResolver, SETTING2);
+        verify(mMockIContentProvider, times(2)).call(any(), any(),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class));
+        assertThat(returnedValue2).isEqualTo("b");
+
+        String cachedValue = Settings.Secure.getString(mMockContentResolver, SETTING);
+        // Modifying the second setting doesn't affect the cache of the first setting
+        verifyNoMoreInteractions(mMockIContentProvider);
+        assertThat(cachedValue).isEqualTo("a");
+
+        String cachedValue2 = Settings.Secure.getString(mMockContentResolver, SETTING2);
+        verifyNoMoreInteractions(mMockIContentProvider);
+        assertThat(cachedValue2).isEqualTo("b");
+    }
+
+    @Test
+    public void testCaching_nullSetting() throws Exception {
+        String returnedValue = Settings.Secure.getString(mMockContentResolver, SETTING);
+        verify(mMockIContentProvider, times(1)).call(any(), any(),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class));
+        assertThat(returnedValue).isNull();
+
+        String cachedValue = Settings.Secure.getString(mMockContentResolver, SETTING);
+        // Empty list won't be cached
+        verify(mMockIContentProvider, times(2)).call(any(), any(),
+                eq(Settings.CALL_METHOD_GET_SECURE), any(), any(Bundle.class));
+        assertThat(cachedValue).isNull();
+    }
 }
diff --git a/packages/SettingsProvider/Android.bp b/packages/SettingsProvider/Android.bp
index 1ac20471..346462d 100644
--- a/packages/SettingsProvider/Android.bp
+++ b/packages/SettingsProvider/Android.bp
@@ -48,6 +48,7 @@
         "test/**/*.java",
         "src/android/provider/settings/backup/*",
         "src/android/provider/settings/validators/*",
+        "src/com/android/providers/settings/GenerationRegistry.java",
         "src/com/android/providers/settings/SettingsBackupAgent.java",
         "src/com/android/providers/settings/SettingsState.java",
         "src/com/android/providers/settings/SettingsHelper.java",
diff --git a/packages/SettingsProvider/src/com/android/providers/settings/GenerationRegistry.java b/packages/SettingsProvider/src/com/android/providers/settings/GenerationRegistry.java
index 5617331..7f3b0ff 100644
--- a/packages/SettingsProvider/src/com/android/providers/settings/GenerationRegistry.java
+++ b/packages/SettingsProvider/src/com/android/providers/settings/GenerationRegistry.java
@@ -17,19 +17,19 @@
 package com.android.providers.settings;
 
 import android.os.Bundle;
-import android.os.UserManager;
 import android.provider.Settings;
+import android.util.ArrayMap;
 import android.util.MemoryIntArray;
 import android.util.Slog;
-import android.util.SparseIntArray;
 
 import com.android.internal.annotations.GuardedBy;
+import com.android.internal.annotations.VisibleForTesting;
 
 import java.io.IOException;
 
 /**
  * This class tracks changes for config/global/secure/system tables
- * on a per user basis and updates a shared memory region which
+ * on a per user basis and updates shared memory regions which
  * client processes can read to determine if their local caches are
  * stale.
  */
@@ -40,138 +40,187 @@
 
     private final Object mLock;
 
+    // Key -> backingStore mapping
     @GuardedBy("mLock")
-    private final SparseIntArray mKeyToIndexMap = new SparseIntArray();
+    private final ArrayMap<Integer, MemoryIntArray> mKeyToBackingStoreMap = new ArrayMap();
+
+    // Key -> (String->Index map) mapping
+    @GuardedBy("mLock")
+    private final ArrayMap<Integer, ArrayMap<String, Integer>> mKeyToIndexMapMap = new ArrayMap<>();
+
+    @VisibleForTesting(visibility = VisibleForTesting.Visibility.PRIVATE)
+    // Maximum number of backing stores allowed
+    static final int NUM_MAX_BACKING_STORE = 8;
 
     @GuardedBy("mLock")
-    private MemoryIntArray mBackingStore;
+    private int mNumBackingStore = 0;
+
+    @VisibleForTesting(visibility = VisibleForTesting.Visibility.PRIVATE)
+    // Maximum size of an individual backing store
+    static final int MAX_BACKING_STORE_SIZE = MemoryIntArray.getMaxSize();
 
     public GenerationRegistry(Object lock) {
         mLock = lock;
     }
 
-    public void incrementGeneration(int key) {
+    /**
+     *  Increment the generation number if the setting is already cached in the backing stores.
+     *  Otherwise, do nothing.
+     */
+    public void incrementGeneration(int key, String name) {
+        final boolean isConfig =
+                (SettingsState.getTypeFromKey(key) == SettingsState.SETTINGS_TYPE_CONFIG);
+        // Only store the prefix if the mutated setting is a config
+        final String indexMapKey = isConfig ? (name.split("/")[0] + "/") : name;
         synchronized (mLock) {
-            MemoryIntArray backingStore = getBackingStoreLocked();
-            if (backingStore != null) {
-                try {
-                    final int index = getKeyIndexLocked(key, mKeyToIndexMap, backingStore);
-                    if (index >= 0) {
-                        final int generation = backingStore.get(index) + 1;
-                        backingStore.set(index, generation);
-                    }
-                } catch (IOException e) {
-                    Slog.e(LOG_TAG, "Error updating generation id", e);
-                    destroyBackingStore();
+            final MemoryIntArray backingStore = getBackingStoreLocked(key,
+                    /* createIfNotExist= */ false);
+            if (backingStore == null) {
+                return;
+            }
+            try {
+                final int index = getKeyIndexLocked(key, indexMapKey, mKeyToIndexMapMap,
+                        backingStore, /* createIfNotExist= */ false);
+                if (index < 0) {
+                    return;
                 }
+                final int generation = backingStore.get(index) + 1;
+                backingStore.set(index, generation);
+                if (DEBUG) {
+                    Slog.i(LOG_TAG, "Incremented generation for setting:" + indexMapKey
+                            + " key:" + SettingsState.keyToString(key)
+                            + " at index:" + index);
+                }
+            } catch (IOException e) {
+                Slog.e(LOG_TAG, "Error updating generation id", e);
+                destroyBackingStoreLocked(key);
             }
         }
     }
 
-    public void addGenerationData(Bundle bundle, int key) {
+    /**
+     *  Return the backing store's reference, the index and the current generation number
+     *  of a cached setting. If it was not in the backing store, first create the entry in it before
+     *  returning the result.
+     */
+    public void addGenerationData(Bundle bundle, int key, String indexMapKey) {
         synchronized (mLock) {
-            MemoryIntArray backingStore = getBackingStoreLocked();
+            final MemoryIntArray backingStore = getBackingStoreLocked(key,
+                    /* createIfNotExist= */ true);
+            if (backingStore == null) {
+                // Error accessing existing backing store or no new backing store is available
+                return;
+            }
             try {
-                if (backingStore != null) {
-                    final int index = getKeyIndexLocked(key, mKeyToIndexMap, backingStore);
-                    if (index >= 0) {
-                        bundle.putParcelable(Settings.CALL_METHOD_TRACK_GENERATION_KEY,
-                                backingStore);
-                        bundle.putInt(Settings.CALL_METHOD_GENERATION_INDEX_KEY, index);
-                        bundle.putInt(Settings.CALL_METHOD_GENERATION_KEY,
-                                backingStore.get(index));
-                        if (DEBUG) {
-                            Slog.i(LOG_TAG, "Exported index:" + index + " for key:"
-                                    + SettingsProvider.keyToString(key));
-                        }
-                    }
+                final int index = getKeyIndexLocked(key, indexMapKey, mKeyToIndexMapMap,
+                        backingStore, /* createIfNotExist= */ true);
+                if (index < 0) {
+                    // Should not happen unless having error accessing the backing store
+                    return;
+                }
+                bundle.putParcelable(Settings.CALL_METHOD_TRACK_GENERATION_KEY,
+                        backingStore);
+                bundle.putInt(Settings.CALL_METHOD_GENERATION_INDEX_KEY, index);
+                bundle.putInt(Settings.CALL_METHOD_GENERATION_KEY,
+                        backingStore.get(index));
+                if (DEBUG) {
+                    Slog.i(LOG_TAG, "Exported index:" + index
+                            + " for setting:" + indexMapKey
+                            + " key:" + SettingsState.keyToString(key));
                 }
             } catch (IOException e) {
                 Slog.e(LOG_TAG, "Error adding generation data", e);
-                destroyBackingStore();
+                destroyBackingStoreLocked(key);
             }
         }
     }
 
     public void onUserRemoved(int userId) {
+        final int secureKey = SettingsState.makeKey(
+                SettingsState.SETTINGS_TYPE_SECURE, userId);
+        final int systemKey = SettingsState.makeKey(
+                SettingsState.SETTINGS_TYPE_SYSTEM, userId);
         synchronized (mLock) {
-            MemoryIntArray backingStore = getBackingStoreLocked();
-            if (backingStore != null && mKeyToIndexMap.size() > 0) {
-                try {
-                    final int secureKey = SettingsProvider.makeKey(
-                            SettingsProvider.SETTINGS_TYPE_SECURE, userId);
-                    resetSlotForKeyLocked(secureKey, mKeyToIndexMap, backingStore);
-
-                    final int systemKey = SettingsProvider.makeKey(
-                            SettingsProvider.SETTINGS_TYPE_SYSTEM, userId);
-                    resetSlotForKeyLocked(systemKey, mKeyToIndexMap, backingStore);
-                } catch (IOException e) {
-                    Slog.e(LOG_TAG, "Error cleaning up for user", e);
-                    destroyBackingStore();
-                }
+            if (mKeyToIndexMapMap.containsKey(secureKey)) {
+                destroyBackingStoreLocked(secureKey);
+                mKeyToIndexMapMap.remove(secureKey);
+                mNumBackingStore = mNumBackingStore - 1;
+            }
+            if (mKeyToIndexMapMap.containsKey(systemKey)) {
+                destroyBackingStoreLocked(systemKey);
+                mKeyToIndexMapMap.remove(systemKey);
+                mNumBackingStore = mNumBackingStore - 1;
             }
         }
     }
 
     @GuardedBy("mLock")
-    private MemoryIntArray getBackingStoreLocked() {
-        if (mBackingStore == null) {
-            // One for the config table, one for the global table, two for system
-            // and secure tables for a managed profile (managed profile is not
-            // included in the max user count), ten for partially deleted users if
-            // users are quickly removed, and twice max user count for system and
-            // secure.
-            final int size = 1 + 1 + 2 + 10 + 2 * UserManager.getMaxSupportedUsers();
+    private MemoryIntArray getBackingStoreLocked(int key, boolean createIfNotExist) {
+        MemoryIntArray backingStore = mKeyToBackingStoreMap.get(key);
+        if (!createIfNotExist) {
+            return backingStore;
+        }
+        if (backingStore == null) {
             try {
-                mBackingStore = new MemoryIntArray(size);
+                if (mNumBackingStore >= NUM_MAX_BACKING_STORE) {
+                    Slog.e(LOG_TAG, "Error creating backing store - at capacity");
+                    return null;
+                }
+                backingStore = new MemoryIntArray(MAX_BACKING_STORE_SIZE);
+                mKeyToBackingStoreMap.put(key, backingStore);
+                mNumBackingStore += 1;
                 if (DEBUG) {
-                    Slog.e(LOG_TAG, "Created backing store " + mBackingStore);
+                    Slog.e(LOG_TAG, "Created backing store for "
+                            + SettingsState.keyToString(key) + " on user: "
+                            + SettingsState.getUserIdFromKey(key));
                 }
             } catch (IOException e) {
                 Slog.e(LOG_TAG, "Error creating generation tracker", e);
             }
         }
-        return mBackingStore;
+        return backingStore;
     }
 
-    private void destroyBackingStore() {
-        if (mBackingStore != null) {
+    @GuardedBy("mLock")
+    private void destroyBackingStoreLocked(int key) {
+        MemoryIntArray backingStore = mKeyToBackingStoreMap.get(key);
+        if (backingStore != null) {
             try {
-                mBackingStore.close();
+                backingStore.close();
                 if (DEBUG) {
-                    Slog.e(LOG_TAG, "Destroyed backing store " + mBackingStore);
+                    Slog.e(LOG_TAG, "Destroyed backing store " + backingStore);
                 }
             } catch (IOException e) {
                 Slog.e(LOG_TAG, "Cannot close generation memory array", e);
             }
-            mBackingStore = null;
+            mKeyToBackingStoreMap.remove(key);
         }
     }
 
-    private static void resetSlotForKeyLocked(int key, SparseIntArray keyToIndexMap,
-            MemoryIntArray backingStore) throws IOException {
-        final int index = keyToIndexMap.get(key, -1);
-        if (index >= 0) {
-            keyToIndexMap.delete(key);
-            backingStore.set(index, 0);
-            if (DEBUG) {
-                Slog.i(LOG_TAG, "Freed index:" + index + " for key:"
-                        + SettingsProvider.keyToString(key));
+    private static int getKeyIndexLocked(int key, String indexMapKey,
+            ArrayMap<Integer, ArrayMap<String, Integer>> keyToIndexMapMap,
+            MemoryIntArray backingStore, boolean createIfNotExist) throws IOException {
+        ArrayMap<String, Integer> nameToIndexMap = keyToIndexMapMap.get(key);
+        if (nameToIndexMap == null) {
+            if (!createIfNotExist) {
+                return -1;
             }
+            nameToIndexMap = new ArrayMap<>();
+            keyToIndexMapMap.put(key, nameToIndexMap);
         }
-    }
-
-    private static int getKeyIndexLocked(int key, SparseIntArray keyToIndexMap,
-            MemoryIntArray backingStore) throws IOException {
-        int index = keyToIndexMap.get(key, -1);
+        int index = nameToIndexMap.getOrDefault(indexMapKey, -1);
         if (index < 0) {
+            if (!createIfNotExist) {
+                return -1;
+            }
             index = findNextEmptyIndex(backingStore);
             if (index >= 0) {
                 backingStore.set(index, 1);
-                keyToIndexMap.append(key, index);
+                nameToIndexMap.put(indexMapKey, index);
                 if (DEBUG) {
-                    Slog.i(LOG_TAG, "Allocated index:" + index + " for key:"
-                            + SettingsProvider.keyToString(key));
+                    Slog.i(LOG_TAG, "Allocated index:" + index + " for setting:" + indexMapKey
+                            + " of type:" + SettingsState.keyToString(key)
+                            + " on user:" + SettingsState.getUserIdFromKey(key));
                 }
             } else {
                 Slog.e(LOG_TAG, "Could not allocate generation index");
diff --git a/packages/SettingsProvider/src/com/android/providers/settings/SettingsProvider.java b/packages/SettingsProvider/src/com/android/providers/settings/SettingsProvider.java
index 683c08e..ba275eb 100644
--- a/packages/SettingsProvider/src/com/android/providers/settings/SettingsProvider.java
+++ b/packages/SettingsProvider/src/com/android/providers/settings/SettingsProvider.java
@@ -35,6 +35,7 @@
 import static com.android.internal.accessibility.AccessibilityShortcutController.MAGNIFICATION_CONTROLLER_NAME;
 import static com.android.internal.accessibility.util.AccessibilityUtils.ACCESSIBILITY_MENU_IN_SYSTEM;
 import static com.android.providers.settings.SettingsState.FALLBACK_FILE_SUFFIX;
+import static com.android.providers.settings.SettingsState.makeKey;
 
 import android.Manifest;
 import android.annotation.NonNull;
@@ -375,10 +376,6 @@
     @GuardedBy("mLock")
     private boolean mSyncConfigDisabledUntilReboot;
 
-    public static int makeKey(int type, int userId) {
-        return SettingsState.makeKey(type, userId);
-    }
-
     public static int getTypeFromKey(int key) {
         return SettingsState.getTypeFromKey(key);
     }
@@ -387,9 +384,6 @@
         return SettingsState.getUserIdFromKey(key);
     }
 
-    public static String keyToString(int key) {
-        return SettingsState.keyToString(key);
-    }
     @ChangeId
     @EnabledSince(targetSdkVersion=android.os.Build.VERSION_CODES.S)
     private static final long ENFORCE_READ_PERMISSION_FOR_MULTI_SIM_DATA_CALL = 172670679L;
@@ -428,22 +422,26 @@
         switch (method) {
             case Settings.CALL_METHOD_GET_CONFIG: {
                 Setting setting = getConfigSetting(name);
-                return packageValueForCallResult(setting, isTrackingGeneration(args));
+                return packageValueForCallResult(SETTINGS_TYPE_CONFIG, name, requestingUserId,
+                        setting, isTrackingGeneration(args));
             }
 
             case Settings.CALL_METHOD_GET_GLOBAL: {
                 Setting setting = getGlobalSetting(name);
-                return packageValueForCallResult(setting, isTrackingGeneration(args));
+                return packageValueForCallResult(SETTINGS_TYPE_GLOBAL, name, requestingUserId,
+                        setting, isTrackingGeneration(args));
             }
 
             case Settings.CALL_METHOD_GET_SECURE: {
                 Setting setting = getSecureSetting(name, requestingUserId);
-                return packageValueForCallResult(setting, isTrackingGeneration(args));
+                return packageValueForCallResult(SETTINGS_TYPE_SECURE, name, requestingUserId,
+                        setting, isTrackingGeneration(args));
             }
 
             case Settings.CALL_METHOD_GET_SYSTEM: {
                 Setting setting = getSystemSetting(name, requestingUserId);
-                return packageValueForCallResult(setting, isTrackingGeneration(args));
+                return packageValueForCallResult(SETTINGS_TYPE_SYSTEM, name, requestingUserId,
+                        setting, isTrackingGeneration(args));
             }
 
             case Settings.CALL_METHOD_PUT_CONFIG: {
@@ -553,7 +551,7 @@
 
             case Settings.CALL_METHOD_LIST_CONFIG: {
                 String prefix = getSettingPrefix(args);
-                Bundle result = packageValuesForCallResult(getAllConfigFlags(prefix),
+                Bundle result = packageValuesForCallResult(prefix, getAllConfigFlags(prefix),
                         isTrackingGeneration(args));
                 reportDeviceConfigAccess(prefix);
                 return result;
@@ -1319,6 +1317,7 @@
         return false;
     }
 
+    @NonNull
     private HashMap<String, String> getAllConfigFlags(@Nullable String prefix) {
         if (DEBUG) {
             Slog.v(LOG_TAG, "getAllConfigFlags() for " + prefix);
@@ -2316,7 +2315,8 @@
                 "get/set setting for user", null);
     }
 
-    private Bundle packageValueForCallResult(Setting setting, boolean trackingGeneration) {
+    private Bundle packageValueForCallResult(int type, @NonNull String name, int userId,
+            @Nullable Setting setting, boolean trackingGeneration) {
         if (!trackingGeneration) {
             if (setting == null || setting.isNull()) {
                 return NULL_SETTING_BUNDLE;
@@ -2325,21 +2325,40 @@
         }
         Bundle result = new Bundle();
         result.putString(Settings.NameValueTable.VALUE,
-                !setting.isNull() ? setting.getValue() : null);
+                (setting != null && !setting.isNull()) ? setting.getValue() : null);
 
-        mSettingsRegistry.mGenerationRegistry.addGenerationData(result, setting.getKey());
+        if ((setting != null && !setting.isNull()) || isSettingPreDefined(name, type)) {
+            // Don't track generation for non-existent settings unless the name is predefined
+            synchronized (mLock) {
+                mSettingsRegistry.mGenerationRegistry.addGenerationData(result,
+                        SettingsState.makeKey(type, userId), name);
+            }
+        }
         return result;
     }
 
-    private Bundle packageValuesForCallResult(HashMap<String, String> keyValues,
-            boolean trackingGeneration) {
+    private boolean isSettingPreDefined(String name, int type) {
+        if (type == SETTINGS_TYPE_GLOBAL) {
+            return sAllGlobalSettings.contains(name);
+        } else if (type == SETTINGS_TYPE_SECURE) {
+            return sAllSecureSettings.contains(name);
+        } else if (type == SETTINGS_TYPE_SYSTEM) {
+            return sAllSystemSettings.contains(name);
+        } else {
+            return false;
+        }
+    }
+
+    private Bundle packageValuesForCallResult(String prefix,
+            @NonNull HashMap<String, String> keyValues, boolean trackingGeneration) {
         Bundle result = new Bundle();
         result.putSerializable(Settings.NameValueTable.VALUE, keyValues);
         if (trackingGeneration) {
+            // Track generation even if the namespace is empty because this is for system apps
             synchronized (mLock) {
                 mSettingsRegistry.mGenerationRegistry.addGenerationData(result,
-                        mSettingsRegistry.getSettingsLocked(
-                                SETTINGS_TYPE_CONFIG, UserHandle.USER_SYSTEM).mKey);
+                        mSettingsRegistry.getSettingsLocked(SETTINGS_TYPE_CONFIG,
+                                UserHandle.USER_SYSTEM).mKey, prefix);
             }
         }
 
@@ -3449,7 +3468,7 @@
 
         private void notifyForSettingsChange(int key, String name) {
             // Increment the generation first, so observers always see the new value
-            mGenerationRegistry.incrementGeneration(key);
+            mGenerationRegistry.incrementGeneration(key, name);
 
             if (isGlobalSettingsKey(key) || isConfigSettingsKey(key)) {
                 final long token = Binder.clearCallingIdentity();
@@ -3487,7 +3506,7 @@
                 List<String> changedSettings) {
 
             // Increment the generation first, so observers always see the new value
-            mGenerationRegistry.incrementGeneration(key);
+            mGenerationRegistry.incrementGeneration(key, prefix);
 
             StringBuilder stringBuilder = new StringBuilder(prefix);
             for (int i = 0; i < changedSettings.size(); ++i) {
@@ -3513,7 +3532,7 @@
                     if (profileId != userId) {
                         final int key = makeKey(type, profileId);
                         // Increment the generation first, so observers always see the new value
-                        mGenerationRegistry.incrementGeneration(key);
+                        mGenerationRegistry.incrementGeneration(key, name);
                         mHandler.obtainMessage(MyHandler.MSG_NOTIFY_URI_CHANGED,
                                 profileId, 0, uri).sendToTarget();
                     }
diff --git a/packages/SettingsProvider/test/src/com/android/providers/settings/GenerationRegistryTest.java b/packages/SettingsProvider/test/src/com/android/providers/settings/GenerationRegistryTest.java
new file mode 100644
index 0000000..d34fe694
--- /dev/null
+++ b/packages/SettingsProvider/test/src/com/android/providers/settings/GenerationRegistryTest.java
@@ -0,0 +1,177 @@
+/*
+ * Copyright (C) 2023 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.providers.settings;
+
+import static android.provider.Settings.CALL_METHOD_GENERATION_INDEX_KEY;
+import static android.provider.Settings.CALL_METHOD_GENERATION_KEY;
+import static android.provider.Settings.CALL_METHOD_TRACK_GENERATION_KEY;
+
+import static com.google.common.truth.Truth.assertThat;
+
+import android.os.Bundle;
+import android.util.MemoryIntArray;
+
+import androidx.test.runner.AndroidJUnit4;
+
+import org.junit.Test;
+import org.junit.runner.RunWith;
+
+import java.io.IOException;
+
+@RunWith(AndroidJUnit4.class)
+public class GenerationRegistryTest {
+    @Test
+    public void testGenerationsWithRegularSetting() throws IOException {
+        final GenerationRegistry generationRegistry = new GenerationRegistry(new Object());
+        final int secureKey = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_SECURE, 0);
+        final String testSecureSetting = "test_secure_setting";
+        Bundle b = new Bundle();
+        // IncrementGeneration should have no effect on a non-cached setting.
+        generationRegistry.incrementGeneration(secureKey, testSecureSetting);
+        generationRegistry.incrementGeneration(secureKey, testSecureSetting);
+        generationRegistry.incrementGeneration(secureKey, testSecureSetting);
+        generationRegistry.addGenerationData(b, secureKey, testSecureSetting);
+        // Default index is 0 and generation is only 1 despite early calls of incrementGeneration
+        checkBundle(b, 0, 1, false);
+
+        generationRegistry.incrementGeneration(secureKey, testSecureSetting);
+        generationRegistry.addGenerationData(b, secureKey, testSecureSetting);
+        // Index is still 0 and generation is now 2; also check direct array access
+        assertThat(getArray(b).get(0)).isEqualTo(2);
+
+        final int systemKey = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_SYSTEM, 0);
+        final String testSystemSetting = "test_system_setting";
+        generationRegistry.addGenerationData(b, systemKey, testSystemSetting);
+        // Default index is 0 and generation is 1 for another backingStore (system)
+        checkBundle(b, 0, 1, false);
+
+        final String testSystemSetting2 = "test_system_setting2";
+        generationRegistry.addGenerationData(b, systemKey, testSystemSetting2);
+        // Second system setting index is 1 and default generation is 1
+        checkBundle(b, 1, 1, false);
+
+        generationRegistry.incrementGeneration(systemKey, testSystemSetting);
+        generationRegistry.incrementGeneration(systemKey, testSystemSetting);
+        generationRegistry.addGenerationData(b, systemKey, testSystemSetting);
+        // First system setting generation now incremented to 3
+        checkBundle(b, 0, 3, false);
+
+        final int systemKey2 = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_SYSTEM, 10);
+        generationRegistry.addGenerationData(b, systemKey2, testSystemSetting);
+        // User 10 has a new set of backingStores
+        checkBundle(b, 0, 1, false);
+
+        // Check user removal
+        generationRegistry.onUserRemoved(10);
+        generationRegistry.incrementGeneration(systemKey2, testSystemSetting);
+
+        // Removed user should not affect existing caches
+        generationRegistry.addGenerationData(b, secureKey, testSecureSetting);
+        assertThat(getArray(b).get(0)).isEqualTo(2);
+
+        // IncrementGeneration should have no effect for a non-cached user
+        b.clear();
+        checkBundle(b, -1, -1, true);
+        // AddGeneration should create new backing store for the non-cached user
+        generationRegistry.addGenerationData(b, systemKey2, testSystemSetting);
+        checkBundle(b, 0, 1, false);
+    }
+
+    @Test
+    public void testGenerationsWithConfigSetting() throws IOException {
+        final GenerationRegistry generationRegistry = new GenerationRegistry(new Object());
+        final String prefix = "test_namespace/";
+        final int configKey = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_CONFIG, 0);
+
+        Bundle b = new Bundle();
+        generationRegistry.addGenerationData(b, configKey, prefix);
+        checkBundle(b, 0, 1, false);
+
+        final String setting = "test_namespace/test_setting";
+        // Check that the generation of the prefix is incremented correctly
+        generationRegistry.incrementGeneration(configKey, setting);
+        generationRegistry.addGenerationData(b, configKey, prefix);
+        checkBundle(b, 0, 2, false);
+    }
+
+    @Test
+    public void testMaxNumBackingStores() throws IOException {
+        final GenerationRegistry generationRegistry = new GenerationRegistry(new Object());
+        final String testSecureSetting = "test_secure_setting";
+        Bundle b = new Bundle();
+        for (int i = 0; i < GenerationRegistry.NUM_MAX_BACKING_STORE; i++) {
+            b.clear();
+            final int key = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_SECURE, i);
+            generationRegistry.addGenerationData(b, key, testSecureSetting);
+            checkBundle(b, 0, 1, false);
+        }
+        b.clear();
+        final int key = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_SECURE,
+                GenerationRegistry.NUM_MAX_BACKING_STORE + 1);
+        generationRegistry.addGenerationData(b, key, testSecureSetting);
+        // Should fail to add generation because the number of backing stores has reached limit
+        checkBundle(b, -1, -1, true);
+        // Remove one user should free up a backing store
+        generationRegistry.onUserRemoved(0);
+        generationRegistry.addGenerationData(b, key, testSecureSetting);
+        checkBundle(b, 0, 1, false);
+    }
+
+    @Test
+    public void testMaxSizeBackingStore() throws IOException {
+        final GenerationRegistry generationRegistry = new GenerationRegistry(new Object());
+        final int secureKey = SettingsState.makeKey(SettingsState.SETTINGS_TYPE_SECURE, 0);
+        final String testSecureSetting = "test_secure_setting";
+        Bundle b = new Bundle();
+        for (int i = 0; i < GenerationRegistry.MAX_BACKING_STORE_SIZE; i++) {
+            generationRegistry.addGenerationData(b, secureKey, testSecureSetting + i);
+            checkBundle(b, i, 1, false);
+        }
+        b.clear();
+        generationRegistry.addGenerationData(b, secureKey, testSecureSetting);
+        // Should fail to increase index because the number of entries in the backing store has
+        // reached the limit
+        checkBundle(b, -1, -1, true);
+        // Shouldn't affect other cached entries
+        generationRegistry.addGenerationData(b, secureKey, testSecureSetting + "0");
+        checkBundle(b, 0, 1, false);
+    }
+
+    private void checkBundle(Bundle b, int expectedIndex, int expectedGeneration, boolean isNull)
+            throws IOException {
+        final MemoryIntArray array = getArray(b);
+        if (isNull) {
+            assertThat(array).isNull();
+        } else {
+            assertThat(array).isNotNull();
+        }
+        final int index = b.getInt(
+                CALL_METHOD_GENERATION_INDEX_KEY, -1);
+        assertThat(index).isEqualTo(expectedIndex);
+        final int generation = b.getInt(CALL_METHOD_GENERATION_KEY, -1);
+        assertThat(generation).isEqualTo(expectedGeneration);
+        if (!isNull) {
+            // Read into the result array with the result index should match the result generation
+            assertThat(array.get(index)).isEqualTo(generation);
+        }
+    }
+
+    private MemoryIntArray getArray(Bundle b) {
+        return b.getParcelable(
+                CALL_METHOD_TRACK_GENERATION_KEY, android.util.MemoryIntArray.class);
+    }
+}