bmalloc: Added a fast XLarge allocator
[WebKit-https.git] / Source / bmalloc / ChangeLog
1 2016-02-25  Geoffrey Garen  <ggaren@apple.com>
2
3         bmalloc: Added a fast XLarge allocator
4         https://bugs.webkit.org/show_bug.cgi?id=154720
5
6         Reviewed by Andreas Kling.
7
8         This is a big speedup for XLarge allocations because it avoids mmap
9         and page fault churn. It also enables future design changes to handle
10         a smaller size range on the fast path.
11
12         * bmalloc.xcodeproj/project.pbxproj:
13
14         * bmalloc/Algorithm.h:
15         (bmalloc::roundUpToMultipleOf):
16         (bmalloc::roundDownToMultipleOf): Added a non-constant round down.
17
18         * bmalloc/Allocator.cpp:
19         (bmalloc::Allocator::tryAllocate): XLarge no longer requires the caller
20         to align things.
21
22         (bmalloc::Allocator::allocate): Tweaked the alignment calculation for
23         clarity. When alignment and largeAlignment are equal, no adjustment
24         is necessary since all allocations guarantee largeAlignment.
25
26         (bmalloc::Allocator::reallocate): Updated for interface change.
27
28         Note that the new interface fixes some concurrency bugs. The old code
29         kept an iterator into the XLarge allocator across lock drop and acquisition,
30         which is not cool.
31
32         (bmalloc::Allocator::allocateXLarge): XLarge no longer requires the caller
33         to align things.
34
35         * bmalloc/Heap.cpp:
36         (bmalloc::Heap::scavengeXLargeObjects): Added scavenging for XLarge.
37
38         (bmalloc::Heap::allocateXLarge):
39
40         (bmalloc::Heap::splitAndAllocate): Split XLarge objects to xLargeAlignment.
41
42         (bmalloc::Heap::tryAllocateXLarge):
43         (bmalloc::Heap::xLargeSize):
44         (bmalloc::Heap::shrinkXLarge):
45         (bmalloc::Heap::deallocateXLarge): Allocate from our map before going
46         to the OS.
47
48         (bmalloc::Heap::findXLarge): Deleted.
49
50         * bmalloc/Heap.h:
51
52         * bmalloc/LargeObject.h:
53         (bmalloc::LargeObject::split):
54
55         * bmalloc/ObjectType.h:
56         (bmalloc::isXLarge): Give XLarge objects an explicit alignment for clarity.
57
58         * bmalloc/Range.h:
59         (bmalloc::Range::size):
60         (bmalloc::Range::operator!):
61         (bmalloc::Range::operator bool):
62         (bmalloc::Range::operator<):
63         (bmalloc::canMerge):
64         (bmalloc::merge): Some helpers that were useful in writing this patch.
65
66         * bmalloc/Sizes.h:
67
68         * bmalloc/SortedVector.h: Added.
69         (bmalloc::SortedVector::Bucket::Bucket):
70         (bmalloc::SortedVector::Bucket::operator<):
71         (bmalloc::SortedVector::iterator::iterator):
72         (bmalloc::SortedVector::iterator::operator++):
73         (bmalloc::SortedVector::iterator::operator!=):
74         (bmalloc::SortedVector::iterator::operator*):
75         (bmalloc::SortedVector::iterator::operator->):
76         (bmalloc::SortedVector::iterator::skipDeletedBuckets):
77         (bmalloc::SortedVector::begin):
78         (bmalloc::SortedVector::end):
79         (bmalloc::SortedVector<T>::insert):
80         (bmalloc::SortedVector<T>::find):
81         (bmalloc::SortedVector<T>::get):
82         (bmalloc::SortedVector<T>::take):
83         (bmalloc::SortedVector<T>::shrinkToFit): A simple abstraction for keeping
84         a sorted vector. Insertion is average amortized log(n) because we keep
85         deleted buckets that we can reuse.
86
87         This is better than a tree because we get better locality, less memory
88         use, and simpler code. Also, trees require a node memory allocator, and
89         implementing a memory allocator in a memory allocator is no fun.
90
91         Arguably we should use a hash table instead. But that's more code, and
92         sorted vector has other nice properties that we might want to take
93         adavantage of in the future.
94
95         * bmalloc/VMAllocate.h:
96         (bmalloc::tryVMAllocate): Fixed an inaccuracy in the alignment calculation
97         here. This code was sort of trying to enforce the alignment that the
98         XLarge allocator enforces -- but it's better to enforce that alignment
99         there.
100
101         The right calculation is:
102
103             vmAlignment - vmPageSize + vmSize
104
105         because the worst case is when you are aligned to 0 + vmPageSize, and
106         you must walk forward vmAlignment - vmPageSize to reach the next
107         vmAlignment.
108
109         (bmalloc::tryVMExtend): Deleted. No need to go back to the OS for VM
110         since we manage our own.
111
112         * bmalloc/VMHeap.cpp:
113         (bmalloc::VMHeap::allocateLargeChunk): Updated for clarity. When we
114         grow the large heap we know that grown region is where the next allocation
115         will take place, so we return it directly instead of pushing it to the
116         free list.
117
118         This fixes a subtle bug where an overly conservative aligned allocation
119         algorithm can fail to allocate at all when it grows the heap.
120
121         * bmalloc/VMHeap.h:
122         (bmalloc::VMHeap::allocateLargeObject): Ditto.
123         (bmalloc::VMHeap::allocateLargeObject): Ditto.
124
125         * bmalloc/VMState.h:
126         (bmalloc::merge): Added a helper.
127
128         * bmalloc/Vector.h:
129         (bmalloc::Vector::begin):
130         (bmalloc::Vector::end):
131         (bmalloc::Vector::size):
132         (bmalloc::Vector::capacity):
133         (bmalloc::Vector::last):
134         (bmalloc::Vector::pop):
135         (bmalloc::Vector<T>::push):
136         (bmalloc::Vector<T>::pop):
137         (bmalloc::Vector<T>::shrink): Use a proper iterator API to play nice
138         with std algorithms.
139
140         (bmalloc::Vector<T>::insert): New function required by SortedVector.
141
142         (bmalloc::Vector<T>::reallocateBuffer):
143         (bmalloc::Vector<T>::shrinkCapacity): Allow for shrinking back all the way
144         to 0 because that's what shrinkToFit wants.
145         (bmalloc::Vector<T>::growCapacity):
146         (bmalloc::Vector<T>::shrinkToFit):
147
148         * bmalloc/XLargeMap.cpp: Added. Helper data structure for managing XLarge
149         objects. We have enough granularity in our metadata to represent any
150         kind of address range.
151
152         We store free ranges in a flat vector because most programs have very
153         few individual free XLarge ranges. (They usually merge.)
154
155         We store allocated ranges in a sorted vector because programs might
156         allocate lots of XLarge ranges. For example, if the XLarge minimum is
157         128kB, and you have a 1GB process, that's 8192 ranges. Linear scan would
158         examine 8192 items but binary search only 13.
159
160         Empirically, this is 1.5X faster than our current large allocator if you
161         modify MallocBench/big to allocate XLarge objects and not to initialize
162         objects and you allocate 128kB-256kB objects in a 1GB address space.
163
164         (bmalloc::XLargeMap::takeFree): Be careful about overflow in this function
165         because we support super huge pointers, alignments, and sizes.
166
167         (bmalloc::XLargeMap::addFree): Merge eagerly on free because the cost
168         of missing an XLarge opportunity is catastrophic. Also, I discovered
169         by experiment that any allocator that doesn't merge eagerly can create
170         lots of subtle opportunities for snowballing fragmentation, as
171         fragmentation in range A forces you to chop up range B, and so on.
172
173         We allocate "first fit" (allocating the lowest address) because someone
174         wrote a paper once that said that it's the best algorithm to combat
175         fragmentation (even though worst case fragmentation is unavoidable
176         regardless of algorithm).
177
178         (bmalloc::XLargeMap::addAllocated):
179         (bmalloc::XLargeMap::getAllocated):
180         (bmalloc::XLargeMap::takeAllocated):
181         (bmalloc::XLargeMap::shrinkToFit):
182         (bmalloc::XLargeMap::takePhysical):
183         (bmalloc::XLargeMap::addVirtual):
184         * bmalloc/XLargeMap.h: Added.
185         (bmalloc::XLargeMap::Allocation::operator<):
186
187         * bmalloc/XLargeRange.h: Added.
188         (bmalloc::XLargeRange::XLargeRange):
189         (bmalloc::XLargeRange::vmState):
190         (bmalloc::XLargeRange::setVMState):
191         (bmalloc::canMerge):
192         (bmalloc::merge):
193         (bmalloc::XLargeRange::split): Helper for tracking VMState in a range.
194
195 2016-02-23  Dan Bernstein  <mitz@apple.com>
196
197         [Xcode] Linker errors display mangled names, but no longer should
198         https://bugs.webkit.org/show_bug.cgi?id=154632
199
200         Reviewed by Sam Weinig.
201
202         * Configurations/Base.xcconfig: Stop setting LINKER_DISPLAYS_MANGLED_NAMES to YES.
203
204 2016-02-22  Konstantin Tokarev  <annulen@yandex.ru>
205
206         Fixed compilation of bmalloc with GCC 4.8 after r196873.
207         https://bugs.webkit.org/show_bug.cgi?id=154534
208
209         Reviewed by Mark Lam.
210
211         See https://gcc.gnu.org/bugzilla/show_bug.cgi?id=55382.
212
213         * bmalloc/LargeChunk.h:
214         * bmalloc/SmallChunk.h:
215
216 2016-02-21  Geoffrey Garen  <ggaren@apple.com>
217
218         bmalloc: Don't use a whole page for metadata
219         https://bugs.webkit.org/show_bug.cgi?id=154510
220
221         Reviewed by Andreas Kling.
222
223         (1) Don't round up metadata to a page boundary. This saves 1.5% dirty
224         memory on iOS and 0.2% on Mac. It also enables a future patch to allocate
225         smaller chunks without wasting memory.
226
227         (2) Initialize metadata lazily. This saves dirty memory when the program
228         allocates primarily small or large objects (but not both), leaving some
229         metadata uninitialized.
230
231         * bmalloc.xcodeproj/project.pbxproj: Medium objects are gone now.
232
233         * bmalloc/BumpAllocator.h:
234         (bmalloc::BumpAllocator::refill): Added an ASSERT to help debug a bug
235         I cause while working on this patch.
236
237         * bmalloc/Heap.cpp:
238         (bmalloc::Heap::allocateSmallBumpRanges): Ditto.
239
240         (bmalloc::Heap::splitAndAllocate):
241         (bmalloc::Heap::allocateLarge): Updated for interface change.
242
243         * bmalloc/LargeChunk.h: Changed the boundaryTagCount calculation to
244         a static_assert.
245
246         Don't round up to page boundary. (See above.)
247
248         (bmalloc::LargeChunk::LargeChunk): Moved code here from LargeChunk::init.
249         A constructor is a more natural / automatic way to do this initialization.
250
251         * bmalloc/LargeObject.h:
252         (bmalloc::LargeObject::init): Deleted. Moved to LargeChunk.
253
254         * bmalloc/Sizes.h: Chagned largeChunkMetadataSize to a simpler constant
255         because metadata size no longer varies by page size.
256
257         * bmalloc/SmallChunk.h:
258         (bmalloc::SmallChunk::begin):
259         (bmalloc::SmallChunk::end):
260         (bmalloc::SmallChunk::lines):
261         (bmalloc::SmallChunk::pages): Use std::array to make begin/end
262         calculations easier.
263
264         (bmalloc::SmallChunk::SmallChunk): Treat our metadata like a series
265         of allocated objects. We used to avoid trampling our metadata by
266         starting object memory at the next page. Now we share the first page
267         between metadata and objects, and we account for metadata explicitly.
268
269         * bmalloc/SuperChunk.h:
270         (bmalloc::SuperChunk::SuperChunk):
271         (bmalloc::SuperChunk::smallChunk):
272         (bmalloc::SuperChunk::largeChunk):
273         (bmalloc::SuperChunk::create): Deleted. Don't eagerly run the SmallChunk
274         and LargeChunk constructors. We'll run them lazily as needed.
275
276         * bmalloc/VMHeap.cpp:
277         (bmalloc::VMHeap::VMHeap):
278         (bmalloc::VMHeap::allocateSmallChunk):
279         (bmalloc::VMHeap::allocateLargeChunk):
280         (bmalloc::VMHeap::allocateSuperChunk):
281         (bmalloc::VMHeap::grow): Deleted. Track small and large chunks explicitly
282         so we can initialize them lazily.
283
284         * bmalloc/VMHeap.h:
285         (bmalloc::VMHeap::allocateSmallPage):
286         (bmalloc::VMHeap::allocateLargeObject): Specify whether we're allocating
287         a small or large chunk since we don't allocate both at once anymore.
288
289 2016-02-20  Mark Lam  <mark.lam@apple.com>
290
291         Use of inlined asm statements causes problems for -std=c99 builds.
292         https://bugs.webkit.org/show_bug.cgi?id=154507
293
294         Reviewed by Dan Bernstein.
295
296         * bmalloc/BAssert.h:
297
298 2016-02-19  Joonghun Park  <jh718.park@samsung.com>
299
300         Unreviewed. Fix debug build error since r196847
301
302         Fix gcc build warning appeared as below
303         by removing BASSERT(refCount <= maxRefCount).
304         error: comparison is always true due to limited range of data type
305         [-Werror=type-limits]
306
307         * bmalloc/SmallLine.h:
308         (bmalloc::SmallLine::ref): Deleted.
309
310 2016-02-19  Geoffrey Garen  <ggaren@apple.com>
311
312         bmalloc: Chunk, Page, and Line don't need to be class templates
313         https://bugs.webkit.org/show_bug.cgi?id=154480
314
315         Reviewed by Gavin Barraclough.
316
317         We needed class templates to distinguish between small and medium,
318         but medium is gone now.
319
320         * bmalloc.xcodeproj/project.pbxproj:
321         * bmalloc/Chunk.h: Removed.
322         * bmalloc/Heap.cpp:
323         (bmalloc::Heap::initializeLineMetadata):
324         (bmalloc::Heap::allocateSmallBumpRanges):
325         * bmalloc/Heap.h:
326         * bmalloc/Line.h: Removed.
327         * bmalloc/Page.h: Removed.
328         * bmalloc/Sizes.h:
329         * bmalloc/SmallChunk.h: Replaced with Source/bmalloc/bmalloc/Chunk.h.
330         (bmalloc::SmallChunk::begin):
331         (bmalloc::SmallChunk::end):
332         (bmalloc::SmallChunk::lines):
333         (bmalloc::SmallChunk::pages):
334         (bmalloc::SmallChunk::get):
335         (bmalloc::SmallLine::get):
336         (bmalloc::SmallLine::begin):
337         (bmalloc::SmallLine::end):
338         (bmalloc::SmallPage::get):
339         (bmalloc::SmallPage::begin):
340         (bmalloc::SmallPage::end):
341         (bmalloc::Chunk::begin): Deleted.
342         (bmalloc::Chunk::end): Deleted.
343         (bmalloc::Chunk::lines): Deleted.
344         (bmalloc::Chunk::pages): Deleted.
345         * bmalloc/SmallLine.h: Replaced with Source/bmalloc/bmalloc/Line.h.
346         (bmalloc::SmallLine::ref):
347         (bmalloc::SmallLine::deref):
348         (bmalloc::Line<Traits>::begin): Deleted.
349         (bmalloc::Line<Traits>::end): Deleted.
350         (bmalloc::Line<Traits>::ref): Deleted.
351         (bmalloc::Line<Traits>::deref): Deleted.
352         * bmalloc/SmallPage.h: Replaced with Source/bmalloc/bmalloc/Page.h.
353         (bmalloc::SmallPage::hasFreeLines):
354         (bmalloc::SmallPage::setHasFreeLines):
355         (bmalloc::SmallPage::ref):
356         (bmalloc::SmallPage::deref):
357         (bmalloc::Page::hasFreeLines): Deleted.
358         (bmalloc::Page::setHasFreeLines): Deleted.
359         (bmalloc::Page<Traits>::ref): Deleted.
360         (bmalloc::Page<Traits>::deref): Deleted.
361         * bmalloc/SmallTraits.h: Removed.
362
363 2016-02-18  Geoffrey Garen  <ggaren@apple.com>
364
365         bmalloc: Remove the concept of medium objects
366         https://bugs.webkit.org/show_bug.cgi?id=154436
367
368         Reviewed by Sam Weinig.
369
370         There's no need to distinguish medium objects from small: Small object
371         metadata works naturally for both as long as we allow an object to
372         span more than two small lines. (We already allow an object to span
373         more than one small line.)
374
375         This change reduces memory use because it eliminates the 1kB line size,
376         so we don't have to hold down 1kB lines for individual 264+ byte objects.
377
378         1kB lines were always a bit of a compromise. The main point of bump
379         allocation is to take advantage of cache lines. Cache lines are usually
380         64 bytes, so line sizes above 256 bytes are a bit of a stretch.
381
382         This change speeds up small object benchmarks because it eliminates the
383         branch to detect medium objects in deallocation log processing.
384
385         This change reduces virtual memory use from worst cast 4X to worst case
386         2X because the medium chunk is gone. iOS cares about virtual memory use
387         and terminates apps above ~1GB, so this change gives us more breathing room.
388
389         This change slows down medium benchmarks a bit because we end up doing
390         more work to recycle fragmented medium objects. Overall, the tradeoff
391         seems justified, since we have a net speedup and a memory use savings.
392
393         * bmalloc.xcodeproj/project.pbxproj: Removed all the medium files. We
394         can simplify even further in a follow-up patch, removing the base class
395         templates for Chunk, Page, and Line as well.
396
397         * bmalloc/Allocator.cpp:
398         (bmalloc::Allocator::Allocator):
399         (bmalloc::Allocator::allocate):
400         (bmalloc::Allocator::reallocate):
401         (bmalloc::Allocator::scavenge):
402         (bmalloc::Allocator::refillAllocatorSlowCase):
403         (bmalloc::Allocator::refillAllocator):
404         (bmalloc::Allocator::allocateSlowCase): Medium is gone. Small max is the
405         new medium max.
406
407         * bmalloc/Allocator.h:
408         (bmalloc::Allocator::allocateFastCase): Ditto.
409
410         * bmalloc/BumpAllocator.h:
411         (bmalloc::BumpAllocator::validate):
412         (bmalloc::BumpAllocator::allocate): No more medium.
413
414         * bmalloc/Chunk.h: No more medium.
415
416         * bmalloc/Deallocator.cpp:
417         (bmalloc::Deallocator::processObjectLog): No check for medium. This is
418         a speedup.
419
420         (bmalloc::Deallocator::deallocateSlowCase): No more medium.
421
422         * bmalloc/Deallocator.h:
423         (bmalloc::Deallocator::deallocateFastCase): Ditto.
424
425         * bmalloc/Heap.cpp:
426         (bmalloc::Heap::initializeLineMetadata): The algorithm here changed from
427         iterating each line to iterating each object. This helps us accomodate
428         objects that might span more than two lines -- i.e., all objects between
429         (512 bytes, 1024 bytes].
430
431         (bmalloc::Heap::scavenge):
432         (bmalloc::Heap::scavengeSmallPages):
433         (bmalloc::Heap::scavengeLargeObjects): Medium is gone.
434
435         (bmalloc::Heap::allocateSmallBumpRanges): Allow for lines that allocate
436         zero objects. This happens when an object spans more than two lines --
437         the middle lines allocate zero objects.
438
439         Also set the "has free lines" bit to false if we consume the last free
440         line. This needs to be a bit now because not all pages agree on their
441         maximum refcount anymore, so we need an explicit signal for the transition
442         from maximum to maximum - 1.
443
444         (bmalloc::Heap::allocateSmallPage): This code didn't change; I just removed
445         the medium code.
446
447         (bmalloc::Heap::deallocateSmallLine): Changed the algorithm to check
448         hasFreeLines. See allocateSmallBumpRanges.
449
450         (bmalloc::Heap::scavengeMediumPages): Deleted.
451         (bmalloc::Heap::allocateMediumBumpRanges): Deleted.
452         (bmalloc::Heap::allocateMediumPage): Deleted.
453         (bmalloc::Heap::deallocateMediumLine): Deleted.
454         * bmalloc/Heap.h:
455         (bmalloc::Heap::derefMediumLine): Deleted.
456
457         * bmalloc/LargeChunk.h:
458         (bmalloc::LargeChunk::get):
459         (bmalloc::LargeChunk::endTag):
460         * bmalloc/Line.h: No more medium.
461
462         * bmalloc/MediumChunk.h: Removed.
463         * bmalloc/MediumLine.h: Removed.
464         * bmalloc/MediumPage.h: Removed.
465         * bmalloc/MediumTraits.h: Removed.
466
467         * bmalloc/ObjectType.cpp:
468         (bmalloc::objectType):
469         * bmalloc/ObjectType.h:
470         (bmalloc::isSmall):
471         (bmalloc::isXLarge):
472         (bmalloc::isSmallOrMedium): Deleted.
473         (bmalloc::isMedium): Deleted. No more medium.
474
475         * bmalloc/Page.h:
476         (bmalloc::Page::sizeClass):
477         (bmalloc::Page::setSizeClass):
478         (bmalloc::Page::hasFreeLines):
479         (bmalloc::Page::setHasFreeLines): Add the free lines bit. You get better
480         codegen if you make it the low bit, since ref / deref can then add / sub
481         2. So do that.
482
483         * bmalloc/Sizes.h:
484         (bmalloc::Sizes::sizeClass): Expand the small size class to include the
485         medium size class.
486
487         * bmalloc/SuperChunk.h:
488         (bmalloc::SuperChunk::SuperChunk):
489         (bmalloc::SuperChunk::smallChunk):
490         (bmalloc::SuperChunk::largeChunk):
491         (bmalloc::SuperChunk::mediumChunk): Deleted. No more medium.
492
493         * bmalloc/VMHeap.cpp:
494         (bmalloc::VMHeap::grow):
495         * bmalloc/VMHeap.h:
496         (bmalloc::VMHeap::allocateSmallPage): Set the has free lines bit before
497         returning a Page to the Heap since this is the correct default state
498         when we first allocate a page.
499
500         (bmalloc::VMHeap::allocateMediumPage): Deleted.
501         (bmalloc::VMHeap::deallocateMediumPage): Deleted.
502
503 2016-02-19  Michael Saboff  <msaboff@apple.com>
504
505         bmalloc: Unify VMHeap and Heap LargeObjects free lists to reduce fragmentation
506         https://bugs.webkit.org/show_bug.cgi?id=154192
507
508         Reviewed by Geoffrey Garen.
509
510         Change the operation of Heap and VMHeap LargeObject free lists.
511         Renamed Owner to VMState to track the state of each LargeObject.
512             Physical - The pages have been allocated.
513             Virtual - The pages have not been allocated.
514             Mixed - The object contains a mixture of Physical and Virtual pages.
515         VMState uses one bit each for Physical and Virtual to simplify merging states
516         when merging two adjacent blocks.  This change enforces the rule that objects in
517         the Heap free list must have have the Physical bit set in their VMState while objects
518         in the VMHeap free list must have the Physical bit clear.  Thie means that the Heap
519         can have LargeObjects in Physical or Mixed VMState, but the VMHeap's free list can
520         only contain Virtual LargeObjects.
521         
522         In both Heap::allocateLarge(), we now allocate physical pages if the LargeObject we
523         pull from the free list has any Virtual pages before we possilby split the 
524         object.  When we merge objects, the result might be made up of Mixed page allocations.
525         When allocating a Mixed LargeObject, we need to allocate memory for them as well.
526         The scavenger deallocates both Physical and Mixed LargeObjects, placing them back into
527         the VMHeap's free list.
528
529         When we allocate or deallocate Mixed LargeObjects, there are pages that within these
530         objects that will be redundantly modified.  It would require additional metadata to
531         eliminate this redundancy.
532
533         * bmalloc.xcodeproj/project.pbxproj:
534         * bmalloc/BoundaryTag.h:
535         (bmalloc::BoundaryTag::vmState): New helper.
536         (bmalloc::BoundaryTag::setVMState): New helper.
537         (bmalloc::BoundaryTag::owner): Deleted.
538         (bmalloc::BoundaryTag::setOwner): Deleted.
539         * bmalloc/Heap.h:
540         (bmalloc::Heap::splitAndAllocate): New helpers.
541         * bmalloc/LargeObject.h:
542         (bmalloc::LargeObject::vmState): New helper.
543         (bmalloc::LargeObject::setVMState): New helper.
544
545         * bmalloc/Heap.cpp:
546         (bmalloc::Heap::splitAndAllocate): New helpers.
547         (bmalloc::Heap::allocateLarge): 
548         (bmalloc::Heap::deallocatePhysicalPages): Refactored from VMHeap::deallocateLargeObjectMemory.
549
550         * bmalloc/FreeList.cpp:
551         (bmalloc::FreeList::takeGreedy):
552         (bmalloc::FreeList::take):
553         (bmalloc::FreeList::removeInvalidAndDuplicateEntries):
554         * bmalloc/FreeList.h:
555         (bmalloc::FreeList::FreeList):
556         (bmalloc::FreeList::push):
557         * bmalloc/Heap.cpp:
558         (bmalloc::Heap::Heap):
559         (bmalloc::Heap::scavengeLargeObjects):
560         * bmalloc/LargeObject.h:
561         (bmalloc::LargeObject::isValidAndFree):
562         (bmalloc::LargeObject::validateSelf):
563         * bmalloc/SegregatedFreeList.cpp:
564         (bmalloc::SegregatedFreeList::SegregatedFreeList): Changed to initialize our required Physical state.
565         * bmalloc/SegregatedFreeList.h:
566         (bmalloc::SegregatedFreeList::SegregatedFreeList):
567         (bmalloc::SegregatedFreeList::insert):
568         (bmalloc::SegregatedFreeList::takeGreedy):
569         (bmalloc::SegregatedFreeList::take):
570         Replaced Owner parameters and checks with VMState::HasPhysical.
571
572         * bmalloc/LargeObject.h:
573         (bmalloc::LargeObject::prevCanMerge): Removed owner from tests.
574         (bmalloc::LargeObject::nextCanMerge): Removed owner from tests.
575         (bmalloc::LargeObject::merge): Removed owner from tests.  Updated to merge VMStates andset the
576         VMState after the merge.
577
578         * bmalloc/LargeObject.h:
579         (bmalloc::LargeObject::owner): Deleted.
580         (bmalloc::LargeObject::setOwner): Deleted.
581
582         * bmalloc/Owner.h: Removed.
583
584         * bmalloc/VMAllocate.h:
585         (bmalloc::vmAllocatePhysicalPagesSloppy): Changed to round begin down to eliminate the left to right
586         allocation constraint.
587
588         * bmalloc/VMHeap.cpp:
589         (bmalloc::VMHeap::grow): Large space managed like small or medium as a vector of LargeChunks.
590         (bmalloc::VMHeap::VMHeap): Changed to initialize our required Physical state.
591
592         * bmalloc/VMHeap.h:
593         (bmalloc::VMHeap::allocateLargeObject): These no longer allocate memory.
594         (bmalloc::VMHeap::deallocateLargeObject): Removed setOwner.  Now we set the VMState after any merges.
595
596         * bmalloc/VMState.h: Copied from Source/bmalloc/bmalloc/Owner.h.
597         (bmalloc::VMState::VMState):
598         (bmalloc::VMState::hasPhysical):
599         (bmalloc::VMState::hasVirtual):
600         (bmalloc::VMState::merge):
601         (bmalloc::VMState::operator ==):
602         (bmalloc::VMState::operator unsigned):
603         New class with various helpers.
604
605 2016-02-12  Michael Saboff  <msaboff@apple.com>
606
607         BASSERTs added in r196421 are causing debug test failures
608         https://bugs.webkit.org/show_bug.cgi?id=154113
609
610         Reviewed by Geoffrey Garen.
611
612         In VMHeap::deallocateLargeObject(), we drop the lock to deallocate the physical pages.
613         If the scavenger thread is running at the same time a synchronous call to scavenge()
614         comes in, we could call VMHeap::deallocateLargeObject() for an adjacent object while the
615         lock in the other thread is dropped.  We fix this by checking for adjacent objects we
616         can merge with and loop if we have one.
617
618         * bmalloc/FreeList.h:
619         (bmalloc::FreeList::push): Added BASSERT to catch adding unmerged free objects
620         * bmalloc/Heap.cpp:
621         (bmalloc::Heap::allocateLarge): Changed to use nextCanMerge().
622         * bmalloc/LargeObject.h:
623         (bmalloc::LargeObject::prevCanMerge): Repurposed prevIsAllocated.
624         (bmalloc::LargeObject::nextCanMerge): Repurposed nextIsAllocated.
625         (bmalloc::LargeObject::prevIsAllocated): Deleted.
626         (bmalloc::LargeObject::nextIsAllocated): Deleted.
627         * bmalloc/VMHeap.h:
628         (bmalloc::VMHeap::allocateLargeObject): Moved adding the extra object back to the free list
629         to after we set the object we'll return as being allocated.
630         (bmalloc::VMHeap::deallocateLargeObject):
631
632 2016-02-12  Mark Lam  <mark.lam@apple.com>
633
634         Make BCRASH() use breakpoint traps too for non-debug OS(DARWIN).
635         https://bugs.webkit.org/show_bug.cgi?id=154184
636
637         Reviewed by Saam Barati.
638
639         This makes it behave consistently with WTFCrash().
640
641         * bmalloc/BAssert.h:
642         * bmalloc/BPlatform.h:
643
644 2016-02-11  Michael Saboff  <msaboff@apple.com>
645
646         Unreviewed build fix after r196421.
647
648         Removed BASSERTs that are firing to eliminate Debug build crashes.  I'll debug locally and
649         enable or alter after the issue is understood.
650
651         * bmalloc/LargeObject.h:
652         (bmalloc::LargeObject::merge): Removed BASSERTs that are firing.
653
654 2016-02-11  Michael Saboff  <msaboff@apple.com>
655
656         bmalloc: large aligned allocations will put 1 or 2 free object on free list without merging with free neighbors
657         https://bugs.webkit.org/show_bug.cgi?id=154091
658
659         Reviewed by Geoffrey Garen.
660
661         If we split off any unused free object in the aligned version of Heap::allocateLarge(), we merge them with
662         free neighbors before putting them back on the free list.  Added helpers to verify that when we
663         add LargeObjects to the free list their neighbors are allocated.
664
665         * bmalloc/Heap.cpp:
666         (bmalloc::Heap::allocateLarge): Deleted private helper version and rolled it into the two the
667         two public versions of allocateLarge().
668         * bmalloc/Heap.h:
669         * bmalloc/LargeObject.h:
670         (bmalloc::LargeObject::prevIsAllocated): New helper.
671         (bmalloc::LargeObject::nextIsAllocated): New helper.
672         (bmalloc::LargeObject::merge): Check that the merge object has allocated neighbors.
673
674 2016-02-05  Saam barati  <sbarati@apple.com>
675
676         bmalloc: largeMax calculation is wrong on iOS
677         https://bugs.webkit.org/show_bug.cgi?id=153923
678
679         Reviewed by Mark Lam.
680
681         Our number for largeMax was larger than what we had
682         space to actually allocate inside the LargeChunk. This made 
683         it so that we would allocate a large object for something
684         that really should be extra large. Previously:
685         largeMax + sizeof(LargeChunk) > 1MB
686         which meant that when we would grow() to accommodate an allocation
687         of a particular size inside a LargeObject despite the fact that
688         the allocation size would be too large to actually fit in the LargeObject.
689         This would manifest when we had an allocation size in the range:
690         1MB - sizeof(LargeChunk) < allocation size < largeMax
691
692         We fix this bug by being precise in our calculation of largeMax
693         instead of just assuming largeChunkSize * 99/100 is enough
694         space for the metadata.
695
696         * bmalloc/LargeChunk.h:
697         (bmalloc::LargeChunk::get):
698         * bmalloc/Sizes.h:
699
700 2016-01-31  Dan Bernstein  <mitz@apple.com>
701
702         [Cocoa] Remove unused definition of HAVE_HEADER_DETECTION_H
703         https://bugs.webkit.org/show_bug.cgi?id=153729
704
705         Reviewed by Sam Weinig.
706
707         After r141700, HAVE_HEADER_DETECTION_H is no longer used.
708
709         * Configurations/Base.xcconfig:
710
711 2015-12-19  Dan Bernstein  <mitz@apple.com>
712
713         [Mac] WebKit contains dead source code for OS X Mavericks and earlier
714         https://bugs.webkit.org/show_bug.cgi?id=152462
715
716         Reviewed by Alexey Proskuryakov.
717
718         * Configurations/DebugRelease.xcconfig: Removed definition of MACOSX_DEPLOYMENT_TARGET for
719           OS X 10.9.
720
721 2015-12-03  Anders Carlsson  <andersca@apple.com>
722
723         Remove Objective-C GC support
724         https://bugs.webkit.org/show_bug.cgi?id=151819
725         rdar://problem/23746991
726
727         Reviewed by Dan Bernstein.
728
729         * Configurations/Base.xcconfig:
730
731 2015-12-03  Michael Saboff  <msaboff@apple.com>
732
733         bmalloc: extra large allocations could be more efficient
734         https://bugs.webkit.org/show_bug.cgi?id=151817
735
736         Reviewed by Geoffrey Garen.
737
738         Reduced the super chunk size from 4MB to 2MB.
739
740         Added path to reallocate() of an extra large object to see if we can extend the allocation.
741
742         * bmalloc/Allocator.cpp:
743         (bmalloc::Allocator::reallocate):
744         * bmalloc/SegregatedFreeList.h:
745         * bmalloc/Sizes.h:
746         * bmalloc/VMAllocate.h:
747         (bmalloc::tryVMAllocate):
748         (bmalloc::tryVMExtend):
749         (bmalloc::vmAllocate):
750
751 2015-11-11  Akos Kiss  <akiss@inf.u-szeged.hu>
752
753         bmalloc: Add libdl dependency
754         https://bugs.webkit.org/show_bug.cgi?id=151140
755
756         Reviewed by Csaba Osztrogonác.
757
758         Make sure that the linker links libdl and finds the references to
759         dlopen, dlsym and dlclose in Environment.cpp.
760
761         * CMakeLists.txt:
762
763 2015-11-02  Andy Estes  <aestes@apple.com>
764
765         [Cocoa] Add tvOS and watchOS to SUPPORTED_PLATFORMS
766         https://bugs.webkit.org/show_bug.cgi?id=150819
767
768         Reviewed by Dan Bernstein.
769
770         This tells Xcode to include these platforms in its Devices dropdown, making it possible to build in the IDE.
771
772         * Configurations/Base.xcconfig:
773
774 2015-11-01  Philip Chimento  <philip.chimento@gmail.com>
775
776         [GTK] Fix combinations of PLATFORM(GTK) and OS(DARWIN)
777         https://bugs.webkit.org/show_bug.cgi?id=144560
778
779         Reviewed by Darin Adler.
780
781         * PlatformGTK.cmake: Added. This adds Zone.cpp to the PlatformGTK
782         build, on Darwin only. Since there was previously nothing for the
783         build system to do that was specific to the GTK platform in
784         bmalloc, we need to create this file.
785
786 2015-10-29  Geoffrey Garen  <ggaren@apple.com>
787
788         bmalloc: AsyncTask should handle destruction
789         https://bugs.webkit.org/show_bug.cgi?id=150648
790
791         Reviewed by Mark Lam.
792
793         So we can use it in more places.
794
795         * bmalloc/AsyncTask.h: Use std::thread instead of pthread because it
796         should be more portable.
797
798         (bmalloc::Function>::AsyncTask): Renamed Signaled to RunRequested for
799         clarity. Added an ExitRequested state.
800
801         (bmalloc::Function>::~AsyncTask): Wait for our child thread to exit
802         before destroying ourselves because our child thread will modify our
803         data (and might modify our client's data). Note that we only need to
804         wait for the last child thread since any prior child thread, having
805         reached the Exited condition, is guaranteed not to read or write any
806         data.
807
808         (bmalloc::Function>::run):
809         (bmalloc::Function>::runSlowCase): Updated for interface changes. Also
810         changed to use our WebKit style for condition signal: Hold the lock
811         during the signal and always notify all. Technically, neither is necessary,
812         but it is easier to understand the code this way, and harder to make
813         mistakes.
814
815         (bmalloc::Function>::threadEntryPoint):
816         (bmalloc::Function>::threadRunLoop): Handle the new ExitRequested state.
817         Technically, this state has no meaningful difference from the Exited
818         state, but it is nice to be explicit.
819
820         (bmalloc::Function>::join): Deleted.
821         (bmalloc::Function>::pthreadEntryPoint): Deleted.
822         (bmalloc::Function>::entryPoint): Deleted.
823
824 2015-10-15  Geoffrey Garen  <ggaren@apple.com>
825
826         bmalloc: per-thread cache data structure should be smaller
827         https://bugs.webkit.org/show_bug.cgi?id=150218
828
829         Reviewed by Andreas Kling.
830
831         Reduce the number of entries in the range cache because it's really
832         big, and the bigness only helps in cases of serious fragmentation, and
833         it only saves us a little bit of lock acquisition time.
834
835         * bmalloc/Allocator.cpp:
836         (bmalloc::Allocator::scavenge):
837         (bmalloc::Allocator::refillAllocatorSlowCase):
838         (bmalloc::Allocator::refillAllocator):
839         (bmalloc::Allocator::allocateLarge):
840         (bmalloc::Allocator::allocateSlowCase):
841         (bmalloc::Allocator::allocateBumpRangeSlowCase): Deleted.
842         (bmalloc::Allocator::allocateBumpRange): Deleted.
843         * bmalloc/Allocator.h: Pass through the empty allocator and the range
844         cache when refilling, and refill both. Otherwise, we always immediately
845         pop the last item in the range cache, wasting that slot of capacity.
846
847         * bmalloc/Heap.cpp:
848         (bmalloc::Heap::allocateSmallBumpRanges):
849         (bmalloc::Heap::allocateMediumBumpRanges): Account for the fact that
850         the range cache is no longer big enough to guarantee that it can hold
851         all the ranges in a page.
852
853         (bmalloc::Heap::refillSmallBumpRangeCache): Deleted.
854         (bmalloc::Heap::refillMediumBumpRangeCache): Deleted.
855
856         * bmalloc/Heap.h: Move VMHeap to the end of the object because it
857         contains a lot of unused / wasted space, and we want to pack our data
858         together in memory.
859
860         * bmalloc/Sizes.h: Make the range cache smaller.
861
862 2015-10-13  Chris Dumez  <cdumez@apple.com>
863
864         Avoid useless copies in range-loops that are using 'auto'
865         https://bugs.webkit.org/show_bug.cgi?id=150091
866
867         Reviewed by Sam Weinig.
868
869         Avoid useless copies in range-loops that are using 'auto'. Also use
870         'auto*' instead of 'auto' when range values are pointers for clarity.
871
872         * bmalloc/Deallocator.cpp:
873         (bmalloc::Deallocator::processObjectLog):
874
875 2015-10-12  Geoffrey Garen  <ggaren@apple.com>
876
877         bmalloc: Don't ASSERT that all syscalls succeed
878         https://bugs.webkit.org/show_bug.cgi?id=150047
879         <rdar://problem/22649531>
880
881         Reviewed by Mark Lam.
882
883         madvise can fail due to VM behaviors outside of our control:
884         copy-on-write, fork, mprotect, and other stuff.
885
886         Older darwin kernels sometimes return this error value, and new kernels
887         might again in future.
888
889         We haven't gained much from this ASSERT so far, so let's remove it.
890
891         Perhaps in future we can come up with a scheme that makes madvise
892         never fail, or that responds to failure.
893
894         * bmalloc/Syscall.h:
895
896 2015-10-10  Dan Bernstein  <mitz@apple.com>
897
898         [iOS] Remove project support for iOS 8
899         https://bugs.webkit.org/show_bug.cgi?id=149993
900
901         Reviewed by Alexey Proskuryakov.
902
903         * Configurations/Base.xcconfig:
904         * Configurations/bmalloc.xcconfig:
905         * Configurations/mbmalloc.xcconfig:
906
907 2015-08-31  Michael Catanzaro  <mcatanzaro@igalia.com>
908
909         Implement bmalloc::isASanEnabled for generic Unix
910         https://bugs.webkit.org/show_bug.cgi?id=148623
911
912         Reviewed by Geoffrey Garen.
913
914         * bmalloc/BPlatform.h: Add BOS_UNIX to detect whether the OS is a Unix.
915         * bmalloc/Environment.cpp:
916         (bmalloc::isASanEnabled): Implement a runtime check that should work on any Unix.
917
918 2015-08-19  Geoffrey Garen  <ggaren@apple.com>
919
920         Crash @ bmalloc::Environment::computeIsBmallocEnabled
921         https://bugs.webkit.org/show_bug.cgi?id=148183
922
923         Reviewed by NOBODY Michael Saboff.
924
925         CrashTracer says we have some crashes beneath computeIsBmallocEnabled
926         dereferencing null in strstr. We null check getenv but not
927         _dyld_get_image_name, so deduction indicates that _dyld_get_image_name
928         must be returning null. _dyld_get_image_name isn't really documented,
929         so let's assume it can return null.
930
931         * bmalloc/Environment.cpp:
932         (bmalloc::isASanEnabled): Check _dyld_get_image_name's return value for
933         null because we can't prove it won't be null.
934
935 2015-07-24  Geoffrey Garen  <ggaren@apple.com>
936
937         vmmap crash at JavaScriptCore: 0x31cd12f6 (the JavaScript malloc zone enumerator)
938         https://bugs.webkit.org/show_bug.cgi?id=147274
939
940         Reviewed by Anders Carlsson.
941
942         It's not really clear why vmmap sometimes fails to read the target
943         process, but we can avoid a crash when it does. This is useful because
944         you'll still get all the non-bmalloc data out of the target process,
945         and bmalloc might not even be relevant to your investigation.
946
947         * bmalloc/Zone.cpp:
948         (bmalloc::remoteRead): Check for failure.
949
950 2015-07-24  Geoffrey Garen  <ggaren@apple.com>
951
952         JavaScriptCore bmalloc should not register its malloc zone more than once
953         https://bugs.webkit.org/show_bug.cgi?id=147273
954
955         Reviewed by Andreas Kling.
956
957         This was a goof: The Zone constructor, by virtue of running automatically,
958         was registering a Zone inside the analysis process.
959
960         * bmalloc/Zone.cpp:
961         (bmalloc::remoteRead): Clarify that the pointer is remote.
962
963         (bmalloc::enumerator):
964         (bmalloc::Zone::Zone):
965         * bmalloc/Zone.h: Separate the normal constructor and the remote constructor.
966         The remote constructor skips zone registration since its goal is not
967         to register a zone in the current process or do any allocation but rather
968         to mirror the bytes of the zone from the target process.
969
970 2015-07-23  Geoffrey Garen  <ggaren@apple.com>
971
972         bmalloc: Shrink the super chunk size (again)
973         https://bugs.webkit.org/show_bug.cgi?id=147240
974
975         Reviewed by Andreas Kling.
976
977         Shrinking to 8MB reduced VM exhaustion crashes but did not eliminate them.
978         Let's try 4MB.
979
980         (My previous comment was that the maximum fast object was 2MB. But it
981         was 4MB! Now it's 2MB for realsies.)
982
983         * bmalloc/Sizes.h:
984
985 2015-07-03  Dan Bernstein  <mitz@apple.com>
986
987         [Xcode] Update some build settings as recommended by Xcode 7
988         https://bugs.webkit.org/show_bug.cgi?id=146597
989
990         Reviewed by Sam Weinig.
991
992         * Configurations/Base.xcconfig: Enabled CLANG_WARN_UNREACHABLE_CODE, GCC_NO_COMMON_BLOCKS,
993         and ENABLE_STRICT_OBJC_MSGSEND. Removed GCC_MODEL_TUNING.
994
995         * bmalloc.xcodeproj/project.pbxproj: Updated LastUpgradeCheck.
996
997 2015-07-02  Geoffrey Garen  <ggaren@apple.com>
998
999         bmalloc: Shrink the super chunk size
1000         https://bugs.webkit.org/show_bug.cgi?id=146519
1001
1002         Reviewed by Andreas Kling.
1003
1004         We have lots of reports of crashing due to failed VM allocation on iOS.
1005         (This VM limit on iOS is usually 1GB-2GB, and has been as low as 256MB.)
1006
1007         Shrink the super chunk size in case fragmentation is the reason for
1008         VM allocation failure.
1009
1010         This has the downside that >= 2MB allocations will now be super slow,
1011         but they are also super rare (as in never on most websites), so this
1012         is probably an OK tradeoff.
1013
1014         * bmalloc/Sizes.h:
1015
1016 2015-07-01  Geoffrey Garen  <ggaren@apple.com>
1017
1018         bmalloc: realloc of an XLarge range can unmap adjacent VM ranges
1019         https://bugs.webkit.org/show_bug.cgi?id=146535
1020
1021         Reviewed by Anders Carlsson.
1022
1023         This bug causes a crash when running fast/css/large-list-of-rules-crash.html
1024         with the fix applied for https://bugs.webkit.org/show_bug.cgi?id=146519.
1025
1026         * bmalloc/Allocator.cpp:
1027         (bmalloc::Allocator::reallocate): Start at object + newSize since starting
1028         at object + oldSize means deleting the adjacent VM range.
1029
1030 2015-05-26  Geoffrey Garen  <ggaren@apple.com>
1031
1032         Integer overflow in XLarge allocation (due to unchecked roundUpToMultipleOf)
1033         https://bugs.webkit.org/show_bug.cgi?id=145385
1034
1035         Reviewed by Andreas Kling.
1036
1037         Added some checking to verify that round-up operations will not overflow
1038         a size_t.
1039
1040         The simplest way to do this was to introduce a notion of xLargeMax, like
1041         we have for smallMax, mediumMax, and largeMax. It's a bit surprising at
1042         first to think that there is an xLargeMax, since xLarge is what we use
1043         to handle the biggest things. But computers have limits, so it makes sense.
1044
1045         FWIW, TCMalloc used to have an xLargeMax too, which it called kMaxValidPages.
1046
1047         No test because this bug was found by code inspection and I don't know
1048         of a practical way to convince WebKit to make an allocation this large.
1049
1050         * bmalloc/Allocator.cpp:
1051         (bmalloc::Allocator::tryAllocate):
1052         (bmalloc::Allocator::allocate):
1053         (bmalloc::Allocator::reallocate):
1054         (bmalloc::Allocator::allocateSlowCase): Check against xLargeMax to avoid
1055         overflow when rounding up.
1056
1057         * bmalloc/BAssert.h: Added support for explicit crashing.
1058
1059         * bmalloc/Sizes.h:
1060
1061 2015-05-26  Dan Bernstein  <mitz@apple.com>
1062
1063         <rdar://problem/21104551> Update build settings
1064
1065         Reviewed by Anders Carlsson.
1066
1067         * Configurations/DebugRelease.xcconfig:
1068
1069 2015-05-23  Dan Bernstein  <mitz@apple.com>
1070
1071         Remove unused definitions of WEBKIT_VERSION_MIN_REQUIRED
1072         https://bugs.webkit.org/show_bug.cgi?id=145345
1073
1074         Reviewed by Sam Weinig.
1075
1076         * Configurations/Base.xcconfig: Also changed to use $(inherited).
1077
1078 2015-05-07  Geoffrey Garen  <ggaren@apple.com>
1079
1080         Release assert in com.apple.WebKit.WebContent under JavaScriptCore: JSC::JSONProtoFuncStringify
1081         https://bugs.webkit.org/show_bug.cgi?id=144758
1082
1083         Reviewed by Andreas Kling.
1084
1085         This was an out-of-memory error when trying to shrink a string builder.
1086         bmalloc was missing the optimization that allowed realloc() to shrink
1087         without copying. So, let's add it.
1088
1089         * bmalloc/Allocator.cpp:
1090         (bmalloc::Allocator::reallocate): Added Large and XLarge cases for
1091         shrinking without copying. This isn't possible for small and medium
1092         objects, and probably not very profitable, either.
1093
1094         * bmalloc/Heap.cpp:
1095         (bmalloc::Heap::findXLarge):
1096         (bmalloc::Heap::deallocateXLarge):
1097         * bmalloc/Heap.h: Refactored this code to return a reference to an
1098         XLarge range. This makes the code reusable, and also makes it easier
1099         for realloc() to update metadata.
1100
1101         * bmalloc/LargeObject.h:
1102         (bmalloc::LargeObject::split): Allow allocated objects to split because
1103         that's what realloc() wants to do, and there's nothing intrinsically
1104         wrong with it.
1105
1106 2015-05-07  Dan Bernstein  <mitz@apple.com>
1107
1108         <rdar://problem/19317140> [Xcode] Remove usage of AspenFamily.xcconfig in Source/
1109         https://bugs.webkit.org/show_bug.cgi?id=144727
1110
1111         Reviewed by Darin Adler.
1112
1113         * Configurations/Base.xcconfig: Dont’s include AspenFamily.xcconfig, and define
1114         INSTALL_PATH_PREFIX for the iOS 8.x Simulator.
1115
1116 2015-04-01  Alex Christensen  <achristensen@webkit.org>
1117
1118         Progress towards CMake on Windows and Mac.
1119         https://bugs.webkit.org/show_bug.cgi?id=143293
1120
1121         Reviewed by Filip Pizlo.
1122
1123         * bmalloc/BAssert.h:
1124         Removed ellipses from macros to appease Visual Studio.
1125
1126 2015-03-13  Alex Christensen  <achristensen@webkit.org>
1127
1128         Progress towards CMake on Mac.
1129         https://bugs.webkit.org/show_bug.cgi?id=142680
1130
1131         Reviewed by Gyuyoung Kim.
1132
1133         * CMakeLists.txt:
1134         * PlatformMac.cmake:
1135         Added Zone.cpp to Mac CMake builds.
1136
1137 2015-03-12  Geoffrey Garen  <ggaren@apple.com>
1138
1139         Assertion failure in bmalloc::LargeObject::validateSelf on Mavericks Debug layout test bot
1140         https://bugs.webkit.org/show_bug.cgi?id=142642
1141
1142         Reviewed by Michael Saboff.
1143
1144         The typical backtrace to this crash shows the main thread trying to
1145         realloc a large string while a DFG compiler thread tries to
1146         free a large vector buffer.
1147
1148         I believe that this is a race condition -- at least in debug builds --
1149         since the main thread will try to validate its object's neighbors
1150         without holding a lock, even though those neighbors might be in the
1151         midst of changing.
1152
1153         In general, there may be sneaky times when it is valid to look at an
1154         object's metadata without holding the heap lock, but it is best not to
1155         do so unless we have a really really good reason to.
1156
1157         * bmalloc/Allocator.cpp:
1158         (bmalloc::Allocator::reallocate): Take a lock before reading the metadata
1159         for this object, since we generally require any access to shared heap
1160         metadata to take a lock.
1161
1162 2015-03-10  Geoffrey Garen  <ggaren@apple.com>
1163
1164         bmalloc: tryFastMalloc shouldn't crash
1165         https://bugs.webkit.org/show_bug.cgi?id=142443
1166
1167         Reviewed by Sam Weinig.
1168
1169         Rolling back in r181307 with a check for whether bmalloc is enabled, to
1170         avoid crashes when running with ASan and GuardMalloc.
1171
1172         * bmalloc/Allocator.cpp:
1173         (bmalloc::Allocator::tryAllocate):
1174         * bmalloc/Allocator.h:
1175         * bmalloc/Cache.cpp:
1176         (bmalloc::Cache::tryAllocateSlowCaseNullCache):
1177         * bmalloc/Cache.h:
1178         (bmalloc::Cache::tryAllocate):
1179         * bmalloc/Heap.cpp:
1180         (bmalloc::Heap::allocateXLarge):
1181         (bmalloc::Heap::tryAllocateXLarge):
1182         * bmalloc/Heap.h:
1183         * bmalloc/VMAllocate.h:
1184         (bmalloc::tryVMAllocate):
1185         (bmalloc::vmAllocate):
1186         * bmalloc/bmalloc.h:
1187         (bmalloc::api::tryMalloc):
1188         (bmalloc::api::realloc):
1189         (bmalloc::api::free):
1190
1191 2015-03-09  Commit Queue  <commit-queue@webkit.org>
1192
1193         Unreviewed, rolling out r181307.
1194         https://bugs.webkit.org/show_bug.cgi?id=142525
1195
1196         Broke ASan tests (Requested by ap on #webkit).
1197
1198         Reverted changeset:
1199
1200         "bmalloc: tryFastMalloc shouldn't crash"
1201         https://bugs.webkit.org/show_bug.cgi?id=142443
1202         http://trac.webkit.org/changeset/181307
1203
1204 2015-03-09  Geoffrey Garen  <ggaren@apple.com>
1205
1206         bmalloc: tryFastMalloc shouldn't crash
1207         https://bugs.webkit.org/show_bug.cgi?id=142443
1208
1209         Reviewed by Darin Adler.
1210
1211         Added support for tryMalloc.
1212
1213         We assume that non-x-large allocations always succeed, and we crash
1214         otherwise, since normal allocation failure will just cause the next
1215         non-try allocation or internal metadata allocation to fail, and it's
1216         hard and not really useful to keep limping along after that. But
1217         extra-large allocations can meaningfully fail, and we can recover.
1218
1219         * bmalloc/Heap.cpp:
1220         (bmalloc::Heap::allocateXLarge):
1221         (bmalloc::Heap::tryAllocateXLarge):
1222         * bmalloc/Heap.h: Added support for non-crashy x-large allocation.
1223
1224         * bmalloc/VMAllocate.h:
1225         (bmalloc::tryVMAllocate):
1226         (bmalloc::vmAllocate): Added support for non-crashy VM allocation.
1227
1228         * bmalloc/bmalloc.h:
1229         (bmalloc::api::tryMalloc):
1230         (bmalloc::api::realloc):
1231         (bmalloc::api::free): Tried to clarify our behavior with some comments.
1232         Unfortunately, calling what we do "malloc" is still not quite right, since
1233         malloc returns null on failure and we don't.
1234
1235 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
1236
1237         bmalloc: Don't branch when setting the owner of a large object
1238         https://bugs.webkit.org/show_bug.cgi?id=142241
1239
1240         Reviewed by Andreas Kling.
1241
1242         * bmalloc/BoundaryTag.h:
1243         (bmalloc::BoundaryTag::owner):
1244         (bmalloc::BoundaryTag::setOwner):
1245
1246 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
1247
1248         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
1249         https://bugs.webkit.org/show_bug.cgi?id=141802
1250
1251         Reviewed by Andreas Kling.
1252
1253         Re-enabled this feature on iOS, now that the iOS crash should be fixed.
1254
1255         * bmalloc/VMHeap.cpp:
1256         (bmalloc::VMHeap::grow):
1257         * bmalloc/VMHeap.h:
1258
1259 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
1260
1261         bmalloc: Added missing features to the malloc zone introspection API
1262         https://bugs.webkit.org/show_bug.cgi?id=142235
1263
1264         Reviewed by Andreas Kling.
1265
1266         This should fix the crash we saw on the iOS PLT bot
1267         (c.f. http://trac.webkit.org/changeset/180604).
1268
1269         * bmalloc/Zone.cpp:
1270         (bmalloc::good_size):
1271         (bmalloc::check):
1272         (bmalloc::print):
1273         (bmalloc::log):
1274         (bmalloc::force_lock):
1275         (bmalloc::force_unlock):
1276         (bmalloc::statistics):
1277         (bmalloc::size):
1278         (bmalloc::enumerator): Provide all of these functions since they are called
1279         indiscriminately on all zones.
1280
1281         (bmalloc::Zone::Zone):
1282         (bmalloc::Zone::size): Deleted.
1283         (bmalloc::Zone::enumerator): Deleted. Moved these functions out of the
1284         Zone class since they can stand alone.
1285
1286         * bmalloc/Zone.h:
1287
1288 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
1289
1290         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
1291         https://bugs.webkit.org/show_bug.cgi?id=141802
1292
1293         Reviewed by Andreas Kling.
1294
1295         Rolling back in but disabled on iOS until I can debug why the iOS PLT crashes.
1296
1297         * bmalloc/VMHeap.cpp:
1298         (bmalloc::VMHeap::grow):
1299         * bmalloc/VMHeap.h:
1300         * bmalloc/Zone.cpp:
1301         (bmalloc::Zone::size):
1302         (bmalloc::Zone::Zone):
1303         * bmalloc/Zone.h:
1304
1305 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
1306
1307         bmalloc: Miscellaneous cleanup
1308         https://bugs.webkit.org/show_bug.cgi?id=142231
1309
1310         Reviewed by Andreas Kling.
1311
1312         No performance change -- maybe a tiny reduction in memory use.
1313
1314         * bmalloc/Heap.cpp: Moved the sleep function into StaticMutex, since
1315         it's a helper for working with mutexes.
1316
1317         (bmalloc::Heap::scavenge): Make sure to wait before we start any
1318         scavenging, since individual scavenging functions now always scavenge
1319         at least one page before waiting themselves.
1320
1321         (bmalloc::Heap::scavengeSmallPages):
1322         (bmalloc::Heap::scavengeMediumPages):
1323         (bmalloc::Heap::scavengeLargeObjects): Use the new wait helper to
1324         simplify this code. Also, we now require our caller to wait until at
1325         least one deallocation is desirable. This simplifies our loop.
1326
1327         (bmalloc::Heap::allocateSmallPage):
1328         (bmalloc::Heap::allocateMediumPage):
1329         (bmalloc::Heap::allocateXLarge):
1330         (bmalloc::Heap::allocateLarge): Don't freak out any time the heap does
1331         an allocation. Only consider the heap to be growing if it actually needs
1332         to allocate new VM. This allows us to shrink the heap back down from a
1333         high water mark more reliably even if heap activity continues.
1334
1335         (bmalloc::sleep): Deleted.
1336         (bmalloc::Heap::scavengeLargeRanges): Renamed to match our use of
1337         "LargeObject".
1338
1339         * bmalloc/Heap.h:
1340
1341         * bmalloc/LargeObject.h:
1342         (bmalloc::LargeObject::operator bool): Added to simplify a while loop.
1343
1344         * bmalloc/StaticMutex.h:
1345         (bmalloc::sleep):
1346         (bmalloc::waitUntilFalse): New helper for waiting until a condition
1347         becomes reliably false.
1348
1349         * bmalloc/Vector.h:
1350         (bmalloc::Vector<T>::~Vector): Oops! Don't deallocate the null pointer.
1351         We don't actually run any Vector destructors, but an iteration of this
1352         patch did, and then crashed. So, let's fix that.
1353
1354 2015-03-02  Geoffrey Garen  <ggaren@apple.com>
1355
1356         bmalloc: Eagerly remove allocated objects from the free list
1357         https://bugs.webkit.org/show_bug.cgi?id=142194
1358
1359         Reviewed by Andreas Kling.
1360
1361         This reduces the pressure to garbage collect the free list.
1362
1363         Might be a 1% speedup on MallocBench.
1364
1365         * bmalloc/FreeList.cpp: Put this comment at the top of the file instead
1366         of repeating it inside of each function. Tried to clarify the details.
1367
1368         (bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
1369         file for consistency -- even though either direction works fine in this
1370         function.
1371
1372         (bmalloc::FreeList::take): Change to iterate from low to high so that we
1373         can maintain an index into the vector that is not disturbed even if we
1374         pop from the middle (which invalidates the last index in the vector).
1375
1376         Decrement i when popping from the middle to make sure that we don't
1377         skip the next item after popping.
1378
1379         (bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.
1380
1381 2015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
1382
1383         Fixed a typo in the previous commit.
1384
1385         * bmalloc/BoundaryTag.h:
1386         (bmalloc::BoundaryTag::setOwner):
1387
1388 2015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
1389
1390         EFL build fix after r180797.
1391
1392         * bmalloc/BoundaryTag.h:
1393         (bmalloc::BoundaryTag::owner):
1394         (bmalloc::BoundaryTag::setOwner):
1395
1396 2015-02-27  Geoffrey Garen  <ggaren@apple.com>
1397
1398         bmalloc: Pathological madvise churn on the free(malloc(x)) benchmark
1399         https://bugs.webkit.org/show_bug.cgi?id=142058
1400
1401         Reviewed by Andreas Kling.
1402
1403         The churn was caused by repeatedly splitting an object with physical
1404         pages from an object without, and then merging them back together again.
1405         The merge would conservatively forget that we had physical pages, forcing
1406         a new call to madvise on the next allocation.
1407
1408         This patch more strictly segregates objects in the heap from objects in
1409         the VM heap, with these changes:
1410
1411         (1) Objects in the heap are not allowed to merge with objects in the VM
1412         heap, and vice versa -- since that would erase our precise knowledge of
1413         which physical pages had been allocated.
1414
1415         (2) The VM heap is exclusively responsible for allocating and deallocating
1416         physical pages.
1417
1418         (3) The heap free list must consider entries for objects that are in the
1419         VM heap to be invalid, and vice versa. (This condition can arise
1420         because the free list does not eagerly remove items.)
1421
1422         With these changes, we can know that any valid object in the heap's free
1423         list already has physical pages, and does not need to call madvise.
1424
1425         Note that the VM heap -- as before -- might sometimes contain ranges
1426         or pieces of ranges that have physical pages, since we allow splitting
1427         of ranges at granularities smaller than the VM page size. These ranges
1428         can eventually merge with ranges in the heap during scavenging.
1429
1430         * bmalloc.xcodeproj/project.pbxproj:
1431
1432         * bmalloc/BoundaryTag.h:
1433         (bmalloc::BoundaryTag::owner):
1434         (bmalloc::BoundaryTag::setOwner):
1435         (bmalloc::BoundaryTag::initSentinel):
1436         (bmalloc::BoundaryTag::hasPhysicalPages): Deleted.
1437         (bmalloc::BoundaryTag::setHasPhysicalPages): Deleted. Replaced the concept
1438         of "has physical pages" with a bit indicating which heap owns the large
1439         object. This is a more precise concept, since the old bit was really a
1440         Yes / Maybe bit.
1441
1442         * bmalloc/Deallocator.cpp:
1443
1444         * bmalloc/FreeList.cpp: Adopt
1445         (bmalloc::FreeList::takeGreedy):
1446         (bmalloc::FreeList::take):
1447         (bmalloc::FreeList::removeInvalidAndDuplicateEntries):
1448         * bmalloc/FreeList.h:
1449         (bmalloc::FreeList::push): Added API for considering the owner when
1450         deciding if a free list entry is valid.
1451
1452         * bmalloc/Heap.cpp:
1453         (bmalloc::Heap::Heap): Adopt new API.
1454
1455         (bmalloc::Heap::scavengeLargeRanges): Scavenge all ranges with no minimum,
1456         since some ranges might be able to merge with ranges in the VM heap, and
1457         they won't be allowed to until we scavenge them.
1458
1459         (bmalloc::Heap::allocateSmallPage):
1460         (bmalloc::Heap::allocateMediumPage):
1461         (bmalloc::Heap::allocateLarge): New VM heap API makes this function
1462         simpler, since we always get back physical pages now.
1463
1464         * bmalloc/Heap.h:
1465         * bmalloc/LargeObject.h:
1466         (bmalloc::LargeObject::end):
1467         (bmalloc::LargeObject::owner):
1468         (bmalloc::LargeObject::setOwner):
1469         (bmalloc::LargeObject::isValidAndFree):
1470         (bmalloc::LargeObject::merge): Do not merge objects across heaps since
1471         that causes madvise churn.
1472         (bmalloc::LargeObject::validateSelf):
1473         (bmalloc::LargeObject::init):
1474         (bmalloc::LargeObject::hasPhysicalPages): Deleted.
1475         (bmalloc::LargeObject::setHasPhysicalPages): Deleted. Propogate the Owner API.
1476
1477         * bmalloc/Owner.h: Added.
1478
1479         * bmalloc/SegregatedFreeList.cpp:
1480         (bmalloc::SegregatedFreeList::SegregatedFreeList):
1481         (bmalloc::SegregatedFreeList::insert):
1482         (bmalloc::SegregatedFreeList::takeGreedy):
1483         (bmalloc::SegregatedFreeList::take):
1484         * bmalloc/SegregatedFreeList.h: Propogate the owner API.
1485
1486         * bmalloc/VMAllocate.h:
1487         (bmalloc::vmDeallocatePhysicalPagesSloppy):
1488         (bmalloc::vmAllocatePhysicalPagesSloppy): Clarified these functions and
1489         removed an edge case.
1490
1491         * bmalloc/VMHeap.cpp:
1492         (bmalloc::VMHeap::VMHeap):
1493         * bmalloc/VMHeap.h:
1494         (bmalloc::VMHeap::allocateSmallPage):
1495         (bmalloc::VMHeap::allocateMediumPage):
1496         (bmalloc::VMHeap::allocateLargeObject):
1497         (bmalloc::VMHeap::deallocateLargeObject): Be sure to give each object
1498         a new chance to merge, since it might have been prohibited from merging
1499         before by virtue of not being in the VM heap.
1500
1501         (bmalloc::VMHeap::allocateLargeRange): Deleted.
1502         (bmalloc::VMHeap::deallocateLargeRange): Deleted.
1503
1504 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
1505
1506         bmalloc: Large object free list can grow infinitely
1507         https://bugs.webkit.org/show_bug.cgi?id=142055
1508
1509         Reviewed by Andreas Kling.
1510
1511         By design, we don't eagerly remove large objects from the free list.
1512         This creates two simple pathologies:
1513
1514             (1) If you free and then allocate the same object repeatedly, it will
1515             duplicate itself in the free list repeatedly. Since it is never
1516             invalid at the time of allocation, it will never be removed.
1517
1518             (2) If you split and then merge the same object repeatedly, it will
1519             duplicate its split sibling in the free list repeatedly. If its
1520             sibling is in a separate free list size class, it will never be
1521             consulted at the time of allocation, so it will never be removed.
1522
1523         So, a simple "while (1) { free(malloc(x)); }" causes infinite memory
1524         use in the free list.
1525
1526         The solution in this patch is a simple helper to remove garbage from the
1527         free list if it grows too large. This pathology is not common, so the
1528         cost is OK.
1529
1530         Long-term, perhaps we should rethink the laziness of these free lists.
1531
1532         * bmalloc/BoundaryTag.h:
1533         (bmalloc::BoundaryTag::isMarked):
1534         (bmalloc::BoundaryTag::setMarked): New bit, used by free list GC.
1535
1536         * bmalloc/FreeList.cpp:
1537         (bmalloc::FreeList::removeInvalidAndDuplicateEntries): The GC algorithm.
1538
1539         * bmalloc/FreeList.h:
1540         (bmalloc::FreeList::FreeList):
1541         (bmalloc::FreeList::push): Invoke the GC if we're getting huge.
1542
1543         * bmalloc/LargeObject.h:
1544         (bmalloc::LargeObject::isMarked):
1545         (bmalloc::LargeObject::setMarked):
1546         (bmalloc::LargeObject::validateSelf): Expose the new bit.
1547
1548         * bmalloc/Sizes.h: New constant to control GC frequency.
1549
1550 2015-02-26  Csaba Osztrogonác  <ossy@webkit.org>
1551
1552         URTBF after r180693.
1553
1554         * CMakeLists.txt:
1555
1556 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
1557
1558         Try to fix the Mac build.
1559
1560         Unreviewed.
1561
1562         * bmalloc.xcodeproj/project.pbxproj: Make FreeList.h available.
1563
1564 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
1565
1566         bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
1567         https://bugs.webkit.org/show_bug.cgi?id=142049
1568
1569         Reviewed by Anders Carlsson.
1570
1571         Split out a FreeList class from SegregatedFreeList. This will make it
1572         easier to add behaviors on free list insertion and removal -- and it's
1573         probably how I should have designed things at the start.
1574
1575         Moved BoundaryTag::init into LargeObject, since all the related logic
1576         lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.
1577
1578         * bmalloc.xcodeproj/project.pbxproj:
1579         * bmalloc/BoundaryTagInlines.h: Removed.
1580         * bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
1581         (bmalloc::FreeList::takeGreedy):
1582         (bmalloc::FreeList::take):
1583         (bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
1584         (bmalloc::SegregatedFreeList::insert): Deleted.
1585         (bmalloc::SegregatedFreeList::takeGreedy): Deleted.
1586         (bmalloc::SegregatedFreeList::take): Deleted.
1587         * bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
1588         (bmalloc::FreeList::push):
1589         * bmalloc/LargeObject.h:
1590         (bmalloc::LargeObject::init):
1591         * bmalloc/SegregatedFreeList.cpp:
1592         (bmalloc::SegregatedFreeList::SegregatedFreeList):
1593         (bmalloc::SegregatedFreeList::insert):
1594         (bmalloc::SegregatedFreeList::takeGreedy):
1595         (bmalloc::SegregatedFreeList::take):
1596         * bmalloc/SegregatedFreeList.h:
1597         * bmalloc/Sizes.h:
1598         * bmalloc/VMHeap.cpp:
1599         (bmalloc::VMHeap::grow):
1600
1601 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
1602
1603         bmalloc: free up a bit in BoundaryTag
1604         https://bugs.webkit.org/show_bug.cgi?id=142048
1605
1606         Reviewed by Brady Eidson.
1607
1608         We were wasting a bit by accident, and I need one now.
1609
1610         * bmalloc/Algorithm.h:
1611         (bmalloc::rightShift): Deleted. Not needed, now that I've simplified
1612         the math.
1613
1614         * bmalloc/BoundaryTag.h: Since each boundary tag bucket is 1024 bytes
1615         long, the maximum offset into a bucket is 1023.
1616
1617         You need 5 bits to count up to 1024, but only 4 to count up to 1023.
1618         
1619         Math is hard.
1620
1621         (bmalloc::BoundaryTag::compactBegin): Switched to division because it
1622         is simpler, and easier to match up with our ASSERT. The compiler will
1623         turn division by constant power of two into a shift for us.
1624
1625         (bmalloc::BoundaryTag::setRange): Added an ASSERT for compactBegin
1626         because we do encode it, so we should ASSERT that encoding did not
1627         lose information.
1628
1629         * bmalloc/Sizes.h: Shifting is no longer used since we use division
1630         instead.
1631
1632 2015-02-24  Stephanie Lewis  <slewis@apple.com>
1633
1634         Rolling out http://trac.webkit.org/changeset/180430 as it causes the PLT to crash.
1635         <rdar://problem/19948015>
1636
1637         Unreviewed.
1638
1639         * bmalloc/VMHeap.cpp:
1640         (bmalloc::VMHeap::grow):
1641         * bmalloc/VMHeap.h:
1642         * bmalloc/Zone.cpp:
1643         (bmalloc::Zone::Zone):
1644         (bmalloc::Zone::size): Deleted.
1645         * bmalloc/Zone.h:
1646
1647 2015-02-24  Geoffrey Garen  <ggaren@apple.com>
1648
1649         bmalloc: Added a little more abstraction for large objects
1650         https://bugs.webkit.org/show_bug.cgi?id=141978
1651
1652         Reviewed by Sam Weinig.
1653
1654         Previously, each client needed to manage the boundary tags of
1655         a large object using free functions. This patch introduces a LargeObject
1656         class that does things a little more automatically.
1657
1658         * bmalloc.xcodeproj/project.pbxproj:
1659
1660         * bmalloc/Allocator.cpp:
1661         (bmalloc::Allocator::reallocate): Use the new LargeObject class.
1662
1663         * bmalloc/BeginTag.h:
1664         (bmalloc::BeginTag::isInFreeList): Deleted. Moved this logic into the
1665         LargeObject class.
1666
1667         * bmalloc/BoundaryTag.h:
1668         (bmalloc::BoundaryTag::isSentinel):
1669         (bmalloc::BoundaryTag::compactBegin):
1670         (bmalloc::BoundaryTag::setRange):
1671         (bmalloc::BoundaryTag::initSentinel): Added an explicit API for sentinels,
1672         which we used to create and test for implicitly.
1673
1674         * bmalloc/BoundaryTagInlines.h:
1675         (bmalloc::BoundaryTag::init):
1676         (bmalloc::validate): Deleted.
1677         (bmalloc::validatePrev): Deleted.
1678         (bmalloc::validateNext): Deleted.
1679         (bmalloc::BoundaryTag::mergeLeft): Deleted.
1680         (bmalloc::BoundaryTag::mergeRight): Deleted.
1681         (bmalloc::BoundaryTag::merge): Deleted.
1682         (bmalloc::BoundaryTag::deallocate): Deleted.
1683         (bmalloc::BoundaryTag::split): Deleted.
1684         (bmalloc::BoundaryTag::allocate): Deleted. Moved this logic into the
1685         LargeObject class.
1686
1687         * bmalloc/EndTag.h:
1688         (bmalloc::EndTag::init):
1689         (bmalloc::EndTag::operator=): Deleted. Re-reading this code, I found
1690         special behavior in the assignment operator to be a surprising API.
1691         So, I replaced the assignment operation with an explicit initializing
1692         function.
1693
1694         * bmalloc/Heap.cpp:
1695         (bmalloc::Heap::scavengeLargeRanges):
1696         (bmalloc::Heap::allocateXLarge):
1697         (bmalloc::Heap::findXLarge):
1698         (bmalloc::Heap::deallocateXLarge):
1699         (bmalloc::Heap::allocateLarge):
1700         (bmalloc::Heap::deallocateLarge):
1701         * bmalloc/Heap.h: No behavior changes here -- just adopting the
1702         LargeObject interface.
1703
1704         * bmalloc/LargeObject.h: Added.
1705         (bmalloc::LargeObject::operator!):
1706         (bmalloc::LargeObject::begin):
1707         (bmalloc::LargeObject::size):
1708         (bmalloc::LargeObject::range):
1709         (bmalloc::LargeObject::LargeObject):
1710         (bmalloc::LargeObject::setFree):
1711         (bmalloc::LargeObject::isFree):
1712         (bmalloc::LargeObject::hasPhysicalPages):
1713         (bmalloc::LargeObject::setHasPhysicalPages):
1714         (bmalloc::LargeObject::isValidAndFree):
1715         (bmalloc::LargeObject::merge):
1716         (bmalloc::LargeObject::split):
1717         (bmalloc::LargeObject::validateSelf):
1718         (bmalloc::LargeObject::validate): Moved this code into a class, out of
1719         BoundaryTag free functions.
1720
1721         New to the class are these features:
1722
1723             (1) Every reference to an object is validated upon creation and use.
1724
1725             (2) There's an explicit API for "This is a reference to an object
1726             that might be stale (the DoNotValidate API)".
1727
1728             (3) The begin and end tags are kept in sync automatically.
1729
1730         * bmalloc/SegregatedFreeList.cpp:
1731         (bmalloc::SegregatedFreeList::insert):
1732         (bmalloc::SegregatedFreeList::takeGreedy):
1733         (bmalloc::SegregatedFreeList::take):
1734         * bmalloc/SegregatedFreeList.h: Adopt the LargeObject interface.
1735
1736         * bmalloc/VMHeap.cpp:
1737         (bmalloc::VMHeap::grow):
1738         * bmalloc/VMHeap.h:
1739         (bmalloc::VMHeap::allocateLargeRange):
1740         (bmalloc::VMHeap::deallocateLargeRange): Adopt the LargeObject interface.
1741
1742 2015-02-20  Geoffrey Garen  <ggaren@apple.com>
1743
1744         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
1745         https://bugs.webkit.org/show_bug.cgi?id=141802
1746
1747         Reviewed by Andreas Kling.
1748
1749         Rolling back in with a fix for a crash seen while using GuardMalloc.
1750
1751         * bmalloc/VMHeap.cpp:
1752         (bmalloc::VMHeap::grow):
1753         * bmalloc/VMHeap.h:
1754         * bmalloc/Zone.cpp: Re-land the old patch.
1755
1756         (bmalloc::Zone::size): Be sure to implement the size() function since
1757         it's accessible indirectly via the malloc_zone_from_ptr public API --
1758         and GuardMalloc calls it all the time.
1759
1760         (bmalloc::Zone::Zone):
1761         * bmalloc/Zone.h: Re-land the old patch.
1762
1763 2015-02-19  Commit Queue  <commit-queue@webkit.org>
1764
1765         Unreviewed, rolling out r180363.
1766         https://bugs.webkit.org/show_bug.cgi?id=141814
1767
1768         Caused >50 crashes when running LayoutTests in GuardMalloc or
1769         ASAN modes. (Requested by jernoble on #webkit).
1770
1771         Reverted changeset:
1772
1773         "bmalloc should implement malloc introspection (to stop false-
1774         positive leaks when MallocStackLogging is off)"
1775         https://bugs.webkit.org/show_bug.cgi?id=141802
1776         http://trac.webkit.org/changeset/180363
1777
1778 2015-02-19  Geoffrey Garen  <ggaren@apple.com>
1779
1780         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
1781         https://bugs.webkit.org/show_bug.cgi?id=141802
1782
1783         Reviewed by Andreas Kling.
1784
1785         Fixed a last-minute type.
1786
1787         The macro is OS, not PLATFORM.
1788
1789         * bmalloc/VMHeap.cpp:
1790         (bmalloc::VMHeap::grow):
1791         * bmalloc/VMHeap.h:
1792         * bmalloc/Zone.h:
1793
1794 2015-02-19  Geoffrey Garen  <ggaren@apple.com>
1795
1796         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
1797         https://bugs.webkit.org/show_bug.cgi?id=141802
1798
1799         Reviewed by Andreas Kling.
1800
1801         This patch does the bare minimum to stop false positive leaks from
1802         being reported by the Darwin leaks tool. We register each super chunk
1803         as a single object, and then request that the leaks tool scan it.
1804
1805         * bmalloc.xcodeproj/project.pbxproj: Added an abstraction for the malloc
1806         zone introspection API.
1807
1808         * bmalloc/Algorithm.h: Missing #include.
1809
1810         * bmalloc/VMHeap.cpp:
1811         (bmalloc::VMHeap::grow):
1812         * bmalloc/VMHeap.h: Adopt the new abstraction.
1813
1814         * bmalloc/Zone.cpp: Added.
1815         (bmalloc::remoteRead): Helper for reading an object out of another process.
1816         (bmalloc::Zone::enumerator):
1817         (bmalloc::Zone::Zone): Register a malloc zone so that we will participate
1818         in introspection.
1819
1820         * bmalloc/Zone.h: Added.
1821         (bmalloc::Zone::superChunks):
1822         (bmalloc::Zone::addSuperChunk): Use a non-dynamically-allocated vector
1823         since our dynamic allocations will not be scanned by leaks since they
1824         will have the malloc VM tag.
1825
1826 2015-02-18  Geoffrey Garen  <ggaren@apple.com>
1827
1828         bmalloc: VMHeap should keep a record of all of its VM ranges (for malloc introspection)
1829         https://bugs.webkit.org/show_bug.cgi?id=141759
1830
1831         Reviewed by Andreas Kling.
1832
1833         * bmalloc.xcodeproj/project.pbxproj:
1834         * bmalloc/SuperChunk.h: Added.
1835         (bmalloc::SuperChunk::create):
1836         (bmalloc::SuperChunk::SuperChunk):
1837         (bmalloc::SuperChunk::smallChunk):
1838         (bmalloc::SuperChunk::mediumChunk):
1839         (bmalloc::SuperChunk::largeChunk): Factored out super chunk creation
1840         into a separate class, for clarity and type safety.
1841
1842         * bmalloc/VMHeap.cpp:
1843         (bmalloc::VMHeap::grow):
1844         (bmalloc::VMHeap::allocateSuperChunk): Renamed "allocateSuperChunk" to
1845         "grow" because Andreas found "allocateSuperChunk" to be unclear.
1846
1847         * bmalloc/VMHeap.h: Track all our VM ranges. We will use this information
1848         for malloc introspection.
1849
1850         (bmalloc::VMHeap::allocateSmallPage):
1851         (bmalloc::VMHeap::allocateMediumPage):
1852         (bmalloc::VMHeap::allocateLargeRange): Updated for renames.
1853
1854 2015-02-18  Zan Dobersek  <zdobersek@igalia.com>
1855
1856         Build bmalloc through CMake as a static library. It's then linked either
1857         into the WTF library (if built as a shared library) or into the JSC and
1858         WebKit2 libraries. There's no need to build it as a standalone shared library.
1859
1860         Rubber-stamped by Carlos Garcia Campos.
1861
1862         * CMakeLists.txt:
1863
1864 2015-02-13  Gyuyoung Kim  <gyuyoung.kim@samsung.com>
1865
1866         [BMalloc] Add a FIXME comment for memory alignas
1867         https://bugs.webkit.org/show_bug.cgi?id=141556
1868
1869         Reviewed by Csaba Osztrogonác.
1870
1871         * bmalloc/Chunk.h: Add a FIXME comment.
1872         * bmalloc/LargeChunk.h: ditto.
1873
1874 2015-02-11  Csaba Osztrogonác  <ossy@webkit.org>
1875
1876         bmalloc buildfix on 32 bit Linux (x86/ARM)
1877         https://bugs.webkit.org/show_bug.cgi?id=141472
1878
1879         Reviewed by Gyuyoung Kim.
1880
1881         * bmalloc/Algorithm.h:
1882         (bmalloc::roundUpToMultipleOf):
1883         * bmalloc/FixedVector.h:
1884         (bmalloc::FixedVector::clear):
1885         * bmalloc/Sizes.h:
1886         (bmalloc::Sizes::sizeClass):
1887
1888 2015-02-11  Gyuyoung Kim  <gyuyoung.kim@samsung.com>
1889
1890         [EFL][GTK] Use bmalloc instead of tcmalloc
1891         https://bugs.webkit.org/show_bug.cgi?id=140162
1892
1893         Reviewed by Carlos Garcia Campos.
1894
1895         Support to use bmalloc on EFL and GTK ports.
1896
1897         * CMakeLists.txt: Added.
1898         * bmalloc/Allocator.cpp:
1899         (bmalloc::Allocator::allocate):
1900             Fix unused return value caused by posix_memalign().
1901         * bmalloc/AsyncTask.h:
1902         * bmalloc/BoundaryTag.h:
1903         (bmalloc::BoundaryTag::clear):
1904         * bmalloc/Chunk.h:
1905             Change Traits::Page with Traits::PageType in order to fix
1906             -fpermitive build error on EFL and GTK port. 
1907         * bmalloc/EndTag.h:
1908         (bmalloc::EndTag::operator=):
1909         * bmalloc/Line.h: ditto.
1910         * bmalloc/MediumTraits.h:
1911         * bmalloc/Page.h: ditto.
1912         * bmalloc/PerThread.h:
1913             EFL port doesn't support __has_include definition yet.
1914             Define HAVE_PTHREAD_MACHDEP_H according to check if __has_include is supported.
1915         * bmalloc/SmallTraits.h: ditto.
1916         * bmalloc/VMAllocate.h:
1917         (bmalloc::vmDeallocatePhysicalPages):
1918         (bmalloc::vmAllocatePhysicalPages):
1919         * bmalloc/Vector.h:
1920         (bmalloc::Vector<T>::push):
1921         (bmalloc::Vector<T>::reallocateBuffer):
1922
1923 2015-01-31  Sam Weinig  <sam@webkit.org>
1924
1925         Remove even more Mountain Lion support
1926         https://bugs.webkit.org/show_bug.cgi?id=141124
1927
1928         Reviewed by Alexey Proskuryakov.
1929
1930         * Configurations/Base.xcconfig:
1931         * Configurations/DebugRelease.xcconfig:
1932
1933 2015-01-30  Geoffrey Garen  <ggaren@apple.com>
1934
1935         GC marking threads should clear malloc caches
1936         https://bugs.webkit.org/show_bug.cgi?id=141097
1937
1938         Reviewed by Andreas Kling.
1939
1940         Split the scavenging API into per-thread vs global, so that you can
1941         request to scavenge your own thread without scavenging the whole heap.
1942
1943         * bmalloc/Cache.cpp:
1944         (bmalloc::Cache::scavenge):
1945         * bmalloc/bmalloc.h:
1946         (bmalloc::api::scavengeThisThread):
1947         (bmalloc::api::scavenge):
1948
1949 2015-01-28  Dana Burkart  <dburkart@apple.com>
1950
1951         Move ASan flag settings from DebugRelease.xcconfig to Base.xcconfig
1952         https://bugs.webkit.org/show_bug.cgi?id=136765
1953
1954         Reviewed by Alexey Proskuryakov.
1955
1956         * Configurations/Base.xcconfig:
1957         * Configurations/DebugRelease.xcconfig:
1958
1959 2015-01-21  Geoffrey Garen  <ggaren@apple.com>
1960
1961         bmalloc: support aligned allocation
1962         https://bugs.webkit.org/show_bug.cgi?id=140732
1963
1964         Reviewed by Andreas Kling.
1965
1966         * bmalloc/Allocator.cpp:
1967         (bmalloc::Allocator::allocate): New function for aligned allocation.
1968
1969         Small and medium requests just allocate and free until they find an
1970         aligned pointer. This is slightly inefficient in the worst case, but
1971         still constant-time with little-to-no space overhead.
1972
1973         Large requests use a new API that requires the client to specify both
1974         its ideal size and alignment, and the worst-case size you would have to
1975         allocate in order to produce some interior pointer of the requested size
1976         and alignment. We put the burden of this calculation on the client
1977         because it simplifies things if we guarantee that allocation won't fail.
1978
1979         XLarge requests are easy: we just forward them to vmAllocate, which
1980         already supported aligned requests.
1981
1982         * bmalloc/BoundaryTag.h:
1983         * bmalloc/BoundaryTagInlines.h:
1984         (bmalloc::BoundaryTag::mergeLeft):
1985         (bmalloc::BoundaryTag::mergeRight):
1986         (bmalloc::BoundaryTag::merge):
1987         (bmalloc::BoundaryTag::deallocate):
1988         (bmalloc::BoundaryTag::split):
1989         (bmalloc::BoundaryTag::allocate): No behavior change here. I just
1990         refactored the interface to remove some reference out parameters in
1991         order to clarify what changes and what doesn't.
1992
1993         * bmalloc/Heap.cpp:
1994         (bmalloc::Heap::allocateXLarge): Added an alignment API.
1995
1996         (bmalloc::Heap::allocateLarge):
1997         * bmalloc/Heap.h: Added an alignment API. I split out allocateLarge into
1998         a few variants, so aligned and unaligned allocation could share some code.
1999
2000         * bmalloc/SegregatedFreeList.cpp:
2001         (bmalloc::SegregatedFreeList::take):
2002         * bmalloc/SegregatedFreeList.h: Changed to use a separate, explicit API
2003         for aligned allocation. It turns out that the aligned path is pretty
2004         different, since it ends up searching for two potential ways to satisfy
2005         an allocation: either large enough and aligned, or large enough to split
2006         into something not aligned and something large enough and aligned.
2007
2008         * bmalloc/VMAllocate.h:
2009         (bmalloc::vmAllocate): Switched alignment to come before size because
2010         that's how the memalign API specifies it.
2011
2012         * bmalloc/VMHeap.h:
2013         (bmalloc::VMHeap::allocateLargeRange): Added an alignment API.
2014
2015 2015-01-20  Geoffrey Garen  <ggaren@apple.com>
2016
2017         bmalloc: a little bit of cleanup
2018         https://bugs.webkit.org/show_bug.cgi?id=140687
2019
2020         Reviewed by Anders Carlsson.
2021
2022         * bmalloc/Algorithm.h:
2023         (bmalloc::isPowerOfTwo): Added a check for 0, since 0 would break a lot
2024         of code.
2025
2026         * bmalloc/BoundaryTag.h:
2027         * bmalloc/BoundaryTagInlines.h:
2028         (bmalloc::BoundaryTag::mergeLeft):
2029         (bmalloc::BoundaryTag::mergeRight):
2030         (bmalloc::BoundaryTag::merge):
2031         (bmalloc::BoundaryTag::deallocate):
2032         (bmalloc::BoundaryTag::split):
2033         (bmalloc::BoundaryTag::allocate):
2034         (bmalloc::BoundaryTag::mergeLargeLeft): Deleted.
2035         (bmalloc::BoundaryTag::mergeLargeRight): Deleted.
2036         (bmalloc::BoundaryTag::mergeLarge): Deleted.
2037         (bmalloc::BoundaryTag::splitLarge): Deleted. Removed the word "Large"
2038         from all these functions, since boundary tags always pertain to large
2039         objects, and putting the word "Large" everywhere wasn't helping to
2040         explain that.
2041
2042         * bmalloc/Heap.cpp:
2043         (bmalloc::Heap::allocateXLarge):
2044         (bmalloc::Heap::findXLarge):
2045         (bmalloc::Heap::deallocateXLarge):
2046         * bmalloc/Heap.h:
2047         * bmalloc/VMHeap.h:
2048         (bmalloc::VMHeap::allocateXLarge): Deleted.
2049         (bmalloc::VMHeap::findXLarge): Deleted.
2050         (bmalloc::VMHeap::deallocateXLarge): Deleted. Moved XLarge allocation
2051         from VMHeap to Heap. Since the purpose of the VMHeap is to cache VM
2052         ranges, and the VMHeap never caches any XLarge ranges, it doesn't
2053         really make sense for the VMHeap to be involved.
2054
2055 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
2056
2057         bmalloc: refactored XLarge allocation for better alignment
2058         https://bugs.webkit.org/show_bug.cgi?id=140582
2059
2060         Reviewed by Andreas Kling.
2061
2062         XLarge objects used to be Large objects with an extra bit of metadata
2063         that said "actually, I'm not large -- I'm extra large".
2064
2065         The metadata header in an XLarge allocation made it impossible for the
2066         XLarge object to honor a very large alignment request.
2067
2068         The solution is to stop using a metadata header for XLarge objects, and
2069         instead to store explicit metadata on the side.
2070
2071         This is a bit less astonishing, which is also nice.
2072
2073         Finding XLarge metadata is now a linear search. That's probably OK, since
2074         it was always so in TCMalloc, and the usual number of XLarge allocations
2075         in a process is 0.
2076
2077         This design makes it possible for the heap to cache XLarge allocations
2078         with and/or without physical pages. I haven't actually done that yet
2079         because the tradeoffs are subtle, so I don't want to do anything without
2080         a motivating test case.
2081
2082         * bmalloc.xcodeproj/project.pbxproj:
2083         * bmalloc/Allocator.cpp:
2084         (bmalloc::Allocator::reallocate): Removed the concept of an XLargeChunk,
2085         since an XLarge allocation is now just a naked buffer without a header.
2086
2087         (bmalloc::Allocator::allocateXLarge): Added an explicit qualifier for
2088         XLarge alignment, since XLargeChunk won't give this to us implicitly
2089         anymore.
2090
2091         * bmalloc/BoundaryTag.h:
2092         (bmalloc::BoundaryTag::setRange):
2093         (bmalloc::BoundaryTag::isXLarge): Deleted.
2094         (bmalloc::BoundaryTag::setXLarge): Deleted.
2095         * bmalloc/BoundaryTagInlines.h:
2096         (bmalloc::validate):
2097         (bmalloc::BoundaryTag::deallocate): Removed the XLarge hacks from Large allocations.
2098
2099         * bmalloc/Deallocator.cpp:
2100         (bmalloc::Deallocator::deallocateXLarge):
2101         (bmalloc::Deallocator::deallocateSlowCase):
2102         * bmalloc/Heap.cpp:
2103         (bmalloc::Heap::findXLarge):
2104         (bmalloc::Heap::allocateXLarge):
2105         (bmalloc::Heap::deallocateXLarge):
2106         * bmalloc/Heap.h: Updated for interface changes.
2107
2108         * bmalloc/ObjectType.cpp:
2109         (bmalloc::objectType):
2110         * bmalloc/ObjectType.h:
2111         (bmalloc::isXLarge): We can now tell if a pointer is XLarge just by
2112         examining its bit pattern -- just like we do for other kinds of
2113         allocations -- which is nice.
2114
2115         * bmalloc/Sizes.h:
2116         * bmalloc/VMHeap.h:
2117         (bmalloc::VMHeap::allocateXLarge):
2118         (bmalloc::VMHeap::findXLarge):
2119         (bmalloc::VMHeap::deallocateXLarge): Keep an explicit vector of metadata
2120         for XLarge allocations.
2121
2122         * bmalloc/XLargeChunk.h: Removed.
2123
2124 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
2125
2126         bmalloc: added some infrastructure for aligned allocation
2127         https://bugs.webkit.org/show_bug.cgi?id=140572
2128
2129         Reviewed by Andreas Kling.
2130
2131         * bmalloc/Algorithm.h:
2132         (bmalloc::isPowerOfTwo):
2133         (bmalloc::roundUpToMultipleOf):
2134         (bmalloc::roundDownToMultipleOf): Refactored some duplicate code to use our
2135         isPowerOfTwo helper function.
2136
2137         * bmalloc/Allocator.cpp:
2138         (bmalloc::Allocator::allocate):
2139         * bmalloc/Allocator.h: Stubbed out an implementation of aligned allocation.
2140         Doesn't do anything yet, but does correctly forward to system malloc
2141         when bmalloc is disabled.
2142
2143         * bmalloc/Cache.cpp:
2144         (bmalloc::Cache::allocateSlowCaseNullCache):
2145         * bmalloc/Cache.h:
2146         (bmalloc::Cache::allocate):
2147         * bmalloc/bmalloc.h:
2148         (bmalloc::api::memalign):
2149         * bmalloc/mbmalloc.cpp: Stubbed out an API for aligned allocation.
2150
2151 2015-01-13  Geoffrey Garen  <ggaren@apple.com>
2152
2153         Consider alignment when allocating from a SegregatedFreeList
2154         https://bugs.webkit.org/show_bug.cgi?id=140408
2155
2156         Reviewed by Sam Weinig.
2157
2158         In preparation for supporting aligned allocation.
2159
2160         No performance change.
2161
2162         Since this is just one extra branch in an already expensive function,
2163         I decided not to duplicate the function just to avoid the branch in
2164         the un-aligned case.
2165
2166         * bmalloc/SegregatedFreeList.cpp:
2167         (bmalloc::SegregatedFreeList::take):
2168         * bmalloc/SegregatedFreeList.h:
2169
2170 2015-01-13  Geoffrey Garen  <ggaren@apple.com>
2171
2172         Renamed minimum to size in SegregatedFreeList
2173         https://bugs.webkit.org/show_bug.cgi?id=140406
2174
2175         Reviewed by Sam Weinig.
2176
2177         In preparation for supporting aligned allocation.
2178
2179         * bmalloc/SegregatedFreeList.cpp:
2180         (bmalloc::SegregatedFreeList::takeGreedy):
2181         (bmalloc::SegregatedFreeList::take): Every size passed to malloc is
2182         really just a minimum. Let's not imply that this value is special.
2183
2184 2015-01-11  Dan Bernstein  <mitz@apple.com>
2185
2186         Geoff is organized, but he is not an organization.
2187
2188         Rubber-stamped by Anders Carlsson.
2189
2190         * bmalloc.xcodeproj/project.pbxproj: Removed the ORGANIZATIONNAME project attribute.
2191
2192 2015-01-07  Geoffrey Garen  <ggaren@apple.com>
2193
2194         Make bmalloc work with ASan
2195         https://bugs.webkit.org/show_bug.cgi?id=140194
2196
2197         Reviewed by Mark Lam.
2198
2199         * bmalloc/BPlatform.h: Added a way to detect Darwin OSes, since we need
2200         an OS-specific API to test for loaded runtime libraries.
2201
2202         * bmalloc/Environment.cpp:
2203         (bmalloc::isASanEnabled):
2204         (bmalloc::Environment::computeIsBmallocEnabled): Disabled bmalloc if
2205         ASan is enabled, since system malloc has the Asan hooks we need.
2206
2207         You could check for the ASan compile-time flag instead, but doing this
2208         check at runtime prepares bmalloc for a world where it is a dynamic
2209         library that might be loaded into projects it did not compile with.
2210
2211 2015-01-05  Geoffrey Garen  <ggaren@apple.com>
2212
2213         Fix up bmalloc's PerThread for use on Linux
2214         https://bugs.webkit.org/show_bug.cgi?id=139804
2215
2216         Reviewed by Anders Carlsson.
2217
2218         The previous implementation was a bit slow.
2219
2220         * bmalloc/PerThread.h:
2221         (bmalloc::PerThreadStorage<Cache>::get):
2222         (bmalloc::PerThreadStorage::get):
2223         (bmalloc::PerThreadStorage::init): Added a catch-all cross-platform Unix
2224         way to do fast per-thread access without taking a lock every time. This
2225         probably works on all the platforms we care about, and it matches other
2226         techniques we use elsewhere in WebKit.
2227
2228         (bmalloc::PerThread<T>::getFastCase): Removed the conditional from
2229         this class because PerThreadStorage now encapsulates everything that
2230         needs to be conditional.
2231
2232         (bmalloc::PerThreadStorage::initSharedKeyIfNeeded): Deleted.
2233
2234 2014-12-26  Dan Bernstein  <mitz@apple.com>
2235
2236         <rdar://problem/19348208> REGRESSION (r177027): iOS builds use the wrong toolchain
2237         https://bugs.webkit.org/show_bug.cgi?id=139950
2238
2239         Reviewed by David Kilzer.
2240
2241         * Configurations/Base.xcconfig: Only define TOOLCHAINS when building for OS X, doing so
2242         in a manner that works with Xcode 5.1.1.
2243
2244 2014-12-15  Geoffrey Garen  <ggaren@apple.com>
2245
2246         Safari crashes when you set Malloc environment variables
2247         https://bugs.webkit.org/show_bug.cgi?id=139656
2248
2249         Reviewed by Michael Saboff.
2250
2251         I forgot to cover the realloc() case. Whoops. (OoPS?)
2252
2253         This time around, I ran the full MallocBench test suite in Malloc=1
2254         mode, and it passed.
2255
2256         * bmalloc/Allocator.cpp:
2257         (bmalloc::Allocator::reallocate):
2258         * bmalloc/Allocator.h: Pushed realloc() logic down into the allocator.
2259         It needs to be down there so that we can do the short-circuiting check
2260         for whether bmalloc is enabled first.
2261
2262         Also added the check.
2263
2264         * bmalloc/Cache.cpp:
2265         (bmalloc::Cache::scavenge):
2266         (bmalloc::Cache::Cache):
2267         (bmalloc::Cache::reallocateSlowCaseNullCache):
2268         * bmalloc/Cache.h:
2269         (bmalloc::Cache::deallocator):
2270         (bmalloc::Cache::reallocate): Ditto.
2271
2272         * bmalloc/bmalloc.h:
2273         (bmalloc::api::free):
2274         (bmalloc::api::realloc): Ditto.
2275
2276         (bmalloc::api::scavenge): Pushed this down into Cache to match the
2277         surrounding functions.
2278
2279 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
2280
2281         bmalloc should support system memory analysis tools (part 2)
2282         https://bugs.webkit.org/show_bug.cgi?id=139565
2283
2284         Reviewed by Mark Lam.
2285
2286         This patch actually queries the environment to see if memory analysis
2287         tools have been enabled.
2288
2289         * bmalloc/Deallocator.cpp:
2290         (bmalloc::Deallocator::scavenge): Don't process the object log if
2291         we've disabled bmalloc because it will be full of invalid nullptrs.
2292
2293         * bmalloc/Environment.cpp:
2294         (bmalloc::isMallocEnvironmentVariableSet): Test for the list of known
2295         Malloc debugging flags. I also added a plain "Malloc" catch-all for
2296         when you want to disable bmalloc without enabling any kind of funny
2297         business.
2298
2299         It would be slightly nicer just to iterate the list of environment
2300         variables and strstr them, but getenv is the more portable option,
2301         and performance here doesn't really matter.
2302
2303         (bmalloc::isLibgmallocEnabled): Test for the libgmalloc insertion
2304         environment variable.
2305
2306         (bmalloc::Environment::computeIsBmallocEnabled):
2307
2308 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
2309
2310         Try to fix the iOS simulator build.
2311
2312         #include the declaration of malloc / free.
2313
2314         * bmalloc/Allocator.cpp:
2315         * bmalloc/Deallocator.cpp:
2316
2317 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
2318
2319         Try to fix the build.
2320
2321         * bmalloc.xcodeproj/project.pbxproj: Marked a header exported.
2322
2323 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
2324
2325         bmalloc should support system memory analysis tools (part 1)
2326         https://bugs.webkit.org/show_bug.cgi?id=139559
2327
2328         Reviewed by Mark Lam.
2329
2330         This patch adds the hooks to disable bmalloc at runtime if certain
2331         environment variables are set, but doesn't actually read from the
2332         environment yet.
2333
2334         No performance change.
2335
2336         * bmalloc.xcodeproj/project.pbxproj: Added the Environment class, which
2337         we'll use to read environment variables and see if memory analysis tools
2338         have been enabled.
2339
2340         * bmalloc/Allocator.cpp:
2341         (bmalloc::Allocator::Allocator):
2342         (bmalloc::Allocator::allocateSlowCase): Added a hook to disable bmalloc
2343         on the allocation path. We cache the setting to make the check fast.
2344
2345         * bmalloc/Allocator.h: Interface changes.
2346
2347         * bmalloc/Cache.cpp:
2348         (bmalloc::Cache::Cache): Pass a heap pointer through to our allocator
2349         and deallocator. This main purpose is to enable them to query the
2350         environment for whether bmalloc is enabled; but this is also a slightly
2351         cleaner way to guarantee to them that the Heap has been pre-initialized.
2352
2353         * bmalloc/Deallocator.cpp:
2354         (bmalloc::Deallocator::Deallocator): If bmalloc is disable, artificially
2355         fill the object log to force us to take the slow path on all deallocations.
2356
2357         (bmalloc::Deallocator::deallocateSlowCase): Do the disabled check.
2358
2359         * bmalloc/Deallocator.h: Interface changes.
2360
2361         * bmalloc/Environment.cpp: Added.
2362         (bmalloc::Environment::Environment):
2363         (bmalloc::Environment::computeIsBmallocEnabled):
2364         * bmalloc/Environment.h: Added.
2365         (bmalloc::Environment::isBmallocEnabled): This is the class that will
2366         encapsulate looking for environment variables that turn on heap
2367         analysis tools.
2368
2369         * bmalloc/Heap.h:
2370         (bmalloc::Heap::environment):
2371
2372         * bmalloc/Mutex.h:
2373         (bmalloc::Mutex::Mutex):
2374         * bmalloc/StaticMutex.h: A little refactoring to clarify these comments,
2375         since I got super confused about them while writing this patch.
2376
2377         * bmalloc/VMHeap.cpp: Fixed an #include.
2378
2379 2014-12-09  David Kilzer  <ddkilzer@apple.com>
2380
2381         Switch from using PLATFORM_NAME to SDK selectors in ANGLE, bmalloc, gtest, JavaScriptCore, WTF
2382         <http://webkit.org/b/139212>
2383
2384         Reviewed by Joseph Pecoraro.
2385
2386         * Configurations/Base.xcconfig:
2387         - Only set GCC_ENABLE_OBJC_GC, GCC_MODEL_TUNING and TOOLCHAINS
2388           on OS X.
2389         * Configurations/DebugRelease.xcconfig:
2390         - Only set MACOSX_DEPLOYMENT_TARGET and SDKROOT on OS X.
2391
2392 2014-11-07  Geoffrey Garen  <ggaren@apple.com>
2393
2394         bmalloc uses 8X more virtual memory than necessary
2395         https://bugs.webkit.org/show_bug.cgi?id=138495
2396
2397         Reviewed by Mark Lam.
2398
2399         iOS has a per-process virtual memory cap around 1GB, so there's some
2400         value to not going totally ham with virtual memory.
2401
2402         We currently use about 8X the necessary amount:
2403             - 2X to align our VM allocation
2404             - 4X to reserve small / medium / (2) large chunk VM ranges per superchunk
2405
2406         We can cut that down:
2407             - Return the unaligned portion of our VM allocation (-2X)
2408             - Use all the chunks in a superchunk, instead of allocating one
2409               chunk per superchunk (-4X)
2410
2411         * bmalloc/Algorithm.h:
2412         (bmalloc::roundUpToMultipleOf): Added a non-constant version of this
2413         function so we can call it with getpagesize() at runtime.
2414
2415         * bmalloc/Chunk.h:
2416         * bmalloc/LargeChunk.h:
2417         (bmalloc::LargeChunk::create): Deleted. Instead of each chunk allocating
2418         its own VM, VMHeap allocates the superchunk and all the chunks in it at a time.
2419
2420         * bmalloc/VMAllocate.h:
2421         (bmalloc::vmValidate):
2422         (bmalloc::vmAllocate): ASSERT that mmap succeeds to make crashes clearer
2423         if it does not succeed. Allocate precisely, and give back the extra.
2424
2425         * bmalloc/VMHeap.cpp:
2426         (bmalloc::VMHeap::allocateSuperChunk):
2427         (bmalloc::VMHeap::allocateSmallChunk): Deleted.
2428         (bmalloc::VMHeap::allocateMediumChunk): Deleted.
2429         (bmalloc::VMHeap::allocateLargeChunk): Deleted. Use all the chunks
2430         in a superchunk, instead of just one.
2431
2432         * bmalloc/VMHeap.h:
2433         (bmalloc::VMHeap::allocateSmallPage):
2434         (bmalloc::VMHeap::allocateMediumPage):
2435         (bmalloc::VMHeap::allocateLargeRange):
2436         * bmalloc/XLargeChunk.h:
2437         (bmalloc::XLargeChunk::create): Updated to match changes above.
2438
2439 2014-11-01  David Kilzer  <ddkilzer@apple.com>
2440
2441         JavaScriptCore is missing debug info for bmalloc because libbmalloc.a is stripped
2442         <https://webkit.org/b/138286>
2443         <rdar://problem/18847087>
2444
2445         Reviewed by Dan Bernstein.
2446
2447         * Configurations/bmalloc.xcconfig: Set STRIP_INSTALLED_PRODUCT
2448         to NO for the target that produces libbmalloc.a so that the
2449         debug symbols will be linked into JavaScriptCore and end up in
2450         its dSYM file.
2451
2452 2014-10-30  Dana Burkart  <dburkart@apple.com>
2453
2454         <rdar://problem/18821260> Prepare for the mysterious future
2455
2456         Reviewed by Lucas Forschler.
2457
2458         * Configurations/Base.xcconfig:
2459         * Configurations/DebugRelease.xcconfig:
2460
2461 2014-09-24  Geoffrey Garen  <ggaren@apple.com>
2462
2463         bmalloc: cleaned up fast path vs slow path
2464         https://bugs.webkit.org/show_bug.cgi?id=137081
2465
2466         Reviewed by Sam Weinig.
2467
2468         Might be a 1% speedup on MallocBench. Also cleans up the code a bit.
2469
2470         * bmalloc/Allocator.cpp:
2471         (bmalloc::Allocator::Allocator): Merged the small and medium range
2472         caches, just like the small and medium allocators. Ranges are abstract
2473         objects that don't really care whether they hold small or medium objects,
2474         so they don't need to be segregated.
2475
2476         (bmalloc::Allocator::scavenge): Ditto.
2477
2478         (bmalloc::Allocator::allocateBumpRangeSlowCase):
2479         (bmalloc::Allocator::allocateBumpRange): Same thing here, except that
2480         we do care a tiny bit, because we need to specify small vs medium when
2481         allocating new ranges from the heap, to ensure that the heap allocates
2482         from the right segment of VM.
2483
2484         (bmalloc::Allocator::allocateLarge):
2485         (bmalloc::Allocator::allocateXLarge): NO_INLINE because this was clouding
2486         up the fast path. Large allocation performance is dominated by allocation
2487         logic and initialization, so inlining it doesn't help.
2488
2489         (bmalloc::Allocator::allocateSlowCase): Slow path got a bit cleaner since
2490         it doesn't need to distinguish small vs medium objects.
2491
2492         (bmalloc::Allocator::allocateSmallBumpRange): Deleted.
2493         (bmalloc::Allocator::allocateMediumBumpRange): Deleted.
2494
2495         * bmalloc/Allocator.h:
2496         * bmalloc/BumpRange.h:
2497
2498         * bmalloc/Cache.cpp:
2499         (bmalloc::Cache::allocateSlowCase): Deleted.
2500         (bmalloc::Cache::deallocateSlowCase): Deleted.
2501         * bmalloc/Cache.h:
2502         (bmalloc::Cache::allocate):
2503         (bmalloc::Cache::deallocate):
2504         (bmalloc::Cache::allocateFastCase): Deleted.
2505         (bmalloc::Cache::deallocateFastCase): Deleted. Removed the Cache slow
2506         paths. The downside to this change is that the fast path branches to two
2507         distinct failure cases instead of one. The upside is that the slow path
2508         doesn't need to re-read the segment register, which is not as cheap as a
2509         normal register, and it doesn't need to do an extra level of function 
2510         call. Seems to be worth it.
2511
2512         * bmalloc/Deallocator.h:
2513         * bmalloc/Heap.cpp:
2514         (bmalloc::Heap::refillSmallBumpRangeCache):
2515         (bmalloc::Heap::refillMediumBumpRangeCache):
2516         * bmalloc/Heap.h: Updated for interface changes.
2517
2518         * bmalloc/Sizes.h: The most ranges a cache will hold is the number of
2519         small lines in a page / 2, since any other free lines will coalesce
2520         with their neighbors.
2521
2522 2014-09-23  Geoffrey Garen  <ggaren@apple.com>
2523
2524         Rolled out r173346.
2525
2526             bmalloc should honor the FastMalloc statistics API
2527             https://bugs.webkit.org/show_bug.cgi?id=136592
2528
2529         This didn't really work. Because we allow ranges with and without
2530         physical pages to merge, and we allow double-committing and
2531         double-decommitting, we can't rely on commit actions to track memory
2532         footprint.
2533
2534         * bmalloc/Heap.cpp:
2535         (bmalloc::Heap::size): Deleted.
2536         (bmalloc::Heap::capacity): Deleted.
2537         * bmalloc/Heap.h:
2538         * bmalloc/VMHeap.cpp:
2539         (bmalloc::VMHeap::VMHeap):
2540         (bmalloc::VMHeap::allocateSmallChunk):
2541         (bmalloc::VMHeap::allocateMediumChunk):
2542         (bmalloc::VMHeap::allocateLargeChunk):
2543         * bmalloc/VMHeap.h:
2544         (bmalloc::VMHeap::allocateSmallPage):
2545         (bmalloc::VMHeap::allocateMediumPage):
2546         (bmalloc::VMHeap::allocateLargeRange):
2547         (bmalloc::VMHeap::deallocateSmallPage):
2548         (bmalloc::VMHeap::deallocateMediumPage):
2549         (bmalloc::VMHeap::deallocateLargeRange):
2550         (bmalloc::VMHeap::size): Deleted.
2551         (bmalloc::VMHeap::capacity): Deleted.
2552         * bmalloc/bmalloc.h:
2553         (bmalloc::api::heapSize): Deleted.
2554         (bmalloc::api::heapCapacity): Deleted.
2555
2556 2014-09-23  Geoffrey Garen  <ggaren@apple.com>
2557
2558         bmalloc: Allocation should be more precise
2559         https://bugs.webkit.org/show_bug.cgi?id=136993
2560
2561         Reviewed by Gavin Barraclough.
2562
2563         13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
2564
2565         This patch teaches the allocator to merge adjacent free lines into a
2566         single allocatable range. This allows us to shrink the size of an
2567         individual line without increasing fragmentation or the rate of allocator
2568         slow paths.
2569
2570         We'll only take more slow paths when available memory is sparse, which
2571         is exactly when it's worth it. When available memory is dense, we'll
2572         take fewer slow paths.
2573
2574         * bmalloc.xcodeproj/project.pbxproj:
2575         * bmalloc/Algorithm.h:
2576         (bmalloc::divideRoundingUp):
2577
2578         * bmalloc/Allocator.cpp:
2579         (bmalloc::Allocator::Allocator): Updated for interface changes.
2580
2581         (bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
2582         Now that we merge lines, it's not convenient to scavenge by line.
2583
2584         (bmalloc::Allocator::allocateSmallBumpRange):
2585         (bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
2586         instead of individual lines.
2587
2588         (bmalloc::Allocator::allocateSlowCase):
2589         (bmalloc::Allocator::allocateSmallLine): Deleted.
2590         (bmalloc::Allocator::allocateMediumLine): Deleted.
2591         (bmalloc::Allocator::allocateMedium): Deleted.
2592         * bmalloc/Allocator.h:
2593         (bmalloc::Allocator::allocateFastCase): Folded medium allocations
2594         into the standard fast path with small allocations. Since a BumpAllocator
2595         just allocates out of an arbitrary range, it doesn't need to distinguish
2596         between small and medium lines.
2597
2598         * bmalloc/BumpAllocator.h:
2599         (bmalloc::BumpAllocator::size):
2600         (bmalloc::BumpAllocator::BumpAllocator):
2601         (bmalloc::BumpAllocator::init):
2602         (bmalloc::BumpAllocator::refill):
2603         (bmalloc::BumpAllocator::line): Deleted. No need to track line information
2604         anymore: the heap just gives us a pointer and a pre-computed number of
2605         objects, and we allocate them.
2606
2607         * bmalloc/Deallocator.cpp:
2608         (bmalloc::Deallocator::processObjectLog): Updated for interface changes.
2609
2610         * bmalloc/Heap.cpp:
2611         (bmalloc::Heap::Heap):
2612         (bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
2613         detailing where all objects will lie in memory. After we merge two lines,
2614         we might allocate an object that spans from one line to the next. This
2615         metadata details which bits of memory overlap in that way, and how they
2616         overlap.
2617
2618         (bmalloc::Heap::refillSmallBumpRangeCache):
2619         (bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
2620         and merge adjacent free lines into BumpRanges.
2621
2622         (bmalloc::Heap::allocateSmallPage):
2623         (bmalloc::Heap::allocateMediumPage):
2624         (bmalloc::Heap::deallocateSmallLine):
2625         (bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
2626         since we scan for free memory a page at a time.
2627
2628         (bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
2629         (bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
2630         fast path.
2631
2632         * bmalloc/Heap.h:
2633         (bmalloc::Heap::derefSmallLine):
2634         (bmalloc::Heap::derefMediumLine):
2635         (bmalloc::Heap::deallocateSmallLine): Deleted.
2636         (bmalloc::Heap::allocateSmallLine): Deleted.
2637         (bmalloc::Heap::deallocateMediumLine): Deleted.
2638         (bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
2639
2640         * bmalloc/Line.h:
2641         (bmalloc::Line<Traits>::ref):
2642         (bmalloc::Line<Traits>::deref):
2643         (bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
2644         anymore, since we only ever deref by 1 now.
2645
2646         * bmalloc/MediumAllocator.h:
2647         (bmalloc::MediumAllocator::isNull): Deleted.
2648         (bmalloc::MediumAllocator::MediumAllocator): Deleted.
2649         (bmalloc::MediumAllocator::line): Deleted.
2650         (bmalloc::MediumAllocator::allocate): Deleted.
2651         (bmalloc::MediumAllocator::derefCount): Deleted.
2652         (bmalloc::MediumAllocator::refill): Deleted.
2653         (bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
2654         been dead for a while, since it doesn't build anymore with this patch.
2655
2656         * bmalloc/Page.h:
2657         (bmalloc::Page::sizeClass):
2658         (bmalloc::Page::setSizeClass):
2659         (bmalloc::Page::smallSizeClass): Deleted.
2660         (bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
2661         to sizeClass, since we use it for medium sizes too.
2662
2663         * bmalloc/Sizes.h:
2664         (bmalloc::Sizes::sizeClass):
2665         (bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
2666
2667         (bmalloc::Sizes::smallSizeClassFor): Deleted.
2668         (bmalloc::Sizes::mediumSizeClassFor): Deleted.
2669
2670         * bmalloc/bmalloc.h:
2671         (bmalloc::api::realloc): Now that we have precise objects sizes, realloc
2672         can be a bit more precise. It also has to be, since we can't guarantee
2673         that an object ends at the end of a line anymore.
2674
2675 2014-09-19  Daniel Bates  <dabates@apple.com>
2676
2677         Always assume internal SDK when building configuration Production
2678         https://bugs.webkit.org/show_bug.cgi?id=136925
2679         <rdar://problem/18362399>
2680
2681         Reviewed by Dan Bernstein.
2682
2683         * Configurations/Base.xcconfig:
2684
2685 2014-09-16  Geoffrey Garen  <ggaren@apple.com>
2686
2687         bmalloc: moved line caches from the deallocator to the allocator
2688         https://bugs.webkit.org/show_bug.cgi?id=136868
2689
2690         Reviewed by Gavin Barraclough.
2691
2692         I did this mostly as a simplification, to make it easier to change the
2693         allocation strategy.
2694
2695         No throughput change on MallocBench. Saves about 50kB.
2696
2697         Since the deallocator needs to lock the heap when freeing lines anyway,
2698         there isn't much benefit to giving the deallocator a local cache of
2699         deallocated lines.
2700
2701         We still give the allocator a local cache of lines because that does
2702         reduce the frequency at which it needs to lock the heap in order to
2703         acquire more lines.
2704
2705         * bmalloc/Allocator.cpp:
2706         (bmalloc::Allocator::scavenge):
2707         (bmalloc::Allocator::allocateSmallLine):
2708         (bmalloc::Allocator::allocateMediumLine):
2709         (bmalloc::Allocator::allocateMedium):
2710         (bmalloc::Allocator::allocateSlowCase):
2711         * bmalloc/Allocator.h:
2712         * bmalloc/Deallocator.cpp:
2713         (bmalloc::Deallocator::Deallocator):
2714         (bmalloc::Deallocator::scavenge):
2715         (bmalloc::Deallocator::processObjectLog):
2716         (bmalloc::Deallocator::deallocateSmallLine): Deleted.
2717         (bmalloc::Deallocator::allocateSmallLine): Deleted.
2718         (bmalloc::Deallocator::deallocateMediumLine): Deleted.
2719         (bmalloc::Deallocator::allocateMediumLine): Deleted.
2720         * bmalloc/Deallocator.h:
2721
2722         * bmalloc/Sizes.h:
2723         * bmalloc/VMAllocate.h: Took the opportunity to make the line cache size
2724         exactly one page in size. That's about what we were shooting for anyway,
2725         and it may make it easier to switch to per-page allocation in future.
2726
2727 2014-09-15  Geoffrey Garen  <ggaren@apple.com>
2728
2729         bmalloc: allocate small and medium objects using the same bump pointer class
2730         https://bugs.webkit.org/show_bug.cgi?id=136843
2731
2732         Reviewed by Gavin Barraclough.
2733
2734         4% speedup on MallocBench.
2735
2736         Now that medium-sized objects have dedicated per-size allocators, they
2737         don't need to use an arbitrary bump pointer allocator. This means that
2738         every allocator knows how many objects it will allocate from the start,
2739         and we don't need a post-processing step to adjust refcounts based on
2740         real allocation count.
2741
2742         * bmalloc.xcodeproj/project.pbxproj: Renamed SmallAllocator to BumpAllocator
2743         since it's used for small and medium objects now.
2744
2745         * bmalloc/Allocator.cpp:
2746         (bmalloc::Allocator::Allocator): Updated to use new interface.
2747         (bmalloc::Allocator::scavenge): To "retire" an allocator, we just need
2748         to make sure that we finish allocating all the objects in it.
2749
2750         (bmalloc::Allocator::allocateMedium):
2751         (bmalloc::Allocator::allocateSlowCase):
2752         (bmalloc::Allocator::retire): Deleted.
2753         (bmalloc::Allocator::processSmallAllocatorLog): Deleted.
2754         (bmalloc::Allocator::processMediumAllocatorLog): Deleted.
2755         * bmalloc/Allocator.h:
2756         (bmalloc::Allocator::allocateFastCase): Removed abstractions and data
2757         used to post-process an allocator based on how many objects it allocated.
2758
2759         * bmalloc/BumpAllocator.h: Copied from Source/bmalloc/bmalloc/SmallAllocator.h.
2760         (bmalloc::BumpAllocator::BumpAllocator):
2761         (bmalloc::BumpAllocator::init):
2762         (bmalloc::BumpAllocator::line):
2763         (bmalloc::BumpAllocator::validate):
2764         (bmalloc::BumpAllocator::allocate):
2765         (bmalloc::BumpAllocator::refill):
2766         (bmalloc::BumpAllocator::clear): Updated these functions to be agnostic
2767         about the kinds of lines they allocate into. In some cases, the line
2768         type must be provided as a template parameter by the caller.
2769
2770         (bmalloc::SmallAllocator::SmallAllocator): Deleted.
2771         (bmalloc::SmallAllocator::line): Deleted.
2772         (bmalloc::SmallAllocator::allocate): Deleted.
2773         (bmalloc::SmallAllocator::objectCount): Deleted.
2774         (bmalloc::SmallAllocator::derefCount): Deleted.
2775         (bmalloc::SmallAllocator::refill): Deleted.
2776         (bmalloc::SmallAllocator::clear): Deleted.
2777
2778         * bmalloc/ObjectType.h:
2779         (bmalloc::isMedium):
2780
2781         * bmalloc/SmallAllocator.h:
2782         (bmalloc::SmallAllocator::isNull): Deleted.
2783         (bmalloc::SmallAllocator::canAllocate): Deleted.
2784         (bmalloc::SmallAllocator::SmallAllocator): Deleted.
2785         (bmalloc::SmallAllocator::line): Deleted.
2786         (bmalloc::SmallAllocator::allocate): Deleted.
2787         (bmalloc::SmallAllocator::objectCount): Deleted.
2788         (bmalloc::SmallAllocator::derefCount): Deleted.
2789         (bmalloc::SmallAllocator::refill): Deleted.
2790         (bmalloc::SmallAllocator::clear): Deleted.
2791
2792 2014-09-12  Geoffrey Garen  <ggaren@apple.com>
2793
2794         Fixed a goof in bmalloc Vector sizing
2795         https://bugs.webkit.org/show_bug.cgi?id=136795
2796
2797         Reviewed by Gavin Barraclough and Sam Weinig.
2798
2799         We want our minimum vector to be page-sized since the OS will give us
2800         a page no matter what -- but we want that many bytes, and not enough
2801         bytes to store that many elements.
2802
2803         * bmalloc/Vector.h: Math is hard.
2804
2805 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
2806
2807         bmalloc should segregate medium-sized objects by line like it does for small-sized objects
2808         https://bugs.webkit.org/show_bug.cgi?id=136693
2809
2810         Reviewed by Gavin Barraclough.
2811
2812         4% reduction in heap size on the MallocBench *_memory_warning benchmarks.
2813
2814         No throughput change.
2815
2816         We keep an array of medium allocators, just like our array of small
2817         allocators.
2818
2819         In future, we can simplify the allocation fast path by merging the small
2820         and medium allocator arrays. For now, this is the simplest change that
2821         gets the win.
2822
2823         * bmalloc/Allocator.cpp:
2824         (bmalloc::Allocator::Allocator):
2825         (bmalloc::Allocator::scavenge):
2826         (bmalloc::Allocator::allocateMedium):
2827         * bmalloc/Allocator.h:
2828         * bmalloc/Sizes.h:
2829         (bmalloc::Sizes::mediumSizeClassFor):
2830
2831 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
2832
2833         Reviewed by Sam Weinig.
2834
2835         Renamed log => retire for clarity.
2836
2837         * bmalloc/Allocator.cpp:
2838         (bmalloc::Allocator::scavenge):
2839         (bmalloc::Allocator::retire):
2840         (bmalloc::Allocator::allocateMedium):
2841         (bmalloc::Allocator::allocateSlowCase):
2842         (bmalloc::Allocator::log): Deleted.
2843         * bmalloc/Allocator.h:
2844
2845 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
2846
2847         bmalloc: eager scavenge leaves behind a bogus allocator
2848         https://bugs.webkit.org/show_bug.cgi?id=136743
2849
2850         Reviewed by Sam Weinig.
2851
2852         Be sure to clear the allocator after logging it in the eager scavenge
2853         case, so that we don't later try to allocate out of the lines that we
2854         have thrown away.
2855
2856         We didn't need to do this previously because scavenge would only happen
2857         at thread exit time, after which no further allocation from the per-thread
2858         cache would take place.
2859
2860         * bmalloc/Allocator.cpp:
2861         (bmalloc::Allocator::scavenge):
2862         * bmalloc/MediumAllocator.h:
2863         (bmalloc::MediumAllocator::clear):
2864         * bmalloc/SmallAllocator.h:
2865         (bmalloc::SmallAllocator::clear):
2866
2867 2014-09-05  Geoffrey Garen  <ggaren@apple.com>
2868
2869         bmalloc should honor the FastMalloc statistics API
2870         https://bugs.webkit.org/show_bug.cgi?id=136592
2871
2872         Reviewed by Gavin Barraclough.
2873
2874         We do this by tracking "size" and "capacity" in the VM heap.
2875
2876         The VM heap's "capacity" is all the VM we ever allocated.
2877
2878         The VM heap's "size" the subset of VM currently held onto by the
2879         VM heap (and therefore not in use by the regular heap).
2880
2881         Somewhat ironically, reducing the process's memory footprint, increases
2882         the size of the VM heap, since the VM heap holds the pages that are
2883         purely virtual and not physical.
2884
2885         * bmalloc/Heap.cpp:
2886         (bmalloc::Heap::size):
2887         (bmalloc::Heap::capacity):
2888         * bmalloc/Heap.h:
2889         * bmalloc/VMHeap.cpp:
2890         (bmalloc::VMHeap::VMHeap):
2891         (bmalloc::VMHeap::allocateSmallChunk):
2892         (bmalloc::VMHeap::allocateMediumChunk):
2893         (bmalloc::VMHeap::allocateLargeChunk):
2894         * bmalloc/VMHeap.h:
2895         (bmalloc::VMHeap::size):
2896         (bmalloc::VMHeap::capacity):
2897         (bmalloc::VMHeap::allocateSmallPage):
2898         (bmalloc::VMHeap::allocateMediumPage):
2899         (bmalloc::VMHeap::allocateLargeRange):
2900         (bmalloc::VMHeap::deallocateSmallPage):
2901         (bmalloc::VMHeap::deallocateMediumPage):
2902         (bmalloc::VMHeap::deallocateLargeRange):
2903         * bmalloc/bmalloc.h:
2904         (bmalloc::api::heapSize):
2905         (bmalloc::api::heapCapacity):
2906
2907 2014-09-02  Geoffrey Garen  <ggaren@apple.com>
2908
2909         bmalloc crashes on the EWS bots (due to bad large object allocation)
2910         https://bugs.webkit.org/show_bug.cgi?id=136469
2911
2912         Reviewed by Andreas Kling.
2913
2914         It's possible to convince bmalloc to perform a bad large object allocation,
2915         through these steps:
2916
2917         (1) Insert object A into freelist F0.
2918
2919         (2) Split, merge and split again A's neighbors such that object B is
2920         inserted into freelist F0, with boundary tag and size equal to object A,
2921         but pointer not completely equal to object A. Put object B at the head of F0.
2922
2923         (3) Allocate some other object from F0, swapping its position in the
2924         freelist with object B, such that object A is now ahead of object B.
2925
2926         --> Now, the next allocation for size A/B will allocate object A, which
2927         has a slightly wrong idea about where the object actually begins.
2928         Immediately, you'll corrupt a little memory, and over time, you'll also
2929         corrupt boundary tag metadata.
2930
2931         The solution is to store the begin pointer in the boundary tag. Luckily,
2932         this doesn't make the tag any bigger, and it's not a noticeable slowdown
2933         on MallocBench.
2934
2935         * bmalloc/Algorithm.h:
2936         (bmalloc::rightShift):
2937         * bmalloc/BeginTag.h:
2938         (bmalloc::BeginTag::isInFreeList): This is the bug fix. Make sure to
2939         validate the start pointer when popping off the free list. Through a
2940         very uncommon set of steps, it is possible to have an item in the free
2941         list that is valid by all accounts except for its start pointer.
2942
2943         * bmalloc/BoundaryTag.h:
2944         (bmalloc::BoundaryTag::compactBegin):
2945         (bmalloc::BoundaryTag::setRange):
2946         (bmalloc::BoundaryTag::setSize): Deleted. Record a compact version of the
2947         start pointer. We don't need the whole pointer -- just the offset, in
2948         largeAlignment increments, into the relevant boundary tag bucket.
2949
2950         * bmalloc/BoundaryTagInlines.h:
2951         (bmalloc::validateNext):
2952         (bmalloc::BoundaryTag::init):
2953         (bmalloc::BoundaryTag::mergeLarge):
2954         (bmalloc::BoundaryTag::splitLarge):
2955         * bmalloc/SegregatedFreeList.cpp:
2956         (bmalloc::SegregatedFreeList::insert):
2957         (bmalloc::SegregatedFreeList::takeGreedy):
2958         (bmalloc::SegregatedFreeList::take): Provide the whole range instead of
2959         the size when establishing a boundary tag, as required by the new
2960         interface.
2961
2962         * bmalloc/Sizes.h:
2963
2964 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
2965
2966         Fixed a bmalloc crash seen on the EWS bot
2967         https://bugs.webkit.org/show_bug.cgi?id=135955
2968
2969         Reviewed by Andreas Kling.
2970
2971         * bmalloc/Syscall.h: Some CG APIs vm_copy their input buffers. If the
2972         input buffer is a malloc region, that region will get marked Copy-On-Write
2973         by the kernel. Calls to madvise() for COW regions fail and return EINVAL
2974         on older OS X's. In 10.10, they still fail, but they do not return
2975         EINVAL.
2976
2977         So, we can only ASSERT that our syscalls succeed starting with 10.10.
2978
2979 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
2980
2981         Fixed the bmalloc build
2982         https://bugs.webkit.org/show_bug.cgi?id=135953
2983
2984         Reviewed by Andreas Kling.
2985
2986         * bmalloc.xcodeproj/project.pbxproj: Marked a few headers as private.
2987         These headers are used, so they must be available outside the project.
2988
2989 2014-08-13  Daniel Bates  <dabates@apple.com>
2990
2991         Attempt to fix the build following <http://trac.webkit.org/changeset/172576>
2992         (https://bugs.webkit.org/show_bug.cgi?id=135895)
2993
2994         Substitute PerThreadStorage<T>::initSharedKeyIfNeeded() for initSharedKeyIfNeeded() in
2995         implementation of PerThread<T>::getFastCase().
2996
2997         * bmalloc/PerThread.h:
2998         (bmalloc::PerThread<T>::getFastCase):
2999
3000 2014-08-13  Daniel Bates  <dabates@apple.com>
3001
3002         Make bmalloc::PerThread work without C++ thread local storage
3003         https://bugs.webkit.org/show_bug.cgi?id=135895
3004
3005         Reviewed by Geoffrey Garen.
3006
3007         Implement support for building bmalloc without C++ thread local storage.
3008
3009         * bmalloc/BPlatform.h: Remove macro define BPLATFORM_IOS_SIMULATOR. Added macro function
3010         BCOMPILER_SUPPORTS() and macro define BCOMPILER_SUPPORTS_CXX_THREAD_LOCAL that can be used
3011         to determine whether the compiler supports C++ thread local storage.
3012         * bmalloc/PerThread.h:
3013         (bmalloc::PerThreadStorage::get): Modified to call pthread_getspecific() when building
3014         without C++ thread local storage.
3015         (bmalloc::PerThreadStorage::initSharedKeyIfNeeded): Added.
3016         (bmalloc::PerThreadStorage::init): Moved logic to initialize shared Pthread key from here to
3017         PerThreadStorage::initSharedKeyIfNeeded().
3018         (bmalloc::PerThread<T>::getFastCase): Modified to call PerThreadStorage::initSharedKeyIfNeeded()
3019         before querying PerThreadStorage::get() when building without C++ thread local storage so as to
3020         ensure that the shared key has been initialized.
3021         (_pthread_setspecific_direct): Deleted.
3022         (_pthread_getspecific_direct): Deleted.
3023
3024 2014-08-13  Daniel Bates  <dabates@apple.com>
3025
3026         [iOS] Make JavaScriptCore and bmalloc build with the public SDK
3027         https://bugs.webkit.org/show_bug.cgi?id=135848
3028
3029         Reviewed by Geoffrey Garen.
3030
3031         * bmalloc/BPlatform.h: Added macro BPLATFORM_IOS_SIMULATOR, which evaluates to true
3032         when building for the iOS Simulator.
3033         * bmalloc/PerThread.h: Use pthread_machdep.h code path when building for iOS Simulator
3034         using the public SDK.
3035         (_pthread_setspecific_direct): Added; only defined when building for the iOS Simulator
3036         using the public SDK.
3037         (_pthread_getspecific_direct): Added; only defined when building for the iOS Simulator
3038         using the public SDK.
3039
3040 2014-08-12  Daniel Bates  <dabates@apple.com>
3041
3042         BPLATFORM(IOS) always evaluates to false
3043         https://bugs.webkit.org/show_bug.cgi?id=135843
3044
3045         Reviewed by Geoffrey Garen.
3046
3047         Fix typo in definition of BPLATFORM() and include system header TargetConditionals.h
3048         (when building on an Apple platform) so that BPLATFORM(X) evaluates to true when
3049         building for platform X. In particular, so that BPLATFORM(IOS) evaluates to true when
3050         building for iOS.
3051
3052         As a side effect of this change, the change made in <http://trac.webkit.org/changeset/167289>
3053         will be honored and iOS will assume a VM page size of 16kB (again) instead of 4kB.
3054
3055         * bmalloc/BPlatform.h:
3056
3057 2014-08-11  Andy Estes  <aestes@apple.com>
3058
3059         [iOS] Get rid of iOS.xcconfig
3060         https://bugs.webkit.org/show_bug.cgi?id=135809
3061
3062         Reviewed by Joseph Pecoraro.
3063
3064         All iOS.xcconfig did was include AspenFamily.xcconfig, so there's no need for the indirection.
3065
3066         * Configurations/Base.xcconfig:
3067         * Configurations/iOS.xcconfig: Removed.
3068         * bmalloc.xcodeproj/project.pbxproj:
3069
3070 2014-05-01  Dan Bernstein  <mitz@apple.com>
3071
3072         Fixed production builds for the iOS Simulator.
3073         <rdar://problem/16792221>
3074
3075         * Configurations/bmalloc.xcconfig: Include INSTALL_PATH_PREFIX in
3076         PRIVATE_HEADERS_FOLDER_PATH when installing.
3077
3078 2014-04-20  Geoffrey Garen  <ggaren@apple.com>
3079
3080         bmalloc: Segregate pages by objects size
3081         https://bugs.webkit.org/show_bug.cgi?id=131909
3082
3083         Reviewed by Andreas Kling.
3084
3085         2% reduction in memory-at-end on the Membuster memory_warning benchmarks.
3086
3087         * bmalloc/Allocator.cpp:
3088         (bmalloc::Allocator::allocateSlowCase):
3089         * bmalloc/Allocator.h:
3090         (bmalloc::Allocator::allocateFastCase):
3091         (bmalloc::Allocator::smallAllocatorFor): Use the new shared helper
3092         function for size class calculation.
3093
3094         * bmalloc/Deallocator.cpp:
3095         (bmalloc::Deallocator::Deallocator):
3096         (bmalloc::Deallocator::scavenge):
3097         (bmalloc::Deallocator::deallocateSmallLine):
3098         (bmalloc::Deallocator::allocateSmallLine):
3099         * bmalloc/Deallocator.h: Keep a cache for every size class, since the
3100         cache can't be shared anymore.
3101
3102         * bmalloc/Heap.cpp:
3103         (bmalloc::Heap::allocateSmallLineSlowCase):
3104         * bmalloc/Heap.h:
3105         (bmalloc::Heap::deallocateSmallLine): Ditto.
3106
3107         (bmalloc::Heap::allocateSmallLine): Check size class in addition to
3108         page refcount when allocating a line because we might have deallocated
3109         the page and the recycled it for another size class.
3110
3111         (bmalloc::Heap::deallocateMediumLine):
3112         (bmalloc::Heap::allocateMediumLine):
3113         * bmalloc/Line.h:
3114         (bmalloc::Line::refCount):
3115         * bmalloc/Page.h:
3116         (bmalloc::Page::refCount):
3117         (bmalloc::Page::smallSizeClass):
3118         (bmalloc::Page::setSmallSizeClass):
3119         (bmalloc::Page<Traits>::refCount): Deleted.
3120         * bmalloc/Sizes.h:
3121         (bmalloc::Sizes::smallSizeClassFor): New shared API for computing
3122         an index into an array from a size.
3123
3124 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
3125
3126         bmalloc: Improved alignment in LargeChunk
3127         https://bugs.webkit.org/show_bug.cgi?id=131895
3128
3129         Reviewed by Andreas Kling.
3130
3131         * bmalloc/Chunk.h:
3132         * bmalloc/LargeChunk.h: Align to vmPageSize just like Chunk does.
3133         Technically, the previous alignment was harmless, but I would prefer,
3134         dear reader, not to have to explain the interlocking set of
3135         circumstances that made it so.
3136
3137 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
3138
3139         Rolled out r167502 because it caused a crash on the facebook benchmark.
3140
3141         Unreviewed.
3142
3143             bmalloc: Added an XSmall line size
3144             https://bugs.webkit.org/show_bug.cgi?id=131851
3145
3146             Reviewed by Sam Weinig.
3147
3148 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
3149
3150         bmalloc: Mutex should be harder to use wrong
3151         https://bugs.webkit.org/show_bug.cgi?id=131879
3152
3153         Reviewed by Andreas Kling.
3154
3155         Mutex now has a proper constructor, so you can't deadlock by forgetting
3156         to initialize it.
3157
3158         * bmalloc.xcodeproj/project.pbxproj:
3159         * bmalloc/Allocator.cpp:
3160         (bmalloc::Allocator::processXSmallAllocatorLog):
3161         (bmalloc::Allocator::processSmallAllocatorLog):
3162         (bmalloc::Allocator::processMediumAllocatorLog):
3163         (bmalloc::Allocator::allocateLarge):
3164         (bmalloc::Allocator::allocateXLarge): Global replace Mutex => StaticMutex,
3165         since the Heap mutex is a static.
3166
3167         * bmalloc/AsyncTask.h:
3168         (bmalloc::Function>::AsyncTask): Use Mutex, since we're not static. No
3169         need for explicit initialization anymore.
3170
3171         * bmalloc/Deallocator.cpp:
3172         (bmalloc::Deallocator::scavenge):
3173         (bmalloc::Deallocator::deallocateLarge):
3174         (bmalloc::Deallocator::deallocateXLarge):
3175         (bmalloc::Deallocator::processObjectLog):
3176         (bmalloc::Deallocator::deallocateSmallLine):
3177         (bmalloc::Deallocator::deallocateXSmallLine):
3178         (bmalloc::Deallocator::allocateSmallLine):
3179         (bmalloc::Deallocator::allocateXSmallLine):
3180         (bmalloc::Deallocator::deallocateMediumLine):
3181         (bmalloc::Deallocator::allocateMediumLine):
3182         * bmalloc/Deallocator.h:
3183         * bmalloc/Heap.cpp:
3184         (bmalloc::sleep):
3185         (bmalloc::Heap::Heap):
3186         (bmalloc::Heap::concurrentScavenge):
3187         (bmalloc::Heap::scavenge):
3188         (bmalloc::Heap::scavengeSmallPages):
3189         (bmalloc::Heap::scavengeXSmallPages):
3190         (bmalloc::Heap::scavengeMediumPages):
3191         (bmalloc::Heap::scavengeLargeRanges):
3192         (bmalloc::Heap::allocateXSmallLineSlowCase):
3193         (bmalloc::Heap::allocateSmallLineSlowCase):
3194         (bmalloc::Heap::allocateMediumLineSlowCase):
3195         (bmalloc::Heap::allocateXLarge):
3196         (bmalloc::Heap::deallocateXLarge):
3197         (bmalloc::Heap::allocateLarge):
3198         (bmalloc::Heap::deallocateLarge):
3199         * bmalloc/Heap.h:
3200         (bmalloc::Heap::deallocateXSmallLine):
3201         (bmalloc::Heap::allocateXSmallLine):
3202         (bmalloc::Heap::deallocateSmallLine):
3203         (bmalloc::Heap::allocateSmallLine):
3204         (bmalloc::Heap::deallocateMediumLine):
3205         (bmalloc::Heap::allocateMediumLine):
3206         * bmalloc/Line.h:
3207         (bmalloc::Line<Traits>::deref):
3208         * bmalloc/Mutex.cpp: Removed.
3209         * bmalloc/Mutex.h:
3210         (bmalloc::Mutex::Mutex):
3211         (bmalloc::Mutex::init): Deleted.
3212         (bmalloc::Mutex::try_lock): Deleted.
3213         (bmalloc::Mutex::lock): Deleted.
3214         (bmalloc::Mutex::unlock): Deleted.
3215         * bmalloc/Page.h:
3216         (bmalloc::Page<Traits>::ref):
3217         (bmalloc::Page<Traits>::deref):
3218         (bmalloc::Page<Traits>::refCount):
3219         * bmalloc/PerProcess.h:
3220         (bmalloc::PerProcess::mutex):
3221         (bmalloc::PerProcess<T>::getSlowCase):
3222         * bmalloc/StaticMutex.cpp: Added.
3223         (bmalloc::StaticMutex::lockSlowCase):
3224         * bmalloc/StaticMutex.h: Added.
3225         (bmalloc::StaticMutex::init):
3226         (bmalloc::StaticMutex::try_lock):
3227         (bmalloc::StaticMutex::lock):
3228         (bmalloc::StaticMutex::unlock):
3229         * bmalloc/VMHeap.h:
3230         (bmalloc::VMHeap::deallocateXSmallPage):
3231         (bmalloc::VMHeap::deallocateSmallPage):
3232         (bmalloc::VMHeap::deallocateMediumPage):
3233         (bmalloc::VMHeap::deallocateLargeRange):
3234         * bmalloc/bmalloc.h:
3235         (bmalloc::api::scavenge): Global replace Mutex => StaticMutex,
3236         since the Heap mutex is a static.
3237
3238 2014-04-18  Geoffrey Garen  <ggaren@apple.com>
3239
3240         bmalloc: AsyncTask should use Mutex instead of std::mutex
3241         https://bugs.webkit.org/show_bug.cgi?id=131865
3242
3243         Reviewed by Gavin Barraclough.
3244
3245         std::mutex is so slow that it makes parallelizing simple tasks through
3246         AsyncTask a net regression. Mutex fixes this.
3247
3248         * bmalloc/AsyncTask.h:
3249         (bmalloc::Function>::AsyncTask):
3250         (bmalloc::Function>::join):
3251         (bmalloc::Function>::runSlowCase):
3252         (bmalloc::Function>::entryPoint):
3253         * bmalloc/Mutex.h:
3254         (bmalloc::Mutex::init):
3255
3256 2014-04-18  Geoffrey Garen  <ggaren@apple.com>
3257
3258         bmalloc: Added an XSmall line size
3259         https://bugs.webkit.org/show_bug.cgi?id=131851
3260
3261         Reviewed by Sam Weinig.
3262
3263         Reduces malloc footprint on Membuster recordings by 10%.
3264
3265         This is a throughput regression, but we're still way ahead of TCMalloc.
3266         I have some ideas for how to recover the regression -- but I wanted to
3267         get this win in first.
3268
3269         Full set of benchmark results:
3270
3271                 bmalloc> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks --measure-heap nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
3272                                                                                                 
3273                                                                nopatch                      patch                                Δ
3274                 Peak Memory:
3275                     reddit_memory_warning                      7,896kB                    7,532kB                  ^ 1.05x smaller
3276                     flickr_memory_warning                     12,968kB                   12,324kB                  ^ 1.05x smaller
3277                     theverge_memory_warning                   16,672kB                   15,200kB                   ^ 1.1x smaller
3278
3279                     <geometric mean>                          11,952kB                   11,216kB                  ^ 1.07x smaller
3280                     <arithmetic mean>                         12,512kB                   11,685kB                  ^ 1.07x smaller
3281                     <harmonic mean>                           11,375kB                   10,726kB                  ^ 1.06x smaller
3282
3283                 Memory at End:
3284                     reddit_memory_warning                      7,320kB                    6,856kB                  ^ 1.07x smaller
3285                     flickr_memory_warning                     10,848kB                    9,692kB                  ^ 1.12x smaller
3286                     theverge_memory_warning                   16,380kB                   14,872kB                   ^ 1.1x smaller
3287
3288                     <geometric mean>                          10,916kB                    9,961kB                   ^ 1.1x smaller
3289                     <arithmetic mean>                         11,516kB                   10,473kB                   ^ 1.1x smaller
3290                     <harmonic mean>                           10,350kB                    9,485kB                  ^ 1.09x smaller
3291
3292                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
3293                                                                                                 
3294                                                    nopatch                patch                         Δ
3295                 Execution Time:
3296                     churn                            127ms                151ms            ! 1.19x slower
3297                     list_allocate                    130ms                164ms            ! 1.26x slower
3298                     tree_allocate                    109ms                127ms            ! 1.17x slower
3299                     tree_churn                       115ms                120ms            ! 1.04x slower
3300                     facebook                         240ms                259ms            ! 1.08x slower
3301                     fragment                          91ms                131ms            ! 1.44x slower
3302                     fragment_iterate                 105ms                106ms            ! 1.01x slower
3303                     message_one                      260ms                259ms             ^ 1.0x faster
3304                     message_many                     149ms                154ms            ! 1.03x slower
3305                     medium                           194ms                248ms            ! 1.28x slower
3306                     big                              157ms                160ms            ! 1.02x slower
3307
3308                     <geometric mean>                 144ms                163ms            ! 1.13x slower
3309                     <arithmetic mean>                152ms                171ms            ! 1.12x slower
3310                     <harmonic mean>                  137ms                156ms            ! 1.14x slower
3311
3312                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
3313                                                                                                 
3314                                                                        nopatch                          patch                                     Δ
3315                 Execution Time:
3316                     churn                                                126ms                          148ms                        ! 1.17x slower
3317                     churn --parallel                                      62ms                           76ms                        ! 1.23x slower
3318                     list_allocate                                        130ms                          164ms                        ! 1.26x slower
3319                     list_allocate --parallel                             120ms                          175ms                        ! 1.46x slower
3320                     tree_allocate                                        111ms                          127ms                        ! 1.14x slower
3321                     tree_allocate --parallel                              95ms                          135ms                        ! 1.42x slower
3322                     tree_churn                                           115ms                          124ms                        ! 1.08x slower
3323                     tree_churn --parallel                                107ms                          126ms                        ! 1.18x slower
3324                     facebook                                             240ms                          276ms                        ! 1.15x slower
3325                     facebook --parallel                                  802ms                        1,088ms                        ! 1.36x slower
3326                     fragment                                              92ms                          130ms                        ! 1.41x slower
3327                     fragment --parallel                                   66ms                          124ms                        ! 1.88x slower
3328                     fragment_iterate                                     109ms                          127ms                        ! 1.17x slower
3329                     fragment_iterate --parallel                           55ms                           64ms                        ! 1.16x slower
3330                     message_one                                          260ms                          260ms                                      
3331                     message_many                                         170ms                          238ms                         ! 1.4x slower
3332                     medium                                               185ms                          250ms                        ! 1.35x slower
3333                     medium --parallel                                    210ms                          334ms                        ! 1.59x slower
3334                     big                                                  150ms                          169ms                        ! 1.13x slower
3335                     big --parallel                                       138ms                          144ms                        ! 1.04x slower
3336
3337                     <geometric mean>                                     135ms                          170ms                        ! 1.26x slower
3338                     <arithmetic mean>                                    167ms                          214ms                        ! 1.28x slower
3339                     <harmonic mean>                                      117ms                          148ms                        ! 1.26x slower
3340
3341                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
3342
3343                                                                     TC                      patch                                Δ
3344                 Peak Memory:
3345                     reddit_memory_warning                     13,836kB                   13,436kB                  ^ 1.03x smaller
3346                     flickr_memory_warning                     24,868kB                   25,188kB                   ! 1.01x bigger
3347                     theverge_memory_warning                   24,504kB                   26,636kB                   ! 1.09x bigger
3348
3349                     <geometric mean>                          20,353kB                   20,812kB                   ! 1.02x bigger
3350                     <arithmetic mean>                         21,069kB                   21,753kB                   ! 1.03x bigger
3351                     <harmonic mean>                           19,570kB                   19,780kB                   ! 1.01x bigger
3352
3353                 Memory at End:
3354                     reddit_memory_warning                      8,656kB                   10,016kB                   ! 1.16x bigger
3355                     flickr_memory_warning                     11,844kB                   13,784kB                   ! 1.16x bigger
3356                     theverge_memory_warning                   18,516kB                   22,748kB                   ! 1.23x bigger
3357
3358                     <geometric mean>                          12,382kB                   14,644kB                   ! 1.18x bigger
3359                     <arithmetic mean>                         13,005kB                   15,516kB                   ! 1.19x bigger
3360                     <harmonic mean>                           11,813kB                   13,867kB                   ! 1.17x bigger
3361
3362                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
3363                                                                                                 
3364                                                         TC                patch                         Δ
3365                 Execution Time:
3366                     churn                            416ms                148ms            ^ 2.81x faster
3367                     list_allocate                    463ms                164ms            ^ 2.82x faster
3368                     tree_allocate                    292ms                127ms             ^ 2.3x faster
3369                     tree_churn                       157ms                120ms            ^ 1.31x faster
3370                     facebook                         327ms                276ms            ^ 1.18x faster
3371                     fragment                         335ms                129ms             ^ 2.6x faster
3372                     fragment_iterate                 344ms                108ms            ^ 3.19x faster
3373                     message_one                      386ms                258ms             ^ 1.5x faster
3374                     message_many                     410ms                154ms            ^ 2.66x faster
3375                     medium                           391ms                245ms             ^ 1.6x faster
3376                     big                              261ms                167ms            ^ 1.56x faster
3377
3378                     <geometric mean>                 332ms                164ms            ^ 2.02x faster
3379                     <arithmetic mean>                344ms                172ms            ^ 1.99x faster
3380                     <harmonic mean>                  317ms                157ms            ^ 2.02x faster
3381
3382         * bmalloc.xcodeproj/project.pbxproj:
3383         * bmalloc/Allocator.cpp:
3384         (bmalloc::Allocator::Allocator): Don't assume that each allocator's
3385         index corresponds with its size. Instead, use the size selection function
3386         explicitly. Now that we have XSmall, some small allocator entries are
3387         unused.
3388
3389         (bmalloc::Allocator::scavenge):
3390         (bmalloc::Allocator::log):
3391         (bmalloc::Allocator::processXSmallAllocatorLog):
3392         (bmalloc::Allocator::allocateSlowCase):
3393         * bmalloc/Allocator.h:
3394         (bmalloc::Allocator::xSmallAllocatorFor):
3395         (bmalloc::Allocator::allocateFastCase):
3396         * bmalloc/Chunk.h:
3397         * bmalloc/Deallocator.cpp:
3398         (bmalloc::Deallocator::scavenge):
3399         (bmalloc::Deallocator::processObjectLog):
3400         (bmalloc::Deallocator::deallocateSlowCase):
3401         (bmalloc::Deallocator::deallocateXSmallLine):
3402         (bmalloc::Deallocator::allocateXSmallLine):
3403         * bmalloc/Deallocator.h:
3404         (bmalloc::Deallocator::deallocateFastCase):
3405         * bmalloc/Heap.cpp:
3406         (bmalloc::Heap::scavenge):
3407         (bmalloc::Heap::scavengeXSmallPages):
3408         (bmalloc::Heap::allocateXSmallLineSlowCase):
3409         * bmalloc/Heap.h:
3410         (bmalloc::Heap::deallocateXSmallLine):
3411         (bmalloc::Heap::allocateXSmallLine):
3412         * bmalloc/LargeChunk.h:
3413         (bmalloc::LargeChunk::get):
3414         (bmalloc::LargeChunk::endTag):
3415         * bmalloc/Line.h:
3416         * bmalloc/MediumAllocator.h:
3417         (bmalloc::MediumAllocator::allocate):
3418         (bmalloc::MediumAllocator::refill):
3419         * bmalloc/ObjectType.cpp:
3420         (bmalloc::objectType):
3421         * bmalloc/ObjectType.h:
3422         (bmalloc::isXSmall):
3423         (bmalloc::isSmall):
3424         (bmalloc::isMedium):
3425         (bmalloc::isLarge):
3426         (bmalloc::isSmallOrMedium): Deleted.
3427         * bmalloc/SegregatedFreeList.h: I boiler-plate copied existing code for
3428         handling small objects. There's probably a reasonable way to share this
3429         code in the future -- I'll look into that once it's stopped changing.
3430
3431         * bmalloc/Sizes.h: Tweaked size classes to make Membuster happy. This
3432         is the main reason things got slower.
3433
3434         * bmalloc/SmallAllocator.h:
3435         (bmalloc::SmallAllocator::allocate):
3436         * bmalloc/SmallTraits.h:
3437         * bmalloc/VMHeap.cpp:
3438         (bmalloc::VMHeap::allocateXSmallChunk):
3439         * bmalloc/VMHeap.h:
3440         (bmalloc::VMHeap::allocateXSmallPage):
3441         (bmalloc::VMHeap::deallocateXSmallPage):
3442         * bmalloc/XSmallAllocator.h: Added.
3443         (bmalloc::XSmallAllocator::isNull):
3444         (bmalloc::XSmallAllocator::canAllocate):
3445         (bmalloc::XSmallAllocator::XSmallAllocator):
3446         (bmalloc::XSmallAllocator::line):
3447         (bmalloc::XSmallAllocator::allocate):
3448         (bmalloc::XSmallAllocator::objectCount):
3449         (bmalloc::XSmallAllocator::derefCount):
3450         (bmalloc::XSmallAllocator::refill):
3451         * bmalloc/XSmallChunk.h: Added.
3452         * bmalloc/XSmallLine.h: Added.
3453         * bmalloc/XSmallPage.h: Added.
3454         * bmalloc/XSmallTraits.h: Added.
3455         * bmalloc/bmalloc.h:
3456         (bmalloc::api::realloc): Boiler-plate copy, as above.
3457
3458 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
3459
3460         MallocBench should scavenge explicitly instead of waiting
3461         https://bugs.webkit.org/show_bug.cgi?id=131661
3462
3463         Reviewed by Andreas Kling.
3464
3465         Added explicit scavenge support to bmalloc. This isn't a memory win,
3466         since bmalloc's per-thread cache is so small. But it makes testing
3467         simpler.
3468
3469         * bmalloc/Allocator.cpp:
3470         (bmalloc::Allocator::~Allocator):
3471         (bmalloc::Allocator::scavenge):
3472         * bmalloc/Allocator.h:
3473         * bmalloc/Cache.cpp:
3474         (bmalloc::Cache::operator new):
3475         (bmalloc::Cache::operator delete):
3476         (bmalloc::Cache::Cache):
3477         (bmalloc::Cache::scavenge):
3478         * bmalloc/Cache.h:
3479         * bmalloc/Deallocator.cpp:
3480         (bmalloc::Deallocator::~Deallocator):
3481         (bmalloc::Deallocator::scavenge):
3482         * bmalloc/Deallocator.h: Factored existing scavenging code into helper
3483         functions, for reuse.
3484
3485         * bmalloc/Heap.cpp:
3486         (bmalloc::sleep):
3487         (bmalloc::Heap::concurrentScavenge):
3488         (bmalloc::Heap::scavenge):
3489         (bmalloc::Heap::scavengeSmallPages):
3490         (bmalloc::Heap::scavengeMediumPages):
3491         (bmalloc::Heap::scavengeLargeRanges):
3492         * bmalloc/Heap.h: Made scavenge sleep duration a parameter. Forced
3493         scavenging -- in response to a benchmark or a low memory warning --
3494         wants to complete as soon as possible, so its sleep duration is 0.
3495
3496         * bmalloc/bmalloc.h:
3497         (bmalloc::api::scavenge):
3498         * bmalloc/mbmalloc.cpp: Exported the scavenge API for MallocBench's use.
3499
3500 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
3501
3502         Use 4kB pages on Mac
3503         https://bugs.webkit.org/show_bug.cgi?id=131658
3504
3505         Reviewed by Sam Weinig.
3506
3507         This reduces memory use a lot on Membuster:
3508
3509                                                                   base                      patch                                Δ
3510                 Execution Time:
3511                     reddit_memory_warning                         18ms                       17ms                   ^ 1.06x faster
3512                     flickr_memory_warning                         34ms                       36ms                   ! 1.06x slower
3513                     theverge_memory_warning                       39ms                       41ms                   ! 1.05x slower
3514
3515                     <geometric mean>                              29ms                       29ms                   ! 1.02x slower
3516                     <arithmetic mean>                             30ms                       31ms                   ! 1.03x slower
3517                     <harmonic mean>                               27ms                       27ms                    ^ 1.0x faster
3518
3519                 Peak Memory:
3520                     reddit_memory_warning                     16,412kB                   16,436kB                    ! 1.0x bigger
3521                     flickr_memory_warning                     30,120kB                   30,184kB                    ! 1.0x bigger
3522                     theverge_memory_warning                   33,408kB                   33,420kB                    ! 1.0x bigger
3523
3524                     <geometric mean>                          25,466kB                   25,499kB                    ! 1.0x bigger
3525                     <arithmetic mean>                         26,647kB                   26,680kB                    ! 1.0x bigger
3526                     <harmonic mean>                           24,181kB                   24,214kB                    ! 1.0x bigger
3527
3528                 Memory at End:
3529                     reddit_memory_warning                      2,404kB                    1,920kB                  ^ 1.25x smaller
3530                     flickr_memory_warning                      3,764kB                    3,072kB                  ^ 1.23x smaller
3531                     theverge_memory_warning                    3,648kB                    3,132kB                  ^ 1.16x smaller
3532
3533                     <geometric mean>                           3,208kB                    2,644kB                  ^ 1.21x smaller
3534                     <arithmetic mean>                          3,272kB                    2,708kB                  ^ 1.21x smaller
3535                     <harmonic mean>                            3,139kB                    2,574kB                  ^ 1.22x smaller
3536
3537
3538         * bmalloc.xcodeproj/project.pbxproj:
3539         * bmalloc/BPlatform.h: Added.
3540         * bmalloc/VMAllocate.h: Only use 16kB pages on iOS because the page size
3541         is 4kB on Mac.
3542
3543 2014-04-14  Alexey Proskuryakov  <ap@apple.com>
3544
3545         Fixed svn:ignore on bmalloc.xcodeproj, it had erroneous leading spaces.
3546
3547         * bmalloc.xcodeproj: Modified property svn:ignore.
3548
3549 2014-04-13  Geoffrey Garen  <ggaren@apple.com>
3550
3551         Fixed some mbmalloc exports
3552         https://bugs.webkit.org/show_bug.cgi?id=131599
3553
3554         Reviewed by Ryosuke Niwa.
3555
3556         * bmalloc.xcodeproj/project.pbxproj: Made some headers a private part
3557         of the project, so we can call them from API.
3558
3559         * bmalloc/mbmalloc.cpp: Marked the mbmalloc functions with default
3560         visibility, so they show up as exported in the .dylib.
3561
3562 2014-04-09  Geoffrey Garen  <ggaren@apple.com>
3563
3564         Put bmalloc headers in the right place
3565         https://bugs.webkit.org/show_bug.cgi?id=131464
3566
3567         Reviewed by Mark Rowe.
3568
3569         * Configurations/bmalloc.xcconfig: Set PRIVATE_HEADERS_FOLDER_PATH to
3570         specify that we don't just want to dump all of our generically-named
3571         headers into /usr/local/include.
3572
3573 2014-04-08  Geoffrey Garen  <ggaren@apple.com>
3574
3575         Made bmalloc more #include friendly
3576         https://bugs.webkit.org/show_bug.cgi?id=131386
3577
3578         Reviewed by Andreas Kling.
3579
3580         Marked a bunch of headers private so they can be used from client code
3581         that #includes bmalloc.h.
3582
3583         Renamed ASSERT macros to BASSERT. This matches their header, which already
3584         had to be renamed, and fixes conflicts with WTF's ASSERT macros.
3585
3586         * bmalloc.xcodeproj/project.pbxproj:
3587         * bmalloc/Allocator.cpp:
3588         (bmalloc::Allocator::allocateSlowCase):
3589         * bmalloc/AsyncTask.h:
3590         (bmalloc::Function>::runSlowCase):
3591         * bmalloc/BAssert.h:
3592         * bmalloc/BoundaryTag.h:
3593         (bmalloc::BoundaryTag::setSize):
3594         * bmalloc/BoundaryTagInlines.h:
3595         (bmalloc::validate):
3596         (bmalloc::BoundaryTag::init):
3597         (bmalloc::BoundaryTag::deallocate):
3598         (bmalloc::BoundaryTag::splitLarge):
3599         (bmalloc::BoundaryTag::allocate):
3600         * bmalloc/Chunk.h:
3601         * bmalloc/Deallocator.cpp:
3602         (bmalloc::Deallocator::processObjectLog):
3603         (bmalloc::Deallocator::deallocateSlowCase):
3604         * bmalloc/Deallocator.h:
3605         (bmalloc::Deallocator::deallocateFastCase):
3606         * bmalloc/FixedVector.h:
3607         (bmalloc::Capacity>::operator):
3608         (bmalloc::Capacity>::push):
3609         (bmalloc::Capacity>::pop):
3610         (bmalloc::Capacity>::shrink):
3611         * bmalloc/Heap.cpp:
3612         (bmalloc::Heap::allocateLarge):
3613         * bmalloc/LargeChunk.h:
3614         (bmalloc::LargeChunk::get):
3615         (bmalloc::LargeChunk::endTag):
3616         * bmalloc/Line.h:
3617         (bmalloc::Line<Traits>::concurrentRef):
3618         (bmalloc::Line<Traits>::deref):
3619         * bmalloc/MediumAllocator.h:
3620         (bmalloc::MediumAllocator::allocate):
3621         * bmalloc/ObjectType.h:
3622         (bmalloc::isSmall):
3623         * bmalloc/Page.h:
3624         (bmalloc::Page<Traits>::ref):
3625         (bmalloc::Page<Traits>::deref):
3626         * bmalloc/PerThread.h:
3627         (bmalloc::PerThread<T>::getSlowCase):
3628         * bmalloc/SegregatedFreeList.cpp:
3629         (bmalloc::SegregatedFreeList::SegregatedFreeList):
3630         (bmalloc::SegregatedFreeList::insert):
3631         * bmalloc/SmallAllocator.h:
3632         (bmalloc::SmallAllocator::allocate):
3633         (bmalloc::SmallAllocator::refill):
3634         * bmalloc/Syscall.h:
3635         * bmalloc/VMAllocate.h:
3636         (bmalloc::vmValidate):
3637         (bmalloc::vmAllocate):
3638         (bmalloc::vmDeallocatePhysicalPagesSloppy):
3639         * bmalloc/Vector.h:
3640         (bmalloc::Vector<T>::operator):
3641         (bmalloc::Vector<T>::pop):
3642         (bmalloc::Vector<T>::shrink):
3643         * bmalloc/XLargeChunk.h:
3644         (bmalloc::XLargeChunk::range):
3645         (bmalloc::XLargeChunk::size):
3646
3647 2014-04-08  Geoffrey Garen  <ggaren@apple.com>
3648
3649         Removed an unused file.
3650
3651         Unreviewed.
3652
3653         * bmalloc/AsyncTask.cpp: Removed.
3654
3655 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
3656
3657         Build bmalloc on Mac
3658         https://bugs.webkit.org/show_bug.cgi?id=131333
3659
3660         Reviewed by Mark Rowe.
3661
3662         * Makefile: Added. For make clients.
3663
3664         These files are required for building any project in WebKit. I copied
3665         them from WTF:
3666         * Configurations: Added.
3667         * Configurations/Base.xcconfig: Added.
3668         * Configurations/DebugRelease.xcconfig: Added.
3669         * Configurations/bmalloc.xcconfig: Added.
3670         * Configurations/iOS.xcconfig: Added.
3671         * Configurations/mbmalloc.xcconfig: Added.
3672
3673         * bmalloc.xcodeproj/project.pbxproj: I removed per-project-file stuff
3674         from here because everything is in .xcconfig files now.
3675
3676         I had to fix a bunch of minor warnings, since they're enabled in our
3677         .xcconfig files:
3678
3679         * bmalloc/AsyncTask.h:
3680         (bmalloc::Function>::AsyncTask):
3681         * bmalloc/BAssert.h:
3682         * bmalloc/BoundaryTagInlines.h:
3683         (bmalloc::validate):
3684         * bmalloc/Heap.cpp:
3685         (bmalloc::Heap::Heap):
3686         (bmalloc::Heap::allocateLarge):
3687         (bmalloc::Heap::deallocateLarge):
3688         * bmalloc/Mutex.h:
3689         (bmalloc::Mutex::Mutex): Deleted.
3690         * bmalloc/VMAllocate.h:
3691         (bmalloc::vmValidate):
3692         * bmalloc/mbmalloc.cpp:
3693
3694 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
3695
3696         bmalloc: Fixed a leak in the per-thread cache
3697         https://bugs.webkit.org/show_bug.cgi?id=131330
3698
3699         Reviewed by Andreas Kling.
3700
3701         Remember to deallocate our line caches upon thread exit.
3702
3703         * bmalloc/Deallocator.cpp:
3704         (bmalloc::Deallocator::~Deallocator):
3705
3706 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
3707
3708         bmalloc: rolled out the tryLock experiment
3709         https://bugs.webkit.org/show_bug.cgi?id=131328
3710
3711         Reviewed by Andreas Kling.
3712
3713         It wasn't a speedup.
3714
3715         * bmalloc.xcodeproj/project.pbxproj:
3716         * bmalloc/Allocator.cpp:
3717         (bmalloc::Allocator::processSmallAllocatorLog):
3718         (bmalloc::Allocator::processMediumAllocatorLog):
3719         * bmalloc/Deallocator.cpp:
3720         (bmalloc::Deallocator::processObjectLog):
3721         (bmalloc::Deallocator::deallocateSlowCase):
3722         (bmalloc::Deallocator::deallocateSmallLine):
3723         (bmalloc::Deallocator::deallocateMediumLine):
3724         * bmalloc/Deallocator.h:
3725         (bmalloc::Deallocator::deallocateFastCase):
3726         * bmalloc/Heap.h:
3727         (bmalloc::Heap::deallocateSmallLine):
3728         (bmalloc::Heap::deallocateMediumLine):
3729         * bmalloc/Line.h:
3730         (bmalloc::Line<Traits>::deref):
3731         * bmalloc/Page.h:
3732         (bmalloc::Page<Traits>::deref):
3733
3734 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
3735
3736         bmalloc
3737         https://bugs.webkit.org/show_bug.cgi?id=131170
3738
3739         Reviewed by Andreas Kling.
3740
3741         Initial commit.
3742
3743         * bmalloc: Added.
3744         * bmalloc.xcodeproj: Added.
3745         * bmalloc.xcodeproj/project.pbxproj: Added.
3746         * bmalloc/Algorithm.h: Added.
3747         (bmalloc::max):
3748         (bmalloc::min):
3749         (bmalloc::mask):
3750         (bmalloc::test):
3751         (bmalloc::roundUpToMultipleOf):
3752         (bmalloc::roundDownToMultipleOf):
3753         (bmalloc::sizeOf):
3754         (bmalloc::bitCount):
3755         (bmalloc::isPowerOfTwo):
3756         * bmalloc/Allocator.cpp: Added.
3757         (bmalloc::Allocator::Allocator):
3758         (bmalloc::Allocator::~Allocator):
3759         (bmalloc::Allocator::log):
3760         (bmalloc::Allocator::processSmallAllocatorLog):
3761         (bmalloc::Allocator::processMediumAllocatorLog):
3762         (bmalloc::Allocator::allocateLarge):
3763         (bmalloc::Allocator::allocateXLarge):
3764         (bmalloc::Allocator::allocateMedium):
3765         (bmalloc::Allocator::allocateSlowCase):
3766         * bmalloc/Allocator.h: Added.
3767         (bmalloc::Allocator::smallAllocatorFor):
3768         (bmalloc::Allocator::allocateFastCase):
3769         (bmalloc::Allocator::allocate):
3770         * bmalloc/AsyncTask.cpp: Added.
3771         (bmalloc::AsyncTask<Function>::runSlowCase):
3772         (bmalloc::AsyncTask<Function>::pthreadEntryPoint):
3773         (bmalloc::AsyncTask<Function>::entryPoint):
3774         * bmalloc/AsyncTask.h: Added.
3775         (bmalloc::Function>::AsyncTask):
3776         (bmalloc::Function>::join):
3777         (bmalloc::Function>::run):
3778         (bmalloc::Function>::runSlowCase):
3779         (bmalloc::Function>::pthreadEntryPoint):
3780         (bmalloc::Function>::entryPoint):
3781         * bmalloc/BAssert.h: Added.
3782         * bmalloc/BeginTag.h: Added.
3783         (bmalloc::BeginTag::isInFreeList):
3784         * bmalloc/BoundaryTag.h: Added.
3785         (bmalloc::BoundaryTag::isXLarge):
3786         (bmalloc::BoundaryTag::setXLarge):
3787         (bmalloc::BoundaryTag::isFree):
3788         (bmalloc::BoundaryTag::setFree):
3789         (bmalloc::BoundaryTag::isEnd):
3790         (bmalloc::BoundaryTag::setEnd):
3791         (bmalloc::BoundaryTag::hasPhysicalPages):
3792         (bmalloc::BoundaryTag::setHasPhysicalPages):
3793         (bmalloc::BoundaryTag::isNull):
3794         (bmalloc::BoundaryTag::clear):
3795         (bmalloc::BoundaryTag::size):
3796         (bmalloc::BoundaryTag::setSize):
3797         (bmalloc::BoundaryTag::prev):
3798         (bmalloc::BoundaryTag::next):
3799         * bmalloc/BoundaryTagInlines.h: Added.
3800         (bmalloc::validate):
3801         (bmalloc::validatePrev):
3802         (bmalloc::validateNext):
3803         (bmalloc::BoundaryTag::init):
3804         (bmalloc::BoundaryTag::mergeLargeLeft):
3805         (bmalloc::BoundaryTag::mergeLargeRight):
3806         (bmalloc::BoundaryTag::mergeLarge):
3807         (bmalloc::BoundaryTag::deallocate):
3808         (bmalloc::BoundaryTag::splitLarge):
3809         (bmalloc::BoundaryTag::allocate):
3810         * bmalloc/Cache.cpp: Added.
3811         (bmalloc::Cache::operator new):
3812         (bmalloc::Cache::operator delete):
3813         (bmalloc::Cache::Cache):
3814         (bmalloc::Cache::allocateSlowCase):
3815         (bmalloc::Cache::allocateSlowCaseNullCache):
3816         (bmalloc::Cache::deallocateSlowCase):
3817         (bmalloc::Cache::deallocateSlowCaseNullCache):
3818         * bmalloc/Cache.h: Added.
3819         (bmalloc::Cache::allocator):
3820         (bmalloc::Cache::deallocator):
3821         (bmalloc::Cache::allocateFastCase):
3822         (bmalloc::Cache::deallocateFastCase):
3823         (bmalloc::Cache::allocate):
3824         (bmalloc::Cache::deallocate):
3825         * bmalloc/Chunk.h: Added.
3826         (bmalloc::Chunk::begin):
3827         (bmalloc::Chunk::end):
3828         (bmalloc::Chunk::lines):
3829         (bmalloc::Chunk::pages):
3830         * bmalloc/Deallocator.cpp: Added.
3831         (bmalloc::Deallocator::Deallocator):
3832         (bmalloc::Deallocator::~Deallocator):
3833         (bmalloc::Deallocator::deallocateLarge):
3834         (bmalloc::Deallocator::deallocateXLarge):
3835         (bmalloc::Deallocator::processObjectLog):
3836         (bmalloc::Deallocator::deallocateSlowCase):
3837         (bmalloc::Deallocator::deallocateSmallLine):
3838         (bmalloc::Deallocator::allocateSmallLine):
3839         (bmalloc::Deallocator::deallocateMediumLine):
3840         (bmalloc::Deallocator::allocateMediumLine):
3841         * bmalloc/Deallocator.h: Added.
3842         (bmalloc::Deallocator::deallocateFastCase):
3843         (bmalloc::Deallocator::deallocate):
3844         * bmalloc/EndTag.h: Added.
3845         (bmalloc::EndTag::operator=):
3846         * bmalloc/FixedVector.h: Added.
3847         (bmalloc::FixedVector::begin):
3848         (bmalloc::FixedVector::end):
3849         (bmalloc::FixedVector::size):
3850         (bmalloc::FixedVector::capacity):
3851         (bmalloc::FixedVector::clear):
3852         (bmalloc::FixedVector::isEmpty):
3853         (bmalloc::Capacity>::FixedVector):
3854         (bmalloc::Capacity>::operator):
3855         (bmalloc::Capacity>::push):
3856         (bmalloc::Capacity>::pop):
3857         (bmalloc::Capacity>::shrink):
3858         * bmalloc/Heap.cpp: Added.
3859         (bmalloc::sleep):
3860         (bmalloc::Heap::Heap):
3861         (bmalloc::Heap::concurrentScavenge):
3862         (bmalloc::Heap::scavengeSmallPages):
3863         (bmalloc::Heap::scavengeMediumPages):
3864         (bmalloc::Heap::scavengeLargeRanges):
3865         (bmalloc::Heap::allocateSmallLineSlowCase):
3866         (bmalloc::Heap::allocateMediumLineSlowCase):
3867         (bmalloc::Heap::allocateXLarge):
3868         (bmalloc::Heap::deallocateXLarge):
3869         (bmalloc::Heap::allocateLarge):
3870         (bmalloc::Heap::deallocateLarge):
3871         * bmalloc/Heap.h: Added.
3872         (bmalloc::Heap::deallocateSmallLine):
3873         (bmalloc::Heap::allocateSmallLine):
3874         (bmalloc::Heap::deallocateMediumLine):
3875         (bmalloc::Heap::allocateMediumLine):
3876         * bmalloc/Inline.h: Added.
3877         * bmalloc/LargeChunk.h: Added.
3878         (bmalloc::LargeChunk::begin):
3879         (bmalloc::LargeChunk::end):
3880         (bmalloc::LargeChunk::create):
3881         (bmalloc::LargeChunk::get):
3882         (bmalloc::LargeChunk::beginTag):
3883         (bmalloc::LargeChunk::endTag):
3884         * bmalloc/Line.h: Added.
3885         (bmalloc::Line<Traits>::begin):
3886         (bmalloc::Line<Traits>::end):
3887         (bmalloc::Line<Traits>::concurrentRef):
3888         (bmalloc::Line<Traits>::deref):
3889         * bmalloc/MediumAllocator.h: Added.
3890         (bmalloc::MediumAllocator::isNull):
3891         (bmalloc::MediumAllocator::MediumAllocator):
3892         (bmalloc::MediumAllocator::line):
3893         (bmalloc::MediumAllocator::allocate):
3894         (bmalloc::MediumAllocator::derefCount):
3895         (bmalloc::MediumAllocator::refill):
3896         * bmalloc/MediumChunk.h: Added.
3897         * bmalloc/MediumLine.h: Added.
3898         * bmalloc/MediumPage.h: Added.