bmalloc: Renamed LargeChunk => Chunk
[WebKit-https.git] / Source / bmalloc / bmalloc / FreeList.cpp
1 /*
2  * Copyright (C) 2014-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 "FreeList.h"
27 #include "Chunk.h"
28 #include "Vector.h"
29
30 namespace bmalloc {
31
32 // We don't eagerly remove invalidated entries from the free list when we merge
33 // large objects. This means that the free list can contain invalid and/or
34 // duplicate entries. (Repeating a merge-and-then-split produces a duplicate.)
35
36 // To avoid infinite growth in invalid entries, we incrementally remove
37 // invalid entries as we discover them during allocation, and we also garbage
38 // collect the free list as it grows.
39
40 LargeObject FreeList::takeGreedy(VMState::HasPhysical hasPhysical)
41 {
42     for (size_t i = 0; i < m_vector.size(); ++i) {
43         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
44         if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
45             m_vector.pop(i--);
46             continue;
47         }
48
49         m_vector.pop(i--);
50         return largeObject;
51     }
52
53     return LargeObject();
54 }
55
56 LargeObject FreeList::take(VMState::HasPhysical hasPhysical, size_t size)
57 {
58     LargeObject candidate;
59     size_t candidateIndex;
60     size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
61     for (size_t i = begin; i < m_vector.size(); ++i) {
62         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
63         if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
64             m_vector.pop(i--);
65             continue;
66         }
67
68         if (largeObject.size() < size)
69             continue;
70
71         if (!!candidate && candidate.begin() < largeObject.begin())
72             continue;
73
74         candidate = largeObject;
75         candidateIndex = i;
76     }
77
78     if (!!candidate)
79         m_vector.pop(candidateIndex);
80     return candidate;
81 }
82
83 LargeObject FreeList::take(VMState::HasPhysical hasPhysical, size_t alignment, size_t size, size_t unalignedSize)
84 {
85     BASSERT(isPowerOfTwo(alignment));
86     size_t alignmentMask = alignment - 1;
87
88     LargeObject candidate;
89     size_t candidateIndex;
90     size_t begin = m_vector.size() > freeListSearchDepth ? m_vector.size() - freeListSearchDepth : 0;
91     for (size_t i = begin; i < m_vector.size(); ++i) {
92         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
93         if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
94             m_vector.pop(i--);
95             continue;
96         }
97
98         if (largeObject.size() < size)
99             continue;
100
101         if (test(largeObject.begin(), alignmentMask) && largeObject.size() < unalignedSize)
102             continue;
103
104         if (!!candidate && candidate.begin() < largeObject.begin())
105             continue;
106
107         candidate = largeObject;
108         candidateIndex = i;
109     }
110     
111     if (!!candidate)
112         m_vector.pop(candidateIndex);
113     return candidate;
114 }
115
116 void FreeList::removeInvalidAndDuplicateEntries(VMState::HasPhysical hasPhysical)
117 {
118     for (size_t i = 0; i < m_vector.size(); ++i) {
119         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
120         if (!largeObject.isValidAndFree(hasPhysical, m_vector[i].size())) {
121             m_vector.pop(i--);
122             continue;
123         }
124         
125         largeObject.setMarked(false);
126     }
127
128     for (size_t i = 0; i < m_vector.size(); ++i) {
129         LargeObject largeObject(LargeObject::DoNotValidate, m_vector[i].begin());
130         if (largeObject.isMarked()) {
131             m_vector.pop(i--);
132             continue;
133         }
134
135         largeObject.setMarked(true);
136     }
137 }
138
139
140 } // namespace bmalloc