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