Reduce LinkerSmallObjectAllocator memory overhead
The current implementation of LinkerSmallObjectAllocator keeps record
of pages in a vector, which uses its own page(s). This is at least a
page overhead per LinkerSmallObjectAllocator.
This change removes the page record vector by managing the pages in a
doubly linked list.
We also fix a bug where we are actually keeping up to 2 free pages
instead of just one.
The memory used by small objects when running 'dd', before this change:
72 KB [anon:linker_alloc_small_objects]
28 KB [anon:linker_alloc_vector]
After this change:
60 KB [anon:linker_alloc_small_objects]
Test: Boot cuttlefish and check memory used by linker.
Change-Id: I3468fa4d853c78b4bc02bfb84a3531653f74fb17
diff --git a/linker/linker_allocator.h b/linker/linker_allocator.h
index 8c4198b..4619817 100644
--- a/linker/linker_allocator.h
+++ b/linker/linker_allocator.h
@@ -36,8 +36,6 @@
#include <stddef.h>
#include <unistd.h>
-#include <vector>
-
#include <async_safe/log.h>
const uint32_t kSmallObjectMaxSizeLog2 = 10;
@@ -59,57 +57,31 @@
};
} __attribute__((aligned(16)));
-struct small_object_page_record {
- void* page_addr;
- size_t free_blocks_cnt;
- size_t allocated_blocks_cnt;
-};
-
-// for lower_bound...
-bool operator<(const small_object_page_record& one, const small_object_page_record& two);
-
struct small_object_block_record {
small_object_block_record* next;
size_t free_blocks_cnt;
};
-// This is implementation for std::vector allocator
-template <typename T>
-class linker_vector_allocator {
- public:
- typedef T value_type;
- typedef T* pointer;
- typedef const T* const_pointer;
- typedef T& reference;
- typedef const T& const_reference;
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
+// This structure is placed at the beginning of each page managed by
+// LinkerSmallObjectAllocator. Note that a page_info struct is expected at the
+// beginning of each page as well, and therefore this structure contains a
+// page_info as its *first* field.
+struct small_object_page_info {
+ page_info info; // Must be the first field.
- T* allocate(size_t n, const T* hint = nullptr) {
- size_t size = n * sizeof(T);
- void* ptr = mmap(const_cast<T*>(hint), size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS,
- -1, 0);
- if (ptr == MAP_FAILED) {
- // Spec says we need to throw std::bad_alloc here but because our
- // code does not support exception handling anyways - we are going to abort.
- async_safe_fatal("mmap failed: %s", strerror(errno));
- }
+ // Doubly linked list for traversing all pages allocated by a
+ // LinkerSmallObjectAllocator.
+ small_object_page_info* next_page;
+ small_object_page_info* prev_page;
- prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector");
+ // Linked list containing all free blocks in this page.
+ small_object_block_record* free_block_list;
- return reinterpret_cast<T*>(ptr);
- }
-
- void deallocate(T* ptr, size_t n) {
- munmap(ptr, n * sizeof(T));
- }
+ // Free/allocated blocks counter.
+ size_t free_blocks_cnt;
+ size_t allocated_blocks_cnt;
};
-typedef
- std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
- linker_vector_t;
-
-
class LinkerSmallObjectAllocator {
public:
LinkerSmallObjectAllocator(uint32_t type, size_t block_size);
@@ -119,18 +91,16 @@
size_t get_block_size() const { return block_size_; }
private:
void alloc_page();
- void free_page(linker_vector_t::iterator page_record);
- linker_vector_t::iterator find_page_record(void* ptr);
- void create_page_record(void* page_addr, size_t free_blocks_cnt);
+ void free_page(small_object_page_info* page);
+ void add_to_page_list(small_object_page_info* page);
+ void remove_from_page_list(small_object_page_info* page);
uint32_t type_;
size_t block_size_;
size_t free_pages_cnt_;
- small_object_block_record* free_blocks_list_;
- // sorted vector of page records
- linker_vector_t page_records_;
+ small_object_page_info* page_list_;
};
class LinkerMemoryAllocator {