Line data    Source code

       1             : // Copyright 2017 the V8 project authors. All rights reserved.
       2             : // Use of this source code is governed by a BSD-style license that can be
       3             : // found in the LICENSE file.
       4             : 
       5             : #include "src/wasm/wasm-heap.h"
       6             : 
       7             : namespace v8 {
       8             : namespace internal {
       9             : namespace wasm {
      10             : 
      11          40 : DisjointAllocationPool::DisjointAllocationPool(Address start, Address end) {
      12          40 :   ranges_.push_back({start, end});
      13          40 : }
      14             : 
      15          54 : void DisjointAllocationPool::Merge(DisjointAllocationPool&& other) {
      16          54 :   auto dest_it = ranges_.begin();
      17             :   auto dest_end = ranges_.end();
      18             : 
      19         249 :   for (auto src_it = other.ranges_.begin(), src_end = other.ranges_.end();
      20             :        src_it != src_end;) {
      21          87 :     if (dest_it == dest_end) {
      22             :       // everything else coming from src will be inserted
      23             :       // at the back of ranges_ from now on.
      24          44 :       ranges_.push_back(*src_it);
      25             :       ++src_it;
      26             :       continue;
      27             :     }
      28             :     // Before or adjacent to dest. Insert or merge, and advance
      29             :     // just src.
      30          43 :     if (dest_it->first >= src_it->second) {
      31           6 :       if (dest_it->first == src_it->second) {
      32           2 :         dest_it->first = src_it->first;
      33             :       } else {
      34          12 :         ranges_.insert(dest_it, {src_it->first, src_it->second});
      35             :       }
      36             :       ++src_it;
      37             :       continue;
      38             :     }
      39             :     // Src is strictly after dest. Skip over this dest.
      40          37 :     if (dest_it->second < src_it->first) {
      41             :       ++dest_it;
      42             :       continue;
      43             :     }
      44             :     // Src is adjacent from above. Merge and advance
      45             :     // just src, because the next src, if any, is bound to be
      46             :     // strictly above the newly-formed range.
      47             :     DCHECK_EQ(dest_it->second, src_it->first);
      48           7 :     dest_it->second = src_it->second;
      49             :     ++src_it;
      50             :     // Now that we merged, maybe this new range is adjacent to
      51             :     // the next. Since we assume src to have come from the
      52             :     // same original memory pool, it follows that the next src
      53             :     // must be above or adjacent to the new bubble.
      54             :     auto next_dest = dest_it;
      55             :     ++next_dest;
      56           7 :     if (next_dest != dest_end && dest_it->second == next_dest->first) {
      57           6 :       dest_it->second = next_dest->second;
      58             :       ranges_.erase(next_dest);
      59             :     }
      60             : 
      61             :     // src_it points now at the next, if any, src
      62             :     DCHECK_IMPLIES(src_it != src_end, src_it->first >= dest_it->second);
      63             :   }
      64          54 : }
      65             : 
      66           6 : DisjointAllocationPool DisjointAllocationPool::Extract(size_t size,
      67             :                                                        ExtractionMode mode) {
      68             :   DisjointAllocationPool ret;
      69          23 :   for (auto it = ranges_.begin(), end = ranges_.end(); it != end;) {
      70             :     auto current = it;
      71             :     ++it;
      72             :     DCHECK_LT(current->first, current->second);
      73           9 :     size_t current_size = reinterpret_cast<size_t>(current->second) -
      74           9 :                           reinterpret_cast<size_t>(current->first);
      75           9 :     if (size == current_size) {
      76           2 :       ret.ranges_.push_back(*current);
      77             :       ranges_.erase(current);
      78             :       return ret;
      79             :     }
      80           7 :     if (size < current_size) {
      81           4 :       ret.ranges_.push_back({current->first, current->first + size});
      82           2 :       current->first += size;
      83             :       DCHECK(current->first < current->second);
      84             :       return ret;
      85             :     }
      86           5 :     if (mode != kContiguous) {
      87           2 :       size -= current_size;
      88           2 :       ret.ranges_.push_back(*current);
      89             :       ranges_.erase(current);
      90             :     }
      91             :   }
      92           2 :   if (size > 0) {
      93           2 :     Merge(std::move(ret));
      94             :     return {};
      95             :   }
      96             :   return ret;
      97             : }
      98             : 
      99             : }  // namespace wasm
     100             : }  // namespace internal
     101             : }  // namespace v8