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