Adding an element to MutableIntSet causes it to be unable to find another item in the set [352560465]

Fixed

Bug

Status Update

No update yet.

Description

an...@google.com

created issue #1

Jul 11, 2024 06:07PM

I'm seeing unexpected behavior after adding an item to a heavily used MutableIntSet. In the following code snippet, 24 is previously added to a MutableSet. After adding another value, 24 in set then returns false.

val set = MutableIntSet()
...

assertTrue(24 in set) // true
set += 6
assertTrue(24 in set) // false

I've attached a deterministic (but not at all concise) repro case to this issue. The ... in the above snippet is actually a sequence of 2,442 specific additions and removals that cause this behavior. I'm sure there's a more concise repro case, this is just one that I immediately have at hand.

This is starting in my local copy of a CL after a recent rebase onto androidx-main, so I'm guessing aosp/3165182 is the culprit.

intSetCorruptionReproTest.kt

33 KB

Download

Comments

ro...@google.com <ro...@google.com> #2Jul 11, 2024 07:12PM

Accepted by ro...@google.com.

Thanks, I'll take a look right away.

ro...@google.com <ro...@google.com> #3Jul 11, 2024 07:32PM

It was caused by the previous change that introduced removeDeletedMarkers(). The optimization didn't break it.

an...@google.com <an...@google.com> #4Jul 11, 2024 10:35PM

Ah, that makes sense. I hadn't rebased the test that flagged this in a minute, so aosp/3141307 definitely would've been included in that range too.

Should we reassign to Andrei?

ro...@google.com <ro...@google.com> #5Jul 11, 2024 11:36PM

No need, I'm working on a fix. It's pretty involved.

ap...@google.com <ap...@google.com> #6Jul 12, 2024 07:37PM

Marked as fixed.

Project: platform/frameworks/support
Branch: androidx-main

commit b61c61768b309c44d651d80521a8ebd6d81ad6a1
Author: Romain Guy <romainguy@google.com>
Date: Thu Jul 11 17:27:16 2024

Rehash in place when dropping deleted entries

The previous implementation only cleaned up the metadata to drop
deleted entries when the map/set was getting full. This caused one
of the invariants of the data structure to be violated, leading
to corrupted queries.

When we want to drop the deleted entries, we must re-probe the
data structure to move the entries in the proper group based on
their hash. Failure to do so means an entry could remain in a
spot where it should only land in the event of a collision.

This change reworks how we clone the metadata at the end of the
array to be slightly more efficient. We could save further
instructions but it could be at the expensve of the data cache
so we're going to leave this as an exercise for our future
selves.

Also cleanup LruCache (set the upper bound of the maxSize
range to be valid for Int storage, pre-size the map used
in snapshot()).

Fixes: 352560465
Test: ScatterMapTest, ScatterSetTest and primitive variants
Relnote: """Fixed a corruption that could happen in ScatterMap,
ScatterSet, and their primitive variants."""

Change-Id: I38a4afee75595958594310a0ad14cca486997163

M collection/collection/api/current.txt
M collection/collection/api/restricted_current.txt
M collection/collection/src/commonMain/kotlin/androidx/collection/DoubleList.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/FloatFloatMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/FloatIntMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/FloatList.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/FloatLongMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/FloatObjectMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/FloatSet.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/IntFloatMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/IntIntMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/IntList.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/IntLongMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/IntObjectMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/IntSet.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LongFloatMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LongIntMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LongList.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LongLongMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LongObjectMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LongSet.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/LruCache.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/ObjectFloatMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/ObjectIntMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/ObjectLongMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/ScatterMap.kt
M collection/collection/src/commonMain/kotlin/androidx/collection/ScatterSet.kt
M collection/collection/template/ObjectPValueMap.kt.template
M collection/collection/template/PKeyList.kt.template
M collection/collection/template/PKeyObjectMap.kt.template
M collection/collection/template/PKeyPValueMap.kt.template
M collection/collection/template/PKeySet.kt.template
M collection/collection/template/ValueClassList.kt.template
M collection/collection/template/ValueClassSet.kt.template
M collection/collection/template/generateCollections.sh

https://android-review.googlesource.com/3168828

ap...@google.com <ap...@google.com> #7Aug 5, 2024 05:18PM

Project: platform/frameworks/support
Branch: androidx-main

commit 2283075d1a2c5e45d9859aa0611e752a61d7dadd
Author: Andrew Bailey <anbailey@google.com>
Date: Mon Aug 05 11:32:26 2024

Partially revert "Pin dependencies to annotation and collection libraries"

This reverts the collection pinning from commit
69fec236c15cfc67d88a9b96b876c7a47f5e3389.

The pinned version of collection has a metadata corruption bug
(

b/352560465

) in ScatterSet, ScatterMap, and their primitive
variants. This commit reverts the pinning for Compose modules,
which use these data structures extensively. We will re-pin
after a new hotfix version of collection is published
(release tracked in

b/357575863

).

Test: N/A
Change-Id: Ib019701d8e4f988e99c6d622e48daae50522de27

M compose/animation/animation-core/build.gradle
M compose/animation/animation-graphics/build.gradle
M compose/animation/animation/build.gradle
M compose/foundation/foundation-layout/build.gradle
M compose/foundation/foundation/build.gradle
M compose/material/material-ripple/build.gradle
M compose/runtime/runtime/build.gradle

https://android-review.googlesource.com/3205338

pr...@google.com <pr...@google.com> #8Aug 13, 2024 06:58PM

The following release(s) address this bug.It is possible this bug has only been partially addressed:

androidx.collection:collection:1.4.3
androidx.collection:collection-iosarm64:1.4.3
androidx.collection:collection-iossimulatorarm64:1.4.3
androidx.collection:collection-iosx64:1.4.3
androidx.collection:collection-jvm:1.4.3
androidx.collection:collection-linuxarm64:1.4.3
androidx.collection:collection-linuxx64:1.4.3
androidx.collection:collection-macosarm64:1.4.3
androidx.collection:collection-macosx64:1.4.3
androidx.collection:collection-tvosarm64:1.4.3
androidx.collection:collection-tvossimulatorarm64:1.4.3
androidx.collection:collection-tvosx64:1.4.3
androidx.collection:collection-watchosarm32:1.4.3
androidx.collection:collection-watchosarm64:1.4.3
androidx.collection:collection-watchossimulatorarm64:1.4.3
androidx.collection:collection-watchosx64:1.4.3

pr...@google.com <pr...@google.com> #9Sep 5, 2024 08:09PM