VM: Fix memory leak during shutdown

VM: Fix memory leak during shutdown

The way runtime/platform/hashmap.h:HashMap was implemented so far did not allow
deleting elements while iterating over the map. If one iterated like this

  HashMap::Entry* cursor = map.Start();
  while (cursor != NULL) {
    if (cond) {
      map.Remove(cursor->key, cursor->hash);
    }
    cursor = map.Next(cursor);
  }

Then the iteration `cursor` will skip elements. This is due to the fact that
`HashMap::Remove()` is left-rotating elements in certain cases and
`HashMap::Next()` will unconditionally advance to the next position in the
backing store.

PROBLEM IS: There was existing code which did remove elements while iterating
over a HashMap.

R=fschneider@google.com

Committed: https://github.com/dart-lang/sdk/commit/d822f36f154340f286efe6df9abb17007c1a4d79

[kustermann, 2016-11-30 12:38:20]

kustermann@google.com changed reviewers:
+ asiva@google.com, fschneider@google.com, vegorov@google.com

[kustermann, 2016-11-30 12:41:46]

Just to clarify: The SEGGFAULTS have been already fixed. This issue here is not
really observable.

[Vyacheslav Egorov (Google), 2016-11-30 12:41:57]

https://codereview.chromium.org/2533303005/diff/1/runtime/bin/socket.cc
File runtime/bin/socket.cc (right):

