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