511088 - GCHeap::FreeBlock can corrupt block list or cause acces violation

Status: VERIFIED INVALID

(Tamarin Graveyard :: Garbage Collection (mmGC), defect)

Description

[Mathieu Baron]

User-Agent:       Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 5.1; Trident/4.0; .NET CLR 1.1.4322; .NET CLR 2.0.50727; InfoPath.1; .NET CLR 3.0.4506.2152; .NET CLR 3.5.30729)
Build Identifier: tamarin-central-dab354bc047c

Code base: tamarin-central-dab354bc047c

Date:    2009-08-17
URL:     http://hg.mozilla.org/tamarin-central/archive/dab354bc047c.zip
File:     ./MMgc/GCHeap.cpp

Problem:
The code can try to access non-reserved memory when freeing blocks. This can lead to an Access Violation exception or memory data corruption.

Method:           
  (line 972)  void GCHeap::FreeBlock(HeapBlock *block) 

 

Description:
    The problem can occur with the following situation:

 

    Initial Memory state:
                   | . . . . . . . . . . . .|
                   | Uncomitted memory (C)  |
                   |                        |
              +->  +========================+  8192
              |    | Heap Block to free (B) |
              |    |                        |      <-- Trying to free this block
              |    |                        |
  Region -----|    +------------------------+  4096
  (0 to 8KB)  |    | Free Heap Block (A)    |
              |    |                        |
              |    |                        |
              +->  +========================+  0

Let’s say we want to free Block #B. 
 
The first thing that is done in the method is to check if the block is a full region to release it to the OS. 
Code: 
  (line 976)     // big block's that map to a region are free'd right away
  (line 977)     Region *r = AddrToRegion(block->baseAddr);
  (line 978)     if(block->baseAddr == r->baseAddr && block->endAddr() == r->reserveTop)
  (line 979)     {
  (line 980)         RemoveBlock(block);
  (line 981)         return;
  (line 982)     }

In this case, the block #B is not a full reserved region and we do not enter the "if" statement. We must continue to trace the method. 
 

Merge the Block #B with it’s predecessor (block #A) 
Code: 
  (line 989)    // Try to coalesce this block with its predecessor
  (line 990)    HeapBlock *prevBlock = block - block->sizePrevious;
  (line 991)    if (!prevBlock->inUse() && prevBlock->committed) {
  (line 992)        // Remove predecessor block from free list
  (line 993)        RemoveFromList(prevBlock);
  (line 994)                       
  (line 995)        // Increase size of predecessor block
  (line 996)        prevBlock->size += block->size;
  (line 997)                       
  (line 998)        block->size = 0;
  (line 999)        block->sizePrevious = 0;
  (line 1000)       block->baseAddr = 0;                
  (line 1001)                   
  (line 1002)       block = prevBlock;
  (line 1003)     }

 o  Memory status after merging blocks::
                   | . . . . . . . . . . . .|
                   | Uncomitted memory (C)  |
                   |                        |
              +->  +========================+  8192
              |    | Heap Block to free     |
              |    |                  (B+A) |      <-- Trying to free this block
              |    |                        |
  Region -----|    |                        |
  (0 to 8KB)  |    |                        |
              |    |                        |
              |    |                        |
              +->  +========================+  0
 
Merge the Block #B with it’s successor 
Code: 
    (line 1005) // Try to coalesce this block with its successor
    (line 1006) HeapBlock *nextBlock = block + block->size;
    (line 1007)                   
    (line 1008) if (!nextBlock->inUse() && nextBlock->committed) {
    (line 1009)     // Remove successor block from free list
    (line 1010)     RemoveFromList(nextBlock);
    (line 1011)                   
    (line 1012)     // Increase size of current block
    (line 1013)     block->size += nextBlock->size;
    (line 1014)     nextBlock->size = 0;
    (line 1015)     nextBlock->baseAddr = 0;
    (line 1016)     nextBlock->sizePrevious = 0;
    (line 1017) }

The BUG:
At line 1006, where the next block location is calculated, you have:
    (line 1018) // Try to coalesce this block with its successor
    (line 1019) HeapBlock *nextBlock = block + block->size;

… but there is no protection against accessing non-reserved memory. In the current case, we will try to access memory located at address 8192 but this memory is not commited: this will lead to an Access Violation or corrupting following if already commited for another purpose.


Reproducible: Always

Steps to Reproduce:
1. Reproduce usign the pattern described in details
Actual Results:  
Acces Violation exception or corrupted memory. 

This can lead to abortion of the garbage collection is such error occurs.

Expected Results:  
We should check for region boundaries.

This may explain Bug 489862 - HeapBlock list gets corrupted causing gc to hang:
https://bugzilla.mozilla.org/show_bug.cgi?id=489862

Comment 1

[Tommy Reilly]

I don't see the bug here.  We don't actually do a memory read on the uncommitted region, that would require dereferencing block->baseAddr somewhere.   nextBlock is always readable memory because we have a sentinel block at the end.  In either case (sentinel or more uncommitted memory) the nextBlock->committed check will prevent us from entering the if block.

Perhaps I'm missing something?

Comment 2

[Mathieu Baron]

I agree with you. I missed the sentinel block following the last block.