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