bmalloc
[WebKit-https.git] / Source / bmalloc / bmalloc / SegregatedFreeList.cpp
1 /*
2  * Copyright (C) 2014 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 "BeginTag.h"
27 #include "LargeChunk.h"
28 #include "SegregatedFreeList.h"
29 #include "Vector.h"
30
31 namespace bmalloc {
32
33 SegregatedFreeList::SegregatedFreeList()
34 {
35     ASSERT(&select(largeMax) - m_lists.begin() == m_lists.size() - 1);
36 }
37
38 void SegregatedFreeList::insert(const Range& range)
39 {
40 IF_DEBUG(
41     BeginTag* beginTag = LargeChunk::beginTag(range.begin());
42     ASSERT(beginTag->isInFreeList(range.size()));
43 )
44
45     auto& list = select(range.size());
46     list.push(range);
47 }
48
49 Range SegregatedFreeList::takeGreedy(size_t minimum)
50 {
51     for (size_t i = m_lists.size(); i-- > 0; ) {
52         Range range = takeGreedy(m_lists[i], minimum);
53         if (!range)
54             continue;
55
56         return range;
57     }
58     return Range();
59 }
60
61 Range SegregatedFreeList::takeGreedy(List& list, size_t minimum)
62 {
63     for (size_t i = list.size(); i-- > 0; ) {
64         Range range = list[i];
65
66         // We don't eagerly remove items when we merge and/or split ranges,
67         // so we need to validate each free list entry before using it.
68         BeginTag* beginTag = LargeChunk::beginTag(range.begin());
69         if (!beginTag->isInFreeList(range.size())) {
70             list.pop(i);
71             continue;
72         }
73
74         if (range.size() < minimum)
75             continue;
76
77         list.pop(i);
78         return range;
79     }
80
81     return Range();
82 }
83
84 Range SegregatedFreeList::take(size_t minimum)
85 {
86     for (auto* list = &select(minimum); list != m_lists.end(); ++list) {
87         Range range = take(*list, minimum);
88         if (!range)
89             continue;
90
91         return range;
92     }
93     return Range();
94 }
95
96 INLINE auto SegregatedFreeList::select(size_t size) -> List&
97 {
98     size_t alignCount = (size - largeMin) / largeAlignment;
99     size_t result = 0;
100     while (alignCount) {
101         ++result;
102         alignCount >>= 1;
103     }
104     return m_lists[result];
105 }
106
107 INLINE Range SegregatedFreeList::take(List& list, size_t minimum)
108 {
109     Range first;
110     size_t end = list.size() > segregatedFreeListSearchDepth ? list.size() - segregatedFreeListSearchDepth : 0;
111     for (size_t i = list.size(); i-- > end; ) {
112         Range range = list[i];
113
114         // We don't eagerly remove items when we merge and/or split ranges, so
115         // we need to validate each free list entry before using it.
116         BeginTag* beginTag = LargeChunk::beginTag(range.begin());
117         if (!beginTag->isInFreeList(range.size())) {
118             list.pop(i);
119             continue;
120         }
121
122         if (range.size() < minimum)
123             continue;
124
125         if (!!first && first < range)
126             continue;
127
128         first = range;
129     }
130     
131     return first;
132 }
133
134 } // namespace bmalloc