Progress towards CMake on Windows and Mac.
[WebKit-https.git] / Source / bmalloc / ChangeLog
1 2015-04-01  Alex Christensen  <achristensen@webkit.org>
2
3         Progress towards CMake on Windows and Mac.
4         https://bugs.webkit.org/show_bug.cgi?id=143293
5
6         Reviewed by Filip Pizlo.
7
8         * bmalloc/BAssert.h:
9         Removed ellipses from macros to appease Visual Studio.
10
11 2015-03-13  Alex Christensen  <achristensen@webkit.org>
12
13         Progress towards CMake on Mac.
14         https://bugs.webkit.org/show_bug.cgi?id=142680
15
16         Reviewed by Gyuyoung Kim.
17
18         * CMakeLists.txt:
19         * PlatformMac.cmake:
20         Added Zone.cpp to Mac CMake builds.
21
22 2015-03-12  Geoffrey Garen  <ggaren@apple.com>
23
24         Assertion failure in bmalloc::LargeObject::validateSelf on Mavericks Debug layout test bot
25         https://bugs.webkit.org/show_bug.cgi?id=142642
26
27         Reviewed by Michael Saboff.
28
29         The typical backtrace to this crash shows the main thread trying to
30         realloc a large string while a DFG compiler thread tries to
31         free a large vector buffer.
32
33         I believe that this is a race condition -- at least in debug builds --
34         since the main thread will try to validate its object's neighbors
35         without holding a lock, even though those neighbors might be in the
36         midst of changing.
37
38         In general, there may be sneaky times when it is valid to look at an
39         object's metadata without holding the heap lock, but it is best not to
40         do so unless we have a really really good reason to.
41
42         * bmalloc/Allocator.cpp:
43         (bmalloc::Allocator::reallocate): Take a lock before reading the metadata
44         for this object, since we generally require any access to shared heap
45         metadata to take a lock.
46
47 2015-03-10  Geoffrey Garen  <ggaren@apple.com>
48
49         bmalloc: tryFastMalloc shouldn't crash
50         https://bugs.webkit.org/show_bug.cgi?id=142443
51
52         Reviewed by Sam Weinig.
53
54         Rolling back in r181307 with a check for whether bmalloc is enabled, to
55         avoid crashes when running with ASan and GuardMalloc.
56
57         * bmalloc/Allocator.cpp:
58         (bmalloc::Allocator::tryAllocate):
59         * bmalloc/Allocator.h:
60         * bmalloc/Cache.cpp:
61         (bmalloc::Cache::tryAllocateSlowCaseNullCache):
62         * bmalloc/Cache.h:
63         (bmalloc::Cache::tryAllocate):
64         * bmalloc/Heap.cpp:
65         (bmalloc::Heap::allocateXLarge):
66         (bmalloc::Heap::tryAllocateXLarge):
67         * bmalloc/Heap.h:
68         * bmalloc/VMAllocate.h:
69         (bmalloc::tryVMAllocate):
70         (bmalloc::vmAllocate):
71         * bmalloc/bmalloc.h:
72         (bmalloc::api::tryMalloc):
73         (bmalloc::api::realloc):
74         (bmalloc::api::free):
75
76 2015-03-09  Commit Queue  <commit-queue@webkit.org>
77
78         Unreviewed, rolling out r181307.
79         https://bugs.webkit.org/show_bug.cgi?id=142525
80
81         Broke ASan tests (Requested by ap on #webkit).
82
83         Reverted changeset:
84
85         "bmalloc: tryFastMalloc shouldn't crash"
86         https://bugs.webkit.org/show_bug.cgi?id=142443
87         http://trac.webkit.org/changeset/181307
88
89 2015-03-09  Geoffrey Garen  <ggaren@apple.com>
90
91         bmalloc: tryFastMalloc shouldn't crash
92         https://bugs.webkit.org/show_bug.cgi?id=142443
93
94         Reviewed by Darin Adler.
95
96         Added support for tryMalloc.
97
98         We assume that non-x-large allocations always succeed, and we crash
99         otherwise, since normal allocation failure will just cause the next
100         non-try allocation or internal metadata allocation to fail, and it's
101         hard and not really useful to keep limping along after that. But
102         extra-large allocations can meaningfully fail, and we can recover.
103
104         * bmalloc/Heap.cpp:
105         (bmalloc::Heap::allocateXLarge):
106         (bmalloc::Heap::tryAllocateXLarge):
107         * bmalloc/Heap.h: Added support for non-crashy x-large allocation.
108
109         * bmalloc/VMAllocate.h:
110         (bmalloc::tryVMAllocate):
111         (bmalloc::vmAllocate): Added support for non-crashy VM allocation.
112
113         * bmalloc/bmalloc.h:
114         (bmalloc::api::tryMalloc):
115         (bmalloc::api::realloc):
116         (bmalloc::api::free): Tried to clarify our behavior with some comments.
117         Unfortunately, calling what we do "malloc" is still not quite right, since
118         malloc returns null on failure and we don't.
119
120 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
121
122         bmalloc: Don't branch when setting the owner of a large object
123         https://bugs.webkit.org/show_bug.cgi?id=142241
124
125         Reviewed by Andreas Kling.
126
127         * bmalloc/BoundaryTag.h:
128         (bmalloc::BoundaryTag::owner):
129         (bmalloc::BoundaryTag::setOwner):
130
131 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
132
133         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
134         https://bugs.webkit.org/show_bug.cgi?id=141802
135
136         Reviewed by Andreas Kling.
137
138         Re-enabled this feature on iOS, now that the iOS crash should be fixed.
139
140         * bmalloc/VMHeap.cpp:
141         (bmalloc::VMHeap::grow):
142         * bmalloc/VMHeap.h:
143
144 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
145
146         bmalloc: Added missing features to the malloc zone introspection API
147         https://bugs.webkit.org/show_bug.cgi?id=142235
148
149         Reviewed by Andreas Kling.
150
151         This should fix the crash we saw on the iOS PLT bot
152         (c.f. http://trac.webkit.org/changeset/180604).
153
154         * bmalloc/Zone.cpp:
155         (bmalloc::good_size):
156         (bmalloc::check):
157         (bmalloc::print):
158         (bmalloc::log):
159         (bmalloc::force_lock):
160         (bmalloc::force_unlock):
161         (bmalloc::statistics):
162         (bmalloc::size):
163         (bmalloc::enumerator): Provide all of these functions since they are called
164         indiscriminately on all zones.
165
166         (bmalloc::Zone::Zone):
167         (bmalloc::Zone::size): Deleted.
168         (bmalloc::Zone::enumerator): Deleted. Moved these functions out of the
169         Zone class since they can stand alone.
170
171         * bmalloc/Zone.h:
172
173 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
174
175         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
176         https://bugs.webkit.org/show_bug.cgi?id=141802
177
178         Reviewed by Andreas Kling.
179
180         Rolling back in but disabled on iOS until I can debug why the iOS PLT crashes.
181
182         * bmalloc/VMHeap.cpp:
183         (bmalloc::VMHeap::grow):
184         * bmalloc/VMHeap.h:
185         * bmalloc/Zone.cpp:
186         (bmalloc::Zone::size):
187         (bmalloc::Zone::Zone):
188         * bmalloc/Zone.h:
189
190 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
191
192         bmalloc: Miscellaneous cleanup
193         https://bugs.webkit.org/show_bug.cgi?id=142231
194
195         Reviewed by Andreas Kling.
196
197         No performance change -- maybe a tiny reduction in memory use.
198
199         * bmalloc/Heap.cpp: Moved the sleep function into StaticMutex, since
200         it's a helper for working with mutexes.
201
202         (bmalloc::Heap::scavenge): Make sure to wait before we start any
203         scavenging, since individual scavenging functions now always scavenge
204         at least one page before waiting themselves.
205
206         (bmalloc::Heap::scavengeSmallPages):
207         (bmalloc::Heap::scavengeMediumPages):
208         (bmalloc::Heap::scavengeLargeObjects): Use the new wait helper to
209         simplify this code. Also, we now require our caller to wait until at
210         least one deallocation is desirable. This simplifies our loop.
211
212         (bmalloc::Heap::allocateSmallPage):
213         (bmalloc::Heap::allocateMediumPage):
214         (bmalloc::Heap::allocateXLarge):
215         (bmalloc::Heap::allocateLarge): Don't freak out any time the heap does
216         an allocation. Only consider the heap to be growing if it actually needs
217         to allocate new VM. This allows us to shrink the heap back down from a
218         high water mark more reliably even if heap activity continues.
219
220         (bmalloc::sleep): Deleted.
221         (bmalloc::Heap::scavengeLargeRanges): Renamed to match our use of
222         "LargeObject".
223
224         * bmalloc/Heap.h:
225
226         * bmalloc/LargeObject.h:
227         (bmalloc::LargeObject::operator bool): Added to simplify a while loop.
228
229         * bmalloc/StaticMutex.h:
230         (bmalloc::sleep):
231         (bmalloc::waitUntilFalse): New helper for waiting until a condition
232         becomes reliably false.
233
234         * bmalloc/Vector.h:
235         (bmalloc::Vector<T>::~Vector): Oops! Don't deallocate the null pointer.
236         We don't actually run any Vector destructors, but an iteration of this
237         patch did, and then crashed. So, let's fix that.
238
239 2015-03-02  Geoffrey Garen  <ggaren@apple.com>
240
241         bmalloc: Eagerly remove allocated objects from the free list
242         https://bugs.webkit.org/show_bug.cgi?id=142194
243
244         Reviewed by Andreas Kling.
245
246         This reduces the pressure to garbage collect the free list.
247
248         Might be a 1% speedup on MallocBench.
249
250         * bmalloc/FreeList.cpp: Put this comment at the top of the file instead
251         of repeating it inside of each function. Tried to clarify the details.
252
253         (bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
254         file for consistency -- even though either direction works fine in this
255         function.
256
257         (bmalloc::FreeList::take): Change to iterate from low to high so that we
258         can maintain an index into the vector that is not disturbed even if we
259         pop from the middle (which invalidates the last index in the vector).
260
261         Decrement i when popping from the middle to make sure that we don't
262         skip the next item after popping.
263
264         (bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.
265
266 2015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
267
268         Fixed a typo in the previous commit.
269
270         * bmalloc/BoundaryTag.h:
271         (bmalloc::BoundaryTag::setOwner):
272
273 2015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
274
275         EFL build fix after r180797.
276
277         * bmalloc/BoundaryTag.h:
278         (bmalloc::BoundaryTag::owner):
279         (bmalloc::BoundaryTag::setOwner):
280
281 2015-02-27  Geoffrey Garen  <ggaren@apple.com>
282
283         bmalloc: Pathological madvise churn on the free(malloc(x)) benchmark
284         https://bugs.webkit.org/show_bug.cgi?id=142058
285
286         Reviewed by Andreas Kling.
287
288         The churn was caused by repeatedly splitting an object with physical
289         pages from an object without, and then merging them back together again.
290         The merge would conservatively forget that we had physical pages, forcing
291         a new call to madvise on the next allocation.
292
293         This patch more strictly segregates objects in the heap from objects in
294         the VM heap, with these changes:
295
296         (1) Objects in the heap are not allowed to merge with objects in the VM
297         heap, and vice versa -- since that would erase our precise knowledge of
298         which physical pages had been allocated.
299
300         (2) The VM heap is exclusively responsible for allocating and deallocating
301         physical pages.
302
303         (3) The heap free list must consider entries for objects that are in the
304         VM heap to be invalid, and vice versa. (This condition can arise
305         because the free list does not eagerly remove items.)
306
307         With these changes, we can know that any valid object in the heap's free
308         list already has physical pages, and does not need to call madvise.
309
310         Note that the VM heap -- as before -- might sometimes contain ranges
311         or pieces of ranges that have physical pages, since we allow splitting
312         of ranges at granularities smaller than the VM page size. These ranges
313         can eventually merge with ranges in the heap during scavenging.
314
315         * bmalloc.xcodeproj/project.pbxproj:
316
317         * bmalloc/BoundaryTag.h:
318         (bmalloc::BoundaryTag::owner):
319         (bmalloc::BoundaryTag::setOwner):
320         (bmalloc::BoundaryTag::initSentinel):
321         (bmalloc::BoundaryTag::hasPhysicalPages): Deleted.
322         (bmalloc::BoundaryTag::setHasPhysicalPages): Deleted. Replaced the concept
323         of "has physical pages" with a bit indicating which heap owns the large
324         object. This is a more precise concept, since the old bit was really a
325         Yes / Maybe bit.
326
327         * bmalloc/Deallocator.cpp:
328
329         * bmalloc/FreeList.cpp: Adopt
330         (bmalloc::FreeList::takeGreedy):
331         (bmalloc::FreeList::take):
332         (bmalloc::FreeList::removeInvalidAndDuplicateEntries):
333         * bmalloc/FreeList.h:
334         (bmalloc::FreeList::push): Added API for considering the owner when
335         deciding if a free list entry is valid.
336
337         * bmalloc/Heap.cpp:
338         (bmalloc::Heap::Heap): Adopt new API.
339
340         (bmalloc::Heap::scavengeLargeRanges): Scavenge all ranges with no minimum,
341         since some ranges might be able to merge with ranges in the VM heap, and
342         they won't be allowed to until we scavenge them.
343
344         (bmalloc::Heap::allocateSmallPage):
345         (bmalloc::Heap::allocateMediumPage):
346         (bmalloc::Heap::allocateLarge): New VM heap API makes this function
347         simpler, since we always get back physical pages now.
348
349         * bmalloc/Heap.h:
350         * bmalloc/LargeObject.h:
351         (bmalloc::LargeObject::end):
352         (bmalloc::LargeObject::owner):
353         (bmalloc::LargeObject::setOwner):
354         (bmalloc::LargeObject::isValidAndFree):
355         (bmalloc::LargeObject::merge): Do not merge objects across heaps since
356         that causes madvise churn.
357         (bmalloc::LargeObject::validateSelf):
358         (bmalloc::LargeObject::init):
359         (bmalloc::LargeObject::hasPhysicalPages): Deleted.
360         (bmalloc::LargeObject::setHasPhysicalPages): Deleted. Propogate the Owner API.
361
362         * bmalloc/Owner.h: Added.
363
364         * bmalloc/SegregatedFreeList.cpp:
365         (bmalloc::SegregatedFreeList::SegregatedFreeList):
366         (bmalloc::SegregatedFreeList::insert):
367         (bmalloc::SegregatedFreeList::takeGreedy):
368         (bmalloc::SegregatedFreeList::take):
369         * bmalloc/SegregatedFreeList.h: Propogate the owner API.
370
371         * bmalloc/VMAllocate.h:
372         (bmalloc::vmDeallocatePhysicalPagesSloppy):
373         (bmalloc::vmAllocatePhysicalPagesSloppy): Clarified these functions and
374         removed an edge case.
375
376         * bmalloc/VMHeap.cpp:
377         (bmalloc::VMHeap::VMHeap):
378         * bmalloc/VMHeap.h:
379         (bmalloc::VMHeap::allocateSmallPage):
380         (bmalloc::VMHeap::allocateMediumPage):
381         (bmalloc::VMHeap::allocateLargeObject):
382         (bmalloc::VMHeap::deallocateLargeObject): Be sure to give each object
383         a new chance to merge, since it might have been prohibited from merging
384         before by virtue of not being in the VM heap.
385
386         (bmalloc::VMHeap::allocateLargeRange): Deleted.
387         (bmalloc::VMHeap::deallocateLargeRange): Deleted.
388
389 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
390
391         bmalloc: Large object free list can grow infinitely
392         https://bugs.webkit.org/show_bug.cgi?id=142055
393
394         Reviewed by Andreas Kling.
395
396         By design, we don't eagerly remove large objects from the free list.
397         This creates two simple pathologies:
398
399             (1) If you free and then allocate the same object repeatedly, it will
400             duplicate itself in the free list repeatedly. Since it is never
401             invalid at the time of allocation, it will never be removed.
402
403             (2) If you split and then merge the same object repeatedly, it will
404             duplicate its split sibling in the free list repeatedly. If its
405             sibling is in a separate free list size class, it will never be
406             consulted at the time of allocation, so it will never be removed.
407
408         So, a simple "while (1) { free(malloc(x)); }" causes infinite memory
409         use in the free list.
410
411         The solution in this patch is a simple helper to remove garbage from the
412         free list if it grows too large. This pathology is not common, so the
413         cost is OK.
414
415         Long-term, perhaps we should rethink the laziness of these free lists.
416
417         * bmalloc/BoundaryTag.h:
418         (bmalloc::BoundaryTag::isMarked):
419         (bmalloc::BoundaryTag::setMarked): New bit, used by free list GC.
420
421         * bmalloc/FreeList.cpp:
422         (bmalloc::FreeList::removeInvalidAndDuplicateEntries): The GC algorithm.
423
424         * bmalloc/FreeList.h:
425         (bmalloc::FreeList::FreeList):
426         (bmalloc::FreeList::push): Invoke the GC if we're getting huge.
427
428         * bmalloc/LargeObject.h:
429         (bmalloc::LargeObject::isMarked):
430         (bmalloc::LargeObject::setMarked):
431         (bmalloc::LargeObject::validateSelf): Expose the new bit.
432
433         * bmalloc/Sizes.h: New constant to control GC frequency.
434
435 2015-02-26  Csaba Osztrogonác  <ossy@webkit.org>
436
437         URTBF after r180693.
438
439         * CMakeLists.txt:
440
441 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
442
443         Try to fix the Mac build.
444
445         Unreviewed.
446
447         * bmalloc.xcodeproj/project.pbxproj: Make FreeList.h available.
448
449 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
450
451         bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
452         https://bugs.webkit.org/show_bug.cgi?id=142049
453
454         Reviewed by Anders Carlsson.
455
456         Split out a FreeList class from SegregatedFreeList. This will make it
457         easier to add behaviors on free list insertion and removal -- and it's
458         probably how I should have designed things at the start.
459
460         Moved BoundaryTag::init into LargeObject, since all the related logic
461         lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.
462
463         * bmalloc.xcodeproj/project.pbxproj:
464         * bmalloc/BoundaryTagInlines.h: Removed.
465         * bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
466         (bmalloc::FreeList::takeGreedy):
467         (bmalloc::FreeList::take):
468         (bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
469         (bmalloc::SegregatedFreeList::insert): Deleted.
470         (bmalloc::SegregatedFreeList::takeGreedy): Deleted.
471         (bmalloc::SegregatedFreeList::take): Deleted.
472         * bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
473         (bmalloc::FreeList::push):
474         * bmalloc/LargeObject.h:
475         (bmalloc::LargeObject::init):
476         * bmalloc/SegregatedFreeList.cpp:
477         (bmalloc::SegregatedFreeList::SegregatedFreeList):
478         (bmalloc::SegregatedFreeList::insert):
479         (bmalloc::SegregatedFreeList::takeGreedy):
480         (bmalloc::SegregatedFreeList::take):
481         * bmalloc/SegregatedFreeList.h:
482         * bmalloc/Sizes.h:
483         * bmalloc/VMHeap.cpp:
484         (bmalloc::VMHeap::grow):
485
486 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
487
488         bmalloc: free up a bit in BoundaryTag
489         https://bugs.webkit.org/show_bug.cgi?id=142048
490
491         Reviewed by Brady Eidson.
492
493         We were wasting a bit by accident, and I need one now.
494
495         * bmalloc/Algorithm.h:
496         (bmalloc::rightShift): Deleted. Not needed, now that I've simplified
497         the math.
498
499         * bmalloc/BoundaryTag.h: Since each boundary tag bucket is 1024 bytes
500         long, the maximum offset into a bucket is 1023.
501
502         You need 5 bits to count up to 1024, but only 4 to count up to 1023.
503         
504         Math is hard.
505
506         (bmalloc::BoundaryTag::compactBegin): Switched to division because it
507         is simpler, and easier to match up with our ASSERT. The compiler will
508         turn division by constant power of two into a shift for us.
509
510         (bmalloc::BoundaryTag::setRange): Added an ASSERT for compactBegin
511         because we do encode it, so we should ASSERT that encoding did not
512         lose information.
513
514         * bmalloc/Sizes.h: Shifting is no longer used since we use division
515         instead.
516
517 2015-02-24  Stephanie Lewis  <slewis@apple.com>
518
519         Rolling out http://trac.webkit.org/changeset/180430 as it causes the PLT to crash.
520         <rdar://problem/19948015>
521
522         Unreviewed.
523
524         * bmalloc/VMHeap.cpp:
525         (bmalloc::VMHeap::grow):
526         * bmalloc/VMHeap.h:
527         * bmalloc/Zone.cpp:
528         (bmalloc::Zone::Zone):
529         (bmalloc::Zone::size): Deleted.
530         * bmalloc/Zone.h:
531
532 2015-02-24  Geoffrey Garen  <ggaren@apple.com>
533
534         bmalloc: Added a little more abstraction for large objects
535         https://bugs.webkit.org/show_bug.cgi?id=141978
536
537         Reviewed by Sam Weinig.
538
539         Previously, each client needed to manage the boundary tags of
540         a large object using free functions. This patch introduces a LargeObject
541         class that does things a little more automatically.
542
543         * bmalloc.xcodeproj/project.pbxproj:
544
545         * bmalloc/Allocator.cpp:
546         (bmalloc::Allocator::reallocate): Use the new LargeObject class.
547
548         * bmalloc/BeginTag.h:
549         (bmalloc::BeginTag::isInFreeList): Deleted. Moved this logic into the
550         LargeObject class.
551
552         * bmalloc/BoundaryTag.h:
553         (bmalloc::BoundaryTag::isSentinel):
554         (bmalloc::BoundaryTag::compactBegin):
555         (bmalloc::BoundaryTag::setRange):
556         (bmalloc::BoundaryTag::initSentinel): Added an explicit API for sentinels,
557         which we used to create and test for implicitly.
558
559         * bmalloc/BoundaryTagInlines.h:
560         (bmalloc::BoundaryTag::init):
561         (bmalloc::validate): Deleted.
562         (bmalloc::validatePrev): Deleted.
563         (bmalloc::validateNext): Deleted.
564         (bmalloc::BoundaryTag::mergeLeft): Deleted.
565         (bmalloc::BoundaryTag::mergeRight): Deleted.
566         (bmalloc::BoundaryTag::merge): Deleted.
567         (bmalloc::BoundaryTag::deallocate): Deleted.
568         (bmalloc::BoundaryTag::split): Deleted.
569         (bmalloc::BoundaryTag::allocate): Deleted. Moved this logic into the
570         LargeObject class.
571
572         * bmalloc/EndTag.h:
573         (bmalloc::EndTag::init):
574         (bmalloc::EndTag::operator=): Deleted. Re-reading this code, I found
575         special behavior in the assignment operator to be a surprising API.
576         So, I replaced the assignment operation with an explicit initializing
577         function.
578
579         * bmalloc/Heap.cpp:
580         (bmalloc::Heap::scavengeLargeRanges):
581         (bmalloc::Heap::allocateXLarge):
582         (bmalloc::Heap::findXLarge):
583         (bmalloc::Heap::deallocateXLarge):
584         (bmalloc::Heap::allocateLarge):
585         (bmalloc::Heap::deallocateLarge):
586         * bmalloc/Heap.h: No behavior changes here -- just adopting the
587         LargeObject interface.
588
589         * bmalloc/LargeObject.h: Added.
590         (bmalloc::LargeObject::operator!):
591         (bmalloc::LargeObject::begin):
592         (bmalloc::LargeObject::size):
593         (bmalloc::LargeObject::range):
594         (bmalloc::LargeObject::LargeObject):
595         (bmalloc::LargeObject::setFree):
596         (bmalloc::LargeObject::isFree):
597         (bmalloc::LargeObject::hasPhysicalPages):
598         (bmalloc::LargeObject::setHasPhysicalPages):
599         (bmalloc::LargeObject::isValidAndFree):
600         (bmalloc::LargeObject::merge):
601         (bmalloc::LargeObject::split):
602         (bmalloc::LargeObject::validateSelf):
603         (bmalloc::LargeObject::validate): Moved this code into a class, out of
604         BoundaryTag free functions.
605
606         New to the class are these features:
607
608             (1) Every reference to an object is validated upon creation and use.
609
610             (2) There's an explicit API for "This is a reference to an object
611             that might be stale (the DoNotValidate API)".
612
613             (3) The begin and end tags are kept in sync automatically.
614
615         * bmalloc/SegregatedFreeList.cpp:
616         (bmalloc::SegregatedFreeList::insert):
617         (bmalloc::SegregatedFreeList::takeGreedy):
618         (bmalloc::SegregatedFreeList::take):
619         * bmalloc/SegregatedFreeList.h: Adopt the LargeObject interface.
620
621         * bmalloc/VMHeap.cpp:
622         (bmalloc::VMHeap::grow):
623         * bmalloc/VMHeap.h:
624         (bmalloc::VMHeap::allocateLargeRange):
625         (bmalloc::VMHeap::deallocateLargeRange): Adopt the LargeObject interface.
626
627 2015-02-20  Geoffrey Garen  <ggaren@apple.com>
628
629         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
630         https://bugs.webkit.org/show_bug.cgi?id=141802
631
632         Reviewed by Andreas Kling.
633
634         Rolling back in with a fix for a crash seen while using GuardMalloc.
635
636         * bmalloc/VMHeap.cpp:
637         (bmalloc::VMHeap::grow):
638         * bmalloc/VMHeap.h:
639         * bmalloc/Zone.cpp: Re-land the old patch.
640
641         (bmalloc::Zone::size): Be sure to implement the size() function since
642         it's accessible indirectly via the malloc_zone_from_ptr public API --
643         and GuardMalloc calls it all the time.
644
645         (bmalloc::Zone::Zone):
646         * bmalloc/Zone.h: Re-land the old patch.
647
648 2015-02-19  Commit Queue  <commit-queue@webkit.org>
649
650         Unreviewed, rolling out r180363.
651         https://bugs.webkit.org/show_bug.cgi?id=141814
652
653         Caused >50 crashes when running LayoutTests in GuardMalloc or
654         ASAN modes. (Requested by jernoble on #webkit).
655
656         Reverted changeset:
657
658         "bmalloc should implement malloc introspection (to stop false-
659         positive leaks when MallocStackLogging is off)"
660         https://bugs.webkit.org/show_bug.cgi?id=141802
661         http://trac.webkit.org/changeset/180363
662
663 2015-02-19  Geoffrey Garen  <ggaren@apple.com>
664
665         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
666         https://bugs.webkit.org/show_bug.cgi?id=141802
667
668         Reviewed by Andreas Kling.
669
670         Fixed a last-minute type.
671
672         The macro is OS, not PLATFORM.
673
674         * bmalloc/VMHeap.cpp:
675         (bmalloc::VMHeap::grow):
676         * bmalloc/VMHeap.h:
677         * bmalloc/Zone.h:
678
679 2015-02-19  Geoffrey Garen  <ggaren@apple.com>
680
681         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
682         https://bugs.webkit.org/show_bug.cgi?id=141802
683
684         Reviewed by Andreas Kling.
685
686         This patch does the bare minimum to stop false positive leaks from
687         being reported by the Darwin leaks tool. We register each super chunk
688         as a single object, and then request that the leaks tool scan it.
689
690         * bmalloc.xcodeproj/project.pbxproj: Added an abstraction for the malloc
691         zone introspection API.
692
693         * bmalloc/Algorithm.h: Missing #include.
694
695         * bmalloc/VMHeap.cpp:
696         (bmalloc::VMHeap::grow):
697         * bmalloc/VMHeap.h: Adopt the new abstraction.
698
699         * bmalloc/Zone.cpp: Added.
700         (bmalloc::remoteRead): Helper for reading an object out of another process.
701         (bmalloc::Zone::enumerator):
702         (bmalloc::Zone::Zone): Register a malloc zone so that we will participate
703         in introspection.
704
705         * bmalloc/Zone.h: Added.
706         (bmalloc::Zone::superChunks):
707         (bmalloc::Zone::addSuperChunk): Use a non-dynamically-allocated vector
708         since our dynamic allocations will not be scanned by leaks since they
709         will have the malloc VM tag.
710
711 2015-02-18  Geoffrey Garen  <ggaren@apple.com>
712
713         bmalloc: VMHeap should keep a record of all of its VM ranges (for malloc introspection)
714         https://bugs.webkit.org/show_bug.cgi?id=141759
715
716         Reviewed by Andreas Kling.
717
718         * bmalloc.xcodeproj/project.pbxproj:
719         * bmalloc/SuperChunk.h: Added.
720         (bmalloc::SuperChunk::create):
721         (bmalloc::SuperChunk::SuperChunk):
722         (bmalloc::SuperChunk::smallChunk):
723         (bmalloc::SuperChunk::mediumChunk):
724         (bmalloc::SuperChunk::largeChunk): Factored out super chunk creation
725         into a separate class, for clarity and type safety.
726
727         * bmalloc/VMHeap.cpp:
728         (bmalloc::VMHeap::grow):
729         (bmalloc::VMHeap::allocateSuperChunk): Renamed "allocateSuperChunk" to
730         "grow" because Andreas found "allocateSuperChunk" to be unclear.
731
732         * bmalloc/VMHeap.h: Track all our VM ranges. We will use this information
733         for malloc introspection.
734
735         (bmalloc::VMHeap::allocateSmallPage):
736         (bmalloc::VMHeap::allocateMediumPage):
737         (bmalloc::VMHeap::allocateLargeRange): Updated for renames.
738
739 2015-02-18  Zan Dobersek  <zdobersek@igalia.com>
740
741         Build bmalloc through CMake as a static library. It's then linked either
742         into the WTF library (if built as a shared library) or into the JSC and
743         WebKit2 libraries. There's no need to build it as a standalone shared library.
744
745         Rubber-stamped by Carlos Garcia Campos.
746
747         * CMakeLists.txt:
748
749 2015-02-13  Gyuyoung Kim  <gyuyoung.kim@samsung.com>
750
751         [BMalloc] Add a FIXME comment for memory alignas
752         https://bugs.webkit.org/show_bug.cgi?id=141556
753
754         Reviewed by Csaba Osztrogonác.
755
756         * bmalloc/Chunk.h: Add a FIXME comment.
757         * bmalloc/LargeChunk.h: ditto.
758
759 2015-02-11  Csaba Osztrogonác  <ossy@webkit.org>
760
761         bmalloc buildfix on 32 bit Linux (x86/ARM)
762         https://bugs.webkit.org/show_bug.cgi?id=141472
763
764         Reviewed by Gyuyoung Kim.
765
766         * bmalloc/Algorithm.h:
767         (bmalloc::roundUpToMultipleOf):
768         * bmalloc/FixedVector.h:
769         (bmalloc::FixedVector::clear):
770         * bmalloc/Sizes.h:
771         (bmalloc::Sizes::sizeClass):
772
773 2015-02-11  Gyuyoung Kim  <gyuyoung.kim@samsung.com>
774
775         [EFL][GTK] Use bmalloc instead of tcmalloc
776         https://bugs.webkit.org/show_bug.cgi?id=140162
777
778         Reviewed by Carlos Garcia Campos.
779
780         Support to use bmalloc on EFL and GTK ports.
781
782         * CMakeLists.txt: Added.
783         * bmalloc/Allocator.cpp:
784         (bmalloc::Allocator::allocate):
785             Fix unused return value caused by posix_memalign().
786         * bmalloc/AsyncTask.h:
787         * bmalloc/BoundaryTag.h:
788         (bmalloc::BoundaryTag::clear):
789         * bmalloc/Chunk.h:
790             Change Traits::Page with Traits::PageType in order to fix
791             -fpermitive build error on EFL and GTK port. 
792         * bmalloc/EndTag.h:
793         (bmalloc::EndTag::operator=):
794         * bmalloc/Line.h: ditto.
795         * bmalloc/MediumTraits.h:
796         * bmalloc/Page.h: ditto.
797         * bmalloc/PerThread.h:
798             EFL port doesn't support __has_include definition yet.
799             Define HAVE_PTHREAD_MACHDEP_H according to check if __has_include is supported.
800         * bmalloc/SmallTraits.h: ditto.
801         * bmalloc/VMAllocate.h:
802         (bmalloc::vmDeallocatePhysicalPages):
803         (bmalloc::vmAllocatePhysicalPages):
804         * bmalloc/Vector.h:
805         (bmalloc::Vector<T>::push):
806         (bmalloc::Vector<T>::reallocateBuffer):
807
808 2015-01-31  Sam Weinig  <sam@webkit.org>
809
810         Remove even more Mountain Lion support
811         https://bugs.webkit.org/show_bug.cgi?id=141124
812
813         Reviewed by Alexey Proskuryakov.
814
815         * Configurations/Base.xcconfig:
816         * Configurations/DebugRelease.xcconfig:
817
818 2015-01-30  Geoffrey Garen  <ggaren@apple.com>
819
820         GC marking threads should clear malloc caches
821         https://bugs.webkit.org/show_bug.cgi?id=141097
822
823         Reviewed by Andreas Kling.
824
825         Split the scavenging API into per-thread vs global, so that you can
826         request to scavenge your own thread without scavenging the whole heap.
827
828         * bmalloc/Cache.cpp:
829         (bmalloc::Cache::scavenge):
830         * bmalloc/bmalloc.h:
831         (bmalloc::api::scavengeThisThread):
832         (bmalloc::api::scavenge):
833
834 2015-01-28  Dana Burkart  <dburkart@apple.com>
835
836         Move ASan flag settings from DebugRelease.xcconfig to Base.xcconfig
837         https://bugs.webkit.org/show_bug.cgi?id=136765
838
839         Reviewed by Alexey Proskuryakov.
840
841         * Configurations/Base.xcconfig:
842         * Configurations/DebugRelease.xcconfig:
843
844 2015-01-21  Geoffrey Garen  <ggaren@apple.com>
845
846         bmalloc: support aligned allocation
847         https://bugs.webkit.org/show_bug.cgi?id=140732
848
849         Reviewed by Andreas Kling.
850
851         * bmalloc/Allocator.cpp:
852         (bmalloc::Allocator::allocate): New function for aligned allocation.
853
854         Small and medium requests just allocate and free until they find an
855         aligned pointer. This is slightly inefficient in the worst case, but
856         still constant-time with little-to-no space overhead.
857
858         Large requests use a new API that requires the client to specify both
859         its ideal size and alignment, and the worst-case size you would have to
860         allocate in order to produce some interior pointer of the requested size
861         and alignment. We put the burden of this calculation on the client
862         because it simplifies things if we guarantee that allocation won't fail.
863
864         XLarge requests are easy: we just forward them to vmAllocate, which
865         already supported aligned requests.
866
867         * bmalloc/BoundaryTag.h:
868         * bmalloc/BoundaryTagInlines.h:
869         (bmalloc::BoundaryTag::mergeLeft):
870         (bmalloc::BoundaryTag::mergeRight):
871         (bmalloc::BoundaryTag::merge):
872         (bmalloc::BoundaryTag::deallocate):
873         (bmalloc::BoundaryTag::split):
874         (bmalloc::BoundaryTag::allocate): No behavior change here. I just
875         refactored the interface to remove some reference out parameters in
876         order to clarify what changes and what doesn't.
877
878         * bmalloc/Heap.cpp:
879         (bmalloc::Heap::allocateXLarge): Added an alignment API.
880
881         (bmalloc::Heap::allocateLarge):
882         * bmalloc/Heap.h: Added an alignment API. I split out allocateLarge into
883         a few variants, so aligned and unaligned allocation could share some code.
884
885         * bmalloc/SegregatedFreeList.cpp:
886         (bmalloc::SegregatedFreeList::take):
887         * bmalloc/SegregatedFreeList.h: Changed to use a separate, explicit API
888         for aligned allocation. It turns out that the aligned path is pretty
889         different, since it ends up searching for two potential ways to satisfy
890         an allocation: either large enough and aligned, or large enough to split
891         into something not aligned and something large enough and aligned.
892
893         * bmalloc/VMAllocate.h:
894         (bmalloc::vmAllocate): Switched alignment to come before size because
895         that's how the memalign API specifies it.
896
897         * bmalloc/VMHeap.h:
898         (bmalloc::VMHeap::allocateLargeRange): Added an alignment API.
899
900 2015-01-20  Geoffrey Garen  <ggaren@apple.com>
901
902         bmalloc: a little bit of cleanup
903         https://bugs.webkit.org/show_bug.cgi?id=140687
904
905         Reviewed by Anders Carlsson.
906
907         * bmalloc/Algorithm.h:
908         (bmalloc::isPowerOfTwo): Added a check for 0, since 0 would break a lot
909         of code.
910
911         * bmalloc/BoundaryTag.h:
912         * bmalloc/BoundaryTagInlines.h:
913         (bmalloc::BoundaryTag::mergeLeft):
914         (bmalloc::BoundaryTag::mergeRight):
915         (bmalloc::BoundaryTag::merge):
916         (bmalloc::BoundaryTag::deallocate):
917         (bmalloc::BoundaryTag::split):
918         (bmalloc::BoundaryTag::allocate):
919         (bmalloc::BoundaryTag::mergeLargeLeft): Deleted.
920         (bmalloc::BoundaryTag::mergeLargeRight): Deleted.
921         (bmalloc::BoundaryTag::mergeLarge): Deleted.
922         (bmalloc::BoundaryTag::splitLarge): Deleted. Removed the word "Large"
923         from all these functions, since boundary tags always pertain to large
924         objects, and putting the word "Large" everywhere wasn't helping to
925         explain that.
926
927         * bmalloc/Heap.cpp:
928         (bmalloc::Heap::allocateXLarge):
929         (bmalloc::Heap::findXLarge):
930         (bmalloc::Heap::deallocateXLarge):
931         * bmalloc/Heap.h:
932         * bmalloc/VMHeap.h:
933         (bmalloc::VMHeap::allocateXLarge): Deleted.
934         (bmalloc::VMHeap::findXLarge): Deleted.
935         (bmalloc::VMHeap::deallocateXLarge): Deleted. Moved XLarge allocation
936         from VMHeap to Heap. Since the purpose of the VMHeap is to cache VM
937         ranges, and the VMHeap never caches any XLarge ranges, it doesn't
938         really make sense for the VMHeap to be involved.
939
940 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
941
942         bmalloc: refactored XLarge allocation for better alignment
943         https://bugs.webkit.org/show_bug.cgi?id=140582
944
945         Reviewed by Andreas Kling.
946
947         XLarge objects used to be Large objects with an extra bit of metadata
948         that said "actually, I'm not large -- I'm extra large".
949
950         The metadata header in an XLarge allocation made it impossible for the
951         XLarge object to honor a very large alignment request.
952
953         The solution is to stop using a metadata header for XLarge objects, and
954         instead to store explicit metadata on the side.
955
956         This is a bit less astonishing, which is also nice.
957
958         Finding XLarge metadata is now a linear search. That's probably OK, since
959         it was always so in TCMalloc, and the usual number of XLarge allocations
960         in a process is 0.
961
962         This design makes it possible for the heap to cache XLarge allocations
963         with and/or without physical pages. I haven't actually done that yet
964         because the tradeoffs are subtle, so I don't want to do anything without
965         a motivating test case.
966
967         * bmalloc.xcodeproj/project.pbxproj:
968         * bmalloc/Allocator.cpp:
969         (bmalloc::Allocator::reallocate): Removed the concept of an XLargeChunk,
970         since an XLarge allocation is now just a naked buffer without a header.
971
972         (bmalloc::Allocator::allocateXLarge): Added an explicit qualifier for
973         XLarge alignment, since XLargeChunk won't give this to us implicitly
974         anymore.
975
976         * bmalloc/BoundaryTag.h:
977         (bmalloc::BoundaryTag::setRange):
978         (bmalloc::BoundaryTag::isXLarge): Deleted.
979         (bmalloc::BoundaryTag::setXLarge): Deleted.
980         * bmalloc/BoundaryTagInlines.h:
981         (bmalloc::validate):
982         (bmalloc::BoundaryTag::deallocate): Removed the XLarge hacks from Large allocations.
983
984         * bmalloc/Deallocator.cpp:
985         (bmalloc::Deallocator::deallocateXLarge):
986         (bmalloc::Deallocator::deallocateSlowCase):
987         * bmalloc/Heap.cpp:
988         (bmalloc::Heap::findXLarge):
989         (bmalloc::Heap::allocateXLarge):
990         (bmalloc::Heap::deallocateXLarge):
991         * bmalloc/Heap.h: Updated for interface changes.
992
993         * bmalloc/ObjectType.cpp:
994         (bmalloc::objectType):
995         * bmalloc/ObjectType.h:
996         (bmalloc::isXLarge): We can now tell if a pointer is XLarge just by
997         examining its bit pattern -- just like we do for other kinds of
998         allocations -- which is nice.
999
1000         * bmalloc/Sizes.h:
1001         * bmalloc/VMHeap.h:
1002         (bmalloc::VMHeap::allocateXLarge):
1003         (bmalloc::VMHeap::findXLarge):
1004         (bmalloc::VMHeap::deallocateXLarge): Keep an explicit vector of metadata
1005         for XLarge allocations.
1006
1007         * bmalloc/XLargeChunk.h: Removed.
1008
1009 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
1010
1011         bmalloc: added some infrastructure for aligned allocation
1012         https://bugs.webkit.org/show_bug.cgi?id=140572
1013
1014         Reviewed by Andreas Kling.
1015
1016         * bmalloc/Algorithm.h:
1017         (bmalloc::isPowerOfTwo):
1018         (bmalloc::roundUpToMultipleOf):
1019         (bmalloc::roundDownToMultipleOf): Refactored some duplicate code to use our
1020         isPowerOfTwo helper function.
1021
1022         * bmalloc/Allocator.cpp:
1023         (bmalloc::Allocator::allocate):
1024         * bmalloc/Allocator.h: Stubbed out an implementation of aligned allocation.
1025         Doesn't do anything yet, but does correctly forward to system malloc
1026         when bmalloc is disabled.
1027
1028         * bmalloc/Cache.cpp:
1029         (bmalloc::Cache::allocateSlowCaseNullCache):
1030         * bmalloc/Cache.h:
1031         (bmalloc::Cache::allocate):
1032         * bmalloc/bmalloc.h:
1033         (bmalloc::api::memalign):
1034         * bmalloc/mbmalloc.cpp: Stubbed out an API for aligned allocation.
1035
1036 2015-01-13  Geoffrey Garen  <ggaren@apple.com>
1037
1038         Consider alignment when allocating from a SegregatedFreeList
1039         https://bugs.webkit.org/show_bug.cgi?id=140408
1040
1041         Reviewed by Sam Weinig.
1042
1043         In preparation for supporting aligned allocation.
1044
1045         No performance change.
1046
1047         Since this is just one extra branch in an already expensive function,
1048         I decided not to duplicate the function just to avoid the branch in
1049         the un-aligned case.
1050
1051         * bmalloc/SegregatedFreeList.cpp:
1052         (bmalloc::SegregatedFreeList::take):
1053         * bmalloc/SegregatedFreeList.h:
1054
1055 2015-01-13  Geoffrey Garen  <ggaren@apple.com>
1056
1057         Renamed minimum to size in SegregatedFreeList
1058         https://bugs.webkit.org/show_bug.cgi?id=140406
1059
1060         Reviewed by Sam Weinig.
1061
1062         In preparation for supporting aligned allocation.
1063
1064         * bmalloc/SegregatedFreeList.cpp:
1065         (bmalloc::SegregatedFreeList::takeGreedy):
1066         (bmalloc::SegregatedFreeList::take): Every size passed to malloc is
1067         really just a minimum. Let's not imply that this value is special.
1068
1069 2015-01-11  Dan Bernstein  <mitz@apple.com>
1070
1071         Geoff is organized, but he is not an organization.
1072
1073         Rubber-stamped by Anders Carlsson.
1074
1075         * bmalloc.xcodeproj/project.pbxproj: Removed the ORGANIZATIONNAME project attribute.
1076
1077 2015-01-07  Geoffrey Garen  <ggaren@apple.com>
1078
1079         Make bmalloc work with ASan
1080         https://bugs.webkit.org/show_bug.cgi?id=140194
1081
1082         Reviewed by Mark Lam.
1083
1084         * bmalloc/BPlatform.h: Added a way to detect Darwin OSes, since we need
1085         an OS-specific API to test for loaded runtime libraries.
1086
1087         * bmalloc/Environment.cpp:
1088         (bmalloc::isASanEnabled):
1089         (bmalloc::Environment::computeIsBmallocEnabled): Disabled bmalloc if
1090         ASan is enabled, since system malloc has the Asan hooks we need.
1091
1092         You could check for the ASan compile-time flag instead, but doing this
1093         check at runtime prepares bmalloc for a world where it is a dynamic
1094         library that might be loaded into projects it did not compile with.
1095
1096 2015-01-05  Geoffrey Garen  <ggaren@apple.com>
1097
1098         Fix up bmalloc's PerThread for use on Linux
1099         https://bugs.webkit.org/show_bug.cgi?id=139804
1100
1101         Reviewed by Anders Carlsson.
1102
1103         The previous implementation was a bit slow.
1104
1105         * bmalloc/PerThread.h:
1106         (bmalloc::PerThreadStorage<Cache>::get):
1107         (bmalloc::PerThreadStorage::get):
1108         (bmalloc::PerThreadStorage::init): Added a catch-all cross-platform Unix
1109         way to do fast per-thread access without taking a lock every time. This
1110         probably works on all the platforms we care about, and it matches other
1111         techniques we use elsewhere in WebKit.
1112
1113         (bmalloc::PerThread<T>::getFastCase): Removed the conditional from
1114         this class because PerThreadStorage now encapsulates everything that
1115         needs to be conditional.
1116
1117         (bmalloc::PerThreadStorage::initSharedKeyIfNeeded): Deleted.
1118
1119 2014-12-26  Dan Bernstein  <mitz@apple.com>
1120
1121         <rdar://problem/19348208> REGRESSION (r177027): iOS builds use the wrong toolchain
1122         https://bugs.webkit.org/show_bug.cgi?id=139950
1123
1124         Reviewed by David Kilzer.
1125
1126         * Configurations/Base.xcconfig: Only define TOOLCHAINS when building for OS X, doing so
1127         in a manner that works with Xcode 5.1.1.
1128
1129 2014-12-15  Geoffrey Garen  <ggaren@apple.com>
1130
1131         Safari crashes when you set Malloc environment variables
1132         https://bugs.webkit.org/show_bug.cgi?id=139656
1133
1134         Reviewed by Michael Saboff.
1135
1136         I forgot to cover the realloc() case. Whoops. (OoPS?)
1137
1138         This time around, I ran the full MallocBench test suite in Malloc=1
1139         mode, and it passed.
1140
1141         * bmalloc/Allocator.cpp:
1142         (bmalloc::Allocator::reallocate):
1143         * bmalloc/Allocator.h: Pushed realloc() logic down into the allocator.
1144         It needs to be down there so that we can do the short-circuiting check
1145         for whether bmalloc is enabled first.
1146
1147         Also added the check.
1148
1149         * bmalloc/Cache.cpp:
1150         (bmalloc::Cache::scavenge):
1151         (bmalloc::Cache::Cache):
1152         (bmalloc::Cache::reallocateSlowCaseNullCache):
1153         * bmalloc/Cache.h:
1154         (bmalloc::Cache::deallocator):
1155         (bmalloc::Cache::reallocate): Ditto.
1156
1157         * bmalloc/bmalloc.h:
1158         (bmalloc::api::free):
1159         (bmalloc::api::realloc): Ditto.
1160
1161         (bmalloc::api::scavenge): Pushed this down into Cache to match the
1162         surrounding functions.
1163
1164 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1165
1166         bmalloc should support system memory analysis tools (part 2)
1167         https://bugs.webkit.org/show_bug.cgi?id=139565
1168
1169         Reviewed by Mark Lam.
1170
1171         This patch actually queries the environment to see if memory analysis
1172         tools have been enabled.
1173
1174         * bmalloc/Deallocator.cpp:
1175         (bmalloc::Deallocator::scavenge): Don't process the object log if
1176         we've disabled bmalloc because it will be full of invalid nullptrs.
1177
1178         * bmalloc/Environment.cpp:
1179         (bmalloc::isMallocEnvironmentVariableSet): Test for the list of known
1180         Malloc debugging flags. I also added a plain "Malloc" catch-all for
1181         when you want to disable bmalloc without enabling any kind of funny
1182         business.
1183
1184         It would be slightly nicer just to iterate the list of environment
1185         variables and strstr them, but getenv is the more portable option,
1186         and performance here doesn't really matter.
1187
1188         (bmalloc::isLibgmallocEnabled): Test for the libgmalloc insertion
1189         environment variable.
1190
1191         (bmalloc::Environment::computeIsBmallocEnabled):
1192
1193 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1194
1195         Try to fix the iOS simulator build.
1196
1197         #include the declaration of malloc / free.
1198
1199         * bmalloc/Allocator.cpp:
1200         * bmalloc/Deallocator.cpp:
1201
1202 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1203
1204         Try to fix the build.
1205
1206         * bmalloc.xcodeproj/project.pbxproj: Marked a header exported.
1207
1208 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1209
1210         bmalloc should support system memory analysis tools (part 1)
1211         https://bugs.webkit.org/show_bug.cgi?id=139559
1212
1213         Reviewed by Mark Lam.
1214
1215         This patch adds the hooks to disable bmalloc at runtime if certain
1216         environment variables are set, but doesn't actually read from the
1217         environment yet.
1218
1219         No performance change.
1220
1221         * bmalloc.xcodeproj/project.pbxproj: Added the Environment class, which
1222         we'll use to read environment variables and see if memory analysis tools
1223         have been enabled.
1224
1225         * bmalloc/Allocator.cpp:
1226         (bmalloc::Allocator::Allocator):
1227         (bmalloc::Allocator::allocateSlowCase): Added a hook to disable bmalloc
1228         on the allocation path. We cache the setting to make the check fast.
1229
1230         * bmalloc/Allocator.h: Interface changes.
1231
1232         * bmalloc/Cache.cpp:
1233         (bmalloc::Cache::Cache): Pass a heap pointer through to our allocator
1234         and deallocator. This main purpose is to enable them to query the
1235         environment for whether bmalloc is enabled; but this is also a slightly
1236         cleaner way to guarantee to them that the Heap has been pre-initialized.
1237
1238         * bmalloc/Deallocator.cpp:
1239         (bmalloc::Deallocator::Deallocator): If bmalloc is disable, artificially
1240         fill the object log to force us to take the slow path on all deallocations.
1241
1242         (bmalloc::Deallocator::deallocateSlowCase): Do the disabled check.
1243
1244         * bmalloc/Deallocator.h: Interface changes.
1245
1246         * bmalloc/Environment.cpp: Added.
1247         (bmalloc::Environment::Environment):
1248         (bmalloc::Environment::computeIsBmallocEnabled):
1249         * bmalloc/Environment.h: Added.
1250         (bmalloc::Environment::isBmallocEnabled): This is the class that will
1251         encapsulate looking for environment variables that turn on heap
1252         analysis tools.
1253
1254         * bmalloc/Heap.h:
1255         (bmalloc::Heap::environment):
1256
1257         * bmalloc/Mutex.h:
1258         (bmalloc::Mutex::Mutex):
1259         * bmalloc/StaticMutex.h: A little refactoring to clarify these comments,
1260         since I got super confused about them while writing this patch.
1261
1262         * bmalloc/VMHeap.cpp: Fixed an #include.
1263
1264 2014-12-09  David Kilzer  <ddkilzer@apple.com>
1265
1266         Switch from using PLATFORM_NAME to SDK selectors in ANGLE, bmalloc, gtest, JavaScriptCore, WTF
1267         <http://webkit.org/b/139212>
1268
1269         Reviewed by Joseph Pecoraro.
1270
1271         * Configurations/Base.xcconfig:
1272         - Only set GCC_ENABLE_OBJC_GC, GCC_MODEL_TUNING and TOOLCHAINS
1273           on OS X.
1274         * Configurations/DebugRelease.xcconfig:
1275         - Only set MACOSX_DEPLOYMENT_TARGET and SDKROOT on OS X.
1276
1277 2014-11-07  Geoffrey Garen  <ggaren@apple.com>
1278
1279         bmalloc uses 8X more virtual memory than necessary
1280         https://bugs.webkit.org/show_bug.cgi?id=138495
1281
1282         Reviewed by Mark Lam.
1283
1284         iOS has a per-process virtual memory cap around 1GB, so there's some
1285         value to not going totally ham with virtual memory.
1286
1287         We currently use about 8X the necessary amount:
1288             - 2X to align our VM allocation
1289             - 4X to reserve small / medium / (2) large chunk VM ranges per superchunk
1290
1291         We can cut that down:
1292             - Return the unaligned portion of our VM allocation (-2X)
1293             - Use all the chunks in a superchunk, instead of allocating one
1294               chunk per superchunk (-4X)
1295
1296         * bmalloc/Algorithm.h:
1297         (bmalloc::roundUpToMultipleOf): Added a non-constant version of this
1298         function so we can call it with getpagesize() at runtime.
1299
1300         * bmalloc/Chunk.h:
1301         * bmalloc/LargeChunk.h:
1302         (bmalloc::LargeChunk::create): Deleted. Instead of each chunk allocating
1303         its own VM, VMHeap allocates the superchunk and all the chunks in it at a time.
1304
1305         * bmalloc/VMAllocate.h:
1306         (bmalloc::vmValidate):
1307         (bmalloc::vmAllocate): ASSERT that mmap succeeds to make crashes clearer
1308         if it does not succeed. Allocate precisely, and give back the extra.
1309
1310         * bmalloc/VMHeap.cpp:
1311         (bmalloc::VMHeap::allocateSuperChunk):
1312         (bmalloc::VMHeap::allocateSmallChunk): Deleted.
1313         (bmalloc::VMHeap::allocateMediumChunk): Deleted.
1314         (bmalloc::VMHeap::allocateLargeChunk): Deleted. Use all the chunks
1315         in a superchunk, instead of just one.
1316
1317         * bmalloc/VMHeap.h:
1318         (bmalloc::VMHeap::allocateSmallPage):
1319         (bmalloc::VMHeap::allocateMediumPage):
1320         (bmalloc::VMHeap::allocateLargeRange):
1321         * bmalloc/XLargeChunk.h:
1322         (bmalloc::XLargeChunk::create): Updated to match changes above.
1323
1324 2014-11-01  David Kilzer  <ddkilzer@apple.com>
1325
1326         JavaScriptCore is missing debug info for bmalloc because libbmalloc.a is stripped
1327         <https://webkit.org/b/138286>
1328         <rdar://problem/18847087>
1329
1330         Reviewed by Dan Bernstein.
1331
1332         * Configurations/bmalloc.xcconfig: Set STRIP_INSTALLED_PRODUCT
1333         to NO for the target that produces libbmalloc.a so that the
1334         debug symbols will be linked into JavaScriptCore and end up in
1335         its dSYM file.
1336
1337 2014-10-30  Dana Burkart  <dburkart@apple.com>
1338
1339         <rdar://problem/18821260> Prepare for the mysterious future
1340
1341         Reviewed by Lucas Forschler.
1342
1343         * Configurations/Base.xcconfig:
1344         * Configurations/DebugRelease.xcconfig:
1345
1346 2014-09-24  Geoffrey Garen  <ggaren@apple.com>
1347
1348         bmalloc: cleaned up fast path vs slow path
1349         https://bugs.webkit.org/show_bug.cgi?id=137081
1350
1351         Reviewed by Sam Weinig.
1352
1353         Might be a 1% speedup on MallocBench. Also cleans up the code a bit.
1354
1355         * bmalloc/Allocator.cpp:
1356         (bmalloc::Allocator::Allocator): Merged the small and medium range
1357         caches, just like the small and medium allocators. Ranges are abstract
1358         objects that don't really care whether they hold small or medium objects,
1359         so they don't need to be segregated.
1360
1361         (bmalloc::Allocator::scavenge): Ditto.
1362
1363         (bmalloc::Allocator::allocateBumpRangeSlowCase):
1364         (bmalloc::Allocator::allocateBumpRange): Same thing here, except that
1365         we do care a tiny bit, because we need to specify small vs medium when
1366         allocating new ranges from the heap, to ensure that the heap allocates
1367         from the right segment of VM.
1368
1369         (bmalloc::Allocator::allocateLarge):
1370         (bmalloc::Allocator::allocateXLarge): NO_INLINE because this was clouding
1371         up the fast path. Large allocation performance is dominated by allocation
1372         logic and initialization, so inlining it doesn't help.
1373
1374         (bmalloc::Allocator::allocateSlowCase): Slow path got a bit cleaner since
1375         it doesn't need to distinguish small vs medium objects.
1376
1377         (bmalloc::Allocator::allocateSmallBumpRange): Deleted.
1378         (bmalloc::Allocator::allocateMediumBumpRange): Deleted.
1379
1380         * bmalloc/Allocator.h:
1381         * bmalloc/BumpRange.h:
1382
1383         * bmalloc/Cache.cpp:
1384         (bmalloc::Cache::allocateSlowCase): Deleted.
1385         (bmalloc::Cache::deallocateSlowCase): Deleted.
1386         * bmalloc/Cache.h:
1387         (bmalloc::Cache::allocate):
1388         (bmalloc::Cache::deallocate):
1389         (bmalloc::Cache::allocateFastCase): Deleted.
1390         (bmalloc::Cache::deallocateFastCase): Deleted. Removed the Cache slow
1391         paths. The downside to this change is that the fast path branches to two
1392         distinct failure cases instead of one. The upside is that the slow path
1393         doesn't need to re-read the segment register, which is not as cheap as a
1394         normal register, and it doesn't need to do an extra level of function 
1395         call. Seems to be worth it.
1396
1397         * bmalloc/Deallocator.h:
1398         * bmalloc/Heap.cpp:
1399         (bmalloc::Heap::refillSmallBumpRangeCache):
1400         (bmalloc::Heap::refillMediumBumpRangeCache):
1401         * bmalloc/Heap.h: Updated for interface changes.
1402
1403         * bmalloc/Sizes.h: The most ranges a cache will hold is the number of
1404         small lines in a page / 2, since any other free lines will coalesce
1405         with their neighbors.
1406
1407 2014-09-23  Geoffrey Garen  <ggaren@apple.com>
1408
1409         Rolled out r173346.
1410
1411             bmalloc should honor the FastMalloc statistics API
1412             https://bugs.webkit.org/show_bug.cgi?id=136592
1413
1414         This didn't really work. Because we allow ranges with and without
1415         physical pages to merge, and we allow double-committing and
1416         double-decommitting, we can't rely on commit actions to track memory
1417         footprint.
1418
1419         * bmalloc/Heap.cpp:
1420         (bmalloc::Heap::size): Deleted.
1421         (bmalloc::Heap::capacity): Deleted.
1422         * bmalloc/Heap.h:
1423         * bmalloc/VMHeap.cpp:
1424         (bmalloc::VMHeap::VMHeap):
1425         (bmalloc::VMHeap::allocateSmallChunk):
1426         (bmalloc::VMHeap::allocateMediumChunk):
1427         (bmalloc::VMHeap::allocateLargeChunk):
1428         * bmalloc/VMHeap.h:
1429         (bmalloc::VMHeap::allocateSmallPage):
1430         (bmalloc::VMHeap::allocateMediumPage):
1431         (bmalloc::VMHeap::allocateLargeRange):
1432         (bmalloc::VMHeap::deallocateSmallPage):
1433         (bmalloc::VMHeap::deallocateMediumPage):
1434         (bmalloc::VMHeap::deallocateLargeRange):
1435         (bmalloc::VMHeap::size): Deleted.
1436         (bmalloc::VMHeap::capacity): Deleted.
1437         * bmalloc/bmalloc.h:
1438         (bmalloc::api::heapSize): Deleted.
1439         (bmalloc::api::heapCapacity): Deleted.
1440
1441 2014-09-23  Geoffrey Garen  <ggaren@apple.com>
1442
1443         bmalloc: Allocation should be more precise
1444         https://bugs.webkit.org/show_bug.cgi?id=136993
1445
1446         Reviewed by Gavin Barraclough.
1447
1448         13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
1449
1450         This patch teaches the allocator to merge adjacent free lines into a
1451         single allocatable range. This allows us to shrink the size of an
1452         individual line without increasing fragmentation or the rate of allocator
1453         slow paths.
1454
1455         We'll only take more slow paths when available memory is sparse, which
1456         is exactly when it's worth it. When available memory is dense, we'll
1457         take fewer slow paths.
1458
1459         * bmalloc.xcodeproj/project.pbxproj:
1460         * bmalloc/Algorithm.h:
1461         (bmalloc::divideRoundingUp):
1462
1463         * bmalloc/Allocator.cpp:
1464         (bmalloc::Allocator::Allocator): Updated for interface changes.
1465
1466         (bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
1467         Now that we merge lines, it's not convenient to scavenge by line.
1468
1469         (bmalloc::Allocator::allocateSmallBumpRange):
1470         (bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
1471         instead of individual lines.
1472
1473         (bmalloc::Allocator::allocateSlowCase):
1474         (bmalloc::Allocator::allocateSmallLine): Deleted.
1475         (bmalloc::Allocator::allocateMediumLine): Deleted.
1476         (bmalloc::Allocator::allocateMedium): Deleted.
1477         * bmalloc/Allocator.h:
1478         (bmalloc::Allocator::allocateFastCase): Folded medium allocations
1479         into the standard fast path with small allocations. Since a BumpAllocator
1480         just allocates out of an arbitrary range, it doesn't need to distinguish
1481         between small and medium lines.
1482
1483         * bmalloc/BumpAllocator.h:
1484         (bmalloc::BumpAllocator::size):
1485         (bmalloc::BumpAllocator::BumpAllocator):
1486         (bmalloc::BumpAllocator::init):
1487         (bmalloc::BumpAllocator::refill):
1488         (bmalloc::BumpAllocator::line): Deleted. No need to track line information
1489         anymore: the heap just gives us a pointer and a pre-computed number of
1490         objects, and we allocate them.
1491
1492         * bmalloc/Deallocator.cpp:
1493         (bmalloc::Deallocator::processObjectLog): Updated for interface changes.
1494
1495         * bmalloc/Heap.cpp:
1496         (bmalloc::Heap::Heap):
1497         (bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
1498         detailing where all objects will lie in memory. After we merge two lines,
1499         we might allocate an object that spans from one line to the next. This
1500         metadata details which bits of memory overlap in that way, and how they
1501         overlap.
1502
1503         (bmalloc::Heap::refillSmallBumpRangeCache):
1504         (bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
1505         and merge adjacent free lines into BumpRanges.
1506
1507         (bmalloc::Heap::allocateSmallPage):
1508         (bmalloc::Heap::allocateMediumPage):
1509         (bmalloc::Heap::deallocateSmallLine):
1510         (bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
1511         since we scan for free memory a page at a time.
1512
1513         (bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
1514         (bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
1515         fast path.
1516
1517         * bmalloc/Heap.h:
1518         (bmalloc::Heap::derefSmallLine):
1519         (bmalloc::Heap::derefMediumLine):
1520         (bmalloc::Heap::deallocateSmallLine): Deleted.
1521         (bmalloc::Heap::allocateSmallLine): Deleted.
1522         (bmalloc::Heap::deallocateMediumLine): Deleted.
1523         (bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
1524
1525         * bmalloc/Line.h:
1526         (bmalloc::Line<Traits>::ref):
1527         (bmalloc::Line<Traits>::deref):
1528         (bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
1529         anymore, since we only ever deref by 1 now.
1530
1531         * bmalloc/MediumAllocator.h:
1532         (bmalloc::MediumAllocator::isNull): Deleted.
1533         (bmalloc::MediumAllocator::MediumAllocator): Deleted.
1534         (bmalloc::MediumAllocator::line): Deleted.
1535         (bmalloc::MediumAllocator::allocate): Deleted.
1536         (bmalloc::MediumAllocator::derefCount): Deleted.
1537         (bmalloc::MediumAllocator::refill): Deleted.
1538         (bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
1539         been dead for a while, since it doesn't build anymore with this patch.
1540
1541         * bmalloc/Page.h:
1542         (bmalloc::Page::sizeClass):
1543         (bmalloc::Page::setSizeClass):
1544         (bmalloc::Page::smallSizeClass): Deleted.
1545         (bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
1546         to sizeClass, since we use it for medium sizes too.
1547
1548         * bmalloc/Sizes.h:
1549         (bmalloc::Sizes::sizeClass):
1550         (bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
1551
1552         (bmalloc::Sizes::smallSizeClassFor): Deleted.
1553         (bmalloc::Sizes::mediumSizeClassFor): Deleted.
1554
1555         * bmalloc/bmalloc.h:
1556         (bmalloc::api::realloc): Now that we have precise objects sizes, realloc
1557         can be a bit more precise. It also has to be, since we can't guarantee
1558         that an object ends at the end of a line anymore.
1559
1560 2014-09-19  Daniel Bates  <dabates@apple.com>
1561
1562         Always assume internal SDK when building configuration Production
1563         https://bugs.webkit.org/show_bug.cgi?id=136925
1564         <rdar://problem/18362399>
1565
1566         Reviewed by Dan Bernstein.
1567
1568         * Configurations/Base.xcconfig:
1569
1570 2014-09-16  Geoffrey Garen  <ggaren@apple.com>
1571
1572         bmalloc: moved line caches from the deallocator to the allocator
1573         https://bugs.webkit.org/show_bug.cgi?id=136868
1574
1575         Reviewed by Gavin Barraclough.
1576
1577         I did this mostly as a simplification, to make it easier to change the
1578         allocation strategy.
1579
1580         No throughput change on MallocBench. Saves about 50kB.
1581
1582         Since the deallocator needs to lock the heap when freeing lines anyway,
1583         there isn't much benefit to giving the deallocator a local cache of
1584         deallocated lines.
1585
1586         We still give the allocator a local cache of lines because that does
1587         reduce the frequency at which it needs to lock the heap in order to
1588         acquire more lines.
1589
1590         * bmalloc/Allocator.cpp:
1591         (bmalloc::Allocator::scavenge):
1592         (bmalloc::Allocator::allocateSmallLine):
1593         (bmalloc::Allocator::allocateMediumLine):
1594         (bmalloc::Allocator::allocateMedium):
1595         (bmalloc::Allocator::allocateSlowCase):
1596         * bmalloc/Allocator.h:
1597         * bmalloc/Deallocator.cpp:
1598         (bmalloc::Deallocator::Deallocator):
1599         (bmalloc::Deallocator::scavenge):
1600         (bmalloc::Deallocator::processObjectLog):
1601         (bmalloc::Deallocator::deallocateSmallLine): Deleted.
1602         (bmalloc::Deallocator::allocateSmallLine): Deleted.
1603         (bmalloc::Deallocator::deallocateMediumLine): Deleted.
1604         (bmalloc::Deallocator::allocateMediumLine): Deleted.
1605         * bmalloc/Deallocator.h:
1606
1607         * bmalloc/Sizes.h:
1608         * bmalloc/VMAllocate.h: Took the opportunity to make the line cache size
1609         exactly one page in size. That's about what we were shooting for anyway,
1610         and it may make it easier to switch to per-page allocation in future.
1611
1612 2014-09-15  Geoffrey Garen  <ggaren@apple.com>
1613
1614         bmalloc: allocate small and medium objects using the same bump pointer class
1615         https://bugs.webkit.org/show_bug.cgi?id=136843
1616
1617         Reviewed by Gavin Barraclough.
1618
1619         4% speedup on MallocBench.
1620
1621         Now that medium-sized objects have dedicated per-size allocators, they
1622         don't need to use an arbitrary bump pointer allocator. This means that
1623         every allocator knows how many objects it will allocate from the start,
1624         and we don't need a post-processing step to adjust refcounts based on
1625         real allocation count.
1626
1627         * bmalloc.xcodeproj/project.pbxproj: Renamed SmallAllocator to BumpAllocator
1628         since it's used for small and medium objects now.
1629
1630         * bmalloc/Allocator.cpp:
1631         (bmalloc::Allocator::Allocator): Updated to use new interface.
1632         (bmalloc::Allocator::scavenge): To "retire" an allocator, we just need
1633         to make sure that we finish allocating all the objects in it.
1634
1635         (bmalloc::Allocator::allocateMedium):
1636         (bmalloc::Allocator::allocateSlowCase):
1637         (bmalloc::Allocator::retire): Deleted.
1638         (bmalloc::Allocator::processSmallAllocatorLog): Deleted.
1639         (bmalloc::Allocator::processMediumAllocatorLog): Deleted.
1640         * bmalloc/Allocator.h:
1641         (bmalloc::Allocator::allocateFastCase): Removed abstractions and data
1642         used to post-process an allocator based on how many objects it allocated.
1643
1644         * bmalloc/BumpAllocator.h: Copied from Source/bmalloc/bmalloc/SmallAllocator.h.
1645         (bmalloc::BumpAllocator::BumpAllocator):
1646         (bmalloc::BumpAllocator::init):
1647         (bmalloc::BumpAllocator::line):
1648         (bmalloc::BumpAllocator::validate):
1649         (bmalloc::BumpAllocator::allocate):
1650         (bmalloc::BumpAllocator::refill):
1651         (bmalloc::BumpAllocator::clear): Updated these functions to be agnostic
1652         about the kinds of lines they allocate into. In some cases, the line
1653         type must be provided as a template parameter by the caller.
1654
1655         (bmalloc::SmallAllocator::SmallAllocator): Deleted.
1656         (bmalloc::SmallAllocator::line): Deleted.
1657         (bmalloc::SmallAllocator::allocate): Deleted.
1658         (bmalloc::SmallAllocator::objectCount): Deleted.
1659         (bmalloc::SmallAllocator::derefCount): Deleted.
1660         (bmalloc::SmallAllocator::refill): Deleted.
1661         (bmalloc::SmallAllocator::clear): Deleted.
1662
1663         * bmalloc/ObjectType.h:
1664         (bmalloc::isMedium):
1665
1666         * bmalloc/SmallAllocator.h:
1667         (bmalloc::SmallAllocator::isNull): Deleted.
1668         (bmalloc::SmallAllocator::canAllocate): Deleted.
1669         (bmalloc::SmallAllocator::SmallAllocator): Deleted.
1670         (bmalloc::SmallAllocator::line): Deleted.
1671         (bmalloc::SmallAllocator::allocate): Deleted.
1672         (bmalloc::SmallAllocator::objectCount): Deleted.
1673         (bmalloc::SmallAllocator::derefCount): Deleted.
1674         (bmalloc::SmallAllocator::refill): Deleted.
1675         (bmalloc::SmallAllocator::clear): Deleted.
1676
1677 2014-09-12  Geoffrey Garen  <ggaren@apple.com>
1678
1679         Fixed a goof in bmalloc Vector sizing
1680         https://bugs.webkit.org/show_bug.cgi?id=136795
1681
1682         Reviewed by Gavin Barraclough and Sam Weinig.
1683
1684         We want our minimum vector to be page-sized since the OS will give us
1685         a page no matter what -- but we want that many bytes, and not enough
1686         bytes to store that many elements.
1687
1688         * bmalloc/Vector.h: Math is hard.
1689
1690 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
1691
1692         bmalloc should segregate medium-sized objects by line like it does for small-sized objects
1693         https://bugs.webkit.org/show_bug.cgi?id=136693
1694
1695         Reviewed by Gavin Barraclough.
1696
1697         4% reduction in heap size on the MallocBench *_memory_warning benchmarks.
1698
1699         No throughput change.
1700
1701         We keep an array of medium allocators, just like our array of small
1702         allocators.
1703
1704         In future, we can simplify the allocation fast path by merging the small
1705         and medium allocator arrays. For now, this is the simplest change that
1706         gets the win.
1707
1708         * bmalloc/Allocator.cpp:
1709         (bmalloc::Allocator::Allocator):
1710         (bmalloc::Allocator::scavenge):
1711         (bmalloc::Allocator::allocateMedium):
1712         * bmalloc/Allocator.h:
1713         * bmalloc/Sizes.h:
1714         (bmalloc::Sizes::mediumSizeClassFor):
1715
1716 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
1717
1718         Reviewed by Sam Weinig.
1719
1720         Renamed log => retire for clarity.
1721
1722         * bmalloc/Allocator.cpp:
1723         (bmalloc::Allocator::scavenge):
1724         (bmalloc::Allocator::retire):
1725         (bmalloc::Allocator::allocateMedium):
1726         (bmalloc::Allocator::allocateSlowCase):
1727         (bmalloc::Allocator::log): Deleted.
1728         * bmalloc/Allocator.h:
1729
1730 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
1731
1732         bmalloc: eager scavenge leaves behind a bogus allocator
1733         https://bugs.webkit.org/show_bug.cgi?id=136743
1734
1735         Reviewed by Sam Weinig.
1736
1737         Be sure to clear the allocator after logging it in the eager scavenge
1738         case, so that we don't later try to allocate out of the lines that we
1739         have thrown away.
1740
1741         We didn't need to do this previously because scavenge would only happen
1742         at thread exit time, after which no further allocation from the per-thread
1743         cache would take place.
1744
1745         * bmalloc/Allocator.cpp:
1746         (bmalloc::Allocator::scavenge):
1747         * bmalloc/MediumAllocator.h:
1748         (bmalloc::MediumAllocator::clear):
1749         * bmalloc/SmallAllocator.h:
1750         (bmalloc::SmallAllocator::clear):
1751
1752 2014-09-05  Geoffrey Garen  <ggaren@apple.com>
1753
1754         bmalloc should honor the FastMalloc statistics API
1755         https://bugs.webkit.org/show_bug.cgi?id=136592
1756
1757         Reviewed by Gavin Barraclough.
1758
1759         We do this by tracking "size" and "capacity" in the VM heap.
1760
1761         The VM heap's "capacity" is all the VM we ever allocated.
1762
1763         The VM heap's "size" the subset of VM currently held onto by the
1764         VM heap (and therefore not in use by the regular heap).
1765
1766         Somewhat ironically, reducing the process's memory footprint, increases
1767         the size of the VM heap, since the VM heap holds the pages that are
1768         purely virtual and not physical.
1769
1770         * bmalloc/Heap.cpp:
1771         (bmalloc::Heap::size):
1772         (bmalloc::Heap::capacity):
1773         * bmalloc/Heap.h:
1774         * bmalloc/VMHeap.cpp:
1775         (bmalloc::VMHeap::VMHeap):
1776         (bmalloc::VMHeap::allocateSmallChunk):
1777         (bmalloc::VMHeap::allocateMediumChunk):
1778         (bmalloc::VMHeap::allocateLargeChunk):
1779         * bmalloc/VMHeap.h:
1780         (bmalloc::VMHeap::size):
1781         (bmalloc::VMHeap::capacity):
1782         (bmalloc::VMHeap::allocateSmallPage):
1783         (bmalloc::VMHeap::allocateMediumPage):
1784         (bmalloc::VMHeap::allocateLargeRange):
1785         (bmalloc::VMHeap::deallocateSmallPage):
1786         (bmalloc::VMHeap::deallocateMediumPage):
1787         (bmalloc::VMHeap::deallocateLargeRange):
1788         * bmalloc/bmalloc.h:
1789         (bmalloc::api::heapSize):
1790         (bmalloc::api::heapCapacity):
1791
1792 2014-09-02  Geoffrey Garen  <ggaren@apple.com>
1793
1794         bmalloc crashes on the EWS bots (due to bad large object allocation)
1795         https://bugs.webkit.org/show_bug.cgi?id=136469
1796
1797         Reviewed by Andreas Kling.
1798
1799         It's possible to convince bmalloc to perform a bad large object allocation,
1800         through these steps:
1801
1802         (1) Insert object A into freelist F0.
1803
1804         (2) Split, merge and split again A's neighbors such that object B is
1805         inserted into freelist F0, with boundary tag and size equal to object A,
1806         but pointer not completely equal to object A. Put object B at the head of F0.
1807
1808         (3) Allocate some other object from F0, swapping its position in the
1809         freelist with object B, such that object A is now ahead of object B.
1810
1811         --> Now, the next allocation for size A/B will allocate object A, which
1812         has a slightly wrong idea about where the object actually begins.
1813         Immediately, you'll corrupt a little memory, and over time, you'll also
1814         corrupt boundary tag metadata.
1815
1816         The solution is to store the begin pointer in the boundary tag. Luckily,
1817         this doesn't make the tag any bigger, and it's not a noticeable slowdown
1818         on MallocBench.
1819
1820         * bmalloc/Algorithm.h:
1821         (bmalloc::rightShift):
1822         * bmalloc/BeginTag.h:
1823         (bmalloc::BeginTag::isInFreeList): This is the bug fix. Make sure to
1824         validate the start pointer when popping off the free list. Through a
1825         very uncommon set of steps, it is possible to have an item in the free
1826         list that is valid by all accounts except for its start pointer.
1827
1828         * bmalloc/BoundaryTag.h:
1829         (bmalloc::BoundaryTag::compactBegin):
1830         (bmalloc::BoundaryTag::setRange):
1831         (bmalloc::BoundaryTag::setSize): Deleted. Record a compact version of the
1832         start pointer. We don't need the whole pointer -- just the offset, in
1833         largeAlignment increments, into the relevant boundary tag bucket.
1834
1835         * bmalloc/BoundaryTagInlines.h:
1836         (bmalloc::validateNext):
1837         (bmalloc::BoundaryTag::init):
1838         (bmalloc::BoundaryTag::mergeLarge):
1839         (bmalloc::BoundaryTag::splitLarge):
1840         * bmalloc/SegregatedFreeList.cpp:
1841         (bmalloc::SegregatedFreeList::insert):
1842         (bmalloc::SegregatedFreeList::takeGreedy):
1843         (bmalloc::SegregatedFreeList::take): Provide the whole range instead of
1844         the size when establishing a boundary tag, as required by the new
1845         interface.
1846
1847         * bmalloc/Sizes.h:
1848
1849 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
1850
1851         Fixed a bmalloc crash seen on the EWS bot
1852         https://bugs.webkit.org/show_bug.cgi?id=135955
1853
1854         Reviewed by Andreas Kling.
1855
1856         * bmalloc/Syscall.h: Some CG APIs vm_copy their input buffers. If the
1857         input buffer is a malloc region, that region will get marked Copy-On-Write
1858         by the kernel. Calls to madvise() for COW regions fail and return EINVAL
1859         on older OS X's. In 10.10, they still fail, but they do not return
1860         EINVAL.
1861
1862         So, we can only ASSERT that our syscalls succeed starting with 10.10.
1863
1864 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
1865
1866         Fixed the bmalloc build
1867         https://bugs.webkit.org/show_bug.cgi?id=135953
1868
1869         Reviewed by Andreas Kling.
1870
1871         * bmalloc.xcodeproj/project.pbxproj: Marked a few headers as private.
1872         These headers are used, so they must be available outside the project.
1873
1874 2014-08-13  Daniel Bates  <dabates@apple.com>
1875
1876         Attempt to fix the build following <http://trac.webkit.org/changeset/172576>
1877         (https://bugs.webkit.org/show_bug.cgi?id=135895)
1878
1879         Substitute PerThreadStorage<T>::initSharedKeyIfNeeded() for initSharedKeyIfNeeded() in
1880         implementation of PerThread<T>::getFastCase().
1881
1882         * bmalloc/PerThread.h:
1883         (bmalloc::PerThread<T>::getFastCase):
1884
1885 2014-08-13  Daniel Bates  <dabates@apple.com>
1886
1887         Make bmalloc::PerThread work without C++ thread local storage
1888         https://bugs.webkit.org/show_bug.cgi?id=135895
1889
1890         Reviewed by Geoffrey Garen.
1891
1892         Implement support for building bmalloc without C++ thread local storage.
1893
1894         * bmalloc/BPlatform.h: Remove macro define BPLATFORM_IOS_SIMULATOR. Added macro function
1895         BCOMPILER_SUPPORTS() and macro define BCOMPILER_SUPPORTS_CXX_THREAD_LOCAL that can be used
1896         to determine whether the compiler supports C++ thread local storage.
1897         * bmalloc/PerThread.h:
1898         (bmalloc::PerThreadStorage::get): Modified to call pthread_getspecific() when building
1899         without C++ thread local storage.
1900         (bmalloc::PerThreadStorage::initSharedKeyIfNeeded): Added.
1901         (bmalloc::PerThreadStorage::init): Moved logic to initialize shared Pthread key from here to
1902         PerThreadStorage::initSharedKeyIfNeeded().
1903         (bmalloc::PerThread<T>::getFastCase): Modified to call PerThreadStorage::initSharedKeyIfNeeded()
1904         before querying PerThreadStorage::get() when building without C++ thread local storage so as to
1905         ensure that the shared key has been initialized.
1906         (_pthread_setspecific_direct): Deleted.
1907         (_pthread_getspecific_direct): Deleted.
1908
1909 2014-08-13  Daniel Bates  <dabates@apple.com>
1910
1911         [iOS] Make JavaScriptCore and bmalloc build with the public SDK
1912         https://bugs.webkit.org/show_bug.cgi?id=135848
1913
1914         Reviewed by Geoffrey Garen.
1915
1916         * bmalloc/BPlatform.h: Added macro BPLATFORM_IOS_SIMULATOR, which evaluates to true
1917         when building for the iOS Simulator.
1918         * bmalloc/PerThread.h: Use pthread_machdep.h code path when building for iOS Simulator
1919         using the public SDK.
1920         (_pthread_setspecific_direct): Added; only defined when building for the iOS Simulator
1921         using the public SDK.
1922         (_pthread_getspecific_direct): Added; only defined when building for the iOS Simulator
1923         using the public SDK.
1924
1925 2014-08-12  Daniel Bates  <dabates@apple.com>
1926
1927         BPLATFORM(IOS) always evaluates to false
1928         https://bugs.webkit.org/show_bug.cgi?id=135843
1929
1930         Reviewed by Geoffrey Garen.
1931
1932         Fix typo in definition of BPLATFORM() and include system header TargetConditionals.h
1933         (when building on an Apple platform) so that BPLATFORM(X) evaluates to true when
1934         building for platform X. In particular, so that BPLATFORM(IOS) evaluates to true when
1935         building for iOS.
1936
1937         As a side effect of this change, the change made in <http://trac.webkit.org/changeset/167289>
1938         will be honored and iOS will assume a VM page size of 16kB (again) instead of 4kB.
1939
1940         * bmalloc/BPlatform.h:
1941
1942 2014-08-11  Andy Estes  <aestes@apple.com>
1943
1944         [iOS] Get rid of iOS.xcconfig
1945         https://bugs.webkit.org/show_bug.cgi?id=135809
1946
1947         Reviewed by Joseph Pecoraro.
1948
1949         All iOS.xcconfig did was include AspenFamily.xcconfig, so there's no need for the indirection.
1950
1951         * Configurations/Base.xcconfig:
1952         * Configurations/iOS.xcconfig: Removed.
1953         * bmalloc.xcodeproj/project.pbxproj:
1954
1955 2014-05-01  Dan Bernstein  <mitz@apple.com>
1956
1957         Fixed production builds for the iOS Simulator.
1958         <rdar://problem/16792221>
1959
1960         * Configurations/bmalloc.xcconfig: Include INSTALL_PATH_PREFIX in
1961         PRIVATE_HEADERS_FOLDER_PATH when installing.
1962
1963 2014-04-20  Geoffrey Garen  <ggaren@apple.com>
1964
1965         bmalloc: Segregate pages by objects size
1966         https://bugs.webkit.org/show_bug.cgi?id=131909
1967
1968         Reviewed by Andreas Kling.
1969
1970         2% reduction in memory-at-end on the Membuster memory_warning benchmarks.
1971
1972         * bmalloc/Allocator.cpp:
1973         (bmalloc::Allocator::allocateSlowCase):
1974         * bmalloc/Allocator.h:
1975         (bmalloc::Allocator::allocateFastCase):
1976         (bmalloc::Allocator::smallAllocatorFor): Use the new shared helper
1977         function for size class calculation.
1978
1979         * bmalloc/Deallocator.cpp:
1980         (bmalloc::Deallocator::Deallocator):
1981         (bmalloc::Deallocator::scavenge):
1982         (bmalloc::Deallocator::deallocateSmallLine):
1983         (bmalloc::Deallocator::allocateSmallLine):
1984         * bmalloc/Deallocator.h: Keep a cache for every size class, since the
1985         cache can't be shared anymore.
1986
1987         * bmalloc/Heap.cpp:
1988         (bmalloc::Heap::allocateSmallLineSlowCase):
1989         * bmalloc/Heap.h:
1990         (bmalloc::Heap::deallocateSmallLine): Ditto.
1991
1992         (bmalloc::Heap::allocateSmallLine): Check size class in addition to
1993         page refcount when allocating a line because we might have deallocated
1994         the page and the recycled it for another size class.
1995
1996         (bmalloc::Heap::deallocateMediumLine):
1997         (bmalloc::Heap::allocateMediumLine):
1998         * bmalloc/Line.h:
1999         (bmalloc::Line::refCount):
2000         * bmalloc/Page.h:
2001         (bmalloc::Page::refCount):
2002         (bmalloc::Page::smallSizeClass):
2003         (bmalloc::Page::setSmallSizeClass):
2004         (bmalloc::Page<Traits>::refCount): Deleted.
2005         * bmalloc/Sizes.h:
2006         (bmalloc::Sizes::smallSizeClassFor): New shared API for computing
2007         an index into an array from a size.
2008
2009 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
2010
2011         bmalloc: Improved alignment in LargeChunk
2012         https://bugs.webkit.org/show_bug.cgi?id=131895
2013
2014         Reviewed by Andreas Kling.
2015
2016         * bmalloc/Chunk.h:
2017         * bmalloc/LargeChunk.h: Align to vmPageSize just like Chunk does.
2018         Technically, the previous alignment was harmless, but I would prefer,
2019         dear reader, not to have to explain the interlocking set of
2020         circumstances that made it so.
2021
2022 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
2023
2024         Rolled out r167502 because it caused a crash on the facebook benchmark.
2025
2026         Unreviewed.
2027
2028             bmalloc: Added an XSmall line size
2029             https://bugs.webkit.org/show_bug.cgi?id=131851
2030
2031             Reviewed by Sam Weinig.
2032
2033 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
2034
2035         bmalloc: Mutex should be harder to use wrong
2036         https://bugs.webkit.org/show_bug.cgi?id=131879
2037
2038         Reviewed by Andreas Kling.
2039
2040         Mutex now has a proper constructor, so you can't deadlock by forgetting
2041         to initialize it.
2042
2043         * bmalloc.xcodeproj/project.pbxproj:
2044         * bmalloc/Allocator.cpp:
2045         (bmalloc::Allocator::processXSmallAllocatorLog):
2046         (bmalloc::Allocator::processSmallAllocatorLog):
2047         (bmalloc::Allocator::processMediumAllocatorLog):
2048         (bmalloc::Allocator::allocateLarge):
2049         (bmalloc::Allocator::allocateXLarge): Global replace Mutex => StaticMutex,
2050         since the Heap mutex is a static.
2051
2052         * bmalloc/AsyncTask.h:
2053         (bmalloc::Function>::AsyncTask): Use Mutex, since we're not static. No
2054         need for explicit initialization anymore.
2055
2056         * bmalloc/Deallocator.cpp:
2057         (bmalloc::Deallocator::scavenge):
2058         (bmalloc::Deallocator::deallocateLarge):
2059         (bmalloc::Deallocator::deallocateXLarge):
2060         (bmalloc::Deallocator::processObjectLog):
2061         (bmalloc::Deallocator::deallocateSmallLine):
2062         (bmalloc::Deallocator::deallocateXSmallLine):
2063         (bmalloc::Deallocator::allocateSmallLine):
2064         (bmalloc::Deallocator::allocateXSmallLine):
2065         (bmalloc::Deallocator::deallocateMediumLine):
2066         (bmalloc::Deallocator::allocateMediumLine):
2067         * bmalloc/Deallocator.h:
2068         * bmalloc/Heap.cpp:
2069         (bmalloc::sleep):
2070         (bmalloc::Heap::Heap):
2071         (bmalloc::Heap::concurrentScavenge):
2072         (bmalloc::Heap::scavenge):
2073         (bmalloc::Heap::scavengeSmallPages):
2074         (bmalloc::Heap::scavengeXSmallPages):
2075         (bmalloc::Heap::scavengeMediumPages):
2076         (bmalloc::Heap::scavengeLargeRanges):
2077         (bmalloc::Heap::allocateXSmallLineSlowCase):
2078         (bmalloc::Heap::allocateSmallLineSlowCase):
2079         (bmalloc::Heap::allocateMediumLineSlowCase):
2080         (bmalloc::Heap::allocateXLarge):
2081         (bmalloc::Heap::deallocateXLarge):
2082         (bmalloc::Heap::allocateLarge):
2083         (bmalloc::Heap::deallocateLarge):
2084         * bmalloc/Heap.h:
2085         (bmalloc::Heap::deallocateXSmallLine):
2086         (bmalloc::Heap::allocateXSmallLine):
2087         (bmalloc::Heap::deallocateSmallLine):
2088         (bmalloc::Heap::allocateSmallLine):
2089         (bmalloc::Heap::deallocateMediumLine):
2090         (bmalloc::Heap::allocateMediumLine):
2091         * bmalloc/Line.h:
2092         (bmalloc::Line<Traits>::deref):
2093         * bmalloc/Mutex.cpp: Removed.
2094         * bmalloc/Mutex.h:
2095         (bmalloc::Mutex::Mutex):
2096         (bmalloc::Mutex::init): Deleted.
2097         (bmalloc::Mutex::try_lock): Deleted.
2098         (bmalloc::Mutex::lock): Deleted.
2099         (bmalloc::Mutex::unlock): Deleted.
2100         * bmalloc/Page.h:
2101         (bmalloc::Page<Traits>::ref):
2102         (bmalloc::Page<Traits>::deref):
2103         (bmalloc::Page<Traits>::refCount):
2104         * bmalloc/PerProcess.h:
2105         (bmalloc::PerProcess::mutex):
2106         (bmalloc::PerProcess<T>::getSlowCase):
2107         * bmalloc/StaticMutex.cpp: Added.
2108         (bmalloc::StaticMutex::lockSlowCase):
2109         * bmalloc/StaticMutex.h: Added.
2110         (bmalloc::StaticMutex::init):
2111         (bmalloc::StaticMutex::try_lock):
2112         (bmalloc::StaticMutex::lock):
2113         (bmalloc::StaticMutex::unlock):
2114         * bmalloc/VMHeap.h:
2115         (bmalloc::VMHeap::deallocateXSmallPage):
2116         (bmalloc::VMHeap::deallocateSmallPage):
2117         (bmalloc::VMHeap::deallocateMediumPage):
2118         (bmalloc::VMHeap::deallocateLargeRange):
2119         * bmalloc/bmalloc.h:
2120         (bmalloc::api::scavenge): Global replace Mutex => StaticMutex,
2121         since the Heap mutex is a static.
2122
2123 2014-04-18  Geoffrey Garen  <ggaren@apple.com>
2124
2125         bmalloc: AsyncTask should use Mutex instead of std::mutex
2126         https://bugs.webkit.org/show_bug.cgi?id=131865
2127
2128         Reviewed by Gavin Barraclough.
2129
2130         std::mutex is so slow that it makes parallelizing simple tasks through
2131         AsyncTask a net regression. Mutex fixes this.
2132
2133         * bmalloc/AsyncTask.h:
2134         (bmalloc::Function>::AsyncTask):
2135         (bmalloc::Function>::join):
2136         (bmalloc::Function>::runSlowCase):
2137         (bmalloc::Function>::entryPoint):
2138         * bmalloc/Mutex.h:
2139         (bmalloc::Mutex::init):
2140
2141 2014-04-18  Geoffrey Garen  <ggaren@apple.com>
2142
2143         bmalloc: Added an XSmall line size
2144         https://bugs.webkit.org/show_bug.cgi?id=131851
2145
2146         Reviewed by Sam Weinig.
2147
2148         Reduces malloc footprint on Membuster recordings by 10%.
2149
2150         This is a throughput regression, but we're still way ahead of TCMalloc.
2151         I have some ideas for how to recover the regression -- but I wanted to
2152         get this win in first.
2153
2154         Full set of benchmark results:
2155
2156                 bmalloc> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks --measure-heap nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
2157                                                                                                 
2158                                                                nopatch                      patch                                Δ
2159                 Peak Memory:
2160                     reddit_memory_warning                      7,896kB                    7,532kB                  ^ 1.05x smaller
2161                     flickr_memory_warning                     12,968kB                   12,324kB                  ^ 1.05x smaller
2162                     theverge_memory_warning                   16,672kB                   15,200kB                   ^ 1.1x smaller
2163
2164                     <geometric mean>                          11,952kB                   11,216kB                  ^ 1.07x smaller
2165                     <arithmetic mean>                         12,512kB                   11,685kB                  ^ 1.07x smaller
2166                     <harmonic mean>                           11,375kB                   10,726kB                  ^ 1.06x smaller
2167
2168                 Memory at End:
2169                     reddit_memory_warning                      7,320kB                    6,856kB                  ^ 1.07x smaller
2170                     flickr_memory_warning                     10,848kB                    9,692kB                  ^ 1.12x smaller
2171                     theverge_memory_warning                   16,380kB                   14,872kB                   ^ 1.1x smaller
2172
2173                     <geometric mean>                          10,916kB                    9,961kB                   ^ 1.1x smaller
2174                     <arithmetic mean>                         11,516kB                   10,473kB                   ^ 1.1x smaller
2175                     <harmonic mean>                           10,350kB                    9,485kB                  ^ 1.09x smaller
2176
2177                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
2178                                                                                                 
2179                                                    nopatch                patch                         Δ
2180                 Execution Time:
2181                     churn                            127ms                151ms            ! 1.19x slower
2182                     list_allocate                    130ms                164ms            ! 1.26x slower
2183                     tree_allocate                    109ms                127ms            ! 1.17x slower
2184                     tree_churn                       115ms                120ms            ! 1.04x slower
2185                     facebook                         240ms                259ms            ! 1.08x slower
2186                     fragment                          91ms                131ms            ! 1.44x slower
2187                     fragment_iterate                 105ms                106ms            ! 1.01x slower
2188                     message_one                      260ms                259ms             ^ 1.0x faster
2189                     message_many                     149ms                154ms            ! 1.03x slower
2190                     medium                           194ms                248ms            ! 1.28x slower
2191                     big                              157ms                160ms            ! 1.02x slower
2192
2193                     <geometric mean>                 144ms                163ms            ! 1.13x slower
2194                     <arithmetic mean>                152ms                171ms            ! 1.12x slower
2195                     <harmonic mean>                  137ms                156ms            ! 1.14x slower
2196
2197                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
2198                                                                                                 
2199                                                                        nopatch                          patch                                     Δ
2200                 Execution Time:
2201                     churn                                                126ms                          148ms                        ! 1.17x slower
2202                     churn --parallel                                      62ms                           76ms                        ! 1.23x slower
2203                     list_allocate                                        130ms                          164ms                        ! 1.26x slower
2204                     list_allocate --parallel                             120ms                          175ms                        ! 1.46x slower
2205                     tree_allocate                                        111ms                          127ms                        ! 1.14x slower
2206                     tree_allocate --parallel                              95ms                          135ms                        ! 1.42x slower
2207                     tree_churn                                           115ms                          124ms                        ! 1.08x slower
2208                     tree_churn --parallel                                107ms                          126ms                        ! 1.18x slower
2209                     facebook                                             240ms                          276ms                        ! 1.15x slower
2210                     facebook --parallel                                  802ms                        1,088ms                        ! 1.36x slower
2211                     fragment                                              92ms                          130ms                        ! 1.41x slower
2212                     fragment --parallel                                   66ms                          124ms                        ! 1.88x slower
2213                     fragment_iterate                                     109ms                          127ms                        ! 1.17x slower
2214                     fragment_iterate --parallel                           55ms                           64ms                        ! 1.16x slower
2215                     message_one                                          260ms                          260ms                                      
2216                     message_many                                         170ms                          238ms                         ! 1.4x slower
2217                     medium                                               185ms                          250ms                        ! 1.35x slower
2218                     medium --parallel                                    210ms                          334ms                        ! 1.59x slower
2219                     big                                                  150ms                          169ms                        ! 1.13x slower
2220                     big --parallel                                       138ms                          144ms                        ! 1.04x slower
2221
2222                     <geometric mean>                                     135ms                          170ms                        ! 1.26x slower
2223                     <arithmetic mean>                                    167ms                          214ms                        ! 1.28x slower
2224                     <harmonic mean>                                      117ms                          148ms                        ! 1.26x slower
2225
2226                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
2227
2228                                                                     TC                      patch                                Δ
2229                 Peak Memory:
2230                     reddit_memory_warning                     13,836kB                   13,436kB                  ^ 1.03x smaller
2231                     flickr_memory_warning                     24,868kB                   25,188kB                   ! 1.01x bigger
2232                     theverge_memory_warning                   24,504kB                   26,636kB                   ! 1.09x bigger
2233
2234                     <geometric mean>                          20,353kB                   20,812kB                   ! 1.02x bigger
2235                     <arithmetic mean>                         21,069kB                   21,753kB                   ! 1.03x bigger
2236                     <harmonic mean>                           19,570kB                   19,780kB                   ! 1.01x bigger
2237
2238                 Memory at End:
2239                     reddit_memory_warning                      8,656kB                   10,016kB                   ! 1.16x bigger
2240                     flickr_memory_warning                     11,844kB                   13,784kB                   ! 1.16x bigger
2241                     theverge_memory_warning                   18,516kB                   22,748kB                   ! 1.23x bigger
2242
2243                     <geometric mean>                          12,382kB                   14,644kB                   ! 1.18x bigger
2244                     <arithmetic mean>                         13,005kB                   15,516kB                   ! 1.19x bigger
2245                     <harmonic mean>                           11,813kB                   13,867kB                   ! 1.17x bigger
2246
2247                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
2248                                                                                                 
2249                                                         TC                patch                         Δ
2250                 Execution Time:
2251                     churn                            416ms                148ms            ^ 2.81x faster
2252                     list_allocate                    463ms                164ms            ^ 2.82x faster
2253                     tree_allocate                    292ms                127ms             ^ 2.3x faster
2254                     tree_churn                       157ms                120ms            ^ 1.31x faster
2255                     facebook                         327ms                276ms            ^ 1.18x faster
2256                     fragment                         335ms                129ms             ^ 2.6x faster
2257                     fragment_iterate                 344ms                108ms            ^ 3.19x faster
2258                     message_one                      386ms                258ms             ^ 1.5x faster
2259                     message_many                     410ms                154ms            ^ 2.66x faster
2260                     medium                           391ms                245ms             ^ 1.6x faster
2261                     big                              261ms                167ms            ^ 1.56x faster
2262
2263                     <geometric mean>                 332ms                164ms            ^ 2.02x faster
2264                     <arithmetic mean>                344ms                172ms            ^ 1.99x faster
2265                     <harmonic mean>                  317ms                157ms            ^ 2.02x faster
2266
2267         * bmalloc.xcodeproj/project.pbxproj:
2268         * bmalloc/Allocator.cpp:
2269         (bmalloc::Allocator::Allocator): Don't assume that each allocator's
2270         index corresponds with its size. Instead, use the size selection function
2271         explicitly. Now that we have XSmall, some small allocator entries are
2272         unused.
2273
2274         (bmalloc::Allocator::scavenge):
2275         (bmalloc::Allocator::log):
2276         (bmalloc::Allocator::processXSmallAllocatorLog):
2277         (bmalloc::Allocator::allocateSlowCase):
2278         * bmalloc/Allocator.h:
2279         (bmalloc::Allocator::xSmallAllocatorFor):
2280         (bmalloc::Allocator::allocateFastCase):
2281         * bmalloc/Chunk.h:
2282         * bmalloc/Deallocator.cpp:
2283         (bmalloc::Deallocator::scavenge):
2284         (bmalloc::Deallocator::processObjectLog):
2285         (bmalloc::Deallocator::deallocateSlowCase):
2286         (bmalloc::Deallocator::deallocateXSmallLine):
2287         (bmalloc::Deallocator::allocateXSmallLine):
2288         * bmalloc/Deallocator.h:
2289         (bmalloc::Deallocator::deallocateFastCase):
2290         * bmalloc/Heap.cpp:
2291         (bmalloc::Heap::scavenge):
2292         (bmalloc::Heap::scavengeXSmallPages):
2293         (bmalloc::Heap::allocateXSmallLineSlowCase):
2294         * bmalloc/Heap.h:
2295         (bmalloc::Heap::deallocateXSmallLine):
2296         (bmalloc::Heap::allocateXSmallLine):
2297         * bmalloc/LargeChunk.h:
2298         (bmalloc::LargeChunk::get):
2299         (bmalloc::LargeChunk::endTag):
2300         * bmalloc/Line.h:
2301         * bmalloc/MediumAllocator.h:
2302         (bmalloc::MediumAllocator::allocate):
2303         (bmalloc::MediumAllocator::refill):
2304         * bmalloc/ObjectType.cpp:
2305         (bmalloc::objectType):
2306         * bmalloc/ObjectType.h:
2307         (bmalloc::isXSmall):
2308         (bmalloc::isSmall):
2309         (bmalloc::isMedium):
2310         (bmalloc::isLarge):
2311         (bmalloc::isSmallOrMedium): Deleted.
2312         * bmalloc/SegregatedFreeList.h: I boiler-plate copied existing code for
2313         handling small objects. There's probably a reasonable way to share this
2314         code in the future -- I'll look into that once it's stopped changing.
2315
2316         * bmalloc/Sizes.h: Tweaked size classes to make Membuster happy. This
2317         is the main reason things got slower.
2318
2319         * bmalloc/SmallAllocator.h:
2320         (bmalloc::SmallAllocator::allocate):
2321         * bmalloc/SmallTraits.h:
2322         * bmalloc/VMHeap.cpp:
2323         (bmalloc::VMHeap::allocateXSmallChunk):
2324         * bmalloc/VMHeap.h:
2325         (bmalloc::VMHeap::allocateXSmallPage):
2326         (bmalloc::VMHeap::deallocateXSmallPage):
2327         * bmalloc/XSmallAllocator.h: Added.
2328         (bmalloc::XSmallAllocator::isNull):
2329         (bmalloc::XSmallAllocator::canAllocate):
2330         (bmalloc::XSmallAllocator::XSmallAllocator):
2331         (bmalloc::XSmallAllocator::line):
2332         (bmalloc::XSmallAllocator::allocate):
2333         (bmalloc::XSmallAllocator::objectCount):
2334         (bmalloc::XSmallAllocator::derefCount):
2335         (bmalloc::XSmallAllocator::refill):
2336         * bmalloc/XSmallChunk.h: Added.
2337         * bmalloc/XSmallLine.h: Added.
2338         * bmalloc/XSmallPage.h: Added.
2339         * bmalloc/XSmallTraits.h: Added.
2340         * bmalloc/bmalloc.h:
2341         (bmalloc::api::realloc): Boiler-plate copy, as above.
2342
2343 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
2344
2345         MallocBench should scavenge explicitly instead of waiting
2346         https://bugs.webkit.org/show_bug.cgi?id=131661
2347
2348         Reviewed by Andreas Kling.
2349
2350         Added explicit scavenge support to bmalloc. This isn't a memory win,
2351         since bmalloc's per-thread cache is so small. But it makes testing
2352         simpler.
2353
2354         * bmalloc/Allocator.cpp:
2355         (bmalloc::Allocator::~Allocator):
2356         (bmalloc::Allocator::scavenge):
2357         * bmalloc/Allocator.h:
2358         * bmalloc/Cache.cpp:
2359         (bmalloc::Cache::operator new):
2360         (bmalloc::Cache::operator delete):
2361         (bmalloc::Cache::Cache):
2362         (bmalloc::Cache::scavenge):
2363         * bmalloc/Cache.h:
2364         * bmalloc/Deallocator.cpp:
2365         (bmalloc::Deallocator::~Deallocator):
2366         (bmalloc::Deallocator::scavenge):
2367         * bmalloc/Deallocator.h: Factored existing scavenging code into helper
2368         functions, for reuse.
2369
2370         * bmalloc/Heap.cpp:
2371         (bmalloc::sleep):
2372         (bmalloc::Heap::concurrentScavenge):
2373         (bmalloc::Heap::scavenge):
2374         (bmalloc::Heap::scavengeSmallPages):
2375         (bmalloc::Heap::scavengeMediumPages):
2376         (bmalloc::Heap::scavengeLargeRanges):
2377         * bmalloc/Heap.h: Made scavenge sleep duration a parameter. Forced
2378         scavenging -- in response to a benchmark or a low memory warning --
2379         wants to complete as soon as possible, so its sleep duration is 0.
2380
2381         * bmalloc/bmalloc.h:
2382         (bmalloc::api::scavenge):
2383         * bmalloc/mbmalloc.cpp: Exported the scavenge API for MallocBench's use.
2384
2385 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
2386
2387         Use 4kB pages on Mac
2388         https://bugs.webkit.org/show_bug.cgi?id=131658
2389
2390         Reviewed by Sam Weinig.
2391
2392         This reduces memory use a lot on Membuster:
2393
2394                                                                   base                      patch                                Δ
2395                 Execution Time:
2396                     reddit_memory_warning                         18ms                       17ms                   ^ 1.06x faster
2397                     flickr_memory_warning                         34ms                       36ms                   ! 1.06x slower
2398                     theverge_memory_warning                       39ms                       41ms                   ! 1.05x slower
2399
2400                     <geometric mean>                              29ms                       29ms                   ! 1.02x slower
2401                     <arithmetic mean>                             30ms                       31ms                   ! 1.03x slower
2402                     <harmonic mean>                               27ms                       27ms                    ^ 1.0x faster
2403
2404                 Peak Memory:
2405                     reddit_memory_warning                     16,412kB                   16,436kB                    ! 1.0x bigger
2406                     flickr_memory_warning                     30,120kB                   30,184kB                    ! 1.0x bigger
2407                     theverge_memory_warning                   33,408kB                   33,420kB                    ! 1.0x bigger
2408
2409                     <geometric mean>                          25,466kB                   25,499kB                    ! 1.0x bigger
2410                     <arithmetic mean>                         26,647kB                   26,680kB                    ! 1.0x bigger
2411                     <harmonic mean>                           24,181kB                   24,214kB                    ! 1.0x bigger
2412
2413                 Memory at End:
2414                     reddit_memory_warning                      2,404kB                    1,920kB                  ^ 1.25x smaller
2415                     flickr_memory_warning                      3,764kB                    3,072kB                  ^ 1.23x smaller
2416                     theverge_memory_warning                    3,648kB                    3,132kB                  ^ 1.16x smaller
2417
2418                     <geometric mean>                           3,208kB                    2,644kB                  ^ 1.21x smaller
2419                     <arithmetic mean>                          3,272kB                    2,708kB                  ^ 1.21x smaller
2420                     <harmonic mean>                            3,139kB                    2,574kB                  ^ 1.22x smaller
2421
2422
2423         * bmalloc.xcodeproj/project.pbxproj:
2424         * bmalloc/BPlatform.h: Added.
2425         * bmalloc/VMAllocate.h: Only use 16kB pages on iOS because the page size
2426         is 4kB on Mac.
2427
2428 2014-04-14  Alexey Proskuryakov  <ap@apple.com>
2429
2430         Fixed svn:ignore on bmalloc.xcodeproj, it had erroneous leading spaces.
2431
2432         * bmalloc.xcodeproj: Modified property svn:ignore.
2433
2434 2014-04-13  Geoffrey Garen  <ggaren@apple.com>
2435
2436         Fixed some mbmalloc exports
2437         https://bugs.webkit.org/show_bug.cgi?id=131599
2438
2439         Reviewed by Ryosuke Niwa.
2440
2441         * bmalloc.xcodeproj/project.pbxproj: Made some headers a private part
2442         of the project, so we can call them from API.
2443
2444         * bmalloc/mbmalloc.cpp: Marked the mbmalloc functions with default
2445         visibility, so they show up as exported in the .dylib.
2446
2447 2014-04-09  Geoffrey Garen  <ggaren@apple.com>
2448
2449         Put bmalloc headers in the right place
2450         https://bugs.webkit.org/show_bug.cgi?id=131464
2451
2452         Reviewed by Mark Rowe.
2453
2454         * Configurations/bmalloc.xcconfig: Set PRIVATE_HEADERS_FOLDER_PATH to
2455         specify that we don't just want to dump all of our generically-named
2456         headers into /usr/local/include.
2457
2458 2014-04-08  Geoffrey Garen  <ggaren@apple.com>
2459
2460         Made bmalloc more #include friendly
2461         https://bugs.webkit.org/show_bug.cgi?id=131386
2462
2463         Reviewed by Andreas Kling.
2464
2465         Marked a bunch of headers private so they can be used from client code
2466         that #includes bmalloc.h.
2467
2468         Renamed ASSERT macros to BASSERT. This matches their header, which already
2469         had to be renamed, and fixes conflicts with WTF's ASSERT macros.
2470
2471         * bmalloc.xcodeproj/project.pbxproj:
2472         * bmalloc/Allocator.cpp:
2473         (bmalloc::Allocator::allocateSlowCase):
2474         * bmalloc/AsyncTask.h:
2475         (bmalloc::Function>::runSlowCase):
2476         * bmalloc/BAssert.h:
2477         * bmalloc/BoundaryTag.h:
2478         (bmalloc::BoundaryTag::setSize):
2479         * bmalloc/BoundaryTagInlines.h:
2480         (bmalloc::validate):
2481         (bmalloc::BoundaryTag::init):
2482         (bmalloc::BoundaryTag::deallocate):
2483         (bmalloc::BoundaryTag::splitLarge):
2484         (bmalloc::BoundaryTag::allocate):
2485         * bmalloc/Chunk.h:
2486         * bmalloc/Deallocator.cpp:
2487         (bmalloc::Deallocator::processObjectLog):
2488         (bmalloc::Deallocator::deallocateSlowCase):
2489         * bmalloc/Deallocator.h:
2490         (bmalloc::Deallocator::deallocateFastCase):
2491         * bmalloc/FixedVector.h:
2492         (bmalloc::Capacity>::operator):
2493         (bmalloc::Capacity>::push):
2494         (bmalloc::Capacity>::pop):
2495         (bmalloc::Capacity>::shrink):
2496         * bmalloc/Heap.cpp:
2497         (bmalloc::Heap::allocateLarge):
2498         * bmalloc/LargeChunk.h:
2499         (bmalloc::LargeChunk::get):
2500         (bmalloc::LargeChunk::endTag):
2501         * bmalloc/Line.h:
2502         (bmalloc::Line<Traits>::concurrentRef):
2503         (bmalloc::Line<Traits>::deref):
2504         * bmalloc/MediumAllocator.h:
2505         (bmalloc::MediumAllocator::allocate):
2506         * bmalloc/ObjectType.h:
2507         (bmalloc::isSmall):
2508         * bmalloc/Page.h:
2509         (bmalloc::Page<Traits>::ref):
2510         (bmalloc::Page<Traits>::deref):
2511         * bmalloc/PerThread.h:
2512         (bmalloc::PerThread<T>::getSlowCase):
2513         * bmalloc/SegregatedFreeList.cpp:
2514         (bmalloc::SegregatedFreeList::SegregatedFreeList):
2515         (bmalloc::SegregatedFreeList::insert):
2516         * bmalloc/SmallAllocator.h:
2517         (bmalloc::SmallAllocator::allocate):
2518         (bmalloc::SmallAllocator::refill):
2519         * bmalloc/Syscall.h:
2520         * bmalloc/VMAllocate.h:
2521         (bmalloc::vmValidate):
2522         (bmalloc::vmAllocate):
2523         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2524         * bmalloc/Vector.h:
2525         (bmalloc::Vector<T>::operator):
2526         (bmalloc::Vector<T>::pop):
2527         (bmalloc::Vector<T>::shrink):
2528         * bmalloc/XLargeChunk.h:
2529         (bmalloc::XLargeChunk::range):
2530         (bmalloc::XLargeChunk::size):
2531
2532 2014-04-08  Geoffrey Garen  <ggaren@apple.com>
2533
2534         Removed an unused file.
2535
2536         Unreviewed.
2537
2538         * bmalloc/AsyncTask.cpp: Removed.
2539
2540 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2541
2542         Build bmalloc on Mac
2543         https://bugs.webkit.org/show_bug.cgi?id=131333
2544
2545         Reviewed by Mark Rowe.
2546
2547         * Makefile: Added. For make clients.
2548
2549         These files are required for building any project in WebKit. I copied
2550         them from WTF:
2551         * Configurations: Added.
2552         * Configurations/Base.xcconfig: Added.
2553         * Configurations/DebugRelease.xcconfig: Added.
2554         * Configurations/bmalloc.xcconfig: Added.
2555         * Configurations/iOS.xcconfig: Added.
2556         * Configurations/mbmalloc.xcconfig: Added.
2557
2558         * bmalloc.xcodeproj/project.pbxproj: I removed per-project-file stuff
2559         from here because everything is in .xcconfig files now.
2560
2561         I had to fix a bunch of minor warnings, since they're enabled in our
2562         .xcconfig files:
2563
2564         * bmalloc/AsyncTask.h:
2565         (bmalloc::Function>::AsyncTask):
2566         * bmalloc/BAssert.h:
2567         * bmalloc/BoundaryTagInlines.h:
2568         (bmalloc::validate):
2569         * bmalloc/Heap.cpp:
2570         (bmalloc::Heap::Heap):
2571         (bmalloc::Heap::allocateLarge):
2572         (bmalloc::Heap::deallocateLarge):
2573         * bmalloc/Mutex.h:
2574         (bmalloc::Mutex::Mutex): Deleted.
2575         * bmalloc/VMAllocate.h:
2576         (bmalloc::vmValidate):
2577         * bmalloc/mbmalloc.cpp:
2578
2579 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2580
2581         bmalloc: Fixed a leak in the per-thread cache
2582         https://bugs.webkit.org/show_bug.cgi?id=131330
2583
2584         Reviewed by Andreas Kling.
2585
2586         Remember to deallocate our line caches upon thread exit.
2587
2588         * bmalloc/Deallocator.cpp:
2589         (bmalloc::Deallocator::~Deallocator):
2590
2591 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2592
2593         bmalloc: rolled out the tryLock experiment
2594         https://bugs.webkit.org/show_bug.cgi?id=131328
2595
2596         Reviewed by Andreas Kling.
2597
2598         It wasn't a speedup.
2599
2600         * bmalloc.xcodeproj/project.pbxproj:
2601         * bmalloc/Allocator.cpp:
2602         (bmalloc::Allocator::processSmallAllocatorLog):
2603         (bmalloc::Allocator::processMediumAllocatorLog):
2604         * bmalloc/Deallocator.cpp:
2605         (bmalloc::Deallocator::processObjectLog):
2606         (bmalloc::Deallocator::deallocateSlowCase):
2607         (bmalloc::Deallocator::deallocateSmallLine):
2608         (bmalloc::Deallocator::deallocateMediumLine):
2609         * bmalloc/Deallocator.h:
2610         (bmalloc::Deallocator::deallocateFastCase):
2611         * bmalloc/Heap.h:
2612         (bmalloc::Heap::deallocateSmallLine):
2613         (bmalloc::Heap::deallocateMediumLine):
2614         * bmalloc/Line.h:
2615         (bmalloc::Line<Traits>::deref):
2616         * bmalloc/Page.h:
2617         (bmalloc::Page<Traits>::deref):
2618
2619 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2620
2621         bmalloc
2622         https://bugs.webkit.org/show_bug.cgi?id=131170
2623
2624         Reviewed by Andreas Kling.
2625
2626         Initial commit.
2627
2628         * bmalloc: Added.
2629         * bmalloc.xcodeproj: Added.
2630         * bmalloc.xcodeproj/project.pbxproj: Added.
2631         * bmalloc/Algorithm.h: Added.
2632         (bmalloc::max):
2633         (bmalloc::min):
2634         (bmalloc::mask):
2635         (bmalloc::test):
2636         (bmalloc::roundUpToMultipleOf):
2637         (bmalloc::roundDownToMultipleOf):
2638         (bmalloc::sizeOf):
2639         (bmalloc::bitCount):
2640         (bmalloc::isPowerOfTwo):
2641         * bmalloc/Allocator.cpp: Added.
2642         (bmalloc::Allocator::Allocator):
2643         (bmalloc::Allocator::~Allocator):
2644         (bmalloc::Allocator::log):
2645         (bmalloc::Allocator::processSmallAllocatorLog):
2646         (bmalloc::Allocator::processMediumAllocatorLog):
2647         (bmalloc::Allocator::allocateLarge):
2648         (bmalloc::Allocator::allocateXLarge):
2649         (bmalloc::Allocator::allocateMedium):
2650         (bmalloc::Allocator::allocateSlowCase):
2651         * bmalloc/Allocator.h: Added.
2652         (bmalloc::Allocator::smallAllocatorFor):
2653         (bmalloc::Allocator::allocateFastCase):
2654         (bmalloc::Allocator::allocate):
2655         * bmalloc/AsyncTask.cpp: Added.
2656         (bmalloc::AsyncTask<Function>::runSlowCase):
2657         (bmalloc::AsyncTask<Function>::pthreadEntryPoint):
2658         (bmalloc::AsyncTask<Function>::entryPoint):
2659         * bmalloc/AsyncTask.h: Added.
2660         (bmalloc::Function>::AsyncTask):
2661         (bmalloc::Function>::join):
2662         (bmalloc::Function>::run):
2663         (bmalloc::Function>::runSlowCase):
2664         (bmalloc::Function>::pthreadEntryPoint):
2665         (bmalloc::Function>::entryPoint):
2666         * bmalloc/BAssert.h: Added.
2667         * bmalloc/BeginTag.h: Added.
2668         (bmalloc::BeginTag::isInFreeList):
2669         * bmalloc/BoundaryTag.h: Added.
2670         (bmalloc::BoundaryTag::isXLarge):
2671         (bmalloc::BoundaryTag::setXLarge):
2672         (bmalloc::BoundaryTag::isFree):
2673         (bmalloc::BoundaryTag::setFree):
2674         (bmalloc::BoundaryTag::isEnd):
2675         (bmalloc::BoundaryTag::setEnd):
2676         (bmalloc::BoundaryTag::hasPhysicalPages):
2677         (bmalloc::BoundaryTag::setHasPhysicalPages):
2678         (bmalloc::BoundaryTag::isNull):
2679         (bmalloc::BoundaryTag::clear):
2680         (bmalloc::BoundaryTag::size):
2681         (bmalloc::BoundaryTag::setSize):
2682         (bmalloc::BoundaryTag::prev):
2683         (bmalloc::BoundaryTag::next):
2684         * bmalloc/BoundaryTagInlines.h: Added.
2685         (bmalloc::validate):
2686         (bmalloc::validatePrev):
2687         (bmalloc::validateNext):
2688         (bmalloc::BoundaryTag::init):
2689         (bmalloc::BoundaryTag::mergeLargeLeft):
2690         (bmalloc::BoundaryTag::mergeLargeRight):
2691         (bmalloc::BoundaryTag::mergeLarge):
2692         (bmalloc::BoundaryTag::deallocate):
2693         (bmalloc::BoundaryTag::splitLarge):
2694         (bmalloc::BoundaryTag::allocate):
2695         * bmalloc/Cache.cpp: Added.
2696         (bmalloc::Cache::operator new):
2697         (bmalloc::Cache::operator delete):
2698         (bmalloc::Cache::Cache):
2699         (bmalloc::Cache::allocateSlowCase):
2700         (bmalloc::Cache::allocateSlowCaseNullCache):
2701         (bmalloc::Cache::deallocateSlowCase):
2702         (bmalloc::Cache::deallocateSlowCaseNullCache):
2703         * bmalloc/Cache.h: Added.
2704         (bmalloc::Cache::allocator):
2705         (bmalloc::Cache::deallocator):
2706         (bmalloc::Cache::allocateFastCase):
2707         (bmalloc::Cache::deallocateFastCase):
2708         (bmalloc::Cache::allocate):
2709         (bmalloc::Cache::deallocate):
2710         * bmalloc/Chunk.h: Added.
2711         (bmalloc::Chunk::begin):
2712         (bmalloc::Chunk::end):
2713         (bmalloc::Chunk::lines):
2714         (bmalloc::Chunk::pages):
2715         * bmalloc/Deallocator.cpp: Added.
2716         (bmalloc::Deallocator::Deallocator):
2717         (bmalloc::Deallocator::~Deallocator):
2718         (bmalloc::Deallocator::deallocateLarge):
2719         (bmalloc::Deallocator::deallocateXLarge):
2720         (bmalloc::Deallocator::processObjectLog):
2721         (bmalloc::Deallocator::deallocateSlowCase):
2722         (bmalloc::Deallocator::deallocateSmallLine):
2723         (bmalloc::Deallocator::allocateSmallLine):
2724         (bmalloc::Deallocator::deallocateMediumLine):
2725         (bmalloc::Deallocator::allocateMediumLine):
2726         * bmalloc/Deallocator.h: Added.
2727         (bmalloc::Deallocator::deallocateFastCase):
2728         (bmalloc::Deallocator::deallocate):
2729         * bmalloc/EndTag.h: Added.
2730         (bmalloc::EndTag::operator=):
2731         * bmalloc/FixedVector.h: Added.
2732         (bmalloc::FixedVector::begin):
2733         (bmalloc::FixedVector::end):
2734         (bmalloc::FixedVector::size):
2735         (bmalloc::FixedVector::capacity):
2736         (bmalloc::FixedVector::clear):
2737         (bmalloc::FixedVector::isEmpty):
2738         (bmalloc::Capacity>::FixedVector):
2739         (bmalloc::Capacity>::operator):
2740         (bmalloc::Capacity>::push):
2741         (bmalloc::Capacity>::pop):
2742         (bmalloc::Capacity>::shrink):
2743         * bmalloc/Heap.cpp: Added.
2744         (bmalloc::sleep):
2745         (bmalloc::Heap::Heap):
2746         (bmalloc::Heap::concurrentScavenge):
2747         (bmalloc::Heap::scavengeSmallPages):
2748         (bmalloc::Heap::scavengeMediumPages):
2749         (bmalloc::Heap::scavengeLargeRanges):
2750         (bmalloc::Heap::allocateSmallLineSlowCase):
2751         (bmalloc::Heap::allocateMediumLineSlowCase):
2752         (bmalloc::Heap::allocateXLarge):
2753         (bmalloc::Heap::deallocateXLarge):
2754         (bmalloc::Heap::allocateLarge):
2755         (bmalloc::Heap::deallocateLarge):
2756         * bmalloc/Heap.h: Added.
2757         (bmalloc::Heap::deallocateSmallLine):
2758         (bmalloc::Heap::allocateSmallLine):
2759         (bmalloc::Heap::deallocateMediumLine):
2760         (bmalloc::Heap::allocateMediumLine):
2761         * bmalloc/Inline.h: Added.
2762         * bmalloc/LargeChunk.h: Added.
2763         (bmalloc::LargeChunk::begin):
2764         (bmalloc::LargeChunk::end):
2765         (bmalloc::LargeChunk::create):
2766         (bmalloc::LargeChunk::get):
2767         (bmalloc::LargeChunk::beginTag):
2768         (bmalloc::LargeChunk::endTag):
2769         * bmalloc/Line.h: Added.
2770         (bmalloc::Line<Traits>::begin):
2771         (bmalloc::Line<Traits>::end):
2772         (bmalloc::Line<Traits>::concurrentRef):
2773         (bmalloc::Line<Traits>::deref):
2774         * bmalloc/MediumAllocator.h: Added.
2775         (bmalloc::MediumAllocator::isNull):
2776         (bmalloc::MediumAllocator::MediumAllocator):
2777         (bmalloc::MediumAllocator::line):
2778         (bmalloc::MediumAllocator::allocate):
2779         (bmalloc::MediumAllocator::derefCount):
2780         (bmalloc::MediumAllocator::refill):
2781         * bmalloc/MediumChunk.h: Added.
2782         * bmalloc/MediumLine.h: Added.
2783         * bmalloc/MediumPage.h: Added.
2784         * bmalloc/MediumTraits.h: Added.
2785         * bmalloc/Mutex.cpp: Added.
2786         (bmalloc::Mutex::lockSlowCase):
2787         * bmalloc/Mutex.h: Added.
2788         (bmalloc::Mutex::Mutex):
2789         (bmalloc::Mutex::try_lock):
2790         (bmalloc::Mutex::lock):
2791         (bmalloc::Mutex::unlock):
2792         * bmalloc/ObjectType.cpp: Added.
2793         (bmalloc::objectType):
2794         * bmalloc/ObjectType.h: Added.
2795         (bmalloc::isSmallOrMedium):
2796         (bmalloc::isSmall):
2797         * bmalloc/Page.h: Added.
2798         (bmalloc::Page<Traits>::ref):
2799         (bmalloc::Page<Traits>::deref):
2800         (bmalloc::Page<Traits>::refCount):
2801         * bmalloc/PerProcess.h: Added.
2802         (bmalloc::PerProcess::mutex):
2803         (bmalloc::PerProcess<T>::getFastCase):
2804         (bmalloc::PerProcess<T>::get):
2805         (bmalloc::PerProcess<T>::getSlowCase):
2806         * bmalloc/PerThread.h: Added.
2807         (bmalloc::PerThreadStorage<Cache>::get):
2808         (bmalloc::PerThreadStorage<Cache>::init):
2809         (bmalloc::PerThreadStorage::get):
2810         (bmalloc::PerThreadStorage::init):
2811         (bmalloc::PerThread<T>::getFastCase):
2812         (bmalloc::PerThread<T>::get):
2813         (bmalloc::PerThread<T>::destructor):
2814         (bmalloc::PerThread<T>::getSlowCase):
2815         * bmalloc/Range.h: Added.
2816         (bmalloc::Range::Range):
2817         (bmalloc::Range::begin):
2818         (bmalloc::Range::end):
2819         (bmalloc::Range::size):
2820         (bmalloc::Range::operator!):
2821         (bmalloc::Range::operator<):
2822         * bmalloc/SegregatedFreeList.cpp: Added.
2823         (bmalloc::SegregatedFreeList::SegregatedFreeList):
2824         (bmalloc::SegregatedFreeList::insert):
2825         (bmalloc::SegregatedFreeList::takeGreedy):
2826         (bmalloc::SegregatedFreeList::take):
2827         * bmalloc/SegregatedFreeList.h: Added.
2828         * bmalloc/Sizes.h: Added.
2829         * bmalloc/SmallAllocator.h: Added.
2830         (bmalloc::SmallAllocator::isNull):
2831         (bmalloc::SmallAllocator::canAllocate):
2832         (bmalloc::SmallAllocator::SmallAllocator):
2833         (bmalloc::SmallAllocator::line):
2834         (bmalloc::SmallAllocator::allocate):
2835         (bmalloc::SmallAllocator::objectCount):
2836         (bmalloc::SmallAllocator::derefCount):
2837         (bmalloc::SmallAllocator::refill):
2838         * bmalloc/SmallChunk.h: Added.
2839         * bmalloc/SmallLine.h: Added.
2840         * bmalloc/SmallPage.h: Added.
2841         * bmalloc/SmallTraits.h: Added.
2842         * bmalloc/Syscall.h: Added.
2843         * bmalloc/VMAllocate.h: Added.
2844         (bmalloc::vmSize):
2845         (bmalloc::vmValidate):
2846         (bmalloc::vmAllocate):
2847         (bmalloc::vmDeallocate):
2848         (bmalloc::vmDeallocatePhysicalPages):
2849         (bmalloc::vmAllocatePhysicalPages):
2850         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2851         (bmalloc::vmAllocatePhysicalPagesSloppy):
2852         * bmalloc/VMHeap.cpp: Added.
2853         (bmalloc::VMHeap::VMHeap):
2854         (bmalloc::VMHeap::allocateSmallChunk):
2855         (bmalloc::VMHeap::allocateMediumChunk):
2856         (bmalloc::VMHeap::allocateLargeChunk):
2857         * bmalloc/VMHeap.h: Added.
2858         (bmalloc::VMHeap::allocateSmallPage):
2859         (bmalloc::VMHeap::allocateMediumPage):
2860         (bmalloc::VMHeap::allocateLargeRange):
2861         (bmalloc::VMHeap::deallocateSmallPage):
2862         (bmalloc::VMHeap::deallocateMediumPage):
2863         (bmalloc::VMHeap::deallocateLargeRange):
2864         * bmalloc/Vector.h: Added.
2865         (bmalloc::Vector::begin):
2866         (bmalloc::Vector::end):
2867         (bmalloc::Vector::size):
2868         (bmalloc::Vector::capacity):
2869         (bmalloc::Vector::last):
2870         (bmalloc::Vector::pop):
2871         (bmalloc::Vector<T>::Vector):
2872         (bmalloc::Vector<T>::~Vector):
2873         (bmalloc::Vector<T>::operator):
2874         (bmalloc::Vector<T>::push):
2875         (bmalloc::Vector<T>::pop):
2876         (bmalloc::Vector<T>::shrink):
2877         (bmalloc::Vector<T>::reallocateBuffer):
2878         (bmalloc::Vector<T>::shrinkCapacity):
2879         (bmalloc::Vector<T>::growCapacity):
2880         * bmalloc/XLargeChunk.h: Added.
2881         (bmalloc::XLargeChunk::get):
2882         (bmalloc::XLargeChunk::begin):
2883         (bmalloc::XLargeChunk::XLargeChunk):
2884         (bmalloc::XLargeChunk::create):
2885         (bmalloc::XLargeChunk::destroy):
2886         (bmalloc::XLargeChunk::range):
2887         (bmalloc::XLargeChunk::size):
2888         * bmalloc/bmalloc.h: Added.
2889         (bmalloc::api::malloc):
2890         (bmalloc::api::free):
2891         (bmalloc::api::realloc):
2892         * bmalloc/mbmalloc.cpp: Added.
2893