| /* |
| * Copyright © 2021 The Fuchsia Authors |
| * |
| * Permission is hereby granted, free of charge, to any person obtaining a |
| * copy of this software and associated documentation files (the "Software"), |
| * to deal in the Software without restriction, including without limitation |
| * the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| * and/or sell copies of the Software, and to permit persons to whom the |
| * Software is furnished to do so, subject to the following conditions: |
| * |
| * The above copyright notice and this permission notice (including the next |
| * paragraph) shall be included in all copies or substantial portions of the |
| * Software. |
| * |
| * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
| * IN THE SOFTWARE. |
| * |
| */ |
| |
| #include "simple_allocator.h" |
| |
| #include <stdint.h> |
| #include <stdio.h> |
| #include <memory> |
| |
| #define LOG_VERBOSE(msg, ...) do { \ |
| if (true) \ |
| fprintf(stderr, "%s:%d " msg "\n", __FILE__, __LINE__, ##__VA_ARGS__); \ |
| fflush(stderr); \ |
| } while (0) |
| |
| bool SimpleAllocator::CheckGap(SimpleAllocator::Region* prev, SimpleAllocator::Region* next, |
| uint64_t align, size_t size, uint64_t* addr_out, |
| bool* continue_search_out) { |
| assert(addr_out); |
| assert(continue_search_out); |
| |
| uint64_t gap_begin = prev ? (prev->base + prev->size) : base(); |
| uint64_t gap_end; // last byte of a gap |
| |
| if (next) { |
| if (gap_begin == next->base) { |
| *continue_search_out = true; |
| return false; |
| } |
| gap_end = next->base - 1; |
| } else { |
| if (gap_begin == base() + this->size()) { |
| *continue_search_out = false; |
| return false; |
| } |
| gap_end = base() + this->size() - 1; |
| } |
| |
| *addr_out = RoundUp(gap_begin, align); |
| |
| if (*addr_out < gap_begin) { |
| *continue_search_out = false; |
| return false; |
| } |
| |
| if (*addr_out < gap_end && ((gap_end - *addr_out + 1) >= size)) |
| return true; |
| |
| *continue_search_out = true; |
| return false; |
| } |
| |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| SimpleAllocator::Region::Region(uint64_t base_in, size_t size_in) : base(base_in), size(size_in) { |
| assert(size > 0); |
| assert(base + size - 1 >= base); |
| } |
| |
| std::unique_ptr<SimpleAllocator> SimpleAllocator::Create(uint64_t base, size_t size) { |
| return std::unique_ptr<SimpleAllocator>(new SimpleAllocator(base, size)); |
| } |
| |
| SimpleAllocator::SimpleAllocator(uint64_t base, size_t size) : AddressSpaceAllocator(base, size) {} |
| |
| bool SimpleAllocator::Alloc(size_t size, uint8_t align_pow2, uint64_t* addr_out) { |
| assert(addr_out); |
| |
| size = RoundUp(size, size_t{GetPageSize()}); |
| if (size == 0) { |
| LOG_VERBOSE("Can't allocate size zero"); |
| return false; |
| } |
| |
| assert(IsPageAligned(size)); |
| |
| uint32_t local_align_pow = align_pow2; |
| const uint32_t page_shift = PageShift(); |
| if (align_pow2 < page_shift) { |
| local_align_pow = page_shift; |
| } |
| |
| uint64_t align = 1UL << local_align_pow; |
| uint64_t addr; |
| bool continue_search; |
| |
| // try to pick spot at the beginning of address space |
| if (CheckGap(nullptr, regions_.empty() ? nullptr : ®ions_.front(), align, size, &addr, |
| &continue_search)) { |
| *addr_out = addr; |
| regions_.emplace_front(addr, size); |
| return true; |
| } |
| |
| // search the middle of the list |
| for (auto iter = regions_.begin(); continue_search && iter != regions_.end();) { |
| auto prev = &(*iter); |
| auto next = (++iter == regions_.end()) ? nullptr : &(*iter); |
| if (CheckGap(prev, next, align, size, &addr, &continue_search)) { |
| *addr_out = addr; |
| regions_.insert(iter, Region(addr, size)); |
| return true; |
| } |
| } |
| |
| LOG_VERBOSE("Failed to allocate"); |
| return false; |
| } |
| |
| bool SimpleAllocator::Free(uint64_t addr) { |
| auto iter = FindRegion(addr); |
| if (iter == regions_.end()) { |
| LOG_VERBOSE("Couldn't find region to free"); |
| return false; |
| } |
| |
| regions_.erase(iter); |
| |
| return true; |
| } |
| |
| bool SimpleAllocator::GetSize(uint64_t addr, size_t* size_out) { |
| auto iter = FindRegion(addr); |
| if (iter == regions_.end()) { |
| LOG_VERBOSE("Couldn't find region"); |
| return false; |
| } |
| |
| *size_out = iter->size; |
| return true; |
| } |
| |
| std::list<SimpleAllocator::Region>::iterator SimpleAllocator::FindRegion(uint64_t addr) { |
| for (auto iter = regions_.begin(); iter != regions_.end(); iter++) { |
| auto region = *iter; |
| if ((addr >= region.base) && (addr <= region.base + region.size - 1)) |
| return iter; |
| } |
| |
| return regions_.end(); |
| } |