285580 - Accessing memory beyond allocation limit in jsgc.c ?

Status: VERIFIED INVALID

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

Consider the lines 598-606 from js_NewGCThing in jsgc.c:

            JSArenaPool *pool = &rt->gcArenaPool[i];
            JSArena *a = pool->current;
            jsuword p = a->avail;
            jsuword q = p + nbytes;

            if (q > (a->limit & ~GC_PAGE_MASK)) {
                thing = gc_new_arena(pool, nbytes);
            } else {

The lines assume that (a->limit & ~GC_PAGE_MASK) always gives the page boundary
where things ends. But this may not hold since after arena allocation a->limit
may exceed a->base + GC_ARENA_SIZE by some margin and (a->limit & ~GC_PAGE_MASK)
may point to the next page after the real boundary. 

Did I miss something?

Comment 1

[Igor Bukanov]

Attachment: Fix

Fix for the bug that would cause override into flags area if areana in fact
holds more then requested number of bytes for GC and there is page boundary in
the unused hole.

Comment 2

[Brendan Eich [:brendan]]

Proposed patch:
-            if (q > (a->limit & ~GC_PAGE_MASK)) {
+            if (q > FIRST_THING_PAGE(a) + GC_THINGS_SIZE) {

From jsgc.c:
#define FIRST_THING_PAGE(a)     (((a)->base + GC_FLAGS_SIZE) & ~GC_PAGE_MASK)

Wish to prove:
    ((a->base + GC_FLAGS_SIZE) & ~GC_PAGE_MASK) + GC_THINGS_SIZE ==
    (a->limit & ~GC_PAGE_MASK)

From jsarena.c:JS_AreneAllocate, with nb == GC_ARENA_SIZE and extra == 0:
    hdrsz = sizeof *a + pool->mask;
    gross = hdrsz + GC_ARENA_SIZE;
    a->base = JS_ARENA_ALIGN(pool, a + 1);
    a->limit = (jsuword)a + gross;

From jsarena.h:
#define JS_ARENA_ALIGN(pool, n) (((jsuword)(n) + (pool)->mask) & ~(pool)->mask)

Substituting:
    a->base  = ((jsuword)(a + 1) + pool->mask) & ~pool->mask;
    a->limit = (jsuword)a + sizeof *a + pool->mask + GC_ARENA_SIZE;

Rearranging second line to state address of a in terms of a->limit:
    a = a->limit - sizeof *a - pool->mask - GC_ARENA_SIZE;

Substituting in a->base definition (note: (a + 1) is ((jsuword)a + sizeof *a)):
    a->base = ((a->limit - sizeof *a - pool->mask - GC_ARENA_SIZE + sizeof *a)
               + pool->mask) & ~pool->mask;
            = (a->limit - GC_ARENA_SIZE) & ~pool->mask;

Substitute into proposed patch's replacement for (a->limit & ~GC_PAGE_MASK):
    ((((a->limit - GC_ARENA_SIZE) & ~pool->mask) + GC_FLAGS_SIZE)
     & ~GC_PAGE_MASK) + GC_THINGS_SIZE

Note that ((a + b) & ~c) distributes as (a & ~c) + (b & ~c) if a > c && b > c:
    ((((a->limit - GC_ARENA_SIZE) & ~pool->mask) & ~GC_PAGE_MASK)
     + (GC_FLAGS_SIZE & ~GC_PAGE_MASK)) + GC_THINGS_SIZE

Since pool->mask < GC_PAGE_MASK, this simplifies to:
    (((a->limit - GC_ARENA_SIZE) & ~GC_PAGE_MASK)
     + (GC_FLAGS_SIZE & ~GC_PAGE_MASK)) + GC_THINGS_SIZE

Distributing again:
    (((a->limit & ~GC_PAGE_MASK) - (GC_ARENA_SIZE & ~GC_PAGE_MASK))
     + (GC_FLAGS_SIZE & ~GC_PAGE_MASK)) + GC_THINGS_SIZE

From jsgc.c, GC_ARENA_SIZE = GC_THINGS_SIZE + GC_FLAGS_SIZE, and all 3 terms
are 0 mod GC_PAGE_SIZE (so == themselves & ~GC_PAGE_MASK).  Substituting and
rearranging:

    ((a->limit & ~GC_PAGE_MASK)
    - (GC_THINGS_SIZE + GC_FLAGS_SIZE)
    + GC_FLAGS_SIZE + GC_THINGS_SIZE

Or just:

    (a->limit & ~GC_PAGE_MASK)

Q.E.D.

Either this bug is INVALID, or my proof is wrong.  Check it carefully!

/be

Comment 3

[Brendan Eich [:brendan]]

I knew I was rushing.  This step is stated incorrectly:

Note that ((a + b) & ~c) distributes as (a & ~c) + (b & ~c) if a > c && b > c:

We need a Lemma.  Revise this step to read:

Note that ((a + b) & ~c) distributes if a > c && b > c && ((a + b) & ~c) != 0
(see Lemma):
    ((((a->limit - GC_ARENA_SIZE) & ~pool->mask) & ~GC_PAGE_MASK)
     + (GC_FLAGS_SIZE & ~GC_PAGE_MASK)) + GC_THINGS_SIZE

I'll put a revised proof up soon (in a meeting now, can't think straight while
listening).

/be

Comment 4

[Igor Bukanov]

(In reply to comment #3)
> I knew I was rushing.  This step is stated incorrectly:

But for the proof you just need ((a + b) & ~c) == (a & ~c) + b if b & ~c == b. 

So the bug is indeed invalid and I got double-blunder :(. The first time was
when I filed the bug and I forgot that GC_ARENA_SIZE % PAGE_SIZE == 0 in CVS
after spending some time on patches for bug 280844 which would make
GC_ARENA_SIZE % PAGE_SIZE != 0 and where the change from the above is essential.

And second blunder is now while posting an old patch without checking.

> 
> Note that ((a + b) & ~c) distributes as (a & ~c) + (b & ~c) if a > c && b > c:
> 
> We need a Lemma.  Revise this step to read:
> 
> Note that ((a + b) & ~c) distributes if a > c && b > c && ((a + b) & ~c) != 0
> (see Lemma):
>     ((((a->limit - GC_ARENA_SIZE) & ~pool->mask) & ~GC_PAGE_MASK)
>      + (GC_FLAGS_SIZE & ~GC_PAGE_MASK)) + GC_THINGS_SIZE
> 
> I'll put a revised proof up soon (in a meeting now, can't think straight while
> listening).
> 
> /be

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> (In reply to comment #3)
> > I knew I was rushing.  This step is stated incorrectly:
> 
> But for the proof you just need ((a + b) & ~c) == (a & ~c) + b if b & ~c == b.

Indeed -- simpler proof!  My meeting is over, and I've had coffee now, but you
have finished the proof.  Thanks.

/be