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