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