Home | History | Annotate | Download | only in utils
      1 /*
      2  * Copyright (C) 2014 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 #include "swap_space.h"
     18 
     19 #include <algorithm>
     20 #include <numeric>
     21 
     22 #include "base/logging.h"
     23 #include "base/macros.h"
     24 #include "base/mutex.h"
     25 #include "thread-inl.h"
     26 
     27 namespace art {
     28 
     29 // The chunk size by which the swap file is increased and mapped.
     30 static constexpr size_t kMininumMapSize = 16 * MB;
     31 
     32 static constexpr bool kCheckFreeMaps = false;
     33 
     34 template <typename FreeBySizeSet>
     35 static void DumpFreeMap(const FreeBySizeSet& free_by_size) {
     36   size_t last_size = static_cast<size_t>(-1);
     37   for (const auto& entry : free_by_size) {
     38     if (last_size != entry.first) {
     39       last_size = entry.first;
     40       LOG(INFO) << "Size " << last_size;
     41     }
     42     LOG(INFO) << "  0x" << std::hex << entry.second->Start()
     43         << " size=" << std::dec << entry.second->size;
     44   }
     45 }
     46 
     47 template <typename FreeByStartSet, typename FreeBySizeSet>
     48 static void RemoveChunk(FreeByStartSet* free_by_start,
     49                         FreeBySizeSet* free_by_size,
     50                         typename FreeBySizeSet::const_iterator free_by_size_pos) {
     51   auto free_by_start_pos = free_by_size_pos->second;
     52   free_by_size->erase(free_by_size_pos);
     53   free_by_start->erase(free_by_start_pos);
     54 }
     55 
     56 template <typename FreeByStartSet, typename FreeBySizeSet>
     57 static void InsertChunk(FreeByStartSet* free_by_start,
     58                         FreeBySizeSet* free_by_size,
     59                         const SpaceChunk& chunk) {
     60   DCHECK_NE(chunk.size, 0u);
     61   auto insert_result = free_by_start->insert(chunk);
     62   DCHECK(insert_result.second);
     63   free_by_size->emplace(chunk.size, insert_result.first);
     64 }
     65 
     66 SwapSpace::SwapSpace(int fd, size_t initial_size)
     67     : fd_(fd),
     68       size_(0),
     69       lock_("SwapSpace lock", static_cast<LockLevel>(LockLevel::kDefaultMutexLevel - 1)) {
     70   // Assume that the file is unlinked.
     71 
     72   InsertChunk(&free_by_start_, &free_by_size_, NewFileChunk(initial_size));
     73 }
     74 
     75 SwapSpace::~SwapSpace() {
     76   // All arenas are backed by the same file. Just close the descriptor.
     77   close(fd_);
     78 }
     79 
     80 template <typename FreeByStartSet, typename FreeBySizeSet>
     81 static size_t CollectFree(const FreeByStartSet& free_by_start, const FreeBySizeSet& free_by_size) {
     82   if (free_by_start.size() != free_by_size.size()) {
     83     LOG(FATAL) << "Size: " << free_by_start.size() << " vs " << free_by_size.size();
     84   }
     85 
     86   // Calculate over free_by_size.
     87   size_t sum1 = 0;
     88   for (const auto& entry : free_by_size) {
     89     sum1 += entry.second->size;
     90   }
     91 
     92   // Calculate over free_by_start.
     93   size_t sum2 = 0;
     94   for (const auto& entry : free_by_start) {
     95     sum2 += entry.size;
     96   }
     97 
     98   if (sum1 != sum2) {
     99     LOG(FATAL) << "Sum: " << sum1 << " vs " << sum2;
    100   }
    101   return sum1;
    102 }
    103 
    104 void* SwapSpace::Alloc(size_t size) {
    105   MutexLock lock(Thread::Current(), lock_);
    106   size = RoundUp(size, 8U);
    107 
    108   // Check the free list for something that fits.
    109   // TODO: Smarter implementation. Global biggest chunk, ...
    110   SpaceChunk old_chunk;
    111   auto it = free_by_start_.empty()
    112       ? free_by_size_.end()
    113       : free_by_size_.lower_bound(FreeBySizeEntry { size, free_by_start_.begin() });
    114   if (it != free_by_size_.end()) {
    115     old_chunk = *it->second;
    116     RemoveChunk(&free_by_start_, &free_by_size_, it);
    117   } else {
    118     // Not a big enough free chunk, need to increase file size.
    119     old_chunk = NewFileChunk(size);
    120   }
    121 
    122   void* ret = old_chunk.ptr;
    123 
    124   if (old_chunk.size != size) {
    125     // Insert the remainder.
    126     SpaceChunk new_chunk = { old_chunk.ptr + size, old_chunk.size - size };
    127     InsertChunk(&free_by_start_, &free_by_size_, new_chunk);
    128   }
    129 
    130   return ret;
    131 }
    132 
    133 SpaceChunk SwapSpace::NewFileChunk(size_t min_size) {
    134 #if !defined(__APPLE__)
    135   size_t next_part = std::max(RoundUp(min_size, kPageSize), RoundUp(kMininumMapSize, kPageSize));
    136   int result = TEMP_FAILURE_RETRY(ftruncate64(fd_, size_ + next_part));
    137   if (result != 0) {
    138     PLOG(FATAL) << "Unable to increase swap file.";
    139   }
    140   uint8_t* ptr = reinterpret_cast<uint8_t*>(
    141       mmap(nullptr, next_part, PROT_READ | PROT_WRITE, MAP_SHARED, fd_, size_));
    142   if (ptr == MAP_FAILED) {
    143     LOG(ERROR) << "Unable to mmap new swap file chunk.";
    144     LOG(ERROR) << "Current size: " << size_ << " requested: " << next_part << "/" << min_size;
    145     LOG(ERROR) << "Free list:";
    146     MutexLock lock(Thread::Current(), lock_);
    147     DumpFreeMap(free_by_size_);
    148     LOG(ERROR) << "In free list: " << CollectFree(free_by_start_, free_by_size_);
    149     LOG(FATAL) << "Aborting...";
    150   }
    151   size_ += next_part;
    152   SpaceChunk new_chunk = {ptr, next_part};
    153   maps_.push_back(new_chunk);
    154   return new_chunk;
    155 #else
    156   UNUSED(kMininumMapSize);
    157   LOG(FATAL) << "No swap file support on the Mac.";
    158   return {nullptr, 0U};  // NOLINT [readability/braces] [4]
    159 #endif
    160 }
    161 
    162 // TODO: Full coalescing.
    163 void SwapSpace::Free(void* ptrV, size_t size) {
    164   MutexLock lock(Thread::Current(), lock_);
    165   size = RoundUp(size, 8U);
    166 
    167   size_t free_before = 0;
    168   if (kCheckFreeMaps) {
    169     free_before = CollectFree(free_by_start_, free_by_size_);
    170   }
    171 
    172   SpaceChunk chunk = { reinterpret_cast<uint8_t*>(ptrV), size };
    173   auto it = free_by_start_.lower_bound(chunk);
    174   if (it != free_by_start_.begin()) {
    175     auto prev = it;
    176     --prev;
    177     CHECK_LE(prev->End(), chunk.Start());
    178     if (prev->End() == chunk.Start()) {
    179       // Merge *prev with this chunk.
    180       chunk.size += prev->size;
    181       chunk.ptr -= prev->size;
    182       auto erase_pos = free_by_size_.find(FreeBySizeEntry { prev->size, prev });
    183       DCHECK(erase_pos != free_by_size_.end());
    184       RemoveChunk(&free_by_start_, &free_by_size_, erase_pos);
    185       // "prev" is invalidated but "it" remains valid.
    186     }
    187   }
    188   if (it != free_by_start_.end()) {
    189     CHECK_LE(chunk.End(), it->Start());
    190     if (chunk.End() == it->Start()) {
    191       // Merge *it with this chunk.
    192       chunk.size += it->size;
    193       auto erase_pos = free_by_size_.find(FreeBySizeEntry { it->size, it });
    194       DCHECK(erase_pos != free_by_size_.end());
    195       RemoveChunk(&free_by_start_, &free_by_size_, erase_pos);
    196       // "it" is invalidated but we don't need it anymore.
    197     }
    198   }
    199   InsertChunk(&free_by_start_, &free_by_size_, chunk);
    200 
    201   if (kCheckFreeMaps) {
    202     size_t free_after = CollectFree(free_by_start_, free_by_size_);
    203 
    204     if (free_after != free_before + size) {
    205       DumpFreeMap(free_by_size_);
    206       CHECK_EQ(free_after, free_before + size) << "Should be " << size << " difference from " << free_before;
    207     }
    208   }
    209 }
    210 
    211 }  // namespace art
    212