1124973 - PLDHashTableLookup() is a terrible API

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Nicholas Nethercote [inactive]]

PLDHashTableLookup() returns a non-null pointer to an entry in the table. If the lookup failed this is an empty entry; otherwise it's a used entry. In order to determine if the lookup succeeded you have to call PL_DHASH_ENTRY_IS_FREE (or its inverse, PL_DHASH_ENTRY_IS_FULL).

Much better would be to simply return |nullptr| on failure, like nsTHashtable::GetEntry() does.

One complication is that a handful of PLDHashTableLookup() callers don't use PL_DHASH_ENTRY_IS_{FREE,BUSY} but instead do a (useless) null-check and maybe a check of another field within the entry. This seems to indicate that the author didn't understand the API -- more evidence that changing it is a good idea -- and so those callsites will have to be modified with caution.

As for comm-central, DXR says there are five calls to PLDHashTableLookup() under mailnews/ and they will all be easy to change.

Comment 1

[Nicholas Nethercote [inactive]]

Attachment: (part 1) - Always use inheritance rather than composition for PLDHashTable entries

Because (a) this is how it's usually done, (b) it allows static_cast<> instead
of reinterpret_cast<>, and (c) it will make subsequent patches easier.

Comment 2

[Nicholas Nethercote [inactive]]

Attachment: (part 2) - Introduce PL_DHashTableSearch(), and replace most PL_DHashTableLookup() calls with it

It feels safer to use a function with a new name rather than just changing the
behaviour of the existing function.

For most of these cases the PL_DHashTableLookup() result was checked with
PL_DHASH_ENTRY_IS_{FREE,BUSY} so the conversion was easy. A few of them
preceded that check with a useless null check, but the intent of these was
still easy to determine.

I'll do the trickier ones in subsequent patches.

Comment 3

[Nicholas Nethercote [inactive]]

Attachment: (part 3) - Use PL_DHashTableSearch() in nsHostResolver.cpp

Currently nsHostResolver.cpp uses PL_DHashTableLookup() and fails to use
PL_DHASH_ENTRY_IS_{FREE,BUSY} on the result the way it should. However, I think
it gets away with this because it always does this on the result:

  if (!he || !he->rec) { /* do stuff with |he->rec| */ }

The |!he| test is useless and always fails, but the |!he->rec| does the right
thing because (a) entry storage is always zeroed when the table is created, (b)
HostDB_ClearEntry() zeroes the |rec| field (via NS_RELEASE). So unused entries
always have a null |rec| field.

Furthermore, |he->rec| is never zero in a used entry because HostDB_InitEntry
always assigns it with a nsHostRecord assigned with infallible new in
nsHostRecord::Create (and there are existing assertions to this effect).

All this means that when this patch switches PL_DHashTableLookup to
PL_DHashTableSearch it can drop the |!he->rec| test and just do this:

  if (!he) { /* do stuff with |he->rec| */ }

Finally, there's a comment about HostDB_InitEntry failing which is bogus
because HostDB_InitEntry cannot fail. This patch fixes that too.

Comment 4

[Steve Workman [:sworkman] (INACTIVE)]

Comment on attachment 8553540 [details] [diff] [review]
(part 3) - Use PL_DHashTableSearch() in nsHostResolver.cpp

Review of attachment 8553540 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks Nicholas! Looks sane to me.

Comment 5

[Steve Workman [:sworkman] (INACTIVE)]

cc'ing Pat to keep him in the loop. Pat, njn is fixing the PLDHash calls in nsHostResolver. It all looks simple and sane, but you should know about it for the (very unlikely imo) case that you start seeing feedback about connectivity issues.

Comment 6

[Nathan Froyd [:froydnj]]

Comment on attachment 8553533 [details] [diff] [review]
(part 1) - Always use inheritance rather than composition for PLDHashTable entries

Review of attachment 8553533 [details] [diff] [review]:
-----------------------------------------------------------------

