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