https://codereview.chromium.org/2533303005/diff/1/runtime/bin/socket.cc#newco...
runtime/bin/socket.cc:207: bool ListeningSocketRegistry::CloseOneSafe(OSSocket*
os_socket,
I suggest a much simple approach: pass a boolean here that says whether to
remove it from the map or not. 

Then CloseAll can just call this function with this boolean set to false and
then clear the whole hash map.

[Florian Schneider, 2016-11-30 17:59:15]

Please add a regression test for this.

Can your approach end up visiting some elements multiple times?

[Florian Schneider, 2016-11-30 18:08:42]

I answered my own previous questions. Here some comments:

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc
File runtime/platform/hashmap.cc (right):

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:110: candidate->hash = 0;
Why clear the hash code?

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:119: void* key = entry->key;
Where is the saved key used after calling Remove?

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:145: p->hash = 0;
Same here. Seems wasted work.

[kustermann, 2016-11-30 21:27:15]

I could also just do the simple thing slava suggested: At cleanup time, just
loop over the hashmap without removing any entries.

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc
File runtime/platform/hashmap.cc (right):

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:110: candidate->hash = 0;
On 2016/11/30 18:08:41, Florian Schneider wrote:
> Why clear the hash code?

For consistency:

The [key] *needs* to be cleared because a NULL key serves as the "free spot"
marker.

The [value] and [hash] don't need to be cleared. But since [value] is cleared,
why not [hash] as well? We could avoid the work and not clear any of
[value]/[hash] (though it's a little weird in the debugger if one examples the
hashmap entries and sees left-over/garbage values in there)

(I thought maybe the reason is ASAN, but then again, [hash] could be the 32-bit
lower bits of [key], so [hash] can contain a valid pointer as well.)

Removed the two assignments now.

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:119: void* key = entry->key;
On 2016/11/30 18:08:41, Florian Schneider wrote:
> Where is the saved key used after calling Remove?

Sorry that was a left-over. The indication whether removal made a free spot is
whether 'key == NULL' if it's not the case, a left rotation has happened.

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:145: p->hash = 0;
On 2016/11/30 18:08:41, Florian Schneider wrote:
> Same here. Seems wasted work.

Same answer.

[Florian Schneider, 2016-11-30 21:51:48]

Lgtm.

If you follow Slava's approach, make sure to still add the comment about using
Remove() while iterating using Next() to the hash map. There is a comment about
insertion, but removal was not mentioned explicitly.

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc
File runtime/platform/hashmap.cc (right):

https://codereview.chromium.org/2533303005/diff/1/runtime/platform/hashmap.cc...
runtime/platform/hashmap.cc:110: candidate->hash = 0;
On 2016/11/30 21:27:15, kustermann wrote:
> On 2016/11/30 18:08:41, Florian Schneider wrote:
> > Why clear the hash code?
> 
> For consistency:
> 
> The [key] *needs* to be cleared because a NULL key serves as the "free spot"
> marker.
> 
> The [value] and [hash] don't need to be cleared. But since [value] is cleared,
> why not [hash] as well? We could avoid the work and not clear any of
> [value]/[hash] (though it's a little weird in the debugger if one examples the
> hashmap entries and sees left-over/garbage values in there)
> 

Agree, on the other hand, it may be useful to examine historical entries in the
hashmap.

Sounds good to remove them - performance should be better as well this way.

[kustermann, 2016-11-30 22:02:42]

Patchset #2 (id:20001) has been deleted

[kustermann, 2016-11-30 22:10:38]

Description was changed from

==========
VM: Fix memory leak during shutdown

The way runtime/platform/hashmap.h:HashMap was implemented so far did not allow
deleting elements while iterating over the map. If one iterated like this

  HashMap::Entry* cursor = map.Start();
  while (cursor != NULL) {
    if (cond) {
      map.Remove(cursor->key, cursor->hash);
    }
    cursor = map.Next(cursor);
  }

Then the iteration `cursor` will skip elements. This is due to the fact that
`HashMap::Remove()` is left-rotating elements in certain cases and
`HashMap::Next()` will unconditionally advance to the next position in the
backing store.

PROBLEM IS: There was existing code which did remove elements while iterating
over a HashMap.

This CL changes that by adding HashMap::Remove() method which takes in a cursor
and returns an (possibly updated) cursor which points to the next element in
iteration order.
==========

to

==========
VM: Fix memory leak during shutdown

The way runtime/platform/hashmap.h:HashMap was implemented so far did not allow
deleting elements while iterating over the map. If one iterated like this

  HashMap::Entry* cursor = map.Start();
  while (cursor != NULL) {
    if (cond) {
      map.Remove(cursor->key, cursor->hash);
    }
    cursor = map.Next(cursor);
  }

Then the iteration `cursor` will skip elements. This is due to the fact that
`HashMap::Remove()` is left-rotating elements in certain cases and
`HashMap::Next()` will unconditionally advance to the next position in the
backing store.

PROBLEM IS: There was existing code which did remove elements while iterating
over a HashMap.
==========

[kustermann, 2016-11-30 22:48:59]

Thanks for the review!

[kustermann, 2016-11-30 22:52:12]

Description was changed from

==========
VM: Fix memory leak during shutdown

The way runtime/platform/hashmap.h:HashMap was implemented so far did not allow
deleting elements while iterating over the map. If one iterated like this

  HashMap::Entry* cursor = map.Start();
  while (cursor != NULL) {
    if (cond) {
      map.Remove(cursor->key, cursor->hash);
    }
    cursor = map.Next(cursor);
  }

Then the iteration `cursor` will skip elements. This is due to the fact that
`HashMap::Remove()` is left-rotating elements in certain cases and
`HashMap::Next()` will unconditionally advance to the next position in the
backing store.

PROBLEM IS: There was existing code which did remove elements while iterating
over a HashMap.
==========

to

==========
VM: Fix memory leak during shutdown

The way runtime/platform/hashmap.h:HashMap was implemented so far did not allow
deleting elements while iterating over the map. If one iterated like this

  HashMap::Entry* cursor = map.Start();
  while (cursor != NULL) {
    if (cond) {
      map.Remove(cursor->key, cursor->hash);
    }
    cursor = map.Next(cursor);
  }

Then the iteration `cursor` will skip elements. This is due to the fact that
`HashMap::Remove()` is left-rotating elements in certain cases and
`HashMap::Next()` will unconditionally advance to the next position in the
backing store.

PROBLEM IS: There was existing code which did remove elements while iterating
over a HashMap.

R=fschneider@google.com

Committed:
https://github.com/dart-lang/sdk/commit/d822f36f154340f286efe6df9abb17007c1a4d79
==========

[kustermann, 2016-11-30 22:52:13]

Committed patchset #3 (id:60001) manually as
d822f36f154340f286efe6df9abb17007c1a4d79 (presubmit successful).