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