diff --git a/nearby/service/java/com/android/server/nearby/provider/AbstractDiscoveryProvider.java b/nearby/service/java/com/android/server/nearby/provider/AbstractDiscoveryProvider.java
index f136695..21b4d7c 100644
--- a/nearby/service/java/com/android/server/nearby/provider/AbstractDiscoveryProvider.java
+++ b/nearby/service/java/com/android/server/nearby/provider/AbstractDiscoveryProvider.java
@@ -40,7 +40,6 @@
     protected final DiscoveryProviderController mController;
     protected final Executor mExecutor;
     protected Listener mListener;
-    protected List<ScanFilter> mScanFilters;
 
     /** Interface for listening to discovery providers. */
     public interface Listener {
@@ -77,6 +76,12 @@
     protected void invalidateScanMode() {}
 
     /**
+     * Callback invoked to inform the provider of new provider scan filters which replaces any prior
+     * provider filters. Always invoked on the provider executor.
+     */
+    protected void onSetScanFilters(List<ScanFilter> filters) {}
+
+    /**
      * Retrieves the controller for this discovery provider. Should never be invoked by subclasses,
      * as a discovery provider should not be controlling itself. Using this method from subclasses
      * could also result in deadlock.
@@ -138,7 +143,7 @@
 
         @Override
         public void setProviderScanFilters(List<ScanFilter> filters) {
-            mScanFilters = filters;
+            mExecutor.execute(() -> onSetScanFilters(filters));
         }
     }
 }
diff --git a/nearby/service/java/com/android/server/nearby/provider/BleDiscoveryProvider.java b/nearby/service/java/com/android/server/nearby/provider/BleDiscoveryProvider.java
index d828ef9..55176ba 100644
--- a/nearby/service/java/com/android/server/nearby/provider/BleDiscoveryProvider.java
+++ b/nearby/service/java/com/android/server/nearby/provider/BleDiscoveryProvider.java
@@ -37,6 +37,7 @@
 import android.os.ParcelUuid;
 import android.util.Log;
 
+import com.android.internal.annotations.GuardedBy;
 import com.android.server.nearby.common.bluetooth.fastpair.Constants;
 import com.android.server.nearby.injector.Injector;
 import com.android.server.nearby.presence.ExtendedAdvertisement;
@@ -63,6 +64,12 @@
     // Don't block the thread as it may be used by other services.
     private static final Executor NEARBY_EXECUTOR = ForegroundThread.getExecutor();
     private final Injector mInjector;
+    private final Object mLock = new Object();
+    // Null when the filters are never set
+    @VisibleForTesting
+    @GuardedBy("mLock")
+    @Nullable
+    private List<android.nearby.ScanFilter> mScanFilters;
     private android.bluetooth.le.ScanCallback mScanCallbackLegacy =
             new android.bluetooth.le.ScanCallback() {
                 @Override
@@ -193,8 +200,10 @@
         Log.v(TAG, "Ble scan stopped.");
         bluetoothLeScanner.stopScan(mScanCallback);
         bluetoothLeScanner.stopScan(mScanCallbackLegacy);
-        if (mScanFilters != null) {
-            mScanFilters.clear();
+        synchronized (mLock) {
+            if (mScanFilters != null) {
+                mScanFilters = null;
+            }
         }
     }
 
@@ -204,6 +213,20 @@
         onStart();
     }
 
+    @Override
+    protected void onSetScanFilters(List<android.nearby.ScanFilter> filters) {
+        synchronized (mLock) {
+            mScanFilters = filters == null ? null : List.copyOf(filters);
+        }
+    }
+
+    @VisibleForTesting
+    protected List<android.nearby.ScanFilter> getFiltersLocked() {
+        synchronized (mLock) {
+            return mScanFilters == null ? null : List.copyOf(mScanFilters);
+        }
+    }
+
     private void startScan(
             List<ScanFilter> scanFilters, ScanSettings scanSettings,
             android.bluetooth.le.ScanCallback scanCallback) {
@@ -253,24 +276,29 @@
 
     private void setPresenceDevice(byte[] data, NearbyDeviceParcelable.Builder builder,
             String deviceName, int rssi) {
-        for (android.nearby.ScanFilter scanFilter : mScanFilters) {
-            if (scanFilter instanceof PresenceScanFilter) {
-                // Iterate all possible authenticity key and identity combinations to decrypt
-                // advertisement
-                PresenceScanFilter presenceFilter = (PresenceScanFilter) scanFilter;
-                for (PublicCredential credential : presenceFilter.getCredentials()) {
-                    ExtendedAdvertisement advertisement =
-                            ExtendedAdvertisement.fromBytes(data, credential);
-                    if (advertisement == null) {
-                        continue;
-                    }
-                    if (CryptorImpIdentityV1.getInstance().verify(
-                            advertisement.getIdentity(),
-                            credential.getEncryptedMetadataKeyTag())) {
-                        builder.setPresenceDevice(getPresenceDevice(advertisement, deviceName,
-                                rssi));
-                        builder.setEncryptionKeyTag(credential.getEncryptedMetadataKeyTag());
-                        return;
+        synchronized (mLock) {
+            if (mScanFilters == null) {
+                return;
+            }
+            for (android.nearby.ScanFilter scanFilter : mScanFilters) {
+                if (scanFilter instanceof PresenceScanFilter) {
+                    // Iterate all possible authenticity key and identity combinations to decrypt
+                    // advertisement
+                    PresenceScanFilter presenceFilter = (PresenceScanFilter) scanFilter;
+                    for (PublicCredential credential : presenceFilter.getCredentials()) {
+                        ExtendedAdvertisement advertisement =
+                                ExtendedAdvertisement.fromBytes(data, credential);
+                        if (advertisement == null) {
+                            continue;
+                        }
+                        if (CryptorImpIdentityV1.getInstance().verify(
+                                advertisement.getIdentity(),
+                                credential.getEncryptedMetadataKeyTag())) {
+                            builder.setPresenceDevice(getPresenceDevice(advertisement, deviceName,
+                                    rssi));
+                            builder.setEncryptionKeyTag(credential.getEncryptedMetadataKeyTag());
+                            return;
+                        }
                     }
                 }
             }
diff --git a/nearby/service/java/com/android/server/nearby/provider/ChreDiscoveryProvider.java b/nearby/service/java/com/android/server/nearby/provider/ChreDiscoveryProvider.java
index d0d0de0..6aefae9 100644
--- a/nearby/service/java/com/android/server/nearby/provider/ChreDiscoveryProvider.java
+++ b/nearby/service/java/com/android/server/nearby/provider/ChreDiscoveryProvider.java
@@ -39,11 +39,13 @@
 import android.nearby.ScanFilter;
 import android.util.Log;
 
+import com.android.internal.annotations.GuardedBy;
 import com.android.internal.annotations.VisibleForTesting;
 
 import com.google.protobuf.ByteString;
 
 import java.util.Collections;
+import java.util.List;
 import java.util.concurrent.Executor;
 
 import service.proto.Blefilter;
@@ -64,10 +66,16 @@
 
     private final ChreCommunication mChreCommunication;
     private final ChreCallback mChreCallback;
+    private final Object mLock = new Object();
+
     private boolean mChreStarted = false;
     private Blefilter.BleFilters mFilters = null;
     private Context mContext;
     private final IntentFilter mIntentFilter;
+    // Null when the filters are never set
+    @GuardedBy("mLock")
+    @Nullable
+    private List<ScanFilter> mScanFilters;
 
     private final BroadcastReceiver mScreenBroadcastReceiver =
             new BroadcastReceiver() {
@@ -98,20 +106,28 @@
     @Override
     protected void onStart() {
         Log.d(TAG, "Start CHRE scan");
-        updateFilters();
+        synchronized (mLock) {
+            updateFiltersLocked();
+        }
     }
 
     @Override
     protected void onStop() {
         Log.d(TAG, "Stop CHRE scan");
-        mScanFilters.clear();
-        updateFilters();
+        synchronized (mLock) {
+            if (mScanFilters != null) {
+                mScanFilters = null;
+            }
+            updateFiltersLocked();
+        }
     }
 
     @Override
-    protected void invalidateScanMode() {
-        onStop();
-        onStart();
+    protected void onSetScanFilters(List<ScanFilter> filters) {
+        synchronized (mLock) {
+            mScanFilters = filters == null ? null : List.copyOf(filters);
+            updateFiltersLocked();
+        }
     }
 
     /**
@@ -123,7 +139,15 @@
         return mChreCommunication.available();
     }
 
-    private synchronized void updateFilters() {
+    @VisibleForTesting
+    List<ScanFilter> getFiltersLocked() {
+        synchronized (mLock) {
+            return mScanFilters == null ? null : List.copyOf(mScanFilters);
+        }
+    }
+
+    @GuardedBy("mLock")
+    private void updateFiltersLocked() {
         if (mScanFilters == null) {
             Log.e(TAG, "ScanFilters not set.");
             return;
diff --git a/nearby/service/java/com/android/server/nearby/provider/DiscoveryProviderManager.java b/nearby/service/java/com/android/server/nearby/provider/DiscoveryProviderManager.java
index b7574c9..41d5686 100644
--- a/nearby/service/java/com/android/server/nearby/provider/DiscoveryProviderManager.java
+++ b/nearby/service/java/com/android/server/nearby/provider/DiscoveryProviderManager.java
@@ -57,7 +57,9 @@
     protected final Object mLock = new Object();
     private final Context mContext;
     private final BleDiscoveryProvider mBleDiscoveryProvider;
-    @Nullable private final ChreDiscoveryProvider mChreDiscoveryProvider;
+    @VisibleForTesting
+    @Nullable
+    final ChreDiscoveryProvider mChreDiscoveryProvider;
     private @ScanRequest.ScanMode int mScanMode;
     private final Injector mInjector;
 
@@ -351,7 +353,8 @@
         mBleDiscoveryProvider.getController().stop();
     }
 
-    private void stopChreProvider() {
+    @VisibleForTesting
+    protected void stopChreProvider() {
         mChreDiscoveryProvider.getController().stop();
     }
 
diff --git a/nearby/tests/unit/src/com/android/server/nearby/provider/BleDiscoveryProviderTest.java b/nearby/tests/unit/src/com/android/server/nearby/provider/BleDiscoveryProviderTest.java
index 9531c53..ebb897e 100644
--- a/nearby/tests/unit/src/com/android/server/nearby/provider/BleDiscoveryProviderTest.java
+++ b/nearby/tests/unit/src/com/android/server/nearby/provider/BleDiscoveryProviderTest.java
@@ -94,7 +94,7 @@
         mBleDiscoveryProvider.getController().setProviderScanFilters(filterList);
         mBleDiscoveryProvider.onStart();
         mBleDiscoveryProvider.onStop();
-        assertThat(mBleDiscoveryProvider.mScanFilters).isEmpty();
+        assertThat(mBleDiscoveryProvider.getFiltersLocked()).isNull();
     }
 
     @Test
diff --git a/nearby/tests/unit/src/com/android/server/nearby/provider/DiscoveryProviderManagerTest.java b/nearby/tests/unit/src/com/android/server/nearby/provider/DiscoveryProviderManagerTest.java
index 8591b60..91a0b56 100644
--- a/nearby/tests/unit/src/com/android/server/nearby/provider/DiscoveryProviderManagerTest.java
+++ b/nearby/tests/unit/src/com/android/server/nearby/provider/DiscoveryProviderManagerTest.java
@@ -45,11 +45,17 @@
 import org.mockito.MockitoAnnotations;
 
 import java.util.HashMap;
+import java.util.List;
 import java.util.Map;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
 
 public class DiscoveryProviderManagerTest {
     private static final int SCAN_MODE_CHRE_ONLY = 3;
     private static final int DATA_TYPE_SCAN_MODE = 102;
+    private static final int UID = 1234;
+    private static final int PID = 5678;
+    private static final String PACKAGE_NAME = "android.nearby.test";
 
     @Mock Injector mInjector;
     @Mock Context mContext;
@@ -81,6 +87,8 @@
                 new DiscoveryProviderManager(mContext, mInjector, mBleDiscoveryProvider,
                         mChreDiscoveryProvider,
                         mScanTypeScanListenerRecordMap);
+        mCallerIdentity = CallerIdentity
+                .forTest(UID, PID, PACKAGE_NAME, /* attributionTag= */ null);
     }
 
     @Test
