734847 - Make nsTHashtable infallible by default

Status: RESOLVED FIXED

(Core :: XPCOM, defect)

Description

[Mats Palmgren (inactive)]

Make nsTHashtable optionally infallible.
Inspired by the same thing in nsTArray.h, although I chose to put
the new types in mozilla:: namespace.  I also added MOZ_DELETE on
the methods we don't want implemented.

Comment 1

[Mats Palmgren (inactive)]

Attachment: fix

Comment 2

[Benjamin Smedberg]

Comment on attachment 605020 [details] [diff] [review]
fix

I'm not sure that template specialization is the best way to do this. Because the underlying hashtable is safe, we could make infallible or fallible versions of the two calls which can fail (Init and PutEntry) by call signature; default to infallible, have an alternate version which passes fallible_t. I think that could involve less codesize, which is a real concern for these templates, and it would be easier to see in-code when you actually do need to null-check various results.

For example, presuming that this style of code would be extended to nsBaseHashtable which is used by most consumers, the signature of "Put" ought to change depending on whether you are using the fallible or infallible allocator (NS_WARN_UNUSED_RESULT for the fallible version, and a void return type for the infallible version).

Comment 3

[Mats Palmgren (inactive)]

Attachment: fix, v2

> we could make infallible or
> fallible versions of the two calls which can fail (Init and PutEntry)

There are more calls that can fail.  RemoveEntry can fail because it
sometimes compacts the internal table by allocating a new one and
copy the live entries to it and then free the old table.
Same for EnumerateEntries if the callback function returns
PL_DHASH_REMOVE.  Same for Clear.

> by call signature

That would be tricky, since the underlying hash table use a
PLDHashTableOps struct with function pointers to the Alloc/Free
to use.  Swapping those pointers between infallible/fallible for
each call seems error prone, especially considering there can be
recursion involved.

Instead, I propose that we only make fallible/infallible versions of
Init() and that the hash table is (in)fallible for its life time.
I've glanced through most of the consumers and I can't see that it
would make sense to mix fallible and infallible calls on the same table.

> the signature of "Put"
> ought to change depending on whether you are using the fallible or
> infallible allocator (NS_WARN_UNUSED_RESULT for the fallible version, and a
> void return type for the infallible version).

I agree, but this didn't work in practice due to MOZALLOC_HAVE_XMALLOC.
If undefined, there is no fallible_t type and no infallible functions,
so the default Init in that case needs to be fallible and its signature
needs to return a bool.

https://tbpl.mozilla.org/?usebuildbot=1&tree=Try&rev=96ecc81e841b

Comment 4

[Mats Palmgren (inactive)]

> this didn't work in practice due to MOZALLOC_HAVE_XMALLOC.

An alternative would be to make fallible_t always available,
then we can have both prototypes with the signatures you suggested.
Although they would both map to fallible malloc/free when
MOZALLOC_HAVE_XMALLOC is undefined.  I'm not sure if this matters
in practice, the #ifdef condition (in nscore.h) is:
#if !defined(XPCOM_GLUE) && !defined(NS_NO_XPCOM) && !defined(MOZ_NO_MOZALLOC)
#  include "mozilla/mozalloc.h"
...

If it matters, we could implement a simple infallible version in xpcom
that just calls abort if malloc fails.

Comment 5

[Benjamin Smedberg]

I don't think you understood my suggestion. I don't think you should flip allocators ever. The pldhash code itself is OOM-safe, so we don't actually need to use the infallible allocator. Instead, we should check the return value of potentially fallible calls and abort in the nsTHash code if the caller isn't prepared to deal. This is what I'm planning to do with the string code as well (see my dev.platform post from today).

I definitely think that we want infallible_t to be available in all configurations, even if we're building the standalone glue and can't use mozalloc.

RemoveEntry and PLD_DHASH_REMOVE cannot fail. We always have enough space when we're removing entries; if we fail to resize the table smaller, the pldhash code continues to use the "too large" table. That's why there are (void) markings in those calls to ChangeTable:

http://hg.mozilla.org/mozilla-central/annotate/082d016c341f/xpcom/glue/pldhash.cpp#l692
http://hg.mozilla.org/mozilla-central/annotate/082d016c341f/xpcom/glue/pldhash.cpp#l786

