41381 - JSArena arena_freelist thread safety problems

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Brendan Eich [:brendan]]

Where do I start?  Assuming addresses won't be replayed by malloc across a
compare and swap is one biggie.  Is there any "lock-free" way to maintain this
linked list?  I'm beginning to suspect not.

/be

Comment 1

[Brendan Eich [:brendan]]

Mine all mine.

/be

Comment 2

[Wan-Teh Chang]

I remember we fixed this in NSPR by adding a lock
around arena_freelist.  Is that not thread safe,
or are you going after a lock-free solution?

On Alpha and PowerPC (and MIPS too, I think), you
can use load-locked and store-conditional, which
don't have the "ABA" problem of compare-and-swap.
Unfortunately Intel x86 and Sparc only have
compare-and-swap.

Comment 3

[Brendan Eich [:brendan]]

I was hoping for lock-free, but a lock will do.  It should not be contentious,
either (my best guess), but we'll have to measure to be sure.  JS uses arenas
for compiler temporaries and for runtime stacks.  But it uses large enough sizes
that I believe it won't be allocating and freeing frequently.

/be

Comment 4

[Brendan Eich [:brendan]]

This'll be fixed soon.

/be

Comment 5

[Brendan Eich [:brendan]]

Attachment: pre-patch, fixes a bug found by tellme folks in jsarena.[ch]

Comment 6

[Brendan Eich [:brendan]]

Attachment: complete patch; I might still fuss with unchecked JS_NEW_LOCK call...

Comment 7

[Brendan Eich [:brendan]]

Attachment: final patch, which adds JS_ArenaShutDown to destroy arena_freelist_lock

Comment 8

[Wan-Teh Chang]

I reviewed the "final patch" (attachment id=11271).
Note that I only reviewed the portion related to arena_freelist_lock.

1. In jsarena.c, function JS_ArenaShutDown has two problems.
   First, arena_freelist is apparently a typo for arena_freelist_lock.
   Second, arena_freelist_lock is defined only if JS_THREADSAFE is
   defined, so all this code should be ifdef'd with JS_THREADSAFE.

2. jsarena.h: just wondering why you add a new function JS_ArenaShutDown
   rather than just destroying arena_freelist_lock in JS_ArenaFinish.

Comment 9

[Brendan Eich [:brendan]]

Thanks, wtc.  Re: 1 -- augh!  I thought I had built this code before attaching
the patch.  I think I built only the JS shell, which is !JS_THREADSAFE, so the
JS_DESTROY_LOCK macro does nothing and there is no compile-time error.

Re: 2, the problem I face with how this old code is used in JS is this:
JS_ArenaFinish is called often, via JS_GC (js_ForceGC).  It wants to free all
arenas cached on the freelist.  Maybe it should be called JS_FlushArenaFreeList
or some such.  There is no JS_ArenaStartUp or JS_ArenaShutDown code in the
current top of trunk, however.  Per-process init has been implicit, and can
continue to be so long as the first thread to call JS_InitArenaPool does not
race with any other thread.

So in order to minimize changes, I'm keeping per-process init (let's call it
"StartUp") implicit.  But I can't destroy the arena_freelit_lock in
JS_ArenaFinish, without opening a race to recreate the lock.  Besides, it
doesn't hurt to keep that lock around while JS is embedded.  But we must free
that lock at "ShutDown" time, hence the new JS_ArenaShutDown.

Thanks again for your comments, keep them coming if you have more.  New patch
coming up.

/be

Comment 10

[Brendan Eich [:brendan]]

Attachment: new really-final patch (I hope)

Comment 11

[Brendan Eich [:brendan]]

Attachment: I give up

Comment 12

[Wan-Teh Chang]

I reviewed patch id=11308.  I found that we
can write JS_ArenaFinish like this to make
the critical section shorter:

JS_PUBLIC_API(void)
JS_ArenaFinish()
{
    JSArena *a, *next;

    JS_ACQUIRE_LOCK(arena_freelist_lock);
    a = arena_freelist;
    arena_freelist = NULL;
    JS_RELEASE_LOCK(arena_freelist_lock);
    for ( ; a; a = next) {
        next = a->next;
        free(a);
    }
}

You may want to replace the for loop by a while
loop depending on your taste.

Comment 13

[Brendan Eich [:brendan]]

Attachment: incorporate wtc's suggestion for JS_ArenaFinish

Comment 14

[Brendan Eich [:brendan]]

Attachment: wtc pointed out another ancient bug, in JS_ArenaAllocate

Comment 15

[Brendan Eich [:brendan]]

I filed bug 45343 on plarena.[ch] in NSPR, for inheriting similar bugs from the
old NSPR1 code.

/be

Comment 16

[Brendan Eich [:brendan]]

Last (must be final?) patch checked in.  Thanks especially to troy and wtc.

/be

Comment 17

[Brendan Eich [:brendan]]

That crazy for loop in JS_ArenaAllocate got me: I tried to break out of it early
when inverting the if (a->next) {...;continue;} clause and what followed, which
fails to update pool->current = a.  Bad things ensue.  Ultimate Mega Turbo patch
coming up.

/be

Comment 18

[Brendan Eich [:brendan]]

Attachment: stick a fork in me, i'm done

Comment 19

[Brendan Eich [:brendan]]

Fix checked in.

/be

Comment 20

[Brendan Eich [:brendan]]

There's a subtle bug in the jsarena.c change that can bust the JS GC.  Patch for
that regression coming up.

/be

Comment 21

[Brendan Eich [:brendan]]

Adding jband, who ran into the regression in xpcshell.

/be

Comment 22

[Brendan Eich [:brendan]]

Attachment: fix to keep parallel arenas in sync (arenasize matching)

Comment 23

[Brendan Eich [:brendan]]

Looking for r= here, quick, before too many people are hosed.

/be

Comment 24

[Brendan Eich [:brendan]]

Attachment: comment fix (not greater than, instead of less than)

Comment 25

[John Bandhauer]

r=[e-mail]

Comment 26

[Brendan Eich [:brendan]]

Jband tested and reviewed, I'm in.  Shoot me now!

/be

Comment 27

[Blake Ross]

something happened to the resolution...

Comment 28

[Blake Ross]

marking fixed

Comment 29

[Phil Schwartau]

Rubber-stamp Verify -