Hm, why am I not surprised that all the instances are in XUL and RDF?  It's too bad we can't statically enforce this somehow. :(

Comment 7

[Nathan Froyd [:froydnj]]

Comment on attachment 8553538 [details] [diff] [review]
(part 2) - Introduce PL_DHashTableSearch(), and replace most PL_DHashTableLookup() calls with it

Review of attachment 8553538 [details] [diff] [review]:
-----------------------------------------------------------------

I support the general idea.

I don't think adding a new function is the right thing to do here; I think we really do want to change the semantics of PL_DHashTableLookup:

1. PL_DHashTableLookup: check the return value with PL_DHASH_ENTRY_IS_BUSY: if it's busy, we can do something with it; if it's not, we can't do anything else with it (if we *did* do something else with it, that strikes me as a bug);
2. PL_DHashTableSearch: check the return value with a null-check: if it's non-nullptr, we can do something with it; if it's nullptr, we can't do anything else with it.

non-nullptr-ness and busy-ness sure sound like the same thing.  (How might one explain when to use Lookup and when to use Search?)

The change also makes things fail fast: if something tries to check busyness with the new *Lookup API, things will segfault, rather than running off into the weeds.  AFAICT, we're also safe from things going wrong with binary components (cf. bug 815467), since PL_DHashTableLookup isn't exported.

Comment 8

[Nicholas Nethercote [inactive]]

Attachment: (part 4) - Remove erroneous uses of PL_DHASH_ENTRY_IS_{BUSY,FREE} in nsJSNPRuntime.cpp

The BUSY check is merely useless, because BUSY is always true for a non-null
entry returned by PL_DHashTableAdd.

The FREE check is downright dangerous because it dereferences |entry| and
PL_DHashTableAdd() returns nullptr on OOM. A null check makes more sense here.

Comment 9

[Nicholas Nethercote [inactive]]

Attachment: (part 5) - Use PL_DHashTableSearch() in gfxFT2FontList.cpp

Because PL_DHashTableLookup() never returns null, GetInfoForFile() features not
one but *two* can-never-fail null checks on its result.

Having said that, the code as written works, at least for non-zero-sized files,
because |entry->mFileSize| will always be zero if the lookup fails (thanks to
PLDHashTable always being zeroed at construction, and |mMap| using
PL_DHashClearEntryStub which also zeroes).

But for zero-sized files the current code will act like they don't exist. Maybe
this can't happen in practice, but it seems dangerous and so I've changed it so
the new code will treat zero-sized files just like non-zero-sized files. jkew,
please correct me if this is wrong!

Comment 10

[Nicholas Nethercote [inactive]]

Attachment: (part 6) - Delete some incorrect comments about PL_DHashTableLookup

The comments about PL_DHashTableLookup in nsContentList.cpp aren't quite
correct -- Add() can OOM even if the looked-for key is already in the table.
More generally, they don't seem worth correcting, so I just removed them.

Comment 11

[Nicholas Nethercote [inactive]]

Attachment: (part 7) - Remove PL_DHashTableSearch

This patch:

- Removes PL_DHashTableSearch().

- Removes PL_DHASH_ENTRY_IS_BUSY(). It's barely used and
  PL_DHASH_ENTRY_IS_FREE() suffices.

- Removes a non-useful, non-sequitur comment ("However, use...").

Comment 12

[Nicholas Nethercote [inactive]]

Now that all the patches are up, we can bikeshed the naming.

- I think keeping the name Lookup() would be a bad idea. Changing the semantics
  of a very long-lived function is asking for trouble. E.g. if we did that,
  comm-central would likely start crashing when these patches land. In
  contrast, if we change the name then comm-central will instead fail to
  compile. Similarly, any binary thingies that use pldhash will crash in a more
  obvious fashion if we change the name.
  
- I like Search() because it's the same length as Lookup(). But GetEntry()
  is what nsTHashtable uses.

Comment 13

[Jonathan Kew [:jfkthame]]

Comment on attachment 8554811 [details] [diff] [review]
(part 5) - Use PL_DHashTableSearch() in gfxFT2FontList.cpp

Review of attachment 8554811 [details] [diff] [review]:
-----------------------------------------------------------------

LGTM, modulo a couple of small details. :) (Note that this code is only built on mobile platforms, so a desktop Firefox build won't check that it compiles.)

Thanks for cleaning this up!

::: gfx/thebes/gfxFT2FontList.cpp
@@ +714,5 @@
>      {
>          if (!mMap.IsInitialized()) {
>              return;
>          }
>          PLDHashEntryHdr *hdr =

s/hdr/entry/ here, I think, or the compiler may have something to say about it....

@@ +716,5 @@
>              return;
>          }
>          PLDHashEntryHdr *hdr =
> +            static_cast<FNCMapEntry*>PL_DHashTableSearch(&mMap,
> +                                                         aFileName.get());

...and parens for the static_cast<...>'s expression, please.

Comment 14

[Nathan Froyd [:froydnj]]

Comment on attachment 8554811 [details] [diff] [review]
(part 5) - Use PL_DHashTableSearch() in gfxFT2FontList.cpp

Review of attachment 8554811 [details] [diff] [review]:
-----------------------------------------------------------------

I agree with Jonathan's comments.

Comment 15

[Nathan Froyd [:froydnj]]

Comment on attachment 8554885 [details] [diff] [review]
(part 7) - Remove PL_DHashTableSearch

Review of attachment 8554885 [details] [diff] [review]:
-----------------------------------------------------------------

I think your commit comment should s/PL_DHashTableSearch/PL_DHashTableLookup/g, yes?

::: xpcom/glue/pldhash.h
@@ -88,5 @@
>    PLDHashNumber keyHash;  /* every entry must begin like this */
>  };
>  
>  MOZ_ALWAYS_INLINE bool
>  PL_DHASH_ENTRY_IS_FREE(PLDHashEntryHdr* aEntry)

