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