c++ - Bounds check in 64bit hardware -

c++ - Bounds check in 64bit hardware -

i reading blog on 64-bit firefox edition on hacks.mozilla.org.

the author states:

for asm.js code, increased address space lets utilize hardware memory protection safely remove bounds checks asm.js heap accesses. gains pretty dramatic: 8%-17% on asmjs-apps-*-throughput tests reported on arewefastyet.com.

i trying understand how 64-bit hardware have automatic bounds check (assuming compiler hardware support) c/c++. not find answers in so. found one technical paper on subject, not able grasp how done.

can explain 64-bit hardware aids in bounds check?

most modern cpus implement virtual addressing/virtual memory - when programme references particular address, address virtual; mapping physical page, if any, implemented cpu's mmu (memory management unit). cpu translates every virtual address physical address looking in page table os set current process. these lookups cached tlb, of time there's no delay. (in non-x86 cpu designs, tlb misses handled in software os.)

so programme accesses address 0x8050, in virtual page 8 (assuming standard 4096 byte (0x1000) page size). cpu sees virtual page 8 mapped physical page 200, , performs read @ physical address 200 * 4096 + 0x50 == 0xc8050. (just tlb caches page table lookups, more familiar l1/l2/l3 caches cache accesses physical ram.)

what happens when cpu not have tlb mapping virtual address? such thing occurs because tlb of limited size. reply cpu generates page fault, handled os.

several outcomes can occur result of page fault:

one, os can "oh, wasn't in tlb because couldn't fit it". os evicts entry tlb , stuffs in new entry using process's page table map, , lets process maintain running. happens thousands of times per sec on moderately loaded machines. (on cpus hardware tlb miss handling, x86, case handled in hardware, , not "minor" page fault.) two, os can "oh, virtual page isn't mapped right because physical page using swapped disk because ran out of memory". os suspends process, finds memory utilize (perhaps swapping out other virtual mapping), queues disk read requested physical memory, , when disk read completes, resumes process freshly filled page table mapping. (this "major" page fault.) three, process trying access memory no mapping exists - it's reading memory shouldn't be. commonly called segmentation fault.

the relevant case number 3. when segfault happens, default behavior of operating scheme abort process , things write out core file. however, process allowed trap own segfaults , effort handle them, perhaps without stopping. things interesting.

we can utilize our advantage perform 'hardware accelerated' index checks, there few more stumbling blocks nail trying so.

first, general idea: every array, set in own virtual memory region, of pages contain array info beingness mapped usual. on either side of real array data, create virtual page mappings unreadable , unwritable. if effort read outside of array, you'll generate page fault. compiler inserts own page fault handler when made program, , handles page fault, turning index-out-of-bounds exception.

stumbling block number one can mark whole pages beingness readable or not. array sizes may not multiple of page size, have problem - can't set fences before , after end of array. best can leave little gap either before origin of array or after end of array between array , nearest 'fence' page.

how around this? well, in java's case, it's not easy compile code performs negative indexing; , if does, doesn't matter anyway because negative index treated it's unsigned, puts index far ahead of origin of array, means it's nail unmapped memory , cause fault anyway.

so align array end of array butts right against end of page, ('-' means unmapped, '+' means mapped):

-----------++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------- | page 1 | page 2 | page 3 | page 4 | page 5 | page 6 | page 7 | ... |----------------array---------------------------|

now, if index past end of array, it'll nail page 7, unmapped, cause page fault, turn index out of bounds exception. if index before origin of array (that is, it's negative), because it's treated unsigned value, it'll become big , positive, putting far past page 7 1 time again causing unmapped memory read, causing page fault, 1 time again turn index out of bounds exception.

stumbling block number 2 should leave a lot of unmapped virtual memory past end of array before map next object, otherwise, if index out of bounds, far, far, far out of bounds, might nail valid page , not cause index-out-of-bounds exception, , instead read or write arbitrary memory.

in order solve this, utilize huge amounts of virtual memory - set each array own 4 gib part of memory, of first n few pages mapped. can because we're using address space here, not actual physical memory. 64 bit process has ~4 billion chunks of 4 gib regions of memory, have plenty of address space work before run out. on 32-bit cpu or process, have little address space play around with, technique isn't feasible. is, many 32-bit programs today running out of virtual address space trying access real memory, nevermind trying map empty 'fence' pages in space seek utilize 'hardware accelerated' index range checks.

c++ c x86-64