Make Holes

Remember, our goal is to arrange for control of the buffer that follows the vulnerable buffer. Assuming defragmentation worked, we should have a number of contiguous buffers at the end of the heap, all roughly the same size as the (yet to be allocated) vulnerable buffer (Figure 3). The next step is to free every other of these contiguous buffers, leaving alternating buffers and holes, all matching the size of the vulnerable buffer. The first step in achieving this is

for(i=900; i<1000; i+=2){
   delete(bigdummy[i]);
}

Unfortunately, at this point, we have a problem. Simply deleting an object in JavaScript does not immediately result in the object's space on the heap being freed. Space on the heap is not relinquished until garbage collection occurs. Internet Explorer provides a CollectGarbage() method that immediately triggers garbage collection [2], but other implementations do not. In particular, WebKit does not. Accordingly, we digress with a discussion of garbage collection in WebKit.

Our inspection of the WebKit source code turned up three main events that can trigger garbage collection. To understand these events, one must be familiar with the way WebKit's JavaScript manages objects.

The implementation maintains two structures, primaryHeap and numberHeap, each of which is essentially an array of pointers to CollectorBlock objects. A CollectorBlock is a fixed-sized array of Cells and each Cell can hold a JSCell object (or derivative). Every JavaScript object occupies a Cell in one of these heaps. Large objects (such as arrays and strings) occupy additional memory on the system heap. We refer to this additional system heap memory as associated storage.

Each CollectorBlock maintains a linked list of those Cells that are free. When an allocation is requested, and no free Cells are available in any existing CollectorBlocks, a new CollectorBlock is allocated.

All JavaScript objects deriving from JSObject are allocated on the primaryHeap. The numberHeap is reserved for NumberImp objects. Note that the latter do not correspond to JavaScript Number objects, but instead are typically short lived number objects corresponding to intermediate arithmetic computations.

When garbage collection is triggered, both heaps are examined for objects with zero reference counts, and such objects (and their associated storage if any) are freed.

We now return to the three events we found that trigger garbage collection. They are

1. Expiration of a dedicated garbage collection timer.
2. An allocation request that occurs when all of the particular heap's CollectorBlocks are full.
3. Allocation of an object with sufficiently large associated storage (or a number of such objects).

The first of these events is not very useful, because JavaScript has no sleep routine, and any kind of sizeable delay in the script runs the risk of causing the ``Slow Script'' dialog to appear.

The last of these events depends on the number of objects in the primaryHeap and the sizes of their associated storage. Experiments suggest that the state of the primaryHeap varies greatly with the number of web pages open in the browser and the degree to which these pages use JavaScript. Consequently, triggering reliable garbage collection with this event is difficult.

On the other hand, the numberHeap appears to be relatively insensitive to these variations. Heuristically, the numberHeap maintains only one allocated CollectorBlock, even during significant web browsing of pages with JavaScript. Since the numberHeap CollectorBlock has 4062 Cells, JavaScript code that allocates at least this many NumberImps should trigger garbage collection. As an example, manipulation of doubles is one operation that results in a NumberImp allocation from the numberHeap, so the following JavaScript code can be used for garbage collection triggering:

for(i=0; i<4100; i++){
  a = .5;
}