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