614126 - Decouple CodeAlloc block size from allocation size

Status: RESOLVED FIXED

(Tamarin Graveyard :: Baseline JIT (CodegenLIR), defect)

Description

[Rick Reitmaier]

Currently, codeAlloc is hard-wired such that blocks are handed out to client that are the same size as those requested from the OS, or more correctly via the allocCodeChunk() SPI.

This is particularly problematic in the case of ARM, where block requests much be < 1 page (constants placed in code memory must be available 'near' the instruction that uses them).

Comment 1

[Rick Reitmaier]

Attachment: decouple code block requests from initial allocation

This bug carries on from where bug 601724 left off.  In that the last patch (attachment 488398 [details] [diff] [review]) is refined and re-posted to this bug.

In particular, Ed brought up the issue of ensuring correct block size and my response was that there is an existing bug.  This patch fixes that bug and accommodates the additional increase in block size needed by this change.

Passes all regressions using 4KB bytePerAlloc size.

Comment 2

[Rick Reitmaier]

Attachment: decouple code block requests from initial allocation

Posted wrong patch for review

Comment 3

[Edwin Smith]

Comment on attachment 492525 [details] [diff] [review]
decouple code block requests from initial allocation

unrelated to the patch:  the optional nBytes parameter to Assembler::codeAlloc() is really ugly, and now it's worse with the new optional byteLimit parameter.  Could we account for allocated bytes somewhere less intrusive?  For example, after we're finished, we could use CodeAlloc::size() to just add up the size of all the fragments.

I can't tell if the new code is right any more than I can tell if the old code is right, unfortunately.

I tried to write a derivation of the correct boundary values, and got pretty confused each time.  I think what this patch needs is a math-proof like comment, that explains the raw constraints, then derives boundary value constants from first principles.

        NanoAssert(!byteLimit || byteLimit > sizeofMinBlock + minAllocSize);
                                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
should probably be "minByteLimit" and derived explicitly in a header comment.

    if ( b->size() <= 2*desired )
                      ^^^^^^^^^^

From the context, i guess this is minFreeBlockSize?

    NanoAssert(b->size() >= 2*( sizeofMinBlock + minAllocSize ) );
                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The comment says this ensures that addRemainder is able to split 
a free block in two.  But it also uses words like "roughly" which make
me really concerned in this area of the code.

in addRemainder(), minHole is defined as:

    size_t minHole = 2*sizeofMinBlock + minAllocSize;

I think it also should go in the header, and i wonder if the lack of parens
here is a bug, compared to that above assert, or is the assert wrong?

   minHole += 2*sizeofMinBlock + 2*minAllocSize;       // additional space needed to ensure that alloc() with a byteLimit can split a free block in 2

defining minHole in two statements consisting of all cosntants, is confusing;
the derivation should account for all constraints.

Then, every predicate in CodeAlloc::alloc(), and free(), should be written
using the boundary constants that are really clear what they're for.

nits:  
 * capitalize and punctuate all new comments
 * no spaces after ( and before ).  Spaces around *.  e.g.

+            if ( b->size() <= 2*desired )

should be

             if (b->size() <= 2 * desired)

Several other places have formatting mistakes too.

(and the 2 * desired should be one of the painfully-obvious-what-it-means boundary constants).

Somewhere, all the derived boundary constants should be compared to each other
in a static assert that is obviously correct from the initial description
of the constraints.

Comment 4

[Rick Reitmaier]

Attachment: revamped

Revamped and more (hopefully) straightforward approach;
 - added helper methods to compute bytes needed for headers and minimum sized block.  This helped clear up most of the confusion for me.
 - alloc() with a byteLimit no longer tries to partition up the space equally for small blocks and instead returns a minimum sized block placing the remainder on the free list, available for the next call.  This change means that all the complex proof requirements should no longer be necessary, as byteLimit > blockSpaceFor(2) is sufficient to guarantee correctness (Please double check the asserts, which amount to the proof).
- Fixed 2 bugs in addRemainder().  After converting to xxxSpaceFor() calls, an issues with minHole calculation became apparent.  In addition, the subtraction in the check was susceptible to underflow.

Comment 5

[Rick Reitmaier]

