You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
413 lines
19 KiB
413 lines
19 KiB
# Native Memory Allocator Verification
|
|
This document describes how to verify the native memory allocator on Android.
|
|
This procedure should be followed when upgrading or moving to a new allocator.
|
|
A small minor upgrade might not need to run all of the benchmarks, however,
|
|
at least the
|
|
[SQL Allocation Trace Benchmark](#sql-allocation-trace-benchmark),
|
|
[Memory Replay Benchmarks](#memory-replay-benchmarks) and
|
|
[Performance Trace Benchmarks](#performance-trace-benchmarks) should be run.
|
|
|
|
It is important to note that there are two modes for a native allocator
|
|
to run in on Android. The first is the normal allocator, the second is
|
|
called the svelte config, which is designed to run on memory constrained
|
|
systems and be a bit slower, but take less RSS. To enable the svelte config,
|
|
add this line to the `BoardConfig.mk` for the given target:
|
|
|
|
MALLOC_SVELTE := true
|
|
|
|
The `BoardConfig.mk` file is usually found in the directory
|
|
`device/<DEVICE_NAME>/` or in a sub directory.
|
|
|
|
When evaluating a native allocator, make sure that you benchmark both
|
|
versions.
|
|
|
|
## Android Extensions
|
|
Android supports a few non-standard functions and mallopt controls that
|
|
a native allocator needs to implement.
|
|
|
|
### Iterator Functions
|
|
These are functions that are used to implement a memory leak detector
|
|
called `libmemunreachable`.
|
|
|
|
#### malloc\_disable
|
|
This function, when called, should pause all threads that are making a
|
|
call to an allocation function (malloc/free/etc). When a call
|
|
is made to `malloc_enable`, the paused threads should start running again.
|
|
|
|
#### malloc\_enable
|
|
This function, when called, does nothing unless there was a previous call
|
|
to `malloc_disable`. This call will unpause any thread which is making
|
|
a call to an allocation function (malloc/free/etc) when `malloc_disable`
|
|
was called previously.
|
|
|
|
#### malloc\_iterate
|
|
This function enumerates all of the allocations currently live in the
|
|
system. It is meant to be called after a call to `malloc_disable` to
|
|
prevent further allocations while this call is being executed. To
|
|
see what is expected for this function, the best description is the
|
|
tests for this funcion in `bionic/tests/malloc_itearte_test.cpp`.
|
|
|
|
### Mallopt Extensions
|
|
These are mallopt options that Android requires for a native allocator
|
|
to work efficiently.
|
|
|
|
#### M\_DECAY\_TIME
|
|
When set to zero, `mallopt(M_DECAY_TIME, 0)`, it is expected that an
|
|
allocator will attempt to purge and release any unused memory back to the
|
|
kernel on free calls. This is important in Android to avoid consuming extra
|
|
RSS.
|
|
|
|
When set to non-zero, `mallopt(M_DECAY_TIME, 1)`, an allocator can delay the
|
|
purge and release action. The amount of delay is up to the allocator
|
|
implementation, but it should be a reasonable amount of time. The jemalloc
|
|
allocator was implemented to have a one second delay.
|
|
|
|
The drawback to this option is that most allocators do not have a separate
|
|
thread to handle the purge, so the decay is only handled when an
|
|
allocation operation occurs. For server processes, this can mean that
|
|
RSS is slightly higher when the server is waiting for the next connection
|
|
and no other allocation calls are made. The `M_PURGE` option is used to
|
|
force a purge in this case.
|
|
|
|
For all applications on Android, the call `mallopt(M_DECAY_TIME, 1)` is
|
|
made by default. The idea is that it allows application frees to run a
|
|
bit faster, while only increasing RSS a bit.
|
|
|
|
#### M\_PURGE
|
|
When called, `mallopt(M_PURGE, 0)`, an allocator should purge and release
|
|
any unused memory immediately. The argument for this call is ignored. If
|
|
possible, this call should clear thread cached memory if it exists. The
|
|
idea is that this can be called to purge memory that has not been
|
|
purged when `M_DECAY_TIME` is set to one. This is useful if you have a
|
|
server application that does a lot of native allocations and the
|
|
application wants to purge that memory before waiting for the next connection.
|
|
|
|
## Correctness Tests
|
|
These are the tests that should be run to verify an allocator is
|
|
working properly according to Android.
|
|
|
|
### Bionic Unit Tests
|
|
The bionic unit tests contain a small number of allocator tests. These
|
|
tests are primarily verifying Android extensions and non-standard behavior
|
|
of allocation routines such as what happens when a non-power of two alignment
|
|
is passed to memalign.
|
|
|
|
To run all of the compliance tests:
|
|
|
|
adb shell /data/nativetest64/bionic-unit-tests/bionic-unit-tests --gtest_filter="malloc*"
|
|
adb shell /data/nativetest/bionic-unit-tests/bionic-unit-tests --gtest_filter="malloc*"
|
|
|
|
The allocation tests are not meant to be complete, so it is expected
|
|
that a native allocator will have its own set of tests that can be run.
|
|
|
|
### Libmemunreachable Tests
|
|
The libmemunreachable tests verify that the iterator functions are working
|
|
properly.
|
|
|
|
To run all of the tests:
|
|
|
|
adb shell /data/nativetest64/memunreachable_binder_test/memunreachable_binder_test
|
|
adb shell /data/nativetest/memunreachable_binder_test/memunreachable_binder_test
|
|
adb shell /data/nativetest64/memunreachable_test/memunreachable_test
|
|
adb shell /data/nativetest/memunreachable_test/memunreachable_test
|
|
adb shell /data/nativetest64/memunreachable_unit_test/memunreachable_unit_test
|
|
adb shell /data/nativetest/memunreachable_unit_test/memunreachable_unit_test
|
|
|
|
### CTS Entropy Test
|
|
In addition to the bionic tests, there is also a CTS test that is designed
|
|
to verify that the addresses returned by malloc are sufficiently randomized
|
|
to help defeat potential security bugs.
|
|
|
|
Run this test thusly:
|
|
|
|
atest AslrMallocTest
|
|
|
|
If there are multiple devices connected to the system, use `-s <SERIAL>`
|
|
to specify a device.
|
|
|
|
## Performance
|
|
There are multiple different ways to evaluate the performance of a native
|
|
allocator on Android. One is allocation speed in various different scenarios,
|
|
another is total RSS taken by the allocator.
|
|
|
|
The last is virtual address space consumed in 32 bit applications. There is
|
|
a limited amount of address space available in 32 bit apps, and there have
|
|
been allocator bugs that cause memory failures when too much virtual
|
|
address space is consumed. For 64 bit executables, this can be ignored.
|
|
|
|
### Bionic Benchmarks
|
|
These are the microbenchmarks that are part of the bionic benchmarks suite of
|
|
benchmarks. These benchmarks can be built using this command:
|
|
|
|
mmma -j bionic/benchmarks
|
|
|
|
These benchmarks are only used to verify the speed of the allocator and
|
|
ignore anything related to RSS and virtual address space consumed.
|
|
|
|
For all of these benchmark runs, it can be useful to add these two options:
|
|
|
|
--benchmark_repetitions=XX
|
|
--benchmark_report_aggregates_only=true
|
|
|
|
This will run the benchmark XX times and then give a mean, median, and stddev
|
|
and helps to get a number that can be compared to the new allocator.
|
|
|
|
In addition, there is another option:
|
|
|
|
--bionic_cpu=XX
|
|
|
|
Which will lock the benchmark to only run on core XX. This also avoids
|
|
any issue related to the code migrating from one core to another
|
|
with different characteristics. For example, on a big-little cpu, if the
|
|
benchmark moves from big to little or vice-versa, this can cause scores
|
|
to fluctuate in indeterminate ways.
|
|
|
|
For most runs, the best set of options to add is:
|
|
|
|
--benchmark_repetitions=10 --benchmark_report_aggregates_only=true --bionic_cpu=3
|
|
|
|
On most phones with a big-little cpu, the third core is the little core.
|
|
Choosing to run on the little core can tend to highlight any performance
|
|
differences.
|
|
|
|
#### Allocate/Free Benchmarks
|
|
These are the benchmarks to verify the allocation speed of a loop doing a
|
|
single allocation, touching every page in the allocation to make it resident
|
|
and then freeing the allocation.
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 0)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_free_default
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=malloc_free_default
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 1)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_free_decay1
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=malloc_free_decay1
|
|
|
|
The last value in the output is the size of the allocation in bytes. It is
|
|
useful to look at these kinds of benchmarks to make sure that there are
|
|
no outliers, but these numbers should not be used to make a final decision.
|
|
If these numbers are slightly worse than the current allocator, the
|
|
single thread numbers from trace data is a better representative of
|
|
real world situations.
|
|
|
|
#### Multiple Allocations Retained Benchmarks
|
|
These are the benchmarks that examine how the allocator handles multiple
|
|
allocations of the same size at the same time.
|
|
|
|
The first set of these benchmarks does a set number of 8192 byte allocations
|
|
in one loop, and then frees all of the allocations at the end of the loop.
|
|
Only the time it takes to do the allocations is recorded, the frees are not
|
|
counted. The value of 8192 was chosen since the jemalloc native allocator
|
|
had issues with this size. It is possible other sizes might show different
|
|
results, but, as mentioned before, these microbenchmark numbers should
|
|
not be used as absolutes for determining if an allocator is worth using.
|
|
|
|
This benchmark is designed to verify that there is no performance issue
|
|
related to having multiple allocations alive at the same time.
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 0)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_multiple_8192_allocs_default
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_multiple_8192_allocs_default
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 1)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_multiple_8192_allocs_decay1
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_multiple_8192_allocs_decay1
|
|
|
|
For these benchmarks, the last parameter is the total number of allocations to
|
|
do in each loop.
|
|
|
|
The other variation of this benchmark is to always do forty allocations in
|
|
each loop, but vary the size of the forty allocations. As with the other
|
|
benchmark, only the time it takes to do the allocations is tracked, the
|
|
frees are not counted. Forty allocations is an arbitrary number that could
|
|
be modified in the future. It was chosen because a version of the native
|
|
allocator, jemalloc, showed a problem at forty allocations.
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 0)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_forty_default
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_forty_default
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 1)`, use these command:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_forty_decay1
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=stdlib_malloc_forty_decay1
|
|
|
|
For these benchmarks, the last parameter in the output is the size of the
|
|
allocation in bytes.
|
|
|
|
As with the other microbenchmarks, an allocator with numbers in the same
|
|
proximity of the current values is usually sufficient to consider making
|
|
a switch. The trace benchmarks are more important than these benchmarks
|
|
since they simulate real world allocation profiles.
|
|
|
|
#### SQL Allocation Trace Benchmark
|
|
This benchmark is a trace of the allocations performed when running
|
|
the SQLite BenchMark app.
|
|
|
|
This benchmark is designed to verify that the allocator will be performant
|
|
in a real world allocation scenario. SQL operations were chosen as a
|
|
benchmark because these operations tend to do lots of malloc/realloc/free
|
|
calls, and they tend to be on the critical path of applications.
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 0)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=malloc_sql_trace_default
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=malloc_sql_trace_default
|
|
|
|
To run the benchmarks with `mallopt(M_DECAY_TIME, 1)`, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=malloc_sql_trace_decay1
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=malloc_sql_trace_decay1
|
|
|
|
These numbers should be as performant as the current allocator.
|
|
|
|
#### mallinfo Benchmark
|
|
This benchmark only verifies that mallinfo is still close to the performance
|
|
of the current allocator.
|
|
|
|
To run the benchmark, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=BM_mallinfo
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=BM_mallinfo
|
|
|
|
Calls to mallinfo are used in ART so a new allocator is required to be
|
|
nearly as performant as the current allocator.
|
|
|
|
#### mallopt M\_PURGE Benchmark
|
|
This benchmark tracks the cost of calling `mallopt(M_PURGE, 0)`. As with the
|
|
mallinfo benchmark, it's not necessary for this to be better than the previous
|
|
allocator, only that the performance be in the same order of magnitude.
|
|
|
|
To run the benchmark, use these commands:
|
|
|
|
adb shell /data/benchmarktest64/bionic-benchmarks/bionic-benchmarks --benchmark_filter=BM_mallopt_purge
|
|
adb shell /data/benchmarktest/bionic-benchmarks/bionic-benchmarks --benchmark_filter=BM_mallopt_purge
|
|
|
|
These calls are used to free unused memory pages back to the kernel.
|
|
|
|
### Memory Trace Benchmarks
|
|
These benchmarks measure all three axes of a native allocator, RSS, virtual
|
|
address space consumed, speed of allocation. They are designed to
|
|
run on a trace of the allocations from a real world application or system
|
|
process.
|
|
|
|
To build this benchmark:
|
|
|
|
mmma -j system/extras/memory_replay
|
|
|
|
This will build two executables:
|
|
|
|
/system/bin/memory_replay32
|
|
/system/bin/memory_replay64
|
|
|
|
And these two benchmark executables:
|
|
|
|
/data/benchmarktest64/trace_benchmark/trace_benchmark
|
|
/data/benchmarktest/trace_benchmark/trace_benchmark
|
|
|
|
#### Memory Replay Benchmarks
|
|
These benchmarks display RSS, virtual memory consumed (VA space), and do a
|
|
bit of performance testing on actual traces taken from running applications.
|
|
|
|
The trace data includes what thread does each operation, so the replay
|
|
mechanism will simulate this by creating threads and replaying the operations
|
|
on a thread as if it was rerunning the real trace. The only issue is that
|
|
this is a worst case scenario for allocations happening at the same time
|
|
in all threads since it collapses all of the allocation operations to occur
|
|
one after another. This will cause a lot of threads allocating at the same
|
|
time. The trace data does not include timestamps,
|
|
so it is not possible to create a completely accurate replay.
|
|
|
|
To generate these traces, see the [Malloc Debug documentation](https://android.googlesource.com/platform/bionic/+/master/libc/malloc_debug/README.md),
|
|
the option [record\_allocs](https://android.googlesource.com/platform/bionic/+/master/libc/malloc_debug/README.md#record_allocs_total_entries).
|
|
|
|
To run these benchmarks, first copy the trace files to the target using
|
|
these commands:
|
|
|
|
adb push system/extras/memory_replay/traces /data/local/tmp
|
|
|
|
Since all of the traces come from applications, the `memory_replay` program
|
|
will always call `mallopt(M_DECAY_TIME, 1)' before running the trace.
|
|
|
|
Run the benchmark thusly:
|
|
|
|
adb shell memory_replay64 /data/local/tmp/traces/XXX.zip
|
|
adb shell memory_replay32 /data/local/tmp/traces/XXX.zip
|
|
|
|
Where XXX.zip is the name of a zipped trace file. The `memory_replay`
|
|
program also can process text files, but all trace files are currently
|
|
checked in as zip files.
|
|
|
|
Every 100000 allocation operations, a dump of the RSS and VA space will be
|
|
performed. At the end, a final RSS and VA space number will be printed.
|
|
For the most part, the intermediate data can be ignored, but it is always
|
|
a good idea to look over the data to verify that no strange spikes are
|
|
occurring.
|
|
|
|
The performance number is a measure of the time it takes to perform all of
|
|
the allocation calls (malloc/memalign/posix_memalign/realloc/free/etc).
|
|
For any call that allocates a pointer, the time for the call and the time
|
|
it takes to make the pointer completely resident in memory is included.
|
|
|
|
The performance numbers for these runs tend to have a wide variability so
|
|
they should not be used as absolute value for comparison against the
|
|
current allocator. But, they should be in the same range as the current
|
|
values.
|
|
|
|
When evaluating an allocator, one of the most important traces is the
|
|
camera.txt trace. The camera application does very large allocations,
|
|
and some allocators might leave large virtual address maps around
|
|
rather than delete them. When that happens, it can lead to allocation
|
|
failures and would cause the camera app to abort/crash. It is
|
|
important to verify that when running this trace using the 32 bit replay
|
|
executable, the virtual address space consumed is not much larger than the
|
|
current allocator. A small increase (on the order of a few MBs) would be okay.
|
|
|
|
There is no specific benchmark for memory fragmentation, instead, the RSS
|
|
when running the memory traces acts as a proxy for this. An allocator that
|
|
is fragmenting badly will show an increase in RSS. The best trace for
|
|
tracking fragmentation is system\_server.txt which is an extremely long
|
|
trace (~13 million operations). The total number of live allocations goes
|
|
up and down a bit, but stays mostly the same so an allocator that fragments
|
|
badly would likely show an abnormal increase in RSS on this trace.
|
|
|
|
NOTE: When a native allocator calls mmap, it is expected that the allocator
|
|
will name the map using the call:
|
|
|
|
prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, <PTR>, <SIZE>, "libc_malloc");
|
|
|
|
If the native allocator creates a different name, then it necessary to
|
|
modify the file:
|
|
|
|
system/extras/memory_replay/NativeInfo.cpp
|
|
|
|
The `GetNativeInfo` function needs to be modified to include the name
|
|
of the maps that this allocator includes.
|
|
|
|
In addition, in order for the frameworks code to keep track of the memory
|
|
of a process, any named maps must be added to the file:
|
|
|
|
frameworks/base/core/jni/android_os_Debug.cpp
|
|
|
|
Modify the `load_maps` function and add a check of the new expected name.
|
|
|
|
#### Performance Trace Benchmarks
|
|
This is a benchmark that treats the trace data as if all allocations
|
|
occurred in a single thread. This is the scenario that could
|
|
happen if all of the allocations are spaced out in time so no thread
|
|
every does an allocation at the same time as another thread.
|
|
|
|
Run these benchmarks thusly:
|
|
|
|
adb shell /data/benchmarktest64/trace_benchmark/trace_benchmark
|
|
adb shell /data/benchmarktest/trace_benchmark/trace_benchmark
|
|
|
|
When run without any arguments, the benchmark will run over all of the
|
|
traces and display data. It takes many minutes to complete these runs in
|
|
order to get as accurate a number as possible.
|