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
31const uint32_t kSmallObjectMaxSizeLog2 = 10;
32const uint32_t kSmallObjectMinSizeLog2 = 4;
33const uint32_t kSmallObjectAllocatorsCount = kSmallObjectMaxSizeLog2 - kSmallObjectMinSizeLog2 + 1;
34
35class 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.
39struct 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
50struct 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...
57bool operator<(const small_object_page_record& one, const small_object_page_record& two);
58
59struct 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
65template <typename T>
66class 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
91  void deallocate(T* ptr, size_t n) {
92    munmap(ptr, n * sizeof(T));
93  }
94};
95
96typedef
97    std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
98    linker_vector_t;
99
100
101class LinkerSmallObjectAllocator {
102 public:
103  LinkerSmallObjectAllocator();
104  void init(uint32_t type, size_t block_size);
105  void* alloc();
106  void free(void* ptr);
107
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
125class 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