[vm/concurrency] Ensure rehashing of maps correctly resets [_deletedKeys]
When we rehash a linked hash map, we rebuild the index but keep the
existing data array. The [_deletedKeys] specifies the number of entries in the
[_index] which were marked as deleted. The Dart code that triggers
rehashing and initializes a new [_index] didn't initialize
[_deletedKeys].
=> We'll fix this in the Dart code and as a precaution also in the
transitive object copy code.
Furthermore we add a missing optimization: In the example from the bug
report we shouldn't even have attempted to re-hash, because the maps
have only primitive keys (which do not rely on identity or user-defined
hashcodes).
=> We'll change the existing optimization to ignore deleted entries when
determining whether a rehash is needed.
The rehashing code for Sets works differently and takes this already
into account.
Closes https://github.com/dart-lang/sdk/issues/47598
TEST=vm/dart{,_2}/isolates/fast_object_copy_test
Change-Id: I3529ecbf500009ab0c72b98e6c427b8840a69371
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/219000
Reviewed-by: Alexander Aprelev <aam@google.com>
Commit-Queue: Martin Kustermann <kustermann@google.com>
diff --git a/runtime/tests/vm/dart/isolates/fast_object_copy_test.dart b/runtime/tests/vm/dart/isolates/fast_object_copy_test.dart
index 6cc3be4..169a1b9 100644
--- a/runtime/tests/vm/dart/isolates/fast_object_copy_test.dart
+++ b/runtime/tests/vm/dart/isolates/fast_object_copy_test.dart
@@ -233,6 +233,7 @@
await testMapRehash();
await testMapRehash2();
await testMapRehash3();
+ await testMapRehash4();
await testSetRehash();
await testSetRehash2();
@@ -532,6 +533,27 @@
Expect.equals(before + 1, after);
}
+ Future testMapRehash4() async {
+ // This is a regression test for http://dartbug.com/47598
+ print('testMapRehash4');
+
+ // This map doesn't need rehashing
+ final graph = {'a': 1, 'b': 2, 'c': 3}..remove('b');
+ final graphCopy = (await sendReceive(graph) as Map);
+ Expect.equals(2, graphCopy.length);
+ Expect.equals(1, graphCopy['a']);
+ Expect.equals(3, graphCopy['c']);
+
+ // This map will need re-hashing due to usage of a key that has a
+ // user-defined get:hashCode.
+ final graph2 = {'a': 1, 'b': 2, const HashIncrementer(): 3}..remove('b');
+ final graph2Copy = (await sendReceive(graph2) as Map);
+ Expect.equals(2, graph2Copy.length);
+ Expect.equals(1, graph2Copy['a']);
+ --HashIncrementer.counter;
+ Expect.equals(3, graph2Copy[const HashIncrementer()]);
+ }
+
Future testSetRehash() async {
print('testSetRehash');
final obj = Object();
diff --git a/runtime/tests/vm/dart_2/isolates/fast_object_copy_test.dart b/runtime/tests/vm/dart_2/isolates/fast_object_copy_test.dart
index 79de0c5..1a1512d 100644
--- a/runtime/tests/vm/dart_2/isolates/fast_object_copy_test.dart
+++ b/runtime/tests/vm/dart_2/isolates/fast_object_copy_test.dart
@@ -235,6 +235,7 @@
await testMapRehash();
await testMapRehash2();
await testMapRehash3();
+ await testMapRehash4();
await testSetRehash();
await testSetRehash2();
@@ -534,6 +535,27 @@
Expect.equals(before + 1, after);
}
+ Future testMapRehash4() async {
+ // This is a regression test for http://dartbug.com/47598
+ print('testMapRehash4');
+
+ // This map doesn't need rehashing
+ final graph = {'a': 1, 'b': 2, 'c': 3}..remove('b');
+ final graphCopy = (await sendReceive(graph) as Map);
+ Expect.equals(2, graphCopy.length);
+ Expect.equals(1, graphCopy['a']);
+ Expect.equals(3, graphCopy['c']);
+
+ // This map will need re-hashing due to usage of a key that has a
+ // user-defined get:hashCode.
+ final graph2 = {'a': 1, 'b': 2, const HashIncrementer(): 3}..remove('b');
+ final graph2Copy = (await sendReceive(graph2) as Map);
+ Expect.equals(2, graph2Copy.length);
+ Expect.equals(1, graph2Copy['a']);
+ --HashIncrementer.counter;
+ Expect.equals(3, graph2Copy[const HashIncrementer()]);
+ }
+
Future testSetRehash() async {
print('testSetRehash');
final obj = Object();
diff --git a/runtime/vm/object_graph_copy.cc b/runtime/vm/object_graph_copy.cc
index bb715ff..d348aec 100644
--- a/runtime/vm/object_graph_copy.cc
+++ b/runtime/vm/object_graph_copy.cc
@@ -1148,8 +1148,9 @@
auto key_value_pairs = untagged_data->data();
for (intptr_t i = 0; i < length; i += one_for_set_two_for_map) {
ObjectPtr key = key_value_pairs[i].Decompress(Base::heap_base_);
+ const bool is_deleted_entry = key == data;
if (key->IsHeapObject()) {
- if (MightNeedReHashing(key)) {
+ if (!is_deleted_entry && MightNeedReHashing(key)) {
needs_rehashing = true;
break;
}
@@ -1171,6 +1172,7 @@
if (needs_rehashing) {
to_untagged->hash_mask_ = Smi::New(0);
to_untagged->index_ = TypedData::RawCast(Object::null());
+ to_untagged->deleted_keys_ = Smi::New(0);
Base::EnqueueObjectToRehash(to);
}
@@ -1185,15 +1187,15 @@
Base::StoreCompressedPointersNoBarrier(
from, to, OFFSET_OF(UntaggedLinkedHashBase, hash_mask_),
OFFSET_OF(UntaggedLinkedHashBase, hash_mask_));
+ Base::StoreCompressedPointersNoBarrier(
+ from, to, OFFSET_OF(UntaggedLinkedHashMap, deleted_keys_),
+ OFFSET_OF(UntaggedLinkedHashMap, deleted_keys_));
}
Base::ForwardCompressedPointer(from, to,
OFFSET_OF(UntaggedLinkedHashBase, data_));
Base::StoreCompressedPointersNoBarrier(
from, to, OFFSET_OF(UntaggedLinkedHashBase, used_data_),
OFFSET_OF(UntaggedLinkedHashBase, used_data_));
- Base::StoreCompressedPointersNoBarrier(
- from, to, OFFSET_OF(UntaggedLinkedHashMap, deleted_keys_),
- OFFSET_OF(UntaggedLinkedHashMap, deleted_keys_));
}
void CopyLinkedHashMap(typename Types::LinkedHashMap from,
diff --git a/sdk/lib/_internal/vm/lib/compact_hash.dart b/sdk/lib/_internal/vm/lib/compact_hash.dart
index 14fbf46..f9b905b 100644
--- a/sdk/lib/_internal/vm/lib/compact_hash.dart
+++ b/sdk/lib/_internal/vm/lib/compact_hash.dart
@@ -372,6 +372,7 @@
_hashMask = _HashBase._indexSizeToHashMask(_index.length);
final int tmpUsed = _usedData;
_usedData = 0;
+ _deletedKeys = 0;
for (int i = 0; i < tmpUsed; i += 2) {
final key = _data[i];
if (!_HashBase._isDeleted(_data, key)) {
