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