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