72034 - JS_ArenaRealloc assumes realloc preserves alignment

Status: VERIFIED FIXED

(Core :: JavaScript Engine, defect, P1)

Description

[Brendan Eich [:brendan]]

And it just ain't so.  Reported by Jeremy Condit <[e-mail]>, patch
supplied by Jeremy and nit-picked by me, coming right up.

/be

Comment 1

[Brendan Eich [:brendan]]

Asa, this fixes a range of subtle long-string-in-JS-loses-chars and worse bugs
on some platforms, which we may not be seeing yet.  It's a safe fix, although I
need r/sr= from shaver and jband as usual.  Cc'ing you in case we want it for
0.8.1 as a preventive measure.

/be

Comment 2

[Brendan Eich [:brendan]]

Attachment: proposed fix

Comment 3

[Phil Schwartau]

Compare bug 69397 : "strings in document trashed or changed"

Comment 4

[Brendan Eich [:brendan]]

*** Bug 69397 has been marked as a duplicate of this bug. ***

Comment 5

[Brendan Eich [:brendan]]

Attachment: shaver wants a newsize temporary; i'm easy

Comment 6

[John Bandhauer]

r/sr=jband I'm 90% sure I understand this right. I wouldn't trust *myself* on 
the correctness of this sort of twiddling w/o seeing the memmove case in a 
debugger. FWIW, I'm a wimp and would add in the (unnecessary) parens to the use 
of the sizeof operator.

Also, It looks like plarena has no realloc. This was a jsarena only addition?

Comment 7

[Brendan Eich [:brendan]]

Targeting at 0.8.1.  Where's my review love?  Shaver gave me r= over IRC.

/be

Comment 8

[John Bandhauer]

brendan: See previous comment. How many more do you want? :)

Comment 9

[Brendan Eich [:brendan]]

jband: I had a nice proof based on modular arithmetic half-way worked out to get
your last 10%, but Mozilla crashed (in docshell code).  I'll go with 90%.  Thanks,

/be

Comment 10

[John Bandhauer]

Ah yes, the old "My dogfood ate my homework" ploy. I know it well :) Yes, please
don't waste your time recreating the proof. I'm good with the patch.

Comment 11

[Mike Shaver (:shaver emeritus)]

Damn, I wanted to see the proof!

Comment 12

[Brendan Eich [:brendan]]

I checked the fix in.

Let a' be the reallocated arena, A the alignment modulus. To prove the memmove
is safe, we need only prove that it can't load from beyond the original size
bytes in a, or store outside the size bytes in a'.  Note that the gross
allocation containing size is (size + A - 1) bytes in length.  The memmove
copies size bytes from a' + boff to a'->base.

Ignore casts and treat pointers in expressions as byte cursors.  We need to show
that |a' + boff - a'->base| < A:

|a' + boff - a'->base| = |a' + a->base - a - a'->base|
                       = |(a->base - a) - (a'->base - a')|

Note that sizeof *a is 16, JS_ARENA_ALIGN(pool,n) is a strength-reduced version
of ((n + A - 1) / A) * A, and a->base = JS_ARENA_ALIGN(a + 16):

a->base     = ((a + 16 + A - 1) / A) * A
            = ((a + 16) % A == 0) ? a + 16 : a + 16 + A - ((a + 16) % A)
a->base - a = ((a + 16) % A == 0) ? 16     : 16 + A - ((a + 16) % A)

Therefore the maximum distance

Max|a' + boff - a'->base| = |A - ((a + 16) % A)|

where (a + 16) % A != 0 and (a' + 16) % A == 0 (or vice versa).

|A - ((a + 16) % A)| = A - ((a + 16) % A)
                     < A

Q.E.D.

NSPR's plarena.c derives from prarena.c from 1995 (written by yours truly,
cloned at that time by me as jsarena.c for standalone JSRef, never re-unified
with NSPR when NSPR 2.0 renamed prarena.c as plarena.c).  There's a bug on
larryh's list (bug 45343) to get the recent jsarena.c fixes and extensions into
plarena.c.  plarena does need this realloc optimization: JS_ArenaRealloc was
added as part of the fix for bug 33390, to avoid O(bad) space growth when
JS_ARENA_GROW is used to extend an allocation that consumes an entire arena.

/be

Comment 13

[alex.dent]

thanks a lot, this indeed fixes all the problems with changed strings i observed
in bug 69397! very cool.

Comment 14

[Phil Schwartau]

Based on [e-mail]'s comment above, marking VERIFIED