Allocate the mark stack as part of heap allocation.
Previously, the mark stack would be allocated and freed as part of a
garbage collection. This had two deficiencies. First, allocating the
mark stack requires a file descriptor to open the ashmem device. If
there are file descriptors free at the time of an garbage collection
the runtime is forced to abort. Second, it turns out that ashmem is
slow. I wrote a benchmark that evaluates the speed of various methods
for allocating memory 1e6 times in a tight loop. The results are
summarized below
madvise 2.
279357911
mprotect 3.
451385496
mmap MAP_ANONYMOUS 4.
408111572
mmap /dev/zero 14.
232635436
ashmem 35.
414886504
The madvise algorithm preallocated some virtual memory, advise the
pages needed during a garbage collection, and advised the same pages
not need afterward. It is not clear if this actually causes pages to
be made available to other processes or mappings in between garbage
collections.
The mprotect algorithm reserves some virtual memory and commit its
pages during a garbage collection and then uncommit its pages
afterward. This releases pages and, like all slower methods, runs the
risk of being unable to allocate those pages afterward if physical
pages are unavailable.
The mmap MAP_ANONYMOUS algorithm allocates and frees virtual memory
each iteration. This is surprisingly competitive with the methods
that preallocate memory and an order of magnitude faster than ashmem.
The mmap /dev/zero algorithm is similar to MAP_ANONYMOUS but allocates
anonymous memory through a file mapping. It is substantially more
expensive than MAP_ANONYMOUS.
The ashmem algorithm is what is currently used. It is also the
slowest method to allocate memory.
With this change, the madvise algorithm is used to allocate the mark
stack. Virtual memory for the largest possible mark stack is reserved
at startup. At the start of a garbage collection enough pages are
advised as needed for a mark stack given the current size of the heap.
At the end of a garbage collection, these pages are advised as no longer
needed.
As part of this change the mark stack has been changed to grow upward.
This makes the code simpler when the mark stack is incrementally
consumed. Also, the pushing and popping routines have been separated
into distinct functions.
Change-Id: Ibe4cc025c95451c2e462fbf10885ca85eef2088a