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