Large virtual memory region allocation requires MMAP_NORESERVE in Linux
[WebKit-https.git] / Source / bmalloc / ChangeLog
1 2017-09-03  Yusuke Suzuki  <utatane.tea@gmail.com>
2
3         Large virtual memory region allocation requires MMAP_NORESERVE in Linux
4         https://bugs.webkit.org/show_bug.cgi?id=176211
5
6         Reviewed by Geoffrey Garen.
7
8         In Linux, we cannot allocate very large memory region without MMAP_NORESERVE.
9         Linux kernel needs to reserve swap area for allocated memory region. If the
10         swap area is exhausted, kernel fails to allocate the memory region with ENOMEM.
11
12         This patch adds MMAP_NORESERVE to mmap flags in Linux. By adding this flag,
13         mmap does not need to reserve swap area for the reserved memory region.
14         This allows us to reserve very large memory region that is necessary for Gigacage.
15
16         * bmalloc/BPlatform.h:
17         * bmalloc/VMAllocate.h:
18         (bmalloc::tryVMAllocate):
19
20 2017-08-22  Filip Pizlo  <fpizlo@apple.com>
21
22         Strings need to be in some kind of gigacage
23         https://bugs.webkit.org/show_bug.cgi?id=174924
24
25         Reviewed by Oliver Hunt.
26         
27         This adds a StringGigacage.
28
29         * bmalloc/Gigacage.cpp:
30         * bmalloc/Gigacage.h:
31         (Gigacage::name):
32         (Gigacage::basePtr):
33         (Gigacage::forEachKind):
34         * bmalloc/HeapKind.h:
35         (bmalloc::isGigacage):
36         (bmalloc::gigacageKind):
37         (bmalloc::heapKind):
38
39 2017-08-30  Matt Lewis  <jlewis3@apple.com>
40
41         Unreviewed, rolling out r221384.
42
43         This patch caused multiple 32-bit JSC test failures.
44
45         Reverted changeset:
46
47         "Strings need to be in some kind of gigacage"
48         https://bugs.webkit.org/show_bug.cgi?id=174924
49         http://trac.webkit.org/changeset/221384
50
51 2017-08-22  Filip Pizlo  <fpizlo@apple.com>
52
53         Strings need to be in some kind of gigacage
54         https://bugs.webkit.org/show_bug.cgi?id=174924
55
56         Reviewed by Oliver Hunt.
57         
58         This adds a StringGigacage.
59
60         * bmalloc/Gigacage.cpp:
61         * bmalloc/Gigacage.h:
62         (Gigacage::name):
63         (Gigacage::basePtr):
64         (Gigacage::forEachKind):
65         * bmalloc/HeapKind.h:
66         (bmalloc::isGigacage):
67         (bmalloc::gigacageKind):
68         (bmalloc::heapKind):
69
70 2017-08-25  Daniel Bates  <dabates@apple.com>
71
72         Demarcate code added due to lack of NSDMI for aggregates
73         https://bugs.webkit.org/show_bug.cgi?id=175990
74
75         Reviewed by Andy Estes.
76
77         * bmalloc/BPlatform.h:
78         * bmalloc/List.h: Be explicit when initializing m_node to improve readability.
79         (bmalloc::ListNode::ListNode):
80
81 2017-08-23  Filip Pizlo  <fpizlo@apple.com>
82
83         Reduce Gigacage sizes
84         https://bugs.webkit.org/show_bug.cgi?id=175920
85
86         Reviewed by Mark Lam.
87
88         This introduces the ability to have different gigacage sizes for different gigacages, and uses it to reduce the size of both
89         gigacages, but to different extents: Primitive gets 32GB with a 16GB runway and JSValue gets 16GB.
90
91         This is a ~10% membuster progression on my Mac Pro.
92
93         * bmalloc/Gigacage.cpp:
94         (Gigacage::ensureGigacage):
95         * bmalloc/Gigacage.h:
96         (Gigacage::size):
97         (Gigacage::alignment):
98         (Gigacage::mask):
99         (Gigacage::runway):
100         (Gigacage::totalSize):
101         (Gigacage::caged):
102         * bmalloc/Heap.cpp:
103         (bmalloc::Heap::Heap):
104         (bmalloc::Heap::gigacageSize):
105         * bmalloc/Heap.h:
106
107 2017-08-08  Filip Pizlo  <fpizlo@apple.com>
108
109         Baseline JIT should do caging
110         https://bugs.webkit.org/show_bug.cgi?id=175037
111
112         Reviewed by Mark Lam.
113         
114         This centralizes the notion of permanently enabling the primitive gigacage, which we only do in jsc
115         and WebProcess.
116         
117         This saves the baseline JIT from emitting some code. Otherwise it would always have to emit enabled
118         checks on each typed array access.
119
120         * bmalloc/Gigacage.cpp:
121         (Gigacage::primitiveGigacageDisabled):
122         (Gigacage::disableDisablingPrimitiveGigacageIfShouldBeEnabled):
123         (Gigacage::isDisablingPrimitiveGigacageDisabled):
124         * bmalloc/Gigacage.h:
125         (Gigacage::isPrimitiveGigacagePermanentlyEnabled):
126         (Gigacage::canPrimitiveGigacageBeDisabled):
127
128 2017-08-08  Ryan Haddad  <ryanhaddad@apple.com>
129
130         Unreviewed, rolling out r220368.
131
132         This change caused WK1 tests to exit early with crashes.
133
134         Reverted changeset:
135
136         "Baseline JIT should do caging"
137         https://bugs.webkit.org/show_bug.cgi?id=175037
138         http://trac.webkit.org/changeset/220368
139
140 2017-08-07  Filip Pizlo  <fpizlo@apple.com>
141
142         Baseline JIT should do caging
143         https://bugs.webkit.org/show_bug.cgi?id=175037
144
145         Reviewed by Mark Lam.
146         
147         This centralizes the notion of permanently enabling the primitive gigacage, which we only do in jsc
148         and WebProcess.
149         
150         This saves the baseline JIT from emitting some code. Otherwise it would always have to emit enabled
151         checks on each typed array access.
152
153         * bmalloc/Gigacage.cpp:
154         (Gigacage::primitiveGigacageDisabled):
155         (Gigacage::disableDisablingPrimitiveGigacageIfShouldBeEnabled):
156         (Gigacage::isDisablingPrimitiveGigacageDisabled):
157         * bmalloc/Gigacage.h:
158         (Gigacage::isPrimitiveGigacagePermanentlyEnabled):
159         (Gigacage::canPrimitiveGigacageBeDisabled):
160
161 2017-08-06  Filip Pizlo  <fpizlo@apple.com>
162
163         Primitive auxiliaries and JSValue auxiliaries should have separate gigacages
164         https://bugs.webkit.org/show_bug.cgi?id=174919
165
166         Reviewed by Keith Miller.
167         
168         This introduces two kinds of Gigacage, Primitive and JSValue. This translates to two kinds of
169         HeapKind, PrimitiveGigacage and JSValueGigacage.
170         
171         The new support functionality required turning Inline.h into BInline.h, and INLINE into BINLINE, and
172         NO_INLINE into BNO_INLINE.
173
174         * bmalloc.xcodeproj/project.pbxproj:
175         * bmalloc/Allocator.cpp:
176         (bmalloc::Allocator::refillAllocatorSlowCase):
177         (bmalloc::Allocator::refillAllocator):
178         (bmalloc::Allocator::allocateLarge):
179         (bmalloc::Allocator::allocateLogSizeClass):
180         * bmalloc/AsyncTask.h:
181         * bmalloc/BInline.h: Copied from Source/bmalloc/bmalloc/Inline.h.
182         * bmalloc/Cache.cpp:
183         (bmalloc::Cache::tryAllocateSlowCaseNullCache):
184         (bmalloc::Cache::allocateSlowCaseNullCache):
185         (bmalloc::Cache::deallocateSlowCaseNullCache):
186         (bmalloc::Cache::reallocateSlowCaseNullCache):
187         * bmalloc/Deallocator.cpp:
188         * bmalloc/Gigacage.cpp:
189         (Gigacage::PrimitiveDisableCallbacks::PrimitiveDisableCallbacks):
190         (Gigacage::ensureGigacage):
191         (Gigacage::disablePrimitiveGigacage):
192         (Gigacage::addPrimitiveDisableCallback):
193         (Gigacage::removePrimitiveDisableCallback):
194         (Gigacage::Callbacks::Callbacks): Deleted.
195         (Gigacage::disableGigacage): Deleted.
196         (Gigacage::addDisableCallback): Deleted.
197         (Gigacage::removeDisableCallback): Deleted.
198         * bmalloc/Gigacage.h:
199         (Gigacage::name):
200         (Gigacage::basePtr):
201         (Gigacage::forEachKind):
202         (Gigacage::caged):
203         (Gigacage::isCaged):
204         * bmalloc/Heap.cpp:
205         (bmalloc::Heap::Heap):
206         (bmalloc::Heap::usingGigacage):
207         (bmalloc::Heap::gigacageBasePtr):
208         * bmalloc/Heap.h:
209         * bmalloc/HeapKind.h:
210         (bmalloc::isGigacage):
211         (bmalloc::gigacageKind):
212         (bmalloc::heapKind):
213         * bmalloc/Inline.h: Removed.
214         * bmalloc/Map.h:
215         * bmalloc/PerProcess.h:
216         (bmalloc::PerProcess<T>::getFastCase):
217         (bmalloc::PerProcess<T>::get):
218         (bmalloc::PerProcess<T>::getSlowCase):
219         * bmalloc/PerThread.h:
220         (bmalloc::PerThread<T>::getFastCase):
221         * bmalloc/Vector.h:
222         (bmalloc::Vector<T>::push):
223         (bmalloc::Vector<T>::shrinkCapacity):
224         (bmalloc::Vector<T>::growCapacity):
225
226 2017-08-02  Filip Pizlo  <fpizlo@apple.com>
227
228         If Gigacage is disabled, bmalloc should service large aligned memory allocation requests through vmAllocate
229         https://bugs.webkit.org/show_bug.cgi?id=175085
230
231         Reviewed by Saam Barati.
232         
233         This fixes a problem where if we used gmalloc, WebAssembly memory allocations would still use
234         bmalloc's large allocator.
235         
236         We want to use the page allocator for those "large" allocations when the Gigacage is disabled.
237
238         * bmalloc/DebugHeap.cpp:
239         (bmalloc::DebugHeap::DebugHeap):
240         (bmalloc::DebugHeap::memalignLarge):
241         (bmalloc::DebugHeap::freeLarge):
242         * bmalloc/DebugHeap.h:
243         * bmalloc/Heap.cpp:
244         (bmalloc::Heap::tryAllocateLarge):
245         (bmalloc::Heap::deallocateLarge):
246
247 2017-08-02  Filip Pizlo  <fpizlo@apple.com>
248
249         We should be OK with the gigacage being disabled on gmalloc
250         https://bugs.webkit.org/show_bug.cgi?id=175082
251
252         Reviewed by Michael Saboff.
253         
254         This adds Gigacage::shouldBeEnabled(), which returns false when we're using gmalloc or other things
255         that enable DebugHeap.
256
257         * bmalloc/Environment.cpp:
258         (bmalloc::Environment::Environment):
259         * bmalloc/Environment.h:
260         * bmalloc/Gigacage.cpp:
261         (Gigacage::ensureGigacage):
262         (Gigacage::shouldBeEnabled):
263         * bmalloc/Gigacage.h:
264         * bmalloc/Heap.cpp:
265         (bmalloc::Heap::Heap):
266         * bmalloc/Heap.h:
267
268 2017-08-01  Filip Pizlo  <fpizlo@apple.com>
269
270         Bmalloc and GC should put auxiliaries (butterflies, typed array backing stores) in a gigacage (separate multi-GB VM region)
271         https://bugs.webkit.org/show_bug.cgi?id=174727
272
273         Reviewed by Mark Lam.
274         
275         This adds a mechanism for managing multiple isolated heaps in bmalloc. For now, these isoheaps
276         (isolated heaps) have a very simple relationship with each other and with the rest of bmalloc:
277         
278         - You have to choose how many isoheaps you will have statically. See numHeaps in HeapKind.h.
279         
280         - Because numHeaps is static, each isoheap gets fast thread-local allocation. Basically, we have a
281           Cache for each heap kind.
282         
283         - Each isoheap gets its own Heap.
284         
285         - Each Heap gets a scavenger thread.
286         
287         - Some things, like Zone/VMHeap/Scavenger, are per-process.
288         
289         Most of the per-HeapKind functionality is handled by PerHeapKind<>.
290         
291         This approach is ideal for supporting special per-HeapKind behaviors. For now we have two heaps:
292         the Primary heap for normal malloc and the Gigacage. The gigacage is a 64GB-aligned 64GB virtual
293         region that we now use for variable-length random-access allocations. No Primary allocations will
294         go into the Gigacage.
295
296         * CMakeLists.txt:
297         * bmalloc.xcodeproj/project.pbxproj:
298         * bmalloc/AllocationKind.h: Added.
299         * bmalloc/Allocator.cpp:
300         (bmalloc::Allocator::Allocator):
301         (bmalloc::Allocator::tryAllocate):
302         (bmalloc::Allocator::allocateImpl):
303         (bmalloc::Allocator::reallocate):
304         (bmalloc::Allocator::refillAllocatorSlowCase):
305         (bmalloc::Allocator::allocateLarge):
306         * bmalloc/Allocator.h:
307         * bmalloc/BExport.h: Added.
308         * bmalloc/Cache.cpp:
309         (bmalloc::Cache::scavenge):
310         (bmalloc::Cache::Cache):
311         (bmalloc::Cache::tryAllocateSlowCaseNullCache):
312         (bmalloc::Cache::allocateSlowCaseNullCache):
313         (bmalloc::Cache::deallocateSlowCaseNullCache):
314         (bmalloc::Cache::reallocateSlowCaseNullCache):
315         (bmalloc::Cache::operator new): Deleted.
316         (bmalloc::Cache::operator delete): Deleted.
317         * bmalloc/Cache.h:
318         (bmalloc::Cache::tryAllocate):
319         (bmalloc::Cache::allocate):
320         (bmalloc::Cache::deallocate):
321         (bmalloc::Cache::reallocate):
322         * bmalloc/Deallocator.cpp:
323         (bmalloc::Deallocator::Deallocator):
324         (bmalloc::Deallocator::scavenge):
325         (bmalloc::Deallocator::processObjectLog):
326         (bmalloc::Deallocator::deallocateSlowCase):
327         * bmalloc/Deallocator.h:
328         * bmalloc/Gigacage.cpp: Added.
329         (Gigacage::Callback::Callback):
330         (Gigacage::Callback::function):
331         (Gigacage::Callbacks::Callbacks):
332         (Gigacage::ensureGigacage):
333         (Gigacage::disableGigacage):
334         (Gigacage::addDisableCallback):
335         (Gigacage::removeDisableCallback):
336         * bmalloc/Gigacage.h: Added.
337         (Gigacage::caged):
338         (Gigacage::isCaged):
339         * bmalloc/Heap.cpp:
340         (bmalloc::Heap::Heap):
341         (bmalloc::Heap::usingGigacage):
342         (bmalloc::Heap::concurrentScavenge):
343         (bmalloc::Heap::splitAndAllocate):
344         (bmalloc::Heap::tryAllocateLarge):
345         (bmalloc::Heap::allocateLarge):
346         (bmalloc::Heap::shrinkLarge):
347         (bmalloc::Heap::deallocateLarge):
348         * bmalloc/Heap.h:
349         (bmalloc::Heap::mutex):
350         (bmalloc::Heap::kind const):
351         (bmalloc::Heap::setScavengerThreadQOSClass): Deleted.
352         * bmalloc/HeapKind.h: Added.
353         * bmalloc/ObjectType.cpp:
354         (bmalloc::objectType):
355         * bmalloc/ObjectType.h:
356         * bmalloc/PerHeapKind.h: Added.
357         (bmalloc::PerHeapKindBase::PerHeapKindBase):
358         (bmalloc::PerHeapKindBase::size):
359         (bmalloc::PerHeapKindBase::at):
360         (bmalloc::PerHeapKindBase::at const):
361         (bmalloc::PerHeapKindBase::operator[]):
362         (bmalloc::PerHeapKindBase::operator[] const):
363         (bmalloc::StaticPerHeapKind::StaticPerHeapKind):
364         (bmalloc::PerHeapKind::PerHeapKind):
365         (bmalloc::PerHeapKind::~PerHeapKind):
366         * bmalloc/PerThread.h:
367         (bmalloc::PerThread<T>::destructor):
368         (bmalloc::PerThread<T>::getSlowCase):
369         (bmalloc::PerThreadStorage<Cache>::get): Deleted.
370         (bmalloc::PerThreadStorage<Cache>::init): Deleted.
371         * bmalloc/Scavenger.cpp: Added.
372         (bmalloc::Scavenger::Scavenger):
373         (bmalloc::Scavenger::scavenge):
374         * bmalloc/Scavenger.h: Added.
375         (bmalloc::Scavenger::setScavengerThreadQOSClass):
376         (bmalloc::Scavenger::requestedScavengerThreadQOSClass const):
377         * bmalloc/VMHeap.cpp:
378         (bmalloc::VMHeap::VMHeap):
379         (bmalloc::VMHeap::tryAllocateLargeChunk):
380         * bmalloc/VMHeap.h:
381         * bmalloc/Zone.cpp:
382         (bmalloc::Zone::Zone):
383         * bmalloc/Zone.h:
384         * bmalloc/bmalloc.h:
385         (bmalloc::api::tryMalloc):
386         (bmalloc::api::malloc):
387         (bmalloc::api::tryMemalign):
388         (bmalloc::api::memalign):
389         (bmalloc::api::realloc):
390         (bmalloc::api::tryLargeMemalignVirtual):
391         (bmalloc::api::free):
392         (bmalloc::api::freeLargeVirtual):
393         (bmalloc::api::scavengeThisThread):
394         (bmalloc::api::scavenge):
395         (bmalloc::api::isEnabled):
396         (bmalloc::api::setScavengerThreadQOSClass):
397         * bmalloc/mbmalloc.cpp:
398
399 2017-08-01  Daewoong Jang  <daewoong.jang@navercorp.com>
400
401         Implement __builtin_clzl for MSVC
402         https://bugs.webkit.org/show_bug.cgi?id=174232
403
404         Reviewed by Geoffrey Garen.
405
406         * bmalloc/Algorithm.h:
407         (bmalloc::clzl):
408         (bmalloc::clzl<1>):
409         (bmalloc::__builtin_clzl):
410         * bmalloc/BPlatform.h:
411
412 2017-07-31  Mark Lam  <mark.lam@apple.com>
413
414         Fixed some comment typos.
415
416         Not reviewed.
417
418         * bmalloc/PerProcess.h:
419
420 2017-07-14  Filip Pizlo  <fpizlo@apple.com>
421
422         It should be easy to decide how WebKit yields
423         https://bugs.webkit.org/show_bug.cgi?id=174298
424
425         Reviewed by Saam Barati.
426         
427         Use sched_yield() explicitly.
428
429         * bmalloc/StaticMutex.cpp:
430         (bmalloc::StaticMutex::lockSlowCase):
431
432 2017-07-20  Chris Dumez  <cdumez@apple.com>
433
434         Replace calls to Vector::resize() with calls to more efficient shrink() / grow() when applicable
435         https://bugs.webkit.org/show_bug.cgi?id=174660
436
437         Reviewed by Geoffrey Garen.
438
439         Replace calls to Vector::resize() with calls to more efficient shrink() / grow() when applicable.
440         This essentially replaces a branch to figure out if the new size is less or greater than the
441         current size by an assertion.
442
443         * bmalloc/Map.h:
444         (bmalloc::Hash>::rehash):
445
446 2017-07-18  Andy Estes  <aestes@apple.com>
447
448         [Xcode] Enable CLANG_WARN_RANGE_LOOP_ANALYSIS
449         https://bugs.webkit.org/show_bug.cgi?id=174631
450
451         Reviewed by Tim Horton.
452
453         * Configurations/Base.xcconfig:
454
455 2017-07-18  Andy Estes  <aestes@apple.com>
456
457         [Xcode] Enable CLANG_WARN_OBJC_LITERAL_CONVERSION
458         https://bugs.webkit.org/show_bug.cgi?id=174631
459
460         Reviewed by Sam Weinig.
461
462         * Configurations/Base.xcconfig:
463
464 2017-07-18  Andy Estes  <aestes@apple.com>
465
466         [Xcode] Enable CLANG_WARN_NON_LITERAL_NULL_CONVERSION
467         https://bugs.webkit.org/show_bug.cgi?id=174631
468
469         Reviewed by Dan Bernstein.
470
471         * Configurations/Base.xcconfig:
472
473 2017-07-18  Andy Estes  <aestes@apple.com>
474
475         [Xcode] Enable CLANG_WARN_BLOCK_CAPTURE_AUTORELEASING
476         https://bugs.webkit.org/show_bug.cgi?id=174631
477
478         Reviewed by Darin Adler.
479
480         * Configurations/Base.xcconfig:
481
482 2017-07-12  Adrian Perez de Castro  <aperez@igalia.com>
483
484         bmalloc: Failure to build when the compiler specifically targets ARMv8-A / defines __ARM_ARCH_8A__
485         https://bugs.webkit.org/show_bug.cgi?id=174424
486
487         Reviewed by Michael Catanzaro.
488
489         * bmalloc/BPlatform.h: Also check for __ARCH_ARM_8A__ to detect ARMv8.
490
491 2017-07-05  Daewoong Jang  <daewoong.jang@navercorp.com>
492
493         reinterpret_cast does not evaluate to constexpr
494         https://bugs.webkit.org/show_bug.cgi?id=173622
495
496         Reviewed by Yusuke Suzuki.
497
498         * bmalloc/Algorithm.h:
499         (bmalloc::mask):
500         (bmalloc::roundUpToMultipleOf):
501
502 2017-07-03  Andy Estes  <aestes@apple.com>
503
504         [Xcode] Add an experimental setting to build with ccache
505         https://bugs.webkit.org/show_bug.cgi?id=173875
506
507         Reviewed by Tim Horton.
508
509         * Configurations/DebugRelease.xcconfig: Included ccache.xcconfig.
510
511 2017-07-01  Dan Bernstein  <mitz@apple.com>
512
513         [iOS] Remove code only needed when building for iOS 9.x
514         https://bugs.webkit.org/show_bug.cgi?id=174068
515
516         Reviewed by Tim Horton.
517
518         * bmalloc/BPlatform.h:
519         * bmalloc/VMAllocate.h:
520         (bmalloc::vmPageSizePhysical):
521
522 2017-07-01  Dan Bernstein  <mitz@apple.com>
523
524         [macOS] Remove code only needed when building for OS X Yosemite
525         https://bugs.webkit.org/show_bug.cgi?id=174067
526
527         Reviewed by Tim Horton.
528
529         * Configurations/Base.xcconfig:
530         * Configurations/DebugRelease.xcconfig:
531
532 2017-06-30  Ryosuke Niwa  <rniwa@webkit.org>
533
534         Ran sort-Xcode-project-file.
535
536         * bmalloc.xcodeproj/project.pbxproj:
537
538 2017-06-19  Geoffrey Garen  <ggaren@apple.com>
539
540         bmalloc: Add a per-thread line cache
541         https://bugs.webkit.org/show_bug.cgi?id=173552
542
543         Reviewed by Darin Adler.
544
545         Previously, any thread could allocate out of any page with free lines.
546         Now, the first thread to free a line in a page owns that page's free
547         lines until the whole page becomes free.
548
549         This patch is a big speedup on multi-threaded benchmarks.
550         tree_churn --parallel gets 14% faster on a 2-core (4-hyper-core) MacBook
551         Air and 2.85X faster on 12-core (24-hyper-core) Mac Pro. Other parallel
552         benchmarks show significant but smaller speedups.
553
554         Thread affinity is a great predictor of object lifetime. The per-thread
555         line cache avoids the pathology of shuffling pages between threads,
556         turning predictable lifetimes into unpredictable lifetimes, increasing
557         fragmentation. On tree_churn --parallel, the per-thread line cache
558         increases free memory found per page scanned by 2.85X.
559
560         Free line scanning in fragmented pages is pretty expensive relative to
561         other allocate / initialize / free operations. According to Instruments,
562         on tree_churn --parallel, scanning is about 10X more expensive than
563         freeing. This explains why a 2.85X improvement in scanning efficiency
564         translates into a 2.85X overall speedup on tree_churn --parallel.
565
566         * bmalloc/Allocator.cpp:
567         (bmalloc::Allocator::refillAllocatorSlowCase): Pass through our line
568         cache so the Heap can fill it.
569
570         * bmalloc/Deallocator.cpp:
571         (bmalloc::Deallocator::scavenge): Scavenge our line cache.
572
573         (bmalloc::Deallocator::processObjectLog): Deleted.
574
575         * bmalloc/Deallocator.h:
576         (bmalloc::Deallocator::lineCache): Added a line cache.
577
578         * bmalloc/Heap.cpp:
579         (bmalloc::Heap::deallocateLineCache): Deallocation function for thread
580         destruction.
581
582         (bmalloc::Heap::allocateSmallPage):
583         (bmalloc::Heap::deallocateSmallLine):
584         (bmalloc::Heap::allocateSmallBumpRangesByMetadata):
585         (bmalloc::Heap::allocateSmallBumpRangesByObject): Consult the new per-thread line
586         cache for allocation and deallocation.
587
588         * bmalloc/Heap.h:
589         (bmalloc::Heap::allocateSmallBumpRanges):
590         (bmalloc::Heap::derefSmallLine):
591
592         * bmalloc/List.h:
593         (bmalloc::List::remove): Remove has always been a logically static
594         operation. Declare it static now so that the Heap can remove a page from
595         a thread's line cache without holding a direct pointer to the cache.
596
597         * bmalloc/SmallPage.h:
598
599 2017-06-10  Dan Bernstein  <mitz@apple.com>
600
601         Reverted r218056 because it made the IDE reindex constantly.
602
603         * Configurations/DebugRelease.xcconfig:
604
605 2017-06-10  Dan Bernstein  <mitz@apple.com>
606
607         [Xcode] With Xcode 9 developer beta, everything rebuilds when switching between command-line and IDE
608         https://bugs.webkit.org/show_bug.cgi?id=173223
609
610         Reviewed by Sam Weinig.
611
612         The rebuilds were happening due to a difference in the compiler options that the IDE and
613         xcodebuild were specifying. Only the IDE was passing the -index-store-path option. To make
614         xcodebuild pass that option, too, set CLANG_INDEX_STORE_ENABLE to YES if it is unset, and
615         specify an appropriate path in CLANG_INDEX_STORE_PATH.
616
617         * Configurations/DebugRelease.xcconfig:
618
619 2017-06-07  Geoffrey Garen  <ggaren@apple.com>
620
621         bmalloc: memory APIs don't need to be heap members
622         https://bugs.webkit.org/show_bug.cgi?id=173076
623
624         Reviewed by Sam Weinig.
625
626         Asking the OS about memory use is unrelated to the state of bmalloc's
627         heap, so it's a better separation of concerns if related code is not 
628         part of the heap.
629
630         * bmalloc/AvailableMemory.cpp:
631         (bmalloc::memoryStatus):
632         * bmalloc/AvailableMemory.h:
633         (bmalloc::MemoryStatus::MemoryStatus):
634         (bmalloc::isUnderMemoryPressure):
635         (bmalloc::memoryFootprint):
636         (bmalloc::percentAvailableMemoryInUse):
637         * bmalloc/Heap.cpp:
638         (bmalloc::Heap::Heap):
639         (bmalloc::Heap::updateMemoryInUseParameters): Deleted.
640         * bmalloc/Heap.h:
641         (bmalloc::Heap::isUnderMemoryPressure): Deleted.
642         (bmalloc::Heap::memoryFootprint): Deleted.
643         (bmalloc::Heap::percentAvailableMemoryInUse): Deleted.
644
645 2017-06-06  Yusuke Suzuki  <utatane.tea@gmail.com>
646
647         struct does not accept initializer-form if member has initializers in GCC 4.9
648         https://bugs.webkit.org/show_bug.cgi?id=172974
649
650         Reviewed by Carlos Garcia Campos.
651
652         struct cannot accept initializer-form constructor (like, `ListNode<T> t { ... }`) if
653         the member of the struct has a default initializer.
654         Here is a simple snippet.
655
656         template<typename T>
657         struct Pair {
658             T* prev { nullptr };
659             T* next { nullptr };
660         };
661
662         Pair<int> pair { nullptr, nullptr };  // compile erorr in GCC 4.9.
663
664         Instead, we define a default constructor (to invoke default initializers) and a constructor
665         to accept the above initialization.
666
667         * bmalloc/List.h:
668         (bmalloc::ListNode::ListNode):
669         (bmalloc::List::iterator::iterator):
670
671 2017-06-06  Geoffrey Garen  <ggaren@apple.com>
672
673         Try to fix the GTK build.
674
675         Unreviewed.
676
677         * bmalloc/List.h:
678         (bmalloc::List::List):
679
680 2017-06-05  Geoffrey Garen  <ggaren@apple.com>
681
682         Try to fix the GTK build.
683
684         Unreviewed.
685
686         * bmalloc/List.h:
687
688 2017-06-02  Geoffrey Garen  <ggaren@apple.com>
689
690         bmalloc: Small and large objects should share memory
691         https://bugs.webkit.org/show_bug.cgi?id=172880
692         <rdar://problem/31494732>
693
694         Reviewed by Sam Weinig.
695
696         This reduces our high water mark memory usage on JetStream on macOS
697         by 10%-20%. It also has the nice side effect that we can free small
698         object metadata after returning from a high water mark.
699
700         No change in throughput.
701
702         Our old algorithm allocated small object chunks and large objects in
703         segregated virtual memory and never recycled addresses between them.
704         This provided a slight security benefit because we could apply guard
705         pages between the segregated ranges and we would never reuse the same
706         virtual address for object and metadata memory.
707
708         Our new algorithm allocates small object chunks from the large object
709         allocator. This naturally recycles memory between small chunks and large
710         objects, and between small chunks of different page classes. This allows
711         us to shift memory between allocation types as a program moves between
712         different phases of allocation, and to delete small object chunk metadata
713         when a program shrinks back from a high water mark.
714
715         Two intuitions I had about memory use turned out to be backwards in
716         this context:
717
718         (1) I thought that this optimization would work because it allowed you to
719         allocate and free a 4MB object and then reuse that large allocation to
720         service small allocations. In practice, the common benefit seems to be
721         the opposite: After you allocate and free many small objects, you can
722         stitch them together to allocate a large object without growing the heap.
723
724         (2) I thought that it would be more memory-efficient to allocate
725         fine-grained pages from the large object allocator. In practice, giving
726         the large object allocator too many arbitrarily-sized ranges to manage
727         leads to fragmentation. Meanwhile, segregated fit is a powerful memory
728         optimization. So, it's best to return small object memory to the large
729         allocator only when a whole small object chunk is free.
730
731         * bmalloc/Chunk.h:
732         (bmalloc::Chunk::ref):
733         (bmalloc::Chunk::deref):
734         (bmalloc::Chunk::refCount):
735         (bmalloc::Chunk::freePages): We keep a free list per chunk and refcount
736         each chunk so we can notice when a chunk becomes empty, and return it
737         to the large allocator.
738
739         (bmalloc::forEachPage): A new helper function for iterating the pages
740         in a Chunk.
741
742         (bmalloc::Chunk::Chunk): Use forEachPage instead of manual iteration.
743         Use { } initialization because we don't get zero-initialized by the OS
744         anymore.
745
746         * bmalloc/Heap.cpp:
747         (bmalloc::Heap::Heap):
748         (bmalloc::Heap::concurrentScavenge):
749         (bmalloc::Heap::scavenge): Don't bother unlocking while scavenging. I
750         wasn't able to show it to be a consistent speedup. A more promising
751         approach, if we find a motivating example, is for the scavenger to give
752         up and return early if any other client is waiting on the lock.
753
754         (bmalloc::Heap::allocateSmallChunk): New helper function for allocating
755         a small chunk. It allocates through the large allocator to facilitate
756         sharing. We still allocate a chunk at a time instead of a page at a time.
757         Surprisingly, more precise page-at-a-time allocation is worse for memory
758         use because of fragmentation. Segregated fit is a powerful optimization.
759
760         (bmalloc::Heap::deallocateSmallChunk): New helper function for deallocating
761         a small chunk.
762
763         (bmalloc::Heap::allocateSmallPage): Updated for new APIs.
764
765         (bmalloc::Heap::deallocateSmallLine):  Updated for new APIs. Note that
766         we cache one free chunk per page class. This avoids churn in the large
767         allocator when you free(malloc(X)).
768
769         (bmalloc::Heap::allocateSmallBumpRangesByMetadata):
770         (bmalloc::Heap::allocateSmallBumpRangesByObject):
771         (bmalloc::Heap::tryAllocateLarge):
772         (bmalloc::Heap::scavengeSmallPages): Deleted.
773         (bmalloc::Heap::scavengeLargeObjects): Deleted.
774         * bmalloc/Heap.h:
775
776         * bmalloc/LargeMap.h:
777         (bmalloc::LargeMap::begin):
778         (bmalloc::LargeMap::end): Added iteration helpers for scavenging.
779
780         * bmalloc/LargeRange.h:
781         (bmalloc::LargeRange::physicalSize): Added a comment about something
782         that I confused myself about in this patch.
783
784         * bmalloc/List.h:
785         (bmalloc::List::iterator::operator*):
786         (bmalloc::List::iterator::operator->):
787         (bmalloc::List::iterator::operator!=):
788         (bmalloc::List::iterator::operator++):
789         (bmalloc::List::begin):
790         (bmalloc::List::end):
791         (bmalloc::List::pushFront):
792         (bmalloc::List::remove):
793         (bmalloc::ListNode::ListNode): Deleted. Added iteration helpers for
794         scavenging. Changed the default state of a Node to null pointers instead
795         of self pointers to distinguish the null node from the empty node for
796         easier debugging.
797
798         * bmalloc/Sizes.h: Changed the chunk size to 1MB to increase the chances
799         of a chunk becoming free and recyclable.
800
801         * bmalloc/SmallPage.h:
802         (bmalloc::SmallPage::hasPhysicalPages):
803         (bmalloc::SmallPage::setHasPhysicalPages): Track physical state by page
804         instead of implicitly by which list a page is in. It's simpler not
805         to have to move chunks and pages between physical vs virtual lists.
806
807         (bmalloc::SmallPage::SmallPage): Deleted.
808
809         * bmalloc/VMHeap.cpp:
810         (bmalloc::VMHeap::tryAllocateLargeChunk):
811         (bmalloc::VMHeap::allocateSmallChunk): Deleted.
812         * bmalloc/VMHeap.h:
813         (bmalloc::VMHeap::allocateSmallPage): Deleted.
814         (bmalloc::VMHeap::deallocateSmallPage): Deleted. Small chunk allocation
815         just forwards to the large allocator now.
816
817         * bmalloc/bmalloc.h:
818         (bmalloc::api::scavenge):
819
820 2017-05-28  Dan Bernstein  <mitz@apple.com>
821
822         [Xcode] ALWAYS_SEARCH_USER_PATHS is set to YES
823         https://bugs.webkit.org/show_bug.cgi?id=172691
824
825         Reviewed by Tim Horton.
826
827         * Configurations/Base.xcconfig: Set ALWAYS_SEARCH_USER_PATHS to NO.
828
829 2017-05-25  Geoffrey Garen  <ggaren@apple.com> and Michael Saboff  <msaboff@apple.com>
830
831         bmalloc: scavenger runs too much on JetStream
832         https://bugs.webkit.org/show_bug.cgi?id=172373
833
834         Reviewed by Geoffrey Garen.
835
836         Instruments says that JetStream on macOS spends about 3% of its time in
837         madvise.
838
839         In <https://bugs.webkit.org/show_bug.cgi?id=160098>, Ben saw some
840         evidence that madvise was the reason that switching to bmalloc for
841         DFG::Node allocations was a slowdown the first time around.
842
843         In <https://bugs.webkit.org/show_bug.cgi?id=172124>, Michael saw that
844         scavening policy can affect JetStream.
845
846         Intuitively, it seems wrong for the heap to idle shrink during hardcore
847         benchmarking.
848
849         The strategy here is to back off in response to any heap growth event,
850         and to wait 2s instead of 0.5s for heap growth to take place -- but we
851         scavenge immediately in response to critical memory pressure, to avoid
852         jetsam.
853
854         One hole in this strategy is that a workload with a perfectly
855         unfragmented heap that allocates and deallocates ~16kB every 2s will
856         never shrink its heap. This doesn't seem to be a problem in practice.
857
858         This looks like a 2% - 4% speedup on JetStream on Mac Pro and MacBook Air.
859
860         * bmalloc/AsyncTask.h:
861         (bmalloc::AsyncTask::willRun):
862         (bmalloc::AsyncTask::willRunSoon):
863         (bmalloc::Function>::AsyncTask):
864         (bmalloc::Function>::run):
865         (bmalloc::Function>::runSoon):
866         (bmalloc::Function>::threadRunLoop):
867         (bmalloc::Function>::runSlowCase): Deleted. Added a "run soon" state
868         so that execution delay is modeled directly instead of implicitly
869         through sleep events. This enables the Heap to issue a "run now" event
870         at any moment in response ot memory pressure.
871
872         * bmalloc/Heap.cpp:
873         (bmalloc::Heap::Heap): Don't call into our own API -- that's a layering
874         violation.
875
876         (bmalloc::Heap::updateMemoryInUseParameters): No need for
877         m_scavengeSleepDuration anymore.
878
879         (bmalloc::Heap::concurrentScavenge): Added a back-off policy when the
880         heap is growing.
881         (bmalloc::Heap::scavenge):
882
883         (bmalloc::Heap::scavengeSmallPages):
884         (bmalloc::Heap::scavengeLargeObjects): Don't try to give up in the middle
885         of a scavenge event. Our new backoff policy supplants that design. Also,
886         it's easier to profile and understand scavenging behavior if it always
887         runs to completion once started.
888
889         (bmalloc::Heap::scheduleScavenger):
890         (bmalloc::Heap::scheduleScavengerIfUnderMemoryPressure): Added a
891         synchronous amortized check for memory pressure. This check has the
892         benefit that it runs immediately during high rates of heap activity,
893         so we can detect memory pressure right away and wake the scavenger
894         instead of waiting for the scavenger to wake up.
895
896         (bmalloc::Heap::allocateSmallPage):
897         (bmalloc::Heap::deallocateSmallLine):
898         (bmalloc::Heap::splitAndAllocate):
899         (bmalloc::Heap::tryAllocateLarge):
900         (bmalloc::Heap::shrinkLarge):
901         (bmalloc::Heap::deallocateLarge):
902         * bmalloc/Heap.h:
903         (bmalloc::Heap::isUnderMemoryPressure):
904         * bmalloc/Sizes.h:
905         * bmalloc/VMHeap.h:
906         (bmalloc::VMHeap::deallocateSmallPage):
907         * bmalloc/bmalloc.h:
908         (bmalloc::api::scavenge): Updated for API changes above.
909
910 2017-05-17  Michael Saboff  <msaboff@apple.com>
911
912         [iOS] The Garbage Collector shouldn't rely on the bmalloc scavenger for up to date memory footprint info (172186)
913         https://bugs.webkit.org/show_bug.cgi?id=172186
914
915         Reviewed by Geoffrey Garen.
916
917         The calls memoryFootprint() and percentAvailableMemoryInUse() now make a system call to get
918         the current memory footprint value.
919
920         * bmalloc/Heap.h:
921         (bmalloc::Heap::memoryFootprint):
922         (bmalloc::Heap::percentAvailableMemoryInUse):
923
924 2017-05-16  Michael Saboff  <msaboff@apple.com>
925
926         REGRESSION(r216763): JetStream is 1% slower on Mac
927         https://bugs.webkit.org/show_bug.cgi?id=172124
928
929         Reviewed by Filip Pizlo.
930
931         It appears that changing maxScavengeSleepDuration from 512 to 250ms in r216763 is
932         responsible for the regression.
933
934         * bmalloc/Sizes.h:
935
936 2017-05-15  Geoffrey Garen  <ggaren@apple.com>
937
938         bmalloc: Bump the size of the deallocator log to 512
939         https://bugs.webkit.org/show_bug.cgi?id=172143
940
941         Reviewed by Michael Saboff.
942
943         This is a speedup on parallel workloads for machines with lots of CPUs.
944
945         * bmalloc/Sizes.h:
946
947 2017-05-12  Michael Saboff  <msaboff@apple.com>
948
949         [iOS] Use memory footprint to dynamically adjust behavior of allocators
950         https://bugs.webkit.org/show_bug.cgi?id=171944
951
952         Reviewed by Filip Pizlo.
953
954         This change is iOS only.
955
956         After the scavenger thread completes scavenging, it asks the OS for how much total memory the
957         process is using.  This information is used to update the sleep delay for the scanvenger thread,
958         as well as to provide memory in use data for other parts of the system.
959
960         The scavenger sleep time is calculated using the following quadradic equation.
961
962             scavengerSleep = 1.2*percentFreeMemory^2 - percentFreeMemory + 2
963
964         Where percentFreeMemory is between 0 and 100.  The result is constrained to the values 2 and 250.
965
966         This equation empirically works out to providing a 2ms sleep time when we have less than 10%
967         memory available, 30ms when 20% is available and 250ms when 50% or more is available.  In testing,
968         this exponentially agressive scavenging delay by itself reduced memory usage and made it much
969         more deterministic when used without the corresponding change in the JSC Heap.
970
971         Changed the scavenger thread to use the User Initiated QOS priority to ensure it doesn't
972         get starved.
973
974         Moved the non-Windows functionality of WTF::RAMSize() to new files AvailableMemory.{cpp,h}
975         and implemented in the function availableMemory().  That functions limits the value returned
976         on iOS to a maximum of 840MB as that is the jetsam soft memory limit.
977         Added a new API availableMemory() so that WTF::RAMSize() will use this value.
978
979         * CMakeLists.txt:
980         * bmalloc.xcodeproj/project.pbxproj:
981         * bmalloc/BPlatform.h:
982         * bmalloc/Heap.cpp:
983         (bmalloc::Heap::Heap):
984         (bmalloc::Heap::updateMemoryInUseParameters):
985         (bmalloc::Heap::concurrentScavenge):
986         (bmalloc::Heap::scavenge):
987         * bmalloc/Heap.h:
988         (bmalloc::Heap::memoryFootprint):
989         (bmalloc::Heap::percentAvailableMemoryInUse):
990         * bmalloc/Sizes.h:
991         * bmalloc/bmalloc.h:
992         (bmalloc::api::availableMemory):
993         (bmalloc::api::memoryFootprint):
994         (bmalloc::api::percentAvailableMemoryInUse):
995         * bmalloc/AvailableMemory.cpp: Added.
996         (bmalloc::computeAvailableMemory):
997         (bmalloc::availableMemory):
998         * bmalloc/AvailableMemory.h: Added.
999
1000 2017-05-05  Joseph Pecoraro  <pecoraro@apple.com>
1001
1002         Leaks always reports "WebKit Malloc Memory Pressure Handler" dispatch_queue/source as leaking
1003         https://bugs.webkit.org/show_bug.cgi?id=171532
1004
1005         Reviewed by Geoffrey Garen.
1006
1007         * bmalloc/Heap.cpp:
1008         (bmalloc::Heap::Heap):
1009         * bmalloc/Heap.h:
1010         Store the dispatch_source_t in a member to avoid a false positive leak.
1011
1012 2017-04-27  Michael Saboff  <msaboff@apple.com>
1013
1014         bmalloc scavenger should know what page classes are allocating
1015         https://bugs.webkit.org/show_bug.cgi?id=171384
1016
1017         Reviewed by Geoffrey Garen.
1018
1019         This change replaces m_isAllocatingPages with a per page class flag to track which page
1020         classes are currently allocating.  When scavenging, we skip page classes that are actively
1021         allocating and come back to them on a subsequent pass.  This reduces the amount of time it
1022         takes for scavenger to free up pages as well as the total time it takes to handle all
1023         page classes.
1024
1025         * bmalloc/Heap.cpp:
1026         (bmalloc::Heap::Heap):
1027         (bmalloc::Heap::concurrentScavenge):
1028         (bmalloc::Heap::scavenge):
1029         (bmalloc::Heap::scavengeSmallPages):
1030         (bmalloc::Heap::scavengeLargeObjects):
1031         (bmalloc::Heap::allocateSmallPage):
1032         (bmalloc::Heap::splitAndAllocate):
1033         (bmalloc::Heap::deallocateLarge):
1034         * bmalloc/Heap.h:
1035         (bmalloc::Heap::takeRequestedScavengerThreadQOSClass): Deleted.
1036         * bmalloc/VMHeap.h:
1037         (bmalloc::VMHeap::deallocateSmallPage):
1038         * bmalloc/bmalloc.h:
1039         (bmalloc::api::scavenge):
1040
1041 2017-04-25  Michael Saboff  <msaboff@apple.com>
1042
1043         Call bmalloc scavenger first when handling a memory pressure event
1044         https://bugs.webkit.org/show_bug.cgi?id=171289
1045
1046         Reviewed by Geoffrey Garen.
1047
1048         Registered a critical memory pressure handler.  We add this handler in addition to the
1049         call to release bmalloc memory in the WebCore releaseMemory handler for the case of
1050         JSC API users that don't use WebCore.  When both handlers are in the process, it is
1051         basically a race.  One will win, but the loser won't do any more work, so it is harmless.
1052
1053         * bmalloc/Heap.cpp:
1054         (bmalloc::Heap::Heap):
1055
1056 2017-04-14  Mark Lam  <mark.lam@apple.com>
1057
1058         Update architectures in xcconfig files.
1059         https://bugs.webkit.org/show_bug.cgi?id=170867
1060         <rdar://problem/31628104>
1061
1062         Reviewed by Joseph Pecoraro.
1063
1064         * Configurations/Base.xcconfig:
1065
1066 2017-04-12  Dan Bernstein  <mitz@apple.com>
1067
1068         [Mac] Future-proof .xcconfig files
1069         https://bugs.webkit.org/show_bug.cgi?id=170802
1070
1071         Reviewed by Tim Horton.
1072
1073         * Configurations/Base.xcconfig:
1074         * Configurations/DebugRelease.xcconfig:
1075
1076 2017-02-03  Ting-Wei Lan  <lantw44@gmail.com>
1077
1078         Include cstdlib before using ::malloc and posix_memalign
1079         https://bugs.webkit.org/show_bug.cgi?id=167800
1080
1081         Reviewed by Geoffrey Garen.
1082
1083         * bmalloc/DebugHeap.cpp:
1084
1085 2017-02-01  Andreas Kling  <akling@apple.com>
1086
1087         Implement the alwaysRunsAtBackgroundPriority WK2 setting using thread QoS.
1088         <https://webkit.org/b/167387>
1089         <rdar://problem/29711409>
1090
1091         Reviewed by Antti Koivisto.
1092
1093         Support changing the QoS level of the scavenger thread asynchronously through
1094         a request variable. This is not the most elegant thing in the world, but since
1095         threads are only allowed to change their own QoS class, our options are limited.
1096
1097         * bmalloc/Heap.cpp:
1098         (bmalloc::Heap::concurrentScavenge):
1099         * bmalloc/Heap.h:
1100         (bmalloc::Heap::takeRequestedScavengerThreadQOSClass):
1101         (bmalloc::Heap::setScavengerThreadQOSClass):
1102         * bmalloc/bmalloc.h:
1103         (bmalloc::api::setScavengerThreadQOSClass):
1104
1105 2017-01-13  Geoffrey Garen  <ggaren@apple.com>
1106
1107         bmalloc: Use a separate zone when using system malloc
1108         https://bugs.webkit.org/show_bug.cgi?id=167014
1109
1110         Reviewed by Filip Pizlo.
1111
1112         Harris asked for this so he could separate Safari and WebKit memory use
1113         when doing memory analysis.
1114
1115         This patch adds an explicit DebugHeap class that contains all our
1116         code for specialized allocation with debugging.
1117
1118         * bmalloc.xcodeproj/project.pbxproj:
1119
1120         * bmalloc/Allocator.cpp:
1121         (bmalloc::Allocator::Allocator):
1122         (bmalloc::Allocator::tryAllocate):
1123         (bmalloc::Allocator::allocateImpl):
1124         (bmalloc::Allocator::reallocate):
1125         (bmalloc::Allocator::allocateSlowCase):
1126         * bmalloc/Allocator.h: Forward to DebugHeap instead of inlining all the
1127         code. This is required for our new interface, and it is also a nice
1128         simplification that moves some not-very-important code out of the way.
1129
1130         * bmalloc/Deallocator.cpp:
1131         (bmalloc::Deallocator::Deallocator):
1132         (bmalloc::Deallocator::scavenge):
1133         (bmalloc::Deallocator::deallocateSlowCase):
1134         * bmalloc/Deallocator.h: Ditto.
1135
1136         * bmalloc/DebugHeap.cpp: Added.
1137         (bmalloc::DebugHeap::DebugHeap):
1138         (bmalloc::DebugHeap::malloc):
1139         (bmalloc::DebugHeap::memalign):
1140         (bmalloc::DebugHeap::realloc):
1141         (bmalloc::DebugHeap::free):
1142         * bmalloc/DebugHeap.h: Added. New class for overriding normal heap
1143         behavior. Right now, it just adds a malloc zone and then forwards to
1144         system malloc -- but we can add lots more kinds of debug heaps in the
1145         future if we find them useful.
1146
1147         * bmalloc/Environment.cpp:
1148         (bmalloc::Environment::Environment):
1149         (bmalloc::Environment::computeIsDebugHeapEnabled):
1150         (bmalloc::Environment::computeIsBmallocEnabled): Deleted.
1151         * bmalloc/Environment.h:
1152         (bmalloc::Environment::isDebugHeapEnabled):
1153         (bmalloc::Environment::isBmallocEnabled): Deleted. Renamed everything to
1154         reflect our new use of DebugHeap.
1155
1156         * bmalloc/Heap.cpp:
1157         (bmalloc::Heap::Heap):
1158         * bmalloc/Heap.h:
1159         (bmalloc::Heap::debugHeap): Updated to use DebugHeap.
1160         (bmalloc::Heap::environment): Deleted. 
1161
1162         * bmalloc/bmalloc.h:
1163         (bmalloc::api::isEnabled): Updated to use DebugHeap.
1164
1165 2016-12-15  Myles C. Maxfield  <mmaxfield@apple.com>
1166
1167         Sort Xcode project files
1168         https://bugs.webkit.org/show_bug.cgi?id=165937
1169
1170         Reviewed by Simon Fraser.
1171
1172         * bmalloc.xcodeproj/project.pbxproj:
1173
1174 2016-12-08  David Kilzer  <ddkilzer@apple.com>
1175
1176         Always check the return value of pthread_key_create()
1177         <https://webkit.org/b/165274>
1178
1179         Reviewed by Darin Adler.
1180
1181         * bmalloc/PerThread.h:
1182         (bmalloc::PerThreadStorage::init): Call BCRASH() if
1183         pthread_key_create() returns an error.  The error code will be
1184         stored in a register available in a crash log, so no need to log
1185         the value explicitly.
1186
1187 2016-12-06  Alexey Proskuryakov  <ap@apple.com>
1188
1189         Correct SDKROOT values in xcconfig files
1190         https://bugs.webkit.org/show_bug.cgi?id=165487
1191         rdar://problem/29539209
1192
1193         Reviewed by Dan Bernstein.
1194
1195         Fix suggested by Dan Bernstein.
1196
1197         * Configurations/DebugRelease.xcconfig:
1198
1199 2016-11-29  Andy Estes  <aestes@apple.com>
1200
1201         [Cocoa] Enable two clang warnings recommended by Xcode
1202         https://bugs.webkit.org/show_bug.cgi?id=164498
1203
1204         Reviewed by Mark Lam.
1205
1206         * Configurations/Base.xcconfig: Enabled CLANG_WARN_INFINITE_RECURSION and CLANG_WARN_SUSPICIOUS_MOVE.
1207
1208 2016-11-10  Geoffrey Garen  <ggaren@apple.com>
1209
1210         bmalloc threads should have a non-default QoS
1211         https://bugs.webkit.org/show_bug.cgi?id=164612
1212
1213         Reviewed by Filip Pizlo.
1214
1215         * bmalloc/AsyncTask.h:
1216         (bmalloc::Function>::threadEntryPoint): Request user-interactive quality
1217         of service because user-interactive tasks use malloc.
1218
1219 2016-10-20  Mark Lam  <mark.lam@apple.com>
1220
1221         bmalloc api should crash on failure to allocate when !isBmallocEnabled.
1222         https://bugs.webkit.org/show_bug.cgi?id=163766
1223
1224         Reviewed by Keith Miller and Filip Pizlo.
1225
1226         We want to crash in bmalloc on failure to allocate even when !isBmallocEnabled.
1227         This is so that failures to allocate memory will manifest as crashes with a
1228         unique signature (i.e. as a SIGTRAP on release builds, or as a write to illegal
1229         address 0xbbadbeef on debug builds) and the crash will manifest inside bmalloc.
1230         This distinguishes allocation failures from other crashing bugs that manifest as
1231         SIGSEGVs due to random pointer dereferences in the clients of bmalloc.
1232
1233         * bmalloc/Allocator.cpp:
1234         (bmalloc::Allocator::allocateImpl):
1235         (bmalloc::Allocator::reallocate):
1236         (bmalloc::Allocator::allocateSlowCase):
1237
1238 2016-09-26  Yoshiaki Jitsukawa  <Yoshiaki.Jitsukawa@sony.com>
1239
1240         Avoid implicit conversion from iterator to pointer
1241         https://bugs.webkit.org/show_bug.cgi?id=162482
1242
1243         Reviewed by Geoffrey Garen.
1244
1245         Not every STL supporting such conversion, we should get a pointer explicitly.
1246
1247         * bmalloc/Chunk.h:
1248         (bmalloc::Chunk::lines):
1249         (bmalloc::Chunk::pages):
1250         * bmalloc/FixedVector.h:
1251         (bmalloc::FixedVector::begin):
1252
1253 2016-08-31  Filip Pizlo  <fpizlo@apple.com>
1254
1255         Butterflies should be allocated in Auxiliary MarkedSpace instead of CopiedSpace and we should rewrite as much of the GC as needed to make this not a regression
1256         https://bugs.webkit.org/show_bug.cgi?id=160125
1257
1258         Reviewed by Geoffrey Garen and Keith Miller.
1259         
1260         I needed to tryMemalign, so I added such a thing.
1261
1262         * bmalloc/Allocator.cpp:
1263         (bmalloc::Allocator::allocate):
1264         (bmalloc::Allocator::tryAllocate):
1265         (bmalloc::Allocator::allocateImpl):
1266         * bmalloc/Allocator.h:
1267         * bmalloc/Cache.h:
1268         (bmalloc::Cache::tryAllocate):
1269         * bmalloc/bmalloc.h:
1270         (bmalloc::api::tryMemalign):
1271
1272 2016-08-30  Yusuke Suzuki  <utatane.tea@gmail.com>
1273
1274         Unreviewed, build fix for GCC ports
1275
1276         std::forward is declared in <utility> header.
1277
1278         * bmalloc/ScopeExit.h:
1279
1280 2016-08-30  Geoffrey Garen  <ggaren@apple.com>
1281
1282         bmalloc: speed up the lock slow path
1283         https://bugs.webkit.org/show_bug.cgi?id=161058
1284
1285         Unreviewed roll-in - with regression fixed.
1286
1287         Revert to using yield() instead of swtch() because very low priority
1288         background tasks can cause priority inversion and deadlock. In the
1289         network process, that happened with com.apple.WebKit.Cache.Storage.serialBackground.
1290
1291         Still a big speedup on MallocBench.
1292
1293         * bmalloc.xcodeproj/project.pbxproj:
1294         * bmalloc/ScopeExit.h: Added.
1295         (bmalloc::ScopeExit::ScopeExit):
1296         (bmalloc::ScopeExit::~ScopeExit):
1297         (bmalloc::makeScopeExit):
1298         * bmalloc/StaticMutex.cpp:
1299         (bmalloc::StaticMutex::lockSlowCase):
1300         * bmalloc/StaticMutex.h:
1301         (bmalloc::StaticMutex::init):
1302
1303 2016-08-26  Geoffrey Garen  <ggaren@apple.com>
1304
1305         Unreviewed build fix.
1306
1307         Fix the CMake build.
1308
1309         * CMakeLists.txt:
1310
1311 2016-08-26  Geoffrey Garen  <ggaren@apple.com>
1312
1313         Renamed XLarge* => Large*
1314         https://bugs.webkit.org/show_bug.cgi?id=161261
1315
1316         Reviewed by Andreas Kling.
1317
1318         XLarge is not a thing anymore: We just have Small and Large.
1319
1320         * bmalloc.xcodeproj/project.pbxproj:
1321         * bmalloc/Heap.cpp:
1322         (bmalloc::Heap::splitAndAllocate):
1323         (bmalloc::Heap::tryAllocateLarge):
1324         (bmalloc::Heap::shrinkLarge):
1325         (bmalloc::Heap::deallocateLarge):
1326         * bmalloc/Heap.h:
1327         * bmalloc/LargeMap.cpp: Copied from Source/bmalloc/bmalloc/XLargeMap.cpp.
1328         (bmalloc::LargeMap::remove):
1329         (bmalloc::LargeMap::add):
1330         (bmalloc::XLargeMap::remove): Deleted.
1331         (bmalloc::XLargeMap::add): Deleted.
1332         * bmalloc/LargeMap.h: Copied from Source/bmalloc/bmalloc/XLargeMap.h.
1333         (bmalloc::LargeMap::ranges):
1334         (bmalloc::XLargeMap::ranges): Deleted.
1335         * bmalloc/LargeRange.h: Copied from Source/bmalloc/bmalloc/XLargeRange.h.
1336         (bmalloc::LargeRange::LargeRange):
1337         (bmalloc::LargeRange::operator<):
1338         (bmalloc::canMerge):
1339         (bmalloc::merge):
1340         (bmalloc::LargeRange::split):
1341         (bmalloc::XLargeRange::XLargeRange): Deleted.
1342         (bmalloc::XLargeRange::operator<): Deleted.
1343         (bmalloc::XLargeRange::split): Deleted.
1344         * bmalloc/VMHeap.cpp:
1345         (bmalloc::VMHeap::tryAllocateLargeChunk):
1346         * bmalloc/VMHeap.h:
1347         * bmalloc/XLargeMap.cpp: Removed.
1348         * bmalloc/XLargeMap.h: Removed.
1349         * bmalloc/XLargeRange.h: Removed.
1350
1351 2016-08-26  Gavin Barraclough  <barraclough@apple.com>
1352
1353         bmalloc: speed up the lock slow path
1354         https://bugs.webkit.org/show_bug.cgi?id=161058
1355
1356         Unreviewed rollout - this caused regressions <rdar://problem/28026089>.
1357
1358         * bmalloc.xcodeproj/project.pbxproj:
1359         * bmalloc/ScopeExit.h: Removed.
1360         * bmalloc/StaticMutex.cpp:
1361         (bmalloc::StaticMutex::lockSlowCase):
1362         * bmalloc/StaticMutex.h:
1363         (bmalloc::StaticMutex::init):
1364         * bmalloc/ThreadSwitch.h: Removed.
1365
1366 2016-08-24  Andreas Kling  <akling@apple.com>
1367
1368         Add bmalloc::api::isEnabled().
1369         <https://webkit.org/b/160534>
1370
1371         Reviewed by Joseph Pecoraro.
1372
1373         * bmalloc/bmalloc.h:
1374         (bmalloc::api::isEnabled):
1375
1376 2016-08-24  Filip Pizlo  <fpizlo@apple.com>
1377
1378         Unreviewed, roll out r204901, r204897, r204866, r204856, r204854.
1379
1380         * bmalloc/Allocator.cpp:
1381         (bmalloc::Allocator::allocate):
1382         (bmalloc::Allocator::tryAllocate): Deleted.
1383         (bmalloc::Allocator::allocateImpl): Deleted.
1384         * bmalloc/Allocator.h:
1385         * bmalloc/Cache.h:
1386         (bmalloc::Cache::tryAllocate): Deleted.
1387         * bmalloc/bmalloc.h:
1388         (bmalloc::api::tryMemalign): Deleted.
1389
1390 2016-08-12  Filip Pizlo  <fpizlo@apple.com>
1391
1392         Butterflies should be allocated in Auxiliary MarkedSpace instead of CopiedSpace and we should rewrite as much of the GC as needed to make this not a regression
1393         https://bugs.webkit.org/show_bug.cgi?id=160125
1394
1395         Reviewed by Geoffrey Garen.
1396         
1397         I needed to tryMemalign, so I added such a thing.
1398
1399         * bmalloc/Allocator.cpp:
1400         (bmalloc::Allocator::allocate):
1401         (bmalloc::Allocator::tryAllocate):
1402         (bmalloc::Allocator::allocateImpl):
1403         (bmalloc::Allocator::reallocate):
1404         * bmalloc/Allocator.h:
1405         * bmalloc/Cache.h:
1406         (bmalloc::Cache::allocate):
1407         (bmalloc::Cache::tryAllocate):
1408         * bmalloc/bmalloc.h:
1409         (bmalloc::api::malloc):
1410         (bmalloc::api::tryMemalign):
1411         (bmalloc::api::memalign):
1412
1413 2016-08-22  Yusuke Suzuki  <utatane.tea@gmail.com>
1414
1415         Unreviewed, build fix on GCC environment
1416         https://bugs.webkit.org/show_bug.cgi?id=161058
1417
1418         std::forward is declared in <utility> header.
1419
1420         * bmalloc/ScopeExit.h:
1421
1422 2016-08-22  Geoffrey Garen  <ggaren@apple.com>
1423
1424         bmalloc: speed up the lock slow path
1425         https://bugs.webkit.org/show_bug.cgi?id=161058
1426
1427         Reviewed by Filip Pizlo.
1428
1429         It is generally accepted practice that a lock should yield instead of
1430         spinning when a lock acquisition fails, to avoid wasting CPU and power.
1431
1432         There are two problems with this generally accepted practice:
1433
1434         (1) It's a fallacy that yielding is free. In reality, yielding itself
1435         consumes CPU and power -- by performing a syscall, running the OS
1436         scheduler, and possibly performing a context switch. (Instruments
1437         traces of MallocBench show the cost of yielding.) Therefore, spinning a
1438         little to avoid yielding can actually *save* CPU and power.
1439
1440         (2) std::this_thread_yield() on Darwin is way too aggressive: It not only
1441         yields but also depresses your priority to absolute zero for 10ms. A
1442         recent PLT trace showed a few spots where the main thread just gave up
1443         on loading and rendering a page for 10ms so an unimportant background
1444         task could run.
1445
1446         To correct these problems, this patch adds a little bit of spinning to
1447         the bmalloc lock slow path.
1448
1449         Below are performance results on various CPUs.
1450
1451         Mac Pro (12 hyperthreaded cores = 24 threads):
1452
1453                                                             Baseline                       Patch                           Δ
1454             Execution Time:
1455                 message_one                                    173ms                       173ms                            
1456                 message_many                                   953ms                       927ms              ^ 1.03x faster
1457                 churn --parallel                                60ms                        41ms              ^ 1.46x faster
1458                 list_allocate --parallel                       224ms                       143ms              ^ 1.57x faster
1459                 tree_allocate --parallel                     1,190ms                       758ms              ^ 1.57x faster
1460                 tree_churn --parallel                        1,517ms                       906ms              ^ 1.67x faster
1461                 facebook --parallel                          6,519ms                     4,580ms              ^ 1.42x faster
1462                 reddit --parallel                            5,097ms                     3,411ms              ^ 1.49x faster
1463                 flickr --parallel                            4,903ms                     3,501ms               ^ 1.4x faster
1464                 theverge --parallel                          6,641ms                     4,505ms              ^ 1.47x faster
1465
1466                 <geometric mean>                             1,158ms                       832ms              ^ 1.39x faster
1467                 <arithmetic mean>                            2,728ms                     1,895ms              ^ 1.44x faster
1468                 <harmonic mean>                                332ms                       240ms              ^ 1.38x faster
1469
1470         MacBook Air (2 hyperthreaded cores = 4 threads):
1471
1472                                                             Baseline                       Patch                           Δ
1473             Execution Time:
1474                 message_one                                    911ms                       907ms               ^ 1.0x faster
1475                 message_many                                   515ms                       513ms               ^ 1.0x faster
1476                 churn --parallel                               132ms                       134ms              ! 1.02x slower
1477                 list_allocate --parallel                       104ms                       102ms              ^ 1.02x faster
1478                 tree_allocate --parallel                       117ms                       111ms              ^ 1.05x faster
1479                 tree_churn --parallel                          154ms                       151ms              ^ 1.02x faster
1480                 facebook --parallel                            719ms                       687ms              ^ 1.05x faster
1481                 reddit --parallel                              382ms                       341ms              ^ 1.12x faster
1482                 flickr --parallel                              372ms                       345ms              ^ 1.08x faster
1483                 theverge --parallel                            489ms                       444ms               ^ 1.1x faster
1484
1485                 <geometric mean>                               299ms                       287ms              ^ 1.04x faster
1486                 <arithmetic mean>                              390ms                       374ms              ^ 1.04x faster
1487                 <harmonic mean>                                227ms                       220ms              ^ 1.03x faster
1488
1489         iPad (2 cores = 2 threads):
1490
1491             [ Doesn't run Ruby, so no pretty subtest output. ]
1492
1493                                                             Baseline                       Patch                           Δ
1494             Execution Time:                                 174.14ms                     171.5ms              ^ 1.02x faster
1495
1496         * bmalloc.xcodeproj/project.pbxproj:
1497
1498         * bmalloc/ScopeExit.h: Added. A barebones very wimpy version of
1499         WTF::ScopeExit.
1500         (bmalloc::ScopeExit::ScopeExit):
1501         (bmalloc::ScopeExit::~ScopeExit):
1502         (bmalloc::makeScopeExit):
1503
1504         * bmalloc/StaticMutex.cpp:
1505         (bmalloc::StaticMutex::lockSlowCase): Spin before yielding -- that's the
1506         speedup. Don't spin if another CPU is already spinning. In theory, more
1507         than one spinner accomplishes nothing, and I found that there's a cutoff
1508         around 8 or 16 spinners that becomes performance negative on Mac Pro.
1509
1510         (Note: Another way to accomplish a similar result, if you don't want to
1511         use a bit of state in the lock, is to spin for a random duration between
1512         0 and aLot. I tested a version of WTF::WeakRandom with unsynchronized
1513         static state and it worked great. But I ultimately opted for the explicit
1514         bit because I thought it was clearer.)
1515
1516         * bmalloc/StaticMutex.h:
1517         (bmalloc::StaticMutex::init): Initialize our new bit.
1518
1519         * bmalloc/ThreadSwitch.h: Added.
1520         (bmalloc::threadSwitch): Don't call yield() on Darwin because it's too
1521         aggressive. swtch() does what we want: Go run something else, without
1522         any other side-effects.
1523
1524 2016-08-03  Geoffrey Garen  <ggaren@apple.com>
1525
1526         [bmalloc] Merging of XLargeRanges can leak the upper range
1527         https://bugs.webkit.org/show_bug.cgi?id=160403
1528
1529         Reviewed by Michael Saboff.
1530
1531         * bmalloc/Heap.cpp:
1532         (bmalloc::Heap::scavengeLargeObjects): Don't use removePhysical().
1533         Recorded physical size is a performance optimization. It is not the
1534         truth. So it might be zero even if a range contains physical pages.
1535
1536         Instead, iterate each range in the map unconditionally.
1537
1538         The map can shrink when we release the lock, so we must clamp our
1539         iterator each time through the loop.
1540
1541         The map can grow when we release the lock, but we don't care because
1542         growth restarts the scavenger from the beginning.
1543
1544         * bmalloc/XLargeMap.cpp:
1545         (bmalloc::XLargeMap::removePhysical): Deleted. Not used anymore.
1546
1547         * bmalloc/XLargeMap.h:
1548         (bmalloc::XLargeMap::ranges): Added direct access for the sake of
1549         scavengeLargeObjects. (This violates our naming conventions -- I'll do
1550         a rename in a follow-up patch.)
1551
1552 2016-07-13  Enrica Casucci  <enrica@apple.com>
1553
1554         Update supported platforms in xcconfig files to match the sdk names.
1555         https://bugs.webkit.org/show_bug.cgi?id=159728
1556
1557         Reviewed by Tim Horton.
1558
1559         * Configurations/Base.xcconfig:
1560
1561 2016-07-11  Geoffrey Garen  <ggaren@apple.com>
1562
1563         Crash due to abort() calling libc++.1.dylib: std::__1::thread::detach()
1564         https://bugs.webkit.org/show_bug.cgi?id=159655
1565
1566         Reviewed by Sam Weinig.
1567
1568         It's not entirely clear what was happening in these crashes, but our
1569         use of detach() was 100% forward-looking, so we can just remove it for
1570         now.
1571
1572         This patch removes the ability for the scavenger owner to die before
1573         the scavenger thread dies (which was unused) and also removes the
1574         ability for the scavenger thread to exit (which was used, but we
1575         messed up and did thread joining lazily, so we never got any benefit
1576         from thread exit.)
1577
1578         We can add these features back when we need them, and make them work then.
1579
1580         * bmalloc/AsyncTask.h:
1581         (bmalloc::Function>::AsyncTask): We start out in the running state now
1582         because we know that starting our thread will run it.
1583
1584         (bmalloc::Function>::~AsyncTask): We don't support destruction anymore.
1585
1586         (bmalloc::Function>::runSlowCase): I removed the Exited state.
1587
1588         (bmalloc::Function>::threadRunLoop): I removed the Exited and
1589         ExitRequested states.
1590
1591         * bmalloc/Heap.h:
1592
1593         * bmalloc/VMHeap.h:
1594
1595 2016-06-12  David Kilzer  <ddkilzer@apple.com>
1596
1597         Crash in com.apple.WebKit.WebContent at std::__1::__call_once_proxy<std::__1::tuple<CrashReporterSupportLibrary()::$_0&&> >
1598         <https://webkit.org/b/158660>
1599         <rdar://problem/25652686>
1600
1601         Reviewed by Darin Adler.
1602
1603         * bmalloc/Logging.cpp: Switch to use
1604         BSOFT_LINK_PRIVATE_FRAMEWORK() to link
1605         CrashReporterSupport.framework.
1606         * bmalloc/darwin/BSoftLinking.h:
1607         (BSOFT_LINK_PRIVATE_FRAMEWORK): Rename from BSOFT_LINK_FRAMEWORK.
1608         Switch to use /System/Library/PrivateFrameworks/.
1609
1610 2016-06-11  David Kilzer  <ddkilzer@apple.com>
1611
1612         Implement logging for RELEASE_BASSERT_WITH_MESSAGE() in BAssert.h
1613         <http://webkit.org/b/155992>
1614
1615         Reviewed by Geoff Garen.
1616
1617         * bmalloc/BAssert.h:
1618         (BLOG_ERROR): Add method to always log error messages.
1619         (RELEASE_BASSERT_WITH_MESSAGE): Use BLOG_ERROR() to implement
1620         logging in Debug builds.
1621         * bmalloc/BPlatform.h:
1622         (BPLATFORM_MAC): Add.
1623         (BUSE): Add BUSE() macro.
1624         (BATTRIBUTE_PRINTF): Add.
1625         (BUSE_OS_LOG): Add.
1626         * bmalloc/Logging.cpp:
1627         (bmalloc::reportAssertionFailureWithMessage): Add.  Logs to
1628         stderr.
1629         * bmalloc/Logging.h:
1630         (bmalloc::reportAssertionFailureWithMessage): Add declaration.
1631
1632 2016-06-07  Pranjal Jumde  <pjumde@apple.com>
1633
1634         Prevents integer overflow in Vector.h
1635         https://bugs.webkit.org/show_bug.cgi?id=158455
1636         <rdar://problem/20235469>
1637
1638         Reviewed by Mark Lam.
1639
1640         * bmalloc/Vector.h:
1641         (bmalloc::Vector<T>::reallocateBuffer):
1642
1643 2016-05-27  Konstantin Tokarev  <annulen@yandex.ru>
1644
1645         [cmake] Deduplicated bmalloc/Zone.cpp handling.
1646         https://bugs.webkit.org/show_bug.cgi?id=158154
1647
1648         Reviewed by Alex Christensen.
1649
1650         File bmalloc/Zone.cpp is required on Darwin irrespectively from what
1651         port is being built.
1652
1653         Also I removed WEBKIT_INCLUDE_CONFIG_FILES_IF_EXISTS() because it's
1654         unlikely that bmalloc will ever need port-specific customizations (as
1655         opposed to OS-specific customizations which should be done in
1656         CMakeLists.txt).
1657
1658         * CMakeLists.txt: Added bmalloc/Zone.cpp for Darwin.
1659         * PlatformGTK.cmake: Removed.
1660         * PlatformMac.cmake: Removed.
1661
1662 2016-05-22  Brady Eidson  <beidson@apple.com>
1663
1664         Move to C++14.
1665         https://bugs.webkit.org/show_bug.cgi?id=157948
1666
1667         Reviewed by Michael Catanzaro.
1668
1669         * Configurations/Base.xcconfig:
1670
1671 2016-05-17  Geoffrey Garen  <ggaren@apple.com>
1672
1673         REGRESSION: JetStream crashes on some iPhones
1674         https://bugs.webkit.org/show_bug.cgi?id=157814
1675
1676         Reviewed by Michael Saboff.
1677
1678         * bmalloc/Sizes.h: Reduce smallMax to 32kB. 
1679
1680         Previous justification for 64kB was:
1681
1682             * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty
1683             reasonable, since sizes between 16kB and 32kB share page sizes. I went
1684             all the way up to 64kB because the GC uses 64kB blocks, and also just
1685             for extra padding to ensure that large allocations are indeed rare.
1686
1687         It turns out that the bump to 64kB substantially increases our memory
1688         high water mark on JetStream, leading to jetsam crashes. Also, there
1689         doesn't seem to be a practical performance problem to putting objects in
1690         the (32kB - 64kB) range in the large allocator.
1691
1692 2016-05-16  Geoffrey Garen  <ggaren@apple.com>
1693
1694         REGRESSION (200035): changes in "WebKit Malloc" VM regions are causing 'leaks' to spew "Failed to map remote region" messages
1695         https://bugs.webkit.org/show_bug.cgi?id=157764
1696
1697         Reviewed by Gavin Barraclough.
1698
1699         We need to allow for guard pages and only report unguarded pages to the
1700         leaks tool -- otherwise, it will try to remote map our guarded pages,
1701         and crash.
1702
1703         * bmalloc/VMHeap.cpp:
1704         (bmalloc::VMHeap::tryAllocateLargeChunk):
1705         (bmalloc::VMHeap::allocateSmallChunk): Adopt the new API for reporting
1706         a range instead of a Chunk*, and report the unguarded range.
1707
1708         This also fixes a separate bug -- very large allocations would not
1709         fully participate in pointer scanning because they would only report 2MB
1710         (chunkSize) in size. This could cause false-positive leak reports.
1711
1712         * bmalloc/Zone.cpp:
1713         (bmalloc::enumerator): Updated to scan ranges instead of fixed-sized
1714         Chunk pointers.
1715
1716         * bmalloc/Zone.h:
1717         (bmalloc::Zone::ranges):
1718         (bmalloc::Zone::addRange): Store ranges instead of fixed-sized Chunk 
1719         pointers because our VM ranges have variable sizes -- both due to guard
1720         pages and due to large allocations.
1721
1722         (bmalloc::Zone::chunks): Deleted.
1723         (bmalloc::Zone::addChunk): Deleted.
1724
1725 2016-05-10  David Kilzer  <ddkilzer@apple.com>
1726
1727         bmalloc should automatically disable itself when ThreadSanitizer is used
1728         <https://webkit.org/b/157527>
1729
1730         Reviewed by Michael Catanzaro.
1731
1732         * bmalloc/Environment.cpp:
1733         (bmalloc::isASanEnabled): Rename to isSanitizerEnabled.
1734         (bmalloc::isSanitizerEnabled): Rename from isASanEnabled. Add
1735         support for detecting ThreadSanitizer.
1736         (bmalloc::Environment::computeIsBmallocEnabled): Switch from
1737         isASanEnabled to isSanitizerEnabled.
1738
1739 2016-05-03  Geoffrey Garen  <ggaren@apple.com>
1740
1741         Assertion failure in bmalloc::vmRevokePermissions(void*, unsigned long).
1742         https://bugs.webkit.org/show_bug.cgi?id=157047
1743
1744         Reviewed by Filip Pizlo.
1745
1746         Renamed roundUpToMultipleOfSloppy => roundUpToMultipleOfNonPowerOfTwo.
1747
1748         * bmalloc/Algorithm.h:
1749         (bmalloc::roundUpToMultipleOfNonPowerOfTwo):
1750         (bmalloc::roundUpToMultipleOfSloppy): Deleted.
1751         * bmalloc/VMHeap.cpp:
1752         (bmalloc::VMHeap::allocateSmallChunk):
1753
1754 2016-05-03  Geoffrey Garen  <ggaren@apple.com>
1755
1756         Assertion failure in bmalloc::vmRevokePermissions(void*, unsigned long).
1757         https://bugs.webkit.org/show_bug.cgi?id=157047
1758
1759         Reviewed by Filip Pizlo.
1760
1761         The previous fix aligned the guard page sizes correctly but forgot to
1762         align the guard page start address correctly.
1763
1764         * bmalloc/Algorithm.h:
1765         (bmalloc::roundUpToMultipleOfSloppy): Use a new helper method to round
1766         up when not working with a power of two, instead of writing out the
1767         math by hand.
1768
1769         * bmalloc/VMHeap.cpp:
1770         (bmalloc::VMHeap::allocateSmallChunk): Make sure to round up the guard
1771         page start address in addition to its size. Assert at the very end to
1772         try to catch more bugs.
1773
1774 2016-04-27  Geoffrey Garen  <ggaren@apple.com>
1775
1776         Assertion failure in bmalloc::vmRevokePermissions(void*, unsigned long).
1777         https://bugs.webkit.org/show_bug.cgi?id=157047
1778
1779         Reviewed by Darin Adler.
1780
1781         * bmalloc/Chunk.h:
1782         (bmalloc::Chunk::Chunk):
1783         (bmalloc::Chunk::get):
1784         (bmalloc::Chunk::offset):
1785         (bmalloc::Chunk::address):
1786         (bmalloc::Object::Object):
1787         (bmalloc::Object::address):
1788         (bmalloc::Object::line):
1789         (bmalloc::Chunk::object): Deleted.
1790         (bmalloc::Object::begin): Deleted.
1791         * bmalloc/Heap.cpp:
1792         (bmalloc::Heap::allocateSmallBumpRangesByObject):
1793         * bmalloc/Object.h:
1794         (bmalloc::Object::chunk):
1795         (bmalloc::Object::offset): Renamed begin() to address() because this is
1796         not an iterator.
1797
1798         * bmalloc/VMHeap.cpp:
1799         (bmalloc::VMHeap::allocateSmallChunk): Round up pageSize to a vmPageSize
1800         multiple because pageSize might be smaller than vmPageSize, but we
1801         think the VM system requires vmPageSize-aligned values.
1802
1803 2016-04-25  Geoffrey Garen  <ggaren@apple.com>
1804
1805         bmalloc: vm allocations should plant guard pages
1806         https://bugs.webkit.org/show_bug.cgi?id=156937
1807
1808         Rolling back in r199936 with a fix for the memory regression.
1809
1810 2016-04-23  Gavin Barraclough  <barraclough@apple.com>
1811
1812         bmalloc: vm allocations should plant guard pages
1813         https://bugs.webkit.org/show_bug.cgi?id=156937
1814
1815         Rolling out - looks like this is memory regression.
1816
1817         * bmalloc/Object.h:
1818         (bmalloc::Object::operator+):
1819         (bmalloc::Object::operator<=):
1820         (bmalloc::Object::operator-): Deleted.
1821         * bmalloc/VMAllocate.h:
1822         (bmalloc::vmDeallocate):
1823         (bmalloc::vmRevokePermissions): Deleted.
1824         * bmalloc/VMHeap.cpp:
1825         (bmalloc::VMHeap::allocateSmallChunk):
1826
1827 2016-04-22  Geoffrey Garen  <ggaren@apple.com>
1828
1829         bmalloc: vm allocations should plant guard pages
1830         https://bugs.webkit.org/show_bug.cgi?id=156937
1831
1832         Reviewed by Michael Saboff.
1833
1834         * bmalloc/Object.h:
1835         (bmalloc::Object::operator-): Added a - helper.
1836
1837         * bmalloc/VMAllocate.h:
1838         (bmalloc::vmRevokePermissions): Added a helper to revoke permissions on
1839         a VM region. We use this for guard pages.
1840
1841         * bmalloc/VMHeap.cpp:
1842         (bmalloc::VMHeap::allocateSmallChunk): Add guard pages to the start and
1843         end of the chunk.
1844
1845         Note that we don't guard large chunks becuase we need to be able to merge
1846         them. Otherwise, we will run out of virtual addresses.
1847
1848 2016-04-22  Geoffrey Garen  <ggaren@apple.com>
1849
1850         bmalloc: Constify introspect function pointer table
1851         https://bugs.webkit.org/show_bug.cgi?id=156936
1852
1853         Reviewed by Michael Saboff.
1854
1855         * bmalloc/Zone.cpp:
1856         (bmalloc::Zone::Zone): Declaring this function pointer table const puts
1857         it in the read-only section of the binary, providing a little hardening
1858         against overwriting the function pointers at runtime. (We have to
1859         const_cast when assigning because the API declares a pointer to non-const,
1860         but we happen to know it will never try to write through that pointer.
1861         This is not my favorite API.)
1862
1863 2016-04-19  Geoffrey Garen  <ggaren@apple.com>
1864
1865         bmalloc: fix up overflow checks
1866         https://bugs.webkit.org/show_bug.cgi?id=156780
1867
1868         Reviewed by Mark Lam.
1869
1870         We used to try to avoid overflow in large object math by setting a very
1871         high limit on the largest large object. But that's a bit error-prone
1872         since the check is far away from the math that might overflow -- and
1873         we were missing some cases.
1874
1875         This patch removes the limit and instead checks at each math site.
1876
1877         * bmalloc/Allocator.cpp:
1878         (bmalloc::Allocator::tryAllocate):
1879         (bmalloc::Allocator::allocate):
1880         (bmalloc::Allocator::reallocate):
1881         (bmalloc::Allocator::allocateSlowCase): Remove the limit. tryAllocateLarge
1882         will check for overflow for us.
1883
1884         * bmalloc/Chunk.h: This ASSERT was just totally wrong.
1885
1886         * bmalloc/Heap.cpp:
1887         (bmalloc::Heap::tryAllocateLarge): Check for overflow when adding.
1888
1889         * bmalloc/Sizes.h:
1890
1891         * bmalloc/VMAllocate.h:
1892         (bmalloc::tryVMAllocate): Check for overflow when adding.
1893
1894         * bmalloc/VMHeap.cpp:
1895         (bmalloc::VMHeap::tryAllocateLargeChunk): Check for overflow when adding.
1896
1897 2016-04-19  Geoffrey Garen  <ggaren@apple.com>
1898
1899         Unreviewed, try to fix an ASSERT seen on the bots.
1900
1901         * bmalloc/Heap.cpp:
1902         (bmalloc::Heap::tryAllocateLarge): This ASSERT is supposed to be about
1903         alignment, not size. Oops.
1904
1905 2016-04-19  Geoffrey Garen  <ggaren@apple.com>
1906
1907         bmalloc: Merge the large and xlarge allocators
1908         https://bugs.webkit.org/show_bug.cgi?id=156734
1909
1910         Reviewed by Andreas Kling.
1911
1912         This give us better defense against worst case memory usage:
1913
1914                                               Baseline                Patch                    Δ
1915             Peak Memory:
1916                 nimlang                      198,132kB            181,468kB      ^ 1.09x smaller
1917
1918         It also eliminates inline metadata for large objects, fixing the
1919         regression introduced in r198675, and more:
1920
1921             run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
1922
1923                                                                   Baseline                          Patch                              Δ
1924             Memory at End:
1925                 big                                               10,880kB                        3,328kB                ^ 3.27x smaller
1926                 facebook                                           3,112kB                        2,868kB                ^ 1.09x smaller
1927                 fragment --parallel                                1,848kB                          760kB                ^ 2.43x smaller
1928                 fragment_iterate --parallel                        4,908kB                          776kB                ^ 6.32x smaller
1929                 big --parallel                                    48,076kB                       11,892kB                ^ 4.04x smaller
1930
1931         Overall memory use looks OK:
1932
1933             run-malloc-benchmarks --memory_warning Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
1934
1935                                                         Baseline                               Patch                                   Δ
1936             Memory at End:
1937                 <arithmetic mean>                       13,992kB                            13,987kB                      ^ 1.0x smaller
1938
1939         Overall throughput looks OK:
1940
1941             run-malloc-benchmarks Baseline:~/OpenSource/WebKitBuildBaseline/Release/ Patch:~/OpenSource/WebKitBuild/Release/
1942
1943                                                                   Baseline                          Patch                              Δ
1944             Execution Time:
1945                 <arithmetic mean>                                    103ms                          104ms                 ! 1.01x slower
1946
1947         We're a bit slower on the "all-out large allocations on all cores"
1948         benchmark, but I think that's an OK price to pay:
1949
1950                                                                   Baseline                          Patch                              Δ
1951             Execution Time:
1952                 big --parallel                                       125ms                          136ms                 ! 1.09x slower
1953
1954         This patch net removes 1.5k lines of code. It turns out that large
1955         allocations are rare, and free memory fragments are also rare, so the
1956         combination is super rare, and a simple O(n) algorithm that ensures good
1957         memory behavior is the best option.
1958
1959         Fun fact: In practice, the odds that the old code would save memory
1960         were *worse* than the odds that it would contain a bug that wasted
1961         memory. :)
1962
1963         * bmalloc.xcodeproj/project.pbxproj:
1964
1965         * bmalloc/Allocator.cpp:
1966         (bmalloc::Allocator::tryAllocate): largeMax is the new xLargeMax since
1967         xLargeMax is gone now.
1968
1969         (bmalloc::Allocator::allocate): I moved the rounding code into allocateLarge,
1970         so we don't have to do it here.
1971
1972         (bmalloc::Allocator::reallocate):
1973         (bmalloc::Allocator::allocateSlowCase):
1974         (bmalloc::Allocator::allocateXLarge): Deleted. No more XLarge case.
1975
1976         * bmalloc/Allocator.h:
1977
1978         * bmalloc/BeginTag.h: Removed.
1979         * bmalloc/BoundaryTag.h: Removed.
1980
1981         * bmalloc/Chunk.h:
1982         (bmalloc::ChunkHash::hash): Added a hash function. The best hash function
1983         is a unique and monotonically increasing integer, and that's exactly what
1984         we typically get from the high bits of a Chunk, since the OS allocates
1985         Chunks at unique and increasing addresses.
1986         (bmalloc::Chunk::boundaryTags): Deleted.
1987         (bmalloc::Chunk::objectType): Deleted.
1988         (bmalloc::Chunk::beginTag): Deleted.
1989         (bmalloc::Chunk::endTag): Deleted.
1990
1991         * bmalloc/Deallocator.cpp:
1992         (bmalloc::Deallocator::deallocateSlowCase): We no longer know for sure,
1993         by looking at its bit pattern, whether a pointer is small or large.
1994         Instead, any pointer with large alignment *might* be large, and when
1995         we occasionally encounter such an object, we have to consult a hash
1996         table in the Heap to find out for sure. This turns out to be just as
1997         cheap in practice.
1998
1999         We don't deallocate large objects on the fast path anymore. We can't,
2000         because large objects have out-of-line metadata now.
2001
2002         (bmalloc::Deallocator::deallocateXLarge): Deleted.
2003
2004         * bmalloc/Deallocator.h:
2005         (bmalloc::Deallocator::deallocateFastCase): See deallocateSlowCase.
2006
2007         * bmalloc/EndTag.h: Removed.
2008         * bmalloc/FreeList.cpp: Removed.
2009         * bmalloc/FreeList.h: Removed.
2010
2011         * bmalloc/Heap.cpp:
2012         (bmalloc::Heap::allocateSmallPage): Be sure to track each chunk in
2013         the object type map, so we can distinguish small vs large objects.
2014
2015         (bmalloc::Heap::deallocateSmallLine): No need to check object type
2016         because we know object type now by virtue of being on the small object
2017         path.
2018
2019         (bmalloc::Heap::splitAndAllocate): Be sure to track each chunk in
2020         the object type map, so we can distinguish small vs large objects. Large
2021         objects can split across chunks, so we need to add each large object's
2022         chunk as it is allocated.
2023
2024         (bmalloc::Heap::tryAllocateLarge):
2025         (bmalloc::Heap::allocateLarge):
2026         (bmalloc::Heap::isLarge):
2027         (bmalloc::Heap::largeSize):
2028         (bmalloc::Heap::shrinkLarge):
2029         (bmalloc::Heap::deallocateLarge): Merged in existing XLarge logic for
2030         large objects.
2031
2032         (bmalloc::Heap::scavengeXLargeObjects): Deleted.
2033         (bmalloc::Heap::allocateXLarge): Deleted.
2034         (bmalloc::Heap::tryAllocateXLarge): Deleted.
2035         (bmalloc::Heap::xLargeSize): Deleted.
2036         (bmalloc::Heap::shrinkXLarge): Deleted.
2037         (bmalloc::Heap::deallocateXLarge): Deleted.
2038
2039         * bmalloc/Heap.h:
2040         (bmalloc::Heap::LargeObjectHash::hash):
2041
2042         * bmalloc/LargeObject.h: Removed.
2043
2044         * bmalloc/Map.h: Added.
2045         (bmalloc::Map::size):
2046         (bmalloc::Map::capacity):
2047         (bmalloc::Map::get):
2048         (bmalloc::Map::set):
2049         (bmalloc::Map::remove):
2050         (bmalloc::Map::shouldGrow):
2051         (bmalloc::Map::shouldShrink):
2052         (bmalloc::Map::find):
2053         (bmalloc::Hash>::rehash): Simple hash table.
2054
2055         * bmalloc/Object.h:
2056
2057         * bmalloc/ObjectType.cpp:
2058         (bmalloc::objectType):
2059         * bmalloc/ObjectType.h:
2060         (bmalloc::mightBeLarge): See deallocateSlowCase.
2061         (bmalloc::isXLarge): Deleted.
2062
2063         * bmalloc/SegregatedFreeList.cpp: Removed.
2064         * bmalloc/SegregatedFreeList.h: Removed.
2065
2066         * bmalloc/Sizes.h: Upped smallMax to 64kB. Upping to 32kB is pretty
2067         reasonable, since sizes between 16kB and 32kB share page sizes. I went
2068         all the way up to 64kB because the GC uses 64kB blocks, and also just
2069         for extra padding to ensure that large allocations are indeed rare.
2070
2071         * bmalloc/SortedVector.h: Removed.
2072
2073         * bmalloc/VMHeap.cpp:
2074         (bmalloc::VMHeap::tryAllocateLargeChunk):
2075         (bmalloc::VMHeap::allocateSmallChunk):
2076         (bmalloc::VMHeap::VMHeap): Deleted.
2077         (bmalloc::VMHeap::allocateChunk): Deleted.
2078         * bmalloc/VMHeap.h:
2079         (bmalloc::VMHeap::deallocateSmallPage):
2080         (bmalloc::VMHeap::allocateLargeObject): Deleted.
2081         (bmalloc::VMHeap::deallocateLargeObject): Deleted. Nixed all the boundary
2082         tag logic since metadata is out of line now.
2083
2084         * bmalloc/VMState.h: Removed. Instead of an abstract state, we track
2085         the precise amount of committed physical pages at the head of a VM
2086         range. This allows us to merge aggressively without triggering an madvise
2087         storm most of the time.
2088
2089         * bmalloc/Vector.h:
2090         (bmalloc::Vector<T>::Vector):
2091         (bmalloc::Vector<T>::insert):
2092         (bmalloc::Vector<T>::remove):
2093         (bmalloc::Vector<T>::resize): Filled out some missing helpers.
2094
2095         * bmalloc/XLargeMap.cpp:
2096         (bmalloc::XLargeMap::remove):
2097         (bmalloc::XLargeMap::add):
2098         (bmalloc::XLargeMap::removePhysical):
2099         (bmalloc::XLargeMap::takeFree): Deleted.
2100         (bmalloc::XLargeMap::addFree): Deleted.
2101         (bmalloc::XLargeMap::addAllocated): Deleted.
2102         (bmalloc::XLargeMap::getAllocated): Deleted.
2103         (bmalloc::XLargeMap::takeAllocated): Deleted.
2104         (bmalloc::XLargeMap::shrinkToFit): Deleted.
2105         (bmalloc::XLargeMap::takePhysical): Deleted.
2106         (bmalloc::XLargeMap::addVirtual): Deleted.
2107         * bmalloc/XLargeMap.h:
2108         (bmalloc::XLargeMap::Allocation::operator<): Deleted. We don't track
2109         object sizes anymore -- just free space. (The Heap tracks object sizes.)
2110         We use plain old linear search for free space. (See intro.)
2111
2112         * bmalloc/XLargeRange.h:
2113         (bmalloc::XLargeRange::physicalSize):
2114         (bmalloc::XLargeRange::setPhysicalSize):
2115         (bmalloc::merge):
2116         (bmalloc::XLargeRange::split):
2117         (bmalloc::XLargeRange::vmState): Deleted.
2118         (bmalloc::XLargeRange::setVMState): Deleted. See VMState.h.
2119
2120 2016-04-11  Fujii Hironori  <Hironori.Fujii@jp.sony.com>
2121
2122         [CMake] Make FOLDER property INHERITED
2123         https://bugs.webkit.org/show_bug.cgi?id=156460
2124
2125         Reviewed by Brent Fulgham.
2126
2127         * CMakeLists.txt:
2128         Set FOLDER property as a directory property not a target property
2129
2130 2016-04-08  Geoffrey Garen  <ggaren@apple.com>
2131
2132         bmalloc: stress_aligned test fails if you increase smallMax
2133         https://bugs.webkit.org/show_bug.cgi?id=156414
2134
2135         Reviewed by Oliver Hunt.
2136
2137         When size exceeds alignment and is a multiple of alignment and is not
2138         a power of two, such as 24kB with 8kB alignment, the small allocator
2139         did not always guarantee alignment. Let's fix that.
2140
2141         * bmalloc/Algorithm.h:
2142         (bmalloc::divideRoundingUp): Math is hard.
2143
2144         * bmalloc/Allocator.cpp:
2145         (bmalloc::Allocator::allocate): Align to the page size unconditionally.
2146         Even if the page size is not a power of two, it might be a multiple of
2147         a power of two, and we want alignment to that smaller power of two to
2148         be guaranteed.
2149
2150 2016-04-06  Geoffrey Garen  <ggaren@apple.com>
2151
2152         bmalloc: handle aligned allocations on the fast path
2153         https://bugs.webkit.org/show_bug.cgi?id=156302
2154
2155         Reviewed by Michael Saboff.
2156
2157         This helps keep the JavaScriptCore GC on the fast path, and it also
2158         helps avoid fragmentation on our website stress test:
2159
2160             nimlang                      209,584kB            198,076kB      ^ 1.06x smaller
2161
2162         * bmalloc/Allocator.cpp:
2163         (bmalloc::Allocator::allocate): Because we arrange for power-of-two size
2164         classes to allocate at power-of-two alignments, we can allocate any
2165         small aligned request on the small path.
2166
2167         * bmalloc/Chunk.h:
2168         (bmalloc::Chunk::bytes):
2169         (bmalloc::Chunk::lines):
2170         (bmalloc::Chunk::pages):
2171         (bmalloc::Chunk::boundaryTags):
2172         (bmalloc::Chunk::objectType): Moved some code around to provide better
2173         API.
2174
2175         (bmalloc::Chunk::Chunk): Moved this code to VMHeap.
2176
2177         (bmalloc::Chunk::offset):
2178         (bmalloc::Chunk::object): Use our new bytes() helper function.
2179
2180         * bmalloc/VMHeap.cpp:
2181         (bmalloc::VMHeap::allocateChunk): Moved code here from Chunk.
2182
2183         (bmalloc::VMHeap::allocateSmallChunk): Ensure that power-of-two page
2184         sizes always begin allocation at the same alignment. Power-of-two object
2185         sizes always request power-of-two page sizes (since that's the least
2186         wasteful option), so if we also ensure that power-of-two page sizes get
2187         power-of-two alignment, then everything is aligned for all small objects.
2188
2189 2016-04-03  Geoffrey Garen  <ggaren@apple.com>
2190
2191         bmalloc: segregate small and large objects again, and allocate more objects on the small path
2192         https://bugs.webkit.org/show_bug.cgi?id=156152
2193
2194         Reviewed by Sam Weinig.
2195
2196         Microbenchmark data suggested that it was a good idea for small and large
2197         objects to share memory. But r198675 did not improve memory use in
2198         full browser benchmarks.
2199
2200         This patch reverts to segregating small and large objects -- but without
2201         going back to doubled VM usage -- in order to capture a few benefits:
2202
2203         (*) Small pages fragment the large heap. Separating them out saves a lot
2204         of memory in our worst case fragmentation recording:
2205
2206             nimlang                                          276,076kB                      209,636kB                ^ 1.32x smaller
2207
2208         (*) Small objects are common enough that even their slow paths benefit 
2209         from simpler code:
2210
2211         Execution Time:
2212             ...
2213             facebook                                             234ms                          216ms                 ^ 1.08x faster
2214             reddit                                               114ms                          108ms                 ^ 1.06x faster
2215             flickr                                               118ms                          111ms                 ^ 1.06x faster
2216             theverge                                             146ms                          140ms                 ^ 1.04x faster
2217             ...
2218             <arithmetic mean>                                    107ms                          102ms                 ^ 1.04x faster
2219
2220         (*) We can use less metadata:
2221
2222         Memory at End:
2223             ...
2224             list_allocate                                        460kB                          384kB                 ^ 1.2x smaller
2225             tree_allocate                                        492kB                          424kB                ^ 1.16x smaller
2226             tree_churn                                           480kB                          404kB                ^ 1.19x smaller
2227             fragment                                             532kB                          452kB                ^ 1.18x smaller
2228             fragment_iterate                                     712kB                          588kB                ^ 1.21x smaller
2229             medium                                            15,152kB                       11,796kB                ^ 1.28x smaller
2230             big                                               15,044kB                       10,976kB                ^ 1.37x smaller
2231             ...
2232             <arithmetic mean>                                  7,724kB                        7,190kB                ^ 1.07x smaller
2233
2234         This patch also takes advantage of our support for varying the page size
2235         at runtime by allocating more objects on the small object path:
2236
2237             medium                                               178ms                          150ms                 ^ 1.19x faster
2238
2239         Some microbenchmarks report memory use increases from this change -- like
2240         they reported memory use decreases from r198675 -- but I'm ignoring them
2241         for now because I expect our full browser memory benchmarks to confirm
2242         that this patch is fine.
2243
2244         * bmalloc/BumpAllocator.h:
2245         (bmalloc::BumpAllocator::BumpAllocator): Use a full unsigned because we
2246         can allocate objects larger than 16kB - 1, and a full unsigned does not
2247         make BumpAllocator any larger on 64bit systems.
2248
2249         * bmalloc/Chunk.h:
2250         (bmalloc::Chunk::begin):
2251         (bmalloc::Chunk::end):
2252         (bmalloc::Chunk::size):
2253         (bmalloc::Chunk::objectType): Store ObjectType in the Chunk, since it only
2254         varies by Chunk now, and not from page to page within a Chunk. Also,
2255         union together small and large object metadata, since we will only use
2256         one or the other. This saves memory.
2257
2258         (bmalloc::Chunk::Chunk): Conditionalize initialization based on object
2259         type, since only one kind of metadata or the other can be used at runtime.
2260
2261         (bmalloc::Object::Object):
2262         (bmalloc::Object::begin):
2263         (bmalloc::SmallPage::end): Deleted.
2264
2265         * bmalloc/Heap.cpp:
2266         (bmalloc::Heap::Heap):
2267         (bmalloc::Heap::initializeLineMetadata): Save a little space, since we
2268         know that lines are only 256 bytes long.
2269
2270         (bmalloc::Heap::initializePageMetadata): Store a dynamic page size for
2271         each size class. We used to use only one page size (the system page size)
2272         but that limited our ability to allocate objects larger than 1kB on the
2273         small object path. Now we can handle any object size we want by storing
2274         objects of that size in a custom page size.
2275
2276         (bmalloc::Heap::concurrentScavenge):
2277         (bmalloc::Heap::scavenge):
2278         (bmalloc::Heap::scavengeSmallPages): Revert to our old linked list
2279         strategy for storing small pages.
2280
2281         (bmalloc::Heap::splitAndAllocate): Object type is per Chunk now.
2282
2283         (bmalloc::Heap::allocateLarge): Don't nuke the small page list when
2284         allocating a large object because the two don't share memory anymore.
2285
2286         (bmalloc::Heap::allocateSmallPage): Revert to our old linked list
2287         strategy for storing small pages.
2288
2289         (bmalloc::Heap::deallocateSmallLine): Don't return early in the case
2290         where this is the first free object in the page. In the case of large-ish
2291         objects, the first free object might also be the last free object,
2292         since there's one object per page.
2293
2294         (bmalloc::Heap::allocateSmallBumpRangesByMetadata): Split out some helper
2295         lambdas to make this code clearer.
2296
2297         (bmalloc::Heap::allocateSmallBumpRangesByObject): Added a fast scan
2298         for objects larger than the line size. When multiple objects fit in
2299         a single line, it's an optimization to scan a line at a time. But when
2300         it's one object per line, or one object per 64 lines, it's better just
2301         to scan an object at a time.
2302
2303         * bmalloc/Heap.h:
2304         (bmalloc::Heap::allocateSmallBumpRanges):
2305         (bmalloc::Heap::derefSmallLine): Match the changes above.
2306
2307         * bmalloc/LineMetadata.h: We weren't using all those bits.
2308
2309         * bmalloc/List.h:
2310         (bmalloc::List::remove): Put a removed Node fully back into the default
2311         (empty) state it was in before it entered the list. This change is not
2312         observable, but it makes things clearer when you're debugging.
2313
2314         * bmalloc/Object.h:
2315         (bmalloc::Object::Object):
2316         (bmalloc::Object::chunk):
2317         (bmalloc::Object::offset):
2318         (bmalloc::Object::operator+):
2319         (bmalloc::Object::operator<=): Added some helpers for iterating by object.
2320
2321         * bmalloc/ObjectType.cpp:
2322         (bmalloc::objectType): Updated for API change.
2323
2324         * bmalloc/Sizes.h:
2325         (bmalloc::Sizes::maskObjectSize):
2326         (bmalloc::Sizes::objectSize):
2327         (bmalloc::Sizes::pageSize): Support more page sizes.
2328
2329         * bmalloc/SmallPage.h:
2330         (bmalloc::SmallPage::SmallPage):
2331         (bmalloc::SmallPage::objectType): Deleted.
2332         (bmalloc::SmallPage::setObjectType): Deleted.
2333         (bmalloc::SmallPage::smallPageCount): Deleted.
2334         (bmalloc::SmallPage::setSmallPageCount): Deleted. Object type is per
2335         Chunk now, and we can infer page count from size class.
2336
2337         * bmalloc/VMHeap.cpp:
2338         (bmalloc::VMHeap::allocateChunk):
2339         (bmalloc::VMHeap::allocateSmallChunk):
2340         * bmalloc/VMHeap.h:
2341         (bmalloc::VMHeap::allocateSmallPage):
2342         (bmalloc::VMHeap::deallocateSmallPage):
2343         (bmalloc::VMHeap::allocateLargeObject): Support our old behavior of
2344         storing free pages in linked lists.
2345
2346 2016-03-29  Geoffrey Garen  <ggaren@apple.com>
2347
2348         bmalloc: support physical page sizes that don't match the virtual page size (take 2)
2349         https://bugs.webkit.org/show_bug.cgi?id=156003
2350
2351         Reviewed by Andreas Kling.
2352
2353         This is a memory savings on iOS devices where the virtual page size
2354         is 16kB but the physical page size is 4kB.
2355
2356         Take 1 was a memory regression on 16kB virtual / 16kB physical systems
2357         because it used a 4kB page size within a 16kB page size, allowing up to
2358         4 different object types to mix within a physical page. Because objects
2359         of the same type tend to deallocate at the same time, mixing objects of
2360         different types made pages less likely to become completely empty.
2361
2362         (Take 1 also had a bug where it used a platform #ifdef that didn't exist.
2363         Oops.)
2364
2365         Take 2 allocates units of SmallPages equal to the physical page size.
2366
2367         * bmalloc/Heap.cpp:
2368         (bmalloc::Heap::Heap):
2369         (bmalloc::Heap::initializeLineMetadata):
2370         (bmalloc::Heap::allocateSmallBumpRanges):
2371         (bmalloc::Heap::allocateSmallPage):
2372         (bmalloc::Heap::allocateLarge):
2373         (bmalloc::Heap::splitAndAllocate):
2374         (bmalloc::Heap::tryAllocateXLarge):
2375         (bmalloc::Heap::shrinkXLarge):
2376         * bmalloc/Heap.h: Use the physical page size for our VM operations because
2377         we're only concerned with returning physical pages to the OS.
2378
2379         * bmalloc/VMAllocate.h:
2380         (bmalloc::vmPageSize):
2381         (bmalloc::vmPageShift):
2382         (bmalloc::vmSize):
2383         (bmalloc::vmValidate):
2384         (bmalloc::vmPageSizePhysical):
2385         (bmalloc::vmValidatePhysical):
2386         (bmalloc::tryVMAllocate):
2387         (bmalloc::vmDeallocatePhysicalPages):
2388         (bmalloc::vmAllocatePhysicalPages):
2389         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2390         (bmalloc::vmAllocatePhysicalPagesSloppy): Use the physical page size.
2391
2392 2016-03-29  Geoffrey Garen  <ggaren@apple.com>
2393
2394         bmalloc: page size should be configurable at runtime
2395         https://bugs.webkit.org/show_bug.cgi?id=155993
2396
2397         Reviewed by Andreas Kling.
2398
2399         This is a memory win on 32bit iOS devices, since their page sizes are
2400         4kB and not 16kB.
2401
2402         It's also a step toward supporting 64bit iOS devices that have a
2403         16kB/4kB virtual/physical page size split.
2404
2405         * bmalloc/Chunk.h: Align to largeAlignment since 2 * smallMax isn't
2406         required by the boundary tag allocator.
2407
2408         (bmalloc::Chunk::page): Account for the slide when accessing a page.
2409         Each SmallPage hashes 4kB of memory. When we want to allocate a region
2410         of memory larger than 4kB, we store our metadata in the first SmallPage
2411         in the region and we assign a slide to the remaining SmallPages, so
2412         they forward to that first SmallPage when accessed.
2413
2414         NOTE: We could use a less flexible technique that just hashed by
2415         vmPageSize() instead of 4kB at runtime, with no slide, but I think we'll
2416         be able to use this slide technique to make even more page sizes
2417         dynamically at runtime, which should save some memory and simplify
2418         the allocator.
2419
2420         (bmalloc::SmallPage::begin): It's invalid to access a SmallPage with
2421         a slide, since such SmallPages do not contain meaningful data.
2422
2423         (bmalloc::SmallPage::end): Account for smallPageCount when computing
2424         the size of a page.
2425
2426         (bmalloc::Chunk::pageBegin): Deleted.
2427         (bmalloc::Chunk::pageEnd): Deleted.
2428         (bmalloc::Object::pageBegin): Deleted.
2429
2430         * bmalloc/Heap.cpp:
2431         (bmalloc::Heap::Heap): Cache vmPageSize because computing it might require
2432         a syscall.
2433
2434         (bmalloc::Heap::initializeLineMetadata): Line metadata is a vector instead
2435         of a 2D array because we don't know how much metadata we'll need until
2436         we know the page size.
2437
2438         (bmalloc::Heap::scavengeSmallPage): Be sure to revert the slide when
2439         deallocating a page. Otherwise, the next attempt to allocate the page
2440         will slide when initializing it, sliding to nowhere.
2441
2442         (bmalloc::Heap::allocateSmallBumpRanges): Account for vector change to
2443         line metadata.
2444
2445         (bmalloc::Heap::allocateSmallPage): Initialize slide and smallPageCount
2446         since they aren't constant anymore.
2447
2448         (bmalloc::Heap::allocateLarge):
2449         (bmalloc::Heap::splitAndAllocate):
2450         (bmalloc::Heap::tryAllocateXLarge):
2451         (bmalloc::Heap::shrinkXLarge): Adopt dynamic page size.
2452
2453         * bmalloc/Heap.h:
2454
2455         * bmalloc/Sizes.h: smallPageSize is no longer equal to the VM page
2456         size -- it's just the smallest VM page size we're interested in supporting.
2457
2458         * bmalloc/SmallPage.h:
2459         (bmalloc::SmallPage::slide):
2460         (bmalloc::SmallPage::setSlide):
2461         (bmalloc::SmallPage::smallPageCount):
2462         (bmalloc::SmallPage::setSmallPageCount):
2463         (bmalloc::SmallPage::ref):
2464         (bmalloc::SmallPage::deref): Support slide and small page count as
2465         dynamic values. This doesn't increase metadata size since sizeof(SmallPage)
2466         rounds up to alignment anyway.
2467
2468         * bmalloc/VMAllocate.h:
2469         (bmalloc::vmPageSize):
2470         (bmalloc::vmPageShift):
2471         (bmalloc::vmSize):
2472         (bmalloc::vmValidate):
2473         (bmalloc::tryVMAllocate):
2474         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2475         (bmalloc::vmAllocatePhysicalPagesSloppy): Treat page size as a variable.
2476
2477         * bmalloc/Vector.h:
2478         (bmalloc::Vector::initialCapacity):
2479         (bmalloc::Vector<T>::insert):
2480         (bmalloc::Vector<T>::grow):
2481         (bmalloc::Vector<T>::shrink):
2482         (bmalloc::Vector<T>::shrinkCapacity):
2483         (bmalloc::Vector<T>::growCapacity): Treat page size as a variable.
2484
2485 2016-03-29  David Kilzer  <ddkilzer@apple.com>
2486
2487         bmalloc: add logging for mmap() failures
2488         <http://webkit.org/b/155409>
2489         <rdar://problem/24568515>
2490
2491         Reviewed by Saam Barati.
2492
2493         This patch causes additional logging to be generated on internal
2494         iOS builds when mmap() fails.  We are trying to track down an
2495         issue where the WebContent process runs out of VM address space
2496         before it is killed by jetsam.
2497
2498         * CMakeLists.txt: Add Logging.cpp.
2499         * bmalloc.xcodeproj/project.pbxproj: Add new files.
2500
2501         * bmalloc/BAssert.h:
2502         (RELEASE_BASSERT_WITH_MESSAGE): Add macro.
2503         * bmalloc/Logging.cpp: Added.
2504         (bmalloc::logVMFailure): Implementation.
2505         * bmalloc/Logging.h: Added.
2506         (bmalloc::logVMFailure): Declaration.
2507         * bmalloc/VMAllocate.h:
2508         (bmalloc::tryVMAllocate): Call logVMFailure() on mmap() failure.
2509         * bmalloc/darwin/BSoftLinking.h: Copied from Source/WebCore/platform/mac/SoftLinking.h.
2510
2511 2016-03-26  Geoffrey Garen  <ggaren@apple.com>
2512
2513         Unreviewed, rolling out r198702, r198704.
2514
2515         Caused a memory regression on PLUM.
2516
2517         Reverted changeset:
2518
2519         bmalloc: fix an ASSERT on iOS
2520         https://bugs.webkit.org/show_bug.cgi?id=155911
2521         http://trac.webkit.org/changeset/198704
2522
2523         bmalloc: support physical page sizes that don't match the virtual page size
2524         https://bugs.webkit.org/show_bug.cgi?id=155898
2525         http://trac.webkit.org/changeset/198702
2526
2527 2016-03-25  Geoffrey Garen  <ggaren@apple.com>
2528
2529         bmalloc: fix an ASSERT on iOS
2530         https://bugs.webkit.org/show_bug.cgi?id=155911
2531
2532         Reviewed by Gavin Barraclough.
2533
2534         * bmalloc/VMAllocate.h:
2535         (bmalloc::vmValidatePhysical): Call through to vmValidatePhysical because
2536         the vmValidate function validates virtual sizes rather than physical
2537         sizes.
2538
2539 2016-03-25  Geoffrey Garen  <ggaren@apple.com>
2540
2541         bmalloc: support physical page sizes that don't match the virtual page size
2542         https://bugs.webkit.org/show_bug.cgi?id=155898
2543
2544         Reviewed by Gavin Barraclough.
2545
2546         This is a memory savings on iOS devices where the virtual page size
2547         is 16kB but the physical page size is 4kB.
2548
2549         * bmalloc/Chunk.h:
2550         (bmalloc::Chunk::Chunk): smallPageSize is now unrelated to the OS's
2551         page size -- it just reflects the optimal unit of memory to recycle
2552         between small objects.
2553
2554         We only need to round up to largeAlignment because small objects allocate
2555         as subsets of large objects now.
2556
2557         (bmalloc::Chunk::page):
2558         (bmalloc::Object::pageBegin):
2559         (bmalloc::Object::line): Adopt smallPageSize.
2560
2561         * bmalloc/Heap.cpp:
2562         (bmalloc::Heap::initializeLineMetadata):
2563         (bmalloc::Heap::allocateSmallPage):
2564         (bmalloc::Heap::allocateLarge): Adopt smallPageSize.
2565
2566         (bmalloc::Heap::splitAndAllocate):
2567         (bmalloc::Heap::tryAllocateXLarge):
2568         (bmalloc::Heap::shrinkXLarge): Adopt vmPageSizePhysical(). We want the
2569         physical page size because that's the unit at which the hardware MMU
2570         will recycle memory.
2571
2572         * bmalloc/Sizes.h: Adopt smallPageSize.
2573
2574         * bmalloc/VMAllocate.h:
2575         (bmalloc::vmPageSizePhysical):
2576         (bmalloc::vmPageSize): Distinguish between page size, which is the virtual
2577         memory page size advertised by the OS, and physical page size, which the
2578         true hardware page size.
2579
2580         (bmalloc::vmSize):
2581         (bmalloc::vmValidate):
2582         (bmalloc::vmValidatePhysical):
2583         (bmalloc::tryVMAllocate):
2584         (bmalloc::vmDeallocatePhysicalPages):
2585         (bmalloc::vmAllocatePhysicalPages):
2586         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2587         (bmalloc::vmAllocatePhysicalPagesSloppy): Adopt vmPageSize() and
2588         vmPageSizePhyiscal().
2589
2590         * bmalloc/Vector.h:
2591         (bmalloc::Vector::initialCapacity):
2592         (bmalloc::Vector<T>::shrink):
2593         (bmalloc::Vector<T>::shrinkCapacity):
2594         (bmalloc::Vector<T>::growCapacity): Adopt vmPageSize(). We'd prefer to
2595         use vmPageSizePhysical() but mmap() doesn't support it.
2596
2597         * bmalloc/XLargeMap.cpp: #include.
2598
2599 2016-03-25  Geoffrey Garen  <ggaren@apple.com>
2600
2601         Unreviewed, rolling in r198679.
2602
2603         r198679 was just a rename. The regression was caused by r198675 and then
2604         fixed in r198693.
2605
2606         Restored changeset:
2607
2608         "bmalloc: Renamed LargeChunk => Chunk"
2609         https://bugs.webkit.org/show_bug.cgi?id=155894
2610         http://trac.webkit.org/changeset/198679
2611
2612 2016-03-25  Geoffrey Garen  <ggaren@apple.com>
2613
2614         Unreviewed, try to fix a crash seen on the bots.
2615
2616         * bmalloc/Allocator.cpp:
2617         (bmalloc::Allocator::reallocate): We have to take the lock even if we're
2618         only reading our own data becuse LargeObject contains validation code
2619         that will read our neighbors' data as well.
2620
2621 2016-03-25  Ryan Haddad  <ryanhaddad@apple.com>
2622
2623         Unreviewed, rolling out r198679.
2624
2625         This change caused flaky LayoutTest crashes
2626
2627         Reverted changeset:
2628
2629         "bmalloc: Renamed LargeChunk => Chunk"
2630         https://bugs.webkit.org/show_bug.cgi?id=155894
2631         http://trac.webkit.org/changeset/198679
2632
2633 2016-03-25  Geoffrey Garen  <ggaren@apple.com>
2634
2635         bmalloc: stress_aligned fails when allocating a zero-sized object with XLarge alignment
2636         https://bugs.webkit.org/show_bug.cgi?id=155896
2637
2638         Reviewed by Andreas Kling.
2639
2640         We normally filter zero-sized allocations into small allocations, but
2641         a zero-sized allocation can sneak through if it requires sufficiently
2642         large alignment.
2643
2644         * bmalloc/Heap.cpp:
2645         (bmalloc::Heap::tryAllocateXLarge): Set a floor on allocation size to
2646         catch zero-sized allocations.
2647
2648 2016-03-25  Geoffrey Garen  <ggaren@apple.com>
2649
2650         bmalloc: Renamed LargeChunk => Chunk
2651         https://bugs.webkit.org/show_bug.cgi?id=155894
2652
2653         Reviewed by Michael Saboff.
2654
2655         A Chunk can contain both small and large objects now.
2656
2657         * bmalloc.xcodeproj/project.pbxproj:
2658         * bmalloc/Allocator.cpp:
2659         (bmalloc::Allocator::allocate):
2660         * bmalloc/BoundaryTag.h:
2661         (bmalloc::BoundaryTag::isFree):
2662         * bmalloc/Chunk.h: Copied from Source/bmalloc/bmalloc/LargeChunk.h.
2663         (bmalloc::Chunk::pages):
2664         (bmalloc::Chunk::begin):
2665         (bmalloc::Chunk::end):
2666         (bmalloc::Chunk::Chunk):
2667         (bmalloc::Chunk::get):
2668         (bmalloc::Chunk::beginTag):
2669         (bmalloc::Chunk::endTag):
2670         (bmalloc::Chunk::offset):
2671         (bmalloc::Chunk::object):
2672         (bmalloc::Chunk::page):
2673         (bmalloc::Chunk::line):
2674         (bmalloc::SmallLine::begin):
2675         (bmalloc::SmallPage::begin):
2676         (bmalloc::SmallPage::end):
2677         (bmalloc::Object::Object):
2678         (bmalloc::Object::begin):
2679         (bmalloc::LargeChunk::pages): Deleted.
2680         (bmalloc::LargeChunk::begin): Deleted.
2681         (bmalloc::LargeChunk::end): Deleted.
2682         (bmalloc::LargeChunk::LargeChunk): Deleted.
2683         (bmalloc::LargeChunk::get): Deleted.
2684         (bmalloc::LargeChunk::beginTag): Deleted.
2685         (bmalloc::LargeChunk::endTag): Deleted.
2686         (bmalloc::LargeChunk::offset): Deleted.
2687         (bmalloc::LargeChunk::object): Deleted.
2688         (bmalloc::LargeChunk::page): Deleted.
2689         (bmalloc::LargeChunk::line): Deleted.
2690         * bmalloc/Deallocator.cpp:
2691         * bmalloc/FreeList.cpp:
2692         * bmalloc/Heap.cpp:
2693         (bmalloc::Heap::allocateLarge):
2694         * bmalloc/LargeChunk.h: Removed.
2695         * bmalloc/LargeObject.h:
2696         (bmalloc::LargeObject::LargeObject):
2697         (bmalloc::LargeObject::merge):
2698         (bmalloc::LargeObject::split):
2699         * bmalloc/Object.h:
2700         (bmalloc::Object::chunk):
2701         * bmalloc/ObjectType.cpp:
2702         * bmalloc/Sizes.h:
2703         * bmalloc/SmallAllocator.h: Removed.
2704         * bmalloc/VMHeap.cpp:
2705         (bmalloc::VMHeap::VMHeap):
2706         (bmalloc::VMHeap::allocateChunk):
2707         (bmalloc::VMHeap::allocateLargeChunk): Deleted.
2708         * bmalloc/VMHeap.h:
2709         (bmalloc::VMHeap::allocateLargeObject):
2710         (bmalloc::VMHeap::deallocateLargeObject):
2711         * bmalloc/Zone.cpp:
2712         (bmalloc::enumerator):
2713         * bmalloc/Zone.h:
2714         (bmalloc::Zone::chunks):
2715         (bmalloc::Zone::addChunk):
2716         (bmalloc::Zone::largeChunks): Deleted.
2717         (bmalloc::Zone::addLargeChunk): Deleted.
2718
2719 2016-03-24  Geoffrey Garen  <ggaren@apple.com>
2720
2721         bmalloc: small and large objects should share memory
2722         https://bugs.webkit.org/show_bug.cgi?id=155866
2723
2724         Reviewed by Andreas Kling.
2725
2726         This patch cuts our VM footprint in half. (VM footprint usually doesn't
2727         matter, but on iOS there's an artificial VM limit around 700MB, and if
2728         you hit it you jetsam / crash.)
2729
2730         It's also a step toward honoring the hardware page size at runtime,
2731         which will reduce memory usage on iOS.
2732
2733         This patch is a small improvement in peak memory usage because it allows
2734         small and large objects to recycle each other's memory. The tradeoff is
2735         that we require more metadata, which causes more memory usage after
2736         shrinking down from peak memory usage. In the end, we have some memory
2737         wins and some losses, and a small win in the mean on our standard memory
2738         benchmarks.
2739
2740         * bmalloc.xcodeproj/project.pbxproj: Removed SuperChunk.
2741
2742         * bmalloc/Allocator.cpp:
2743         (bmalloc::Allocator::reallocate): Adopt a new Heap API for shrinking
2744         large objects because it's a little more complicated than it used to be.
2745
2746         Don't check for equality in the XLarge case because we don't do it in
2747         other cases, and it's unlikely that we'll be called for no reason.
2748
2749         * bmalloc/BumpAllocator.h:
2750         (bmalloc::BumpAllocator::allocate): Don't ASSERT isSmall because that's
2751         an old concept from when small and large objects were in distinct memory
2752         regions.
2753
2754         * bmalloc/Deallocator.cpp:
2755         (bmalloc::Deallocator::deallocateSlowCase): Large objects are not
2756         segregated anymore.
2757
2758         (bmalloc::Deallocator::deallocateLarge): Deleted.
2759
2760         * bmalloc/Deallocator.h:
2761         (bmalloc::Deallocator::deallocateFastCase): Don't ASSERT isSmall(). See
2762         above.
2763
2764         * bmalloc/Heap.cpp:
2765         (bmalloc::Heap::scavenge):
2766         (bmalloc::Heap::scavengeSmallPage):
2767         (bmalloc::Heap::scavengeSmallPages): New helpers for returning cached
2768         small pages to the large object heap.
2769
2770         (bmalloc::Heap::allocateSmallPage): Allocate small pages from the large
2771         object heap. This is how we accomplish sharing.
2772
2773         (bmalloc::Heap::deallocateSmallLine): Handle large objects since we can
2774         encounter them on this code path now.
2775
2776         (bmalloc::Heap::splitAndAllocate): Fixed a bug where we would sometimes
2777         not split even though we could.
2778
2779         Allocating a large object also requires ref'ing its small line so that
2780         we can alias memory between small and large objects.
2781
2782         (bmalloc::Heap::allocateLarge): Return cached small pages before
2783         allocating a large object that would fit in a cached small page. This
2784         allows some large allocations to reuse small object memory.
2785
2786         (bmalloc::Heap::shrinkLarge): New helper.
2787
2788         (bmalloc::Heap::deallocateLarge): Deleted.
2789
2790         * bmalloc/Heap.h:
2791
2792         * bmalloc/LargeChunk.h:
2793         (bmalloc::LargeChunk::pageBegin):
2794         (bmalloc::LargeChunk::pageEnd):
2795         (bmalloc::LargeChunk::lines):
2796         (bmalloc::LargeChunk::pages):
2797         (bmalloc::LargeChunk::begin):
2798         (bmalloc::LargeChunk::end):
2799         (bmalloc::LargeChunk::LargeChunk):
2800         (bmalloc::LargeChunk::get):
2801         (bmalloc::LargeChunk::endTag):
2802         (bmalloc::LargeChunk::offset):
2803         (bmalloc::LargeChunk::object):
2804         (bmalloc::LargeChunk::page):
2805         (bmalloc::LargeChunk::line):
2806         (bmalloc::SmallLine::begin):
2807         (bmalloc::SmallLine::end):
2808         (bmalloc::SmallPage::begin):
2809         (bmalloc::SmallPage::end):
2810         (bmalloc::Object::Object):
2811         (bmalloc::Object::begin):
2812         (bmalloc::Object::pageBegin):
2813         (bmalloc::Object::line):
2814         (bmalloc::Object::page): I merged all the SmallChunk metadata and code
2815         into LargeChunk. Now we use a single class to track both small and large
2816         metadata, so we can share memory between small and large objects.
2817
2818         I'm going to rename this class to Chunk in a follow-up patch.
2819
2820         * bmalloc/Object.h:
2821         (bmalloc::Object::chunk): Updated for LargeChunk transition.
2822
2823         * bmalloc/ObjectType.cpp:
2824         (bmalloc::objectType):
2825         * bmalloc/ObjectType.h:
2826         (bmalloc::isXLarge):
2827         (bmalloc::isSmall): Deleted. The difference between small and large
2828         objects is now stored in metadata and is not a property of their
2829         virtual address range.
2830
2831         * bmalloc/SegregatedFreeList.h: One more entry because we cover all of
2832         what used to be the super chunk in a large chunk now.
2833
2834         * bmalloc/Sizes.h: Removed bit masking helpers because we don't use
2835         address masks to distinguish small vs large object type anymore.
2836
2837         * bmalloc/SmallChunk.h: Removed.
2838
2839         * bmalloc/SmallPage.h:
2840         (bmalloc::SmallPage::SmallPage): Store object type per page because any
2841         given page can be used for large objects or small objects.
2842
2843         * bmalloc/SuperChunk.h: Removed.
2844
2845         * bmalloc/VMHeap.cpp:
2846         (bmalloc::VMHeap::VMHeap):
2847         (bmalloc::VMHeap::allocateLargeChunk):
2848         (bmalloc::VMHeap::allocateSmallChunk): Deleted.
2849         (bmalloc::VMHeap::allocateSuperChunk): Deleted.
2850         * bmalloc/VMHeap.h:
2851         (bmalloc::VMHeap::allocateLargeObject):
2852         (bmalloc::VMHeap::deallocateLargeObject):
2853         (bmalloc::VMHeap::allocateSmallPage): Deleted.
2854         (bmalloc::VMHeap::deallocateSmallPage): Deleted. Removed super chunk and
2855         small chunk support.
2856
2857         * bmalloc/Zone.cpp:
2858         (bmalloc::enumerator):
2859         * bmalloc/Zone.h:
2860         (bmalloc::Zone::largeChunks):
2861         (bmalloc::Zone::addLargeChunk):
2862         (bmalloc::Zone::superChunks): Deleted.
2863         (bmalloc::Zone::addSuperChunk): Deleted. Removed super chunk and
2864         small chunk support.
2865
2866 2016-03-23  Geoffrey Garen  <ggaren@apple.com>
2867
2868         bmalloc: Added an Object helper class
2869         https://bugs.webkit.org/show_bug.cgi?id=155818
2870
2871         Reviewed by Gavin Barraclough.
2872
2873         Object is an abstraction that breaks out a void* into its component
2874         metadata pointers.
2875
2876         This is slightly faster than recomputing them, and it enables a future
2877         patch in which Object will tell us whether it is small or large.
2878
2879         * bmalloc.xcodeproj/project.pbxproj: Added to the project.
2880
2881         * bmalloc/Allocator.cpp:
2882         (bmalloc::Allocator::reallocate): Use Object to compute size.
2883
2884         * bmalloc/Deallocator.cpp:
2885         (bmalloc::Deallocator::processObjectLog):
2886         * bmalloc/Heap.cpp:
2887         (bmalloc::Heap::allocateSmallPage):
2888         (bmalloc::Heap::deallocateSmallLine):
2889         * bmalloc/Heap.h:
2890         (bmalloc::Heap::derefSmallLine): Use Object to deallocate.
2891
2892         * bmalloc/Object.h: Added.
2893         (bmalloc::Object::Object):
2894         (bmalloc::Object::chunk):
2895         (bmalloc::Object::line):
2896         (bmalloc::Object::page): Helper class to break out a void* into its
2897         component metadata pointers.
2898
2899         * bmalloc/SmallChunk.h:
2900         (bmalloc::SmallChunk::SmallChunk): SmallPage::get doesn't exist anymore
2901         so we use our new helper functions instead.
2902
2903         (bmalloc::SmallChunk::offset):
2904         (bmalloc::SmallChunk::object):
2905         (bmalloc::SmallChunk::page):
2906         (bmalloc::SmallChunk::line):
2907         (bmalloc::SmallLine::begin):
2908         (bmalloc::SmallLine::end):
2909         (bmalloc::SmallPage::begin): New helpers that operate on the data
2910         stored in Object.
2911
2912         (bmalloc::SmallLine::get): Deleted.
2913         (bmalloc::SmallPage::get): Deleted.
2914
2915         * bmalloc/SmallLine.h:
2916         (bmalloc::SmallLine::refCount): Added a default ref value for convenience.
2917
2918         * bmalloc/SmallPage.h:
2919         (bmalloc::SmallPage::SmallPage):
2920
2921 2016-03-23  Geoffrey Garen  <ggaren@apple.com>
2922
2923         bmalloc: process the object log before asking for new memory
2924         https://bugs.webkit.org/show_bug.cgi?id=155801
2925
2926         Reviewed by Gavin Barraclough.
2927
2928         This is a step toward merging large and small objects: In future, if we
2929         have large objects in the log, we need to process them right away to
2930         avoid pushing up peak memory use.
2931
2932         But it also appears to be a speedup and memory use improvement now.
2933
2934         * bmalloc/Allocator.cpp:
2935         (bmalloc::Allocator::allocate):
2936         (bmalloc::Allocator::refillAllocatorSlowCase):
2937         (bmalloc::Allocator::allocateLarge): Process the log before asking for
2938         more memory.
2939
2940         * bmalloc/Deallocator.cpp:
2941         (bmalloc::Deallocator::processObjectLog):
2942         (bmalloc::Deallocator::deallocateSlowCase):
2943         * bmalloc/Deallocator.h: Provide a public API for processing the object log.
2944
2945         * bmalloc/Heap.cpp:
2946         (bmalloc::Heap::allocateSmallPage): Pop fragmented pages from the front
2947         instead of from the back. This resolves a regression on tree_churn
2948         --parallel. Popping from the front gives us the oldest pages. The oldest
2949         pages have had the most time to accumulate free lines. They are therefore
2950         the least fragmented on average.
2951
2952         * bmalloc/List.h:
2953         (bmalloc::List::popFront):
2954         (bmalloc::List::insertAfter): New API to pop from front.
2955
2956 2016-03-22  Geoffrey Garen  <ggaren@apple.com>
2957
2958         bmalloc: use a log scale for large-ish size classes
2959         https://bugs.webkit.org/show_bug.cgi?id=155770
2960
2961         Reviewed by Michael Saboff.
2962
2963         At larger sizes, precise allocation sizes don't save much memory -- and
2964         they can cost memory when objects of distinct size classes can't
2965         allocate together.
2966
2967         This is a small savings up to our current allocation limits, and it may
2968         enable changing those limits in the long term.
2969
2970         * bmalloc/Algorithm.h:
2971         (bmalloc::log2): We use this to compute large-ish size classes.
2972
2973         * bmalloc/Allocator.cpp:
2974         (bmalloc::Allocator::Allocator): Iterate by size class instead of by
2975         object size so we can change object size limits without breaking stuff.
2976
2977         (bmalloc::Allocator::scavenge): Ditto.
2978
2979         (bmalloc::Allocator::allocateLogSizeClass): New helper function for
2980         allocating based on log size classes.
2981
2982         (bmalloc::Allocator::allocateSlowCase): Account for extra size class
2983         possibilities.
2984
2985         * bmalloc/Allocator.h:
2986         (bmalloc::Allocator::allocateFastCase): We only handle up to 512b on
2987         the fastest fast path now.
2988
2989         * bmalloc/BumpAllocator.h:
2990         (bmalloc::BumpAllocator::validate): Deleted. I noticed that this function
2991         had been refactored not to do anything anymore.
2992
2993         * bmalloc/Heap.cpp:
2994         (bmalloc::Heap::initializeLineMetadata): Iterate by size class. (See
2995         Allocator::Allocator.)
2996
2997         * bmalloc/Heap.h: Use the sizeClassCount constant instead of hard coding
2998         things.
2999
3000         * bmalloc/Sizes.h:
3001         (bmalloc::Sizes::maskSizeClass):
3002         (bmalloc::Sizes::maskObjectSize):
3003         (bmalloc::Sizes::logSizeClass):
3004         (bmalloc::Sizes::logObjectSize):
3005         (bmalloc::Sizes::sizeClass):
3006         (bmalloc::Sizes::objectSize): Separate size class calculation between
3007         simple size classes that can be computed with a mask and are 8-byte-precise
3008         and complex size classes that require more math and are less precise.
3009
3010         * bmalloc/SmallLine.h:
3011         (bmalloc::SmallLine::ref):
3012         * bmalloc/SmallPage.h:
3013         (bmalloc::SmallPage::SmallPage):
3014         (bmalloc::SmallPage::ref):
3015         (bmalloc::SmallPage::deref): Cleaned up some ASSERTs that triggered
3016         while working on this patch.
3017
3018         * bmalloc/Zone.cpp:
3019         (bmalloc::statistics):
3020         (bmalloc::zoneSize):
3021         (bmalloc::Zone::Zone):
3022         (bmalloc::size): Deleted. Renamed these symbols to work around an lldb
3023         bug that makes it impossible to print out variables named 'size' -- which
3024         can be a problem when working on malloc.
3025
3026 2016-03-22  Geoffrey Garen  <ggaren@apple.com>
3027
3028         bmalloc: shrink largeMax
3029         https://bugs.webkit.org/show_bug.cgi?id=155759
3030
3031         Reviewed by Michael Saboff.
3032
3033         If a largeChunk contains N bytes and we allocate objects of size
3034         N / 2 + 8 bytes, then we waste 50% of physical memory at peak.
3035
3036         This patch sets largeMax to N / 2, reducing maximum waste to 25%.
3037
3038         * bmalloc/BoundaryTag.h:
3039         * bmalloc/LargeChunk.h:
3040         (bmalloc::LargeChunk::LargeChunk):
3041         * bmalloc/SegregatedFreeList.cpp:
3042         (bmalloc::SegregatedFreeList::SegregatedFreeList):
3043         (bmalloc::SegregatedFreeList::insert): Honor largeMax vs largeObjectMax.
3044
3045         * bmalloc/Sizes.h: Distinguish between the largest thing we can store
3046         in a free list (largeObjectMax) and the largest thing we're willing to
3047         allocate (largeMax).
3048
3049 2016-03-20  Dan Bernstein  <mitz@apple.com>
3050
3051         [Mac] Determine TARGET_MAC_OS_X_VERSION_MAJOR from MACOSX_DEPLOYMENT_TARGET rather than from MAC_OS_X_VERSION_MAJOR
3052         https://bugs.webkit.org/show_bug.cgi?id=155707
3053         <rdar://problem/24980691>
3054
3055         Reviewed by Darin Adler.
3056
3057         * Configurations/Base.xcconfig: Set TARGET_MAC_OS_X_VERSION_MAJOR based on the last
3058           component of MACOSX_DEPLOYMENT_TARGET.
3059         * Configurations/DebugRelease.xcconfig: For engineering builds, preserve the behavior of
3060           TARGET_MAC_OS_X_VERSION_MAJOR being the host’s OS version.
3061
3062 2016-03-20  Dan Bernstein  <mitz@apple.com>
3063
3064         Update build settings
3065
3066         Rubber-stamped by Andy Estes.
3067
3068         * Configurations/DebugRelease.xcconfig:
3069
3070 2016-03-14  Geoffrey Garen  <ggaren@apple.com>
3071
3072         Unreviewed, rolling out r197955.
3073
3074         I decided to go in another direction
3075
3076         Reverted changeset:
3077
3078         "bmalloc: Rename SmallPage to SmallRun"
3079         https://bugs.webkit.org/show_bug.cgi?id=155320
3080         http://trac.webkit.org/changeset/197955
3081
3082 2016-03-10  Geoffrey Garen  <ggaren@apple.com>
3083
3084         bmalloc: Rename SmallPage to SmallRun
3085         https://bugs.webkit.org/show_bug.cgi?id=155320
3086
3087         Reviewed by Alex Christensen.
3088
3089         A page is a fixed-size set of lines.
3090
3091         A run is an variable-sized set of lines.
3092
3093         We want to start using runs because:
3094
3095             (a) we want to support varying the hardware page size by OS;
3096
3097             (b) we want to support allocations larger than our current page size.
3098
3099         * bmalloc.xcodeproj/project.pbxproj:
3100         * bmalloc/Allocator.cpp:
3101         (bmalloc::Allocator::reallocate):
3102         * bmalloc/Heap.cpp:
3103         (bmalloc::Heap::Heap):
3104         (bmalloc::Heap::initializeSmallRunMetadata):
3105         (bmalloc::Heap::scavenge):
3106         (bmalloc::Heap::scavengeSmallRuns):
3107         (bmalloc::Heap::allocateSmallBumpRanges):
3108         (bmalloc::Heap::allocateSmallRun):
3109         (bmalloc::Heap::deallocateSmallLine):
3110         (bmalloc::Heap::initializeLineMetadata): Deleted.
3111         (bmalloc::Heap::scavengeSmallPages): Deleted.
3112         (bmalloc::Heap::allocateSmallPage): Deleted.
3113         * bmalloc/Heap.h:
3114         * bmalloc/LineMetadata.h:
3115         * bmalloc/SmallChunk.h:
3116         (bmalloc::SmallChunk::begin):
3117         (bmalloc::SmallChunk::end):
3118         (bmalloc::SmallChunk::lines):
3119         (bmalloc::SmallChunk::runs):
3120         (bmalloc::SmallChunk::SmallChunk):
3121         (bmalloc::SmallLine::end):
3122         (bmalloc::SmallRun::get):
3123         (bmalloc::SmallRun::begin):
3124         (bmalloc::SmallRun::end):
3125         (bmalloc::SmallChunk::pages): Deleted.
3126         (bmalloc::SmallPage::get): Deleted.
3127         (bmalloc::SmallPage::begin): Deleted.
3128         (bmalloc::SmallPage::end): Deleted.
3129         * bmalloc/SmallPage.h: Removed.
3130         * bmalloc/SmallRun.h: Copied from Source/bmalloc/bmalloc/SmallPage.h.
3131         (bmalloc::SmallRun::SmallRun):
3132         (bmalloc::SmallRun::ref):
3133         (bmalloc::SmallRun::deref):
3134         (bmalloc::SmallPage::SmallPage): Deleted.
3135         (bmalloc::SmallPage::ref): Deleted.
3136         (bmalloc::SmallPage::deref): Deleted.
3137         * bmalloc/VMHeap.cpp:
3138         (bmalloc::VMHeap::allocateSmallChunk):
3139         (bmalloc::VMHeap::allocateLargeChunk):
3140         * bmalloc/VMHeap.h:
3141         (bmalloc::VMHeap::allocateSmallRun):
3142         (bmalloc::VMHeap::allocateLargeObject):
3143         (bmalloc::VMHeap::deallocateSmallRun):
3144         (bmalloc::VMHeap::deallocateLargeObject):
3145         (bmalloc::VMHeap::allocateSmallPage): Deleted.
3146         (bmalloc::VMHeap::deallocateSmallPage): Deleted.
3147
3148 2016-03-08  Geoffrey Garen  <ggaren@apple.com>
3149
3150         Unreviewed, rolling in r197722.
3151         https://bugs.webkit.org/show_bug.cgi?id=155171
3152
3153         The right calculation for our static_assert is actually:
3154
3155             sizeof(SmallChunk) % vmPageSize + 2 * smallMax <= vmPageSize
3156
3157         instead of:
3158
3159             sizeof(SmallChunk) % vmPageSize + smallMax <= vmPageSize
3160
3161         smallMax is not enough because line metadata might require us to begin
3162         allocation at an offset as large as smallMax, so we need 2 * smallMax.
3163
3164         Once correct, this static_assert fires, and we fix it by increasing
3165         the alignment of SmallChunk.
3166
3167         Restored changeset:
3168
3169         "bmalloc: Use List<T> instead of Vector<T> in some places"
3170         https://bugs.webkit.org/show_bug.cgi?id=155150
3171         http://trac.webkit.org/changeset/197722
3172
3173 2016-03-08  Commit Queue  <commit-queue@webkit.org>
3174
3175         Unreviewed, rolling out r197722.
3176         https://bugs.webkit.org/show_bug.cgi?id=155171
3177
3178         This change caused 800+ JSC test failures (Requested by
3179         ryanhaddad on #webkit).
3180
3181         Reverted changeset:
3182
3183         "bmalloc: Use List<T> instead of Vector<T> in some places"
3184         https://bugs.webkit.org/show_bug.cgi?id=155150
3185         http://trac.webkit.org/changeset/197722
3186
3187 2016-03-07  Geoffrey Garen  <ggaren@apple.com>
3188
3189         bmalloc: Use List<T> instead of Vector<T> in some places
3190         https://bugs.webkit.org/show_bug.cgi?id=155150
3191
3192         Reviewed by Andreas Kling.
3193
3194         Vector<T> is expensive when you want a lot of them because our minimum
3195         allocation size is the system page size.
3196
3197         * bmalloc.xcodeproj/project.pbxproj: Added a List<T> class.
3198
3199         * bmalloc/Heap.cpp:
3200         (bmalloc::Heap::scavengeSmallPages):
3201         (bmalloc::Heap::allocateSmallPage): Use the List<T> API. No need to check
3202         for stale entries anymore because List<T> supports O(1) eager removal
3203         and we remove eagerly now.
3204
3205         (bmalloc::Heap::deallocateSmallLine): Remove eagerly. This simplifies
3206         the allocation code and it is also required for correctness since we
3207         only have enough metadata to be in one list at a time.
3208
3209         * bmalloc/Heap.h: List!
3210
3211         * bmalloc/SmallChunk.h: Made this assert a little more precise since this
3212         patch triggered the old version in a benign way.
3213
3214         (bmalloc::SmallChunk::SmallChunk): This code moved to the SmallPage
3215         constructor.
3216
3217         * bmalloc/SmallPage.h:
3218         (bmalloc::SmallPage::SmallPage): Accomodate the List<T> data structure.
3219         This is a net memory savings on Mac for heaps smaller than ~128MB and on
3220         iOS for heaps smaller than ~512MB. The maximum memory saved is 512kB on
3221         Mac and 2MB on iOS. For larger heaps, there's a memory cost of 0.4% on
3222         Mac and 0.1% on iOS.
3223
3224         * bmalloc/VMHeap.h:
3225         (bmalloc::VMHeap::allocateSmallPage): Use List<T> API.
3226
3227 2016-03-03  Geoffrey Garen  <ggaren@apple.com>
3228
3229         Unreviewed, rolling in r197174.
3230         https://bugs.webkit.org/show_bug.cgi?id=154762
3231
3232         The right calculation for alignment is actually:
3233
3234             vmAlignment - getpagesize() + vmSize
3235
3236         instead of:
3237
3238             vmAlignment - vmPageSize + vmSize
3239
3240         The vmPageSize might be larger than getpagesize().
3241
3242         Restored changeset:
3243
3244         "bmalloc: Added a fast XLarge allocator"
3245         https://bugs.webkit.org/show_bug.cgi?id=154720
3246         http://trac.webkit.org/changeset/197174
3247
3248 2016-02-26  Commit Queue  <commit-queue@webkit.org>
3249
3250         Unreviewed, rolling out r197174.
3251         https://bugs.webkit.org/show_bug.cgi?id=154762
3252
3253         This change caused LayoutTests to crash on iOS simulator
3254         (Requested by ryanhaddad on #webkit).
3255
3256         Reverted changeset:
3257
3258         "bmalloc: Added a fast XLarge allocator"
3259         https://bugs.webkit.org/show_bug.cgi?id=154720
3260         http://trac.webkit.org/changeset/197174
3261
3262 2016-02-25  Geoffrey Garen  <ggaren@apple.com>
3263
3264         bmalloc: Added a fast XLarge allocator
3265         https://bugs.webkit.org/show_bug.cgi?id=154720
3266
3267         Reviewed by Andreas Kling.
3268
3269         This is a big speedup for XLarge allocations because it avoids mmap
3270         and page fault churn. It also enables future design changes to handle
3271         a smaller size range on the fast path.
3272
3273         * bmalloc.xcodeproj/project.pbxproj:
3274
3275         * bmalloc/Algorithm.h:
3276         (bmalloc::roundUpToMultipleOf):
3277         (bmalloc::roundDownToMultipleOf): Added a non-constant round down.
3278
3279         * bmalloc/Allocator.cpp:
3280         (bmalloc::Allocator::tryAllocate): XLarge no longer requires the caller
3281         to align things.
3282
3283         (bmalloc::Allocator::allocate): Tweaked the alignment calculation for
3284         clarity. When alignment and largeAlignment are equal, no adjustment
3285         is necessary since all allocations guarantee largeAlignment.
3286
3287         (bmalloc::Allocator::reallocate): Updated for interface change.
3288
3289         Note that the new interface fixes some concurrency bugs. The old code
3290         kept an iterator into the XLarge allocator across lock drop and acquisition,
3291         which is not cool.
3292
3293         (bmalloc::Allocator::allocateXLarge): XLarge no longer requires the caller
3294         to align things.
3295
3296         * bmalloc/Heap.cpp:
3297         (bmalloc::Heap::scavengeXLargeObjects): Added scavenging for XLarge.
3298
3299         (bmalloc::Heap::allocateXLarge):
3300
3301         (bmalloc::Heap::splitAndAllocate): Split XLarge objects to xLargeAlignment.
3302
3303         (bmalloc::Heap::tryAllocateXLarge):
3304         (bmalloc::Heap::xLargeSize):
3305         (bmalloc::Heap::shrinkXLarge):
3306         (bmalloc::Heap::deallocateXLarge): Allocate from our map before going
3307         to the OS.
3308
3309         (bmalloc::Heap::findXLarge): Deleted.
3310
3311         * bmalloc/Heap.h:
3312
3313         * bmalloc/LargeObject.h:
3314         (bmalloc::LargeObject::split):
3315
3316         * bmalloc/ObjectType.h:
3317         (bmalloc::isXLarge): Give XLarge objects an explicit alignment for clarity.
3318
3319         * bmalloc/Range.h:
3320         (bmalloc::Range::size):
3321         (bmalloc::Range::operator!):
3322         (bmalloc::Range::operator bool):
3323         (bmalloc::Range::operator<):
3324         (bmalloc::canMerge):
3325         (bmalloc::merge): Some helpers that were useful in writing this patch.
3326
3327         * bmalloc/Sizes.h:
3328
3329         * bmalloc/SortedVector.h: Added.
3330         (bmalloc::SortedVector::Bucket::Bucket):
3331         (bmalloc::SortedVector::Bucket::operator<):
3332         (bmalloc::SortedVector::iterator::iterator):
3333         (bmalloc::SortedVector::iterator::operator++):
3334         (bmalloc::SortedVector::iterator::operator!=):
3335         (bmalloc::SortedVector::iterator::operator*):
3336         (bmalloc::SortedVector::iterator::operator->):
3337         (bmalloc::SortedVector::iterator::skipDeletedBuckets):
3338         (bmalloc::SortedVector::begin):
3339         (bmalloc::SortedVector::end):
3340         (bmalloc::SortedVector<T>::insert):
3341         (bmalloc::SortedVector<T>::find):
3342         (bmalloc::SortedVector<T>::get):
3343         (bmalloc::SortedVector<T>::take):
3344         (bmalloc::SortedVector<T>::shrinkToFit): A simple abstraction for keeping
3345         a sorted vector. Insertion is average amortized log(n) because we keep
3346         deleted buckets that we can reuse.
3347
3348         This is better than a tree because we get better locality, less memory
3349         use, and simpler code. Also, trees require a node memory allocator, and
3350         implementing a memory allocator in a memory allocator is no fun.
3351
3352         Arguably we should use a hash table instead. But that's more code, and
3353         sorted vector has other nice properties that we might want to take
3354         adavantage of in the future.
3355
3356         * bmalloc/VMAllocate.h:
3357         (bmalloc::tryVMAllocate): Fixed an inaccuracy in the alignment calculation
3358         here. This code was sort of trying to enforce the alignment that the
3359         XLarge allocator enforces -- but it's better to enforce that alignment
3360         there.
3361
3362         The right calculation is:
3363
3364             vmAlignment - vmPageSize + vmSize
3365
3366         because the worst case is when you are aligned to 0 + vmPageSize, and
3367         you must walk forward vmAlignment - vmPageSize to reach the next
3368         vmAlignment.
3369
3370         (bmalloc::tryVMExtend): Deleted. No need to go back to the OS for VM
3371         since we manage our own.
3372
3373         * bmalloc/VMHeap.cpp:
3374         (bmalloc::VMHeap::allocateLargeChunk): Updated for clarity. When we
3375         grow the large heap we know that grown region is where the next allocation
3376         will take place, so we return it directly instead of pushing it to the
3377         free list.
3378
3379         This fixes a subtle bug where an overly conservative aligned allocation
3380         algorithm can fail to allocate at all when it grows the heap.
3381
3382         * bmalloc/VMHeap.h:
3383         (bmalloc::VMHeap::allocateLargeObject): Ditto.
3384         (bmalloc::VMHeap::allocateLargeObject): Ditto.
3385
3386         * bmalloc/VMState.h:
3387         (bmalloc::merge): Added a helper.
3388
3389         * bmalloc/Vector.h:
3390         (bmalloc::Vector::begin):
3391         (bmalloc::Vector::end):
3392         (bmalloc::Vector::size):
3393         (bmalloc::Vector::capacity):
3394         (bmalloc::Vector::last):
3395         (bmalloc::Vector::pop):
3396         (bmalloc::Vector<T>::push):
3397         (bmalloc::Vector<T>::pop):
3398         (bmalloc::Vector<T>::shrink): Use a proper iterator API to play nice
3399         with std algorithms.
3400
3401         (bmalloc::Vector<T>::insert): New function required by SortedVector.
3402
3403         (bmalloc::Vector<T>::reallocateBuffer):
3404         (bmalloc::Vector<T>::shrinkCapacity): Allow for shrinking back all the way
3405         to 0 because that's what shrinkToFit wants.
3406         (bmalloc::Vector<T>::growCapacity):
3407         (bmalloc::Vector<T>::shrinkToFit):
3408
3409         * bmalloc/XLargeMap.cpp: Added. Helper data structure for managing XLarge
3410         objects. We have enough granularity in our metadata to represent any
3411         kind of address range.
3412
3413         We store free ranges in a flat vector because most programs have very
3414         few individual free XLarge ranges. (They usually merge.)
3415
3416         We store allocated ranges in a sorted vector because programs might
3417         allocate lots of XLarge ranges. For example, if the XLarge minimum is
3418         128kB, and you have a 1GB process, that's 8192 ranges. Linear scan would
3419         examine 8192 items but binary search only 13.
3420
3421         Empirically, this is 1.5X faster than our current large allocator if you