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

1 files changed, 21 insertions, 51 deletions

diff --git a/linker/linker_allocator.h b/linker/linker_allocator.h
index 8c4198b65..46198177e 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,56 +57,30 @@ struct page_info {
   };
 } __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;
-
-  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));
-    }
-
-    prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector");
-
-    return reinterpret_cast<T*>(ptr);
-  }
-
-  void deallocate(T* ptr, size_t n) {
-    munmap(ptr, n * sizeof(T));
-  }
-};
+// 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.
+
+  // Doubly linked list for traversing all pages allocated by a
+  // LinkerSmallObjectAllocator.
+  small_object_page_info* next_page;
+  small_object_page_info* prev_page;
 
-typedef
-    std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
-    linker_vector_t;
+  // Linked list containing all free blocks in this page.
+  small_object_block_record* free_block_list;
 
+  // Free/allocated blocks counter.
+  size_t free_blocks_cnt;
+  size_t allocated_blocks_cnt;
+};
 
 class LinkerSmallObjectAllocator {
  public:
@@ -119,18 +91,16 @@ class LinkerSmallObjectAllocator {
   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 {