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