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