(In reply to comment #4)
> Created attachment 498417 [details] [diff] [review]
> revamped

Passing regressions, but I'm seeing a slight slowdown on beagleboard ARM.  Moving the pagesPerAlloc back to 1 fixes it, so I'm guessing that the overhead of managing of blks is greater than the cost to malloc()'ing another page in this architecture.

This behaviour is not observable on osx x86-32, as no significant differences exist pre/post patch.

I'm not sure how this will behave on android but thinking the best course of action is to land the patch without the pagesPerAlloc change and then open a new bug if needed to study behaviour changes associated with it.

Will post new patch shortly.

Comment 6

[Rick Reitmaier]

Attachment: revamped

same as attachment 498417 [details] [diff] [review], except restored pagesPerAlloc to 1 for ARM.

Performance testing shows flat results in x86-32 and ARM beagleboard.

Comment 7

[Edwin Smith]

Comment on attachment 498463 [details] [diff] [review]
revamped


Assembler.h: you have the default argument for codeAlloc() declared as size_t byteLimit=0, and also in CodeAlloc.h you have the default arg for alloc() declared as byteLimit=0.  Since Assembler::codeAlloc() calls CodeAlloc::alloc(), and that is the only callsite, the default on the Assembler api is the one that "rules".

If you make the default value be a large number (greater than CodeAlloc::bytesPerAlloc), then you don't need the check for zero here:

>+        // grab a block
>+        NanoAssert(!byteLimit || byteLimit > blkSpaceFor(2));

or here:

>+        // block is too big, break it apart?
>+        if (byteLimit > 0 && b->size() > byteLimit) {

This should be deleted:

>+        //memset(b->start(), 0xCC, b->size()); // INT 3 instruction

nit: capitalization, here:

>+        // block is too big, break it apart?

and several other places. (add punctuation too; all new comments that
read like sentences should be capitalized and punctuated.).

Nothing else looks obviously wrong; all bugs are guaranteed to be super
subtle from here on out.

Comment 8

[Rick Reitmaier]

(In reply to comment #7)
> 
> size_t byteLimit=0, and also in CodeAlloc.h 

will remove before landing patch. 

> 
> If you make the default value be a large number (greater than
> CodeAlloc::bytesPerAlloc), then you don't need the check for zero here:
> 

True, but I'd argue that byteLimit=0 is 'more obvious' than byteLimit=bytesPerAlloc+1.

> 
> This should be deleted:
> 
> >+        //memset(b->start(), 0xCC, b->size()); // INT 3 instruction
> 

will do.

> nit: capitalization, here:
> 
> >+        // block is too big, break it apart?
> 
> and several other places. (add punctuation too; all new comments that
> read like sentences should be capitalized and punctuated.).
> 

For phrases contained on a single line comment I don't usually fully punctuate, as I find it adds clutter and distracts from the surrounding context/code.

For a block comment, I fully agree that the text should be treated (and thus punctuated) as English prose. 

> Nothing else looks obviously wrong; all bugs are guaranteed to be super
> subtle from here on out.

hopefully with the fix to addRemainder(), the addition of asserts and the clarity of the spaceFor() routines, we'll be better protected.

Comment 9

[Nicholas Nethercote [inactive]]

Comment on attachment 498463 [details] [diff] [review]
revamped

>+        NanoAssert(b->size() >= minAllocSize);
>+        b->next = 0; // not technically needed (except for debug builds), but good hygine.

s/hygine/hygiene/


>         debug_only(sanity_check();)
>+        //memset(b->start(), 0xCC, b->size()); // INT 3 instruction

What's this, why is it commented out?

r=me with those nits fixed.

Comment 10

[Rick Reitmaier]

rreitmai http://hg.mozilla.org/projects/nanojit-central/rev/2c9dc64162bd

Comment 11

[Rick Reitmaier]

(In reply to comment #9)
> Comment on attachment 498463 [details] [diff] [review] 
> What's this, why is it commented out?

Fixed typo and memset 0xCC was a debugging aid; see addRemainder() for similar usage.  Anyway I removed it in the final patch.

Comment 12

[Tamarin Bot]

changeset: 5728:441d023515f0
user:      Rick Reitmaier <[e-mail]>
summary:   Bug 614126 - Decouple CodeAlloc block size from allocation size (r+edwsmith,nnethercote)

http://hg.mozilla.org/tamarin-redux/rev/441d023515f0

Comment 13

[Nicholas Nethercote [inactive]]

A dumb, belated question:  bytesPerAlloc is already 4096 on ARM.  And NJ_MAX_CPOOL_OFFSET is also 4096 bytes.  So how can we get a block that is larger than 'byteLimit'?

Comment 14

[Rick Reitmaier]

Correct.  I saw some slight variation on the arm devices I was testing against re: comment 5, so decided to land with no ARM change for now. 

Will revisit (and open new bug) if necessary.

Comment 15

[Nicholas Nethercote [inactive]]

http://hg.mozilla.org/tracemonkey/rev/013a2d11f493

Comment 16

[Chris Leary [:cdleary] (not checking bugmail)]

cdleary-bot mozilla-central merge info:
http://hg.mozilla.org/mozilla-central/rev/013a2d11f493