a82a04a2f9110a31db1321b0bd7eedadb309bb58
[WebKit.git] / Source / bmalloc / bmalloc / XLargeMap.cpp
1 /*
2  * Copyright (C) 2016 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
24  */
25
26 #include "XLargeMap.h"
27
28 namespace bmalloc {
29
30 XLargeRange XLargeMap::takeFree(size_t alignment, size_t size)
31 {
32     size_t alignmentMask = alignment - 1;
33
34     XLargeRange* candidate = m_free.end();
35     for (XLargeRange* it = m_free.begin(); it != m_free.end(); ++it) {
36         if (it->size() < size)
37             continue;
38
39         if (candidate != m_free.end() && candidate->begin() < it->begin())
40             continue;
41
42         if (test(it->begin(), alignmentMask)) {
43             char* aligned = roundUpToMultipleOf(alignment, it->begin());
44             if (aligned < it->begin()) // Check for overflow.
45                 continue;
46
47             char* alignedEnd = aligned + size;
48             if (alignedEnd < aligned) // Check for overflow.
49                 continue;
50
51             if (alignedEnd > it->end())
52                 continue;
53         }
54
55         candidate = it;
56     }
57     
58     if (candidate == m_free.end())
59         return XLargeRange();
60
61     return m_free.pop(candidate);
62 }
63
64 void XLargeMap::addFree(const XLargeRange& range)
65 {
66     XLargeRange merged = range;
67
68     for (size_t i = 0; i < m_free.size(); ++i) {
69         auto& other = m_free[i];
70
71         if (!canMerge(merged, other))
72             continue;
73
74         merged = merge(merged, m_free.pop(i--));
75     }
76     
77     m_free.push(merged);
78 }
79
80 void XLargeMap::addAllocated(const XLargeRange& prev, const std::pair<XLargeRange, XLargeRange>& allocated, const XLargeRange& next)
81 {
82     if (prev)
83         m_free.push(prev);
84     
85     if (next)
86         m_free.push(next);
87
88     m_allocated.insert({ allocated.first, allocated.second });
89 }
90
91 XLargeRange XLargeMap::getAllocated(void* object)
92 {
93     return m_allocated.find(object)->object;
94 }
95
96 XLargeRange XLargeMap::takeAllocated(void* object)
97 {
98     Allocation allocation = m_allocated.take(object);
99     return merge(allocation.object, allocation.unused);
100 }
101
102 void XLargeMap::shrinkToFit()
103 {
104     m_free.shrinkToFit();
105     m_allocated.shrinkToFit();
106 }
107
108 XLargeRange XLargeMap::takePhysical() {
109     auto hasPhysical = [](const XLargeRange& range) {
110         return range.vmState().hasPhysical();
111     };
112
113     auto it = std::find_if(m_free.begin(), m_free.end(), hasPhysical);
114     if (it != m_free.end())
115         return m_free.pop(it);
116
117     auto hasUnused = [](const Allocation& allocation) {
118         return allocation.unused && allocation.unused.vmState().hasPhysical();
119     };
120     
121     XLargeRange swapped;
122     auto it2 = std::find_if(m_allocated.begin(), m_allocated.end(), hasUnused);
123     if (it2 != m_allocated.end())
124         std::swap(it2->unused, swapped);
125     
126     return swapped;
127 }
128
129 void XLargeMap::addVirtual(const XLargeRange& range)
130 {
131     auto canMerge = [&range](const Allocation& other) {
132         return other.object.end() == range.begin();
133     };
134
135     if (range.size() < xLargeAlignment) {
136         // This is an unused fragment, so it might belong in the allocated list.
137         auto it = std::find_if(m_allocated.begin(), m_allocated.end(), canMerge);
138         if (it != m_allocated.end()) {
139             BASSERT(!it->unused);
140             it->unused = range;
141             return;
142         }
143
144         // If we didn't find a neighbor in the allocated list, our neighbor must
145         // have been freed. We'll merge with it below.
146     }
147
148     addFree(range);
149 }
150
151 } // namespace bmalloc