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