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