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);
+    }
+}