Closed Bug 563326 Opened 14 years ago Closed 14 years ago

usability of js::HashMap::generation()

Categories

(Core :: JavaScript Engine, defect)

Product:
Core
Component:
JavaScript Engine
Version:
Other Branch
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

(Whiteboard: fixed-in-tracemonkey)

Attachments

(2 files, 5 obsolete files)

v3
20.96 KB, patch
luke
: review+
Details | Diff | Splinter Review
follow up to fix oom reporting
1.49 KB, patch
Details | Diff | Splinter Review 
Currently js::HashMap::generation() cannot be used to avoid an extra lookup if after lookupForAdd other table mutation operations can happen before the add call. For example, the following does not work:

lock();
AddPtr p = table.lookupFotAdd(key);
if (!p) {
    uint32 gen = table.generation();
    unlock();
    value = new_thing_to_hash();
    lock();
    if (gen != table.generation()) {
        p = table.lookupForAdd(key);
    }
    table.add(p, key, value); 
}
unlock();

The problem is that the generation counter is only increased when rehashing the table. It is not incremented when adding or deleting entries from the table. As such in the above example another thread may add new elements to the table when the current thread is doing new_thing_to_hash(). That can take the location pointed by p so table.add fails the assert that insists on !p.found().
In the bug 519476 I have assumed that the pattern above works, see http://hg.mozilla.org/tracemonkey/annotate/c3ee09da6532/js/src/jsstr.cpp#l3850. So without fixing this bug there is a regression there.
Blocks: 519476
Attached patch v1 (obsolete) — — Splinter Review 
The patch adds gen++ after all add/remove operations. There is also a jsapi test to verify that.
Assignee: general → igor
Attachment #443089 - Flags: review?(lw)
Attached patch v2 (obsolete) — — Splinter Review 

        Attachment #443091 -
        Flags: review?(lw)

    
    

    
  
The jsdhash design counted only table reallocations as generations, in order to solve the address instability problem. The code in comment 0 therefore would (with jsdhash) sample table->generation *before* the lookup. See jsatom.cpp, e.g. js_AtomizeDouble.

Something is different if lookupForAdd does not return the to-be-stabilized entry address unless OOM, indeed. But even with jsdhash, the race loser might overwrite the entry filled in by some other thread. For jsatom.cpp this is ok. But it does seem too delicate.

/be

    
    

    
  
