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#include <inttypes.h>
31#include <string.h>
32#include <sys/mman.h>
33#include <unistd.h>
34
35#include "private/bionic_prctl.h"
36
37// the multiplier should be power of 2
38static constexpr size_t round_up(size_t size, size_t multiplier) {
39  return (size + (multiplier - 1)) & ~(multiplier-1);
40}
41
42struct LinkerBlockAllocatorPage {
43  LinkerBlockAllocatorPage* next;
44  uint8_t bytes[PAGE_SIZE - 16] __attribute__((aligned(16)));
45};
46
47struct FreeBlockInfo {
48  void* next_block;
49  size_t num_free_blocks;
50};
51
52LinkerBlockAllocator::LinkerBlockAllocator(size_t block_size)
53  : block_size_(
54      round_up(block_size < sizeof(FreeBlockInfo) ? sizeof(FreeBlockInfo) : block_size, 16)),
55    page_list_(nullptr),
56    free_block_list_(nullptr)
57{}
58
59void* LinkerBlockAllocator::alloc() {
60  if (free_block_list_ == nullptr) {
61    create_new_page();
62  }
63
64  FreeBlockInfo* block_info = reinterpret_cast<FreeBlockInfo*>(free_block_list_);
65  if (block_info->num_free_blocks > 1) {
66    FreeBlockInfo* next_block_info = reinterpret_cast<FreeBlockInfo*>(
67      reinterpret_cast<char*>(free_block_list_) + block_size_);
68    next_block_info->next_block = block_info->next_block;
69    next_block_info->num_free_blocks = block_info->num_free_blocks - 1;
70    free_block_list_ = next_block_info;
71  } else {
72    free_block_list_ = block_info->next_block;
73  }
74
75  memset(block_info, 0, block_size_);
76
77  return block_info;
78}
79
80void LinkerBlockAllocator::free(void* block) {
81  if (block == nullptr) {
82    return;
83  }
84
85  LinkerBlockAllocatorPage* page = find_page(block);
86
87  if (page == nullptr) {
88    abort();
89  }
90
91  ssize_t offset = reinterpret_cast<uint8_t*>(block) - page->bytes;
92
93  if (offset % block_size_ != 0) {
94    abort();
95  }
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
107void LinkerBlockAllocator::protect_all(int prot) {
108  for (LinkerBlockAllocatorPage* page = page_list_; page != nullptr; page = page->next) {
109    if (mprotect(page, PAGE_SIZE, prot) == -1) {
110      abort();
111    }
112  }
113}
114
115void LinkerBlockAllocator::create_new_page() {
116  static_assert(sizeof(LinkerBlockAllocatorPage) == PAGE_SIZE,
117                "Invalid sizeof(LinkerBlockAllocatorPage)");
118
119  LinkerBlockAllocatorPage* page = reinterpret_cast<LinkerBlockAllocatorPage*>(
120      mmap(nullptr, PAGE_SIZE, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0));
121
122  if (page == MAP_FAILED) {
123    abort(); // oom
124  }
125
126  prctl(PR_SET_VMA, PR_SET_VMA_ANON_NAME, page, PAGE_SIZE, "linker_alloc");
127
128  FreeBlockInfo* first_block = reinterpret_cast<FreeBlockInfo*>(page->bytes);
129  first_block->next_block = free_block_list_;
130  first_block->num_free_blocks = (PAGE_SIZE - sizeof(LinkerBlockAllocatorPage*))/block_size_;
131
132  free_block_list_ = first_block;
133
134  page->next = page_list_;
135  page_list_ = page;
136}
137
138LinkerBlockAllocatorPage* LinkerBlockAllocator::find_page(void* block) {
139  if (block == nullptr) {
140    abort();
141  }
142
143  LinkerBlockAllocatorPage* page = page_list_;
144  while (page != nullptr) {
145    const uint8_t* page_ptr = reinterpret_cast<const uint8_t*>(page);
146    if (block >= (page_ptr + sizeof(page->next)) && block < (page_ptr + PAGE_SIZE)) {
147      return page;
148    }
149
150    page = page->next;
151  }
152
153  abort();
154}
155