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