Comment 6

[Mats Palmgren (inactive)]

OK, I see what you mean now.  I still think having distinct infallable/fallible
types is preferable over having two signatures of Init/PutEntry in the same class
because the compiler can enforce that there's no mix of fallible/infallible
calls on the same hash table instance, which is very likely a programmer error.

I don't think code size will be a problem in practice since it should be rare
to instantiate both FallibleTHashtable<T> and InfallibleTHashtable<T> for the
same T.  Looking at the current use of nsTHashtable, I don't think
FallibleTHashtable will be used much at all actually.

Comment 7

[Mats Palmgren (inactive)]

Attachment: fix, part 1

This patch implements separate infallible/fallible types for nsTHashtable
nsBaseHashtable, etc.  This is roughly what the new types looks like:

namespace mozilla {

InfallibleHashtable : public Hashtable {
  void Init(PRUint32 aSize = ...);
  EntryType* PutEntry(KeyType aKey);
}

FallibleHashtable : public Hashtable {
  bool Init(PRUint32 aSize = ...) NS_WARN_UNUSED_RESULT;
  EntryType* PutEntry(KeyType aKey) NS_WARN_UNUSED_RESULT;
}

}

nsTHashtable becomes an alias for mozilla::InfallibleHashtable

(similar layout for the other *Hashtable classes)

Comment 8

[Mats Palmgren (inactive)]

Attachment: part 2, fix consumers

Fix consumers.  This is a rollup patch - I have 15 separate patches
(per top directory mostly) if you prefer.

Comment 9

[Mats Palmgren (inactive)]

Regarding code size cost: it increases the size of libxul.so by 0.4%.
The package size (firefox.linux-x86_64.tar.bz2) is roughly the same
(within margin of error).  (This is for an Opt build on Linux x86-64
compiled with gcc)  I don't know which metric matters here though,
let me know if you want more data.

Comment 10

[Christian Holler (:decoder)]

Marking sg:want, as this will potentially defuse quite a few dangerous OOM bugs. Thanks for putting effort into this :)

Comment 11

[Benjamin Smedberg]

Attachment: Infallible-by-default hashtables, override with mozilla::fallible_t, rev. 1

This is the way I want it to look.

Comment 12

[Benjamin Smedberg]

Attachment: Tree changes, rev. 2

This is mats patch updated to the slightly different API.

Comment 13

[Benjamin Smedberg]

Comment on attachment 620779 [details] [diff] [review]
Infallible-by-default hashtables, override with mozilla::fallible_t, rev. 1

Passed tryserver.

Comment 14

[Benjamin Smedberg]

Comment on attachment 620782 [details] [diff] [review]
Tree changes, rev. 2

Let me know if you think additional people should review any of this.

Comment 15

[Justin Lebar (not reading bugmail)]

I don't see why this was necessary:

-  bool Init(PRUint32 initSize = PL_DHASH_MIN_SIZE)
-  { return nsTHashtable<EntryType>::Init(initSize); }
+  void Init(PRUint32 initSize = PL_DHASH_MIN_SIZE)
+  {
+    if (!nsTHashtable<EntryType>::Init(initSize, fallible_t()))
+      NS_RUNTIMEABORT("OOM");
+  }

Otherwise, looks good to me.

Comment 16

[Jan Varga [:janv]]

Thanks god for this, I need to convert some nsTArray to nsTHashtable in bug 726593.
I would need to rework a lot of stuff otherwise.

Comment 17

[Justin Lebar (not reading bugmail)]

Phew!

@@ -1084,22 +1084,17 @@ bool nsSkeletonState::DecodeHeader(ogg_p
>     }
> 
>     // Extract the segment length.
>     mLength = LEInt64(aPacket->packet + SKELETON_FILE_LENGTH_OFFSET);
> 
>     LOG(PR_LOG_DEBUG, ("Skeleton segment length: %lld", mLength));
> 
>     // Initialize the serianlno-to-index map.
>-    bool init = mIndex.Init();
>-    if (!init) {
>-      NS_WARNING("Failed to initialize Ogg skeleton serialno-to-index map");
>-      mActive = false;
>-      return mDoneReadingHeaders = true;
>-    }
>+    mIndex.Init();
>     mActive = true;

I wonder if that return statement was a bug!