@@ -216,6 +224,89 @@
         assertThat(start).isTrue();
     }
 
+    @Test
+    public void test_stopChreProvider_clearFilters() throws Exception {
+        // Cannot use mocked ChreDiscoveryProvider,
+        // so we cannot use class variable mDiscoveryProviderManager
+        ExecutorService executor = Executors.newSingleThreadExecutor();
+        DiscoveryProviderManager manager =
+                new DiscoveryProviderManager(mContext, mInjector, mBleDiscoveryProvider,
+                        new ChreDiscoveryProvider(
+                                mContext,
+                                new ChreCommunication(mInjector, mContext, executor), executor),
+                mScanTypeScanListenerRecordMap);
+        ScanRequest scanRequest = new ScanRequest.Builder()
+                .setScanType(SCAN_TYPE_NEARBY_PRESENCE)
+                .addScanFilter(getPresenceScanFilter()).build();
+        DiscoveryProviderManager.ScanListenerRecord record =
+                new DiscoveryProviderManager.ScanListenerRecord(scanRequest, mScanListener,
+                        mCallerIdentity, mScanListenerDeathRecipient);
+        mScanTypeScanListenerRecordMap.put(mIBinder, record);
+        manager.startChreProvider(List.of(getPresenceScanFilter()));
+        // This is an asynchronized process. The filters will be set in executor thread. So we need
+        // to wait for some time to get the correct result.
+        Thread.sleep(200);
+
+        assertThat(manager.mChreDiscoveryProvider.getController().isStarted())
+                .isTrue();
+        assertThat(manager.mChreDiscoveryProvider.getFiltersLocked()).isNotNull();
+
+        manager.stopChreProvider();
+        Thread.sleep(200);
+        // The filters should be cleared right after.
+        assertThat(manager.mChreDiscoveryProvider.getController().isStarted())
+                .isFalse();
+        assertThat(manager.mChreDiscoveryProvider.getFiltersLocked()).isNull();
+    }
+
+    @Test
+    public void test_restartChreProvider() throws Exception {
+        // Cannot use mocked ChreDiscoveryProvider,
+        // so we cannot use class variable mDiscoveryProviderManager
+        ExecutorService executor = Executors.newSingleThreadExecutor();
+        DiscoveryProviderManager manager =
+                new DiscoveryProviderManager(mContext, mInjector, mBleDiscoveryProvider,
+                        new ChreDiscoveryProvider(
+                                mContext,
+                                new ChreCommunication(mInjector, mContext, executor), executor),
+                        mScanTypeScanListenerRecordMap);
+        ScanRequest scanRequest = new ScanRequest.Builder()
+                .setScanType(SCAN_TYPE_NEARBY_PRESENCE)
+                .addScanFilter(getPresenceScanFilter()).build();
+        DiscoveryProviderManager.ScanListenerRecord record =
+                new DiscoveryProviderManager.ScanListenerRecord(scanRequest, mScanListener,
+                        mCallerIdentity, mScanListenerDeathRecipient);
+        mScanTypeScanListenerRecordMap.put(mIBinder, record);
+        manager.startChreProvider(List.of(getPresenceScanFilter()));
+        // This is an asynchronized process. The filters will be set in executor thread. So we need
+        // to wait for some time to get the correct result.
+        Thread.sleep(200);
+
+        assertThat(manager.mChreDiscoveryProvider.getController().isStarted())
+                .isTrue();
+        assertThat(manager.mChreDiscoveryProvider.getFiltersLocked()).isNotNull();
+
+        // We want to make sure quickly restart the provider the filters should
+        // be reset correctly.
+        // See b/255922206, there can be a race condition that filters get cleared because onStop()
+        // get executed after onStart() if they are called from different threads.
+        manager.stopChreProvider();
+        manager.mChreDiscoveryProvider.getController().setProviderScanFilters(
+                List.of(getPresenceScanFilter()));
+        manager.startChreProvider(List.of(getPresenceScanFilter()));
+        Thread.sleep(200);
+        assertThat(manager.mChreDiscoveryProvider.getController().isStarted())
+                .isTrue();
+        assertThat(manager.mChreDiscoveryProvider.getFiltersLocked()).isNotNull();
+
+        // Wait for enough time
+        Thread.sleep(1000);
+
+        assertThat(manager.mChreDiscoveryProvider.getController().isStarted())
+                .isTrue();
+        assertThat(manager.mChreDiscoveryProvider.getFiltersLocked()).isNotNull();
+    }
+
     private static PresenceScanFilter getPresenceScanFilter() {
         final byte[] secretId = new byte[]{1, 2, 3, 4};
         final byte[] authenticityKey = new byte[]{0, 1, 1, 1};