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