Is this worthwhile to keep around?  Could we at least move it out of the public interface?

Comment 16

[Nathan Froyd [:froydnj]]

A dev-platform post about this change would be a good thing, at least so more comm-central people know breaking changes are coming.

Comment 17

[Nicholas Nethercote [inactive]]

> I agree with Jonathan's comments.

What... syntax errors are bad? I haven't yet done a try push but I will do so before landing :)


> (part 7) - Remove PL_DHashTableSearch
> 
> I think your commit comment should
> s/PL_DHashTableSearch/PL_DHashTableLookup/g, yes?

Yes! Two instances. Good catch.


> >  MOZ_ALWAYS_INLINE bool
> >  PL_DHASH_ENTRY_IS_FREE(PLDHashEntryHdr* aEntry)
> 
> Is this worthwhile to keep around?  Could we at least move it out of the
> public interface?

Good idea. It still has a few uses in pldhash.cpp so I will move it into that file.

Thank you for the fast reviews.

Comment 18

[Nathan Froyd [:froydnj]]

Comment on attachment 8553538 [details] [diff] [review]
(part 2) - Introduce PL_DHashTableSearch(), and replace most PL_DHashTableLookup() calls with it

Review of attachment 8553538 [details] [diff] [review]:
-----------------------------------------------------------------

Given subsequent patches, and given that I failed to correctly interpret "I'll do the trickier ones in subsequent patches" as "I am going to kill this API with fire", r+.

Comment 19

[Nicholas Nethercote [inactive]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/1c86241afc93
https://hg.mozilla.org/integration/mozilla-inbound/rev/9e2dbe7f144b
https://hg.mozilla.org/integration/mozilla-inbound/rev/ec10af0d2181
https://hg.mozilla.org/integration/mozilla-inbound/rev/fc7c269f2b7a
https://hg.mozilla.org/integration/mozilla-inbound/rev/332e69cd3273
https://hg.mozilla.org/integration/mozilla-inbound/rev/fd36ee6e8307
https://hg.mozilla.org/integration/mozilla-inbound/rev/1a087d928c9d

Comment 20

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/1c86241afc93
https://hg.mozilla.org/mozilla-central/rev/9e2dbe7f144b
https://hg.mozilla.org/mozilla-central/rev/ec10af0d2181
https://hg.mozilla.org/mozilla-central/rev/fc7c269f2b7a
https://hg.mozilla.org/mozilla-central/rev/332e69cd3273
https://hg.mozilla.org/mozilla-central/rev/fd36ee6e8307
https://hg.mozilla.org/mozilla-central/rev/1a087d928c9d