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