1 /*
2 * Copyright (C) 2014 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 #include "linker_block_allocator.h"
30
31 #include <inttypes.h>
32 #include <string.h>
33 #include <sys/mman.h>
34 #include <sys/param.h>
35 #include <sys/prctl.h>
36 #include <unistd.h>
37
38 #include "linker_debug.h"
39
40 static constexpr size_t kMaxPageSize = 65536;
41 static constexpr size_t kAllocateSize = kMaxPageSize * 6;
42 static_assert(kAllocateSize % kMaxPageSize == 0, "Invalid kAllocateSize.");
43
44 struct LinkerBlockAllocatorPage {
45 LinkerBlockAllocatorPage* next;
46 uint8_t bytes[kAllocateSize - 16] __attribute__((aligned(16)));
47 };
48
49 struct FreeBlockInfo {
50 void* next_block;
51 size_t num_free_blocks;
52 };
53
54 static_assert(kBlockSizeAlign >= alignof(FreeBlockInfo));
55 static_assert(kBlockSizeMin == sizeof(FreeBlockInfo));
56
LinkerBlockAllocator(size_t block_size)57 LinkerBlockAllocator::LinkerBlockAllocator(size_t block_size)
58 : block_size_(__BIONIC_ALIGN(MAX(block_size, kBlockSizeMin), kBlockSizeAlign)),
59 page_list_(nullptr),
60 free_block_list_(nullptr),
61 allocated_(0) {}
62
alloc()63 void* LinkerBlockAllocator::alloc() {
64 if (free_block_list_ == nullptr) {
65 create_new_page();
66 }
67
68 FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(free_block_list_);
69 if (block_info->num_free_blocks > 1) {
70 FreeBlockInfo* next_block_info = reinterpret_cast<FreeBlockInfo*>(
71 reinterpret_cast<char*>(free_block_list_) + block_size_);
72 next_block_info->next_block = block_info->next_block;
73 next_block_info->num_free_blocks = block_info->num_free_blocks - 1;
74 free_block_list_ = next_block_info;
75 } else {
76 free_block_list_ = block_info->next_block;
77 }
78
79 memset(block_info, 0, block_size_);
80
81 ++allocated_;
82
83 return block_info;
84 }
85
free(void * block)86 void LinkerBlockAllocator::free(void* block) {
87 if (block == nullptr) {
88 return;
89 }
90
91 LinkerBlockAllocatorPage* page = find_page(block);
92 CHECK(page != nullptr);
93
94 ssize_t offset = reinterpret_cast<uint8_t*>(block) - page->bytes;
95 CHECK((offset % block_size_) == 0);
96
97 memset(block, 0, block_size_);
98
99 FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(block);
100
101 block_info->next_block = free_block_list_;
102 block_info->num_free_blocks = 1;
103
104 free_block_list_ = block_info;
105
106 --allocated_;
107 }
108
protect_all(int prot)109 void LinkerBlockAllocator::protect_all(int prot) {
110 for (LinkerBlockAllocatorPage* page = page_list_; page != nullptr; page = page->next) {
111 if (mprotect(page, kAllocateSize, prot) == -1) {
112 async_safe_fatal("mprotect(%p, %zu, %d) failed: %m", page, kAllocateSize, prot);
113 }
114 }
115 }
116
create_new_page()117 void LinkerBlockAllocator::create_new_page() {
118 static_assert(sizeof(LinkerBlockAllocatorPage) == kAllocateSize,
119 "Invalid sizeof(LinkerBlockAllocatorPage)");
120
121 LinkerBlockAllocatorPage* page = reinterpret_cast<LinkerBlockAllocatorPage*>(
122 mmap(nullptr, kAllocateSize, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0));
123 CHECK(page != MAP_FAILED);
124
125 prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, page, kAllocateSize, "linker_alloc");
126
127 FreeBlockInfo* first_block = reinterpret_cast<FreeBlockInfo*>(page->bytes);
128 first_block->next_block = free_block_list_;
129 first_block->num_free_blocks = sizeof(page->bytes) / block_size_;
130
131 free_block_list_ = first_block;
132
133 page->next = page_list_;
134 page_list_ = page;
135 }
136
find_page(void * block)137 LinkerBlockAllocatorPage* LinkerBlockAllocator::find_page(void* block) {
138 CHECK(block != nullptr);
139
140 LinkerBlockAllocatorPage* page = page_list_;
141 while (page != nullptr) {
142 const uint8_t* page_ptr = reinterpret_cast<const uint8_t*>(page);
143 if (block >= (page_ptr + sizeof(page->next)) && block < (page_ptr + kAllocateSize)) {
144 return page;
145 }
146
147 page = page->next;
148 }
149
150 async_safe_fatal("couldn't find page for %p", block);
151 }
152
purge()153 void LinkerBlockAllocator::purge() {
154 if (allocated_) {
155 return;
156 }
157
158 LinkerBlockAllocatorPage* page = page_list_;
159 while (page) {
160 LinkerBlockAllocatorPage* next = page->next;
161 munmap(page, kAllocateSize);
162 page = next;
163 }
164 page_list_ = nullptr;
165 free_block_list_ = nullptr;
166 }
167