1 /*
2  * Copyright (C) 2015 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #ifndef __LINKER_ALLOCATOR_H
18 #define __LINKER_ALLOCATOR_H
19 
20 #include <stdlib.h>
21 #include <sys/cdefs.h>
22 #include <sys/mman.h>
23 #include <stddef.h>
24 #include <unistd.h>
25 
26 #include <vector>
27 
28 #include "private/bionic_prctl.h"
29 #include "private/libc_logging.h"
30 
31 const uint32_t kSmallObjectMaxSizeLog2 = 10;
32 const uint32_t kSmallObjectMinSizeLog2 = 4;
33 const uint32_t kSmallObjectAllocatorsCount = kSmallObjectMaxSizeLog2 - kSmallObjectMinSizeLog2 + 1;
34 
35 class LinkerSmallObjectAllocator;
36 
37 // This structure is placed at the beginning of each addressable page
38 // and has all information we need to find the corresponding memory allocator.
39 struct page_info {
40   char signature[4];
41   uint32_t type;
42   union {
43     // we use allocated_size for large objects allocator
44     size_t allocated_size;
45     // and allocator_addr for small ones.
46     LinkerSmallObjectAllocator* allocator_addr;
47   };
48 } __attribute__((aligned(16)));
49 
50 struct small_object_page_record {
51   void* page_addr;
52   size_t free_blocks_cnt;
53   size_t allocated_blocks_cnt;
54 };
55 
56 // for lower_bound...
57 bool operator<(const small_object_page_record& one, const small_object_page_record& two);
58 
59 struct small_object_block_record {
60   small_object_block_record* next;
61   size_t free_blocks_cnt;
62 };
63 
64 // This is implementation for std::vector allocator
65 template <typename T>
66 class linker_vector_allocator {
67  public:
68   typedef T value_type;
69   typedef T* pointer;
70   typedef const T* const_pointer;
71   typedef T& reference;
72   typedef const T& const_reference;
73   typedef size_t size_type;
74   typedef ptrdiff_t difference_type;
75 
76   T* allocate(size_t n, const T* hint = nullptr) {
77     size_t size = n * sizeof(T);
78     void* ptr = mmap(const_cast<T*>(hint), size,
79         PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
80     if (ptr == MAP_FAILED) {
81       // Spec says we need to throw std::bad_alloc here but because our
82       // code does not support exception handling anyways - we are going to abort.
83       __libc_fatal("mmap failed");
84     }
85 
86     prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector");
87 
88     return reinterpret_cast<T*>(ptr);
89   }
90 
deallocate(T * ptr,size_t n)91   void deallocate(T* ptr, size_t n) {
92     munmap(ptr, n * sizeof(T));
93   }
94 };
95 
96 typedef
97     std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
98     linker_vector_t;
99 
100 
101 class LinkerSmallObjectAllocator {
102  public:
103   LinkerSmallObjectAllocator();
104   void init(uint32_t type, size_t block_size);
105   void* alloc();
106   void free(void* ptr);
107 
get_block_size()108   size_t get_block_size() const { return block_size_; }
109  private:
110   void alloc_page();
111   void free_page(linker_vector_t::iterator page_record);
112   linker_vector_t::iterator find_page_record(void* ptr);
113   void create_page_record(void* page_addr, size_t free_blocks_cnt);
114 
115   uint32_t type_;
116   size_t block_size_;
117 
118   size_t free_pages_cnt_;
119   small_object_block_record* free_blocks_list_;
120 
121   // sorted vector of page records
122   linker_vector_t page_records_;
123 };
124 
125 class LinkerMemoryAllocator {
126  public:
127   LinkerMemoryAllocator();
128   void* alloc(size_t size);
129 
130   // Note that this implementation of realloc never shrinks allocation
131   void* realloc(void* ptr, size_t size);
132   void free(void* ptr);
133  private:
134   void* alloc_mmap(size_t size);
135   page_info* get_page_info(void* ptr);
136   LinkerSmallObjectAllocator* get_small_object_allocator(uint32_t type);
137 
138   LinkerSmallObjectAllocator allocators_[kSmallObjectAllocatorsCount];
139 };
140 
141 
142 #endif  /* __LINKER_ALLOCATOR_H */
143