Source/bmalloc/ChangeLog

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