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