Accessing memory beyond allocation limit in jsgc.c ?

VERIFIED INVALID

Status

()

Core
JavaScript Engine
VERIFIED INVALID
13 years ago
12 years ago

People

(Reporter: Igor Bukanov, Unassigned)

Tracking

Trunk
x86
Linux
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment)

(Reporter)

Description

13 years ago
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?
(Reporter)

Comment 1

13 years ago
Created attachment 199069 [details] [diff] [review]
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.
Attachment #199069 - Flags: review?(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
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
(Reporter)

Comment 4

13 years ago
(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

Status: NEW → RESOLVED
Last Resolved: 13 years ago
Resolution: --- → INVALID
(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
Status: RESOLVED → VERIFIED
(Reporter)

Updated

12 years ago
Attachment #199069 - Flags: review?(brendan)
You need to log in before you can comment on or make changes to this bug.