1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *  * Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 *  * Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in
12 *    the documentation and/or other materials provided with the
13 *    distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
16 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
17 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
18 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
19 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
20 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
21 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
22 * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
23 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
25 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
26 * SUCH DAMAGE.
27 */
28
29#pragma once
30
31#include <errno.h>
32#include <stdlib.h>
33#include <sys/cdefs.h>
34#include <sys/mman.h>
35#include <stddef.h>
36#include <unistd.h>
37
38#include <vector>
39
40#include <async_safe/log.h>
41
42#include "private/bionic_prctl.h"
43
44const uint32_t kSmallObjectMaxSizeLog2 = 10;
45const uint32_t kSmallObjectMinSizeLog2 = 4;
46const uint32_t kSmallObjectAllocatorsCount = kSmallObjectMaxSizeLog2 - kSmallObjectMinSizeLog2 + 1;
47
48class LinkerSmallObjectAllocator;
49
50// This structure is placed at the beginning of each addressable page
51// and has all information we need to find the corresponding memory allocator.
52struct page_info {
53  char signature[4];
54  uint32_t type;
55  union {
56    // we use allocated_size for large objects allocator
57    size_t allocated_size;
58    // and allocator_addr for small ones.
59    LinkerSmallObjectAllocator* allocator_addr;
60  };
61} __attribute__((aligned(16)));
62
63struct small_object_page_record {
64  void* page_addr;
65  size_t free_blocks_cnt;
66  size_t allocated_blocks_cnt;
67};
68
69// for lower_bound...
70bool operator<(const small_object_page_record& one, const small_object_page_record& two);
71
72struct small_object_block_record {
73  small_object_block_record* next;
74  size_t free_blocks_cnt;
75};
76
77// This is implementation for std::vector allocator
78template <typename T>
79class linker_vector_allocator {
80 public:
81  typedef T value_type;
82  typedef T* pointer;
83  typedef const T* const_pointer;
84  typedef T& reference;
85  typedef const T& const_reference;
86  typedef size_t size_type;
87  typedef ptrdiff_t difference_type;
88
89  T* allocate(size_t n, const T* hint = nullptr) {
90    size_t size = n * sizeof(T);
91    void* ptr = mmap(const_cast<T*>(hint), size, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS,
92                     -1, 0);
93    if (ptr == MAP_FAILED) {
94      // Spec says we need to throw std::bad_alloc here but because our
95      // code does not support exception handling anyways - we are going to abort.
96      async_safe_fatal("mmap failed: %s", strerror(errno));
97    }
98
99    prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, ptr, size, "linker_alloc_vector");
100
101    return reinterpret_cast<T*>(ptr);
102  }
103
104  void deallocate(T* ptr, size_t n) {
105    munmap(ptr, n * sizeof(T));
106  }
107};
108
109typedef
110    std::vector<small_object_page_record, linker_vector_allocator<small_object_page_record>>
111    linker_vector_t;
112
113
114class LinkerSmallObjectAllocator {
115 public:
116  LinkerSmallObjectAllocator(uint32_t type, size_t block_size);
117  void* alloc();
118  void free(void* ptr);
119
120  size_t get_block_size() const { return block_size_; }
121 private:
122  void alloc_page();
123  void free_page(linker_vector_t::iterator page_record);
124  linker_vector_t::iterator find_page_record(void* ptr);
125  void create_page_record(void* page_addr, size_t free_blocks_cnt);
126
127  uint32_t type_;
128  size_t block_size_;
129
130  size_t free_pages_cnt_;
131  small_object_block_record* free_blocks_list_;
132
133  // sorted vector of page records
134  linker_vector_t page_records_;
135};
136
137class LinkerMemoryAllocator {
138 public:
139  constexpr LinkerMemoryAllocator() : allocators_(nullptr), allocators_buf_() {}
140  void* alloc(size_t size);
141
142  // Note that this implementation of realloc never shrinks allocation
143  void* realloc(void* ptr, size_t size);
144  void free(void* ptr);
145 private:
146  void* alloc_mmap(size_t size);
147  page_info* get_page_info(void* ptr);
148  LinkerSmallObjectAllocator* get_small_object_allocator(uint32_t type);
149  void initialize_allocators();
150
151  LinkerSmallObjectAllocator* allocators_;
152  uint8_t allocators_buf_[sizeof(LinkerSmallObjectAllocator)*kSmallObjectAllocatorsCount];
153};
154