Use hash map for event handler file descriptor map

Use hash map for event handler file descriptor map

Instead of using an array indexed using the file descriptor for
looking up data associated with a socket (SocketData objects) this is
now stored in a hash map using the file descriptor as key.

Added hash map implementation like the one used in the V8 project.

R=ager@google.com, whesse@google.com

BUG=
TEST=

Committed: https://code.google.com/p/dart/source/detail?r=3483

[Mads Ager (chromium), 2012-01-13 13:33:16]

I think we should shared PowerOf2 and hash functions between the components in
platform/utils.h as you sugges.

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.cc#newco...
runtime/bin/hashmap.cc:36: if (occupancy_ + occupancy_/4 >= capacity_) {
occupancy_ + (occupancy_ / 4)

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap_test.cc
File runtime/bin/hashmap_test.cc (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap_test.cc#...
runtime/bin/hashmap_test.cc:27: // we don't care about p->value
Begin comment with capital letter and end with period.

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/utils.h
File runtime/bin/utils.h (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/utils.h#newcode8
runtime/bin/utils.h:8: // TODO(sgjesse): Should this be moved to
platform/utils.h? How about
I think we should share this with vm/utils.h.

PowerOf2 is already there. There is also a word hashing function. Maybe we
should use that one instead of the ones you have added here?

[Søren Gjesse, 2012-01-13 14:51:23]

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.cc#newco...
runtime/bin/hashmap.cc:36: if (occupancy_ + occupancy_/4 >= capacity_) {
On 2012/01/13 13:33:16, Mads Sig Ager wrote:
> occupancy_ + (occupancy_ / 4)

Done.

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap_test.cc
File runtime/bin/hashmap_test.cc (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap_test.cc#...
runtime/bin/hashmap_test.cc:27: // we don't care about p->value
On 2012/01/13 13:33:16, Mads Sig Ager wrote:
> Begin comment with capital letter and end with period.

Done.

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/utils.h
File runtime/bin/utils.h (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/utils.h#newcode8
runtime/bin/utils.h:8: // TODO(sgjesse): Should this be moved to
platform/utils.h? How about
On 2012/01/13 13:33:16, Mads Sig Ager wrote:
> I think we should share this with vm/utils.h.
> 
> PowerOf2 is already there. There is also a word hashing function. Maybe we
> should use that one instead of the ones you have added here?

Started http://codereview.chromium.org/9209001/ for moving utils.h and utils.cc
from vm/ to platform/ for sharing PowerOfTwo and hash function. When that has
landed I will merge and continue on this one.

[Ivan Posva, 2012-01-14 01:19:02]

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.h
File runtime/bin/hashmap.h (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.h#newcode20
runtime/bin/hashmap.h:20: explicit HashMap(MatchFun match = &SamePointerValue,
Is explicit needed here?

[Søren Gjesse, 2012-01-16 14:14:58]

Now using shared PowerOfTwo and WorkHash from platform/utils.h

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.h
File runtime/bin/hashmap.h (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/hashmap.h#newcode20
runtime/bin/hashmap.h:20: explicit HashMap(MatchFun match = &SamePointerValue,
On 2012/01/14 01:19:02, Ivan Posva wrote:
> Is explicit needed here?

No - forgot to remove it when I added a default value for match.

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/utils.h
File runtime/bin/utils.h (right):

http://codereview.chromium.org/9186035/diff/2001/runtime/bin/utils.h#newcode8
runtime/bin/utils.h:8: // TODO(sgjesse): Should this be moved to
platform/utils.h? How about
On 2012/01/13 13:33:16, Mads Sig Ager wrote:
> I think we should share this with vm/utils.h.
> 
> PowerOf2 is already there. There is also a word hashing function. Maybe we
> should use that one instead of the ones you have added here?

Removed bin/utils.h and used PowerOfTwo and WordHash from platform/utils.h

[Mads Ager (google), 2012-01-16 14:23:48]

LGTM

http://codereview.chromium.org/9186035/diff/21001/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/21001/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:161: abort();
Maybe we should use the FATAL macro here with a telling error message.

[Søren Gjesse, 2012-01-16 16:18:08]

http://codereview.chromium.org/9186035/diff/21001/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/21001/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:161: abort();
On 2012/01/16 14:23:48, Mads Ager wrote:
> Maybe we should use the FATAL macro here with a telling error message.

Done.

[Bill Hesse, 2012-01-16 17:04:42]

LGTM.

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/eventhandler_ma...
File runtime/bin/eventhandler_macos.cc (right):

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/eventhandler_ma...
runtime/bin/eventhandler_macos.cc:385: return dart::Utils::WordHash(fd + 1);
Even with this, an attacker may be able to get quadratic behavior on some
systems, but even that shouldn't be a problem, given that n is at most in the
tens of thousands,
and the search is very fast.

WordHash may not be good enough for other uses of the hash table though - we
might need randomization.

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:103: // Clear the entry which is allowed to en emptied.
to en emptied?  en is not a word.

[Ivan Posva, 2012-01-17 07:57:40]

Needs some more work.

-Ivan

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/eventhandler_li...
File runtime/bin/eventhandler_linux.cc (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/eventhandler_li...
runtime/bin/eventhandler_linux.cc:29: static const int kPortMapGrowingFactor =
2;
kPortMapGrowingFactor is not used any more. Please remove.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/eventhandler_li...
runtime/bin/eventhandler_linux.cc:78: sd = new SocketData(fd);
Are we leaking this SocketData object?

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:75: Entry* q = p;  // Start at the entry to remove.
Personally I find it really hard to follow these algorithms when using p, q and
similar names. Rather than having the explanation in a comment, can you use
descriptive names?

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:103: // Clear the entry which is allowed to en emptied.
This comment does not parse.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.h
File runtime/bin/hashmap.h (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.h#newco...
runtime/bin/hashmap.h:47: uint32_t occupancy() const { return occupancy_; }
We have been using intptr_t for sizes all across the VM. Please preserve this.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.h#newco...
runtime/bin/hashmap.h:52: uint32_t capacity() const { return capacity_; }
ditto.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc
File runtime/bin/hashmap_test.cc (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:53: EXPECT_EQ(map_.occupancy(),
static_cast<double>(count));
Why the cast to double?

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:64: static uint32_t CollisionHash(uint32_t key)  {
return key & 0x3; }
By using these two hash functions you will tend to cluster the collisions at the
beginning. How do you ensure you test wrap around?

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:109: EXPECT_EQ(i,
static_cast<double>(set.occupancy()));
ditto. Cast to double?

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:113: EXPECT_EQ(n,
static_cast<double>(set.occupancy()));
ditto. And more places...

http://codereview.chromium.org/9186035/diff/20002/tests/standalone/src/Proces...
File tests/standalone/src/ProcessStderrTest.dart (right):

http://codereview.chromium.org/9186035/diff/20002/tests/standalone/src/Proces...
tests/standalone/src/ProcessStderrTest.dart:53: process.exitHandler = (exitCode)
{
Is this being enabled by the hash table for fds?

[Søren Gjesse, 2012-01-17 09:28:04]

PTAL

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/eventhandler_ma...
File runtime/bin/eventhandler_macos.cc (right):

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/eventhandler_ma...
runtime/bin/eventhandler_macos.cc:385: return dart::Utils::WordHash(fd + 1);
On 2012/01/16 17:04:43, Bill Hesse wrote:
> Even with this, an attacker may be able to get quadratic behavior on some
> systems, but even that shouldn't be a problem, given that n is at most in the
> tens of thousands,
> and the search is very fast.
> 
> WordHash may not be good enough for other uses of the hash table though - we
> might need randomization.

This hash is just what is currently in utils, so I just picked it. It is easily
replaced if it turns out to have some unwanted properties. We can also change
the hash map implementation if linear probing turns out to cause problems.

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/17002/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:103: // Clear the entry which is allowed to en emptied.
On 2012/01/16 17:04:43, Bill Hesse wrote:
> to en emptied?  en is not a word.

Rephrased.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/eventhandler_li...
File runtime/bin/eventhandler_linux.cc (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/eventhandler_li...
runtime/bin/eventhandler_linux.cc:29: static const int kPortMapGrowingFactor =
2;
On 2012/01/17 07:57:41, Ivan Posva wrote:
> kPortMapGrowingFactor is not used any more. Please remove.

Done.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/eventhandler_li...
runtime/bin/eventhandler_linux.cc:78: sd = new SocketData(fd);
On 2012/01/17 07:57:41, Ivan Posva wrote:
> Are we leaking this SocketData object?

Crap - yes! Good catch - added a delete where it is removed from the hash map.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:75: Entry* q = p;  // Start at the entry to remove.
On 2012/01/17 07:57:41, Ivan Posva wrote:
> Personally I find it really hard to follow these algorithms when using p, q
and
> similar names. Rather than having the explanation in a comment, can you use
> descriptive names?

Changed names p, q and r to candidate, next and start. Updated the comments as
well.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.cc#newc...
runtime/bin/hashmap.cc:103: // Clear the entry which is allowed to en emptied.
On 2012/01/17 07:57:41, Ivan Posva wrote:
> This comment does not parse.

Rephrased.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.h
File runtime/bin/hashmap.h (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.h#newco...
runtime/bin/hashmap.h:47: uint32_t occupancy() const { return occupancy_; }
On 2012/01/17 07:57:41, Ivan Posva wrote:
> We have been using intptr_t for sizes all across the VM. Please preserve this.

Done.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap.h#newco...
runtime/bin/hashmap.h:52: uint32_t capacity() const { return capacity_; }
On 2012/01/17 07:57:41, Ivan Posva wrote:
> ditto.

Done.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc
File runtime/bin/hashmap_test.cc (right):

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:53: EXPECT_EQ(map_.occupancy(),
static_cast<double>(count));
On 2012/01/17 07:57:41, Ivan Posva wrote:
> Why the cast to double?

Don't know. Changed count to type intptr_t and removed cast.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:64: static uint32_t CollisionHash(uint32_t key)  {
return key & 0x3; }
On 2012/01/17 07:57:41, Ivan Posva wrote:
> By using these two hash functions you will tend to cluster the collisions at
the
> beginning. How do you ensure you test wrap around?

Added a number of additional hash functions with collision at the end (as long
as the backing store as the initial size). Extended the test to use these as
well as the Utils::WordHash hash function.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:109: EXPECT_EQ(i,
static_cast<double>(set.occupancy()));
On 2012/01/17 07:57:41, Ivan Posva wrote:
> ditto. Cast to double?

Removed.

http://codereview.chromium.org/9186035/diff/20002/runtime/bin/hashmap_test.cc...
runtime/bin/hashmap_test.cc:113: EXPECT_EQ(n,
static_cast<double>(set.occupancy()));
On 2012/01/17 07:57:41, Ivan Posva wrote:
> ditto. And more places...

Removed.

http://codereview.chromium.org/9186035/diff/20002/tests/standalone/src/Proces...
File tests/standalone/src/ProcessStderrTest.dart (right):

http://codereview.chromium.org/9186035/diff/20002/tests/standalone/src/Proces...
tests/standalone/src/ProcessStderrTest.dart:53: process.exitHandler = (exitCode)
{
On 2012/01/17 07:57:41, Ivan Posva wrote:
> Is this being enabled by the hash table for fds?

I added this while tracking down a bug caused by the key "0" (stdin) not being
allowed in the hash map. The VM used to run the script crashed and this added
exit handler test exposed that.

[Ivan Posva, 2012-01-20 21:42:57]

LGTM with comments.

-Ivan

https://chromiumcodereview.appspot.com/9186035/diff/20002/tests/standalone/sr...
File tests/standalone/src/ProcessStderrTest.dart (right):

https://chromiumcodereview.appspot.com/9186035/diff/20002/tests/standalone/sr...
tests/standalone/src/ProcessStderrTest.dart:53: process.exitHandler = (exitCode)
{
On 2012/01/17 09:28:04, Søren Gjesse wrote:
> On 2012/01/17 07:57:41, Ivan Posva wrote:
> > Is this being enabled by the hash table for fds?
> 
> I added this while tracking down a bug caused by the key "0" (stdin) not being
> allowed in the hash map. The VM used to run the script crashed and this added
> exit handler test exposed that.

Thanks for the explanation.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/eventha...
File runtime/bin/eventhandler_linux.cc (right):

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/eventha...
runtime/bin/eventhandler_linux.cc:77: sd = new SocketData(fd);
Please add a comment making it clear that you are now populating the entry in
the socket_map_.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap...
runtime/bin/hashmap.cc:37: if (occupancy_ + occupancy_ / 4 >= capacity_) {
Operator precedence in conjunction with relation operators always makes me
nervous. Please write LISP:
if ((occupancy_ + (occupancy_ / 4)) >= capacity_)

I also am convinced that greatly improves readability for humans.

Also it might make sense to calculate a limit_ when capacity_ changes and avoid
any calculation in this case.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap.h
File runtime/bin/hashmap.h (right):

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap...
runtime/bin/hashmap.h:20: HashMap(MatchFun match = &SamePointerValue, uint32_t
initial_capacity = 8);
I am not sure I like the default parameters here. Please make the user specify
them.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap...
runtime/bin/hashmap.h:47: intptr_t occupancy() const { return occupancy_; }
Are occupancy and capacity really needed in the public API of HashMap?

[Søren Gjesse, 2012-01-23 09:03:49]

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/eventha...
File runtime/bin/eventhandler_linux.cc (right):

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/eventha...
runtime/bin/eventhandler_linux.cc:77: sd = new SocketData(fd);
On 2012/01/20 21:42:57, Ivan Posva wrote:
> Please add a comment making it clear that you are now populating the entry in
> the socket_map_.

Done.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap.cc
File runtime/bin/hashmap.cc (right):

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap...
runtime/bin/hashmap.cc:37: if (occupancy_ + occupancy_ / 4 >= capacity_) {
On 2012/01/20 21:42:57, Ivan Posva wrote:
> Operator precedence in conjunction with relation operators always makes me
> nervous. Please write LISP:
> if ((occupancy_ + (occupancy_ / 4)) >= capacity_)
> 
> I also am convinced that greatly improves readability for humans.
> 
> Also it might make sense to calculate a limit_ when capacity_ changes and
avoid
> any calculation in this case.

Done.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap.h
File runtime/bin/hashmap.h (right):

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap...
runtime/bin/hashmap.h:20: HashMap(MatchFun match = &SamePointerValue, uint32_t
initial_capacity = 8);
On 2012/01/20 21:42:57, Ivan Posva wrote:
> I am not sure I like the default parameters here. Please make the user specify
> them.

OK, removed defaults.

https://chromiumcodereview.appspot.com/9186035/diff/31001/runtime/bin/hashmap...
runtime/bin/hashmap.h:47: intptr_t occupancy() const { return occupancy_; }
On 2012/01/20 21:42:57, Ivan Posva wrote:
> Are occupancy and capacity really needed in the public API of HashMap?

No, removed. It is used a a test, so I added a friend class for that.