On an unrelated note, this idiom of

  if (!ht.IsInitialized()) {
    ht.Init();
  }

appears a lot.  It might be worth making an EnsureInitialized() method, if we care about having a nice API here.

>@@ -486,17 +486,17 @@ ListBase<LC>::getPrototype(JSContext *cx
>     if (!JS_DefineProperty(cx, receiver, sInterfaceClass.name, OBJECT_TO_JSVAL(interface), NULL,
>                            NULL, 0))
>         return NULL;
> 
>     // This needs to happen after we've set all our own properties on interfacePrototype, to
>     // overwrite the value set by InvalidateProtoShape_add when we set our own properties.
>     js::SetReservedSlot(interfacePrototype, 0, PrivateUint32Value(USE_CACHE));
> 
>-    if (!cache.Put(sInterfaceClass.name, interfacePrototype))
>+    if (!cache.Put(sInterfaceClass.name, interfacePrototype, mozilla::fallible_t()))
>         return NULL;
> 
>     return interfacePrototype;
> }
> 
> template<class LC>
> JSObject *
> ListBase<LC>::create(JSContext *cx, JSObject *scope, ListType *aList,

Do we prefer |using mozilla::fallible_t| or |using namespace mozilla| inside cpp files?

>diff --git a/modules/libjar/zipwriter/src/nsZipWriter.cpp b/modules/libjar/zipwriter/src/nsZipWriter.cpp
>--- a/modules/libjar/zipwriter/src/nsZipWriter.cpp
>+++ b/modules/libjar/zipwriter/src/nsZipWriter.cpp
>@@ -74,17 +74,17 @@
>  * [central directory]
>  * [end of central directory record]
>  */
> NS_IMPL_ISUPPORTS2(nsZipWriter, nsIZipWriter,
>                                 nsIRequestObserver)
> 
> nsZipWriter::nsZipWriter()
> {
>-    mEntryHash.Init();
>+    (void) mEntryHash.Init(); // XXX can fail - move this out of the ctor!

??  Why isn't this infallible?

> nsFaviconService::AddFailedFavicon(nsIURI* aFaviconURI)
> {
>   NS_ENSURE_ARG(aFaviconURI);
> 
>   nsCAutoString spec;
>   nsresult rv = aFaviconURI->GetSpec(spec);
>   NS_ENSURE_SUCCESS(rv, rv);
> 
>-  if (! mFailedFavicons.Put(spec, mFailedFaviconSerial))
>+  if (! mFailedFavicons.Put(spec, mFailedFaviconSerial, mozilla::fallible_t()))
>     return NS_ERROR_OUT_OF_MEMORY;
>   mFailedFaviconSerial ++;
> 
>   if (mFailedFavicons.Count() > MAX_FAVICON_CACHE_SIZE) {
>     // need to expire some entries, delete the FAVICON_CACHE_REDUCE_COUNT number
>     // of items that are the oldest
>     PRUint32 threshold = mFailedFaviconSerial -
>                          MAX_FAVICON_CACHE_SIZE + FAVICON_CACHE_REDUCE_COUNT;

Does this need to be fallible?  It looks like MAX_FAVICON_CACHE_SIZE is 256, so
this table will never hold more than 257 members.

In general I can't vouch 100% that you made the right fallible/infallible decisions.  They seemed reasonable to me!

Comment 18

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Comment on attachment 620782 [details] [diff] [review]
Tree changes, rev. 2

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

::: content/base/src/nsDOMAttributeMap.cpp
@@ +65,5 @@
>  bool
>  nsDOMAttributeMap::Init()
>  {
> +  mAttributeCache.Init();
> +  return true;

Followup to move this to the ctor

::: content/xbl/src/nsXBLBinding.cpp
@@ +1433,5 @@
>  
>  nsresult
>  nsXBLBinding::GetInsertionPointsFor(nsIContent* aParent,
>                                      nsInsertionPointList** aResult)
>  {

Followup here too

Comment 19

[Benjamin Smedberg]

https://hg.mozilla.org/integration/mozilla-inbound/rev/0afd21145f0a
https://hg.mozilla.org/integration/mozilla-inbound/rev/8300b50ca098

Comment 20

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/0afd21145f0a
https://hg.mozilla.org/mozilla-central/rev/8300b50ca098