(In reply to comment #4)
> Something is different if lookupForAdd does not return the to-be-stabilized
> entry address unless OOM, indeed. But even with jsdhash, the race loser might
> overwrite the entry filled in by some other thread. 

The problem is that when lookupForAdd returns a new entry, the following add expects that and just writes an entry at the passed pointer. If a complex code or another thread overwrites that before the add, then the add operation will creates an inconsistent table.

    
  
Blocks: 563345

    
    

    
  
The difference between JSDHashTable and HashMap is that for the former JS_DHashTableOperate(JS_DHASH_ADD) would add an entry and update the internal state if the entry was not in the table while for the latter lookupForAdds does not do that as it is a read-only operation. This way the following works even if the generation is only updates when the table is reshaped:

lock();
entry = JS_DHashTableOperate(key, JS_DHASH_ADD);
if (found) 
    return;
entry->key = key;
entry->value = NULL;
gen = table->generation;
unlock();
new_value = create_new_value;
lock();
if (gen != table->generation) {
    entry = JS_DHashTableOperate(key, JS_DHASH_ADD);
    if (found && entry->value) { 
        /* Another thread has overwritten the value. */
        return;
    }
}
entry->value = new_value;
unlock();

But for HashMap semantics the code really needs the generation update on any mutation.

    
    

    
  
What bugs me about the generation-counter strategy is that it is, however unlikely, possible for the generation to wrap around such that the table has been reallocated and the generation number is the same.  However, when it is only done on table-size-change, that is a bunch of hash table operation and so it seems highly unlikely.

Doing a generation bump on every add/remove operation increases the speed at which we go through generations.  Moreover, since hash table add/removes are often caused by content js, it seems like this provides a more direct way for content js to control the generation.  I'm not sure about Igor's particular use of generation, but it seems like, in general, this could be deterministically exploited.

An alternative solution would to add some auto guard class:

struct Guard {
  bool changed;
  Guard *next;
  Guard(HashTable &ht) : changed(false), next(ht.first) { ht.first = this; }
  ~Guard(); // unlink
};

then do:

s/++gen;/for(Guard *g = first; g; g = g->next) g->changed = true;/

and have user code write:

AddPtr p = ht.lookupForAdd(x);
if (!p) {
  Guard g(&ht);
  ... do stuff
  if (g.changed) {
    ...
  }
}

Furthermore, the guard class could be given two flags: "tableResized" and "contentsChanged" (where tableResized implies contentsChanged), each with the necessary invariant for the two use cases mentioned above.  (In the case where code only cared about address stability, not add/remove, this would mean less false negatives.)

    
    

    
  
(In reply to comment #7)
> What bugs me about the generation-counter strategy is that it is, however
> unlikely, possible for the generation to wrap around such that the table has
> been reallocated and the generation number is the same.  However, when it is
> only done on table-size-change, that is a bunch of hash table operation and so
> it seems highly unlikely.

We can make it uint64 if necessary. There is no way for it to wrap around in non-cosmological time, then.

> Furthermore, the guard class could be given two flags: "tableResized" and
> "contentsChanged" (where tableResized implies contentsChanged), each with the
> necessary invariant for the two use cases mentioned above.  (In the case where
> code only cared about address stability, not add/remove, this would mean less
> false negatives.)

This sounds better, but adding the contentsChanged check will slow adds and removes down. Do we really need it? jsdhash did without not only by virtue of client code such as jsatom.cpp assuming add was idempotent, it also handed back a pointer to quasi-stable storage from lookup, so if generation didn't change you could check (with locking if MT) whether a racer added something for the same key.

Luke, could you remind me why lookupForAdd doesn't return a quasi-stable entry pointer?

/be

    
    

    
  
(In reply to comment #8)
> Luke, could you remind me why lookupForAdd doesn't return a quasi-stable entry
> pointer?

I deviated from JS_DHashTable in this regard because it means that a lookupForAdd is really an allocation in disguise.  That is, if you do

  p = hm.lookupForAdd(k);

and then, for whatever reason, don't do

  hm.add(p,k,v);

you have "leaked" the entry pointed to by p (assuming HashPolicy::hash(K()) is != p.entry->keyHash).  Such a design would impose a subtle requirement on callers, essentially turning lookupForAdd into lookupAndIPromoseToAdd().

Now, JS_DHashTable does literally name the operation JS_DHASH_ADD, so if the user does such an add and then doesn't initialize the returned element, it is the user's fault.  However, a major goal of the new hash table was to back away from the complexity associated with JS_DHASH_ADD-dance.

Also, note that, when there are no Guards watching, the cost of contentsChanged is a single, predictable null-check.

    
    

    
  
(In reply to comment #9)
> Such a design would impose a subtle requirement on
> callers, essentially turning lookupForAdd into lookupAndIPromoseToAdd().

As they say in Texas, "damn straight!" :-|.

> Now, JS_DHashTable does literally name the operation JS_DHASH_ADD, so if the
> user does such an add and then doesn't initialize the returned element, it is
> the user's fault.  However, a major goal of the new hash table was to back away
> from the complexity associated with JS_DHASH_ADD-dance.

What complexity? I smell complexity right here, in the alternative.

Intentionality in hashtable usage is everything. Are you looking up to add, to remove, to probe a cache without intent to fill, or just cuz, I dunno, you feel like it? The last is a bug.

/be

    
    

    
  

      
      
      
      

        Attached patch
          
          
        patch (obsolete)
        — 
          — Splinter Review
      

    


  
(In reply to comment #10)
> What complexity?

The complexity is having an 'add' operation that either:
 (1) fails
 (2) finds an existing entry
 (3) mostly-adds an entry, requiring the user to finish adding the element

In particular (3) leaves the hash table, upon return from JS_DHashTableOperate, in an invalid state until the entry is filled in by the caller.  It's just a lot for the caller to understand.

> Intentionality in hashtable usage is everything. Are you looking up to add, to
> remove, to probe a cache without intent to fill, or just cuz, I dunno, you feel
> like it? The last is a bug.

The intention of lookupForAdd is to lookup and, unless something bad happens, add an element.  But, if something bad does happen, all the caller has done is an (externally) effect-free lookup operation, so they can, e.g., return immediately.

Thinking a bit more about Igor's situation, it seems like all that is needed is a lookupOrAdd helper.  That better matches the intention of "add this key if it is not found, I'll initialize the value it later".  (It is also more complicated because it introduces an additional state that a hashmap-entry can be in, but this seems hard to avoid without something like the 'contentsChanged' flag discussed above.

    
    

    
  
In particular, the problem in comment 1 can be solved with:

lock();
HashMap<K,T*>::Entry *e = table.lookupOrAdd(key);
if (!e)
   // error
if (!e->value) {  /* default-initialized value for T* is NULL */
    uint32 gen = table.generation();
    unlock();
    value = new_thing_to_hash();
    lock();
    if (gen != table.generation()) {
        e = &*table.lookup(key);
    }
    e->value = value;
}
unlock();

    
    

    
  
(In reply to comment #11)
> The complexity is having an 'add' operation that either:
>  (1) fails
>  (2) finds an existing entry
>  (3) mostly-adds an entry, requiring the user to finish adding the element

I think a good alternative to the current lookupForAdd/add pair would be something like:

p = putIfAbsent(key, value);

The method will add the value but only if one does not exist. Otherwise it will keep the old value. The method will return a pointer into the added entry or a flag indicating OOM error. This way the generation counter would need to be updated only on the table resize.

The drawback is that the caller would be forced to use a special value to indicate just added entry that was not yet been initialized. But in practice a NULL or zero would do the trick and the hash code would not need to deal with 2 and 3 above on its own.

The usage for the lazy initialization would be like:

AutoLock lock();
p = table.putIfAbsent(key, NULL);
if (!p) {
    report_oom();
    return NULL;
}

if (p->value)
    return p->value;

uint32 gen = table.generation();

{
    AutoUnlock unlock();
    new_value = create_new_value();
}

if (gen != table.generation())
    p = table.putIfAbsent(key, NULL);

// check if another thread has added a value
if (p->value) {
    destoy(new_value);
    return p->value;
}

p->value = new_value;
return new_value;

    
    

    
  
(In reply to comment #12)
> In particular, the problem in comment 1 can be solved with:
....
> 
> lock();
> HashMap<K,T*>::Entry *e = table.lookupOrAdd(key);

You have won the the race of proposing a solution :). The only difference with your suggestion is that I would like to see an explicit value parameter for the lookupOrAdd() not to rely on T().

    
    

    
  
(In reply to comment #15)
> You have won the the race of proposing a solution :). The only difference with
> your suggestion is that I would like to see an explicit value parameter for the
> lookupOrAdd() not to rely on T().

Sounds good.  Perhaps:

  Entry *HashMap::lookupOrAdd(const Key &k, const Value &v = Value())

?

The patch in comment 11 is tiny, so maybe you can just throw it in with bug 563345 or the bugfix for bug 519476?

    
    

    
  
Complexity moves around, it doesn't go away, I claim -- no free lunch in these cases, specifically no way for the caller to avoid checking for race loss.

Which approach uses fewer static instructions, fewer cycles on common paths, etc. we can measure. But the complexity of a half-initialized entry state is arguably no worse for low-level code than the complexity of a guard declaration and test.

/be

    
    

    
  
(In reply to comment #17)
> But the complexity of a half-initialized entry state is
> arguably no worse for low-level code than the complexity of a guard declaration
> and test.

True, the code the user writes using JS_DHASH_ADD or lookupOrAdd is isomorphic (for some definition of structure).  I guess then my only real complaint was with "half-initialization".

On the subject of the complexity of the 'racing add' case, though, it seems like this whole 'generation' trickery can be made a bit simpler:

Map::WeakPtr p = hm.lookupOrAdd(k, NULL);
if (!p)
  goto error;
if (!p->value) {
  do_stuff();
  if (!p)  // ** p turns to !p if the table generation changes **
    p = hm.lookup(k);
  p->value = ...
}
... =  p->value

by having 'p' manage the generation.

    
    

    
  
Your Northern C++ WeakPtr fu is strong -- we of the Southern Crane C technique bow before it.

/be

    
    

    
  
It seems it is possible to get away form the generation number for lazy initialization of values. The idea is to have a method to check the entry pointer validity. The method would just check that the entry still points into the hashtable and that the key still matches. With that we can remove the generation counter. Here is an example how that would work:

p = hm.lookupOrAdd(k, NULL);
if (!p)
    goto error;
if (!p->value) {
    do_stuff_that_can_mutate_table_and_create_new_value();
    p = hm.lookupOrAdd(p, k, new_value);
    if (!p)
        goto error;
    if (p->value != new_value) {
        // lost race
        destroy_new_value;
    }
}
return p->value;

The 3-argument method lookupOrAdd will use p as hint to quickly verify that p is still a valid pointer. If not, an ordinary lookupOrAdd will be invoked.

To completely remove the need for the generation counter it would be necessary to add method like remove(p, key). That method again would verify that p is valid and run an ordinary remove(key) if not.

    
    

    
  
(In reply to comment #20)
Ah, good observation about not needing generation!  Perhaps, though, we can decouple this functionality from any effectful operation as 'hm.stillValid(p)'.  This allows stillValid to be independently combined with lookup/lookupForAdd/lookupOrAdd/remove.

p = hm.lookupOrAdd(k, NULL);
if (!p)
  goto error;
if (!p->value) {
  do_stuff_that_can_mutate_table_but_not_remove_p_and_create_new_value();
  if (!hm.stillValid(p))
    p = hm.lookup(k);
  if (p->value)
    destroy_new_value;
}

(I noticed the sample code in comment 20 checks for the possibility that the entry has been removed by the racing code, which is true in general, but looking at the two use cases in bug 563345 and bug 519476, this shouldn't be possible (the JSString* should be rooted; js_PurgeThreads will need to check (and not remove) null-valued entries).  Hence, the 'lookup', not 'lookupOrAdd', above.)

    
    

    
  
Oops, that should be 'hm.stillValid(p, k)'.

Also, stillValid will be significantly more expensive than generation-checking when key equality is non-trivial.  I was thinking that maybe a weaker "points into hash table" condition (that doesn't need key equality) would suffice for callers who know that the element in question can't be removed (like the two cases mentioned above) but in-place rehashing breaks this.

    
    

    
  
(In reply to comment #21)
>   do_stuff_that_can_mutate_table_but_not_remove_p_and_create_new_value();
>   if (!hm.stillValid(p))

For the deflated string case another thread can create an entry but it is true that for the current HashMap uses the entry cannot be removed for the above use cases. Still I do not see why the assumption that do_stuff cannot remove a value is necessary.

Another observation is that it is better not to leak stillValid to the table users. Instead the table should provide a version of the lookup, lookupOrAdd and remove methods that would take p as an extra parameter and do the validness checks on its own.

    
    

    
  
(In reply to comment #22)
> Oops, that should be 'hm.stillValid(p, k)'.
> 
> Also, stillValid will be significantly more expensive than generation-checking
> when key equality is non-trivial.

For our use cases the key equality just compares the words. Plus in these cases where stillValid is necessary a couple of extra checks compared with the generation counter check should not make a significant difference. There are too much other checks and code there already. Thus I would prefer to have an interface to the table that cannot be abused. For example, just look at the usage of the generation() in http://hg.mozilla.org/tracemonkey/file/11a9245e9ed6/js/src/jsarray.cpp#l1489 . It is not straightforward to see that the usage is correct there given that the keys will be added or removed from the table.

    
    

    
  
(In reply to comment #24)
> > Also, stillValid will be significantly more expensive than generation-checking
> > when key equality is non-trivial.
> 
> For our use cases the key equality just compares the words.

Yes, they are in the 'trivial' category.  But we cannot assume all uses are as well.  I suspect it's fairly common to stick strings in a hash table.

> Thus I would prefer to have an
> interface to the table that cannot be abused.

I'm not sure what mythical interface you are talking about that cannot be abused ;-)  You can't force the caller to use the proposed ternary lookupOrAdd  before using a possibly-invalidated Ptr; they have to know "this  could be invalid by now, I need to check", and once they've done that, stillExist and lookupOrAdd are equally "safe".  The difference is that the proposed ternary lookupOrAdd does more stuff at once, which would be fine if it was a helper function built up on top stillExist, but it is not suitable as the primitive way of handling pointer invalidation.  The same design is used to build the has, put, and remove helpers.

I do think, though, that adding helpers for common use cases makes sense, but I would like their names to include something that makes it clear that there may have been invalidation so that future maintainers can be cautious.  E.g.:

 relookupIfInvalid(p, k)
 relookupIfInvalidAndAddIfRemoved(p, k, new_value)
 removePossiblyInvalidIfPresent(p, k)
 removePossiblyInvalid(p, k)            // asserts present

Long, I know, but it makes explicit the subtle game that is afoot.

> It is not straightforward to see that the usage is correct there given that the
> keys will be added or removed from the table.

If you're not sure, then use removePossiblyInvalidIfPresent.  But here, we can be sure, so removePossiblyInvalid would state our intention and assumption.

    
    

    
  
(In reply to comment #25)
> Yes, they are in the 'trivial' category.  But we cannot assume all uses are as
> well.  I suspect it's fairly common to stick strings in a hash table.

I would like to see a case when a string hash map needs lazy initialization that we are going to use in the engine soon. If there are no such case, then lets not generalize the interface until the need will come.

> I'm not sure what mythical interface you are talking about that cannot be
> abused ;-)

Currently the usage of the remove and add methods in the HashMap that take an entry pointer could be problematic or at least not so easy to analyze. But you are right that is is not easy to come up with something that is hard to abuse. Let me sleep over this!

    
    

    
  
(In reply to comment #26)
> (In reply to comment #25)
> > Yes, they are in the 'trivial' category.  But we cannot assume all uses are as
> > well.  I suspect it's fairly common to stick strings in a hash table.
> 
> I would like to see a case when a string hash map needs lazy initialization
> that we are going to use in the engine soon. If there are no such case, then
> lets not generalize the interface until the need will come.

The point was not to suggest one interface over the other; either way requires key matching.  But you are right that this only occurs with lazy-initialization + non-trivial hash, so we can not worry about it (for now).

I'll let you sleep though :)

    
    

    
  
Let consider a usage pattern for lazy adds if the generation() method would not exists with the current API that JS_GetStringBytes() would use:

Ptr p = lookup(key);
if (p)
    return p->value;
create_new_value_and_do_other_stuff();
AddPtr p2 = lookupForAdd(key);
if (p2) {
    // lost race
    destroy_new_value();
    return p2->value;
}
if (!add(p2, key, new_value)) {
    destroy_new_value();
    return NULL;
}
return new_value;

This is, of cause, suboptimal since it do double-lookup. On the other hand for a normal case of few collisions and when the race is not the second lookup would just do:

        /* Improve keyHash distribution. */
        keyHash *= sGoldenRatio;

        /* Avoid reserved hash codes. */
        if (keyHash < 2)
            keyHash -= 2;
        keyHash &= ~sCollisionBit;

        /* Compute the primary hash address. */
        uint32 h1 = hash1(keyHash, hashShift);
        Entry *entry = &table[h1];

        /* Miss: return space for a new entry. */
        if (entry->isFree()) {
            METER(stats.misses++);
            return AddPtr(*entry, keyHash);
        }

If we simply reuse the hash calculations from the first lookup then the code path would be:

        uint32 h1 = hash1(keyHash, hashShift);
        Entry *entry = &table[h1];

        /* Miss: return space for a new entry. */
        if (entry->isFree()) {
            METER(stats.misses++);
            return AddPtr(*entry, keyHash);
        }
 
So the would be single if here together with some shifts, adds and dereferences. This is not much worse then doing the generation check. Similarly for the case of single collision the would be 3 checks. That is worse than the generation check but is better than the proposed isValid checks since it would avoid the key compare.

This suggests to add a single extra function like that relookupIfInvalidAndAddIfRemoved(p, k, new_value) or relookupOrAdd for shortness. The function would use p only to get cached calculated hash. With that the usage becomes:

AddPtr p = lookupForAdd(key);
if (p)
    return p->value;
create_new_value_and_do_other_stuff();
Ptr p2 = relookupOrAdd(p, key, new_value);
if (!p2 || p2->value != new_value) {
    // lost race
    destroy_new_value();
    return p2 ? p2->value : NULL;
}
return new_value;


This does not deal with the remove case from jsarray.cpp, but that we can deal in another bug.

    
    

    
  

      
      
      
      

        Attached patch
          
          
        patch per comment above (obsolete)
        — 
          — Splinter Review
      

    


  
The new patch implements the comment 28 and adds relookupOrAdd function. It also adds debug-only mutationCount so the code can detect that were no mutations between lookupForAdd and the add call.

There also changes to consistently to use HashNumber, not uint32, for key hash operations. This way it should be easier to switch HashNumber to 64 bits on 64 bits platforms.

The patch is untested.

        Attachment #443089 -
        Attachment is obsolete: true

        Attachment #443091 -
        Attachment is obsolete: true

        Attachment #443301 -
        Attachment is obsolete: true

        Attachment #443089 -
        Flags: review?(lw)

        Attachment #443091 -
        Flags: review?(lw)

    
    

    
  
Looks good!  That is a good point that relookupOrAdd can be faster than stillValid (or anything composed of stillValid) since it is only trying to find a free entry, not a key match.  Also, unlike the lookupOrAdd schemes above, this approach doesn't put entries with not-yet-initialized values in the table that other lookups need to check for.

From a quick glance at the patch, I noticed that you changed HashTable::lookup to always setCollision().  What is the reason for this?  Code bloat?

Ironically, I put a 'TODO' on my list yesterday to change the type of sCollisionBit from unsigned to HashNumber, which you have fixed here.  (I think this is a real bug on systems where sizeof(unsigned) != sizeof(uint32) since HashTable does (keyHash & ~sCollisionBit).)

    
    

    
  
(In reply to comment #30)
> From a quick glance at the patch, I noticed that you changed HashTable::lookup
> to always setCollision().  What is the reason for this?  Code bloat?

The patch does setCollision(collisionBit) where collisionBit is passed by an argument and is either 0 or sCollisionBit. This way if the compiler decides to inline the lookup method then there would be no difference with the template version as the compiler should be able to optimize away useless x|= 0. But if the lookup would be a call then its avoids the code bloat for the price of doing x |= collisionBit with collisionBit == 0 during the ordinary lookup.

    
    

    
  
Ah, I see; I should have taken a slower glance :P

    
    

    
  

      
      
      
      

        Attached patch
          
          
        patch per comment above v2 (obsolete)
        — 
          — Splinter Review
      

    


  
The new patch fixes a bug in the deflated cache implementation in v1 (you are right, it is impossible to come up with something that can withstand rough handling), adds comments and make shure that all hash policy implementation classes returns HashNumber from the hash method.

        Attachment #443868 -
        Attachment is obsolete: true

        Attachment #444012 -
        Flags: review?(lw)

    
    

    
  
>+     *
>+     * The |add(p,k,v)| must not be used if after |lookupForAdd(l)| the map
>+     * can be altered (perhaps by other threads doing map mutations) before
>+     * the new value is put into the map. Use |relookupOrAdd(p,k,v) if it is
>+     * possible. That method relookups the map if necessary and inserts the
>+     * new value only if the key still does not exist.
>      */

I would like to suggest a slightly expanded version:

 *
 * N.B. The caller must ensure that no mutating hash table operations occur
 * between a pair of |lookupForAdd| and |add| calls. To avoid looking up the
 * key a second time, the caller may use the more efficient relookupOrAdd
 * method. For example, a mutation-handling version of the previous example:
 *
 *    HM::AddPtr p = h.lookupForAdd(3);
 *    if (!p) {
 *      call_that_may_mutate_h();
 *      if (!h.relookupOrAdd(p, 3, 'a'))
 *        return false;
 *    }
 *    const HM::Entry &e = *p;
 *    assert(p->key == 3);
 *    char val = p->value;
 */

> char *
> DeflatedStringCache::getBytes(JSContext *cx, JSString *str)
> {
>     JS_ACQUIRE_LOCK(lock);
>+    Map::AddPtr p = map.lookupForAdd(str);
>+    char *bytes = p ? p->value : NULL;
>+    JS_RELEASE_LOCK(lock);
>+
>+    if (bytes)
>+        return bytes;

Perhaps

  Map::AddPtr p;
  {
    AutoLock guard(lock);
    p = map.lookupForAdd(str);
    if (p)
      return p->value;
  }

>+    bytes = js_DeflateString(cx, str->chars(), str->length());
>+    if (!bytes)
>+        return NULL;
>+    char *bytesToFree = NULL;

A custom guard would avoid the control-flow dependency for freeing bytes:

struct FreeBytesGuard {
  JSContext *cx;
  char *bytes;
  FreeBytesGuard(JSContext *cx) : cx(cx), bytes(NULL) {}
  ~FreeBytesGuard() { if (bytes) if (cx) cx->free(bytes) else js_free(bytes); }
} guard(cx);

guard.bytes = js_DeflateString(cx, str->chars(), str->length());
if (!guard.bytes)
  return NULL;

etc.

>+#ifdef JS_THREADSAFE
>+    JS_ACQUIRE_LOCK(lock);
>+    bool ok = map.relookupOrAdd(p, str, bytes);
>+    if (!ok) {
>+        bytesToFree = bytes;
>+        bytes = NULL;
>+    } else if (p->value != bytes) {
>+        /* Some other thread has asked for str bytes .*/
>+        JS_ASSERT(!strcmp(p->value, bytes));
>+        bytesToFree = bytes;
>+        bytes = p->value;
>+    }
>     JS_RELEASE_LOCK(lock);
>+#else  /* !JS_THREADSAFE */

AutoLock?

>+    if (!map.add(p, str, bytes)) {
>+        bytesToFree = bytes;
>+        bytes = NULL;
>+    }

I think you need map.relookupOrAdd here too, unless there is something special about js_DeflateString and !defined(JS_THREADSAFE).

    
    

    
  
(In reply to comment #34)
> Perhaps
> 
>   Map::AddPtr p;
>   {
>     AutoLock guard(lock);
>     p = map.lookupForAdd(str);
>     if (p)
>       return p->value;
>   }

That would require to add a default constructor for AddPtr and to add more ifdef JS_THREADSAFE  noise to skip the AutoLock constructor. I am not sure that we want that. But I am fine to consider that in another bug.

> A custom guard would avoid the control-flow dependency for freeing bytes:
> 
> struct FreeBytesGuard {
>   JSContext *cx;
>   char *bytes;
>   FreeBytesGuard(JSContext *cx) : cx(cx), bytes(NULL) {}
>   ~FreeBytesGuard() { if (bytes) if (cx) cx->free(bytes) else js_free(bytes); }
> } guard(cx);

Such guard adds source complexity with not very clear benefits. The control flow dependency is very straightforward here IMO and does not justify the extra efforts to understand the guarded version.

> >+#else  /* !JS_THREADSAFE */
> >+    if (!map.add(p, str, bytes)) {
> >+        bytesToFree = bytes;
> >+        bytes = NULL;
> >+    }
> 
> I think you need map.relookupOrAdd here too, unless there is something special
> about js_DeflateString and !defined(JS_THREADSAFE).

The single threaded case is special because the table is not mutated between the lookup and the add calls. If js_DeflateString would run a GC when a malloc returns NULL then it would be necessary. But the engine is inherently unsafe currently against such GC. So I prefer not to penalize the single threaded case against hypothetical future usage.

    
    

    
  

      
      
      
      

        Attached patch
          
          
        v3
        — 
          — Splinter Review
      

    


  
The new version fixes the comments. It does not change the getBytes implementation.

        Attachment #444012 -
        Attachment is obsolete: true

        Attachment #444173 -
        Flags: review?

        Attachment #444012 -
        Flags: review?(lw)

    
    

    
  
(In reply to comment #35)
> That would require to add a default constructor for AddPtr and to add more
> ifdef JS_THREADSAFE  noise to skip the AutoLock constructor. I am not sure that
> we want that. But I am fine to consider that in another bug.

Ooops, I assumed there were #ifdefs hidden inside AutoLock (like ReentrancyGuard).

> Such guard adds source complexity with not very clear benefits. The control
> flow dependency is very straightforward here IMO and does not justify the extra
> efforts to understand the guarded version.

Yes, this case is rather straightforward so its fine to not have a guard.  I just use the general guideline "if you can't return false on error, because something would be leaked, add a guard", and this falls in that category.

> The single threaded case is special because the table is not mutated between
> the lookup and the add calls.

Ah.  Perhaps that special fact bears a comment?

But it all looks good, r+.

    
  

        Attachment #444173 -
        Flags: review? → review+

    
    

    
  
http://hg.mozilla.org/tracemonkey/rev/3a9808cb8d50
Whiteboard: fixed-in-tracemonkey

    
    

    
  
Robert Sayre - this has been backed out. What was the reason for that?
Whiteboard: fixed-in-tracemonkey

    
    

    
  
Sorry, this patch is still in the tree: http://hg.mozilla.org/tracemonkey/rev/3a9808cb8d50
Whiteboard: fixed-in-tracemonkey

    
    

    
  
Should DeflatedStringCache::getBytes report out of memory if relookupOrAdd fails?

    
    

    
  
(In reply to comment #41)
> Should DeflatedStringCache::getBytes report out of memory if relookupOrAdd
> fails?

Thanks for the catch!

    
    

    
  


  
I will land this later today after some testing

    
    

    
  
I am really feeling what Brendan was complaining about on IRC the other day regarding the non-local nature of allocation policies.  I only found the comment 42 bug because I had a similar bug.  I wonder if there is a non-awful way to make it clear, in a local context, that you are using the SystemAllocPolicy and thus must report errors yourself.  Definitely doesn't belong in this bug though...

    
    

    
  
http://hg.mozilla.org/tracemonkey/rev/e5ae28ee811b - followup to fix OOM reporting

    
    

    
  
(In reply to comment #44)
> I am really feeling what Brendan was complaining about on IRC the other day
> regarding the non-local nature of allocation policies. 

The getBytes implementation uses the system allocation policy because the hashing happens inside the lock while the errors should be reported outside the lock. But it is well too easy to forget that using hashing inside locks means OOM reporting on its own.

> I wonder if there is a non-awful way to make it clear, in a local context, that you are using the SystemAllocPolicy and thus must report errors yourself.

I suppose having a version of the map that would require to write something like add(p, key, value, NO_OOM_REPORTING) as long as the table as whole uses the system allocation would do that. But I am not sure that this is non-awful.

    
    

    
  
http://hg.mozilla.org/mozilla-central/rev/3a9808cb8d50
Status: NEW → RESOLVED
Closed: 14 years ago
Resolution: --- → FIXED

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: