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