Source/bmalloc/ChangeLog

   1 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
   2
   3         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
   4         https://bugs.webkit.org/show_bug.cgi?id=141802
   5
   6         Reviewed by Andreas Kling.
   7
   8         Rolling back in but disabled on iOS until I can debug why the iOS PLT crashes.
   9
  10         * bmalloc/VMHeap.cpp:
  11         (bmalloc::VMHeap::grow):
  12         * bmalloc/VMHeap.h:
  13         * bmalloc/Zone.cpp:
  14         (bmalloc::Zone::size):
  15         (bmalloc::Zone::Zone):
  16         * bmalloc/Zone.h:
  17
  18 2015-03-03  Geoffrey Garen  <ggaren@apple.com>
  19
  20         bmalloc: Miscellaneous cleanup
  21         https://bugs.webkit.org/show_bug.cgi?id=142231
  22
  23         Reviewed by Andreas Kling.
  24
  25         No performance change -- maybe a tiny reduction in memory use.
  26
  27         * bmalloc/Heap.cpp: Moved the sleep function into StaticMutex, since
  28         it's a helper for working with mutexes.
  29
  30         (bmalloc::Heap::scavenge): Make sure to wait before we start any
  31         scavenging, since individual scavenging functions now always scavenge
  32         at least one page before waiting themselves.
  33
  34         (bmalloc::Heap::scavengeSmallPages):
  35         (bmalloc::Heap::scavengeMediumPages):
  36         (bmalloc::Heap::scavengeLargeObjects): Use the new wait helper to
  37         simplify this code. Also, we now require our caller to wait until at
  38         least one deallocation is desirable. This simplifies our loop.
  39
  40         (bmalloc::Heap::allocateSmallPage):
  41         (bmalloc::Heap::allocateMediumPage):
  42         (bmalloc::Heap::allocateXLarge):
  43         (bmalloc::Heap::allocateLarge): Don't freak out any time the heap does
  44         an allocation. Only consider the heap to be growing if it actually needs
  45         to allocate new VM. This allows us to shrink the heap back down from a
  46         high water mark more reliably even if heap activity continues.
  47
  48         (bmalloc::sleep): Deleted.
  49         (bmalloc::Heap::scavengeLargeRanges): Renamed to match our use of
  50         "LargeObject".
  51
  52         * bmalloc/Heap.h:
  53
  54         * bmalloc/LargeObject.h:
  55         (bmalloc::LargeObject::operator bool): Added to simplify a while loop.
  56
  57         * bmalloc/StaticMutex.h:
  58         (bmalloc::sleep):
  59         (bmalloc::waitUntilFalse): New helper for waiting until a condition
  60         becomes reliably false.
  61
  62         * bmalloc/Vector.h:
  63         (bmalloc::Vector<T>::~Vector): Oops! Don't deallocate the null pointer.
  64         We don't actually run any Vector destructors, but an iteration of this
  65         patch did, and then crashed. So, let's fix that.
  66
  67 2015-03-02  Geoffrey Garen  <ggaren@apple.com>
  68
  69         bmalloc: Eagerly remove allocated objects from the free list
  70         https://bugs.webkit.org/show_bug.cgi?id=142194
  71
  72         Reviewed by Andreas Kling.
  73
  74         This reduces the pressure to garbage collect the free list.
  75
  76         Might be a 1% speedup on MallocBench.
  77
  78         * bmalloc/FreeList.cpp: Put this comment at the top of the file instead
  79         of repeating it inside of each function. Tried to clarify the details.
  80
  81         (bmalloc::FreeList::takeGreedy): Matched the other iteration code in this
  82         file for consistency -- even though either direction works fine in this
  83         function.
  84
  85         (bmalloc::FreeList::take): Change to iterate from low to high so that we
  86         can maintain an index into the vector that is not disturbed even if we
  87         pop from the middle (which invalidates the last index in the vector).
  88
  89         Decrement i when popping from the middle to make sure that we don't
  90         skip the next item after popping.
  91
  92         (bmalloc::FreeList::removeInvalidAndDuplicateEntries): Ditto.
  93
  94 2015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
  95
  96         Fixed a typo in the previous commit.
  97
  98         * bmalloc/BoundaryTag.h:
  99         (bmalloc::BoundaryTag::setOwner):
 100
 101 2015-02-27  Ryosuke Niwa  <rniwa@webkit.org>
 102
 103         EFL build fix after r180797.
 104
 105         * bmalloc/BoundaryTag.h:
 106         (bmalloc::BoundaryTag::owner):
 107         (bmalloc::BoundaryTag::setOwner):
 108
 109 2015-02-27  Geoffrey Garen  <ggaren@apple.com>
 110
 111         bmalloc: Pathological madvise churn on the free(malloc(x)) benchmark
 112         https://bugs.webkit.org/show_bug.cgi?id=142058
 113
 114         Reviewed by Andreas Kling.
 115
 116         The churn was caused by repeatedly splitting an object with physical
 117         pages from an object without, and then merging them back together again.
 118         The merge would conservatively forget that we had physical pages, forcing
 119         a new call to madvise on the next allocation.
 120
 121         This patch more strictly segregates objects in the heap from objects in
 122         the VM heap, with these changes:
 123
 124         (1) Objects in the heap are not allowed to merge with objects in the VM
 125         heap, and vice versa -- since that would erase our precise knowledge of
 126         which physical pages had been allocated.
 127
 128         (2) The VM heap is exclusively responsible for allocating and deallocating
 129         physical pages.
 130
 131         (3) The heap free list must consider entries for objects that are in the
 132         VM heap to be invalid, and vice versa. (This condition can arise
 133         because the free list does not eagerly remove items.)
 134
 135         With these changes, we can know that any valid object in the heap's free
 136         list already has physical pages, and does not need to call madvise.
 137
 138         Note that the VM heap -- as before -- might sometimes contain ranges
 139         or pieces of ranges that have physical pages, since we allow splitting
 140         of ranges at granularities smaller than the VM page size. These ranges
 141         can eventually merge with ranges in the heap during scavenging.
 142
 143         * bmalloc.xcodeproj/project.pbxproj:
 144
 145         * bmalloc/BoundaryTag.h:
 146         (bmalloc::BoundaryTag::owner):
 147         (bmalloc::BoundaryTag::setOwner):
 148         (bmalloc::BoundaryTag::initSentinel):
 149         (bmalloc::BoundaryTag::hasPhysicalPages): Deleted.
 150         (bmalloc::BoundaryTag::setHasPhysicalPages): Deleted. Replaced the concept
 151         of "has physical pages" with a bit indicating which heap owns the large
 152         object. This is a more precise concept, since the old bit was really a
 153         Yes / Maybe bit.
 154
 155         * bmalloc/Deallocator.cpp:
 156
 157         * bmalloc/FreeList.cpp: Adopt
 158         (bmalloc::FreeList::takeGreedy):
 159         (bmalloc::FreeList::take):
 160         (bmalloc::FreeList::removeInvalidAndDuplicateEntries):
 161         * bmalloc/FreeList.h:
 162         (bmalloc::FreeList::push): Added API for considering the owner when
 163         deciding if a free list entry is valid.
 164
 165         * bmalloc/Heap.cpp:
 166         (bmalloc::Heap::Heap): Adopt new API.
 167
 168         (bmalloc::Heap::scavengeLargeRanges): Scavenge all ranges with no minimum,
 169         since some ranges might be able to merge with ranges in the VM heap, and
 170         they won't be allowed to until we scavenge them.
 171
 172         (bmalloc::Heap::allocateSmallPage):
 173         (bmalloc::Heap::allocateMediumPage):
 174         (bmalloc::Heap::allocateLarge): New VM heap API makes this function
 175         simpler, since we always get back physical pages now.
 176
 177         * bmalloc/Heap.h:
 178         * bmalloc/LargeObject.h:
 179         (bmalloc::LargeObject::end):
 180         (bmalloc::LargeObject::owner):
 181         (bmalloc::LargeObject::setOwner):
 182         (bmalloc::LargeObject::isValidAndFree):
 183         (bmalloc::LargeObject::merge): Do not merge objects across heaps since
 184         that causes madvise churn.
 185         (bmalloc::LargeObject::validateSelf):
 186         (bmalloc::LargeObject::init):
 187         (bmalloc::LargeObject::hasPhysicalPages): Deleted.
 188         (bmalloc::LargeObject::setHasPhysicalPages): Deleted. Propogate the Owner API.
 189
 190         * bmalloc/Owner.h: Added.
 191
 192         * bmalloc/SegregatedFreeList.cpp:
 193         (bmalloc::SegregatedFreeList::SegregatedFreeList):
 194         (bmalloc::SegregatedFreeList::insert):
 195         (bmalloc::SegregatedFreeList::takeGreedy):
 196         (bmalloc::SegregatedFreeList::take):
 197         * bmalloc/SegregatedFreeList.h: Propogate the owner API.
 198
 199         * bmalloc/VMAllocate.h:
 200         (bmalloc::vmDeallocatePhysicalPagesSloppy):
 201         (bmalloc::vmAllocatePhysicalPagesSloppy): Clarified these functions and
 202         removed an edge case.
 203
 204         * bmalloc/VMHeap.cpp:
 205         (bmalloc::VMHeap::VMHeap):
 206         * bmalloc/VMHeap.h:
 207         (bmalloc::VMHeap::allocateSmallPage):
 208         (bmalloc::VMHeap::allocateMediumPage):
 209         (bmalloc::VMHeap::allocateLargeObject):
 210         (bmalloc::VMHeap::deallocateLargeObject): Be sure to give each object
 211         a new chance to merge, since it might have been prohibited from merging
 212         before by virtue of not being in the VM heap.
 213
 214         (bmalloc::VMHeap::allocateLargeRange): Deleted.
 215         (bmalloc::VMHeap::deallocateLargeRange): Deleted.
 216
 217 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
 218
 219         bmalloc: Large object free list can grow infinitely
 220         https://bugs.webkit.org/show_bug.cgi?id=142055
 221
 222         Reviewed by Andreas Kling.
 223
 224         By design, we don't eagerly remove large objects from the free list.
 225         This creates two simple pathologies:
 226
 227             (1) If you free and then allocate the same object repeatedly, it will
 228             duplicate itself in the free list repeatedly. Since it is never
 229             invalid at the time of allocation, it will never be removed.
 230
 231             (2) If you split and then merge the same object repeatedly, it will
 232             duplicate its split sibling in the free list repeatedly. If its
 233             sibling is in a separate free list size class, it will never be
 234             consulted at the time of allocation, so it will never be removed.
 235
 236         So, a simple "while (1) { free(malloc(x)); }" causes infinite memory
 237         use in the free list.
 238
 239         The solution in this patch is a simple helper to remove garbage from the
 240         free list if it grows too large. This pathology is not common, so the
 241         cost is OK.
 242
 243         Long-term, perhaps we should rethink the laziness of these free lists.
 244
 245         * bmalloc/BoundaryTag.h:
 246         (bmalloc::BoundaryTag::isMarked):
 247         (bmalloc::BoundaryTag::setMarked): New bit, used by free list GC.
 248
 249         * bmalloc/FreeList.cpp:
 250         (bmalloc::FreeList::removeInvalidAndDuplicateEntries): The GC algorithm.
 251
 252         * bmalloc/FreeList.h:
 253         (bmalloc::FreeList::FreeList):
 254         (bmalloc::FreeList::push): Invoke the GC if we're getting huge.
 255
 256         * bmalloc/LargeObject.h:
 257         (bmalloc::LargeObject::isMarked):
 258         (bmalloc::LargeObject::setMarked):
 259         (bmalloc::LargeObject::validateSelf): Expose the new bit.
 260
 261         * bmalloc/Sizes.h: New constant to control GC frequency.
 262
 263 2015-02-26  Csaba Osztrogonác  <ossy@webkit.org>
 264
 265         URTBF after r180693.
 266
 267         * CMakeLists.txt:
 268
 269 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
 270
 271         Try to fix the Mac build.
 272
 273         Unreviewed.
 274
 275         * bmalloc.xcodeproj/project.pbxproj: Make FreeList.h available.
 276
 277 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
 278
 279         bmalloc: Refactored SegregatedFreeList and BoundaryTag::init
 280         https://bugs.webkit.org/show_bug.cgi?id=142049
 281
 282         Reviewed by Anders Carlsson.
 283
 284         Split out a FreeList class from SegregatedFreeList. This will make it
 285         easier to add behaviors on free list insertion and removal -- and it's
 286         probably how I should have designed things at the start.
 287
 288         Moved BoundaryTag::init into LargeObject, since all the related logic
 289         lives in LargeObject now too, and this allows us to remove BoundaryTagInlines.h.
 290
 291         * bmalloc.xcodeproj/project.pbxproj:
 292         * bmalloc/BoundaryTagInlines.h: Removed.
 293         * bmalloc/FreeList.cpp: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.cpp.
 294         (bmalloc::FreeList::takeGreedy):
 295         (bmalloc::FreeList::take):
 296         (bmalloc::SegregatedFreeList::SegregatedFreeList): Deleted.
 297         (bmalloc::SegregatedFreeList::insert): Deleted.
 298         (bmalloc::SegregatedFreeList::takeGreedy): Deleted.
 299         (bmalloc::SegregatedFreeList::take): Deleted.
 300         * bmalloc/FreeList.h: Copied from Source/bmalloc/bmalloc/SegregatedFreeList.h.
 301         (bmalloc::FreeList::push):
 302         * bmalloc/LargeObject.h:
 303         (bmalloc::LargeObject::init):
 304         * bmalloc/SegregatedFreeList.cpp:
 305         (bmalloc::SegregatedFreeList::SegregatedFreeList):
 306         (bmalloc::SegregatedFreeList::insert):
 307         (bmalloc::SegregatedFreeList::takeGreedy):
 308         (bmalloc::SegregatedFreeList::take):
 309         * bmalloc/SegregatedFreeList.h:
 310         * bmalloc/Sizes.h:
 311         * bmalloc/VMHeap.cpp:
 312         (bmalloc::VMHeap::grow):
 313
 314 2015-02-26  Geoffrey Garen  <ggaren@apple.com>
 315
 316         bmalloc: free up a bit in BoundaryTag
 317         https://bugs.webkit.org/show_bug.cgi?id=142048
 318
 319         Reviewed by Brady Eidson.
 320
 321         We were wasting a bit by accident, and I need one now.
 322
 323         * bmalloc/Algorithm.h:
 324         (bmalloc::rightShift): Deleted. Not needed, now that I've simplified
 325         the math.
 326
 327         * bmalloc/BoundaryTag.h: Since each boundary tag bucket is 1024 bytes
 328         long, the maximum offset into a bucket is 1023.
 329
 330         You need 5 bits to count up to 1024, but only 4 to count up to 1023.
 331
 332         Math is hard.
 333
 334         (bmalloc::BoundaryTag::compactBegin): Switched to division because it
 335         is simpler, and easier to match up with our ASSERT. The compiler will
 336         turn division by constant power of two into a shift for us.
 337
 338         (bmalloc::BoundaryTag::setRange): Added an ASSERT for compactBegin
 339         because we do encode it, so we should ASSERT that encoding did not
 340         lose information.
 341
 342         * bmalloc/Sizes.h: Shifting is no longer used since we use division
 343         instead.
 344
 345 2015-02-24  Stephanie Lewis  <slewis@apple.com>
 346
 347         Rolling out http://trac.webkit.org/changeset/180430 as it causes the PLT to crash.
 348         <rdar://problem/19948015>
 349
 350         Unreviewed.
 351
 352         * bmalloc/VMHeap.cpp:
 353         (bmalloc::VMHeap::grow):
 354         * bmalloc/VMHeap.h:
 355         * bmalloc/Zone.cpp:
 356         (bmalloc::Zone::Zone):
 357         (bmalloc::Zone::size): Deleted.
 358         * bmalloc/Zone.h:
 359
 360 2015-02-24  Geoffrey Garen  <ggaren@apple.com>
 361
 362         bmalloc: Added a little more abstraction for large objects
 363         https://bugs.webkit.org/show_bug.cgi?id=141978
 364
 365         Reviewed by Sam Weinig.
 366
 367         Previously, each client needed to manage the boundary tags of
 368         a large object using free functions. This patch introduces a LargeObject
 369         class that does things a little more automatically.
 370
 371         * bmalloc.xcodeproj/project.pbxproj:
 372
 373         * bmalloc/Allocator.cpp:
 374         (bmalloc::Allocator::reallocate): Use the new LargeObject class.
 375
 376         * bmalloc/BeginTag.h:
 377         (bmalloc::BeginTag::isInFreeList): Deleted. Moved this logic into the
 378         LargeObject class.
 379
 380         * bmalloc/BoundaryTag.h:
 381         (bmalloc::BoundaryTag::isSentinel):
 382         (bmalloc::BoundaryTag::compactBegin):
 383         (bmalloc::BoundaryTag::setRange):
 384         (bmalloc::BoundaryTag::initSentinel): Added an explicit API for sentinels,
 385         which we used to create and test for implicitly.
 386
 387         * bmalloc/BoundaryTagInlines.h:
 388         (bmalloc::BoundaryTag::init):
 389         (bmalloc::validate): Deleted.
 390         (bmalloc::validatePrev): Deleted.
 391         (bmalloc::validateNext): Deleted.
 392         (bmalloc::BoundaryTag::mergeLeft): Deleted.
 393         (bmalloc::BoundaryTag::mergeRight): Deleted.
 394         (bmalloc::BoundaryTag::merge): Deleted.
 395         (bmalloc::BoundaryTag::deallocate): Deleted.
 396         (bmalloc::BoundaryTag::split): Deleted.
 397         (bmalloc::BoundaryTag::allocate): Deleted. Moved this logic into the
 398         LargeObject class.
 399
 400         * bmalloc/EndTag.h:
 401         (bmalloc::EndTag::init):
 402         (bmalloc::EndTag::operator=): Deleted. Re-reading this code, I found
 403         special behavior in the assignment operator to be a surprising API.
 404         So, I replaced the assignment operation with an explicit initializing
 405         function.
 406
 407         * bmalloc/Heap.cpp:
 408         (bmalloc::Heap::scavengeLargeRanges):
 409         (bmalloc::Heap::allocateXLarge):
 410         (bmalloc::Heap::findXLarge):
 411         (bmalloc::Heap::deallocateXLarge):
 412         (bmalloc::Heap::allocateLarge):
 413         (bmalloc::Heap::deallocateLarge):
 414         * bmalloc/Heap.h: No behavior changes here -- just adopting the
 415         LargeObject interface.
 416
 417         * bmalloc/LargeObject.h: Added.
 418         (bmalloc::LargeObject::operator!):
 419         (bmalloc::LargeObject::begin):
 420         (bmalloc::LargeObject::size):
 421         (bmalloc::LargeObject::range):
 422         (bmalloc::LargeObject::LargeObject):
 423         (bmalloc::LargeObject::setFree):
 424         (bmalloc::LargeObject::isFree):
 425         (bmalloc::LargeObject::hasPhysicalPages):
 426         (bmalloc::LargeObject::setHasPhysicalPages):
 427         (bmalloc::LargeObject::isValidAndFree):
 428         (bmalloc::LargeObject::merge):
 429         (bmalloc::LargeObject::split):
 430         (bmalloc::LargeObject::validateSelf):
 431         (bmalloc::LargeObject::validate): Moved this code into a class, out of
 432         BoundaryTag free functions.
 433
 434         New to the class are these features:
 435
 436             (1) Every reference to an object is validated upon creation and use.
 437
 438             (2) There's an explicit API for "This is a reference to an object
 439             that might be stale (the DoNotValidate API)".
 440
 441             (3) The begin and end tags are kept in sync automatically.
 442
 443         * bmalloc/SegregatedFreeList.cpp:
 444         (bmalloc::SegregatedFreeList::insert):
 445         (bmalloc::SegregatedFreeList::takeGreedy):
 446         (bmalloc::SegregatedFreeList::take):
 447         * bmalloc/SegregatedFreeList.h: Adopt the LargeObject interface.
 448
 449         * bmalloc/VMHeap.cpp:
 450         (bmalloc::VMHeap::grow):
 451         * bmalloc/VMHeap.h:
 452         (bmalloc::VMHeap::allocateLargeRange):
 453         (bmalloc::VMHeap::deallocateLargeRange): Adopt the LargeObject interface.
 454
 455 2015-02-20  Geoffrey Garen  <ggaren@apple.com>
 456
 457         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
 458         https://bugs.webkit.org/show_bug.cgi?id=141802
 459
 460         Reviewed by Andreas Kling.
 461
 462         Rolling back in with a fix for a crash seen while using GuardMalloc.
 463
 464         * bmalloc/VMHeap.cpp:
 465         (bmalloc::VMHeap::grow):
 466         * bmalloc/VMHeap.h:
 467         * bmalloc/Zone.cpp: Re-land the old patch.
 468
 469         (bmalloc::Zone::size): Be sure to implement the size() function since
 470         it's accessible indirectly via the malloc_zone_from_ptr public API --
 471         and GuardMalloc calls it all the time.
 472
 473         (bmalloc::Zone::Zone):
 474         * bmalloc/Zone.h: Re-land the old patch.
 475
 476 2015-02-19  Commit Queue  <commit-queue@webkit.org>
 477
 478         Unreviewed, rolling out r180363.
 479         https://bugs.webkit.org/show_bug.cgi?id=141814
 480
 481         Caused >50 crashes when running LayoutTests in GuardMalloc or
 482         ASAN modes. (Requested by jernoble on #webkit).
 483
 484         Reverted changeset:
 485
 486         "bmalloc should implement malloc introspection (to stop false-
 487         positive leaks when MallocStackLogging is off)"
 488         https://bugs.webkit.org/show_bug.cgi?id=141802
 489         http://trac.webkit.org/changeset/180363
 490
 491 2015-02-19  Geoffrey Garen  <ggaren@apple.com>
 492
 493         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
 494         https://bugs.webkit.org/show_bug.cgi?id=141802
 495
 496         Reviewed by Andreas Kling.
 497
 498         Fixed a last-minute type.
 499
 500         The macro is OS, not PLATFORM.
 501
 502         * bmalloc/VMHeap.cpp:
 503         (bmalloc::VMHeap::grow):
 504         * bmalloc/VMHeap.h:
 505         * bmalloc/Zone.h:
 506
 507 2015-02-19  Geoffrey Garen  <ggaren@apple.com>
 508
 509         bmalloc should implement malloc introspection (to stop false-positive leaks when MallocStackLogging is off)
 510         https://bugs.webkit.org/show_bug.cgi?id=141802
 511
 512         Reviewed by Andreas Kling.
 513
 514         This patch does the bare minimum to stop false positive leaks from
 515         being reported by the Darwin leaks tool. We register each super chunk
 516         as a single object, and then request that the leaks tool scan it.
 517
 518         * bmalloc.xcodeproj/project.pbxproj: Added an abstraction for the malloc
 519         zone introspection API.
 520
 521         * bmalloc/Algorithm.h: Missing #include.
 522
 523         * bmalloc/VMHeap.cpp:
 524         (bmalloc::VMHeap::grow):
 525         * bmalloc/VMHeap.h: Adopt the new abstraction.
 526
 527         * bmalloc/Zone.cpp: Added.
 528         (bmalloc::remoteRead): Helper for reading an object out of another process.
 529         (bmalloc::Zone::enumerator):
 530         (bmalloc::Zone::Zone): Register a malloc zone so that we will participate
 531         in introspection.
 532
 533         * bmalloc/Zone.h: Added.
 534         (bmalloc::Zone::superChunks):
 535         (bmalloc::Zone::addSuperChunk): Use a non-dynamically-allocated vector
 536         since our dynamic allocations will not be scanned by leaks since they
 537         will have the malloc VM tag.
 538
 539 2015-02-18  Geoffrey Garen  <ggaren@apple.com>
 540
 541         bmalloc: VMHeap should keep a record of all of its VM ranges (for malloc introspection)
 542         https://bugs.webkit.org/show_bug.cgi?id=141759
 543
 544         Reviewed by Andreas Kling.
 545
 546         * bmalloc.xcodeproj/project.pbxproj:
 547         * bmalloc/SuperChunk.h: Added.
 548         (bmalloc::SuperChunk::create):
 549         (bmalloc::SuperChunk::SuperChunk):
 550         (bmalloc::SuperChunk::smallChunk):
 551         (bmalloc::SuperChunk::mediumChunk):
 552         (bmalloc::SuperChunk::largeChunk): Factored out super chunk creation
 553         into a separate class, for clarity and type safety.
 554
 555         * bmalloc/VMHeap.cpp:
 556         (bmalloc::VMHeap::grow):
 557         (bmalloc::VMHeap::allocateSuperChunk): Renamed "allocateSuperChunk" to
 558         "grow" because Andreas found "allocateSuperChunk" to be unclear.
 559
 560         * bmalloc/VMHeap.h: Track all our VM ranges. We will use this information
 561         for malloc introspection.
 562
 563         (bmalloc::VMHeap::allocateSmallPage):
 564         (bmalloc::VMHeap::allocateMediumPage):
 565         (bmalloc::VMHeap::allocateLargeRange): Updated for renames.
 566
 567 2015-02-18  Zan Dobersek  <zdobersek@igalia.com>
 568
 569         Build bmalloc through CMake as a static library. It's then linked either
 570         into the WTF library (if built as a shared library) or into the JSC and
 571         WebKit2 libraries. There's no need to build it as a standalone shared library.
 572
 573         Rubber-stamped by Carlos Garcia Campos.
 574
 575         * CMakeLists.txt:
 576
 577 2015-02-13  Gyuyoung Kim  <gyuyoung.kim@samsung.com>
 578
 579         [BMalloc] Add a FIXME comment for memory alignas
 580         https://bugs.webkit.org/show_bug.cgi?id=141556
 581
 582         Reviewed by Csaba Osztrogonác.
 583
 584         * bmalloc/Chunk.h: Add a FIXME comment.
 585         * bmalloc/LargeChunk.h: ditto.
 586
 587 2015-02-11  Csaba Osztrogonác  <ossy@webkit.org>
 588
 589         bmalloc buildfix on 32 bit Linux (x86/ARM)
 590         https://bugs.webkit.org/show_bug.cgi?id=141472
 591
 592         Reviewed by Gyuyoung Kim.
 593
 594         * bmalloc/Algorithm.h:
 595         (bmalloc::roundUpToMultipleOf):
 596         * bmalloc/FixedVector.h:
 597         (bmalloc::FixedVector::clear):
 598         * bmalloc/Sizes.h:
 599         (bmalloc::Sizes::sizeClass):
 600
 601 2015-02-11  Gyuyoung Kim  <gyuyoung.kim@samsung.com>
 602
 603         [EFL][GTK] Use bmalloc instead of tcmalloc
 604         https://bugs.webkit.org/show_bug.cgi?id=140162
 605
 606         Reviewed by Carlos Garcia Campos.
 607
 608         Support to use bmalloc on EFL and GTK ports.
 609
 610         * CMakeLists.txt: Added.
 611         * bmalloc/Allocator.cpp:
 612         (bmalloc::Allocator::allocate):
 613             Fix unused return value caused by posix_memalign().
 614         * bmalloc/AsyncTask.h:
 615         * bmalloc/BoundaryTag.h:
 616         (bmalloc::BoundaryTag::clear):
 617         * bmalloc/Chunk.h:
 618             Change Traits::Page with Traits::PageType in order to fix
 619             -fpermitive build error on EFL and GTK port.
 620         * bmalloc/EndTag.h:
 621         (bmalloc::EndTag::operator=):
 622         * bmalloc/Line.h: ditto.
 623         * bmalloc/MediumTraits.h:
 624         * bmalloc/Page.h: ditto.
 625         * bmalloc/PerThread.h:
 626             EFL port doesn't support __has_include definition yet.
 627             Define HAVE_PTHREAD_MACHDEP_H according to check if __has_include is supported.
 628         * bmalloc/SmallTraits.h: ditto.
 629         * bmalloc/VMAllocate.h:
 630         (bmalloc::vmDeallocatePhysicalPages):
 631         (bmalloc::vmAllocatePhysicalPages):
 632         * bmalloc/Vector.h:
 633         (bmalloc::Vector<T>::push):
 634         (bmalloc::Vector<T>::reallocateBuffer):
 635
 636 2015-01-31  Sam Weinig  <sam@webkit.org>
 637
 638         Remove even more Mountain Lion support
 639         https://bugs.webkit.org/show_bug.cgi?id=141124
 640
 641         Reviewed by Alexey Proskuryakov.
 642
 643         * Configurations/Base.xcconfig:
 644         * Configurations/DebugRelease.xcconfig:
 645
 646 2015-01-30  Geoffrey Garen  <ggaren@apple.com>
 647
 648         GC marking threads should clear malloc caches
 649         https://bugs.webkit.org/show_bug.cgi?id=141097
 650
 651         Reviewed by Andreas Kling.
 652
 653         Split the scavenging API into per-thread vs global, so that you can
 654         request to scavenge your own thread without scavenging the whole heap.
 655
 656         * bmalloc/Cache.cpp:
 657         (bmalloc::Cache::scavenge):
 658         * bmalloc/bmalloc.h:
 659         (bmalloc::api::scavengeThisThread):
 660         (bmalloc::api::scavenge):
 661
 662 2015-01-28  Dana Burkart  <dburkart@apple.com>
 663
 664         Move ASan flag settings from DebugRelease.xcconfig to Base.xcconfig
 665         https://bugs.webkit.org/show_bug.cgi?id=136765
 666
 667         Reviewed by Alexey Proskuryakov.
 668
 669         * Configurations/Base.xcconfig:
 670         * Configurations/DebugRelease.xcconfig:
 671
 672 2015-01-21  Geoffrey Garen  <ggaren@apple.com>
 673
 674         bmalloc: support aligned allocation
 675         https://bugs.webkit.org/show_bug.cgi?id=140732
 676
 677         Reviewed by Andreas Kling.
 678
 679         * bmalloc/Allocator.cpp:
 680         (bmalloc::Allocator::allocate): New function for aligned allocation.
 681
 682         Small and medium requests just allocate and free until they find an
 683         aligned pointer. This is slightly inefficient in the worst case, but
 684         still constant-time with little-to-no space overhead.
 685
 686         Large requests use a new API that requires the client to specify both
 687         its ideal size and alignment, and the worst-case size you would have to
 688         allocate in order to produce some interior pointer of the requested size
 689         and alignment. We put the burden of this calculation on the client
 690         because it simplifies things if we guarantee that allocation won't fail.
 691
 692         XLarge requests are easy: we just forward them to vmAllocate, which
 693         already supported aligned requests.
 694
 695         * bmalloc/BoundaryTag.h:
 696         * bmalloc/BoundaryTagInlines.h:
 697         (bmalloc::BoundaryTag::mergeLeft):
 698         (bmalloc::BoundaryTag::mergeRight):
 699         (bmalloc::BoundaryTag::merge):
 700         (bmalloc::BoundaryTag::deallocate):
 701         (bmalloc::BoundaryTag::split):
 702         (bmalloc::BoundaryTag::allocate): No behavior change here. I just
 703         refactored the interface to remove some reference out parameters in
 704         order to clarify what changes and what doesn't.
 705
 706         * bmalloc/Heap.cpp:
 707         (bmalloc::Heap::allocateXLarge): Added an alignment API.
 708
 709         (bmalloc::Heap::allocateLarge):
 710         * bmalloc/Heap.h: Added an alignment API. I split out allocateLarge into
 711         a few variants, so aligned and unaligned allocation could share some code.
 712
 713         * bmalloc/SegregatedFreeList.cpp:
 714         (bmalloc::SegregatedFreeList::take):
 715         * bmalloc/SegregatedFreeList.h: Changed to use a separate, explicit API
 716         for aligned allocation. It turns out that the aligned path is pretty
 717         different, since it ends up searching for two potential ways to satisfy
 718         an allocation: either large enough and aligned, or large enough to split
 719         into something not aligned and something large enough and aligned.
 720
 721         * bmalloc/VMAllocate.h:
 722         (bmalloc::vmAllocate): Switched alignment to come before size because
 723         that's how the memalign API specifies it.
 724
 725         * bmalloc/VMHeap.h:
 726         (bmalloc::VMHeap::allocateLargeRange): Added an alignment API.
 727
 728 2015-01-20  Geoffrey Garen  <ggaren@apple.com>
 729
 730         bmalloc: a little bit of cleanup
 731         https://bugs.webkit.org/show_bug.cgi?id=140687
 732
 733         Reviewed by Anders Carlsson.
 734
 735         * bmalloc/Algorithm.h:
 736         (bmalloc::isPowerOfTwo): Added a check for 0, since 0 would break a lot
 737         of code.
 738
 739         * bmalloc/BoundaryTag.h:
 740         * bmalloc/BoundaryTagInlines.h:
 741         (bmalloc::BoundaryTag::mergeLeft):
 742         (bmalloc::BoundaryTag::mergeRight):
 743         (bmalloc::BoundaryTag::merge):
 744         (bmalloc::BoundaryTag::deallocate):
 745         (bmalloc::BoundaryTag::split):
 746         (bmalloc::BoundaryTag::allocate):
 747         (bmalloc::BoundaryTag::mergeLargeLeft): Deleted.
 748         (bmalloc::BoundaryTag::mergeLargeRight): Deleted.
 749         (bmalloc::BoundaryTag::mergeLarge): Deleted.
 750         (bmalloc::BoundaryTag::splitLarge): Deleted. Removed the word "Large"
 751         from all these functions, since boundary tags always pertain to large
 752         objects, and putting the word "Large" everywhere wasn't helping to
 753         explain that.
 754
 755         * bmalloc/Heap.cpp:
 756         (bmalloc::Heap::allocateXLarge):
 757         (bmalloc::Heap::findXLarge):
 758         (bmalloc::Heap::deallocateXLarge):
 759         * bmalloc/Heap.h:
 760         * bmalloc/VMHeap.h:
 761         (bmalloc::VMHeap::allocateXLarge): Deleted.
 762         (bmalloc::VMHeap::findXLarge): Deleted.
 763         (bmalloc::VMHeap::deallocateXLarge): Deleted. Moved XLarge allocation
 764         from VMHeap to Heap. Since the purpose of the VMHeap is to cache VM
 765         ranges, and the VMHeap never caches any XLarge ranges, it doesn't
 766         really make sense for the VMHeap to be involved.
 767
 768 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
 769
 770         bmalloc: refactored XLarge allocation for better alignment
 771         https://bugs.webkit.org/show_bug.cgi?id=140582
 772
 773         Reviewed by Andreas Kling.
 774
 775         XLarge objects used to be Large objects with an extra bit of metadata
 776         that said "actually, I'm not large -- I'm extra large".
 777
 778         The metadata header in an XLarge allocation made it impossible for the
 779         XLarge object to honor a very large alignment request.
 780
 781         The solution is to stop using a metadata header for XLarge objects, and
 782         instead to store explicit metadata on the side.
 783
 784         This is a bit less astonishing, which is also nice.
 785
 786         Finding XLarge metadata is now a linear search. That's probably OK, since
 787         it was always so in TCMalloc, and the usual number of XLarge allocations
 788         in a process is 0.
 789
 790         This design makes it possible for the heap to cache XLarge allocations
 791         with and/or without physical pages. I haven't actually done that yet
 792         because the tradeoffs are subtle, so I don't want to do anything without
 793         a motivating test case.
 794
 795         * bmalloc.xcodeproj/project.pbxproj:
 796         * bmalloc/Allocator.cpp:
 797         (bmalloc::Allocator::reallocate): Removed the concept of an XLargeChunk,
 798         since an XLarge allocation is now just a naked buffer without a header.
 799
 800         (bmalloc::Allocator::allocateXLarge): Added an explicit qualifier for
 801         XLarge alignment, since XLargeChunk won't give this to us implicitly
 802         anymore.
 803
 804         * bmalloc/BoundaryTag.h:
 805         (bmalloc::BoundaryTag::setRange):
 806         (bmalloc::BoundaryTag::isXLarge): Deleted.
 807         (bmalloc::BoundaryTag::setXLarge): Deleted.
 808         * bmalloc/BoundaryTagInlines.h:
 809         (bmalloc::validate):
 810         (bmalloc::BoundaryTag::deallocate): Removed the XLarge hacks from Large allocations.
 811
 812         * bmalloc/Deallocator.cpp:
 813         (bmalloc::Deallocator::deallocateXLarge):
 814         (bmalloc::Deallocator::deallocateSlowCase):
 815         * bmalloc/Heap.cpp:
 816         (bmalloc::Heap::findXLarge):
 817         (bmalloc::Heap::allocateXLarge):
 818         (bmalloc::Heap::deallocateXLarge):
 819         * bmalloc/Heap.h: Updated for interface changes.
 820
 821         * bmalloc/ObjectType.cpp:
 822         (bmalloc::objectType):
 823         * bmalloc/ObjectType.h:
 824         (bmalloc::isXLarge): We can now tell if a pointer is XLarge just by
 825         examining its bit pattern -- just like we do for other kinds of
 826         allocations -- which is nice.
 827
 828         * bmalloc/Sizes.h:
 829         * bmalloc/VMHeap.h:
 830         (bmalloc::VMHeap::allocateXLarge):
 831         (bmalloc::VMHeap::findXLarge):
 832         (bmalloc::VMHeap::deallocateXLarge): Keep an explicit vector of metadata
 833         for XLarge allocations.
 834
 835         * bmalloc/XLargeChunk.h: Removed.
 836
 837 2015-01-16  Geoffrey Garen  <ggaren@apple.com>
 838
 839         bmalloc: added some infrastructure for aligned allocation
 840         https://bugs.webkit.org/show_bug.cgi?id=140572
 841
 842         Reviewed by Andreas Kling.
 843
 844         * bmalloc/Algorithm.h:
 845         (bmalloc::isPowerOfTwo):
 846         (bmalloc::roundUpToMultipleOf):
 847         (bmalloc::roundDownToMultipleOf): Refactored some duplicate code to use our
 848         isPowerOfTwo helper function.
 849
 850         * bmalloc/Allocator.cpp:
 851         (bmalloc::Allocator::allocate):
 852         * bmalloc/Allocator.h: Stubbed out an implementation of aligned allocation.
 853         Doesn't do anything yet, but does correctly forward to system malloc
 854         when bmalloc is disabled.
 855
 856         * bmalloc/Cache.cpp:
 857         (bmalloc::Cache::allocateSlowCaseNullCache):
 858         * bmalloc/Cache.h:
 859         (bmalloc::Cache::allocate):
 860         * bmalloc/bmalloc.h:
 861         (bmalloc::api::memalign):
 862         * bmalloc/mbmalloc.cpp: Stubbed out an API for aligned allocation.
 863
 864 2015-01-13  Geoffrey Garen  <ggaren@apple.com>
 865
 866         Consider alignment when allocating from a SegregatedFreeList
 867         https://bugs.webkit.org/show_bug.cgi?id=140408
 868
 869         Reviewed by Sam Weinig.
 870
 871         In preparation for supporting aligned allocation.
 872
 873         No performance change.
 874
 875         Since this is just one extra branch in an already expensive function,
 876         I decided not to duplicate the function just to avoid the branch in
 877         the un-aligned case.
 878
 879         * bmalloc/SegregatedFreeList.cpp:
 880         (bmalloc::SegregatedFreeList::take):
 881         * bmalloc/SegregatedFreeList.h:
 882
 883 2015-01-13  Geoffrey Garen  <ggaren@apple.com>
 884
 885         Renamed minimum to size in SegregatedFreeList
 886         https://bugs.webkit.org/show_bug.cgi?id=140406
 887
 888         Reviewed by Sam Weinig.
 889
 890         In preparation for supporting aligned allocation.
 891
 892         * bmalloc/SegregatedFreeList.cpp:
 893         (bmalloc::SegregatedFreeList::takeGreedy):
 894         (bmalloc::SegregatedFreeList::take): Every size passed to malloc is
 895         really just a minimum. Let's not imply that this value is special.
 896
 897 2015-01-11  Dan Bernstein  <mitz@apple.com>
 898
 899         Geoff is organized, but he is not an organization.
 900
 901         Rubber-stamped by Anders Carlsson.
 902
 903         * bmalloc.xcodeproj/project.pbxproj: Removed the ORGANIZATIONNAME project attribute.
 904
 905 2015-01-07  Geoffrey Garen  <ggaren@apple.com>
 906
 907         Make bmalloc work with ASan
 908         https://bugs.webkit.org/show_bug.cgi?id=140194
 909
 910         Reviewed by Mark Lam.
 911
 912         * bmalloc/BPlatform.h: Added a way to detect Darwin OSes, since we need
 913         an OS-specific API to test for loaded runtime libraries.
 914
 915         * bmalloc/Environment.cpp:
 916         (bmalloc::isASanEnabled):
 917         (bmalloc::Environment::computeIsBmallocEnabled): Disabled bmalloc if
 918         ASan is enabled, since system malloc has the Asan hooks we need.
 919
 920         You could check for the ASan compile-time flag instead, but doing this
 921         check at runtime prepares bmalloc for a world where it is a dynamic
 922         library that might be loaded into projects it did not compile with.
 923
 924 2015-01-05  Geoffrey Garen  <ggaren@apple.com>
 925
 926         Fix up bmalloc's PerThread for use on Linux
 927         https://bugs.webkit.org/show_bug.cgi?id=139804
 928
 929         Reviewed by Anders Carlsson.
 930
 931         The previous implementation was a bit slow.
 932
 933         * bmalloc/PerThread.h:
 934         (bmalloc::PerThreadStorage<Cache>::get):
 935         (bmalloc::PerThreadStorage::get):
 936         (bmalloc::PerThreadStorage::init): Added a catch-all cross-platform Unix
 937         way to do fast per-thread access without taking a lock every time. This
 938         probably works on all the platforms we care about, and it matches other
 939         techniques we use elsewhere in WebKit.
 940
 941         (bmalloc::PerThread<T>::getFastCase): Removed the conditional from
 942         this class because PerThreadStorage now encapsulates everything that
 943         needs to be conditional.
 944
 945         (bmalloc::PerThreadStorage::initSharedKeyIfNeeded): Deleted.
 946
 947 2014-12-26  Dan Bernstein  <mitz@apple.com>
 948
 949         <rdar://problem/19348208> REGRESSION (r177027): iOS builds use the wrong toolchain
 950         https://bugs.webkit.org/show_bug.cgi?id=139950
 951
 952         Reviewed by David Kilzer.
 953
 954         * Configurations/Base.xcconfig: Only define TOOLCHAINS when building for OS X, doing so
 955         in a manner that works with Xcode 5.1.1.
 956
 957 2014-12-15  Geoffrey Garen  <ggaren@apple.com>
 958
 959         Safari crashes when you set Malloc environment variables
 960         https://bugs.webkit.org/show_bug.cgi?id=139656
 961
 962         Reviewed by Michael Saboff.
 963
 964         I forgot to cover the realloc() case. Whoops. (OoPS?)
 965
 966         This time around, I ran the full MallocBench test suite in Malloc=1
 967         mode, and it passed.
 968
 969         * bmalloc/Allocator.cpp:
 970         (bmalloc::Allocator::reallocate):
 971         * bmalloc/Allocator.h: Pushed realloc() logic down into the allocator.
 972         It needs to be down there so that we can do the short-circuiting check
 973         for whether bmalloc is enabled first.
 974
 975         Also added the check.
 976
 977         * bmalloc/Cache.cpp:
 978         (bmalloc::Cache::scavenge):
 979         (bmalloc::Cache::Cache):
 980         (bmalloc::Cache::reallocateSlowCaseNullCache):
 981         * bmalloc/Cache.h:
 982         (bmalloc::Cache::deallocator):
 983         (bmalloc::Cache::reallocate): Ditto.
 984
 985         * bmalloc/bmalloc.h:
 986         (bmalloc::api::free):
 987         (bmalloc::api::realloc): Ditto.
 988
 989         (bmalloc::api::scavenge): Pushed this down into Cache to match the
 990         surrounding functions.
 991
 992 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
 993
 994         bmalloc should support system memory analysis tools (part 2)
 995         https://bugs.webkit.org/show_bug.cgi?id=139565
 996
 997         Reviewed by Mark Lam.
 998
 999         This patch actually queries the environment to see if memory analysis
1000         tools have been enabled.
1001
1002         * bmalloc/Deallocator.cpp:
1003         (bmalloc::Deallocator::scavenge): Don't process the object log if
1004         we've disabled bmalloc because it will be full of invalid nullptrs.
1005
1006         * bmalloc/Environment.cpp:
1007         (bmalloc::isMallocEnvironmentVariableSet): Test for the list of known
1008         Malloc debugging flags. I also added a plain "Malloc" catch-all for
1009         when you want to disable bmalloc without enabling any kind of funny
1010         business.
1011
1012         It would be slightly nicer just to iterate the list of environment
1013         variables and strstr them, but getenv is the more portable option,
1014         and performance here doesn't really matter.
1015
1016         (bmalloc::isLibgmallocEnabled): Test for the libgmalloc insertion
1017         environment variable.
1018
1019         (bmalloc::Environment::computeIsBmallocEnabled):
1020
1021 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1022
1023         Try to fix the iOS simulator build.
1024
1025         #include the declaration of malloc / free.
1026
1027         * bmalloc/Allocator.cpp:
1028         * bmalloc/Deallocator.cpp:
1029
1030 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1031
1032         Try to fix the build.
1033
1034         * bmalloc.xcodeproj/project.pbxproj: Marked a header exported.
1035
1036 2014-12-11  Geoffrey Garen  <ggaren@apple.com>
1037
1038         bmalloc should support system memory analysis tools (part 1)
1039         https://bugs.webkit.org/show_bug.cgi?id=139559
1040
1041         Reviewed by Mark Lam.
1042
1043         This patch adds the hooks to disable bmalloc at runtime if certain
1044         environment variables are set, but doesn't actually read from the
1045         environment yet.
1046
1047         No performance change.
1048
1049         * bmalloc.xcodeproj/project.pbxproj: Added the Environment class, which
1050         we'll use to read environment variables and see if memory analysis tools
1051         have been enabled.
1052
1053         * bmalloc/Allocator.cpp:
1054         (bmalloc::Allocator::Allocator):
1055         (bmalloc::Allocator::allocateSlowCase): Added a hook to disable bmalloc
1056         on the allocation path. We cache the setting to make the check fast.
1057
1058         * bmalloc/Allocator.h: Interface changes.
1059
1060         * bmalloc/Cache.cpp:
1061         (bmalloc::Cache::Cache): Pass a heap pointer through to our allocator
1062         and deallocator. This main purpose is to enable them to query the
1063         environment for whether bmalloc is enabled; but this is also a slightly
1064         cleaner way to guarantee to them that the Heap has been pre-initialized.
1065
1066         * bmalloc/Deallocator.cpp:
1067         (bmalloc::Deallocator::Deallocator): If bmalloc is disable, artificially
1068         fill the object log to force us to take the slow path on all deallocations.
1069
1070         (bmalloc::Deallocator::deallocateSlowCase): Do the disabled check.
1071
1072         * bmalloc/Deallocator.h: Interface changes.
1073
1074         * bmalloc/Environment.cpp: Added.
1075         (bmalloc::Environment::Environment):
1076         (bmalloc::Environment::computeIsBmallocEnabled):
1077         * bmalloc/Environment.h: Added.
1078         (bmalloc::Environment::isBmallocEnabled): This is the class that will
1079         encapsulate looking for environment variables that turn on heap
1080         analysis tools.
1081
1082         * bmalloc/Heap.h:
1083         (bmalloc::Heap::environment):
1084
1085         * bmalloc/Mutex.h:
1086         (bmalloc::Mutex::Mutex):
1087         * bmalloc/StaticMutex.h: A little refactoring to clarify these comments,
1088         since I got super confused about them while writing this patch.
1089
1090         * bmalloc/VMHeap.cpp: Fixed an #include.
1091
1092 2014-12-09  David Kilzer  <ddkilzer@apple.com>
1093
1094         Switch from using PLATFORM_NAME to SDK selectors in ANGLE, bmalloc, gtest, JavaScriptCore, WTF
1095         <http://webkit.org/b/139212>
1096
1097         Reviewed by Joseph Pecoraro.
1098
1099         * Configurations/Base.xcconfig:
1100         - Only set GCC_ENABLE_OBJC_GC, GCC_MODEL_TUNING and TOOLCHAINS
1101           on OS X.
1102         * Configurations/DebugRelease.xcconfig:
1103         - Only set MACOSX_DEPLOYMENT_TARGET and SDKROOT on OS X.
1104
1105 2014-11-07  Geoffrey Garen  <ggaren@apple.com>
1106
1107         bmalloc uses 8X more virtual memory than necessary
1108         https://bugs.webkit.org/show_bug.cgi?id=138495
1109
1110         Reviewed by Mark Lam.
1111
1112         iOS has a per-process virtual memory cap around 1GB, so there's some
1113         value to not going totally ham with virtual memory.
1114
1115         We currently use about 8X the necessary amount:
1116             - 2X to align our VM allocation
1117             - 4X to reserve small / medium / (2) large chunk VM ranges per superchunk
1118
1119         We can cut that down:
1120             - Return the unaligned portion of our VM allocation (-2X)
1121             - Use all the chunks in a superchunk, instead of allocating one
1122               chunk per superchunk (-4X)
1123
1124         * bmalloc/Algorithm.h:
1125         (bmalloc::roundUpToMultipleOf): Added a non-constant version of this
1126         function so we can call it with getpagesize() at runtime.
1127
1128         * bmalloc/Chunk.h:
1129         * bmalloc/LargeChunk.h:
1130         (bmalloc::LargeChunk::create): Deleted. Instead of each chunk allocating
1131         its own VM, VMHeap allocates the superchunk and all the chunks in it at a time.
1132
1133         * bmalloc/VMAllocate.h:
1134         (bmalloc::vmValidate):
1135         (bmalloc::vmAllocate): ASSERT that mmap succeeds to make crashes clearer
1136         if it does not succeed. Allocate precisely, and give back the extra.
1137
1138         * bmalloc/VMHeap.cpp:
1139         (bmalloc::VMHeap::allocateSuperChunk):
1140         (bmalloc::VMHeap::allocateSmallChunk): Deleted.
1141         (bmalloc::VMHeap::allocateMediumChunk): Deleted.
1142         (bmalloc::VMHeap::allocateLargeChunk): Deleted. Use all the chunks
1143         in a superchunk, instead of just one.
1144
1145         * bmalloc/VMHeap.h:
1146         (bmalloc::VMHeap::allocateSmallPage):
1147         (bmalloc::VMHeap::allocateMediumPage):
1148         (bmalloc::VMHeap::allocateLargeRange):
1149         * bmalloc/XLargeChunk.h:
1150         (bmalloc::XLargeChunk::create): Updated to match changes above.
1151
1152 2014-11-01  David Kilzer  <ddkilzer@apple.com>
1153
1154         JavaScriptCore is missing debug info for bmalloc because libbmalloc.a is stripped
1155         <https://webkit.org/b/138286>
1156         <rdar://problem/18847087>
1157
1158         Reviewed by Dan Bernstein.
1159
1160         * Configurations/bmalloc.xcconfig: Set STRIP_INSTALLED_PRODUCT
1161         to NO for the target that produces libbmalloc.a so that the
1162         debug symbols will be linked into JavaScriptCore and end up in
1163         its dSYM file.
1164
1165 2014-10-30  Dana Burkart  <dburkart@apple.com>
1166
1167         <rdar://problem/18821260> Prepare for the mysterious future
1168
1169         Reviewed by Lucas Forschler.
1170
1171         * Configurations/Base.xcconfig:
1172         * Configurations/DebugRelease.xcconfig:
1173
1174 2014-09-24  Geoffrey Garen  <ggaren@apple.com>
1175
1176         bmalloc: cleaned up fast path vs slow path
1177         https://bugs.webkit.org/show_bug.cgi?id=137081
1178
1179         Reviewed by Sam Weinig.
1180
1181         Might be a 1% speedup on MallocBench. Also cleans up the code a bit.
1182
1183         * bmalloc/Allocator.cpp:
1184         (bmalloc::Allocator::Allocator): Merged the small and medium range
1185         caches, just like the small and medium allocators. Ranges are abstract
1186         objects that don't really care whether they hold small or medium objects,
1187         so they don't need to be segregated.
1188
1189         (bmalloc::Allocator::scavenge): Ditto.
1190
1191         (bmalloc::Allocator::allocateBumpRangeSlowCase):
1192         (bmalloc::Allocator::allocateBumpRange): Same thing here, except that
1193         we do care a tiny bit, because we need to specify small vs medium when
1194         allocating new ranges from the heap, to ensure that the heap allocates
1195         from the right segment of VM.
1196
1197         (bmalloc::Allocator::allocateLarge):
1198         (bmalloc::Allocator::allocateXLarge): NO_INLINE because this was clouding
1199         up the fast path. Large allocation performance is dominated by allocation
1200         logic and initialization, so inlining it doesn't help.
1201
1202         (bmalloc::Allocator::allocateSlowCase): Slow path got a bit cleaner since
1203         it doesn't need to distinguish small vs medium objects.
1204
1205         (bmalloc::Allocator::allocateSmallBumpRange): Deleted.
1206         (bmalloc::Allocator::allocateMediumBumpRange): Deleted.
1207
1208         * bmalloc/Allocator.h:
1209         * bmalloc/BumpRange.h:
1210
1211         * bmalloc/Cache.cpp:
1212         (bmalloc::Cache::allocateSlowCase): Deleted.
1213         (bmalloc::Cache::deallocateSlowCase): Deleted.
1214         * bmalloc/Cache.h:
1215         (bmalloc::Cache::allocate):
1216         (bmalloc::Cache::deallocate):
1217         (bmalloc::Cache::allocateFastCase): Deleted.
1218         (bmalloc::Cache::deallocateFastCase): Deleted. Removed the Cache slow
1219         paths. The downside to this change is that the fast path branches to two
1220         distinct failure cases instead of one. The upside is that the slow path
1221         doesn't need to re-read the segment register, which is not as cheap as a
1222         normal register, and it doesn't need to do an extra level of function
1223         call. Seems to be worth it.
1224
1225         * bmalloc/Deallocator.h:
1226         * bmalloc/Heap.cpp:
1227         (bmalloc::Heap::refillSmallBumpRangeCache):
1228         (bmalloc::Heap::refillMediumBumpRangeCache):
1229         * bmalloc/Heap.h: Updated for interface changes.
1230
1231         * bmalloc/Sizes.h: The most ranges a cache will hold is the number of
1232         small lines in a page / 2, since any other free lines will coalesce
1233         with their neighbors.
1234
1235 2014-09-23  Geoffrey Garen  <ggaren@apple.com>
1236
1237         Rolled out r173346.
1238
1239             bmalloc should honor the FastMalloc statistics API
1240             https://bugs.webkit.org/show_bug.cgi?id=136592
1241
1242         This didn't really work. Because we allow ranges with and without
1243         physical pages to merge, and we allow double-committing and
1244         double-decommitting, we can't rely on commit actions to track memory
1245         footprint.
1246
1247         * bmalloc/Heap.cpp:
1248         (bmalloc::Heap::size): Deleted.
1249         (bmalloc::Heap::capacity): Deleted.
1250         * bmalloc/Heap.h:
1251         * bmalloc/VMHeap.cpp:
1252         (bmalloc::VMHeap::VMHeap):
1253         (bmalloc::VMHeap::allocateSmallChunk):
1254         (bmalloc::VMHeap::allocateMediumChunk):
1255         (bmalloc::VMHeap::allocateLargeChunk):
1256         * bmalloc/VMHeap.h:
1257         (bmalloc::VMHeap::allocateSmallPage):
1258         (bmalloc::VMHeap::allocateMediumPage):
1259         (bmalloc::VMHeap::allocateLargeRange):
1260         (bmalloc::VMHeap::deallocateSmallPage):
1261         (bmalloc::VMHeap::deallocateMediumPage):
1262         (bmalloc::VMHeap::deallocateLargeRange):
1263         (bmalloc::VMHeap::size): Deleted.
1264         (bmalloc::VMHeap::capacity): Deleted.
1265         * bmalloc/bmalloc.h:
1266         (bmalloc::api::heapSize): Deleted.
1267         (bmalloc::api::heapCapacity): Deleted.
1268
1269 2014-09-23  Geoffrey Garen  <ggaren@apple.com>
1270
1271         bmalloc: Allocation should be more precise
1272         https://bugs.webkit.org/show_bug.cgi?id=136993
1273
1274         Reviewed by Gavin Barraclough.
1275
1276         13% reduction in heap size on the MallocBench *_memory_warning benchmarks.
1277
1278         This patch teaches the allocator to merge adjacent free lines into a
1279         single allocatable range. This allows us to shrink the size of an
1280         individual line without increasing fragmentation or the rate of allocator
1281         slow paths.
1282
1283         We'll only take more slow paths when available memory is sparse, which
1284         is exactly when it's worth it. When available memory is dense, we'll
1285         take fewer slow paths.
1286
1287         * bmalloc.xcodeproj/project.pbxproj:
1288         * bmalloc/Algorithm.h:
1289         (bmalloc::divideRoundingUp):
1290
1291         * bmalloc/Allocator.cpp:
1292         (bmalloc::Allocator::Allocator): Updated for interface changes.
1293
1294         (bmalloc::Allocator::scavenge): Scavenge by object instead of by line.
1295         Now that we merge lines, it's not convenient to scavenge by line.
1296
1297         (bmalloc::Allocator::allocateSmallBumpRange):
1298         (bmalloc::Allocator::allocateMediumBumpRange): Allocate whole ranges
1299         instead of individual lines.
1300
1301         (bmalloc::Allocator::allocateSlowCase):
1302         (bmalloc::Allocator::allocateSmallLine): Deleted.
1303         (bmalloc::Allocator::allocateMediumLine): Deleted.
1304         (bmalloc::Allocator::allocateMedium): Deleted.
1305         * bmalloc/Allocator.h:
1306         (bmalloc::Allocator::allocateFastCase): Folded medium allocations
1307         into the standard fast path with small allocations. Since a BumpAllocator
1308         just allocates out of an arbitrary range, it doesn't need to distinguish
1309         between small and medium lines.
1310
1311         * bmalloc/BumpAllocator.h:
1312         (bmalloc::BumpAllocator::size):
1313         (bmalloc::BumpAllocator::BumpAllocator):
1314         (bmalloc::BumpAllocator::init):
1315         (bmalloc::BumpAllocator::refill):
1316         (bmalloc::BumpAllocator::line): Deleted. No need to track line information
1317         anymore: the heap just gives us a pointer and a pre-computed number of
1318         objects, and we allocate them.
1319
1320         * bmalloc/Deallocator.cpp:
1321         (bmalloc::Deallocator::processObjectLog): Updated for interface changes.
1322
1323         * bmalloc/Heap.cpp:
1324         (bmalloc::Heap::Heap):
1325         (bmalloc::Heap::initializeLineMetadata): Pre-compute precise metadata
1326         detailing where all objects will lie in memory. After we merge two lines,
1327         we might allocate an object that spans from one line to the next. This
1328         metadata details which bits of memory overlap in that way, and how they
1329         overlap.
1330
1331         (bmalloc::Heap::refillSmallBumpRangeCache):
1332         (bmalloc::Heap::refillMediumBumpRangeCache): Scan a whole page at a time,
1333         and merge adjacent free lines into BumpRanges.
1334
1335         (bmalloc::Heap::allocateSmallPage):
1336         (bmalloc::Heap::allocateMediumPage):
1337         (bmalloc::Heap::deallocateSmallLine):
1338         (bmalloc::Heap::deallocateMediumLine): Track pages rather than lines,
1339         since we scan for free memory a page at a time.
1340
1341         (bmalloc::Heap::allocateSmallLineSlowCase): Deleted.
1342         (bmalloc::Heap::allocateMediumLineSlowCase): Deleted. Folded into the
1343         fast path.
1344
1345         * bmalloc/Heap.h:
1346         (bmalloc::Heap::derefSmallLine):
1347         (bmalloc::Heap::derefMediumLine):
1348         (bmalloc::Heap::deallocateSmallLine): Deleted.
1349         (bmalloc::Heap::allocateSmallLine): Deleted.
1350         (bmalloc::Heap::deallocateMediumLine): Deleted.
1351         (bmalloc::Heap::allocateMediumLine): Deleted. Updated for interface changes.
1352
1353         * bmalloc/Line.h:
1354         (bmalloc::Line<Traits>::ref):
1355         (bmalloc::Line<Traits>::deref):
1356         (bmalloc::Line<Traits>::concurrentRef): Deleted. We don't pass a derefCount
1357         anymore, since we only ever deref by 1 now.
1358
1359         * bmalloc/MediumAllocator.h:
1360         (bmalloc::MediumAllocator::isNull): Deleted.
1361         (bmalloc::MediumAllocator::MediumAllocator): Deleted.
1362         (bmalloc::MediumAllocator::line): Deleted.
1363         (bmalloc::MediumAllocator::allocate): Deleted.
1364         (bmalloc::MediumAllocator::derefCount): Deleted.
1365         (bmalloc::MediumAllocator::refill): Deleted.
1366         (bmalloc::MediumAllocator::clear): Deleted. Deleted some code that's
1367         been dead for a while, since it doesn't build anymore with this patch.
1368
1369         * bmalloc/Page.h:
1370         (bmalloc::Page::sizeClass):
1371         (bmalloc::Page::setSizeClass):
1372         (bmalloc::Page::smallSizeClass): Deleted.
1373         (bmalloc::Page::setSmallSizeClass): Deleted. Renamed setSmallSizeClass
1374         to sizeClass, since we use it for medium sizes too.
1375
1376         * bmalloc/Sizes.h:
1377         (bmalloc::Sizes::sizeClass):
1378         (bmalloc::Sizes::objectSize): Shrank line sizes to save memory.
1379
1380         (bmalloc::Sizes::smallSizeClassFor): Deleted.
1381         (bmalloc::Sizes::mediumSizeClassFor): Deleted.
1382
1383         * bmalloc/bmalloc.h:
1384         (bmalloc::api::realloc): Now that we have precise objects sizes, realloc
1385         can be a bit more precise. It also has to be, since we can't guarantee
1386         that an object ends at the end of a line anymore.
1387
1388 2014-09-19  Daniel Bates  <dabates@apple.com>
1389
1390         Always assume internal SDK when building configuration Production
1391         https://bugs.webkit.org/show_bug.cgi?id=136925
1392         <rdar://problem/18362399>
1393
1394         Reviewed by Dan Bernstein.
1395
1396         * Configurations/Base.xcconfig:
1397
1398 2014-09-16  Geoffrey Garen  <ggaren@apple.com>
1399
1400         bmalloc: moved line caches from the deallocator to the allocator
1401         https://bugs.webkit.org/show_bug.cgi?id=136868
1402
1403         Reviewed by Gavin Barraclough.
1404
1405         I did this mostly as a simplification, to make it easier to change the
1406         allocation strategy.
1407
1408         No throughput change on MallocBench. Saves about 50kB.
1409
1410         Since the deallocator needs to lock the heap when freeing lines anyway,
1411         there isn't much benefit to giving the deallocator a local cache of
1412         deallocated lines.
1413
1414         We still give the allocator a local cache of lines because that does
1415         reduce the frequency at which it needs to lock the heap in order to
1416         acquire more lines.
1417
1418         * bmalloc/Allocator.cpp:
1419         (bmalloc::Allocator::scavenge):
1420         (bmalloc::Allocator::allocateSmallLine):
1421         (bmalloc::Allocator::allocateMediumLine):
1422         (bmalloc::Allocator::allocateMedium):
1423         (bmalloc::Allocator::allocateSlowCase):
1424         * bmalloc/Allocator.h:
1425         * bmalloc/Deallocator.cpp:
1426         (bmalloc::Deallocator::Deallocator):
1427         (bmalloc::Deallocator::scavenge):
1428         (bmalloc::Deallocator::processObjectLog):
1429         (bmalloc::Deallocator::deallocateSmallLine): Deleted.
1430         (bmalloc::Deallocator::allocateSmallLine): Deleted.
1431         (bmalloc::Deallocator::deallocateMediumLine): Deleted.
1432         (bmalloc::Deallocator::allocateMediumLine): Deleted.
1433         * bmalloc/Deallocator.h:
1434
1435         * bmalloc/Sizes.h:
1436         * bmalloc/VMAllocate.h: Took the opportunity to make the line cache size
1437         exactly one page in size. That's about what we were shooting for anyway,
1438         and it may make it easier to switch to per-page allocation in future.
1439
1440 2014-09-15  Geoffrey Garen  <ggaren@apple.com>
1441
1442         bmalloc: allocate small and medium objects using the same bump pointer class
1443         https://bugs.webkit.org/show_bug.cgi?id=136843
1444
1445         Reviewed by Gavin Barraclough.
1446
1447         4% speedup on MallocBench.
1448
1449         Now that medium-sized objects have dedicated per-size allocators, they
1450         don't need to use an arbitrary bump pointer allocator. This means that
1451         every allocator knows how many objects it will allocate from the start,
1452         and we don't need a post-processing step to adjust refcounts based on
1453         real allocation count.
1454
1455         * bmalloc.xcodeproj/project.pbxproj: Renamed SmallAllocator to BumpAllocator
1456         since it's used for small and medium objects now.
1457
1458         * bmalloc/Allocator.cpp:
1459         (bmalloc::Allocator::Allocator): Updated to use new interface.
1460         (bmalloc::Allocator::scavenge): To "retire" an allocator, we just need
1461         to make sure that we finish allocating all the objects in it.
1462
1463         (bmalloc::Allocator::allocateMedium):
1464         (bmalloc::Allocator::allocateSlowCase):
1465         (bmalloc::Allocator::retire): Deleted.
1466         (bmalloc::Allocator::processSmallAllocatorLog): Deleted.
1467         (bmalloc::Allocator::processMediumAllocatorLog): Deleted.
1468         * bmalloc/Allocator.h:
1469         (bmalloc::Allocator::allocateFastCase): Removed abstractions and data
1470         used to post-process an allocator based on how many objects it allocated.
1471
1472         * bmalloc/BumpAllocator.h: Copied from Source/bmalloc/bmalloc/SmallAllocator.h.
1473         (bmalloc::BumpAllocator::BumpAllocator):
1474         (bmalloc::BumpAllocator::init):
1475         (bmalloc::BumpAllocator::line):
1476         (bmalloc::BumpAllocator::validate):
1477         (bmalloc::BumpAllocator::allocate):
1478         (bmalloc::BumpAllocator::refill):
1479         (bmalloc::BumpAllocator::clear): Updated these functions to be agnostic
1480         about the kinds of lines they allocate into. In some cases, the line
1481         type must be provided as a template parameter by the caller.
1482
1483         (bmalloc::SmallAllocator::SmallAllocator): Deleted.
1484         (bmalloc::SmallAllocator::line): Deleted.
1485         (bmalloc::SmallAllocator::allocate): Deleted.
1486         (bmalloc::SmallAllocator::objectCount): Deleted.
1487         (bmalloc::SmallAllocator::derefCount): Deleted.
1488         (bmalloc::SmallAllocator::refill): Deleted.
1489         (bmalloc::SmallAllocator::clear): Deleted.
1490
1491         * bmalloc/ObjectType.h:
1492         (bmalloc::isMedium):
1493
1494         * bmalloc/SmallAllocator.h:
1495         (bmalloc::SmallAllocator::isNull): Deleted.
1496         (bmalloc::SmallAllocator::canAllocate): Deleted.
1497         (bmalloc::SmallAllocator::SmallAllocator): Deleted.
1498         (bmalloc::SmallAllocator::line): Deleted.
1499         (bmalloc::SmallAllocator::allocate): Deleted.
1500         (bmalloc::SmallAllocator::objectCount): Deleted.
1501         (bmalloc::SmallAllocator::derefCount): Deleted.
1502         (bmalloc::SmallAllocator::refill): Deleted.
1503         (bmalloc::SmallAllocator::clear): Deleted.
1504
1505 2014-09-12  Geoffrey Garen  <ggaren@apple.com>
1506
1507         Fixed a goof in bmalloc Vector sizing
1508         https://bugs.webkit.org/show_bug.cgi?id=136795
1509
1510         Reviewed by Gavin Barraclough and Sam Weinig.
1511
1512         We want our minimum vector to be page-sized since the OS will give us
1513         a page no matter what -- but we want that many bytes, and not enough
1514         bytes to store that many elements.
1515
1516         * bmalloc/Vector.h: Math is hard.
1517
1518 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
1519
1520         bmalloc should segregate medium-sized objects by line like it does for small-sized objects
1521         https://bugs.webkit.org/show_bug.cgi?id=136693
1522
1523         Reviewed by Gavin Barraclough.
1524
1525         4% reduction in heap size on the MallocBench *_memory_warning benchmarks.
1526
1527         No throughput change.
1528
1529         We keep an array of medium allocators, just like our array of small
1530         allocators.
1531
1532         In future, we can simplify the allocation fast path by merging the small
1533         and medium allocator arrays. For now, this is the simplest change that
1534         gets the win.
1535
1536         * bmalloc/Allocator.cpp:
1537         (bmalloc::Allocator::Allocator):
1538         (bmalloc::Allocator::scavenge):
1539         (bmalloc::Allocator::allocateMedium):
1540         * bmalloc/Allocator.h:
1541         * bmalloc/Sizes.h:
1542         (bmalloc::Sizes::mediumSizeClassFor):
1543
1544 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
1545
1546         Reviewed by Sam Weinig.
1547
1548         Renamed log => retire for clarity.
1549
1550         * bmalloc/Allocator.cpp:
1551         (bmalloc::Allocator::scavenge):
1552         (bmalloc::Allocator::retire):
1553         (bmalloc::Allocator::allocateMedium):
1554         (bmalloc::Allocator::allocateSlowCase):
1555         (bmalloc::Allocator::log): Deleted.
1556         * bmalloc/Allocator.h:
1557
1558 2014-09-11  Geoffrey Garen  <ggaren@apple.com>
1559
1560         bmalloc: eager scavenge leaves behind a bogus allocator
1561         https://bugs.webkit.org/show_bug.cgi?id=136743
1562
1563         Reviewed by Sam Weinig.
1564
1565         Be sure to clear the allocator after logging it in the eager scavenge
1566         case, so that we don't later try to allocate out of the lines that we
1567         have thrown away.
1568
1569         We didn't need to do this previously because scavenge would only happen
1570         at thread exit time, after which no further allocation from the per-thread
1571         cache would take place.
1572
1573         * bmalloc/Allocator.cpp:
1574         (bmalloc::Allocator::scavenge):
1575         * bmalloc/MediumAllocator.h:
1576         (bmalloc::MediumAllocator::clear):
1577         * bmalloc/SmallAllocator.h:
1578         (bmalloc::SmallAllocator::clear):
1579
1580 2014-09-05  Geoffrey Garen  <ggaren@apple.com>
1581
1582         bmalloc should honor the FastMalloc statistics API
1583         https://bugs.webkit.org/show_bug.cgi?id=136592
1584
1585         Reviewed by Gavin Barraclough.
1586
1587         We do this by tracking "size" and "capacity" in the VM heap.
1588
1589         The VM heap's "capacity" is all the VM we ever allocated.
1590
1591         The VM heap's "size" the subset of VM currently held onto by the
1592         VM heap (and therefore not in use by the regular heap).
1593
1594         Somewhat ironically, reducing the process's memory footprint, increases
1595         the size of the VM heap, since the VM heap holds the pages that are
1596         purely virtual and not physical.
1597
1598         * bmalloc/Heap.cpp:
1599         (bmalloc::Heap::size):
1600         (bmalloc::Heap::capacity):
1601         * bmalloc/Heap.h:
1602         * bmalloc/VMHeap.cpp:
1603         (bmalloc::VMHeap::VMHeap):
1604         (bmalloc::VMHeap::allocateSmallChunk):
1605         (bmalloc::VMHeap::allocateMediumChunk):
1606         (bmalloc::VMHeap::allocateLargeChunk):
1607         * bmalloc/VMHeap.h:
1608         (bmalloc::VMHeap::size):
1609         (bmalloc::VMHeap::capacity):
1610         (bmalloc::VMHeap::allocateSmallPage):
1611         (bmalloc::VMHeap::allocateMediumPage):
1612         (bmalloc::VMHeap::allocateLargeRange):
1613         (bmalloc::VMHeap::deallocateSmallPage):
1614         (bmalloc::VMHeap::deallocateMediumPage):
1615         (bmalloc::VMHeap::deallocateLargeRange):
1616         * bmalloc/bmalloc.h:
1617         (bmalloc::api::heapSize):
1618         (bmalloc::api::heapCapacity):
1619
1620 2014-09-02  Geoffrey Garen  <ggaren@apple.com>
1621
1622         bmalloc crashes on the EWS bots (due to bad large object allocation)
1623         https://bugs.webkit.org/show_bug.cgi?id=136469
1624
1625         Reviewed by Andreas Kling.
1626
1627         It's possible to convince bmalloc to perform a bad large object allocation,
1628         through these steps:
1629
1630         (1) Insert object A into freelist F0.
1631
1632         (2) Split, merge and split again A's neighbors such that object B is
1633         inserted into freelist F0, with boundary tag and size equal to object A,
1634         but pointer not completely equal to object A. Put object B at the head of F0.
1635
1636         (3) Allocate some other object from F0, swapping its position in the
1637         freelist with object B, such that object A is now ahead of object B.
1638
1639         --> Now, the next allocation for size A/B will allocate object A, which
1640         has a slightly wrong idea about where the object actually begins.
1641         Immediately, you'll corrupt a little memory, and over time, you'll also
1642         corrupt boundary tag metadata.
1643
1644         The solution is to store the begin pointer in the boundary tag. Luckily,
1645         this doesn't make the tag any bigger, and it's not a noticeable slowdown
1646         on MallocBench.
1647
1648         * bmalloc/Algorithm.h:
1649         (bmalloc::rightShift):
1650         * bmalloc/BeginTag.h:
1651         (bmalloc::BeginTag::isInFreeList): This is the bug fix. Make sure to
1652         validate the start pointer when popping off the free list. Through a
1653         very uncommon set of steps, it is possible to have an item in the free
1654         list that is valid by all accounts except for its start pointer.
1655
1656         * bmalloc/BoundaryTag.h:
1657         (bmalloc::BoundaryTag::compactBegin):
1658         (bmalloc::BoundaryTag::setRange):
1659         (bmalloc::BoundaryTag::setSize): Deleted. Record a compact version of the
1660         start pointer. We don't need the whole pointer -- just the offset, in
1661         largeAlignment increments, into the relevant boundary tag bucket.
1662
1663         * bmalloc/BoundaryTagInlines.h:
1664         (bmalloc::validateNext):
1665         (bmalloc::BoundaryTag::init):
1666         (bmalloc::BoundaryTag::mergeLarge):
1667         (bmalloc::BoundaryTag::splitLarge):
1668         * bmalloc/SegregatedFreeList.cpp:
1669         (bmalloc::SegregatedFreeList::insert):
1670         (bmalloc::SegregatedFreeList::takeGreedy):
1671         (bmalloc::SegregatedFreeList::take): Provide the whole range instead of
1672         the size when establishing a boundary tag, as required by the new
1673         interface.
1674
1675         * bmalloc/Sizes.h:
1676
1677 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
1678
1679         Fixed a bmalloc crash seen on the EWS bot
1680         https://bugs.webkit.org/show_bug.cgi?id=135955
1681
1682         Reviewed by Andreas Kling.
1683
1684         * bmalloc/Syscall.h: Some CG APIs vm_copy their input buffers. If the
1685         input buffer is a malloc region, that region will get marked Copy-On-Write
1686         by the kernel. Calls to madvise() for COW regions fail and return EINVAL
1687         on older OS X's. In 10.10, they still fail, but they do not return
1688         EINVAL.
1689
1690         So, we can only ASSERT that our syscalls succeed starting with 10.10.
1691
1692 2014-08-14  Geoffrey Garen  <ggaren@apple.com>
1693
1694         Fixed the bmalloc build
1695         https://bugs.webkit.org/show_bug.cgi?id=135953
1696
1697         Reviewed by Andreas Kling.
1698
1699         * bmalloc.xcodeproj/project.pbxproj: Marked a few headers as private.
1700         These headers are used, so they must be available outside the project.
1701
1702 2014-08-13  Daniel Bates  <dabates@apple.com>
1703
1704         Attempt to fix the build following <http://trac.webkit.org/changeset/172576>
1705         (https://bugs.webkit.org/show_bug.cgi?id=135895)
1706
1707         Substitute PerThreadStorage<T>::initSharedKeyIfNeeded() for initSharedKeyIfNeeded() in
1708         implementation of PerThread<T>::getFastCase().
1709
1710         * bmalloc/PerThread.h:
1711         (bmalloc::PerThread<T>::getFastCase):
1712
1713 2014-08-13  Daniel Bates  <dabates@apple.com>
1714
1715         Make bmalloc::PerThread work without C++ thread local storage
1716         https://bugs.webkit.org/show_bug.cgi?id=135895
1717
1718         Reviewed by Geoffrey Garen.
1719
1720         Implement support for building bmalloc without C++ thread local storage.
1721
1722         * bmalloc/BPlatform.h: Remove macro define BPLATFORM_IOS_SIMULATOR. Added macro function
1723         BCOMPILER_SUPPORTS() and macro define BCOMPILER_SUPPORTS_CXX_THREAD_LOCAL that can be used
1724         to determine whether the compiler supports C++ thread local storage.
1725         * bmalloc/PerThread.h:
1726         (bmalloc::PerThreadStorage::get): Modified to call pthread_getspecific() when building
1727         without C++ thread local storage.
1728         (bmalloc::PerThreadStorage::initSharedKeyIfNeeded): Added.
1729         (bmalloc::PerThreadStorage::init): Moved logic to initialize shared Pthread key from here to
1730         PerThreadStorage::initSharedKeyIfNeeded().
1731         (bmalloc::PerThread<T>::getFastCase): Modified to call PerThreadStorage::initSharedKeyIfNeeded()
1732         before querying PerThreadStorage::get() when building without C++ thread local storage so as to
1733         ensure that the shared key has been initialized.
1734         (_pthread_setspecific_direct): Deleted.
1735         (_pthread_getspecific_direct): Deleted.
1736
1737 2014-08-13  Daniel Bates  <dabates@apple.com>
1738
1739         [iOS] Make JavaScriptCore and bmalloc build with the public SDK
1740         https://bugs.webkit.org/show_bug.cgi?id=135848
1741
1742         Reviewed by Geoffrey Garen.
1743
1744         * bmalloc/BPlatform.h: Added macro BPLATFORM_IOS_SIMULATOR, which evaluates to true
1745         when building for the iOS Simulator.
1746         * bmalloc/PerThread.h: Use pthread_machdep.h code path when building for iOS Simulator
1747         using the public SDK.
1748         (_pthread_setspecific_direct): Added; only defined when building for the iOS Simulator
1749         using the public SDK.
1750         (_pthread_getspecific_direct): Added; only defined when building for the iOS Simulator
1751         using the public SDK.
1752
1753 2014-08-12  Daniel Bates  <dabates@apple.com>
1754
1755         BPLATFORM(IOS) always evaluates to false
1756         https://bugs.webkit.org/show_bug.cgi?id=135843
1757
1758         Reviewed by Geoffrey Garen.
1759
1760         Fix typo in definition of BPLATFORM() and include system header TargetConditionals.h
1761         (when building on an Apple platform) so that BPLATFORM(X) evaluates to true when
1762         building for platform X. In particular, so that BPLATFORM(IOS) evaluates to true when
1763         building for iOS.
1764
1765         As a side effect of this change, the change made in <http://trac.webkit.org/changeset/167289>
1766         will be honored and iOS will assume a VM page size of 16kB (again) instead of 4kB.
1767
1768         * bmalloc/BPlatform.h:
1769
1770 2014-08-11  Andy Estes  <aestes@apple.com>
1771
1772         [iOS] Get rid of iOS.xcconfig
1773         https://bugs.webkit.org/show_bug.cgi?id=135809
1774
1775         Reviewed by Joseph Pecoraro.
1776
1777         All iOS.xcconfig did was include AspenFamily.xcconfig, so there's no need for the indirection.
1778
1779         * Configurations/Base.xcconfig:
1780         * Configurations/iOS.xcconfig: Removed.
1781         * bmalloc.xcodeproj/project.pbxproj:
1782
1783 2014-05-01  Dan Bernstein  <mitz@apple.com>
1784
1785         Fixed production builds for the iOS Simulator.
1786         <rdar://problem/16792221>
1787
1788         * Configurations/bmalloc.xcconfig: Include INSTALL_PATH_PREFIX in
1789         PRIVATE_HEADERS_FOLDER_PATH when installing.
1790
1791 2014-04-20  Geoffrey Garen  <ggaren@apple.com>
1792
1793         bmalloc: Segregate pages by objects size
1794         https://bugs.webkit.org/show_bug.cgi?id=131909
1795
1796         Reviewed by Andreas Kling.
1797
1798         2% reduction in memory-at-end on the Membuster memory_warning benchmarks.
1799
1800         * bmalloc/Allocator.cpp:
1801         (bmalloc::Allocator::allocateSlowCase):
1802         * bmalloc/Allocator.h:
1803         (bmalloc::Allocator::allocateFastCase):
1804         (bmalloc::Allocator::smallAllocatorFor): Use the new shared helper
1805         function for size class calculation.
1806
1807         * bmalloc/Deallocator.cpp:
1808         (bmalloc::Deallocator::Deallocator):
1809         (bmalloc::Deallocator::scavenge):
1810         (bmalloc::Deallocator::deallocateSmallLine):
1811         (bmalloc::Deallocator::allocateSmallLine):
1812         * bmalloc/Deallocator.h: Keep a cache for every size class, since the
1813         cache can't be shared anymore.
1814
1815         * bmalloc/Heap.cpp:
1816         (bmalloc::Heap::allocateSmallLineSlowCase):
1817         * bmalloc/Heap.h:
1818         (bmalloc::Heap::deallocateSmallLine): Ditto.
1819
1820         (bmalloc::Heap::allocateSmallLine): Check size class in addition to
1821         page refcount when allocating a line because we might have deallocated
1822         the page and the recycled it for another size class.
1823
1824         (bmalloc::Heap::deallocateMediumLine):
1825         (bmalloc::Heap::allocateMediumLine):
1826         * bmalloc/Line.h:
1827         (bmalloc::Line::refCount):
1828         * bmalloc/Page.h:
1829         (bmalloc::Page::refCount):
1830         (bmalloc::Page::smallSizeClass):
1831         (bmalloc::Page::setSmallSizeClass):
1832         (bmalloc::Page<Traits>::refCount): Deleted.
1833         * bmalloc/Sizes.h:
1834         (bmalloc::Sizes::smallSizeClassFor): New shared API for computing
1835         an index into an array from a size.
1836
1837 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
1838
1839         bmalloc: Improved alignment in LargeChunk
1840         https://bugs.webkit.org/show_bug.cgi?id=131895
1841
1842         Reviewed by Andreas Kling.
1843
1844         * bmalloc/Chunk.h:
1845         * bmalloc/LargeChunk.h: Align to vmPageSize just like Chunk does.
1846         Technically, the previous alignment was harmless, but I would prefer,
1847         dear reader, not to have to explain the interlocking set of
1848         circumstances that made it so.
1849
1850 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
1851
1852         Rolled out r167502 because it caused a crash on the facebook benchmark.
1853
1854         Unreviewed.
1855
1856             bmalloc: Added an XSmall line size
1857             https://bugs.webkit.org/show_bug.cgi?id=131851
1858
1859             Reviewed by Sam Weinig.
1860
1861 2014-04-19  Geoffrey Garen  <ggaren@apple.com>
1862
1863         bmalloc: Mutex should be harder to use wrong
1864         https://bugs.webkit.org/show_bug.cgi?id=131879
1865
1866         Reviewed by Andreas Kling.
1867
1868         Mutex now has a proper constructor, so you can't deadlock by forgetting
1869         to initialize it.
1870
1871         * bmalloc.xcodeproj/project.pbxproj:
1872         * bmalloc/Allocator.cpp:
1873         (bmalloc::Allocator::processXSmallAllocatorLog):
1874         (bmalloc::Allocator::processSmallAllocatorLog):
1875         (bmalloc::Allocator::processMediumAllocatorLog):
1876         (bmalloc::Allocator::allocateLarge):
1877         (bmalloc::Allocator::allocateXLarge): Global replace Mutex => StaticMutex,
1878         since the Heap mutex is a static.
1879
1880         * bmalloc/AsyncTask.h:
1881         (bmalloc::Function>::AsyncTask): Use Mutex, since we're not static. No
1882         need for explicit initialization anymore.
1883
1884         * bmalloc/Deallocator.cpp:
1885         (bmalloc::Deallocator::scavenge):
1886         (bmalloc::Deallocator::deallocateLarge):
1887         (bmalloc::Deallocator::deallocateXLarge):
1888         (bmalloc::Deallocator::processObjectLog):
1889         (bmalloc::Deallocator::deallocateSmallLine):
1890         (bmalloc::Deallocator::deallocateXSmallLine):
1891         (bmalloc::Deallocator::allocateSmallLine):
1892         (bmalloc::Deallocator::allocateXSmallLine):
1893         (bmalloc::Deallocator::deallocateMediumLine):
1894         (bmalloc::Deallocator::allocateMediumLine):
1895         * bmalloc/Deallocator.h:
1896         * bmalloc/Heap.cpp:
1897         (bmalloc::sleep):
1898         (bmalloc::Heap::Heap):
1899         (bmalloc::Heap::concurrentScavenge):
1900         (bmalloc::Heap::scavenge):
1901         (bmalloc::Heap::scavengeSmallPages):
1902         (bmalloc::Heap::scavengeXSmallPages):
1903         (bmalloc::Heap::scavengeMediumPages):
1904         (bmalloc::Heap::scavengeLargeRanges):
1905         (bmalloc::Heap::allocateXSmallLineSlowCase):
1906         (bmalloc::Heap::allocateSmallLineSlowCase):
1907         (bmalloc::Heap::allocateMediumLineSlowCase):
1908         (bmalloc::Heap::allocateXLarge):
1909         (bmalloc::Heap::deallocateXLarge):
1910         (bmalloc::Heap::allocateLarge):
1911         (bmalloc::Heap::deallocateLarge):
1912         * bmalloc/Heap.h:
1913         (bmalloc::Heap::deallocateXSmallLine):
1914         (bmalloc::Heap::allocateXSmallLine):
1915         (bmalloc::Heap::deallocateSmallLine):
1916         (bmalloc::Heap::allocateSmallLine):
1917         (bmalloc::Heap::deallocateMediumLine):
1918         (bmalloc::Heap::allocateMediumLine):
1919         * bmalloc/Line.h:
1920         (bmalloc::Line<Traits>::deref):
1921         * bmalloc/Mutex.cpp: Removed.
1922         * bmalloc/Mutex.h:
1923         (bmalloc::Mutex::Mutex):
1924         (bmalloc::Mutex::init): Deleted.
1925         (bmalloc::Mutex::try_lock): Deleted.
1926         (bmalloc::Mutex::lock): Deleted.
1927         (bmalloc::Mutex::unlock): Deleted.
1928         * bmalloc/Page.h:
1929         (bmalloc::Page<Traits>::ref):
1930         (bmalloc::Page<Traits>::deref):
1931         (bmalloc::Page<Traits>::refCount):
1932         * bmalloc/PerProcess.h:
1933         (bmalloc::PerProcess::mutex):
1934         (bmalloc::PerProcess<T>::getSlowCase):
1935         * bmalloc/StaticMutex.cpp: Added.
1936         (bmalloc::StaticMutex::lockSlowCase):
1937         * bmalloc/StaticMutex.h: Added.
1938         (bmalloc::StaticMutex::init):
1939         (bmalloc::StaticMutex::try_lock):
1940         (bmalloc::StaticMutex::lock):
1941         (bmalloc::StaticMutex::unlock):
1942         * bmalloc/VMHeap.h:
1943         (bmalloc::VMHeap::deallocateXSmallPage):
1944         (bmalloc::VMHeap::deallocateSmallPage):
1945         (bmalloc::VMHeap::deallocateMediumPage):
1946         (bmalloc::VMHeap::deallocateLargeRange):
1947         * bmalloc/bmalloc.h:
1948         (bmalloc::api::scavenge): Global replace Mutex => StaticMutex,
1949         since the Heap mutex is a static.
1950
1951 2014-04-18  Geoffrey Garen  <ggaren@apple.com>
1952
1953         bmalloc: AsyncTask should use Mutex instead of std::mutex
1954         https://bugs.webkit.org/show_bug.cgi?id=131865
1955
1956         Reviewed by Gavin Barraclough.
1957
1958         std::mutex is so slow that it makes parallelizing simple tasks through
1959         AsyncTask a net regression. Mutex fixes this.
1960
1961         * bmalloc/AsyncTask.h:
1962         (bmalloc::Function>::AsyncTask):
1963         (bmalloc::Function>::join):
1964         (bmalloc::Function>::runSlowCase):
1965         (bmalloc::Function>::entryPoint):
1966         * bmalloc/Mutex.h:
1967         (bmalloc::Mutex::init):
1968
1969 2014-04-18  Geoffrey Garen  <ggaren@apple.com>
1970
1971         bmalloc: Added an XSmall line size
1972         https://bugs.webkit.org/show_bug.cgi?id=131851
1973
1974         Reviewed by Sam Weinig.
1975
1976         Reduces malloc footprint on Membuster recordings by 10%.
1977
1978         This is a throughput regression, but we're still way ahead of TCMalloc.
1979         I have some ideas for how to recover the regression -- but I wanted to
1980         get this win in first.
1981
1982         Full set of benchmark results:
1983
1984                 bmalloc> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks --measure-heap nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
1985
1986                                                                nopatch                      patch                                Δ
1987                 Peak Memory:
1988                     reddit_memory_warning                      7,896kB                    7,532kB                  ^ 1.05x smaller
1989                     flickr_memory_warning                     12,968kB                   12,324kB                  ^ 1.05x smaller
1990                     theverge_memory_warning                   16,672kB                   15,200kB                   ^ 1.1x smaller
1991
1992                     <geometric mean>                          11,952kB                   11,216kB                  ^ 1.07x smaller
1993                     <arithmetic mean>                         12,512kB                   11,685kB                  ^ 1.07x smaller
1994                     <harmonic mean>                           11,375kB                   10,726kB                  ^ 1.06x smaller
1995
1996                 Memory at End:
1997                     reddit_memory_warning                      7,320kB                    6,856kB                  ^ 1.07x smaller
1998                     flickr_memory_warning                     10,848kB                    9,692kB                  ^ 1.12x smaller
1999                     theverge_memory_warning                   16,380kB                   14,872kB                   ^ 1.1x smaller
2000
2001                     <geometric mean>                          10,916kB                    9,961kB                   ^ 1.1x smaller
2002                     <arithmetic mean>                         11,516kB                   10,473kB                   ^ 1.1x smaller
2003                     <harmonic mean>                           10,350kB                    9,485kB                  ^ 1.09x smaller
2004
2005                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
2006
2007                                                    nopatch                patch                         Δ
2008                 Execution Time:
2009                     churn                            127ms                151ms            ! 1.19x slower
2010                     list_allocate                    130ms                164ms            ! 1.26x slower
2011                     tree_allocate                    109ms                127ms            ! 1.17x slower
2012                     tree_churn                       115ms                120ms            ! 1.04x slower
2013                     facebook                         240ms                259ms            ! 1.08x slower
2014                     fragment                          91ms                131ms            ! 1.44x slower
2015                     fragment_iterate                 105ms                106ms            ! 1.01x slower
2016                     message_one                      260ms                259ms             ^ 1.0x faster
2017                     message_many                     149ms                154ms            ! 1.03x slower
2018                     medium                           194ms                248ms            ! 1.28x slower
2019                     big                              157ms                160ms            ! 1.02x slower
2020
2021                     <geometric mean>                 144ms                163ms            ! 1.13x slower
2022                     <arithmetic mean>                152ms                171ms            ! 1.12x slower
2023                     <harmonic mean>                  137ms                156ms            ! 1.14x slower
2024
2025                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks nopatch:~/scratch/Build-nopatch/Release/ patch:~/webkit/WebKitBuild/Release/
2026
2027                                                                        nopatch                          patch                                     Δ
2028                 Execution Time:
2029                     churn                                                126ms                          148ms                        ! 1.17x slower
2030                     churn --parallel                                      62ms                           76ms                        ! 1.23x slower
2031                     list_allocate                                        130ms                          164ms                        ! 1.26x slower
2032                     list_allocate --parallel                             120ms                          175ms                        ! 1.46x slower
2033                     tree_allocate                                        111ms                          127ms                        ! 1.14x slower
2034                     tree_allocate --parallel                              95ms                          135ms                        ! 1.42x slower
2035                     tree_churn                                           115ms                          124ms                        ! 1.08x slower
2036                     tree_churn --parallel                                107ms                          126ms                        ! 1.18x slower
2037                     facebook                                             240ms                          276ms                        ! 1.15x slower
2038                     facebook --parallel                                  802ms                        1,088ms                        ! 1.36x slower
2039                     fragment                                              92ms                          130ms                        ! 1.41x slower
2040                     fragment --parallel                                   66ms                          124ms                        ! 1.88x slower
2041                     fragment_iterate                                     109ms                          127ms                        ! 1.17x slower
2042                     fragment_iterate --parallel                           55ms                           64ms                        ! 1.16x slower
2043                     message_one                                          260ms                          260ms
2044                     message_many                                         170ms                          238ms                         ! 1.4x slower
2045                     medium                                               185ms                          250ms                        ! 1.35x slower
2046                     medium --parallel                                    210ms                          334ms                        ! 1.59x slower
2047                     big                                                  150ms                          169ms                        ! 1.13x slower
2048                     big --parallel                                       138ms                          144ms                        ! 1.04x slower
2049
2050                     <geometric mean>                                     135ms                          170ms                        ! 1.26x slower
2051                     <arithmetic mean>                                    167ms                          214ms                        ! 1.28x slower
2052                     <harmonic mean>                                      117ms                          148ms                        ! 1.26x slower
2053
2054                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
2055
2056                                                                     TC                      patch                                Δ
2057                 Peak Memory:
2058                     reddit_memory_warning                     13,836kB                   13,436kB                  ^ 1.03x smaller
2059                     flickr_memory_warning                     24,868kB                   25,188kB                   ! 1.01x bigger
2060                     theverge_memory_warning                   24,504kB                   26,636kB                   ! 1.09x bigger
2061
2062                     <geometric mean>                          20,353kB                   20,812kB                   ! 1.02x bigger
2063                     <arithmetic mean>                         21,069kB                   21,753kB                   ! 1.03x bigger
2064                     <harmonic mean>                           19,570kB                   19,780kB                   ! 1.01x bigger
2065
2066                 Memory at End:
2067                     reddit_memory_warning                      8,656kB                   10,016kB                   ! 1.16x bigger
2068                     flickr_memory_warning                     11,844kB                   13,784kB                   ! 1.16x bigger
2069                     theverge_memory_warning                   18,516kB                   22,748kB                   ! 1.23x bigger
2070
2071                     <geometric mean>                          12,382kB                   14,644kB                   ! 1.18x bigger
2072                     <arithmetic mean>                         13,005kB                   15,516kB                   ! 1.19x bigger
2073                     <harmonic mean>                           11,813kB                   13,867kB                   ! 1.17x bigger
2074
2075                 MallocBench> ~/webkit/PerformanceTests/MallocBench/run-malloc-benchmarks TC:~/scratch/Build-TCMalloc/Release/ patch:~/webkit/WebKitBuild/Release/
2076
2077                                                         TC                patch                         Δ
2078                 Execution Time:
2079                     churn                            416ms                148ms            ^ 2.81x faster
2080                     list_allocate                    463ms                164ms            ^ 2.82x faster
2081                     tree_allocate                    292ms                127ms             ^ 2.3x faster
2082                     tree_churn                       157ms                120ms            ^ 1.31x faster
2083                     facebook                         327ms                276ms            ^ 1.18x faster
2084                     fragment                         335ms                129ms             ^ 2.6x faster
2085                     fragment_iterate                 344ms                108ms            ^ 3.19x faster
2086                     message_one                      386ms                258ms             ^ 1.5x faster
2087                     message_many                     410ms                154ms            ^ 2.66x faster
2088                     medium                           391ms                245ms             ^ 1.6x faster
2089                     big                              261ms                167ms            ^ 1.56x faster
2090
2091                     <geometric mean>                 332ms                164ms            ^ 2.02x faster
2092                     <arithmetic mean>                344ms                172ms            ^ 1.99x faster
2093                     <harmonic mean>                  317ms                157ms            ^ 2.02x faster
2094
2095         * bmalloc.xcodeproj/project.pbxproj:
2096         * bmalloc/Allocator.cpp:
2097         (bmalloc::Allocator::Allocator): Don't assume that each allocator's
2098         index corresponds with its size. Instead, use the size selection function
2099         explicitly. Now that we have XSmall, some small allocator entries are
2100         unused.
2101
2102         (bmalloc::Allocator::scavenge):
2103         (bmalloc::Allocator::log):
2104         (bmalloc::Allocator::processXSmallAllocatorLog):
2105         (bmalloc::Allocator::allocateSlowCase):
2106         * bmalloc/Allocator.h:
2107         (bmalloc::Allocator::xSmallAllocatorFor):
2108         (bmalloc::Allocator::allocateFastCase):
2109         * bmalloc/Chunk.h:
2110         * bmalloc/Deallocator.cpp:
2111         (bmalloc::Deallocator::scavenge):
2112         (bmalloc::Deallocator::processObjectLog):
2113         (bmalloc::Deallocator::deallocateSlowCase):
2114         (bmalloc::Deallocator::deallocateXSmallLine):
2115         (bmalloc::Deallocator::allocateXSmallLine):
2116         * bmalloc/Deallocator.h:
2117         (bmalloc::Deallocator::deallocateFastCase):
2118         * bmalloc/Heap.cpp:
2119         (bmalloc::Heap::scavenge):
2120         (bmalloc::Heap::scavengeXSmallPages):
2121         (bmalloc::Heap::allocateXSmallLineSlowCase):
2122         * bmalloc/Heap.h:
2123         (bmalloc::Heap::deallocateXSmallLine):
2124         (bmalloc::Heap::allocateXSmallLine):
2125         * bmalloc/LargeChunk.h:
2126         (bmalloc::LargeChunk::get):
2127         (bmalloc::LargeChunk::endTag):
2128         * bmalloc/Line.h:
2129         * bmalloc/MediumAllocator.h:
2130         (bmalloc::MediumAllocator::allocate):
2131         (bmalloc::MediumAllocator::refill):
2132         * bmalloc/ObjectType.cpp:
2133         (bmalloc::objectType):
2134         * bmalloc/ObjectType.h:
2135         (bmalloc::isXSmall):
2136         (bmalloc::isSmall):
2137         (bmalloc::isMedium):
2138         (bmalloc::isLarge):
2139         (bmalloc::isSmallOrMedium): Deleted.
2140         * bmalloc/SegregatedFreeList.h: I boiler-plate copied existing code for
2141         handling small objects. There's probably a reasonable way to share this
2142         code in the future -- I'll look into that once it's stopped changing.
2143
2144         * bmalloc/Sizes.h: Tweaked size classes to make Membuster happy. This
2145         is the main reason things got slower.
2146
2147         * bmalloc/SmallAllocator.h:
2148         (bmalloc::SmallAllocator::allocate):
2149         * bmalloc/SmallTraits.h:
2150         * bmalloc/VMHeap.cpp:
2151         (bmalloc::VMHeap::allocateXSmallChunk):
2152         * bmalloc/VMHeap.h:
2153         (bmalloc::VMHeap::allocateXSmallPage):
2154         (bmalloc::VMHeap::deallocateXSmallPage):
2155         * bmalloc/XSmallAllocator.h: Added.
2156         (bmalloc::XSmallAllocator::isNull):
2157         (bmalloc::XSmallAllocator::canAllocate):
2158         (bmalloc::XSmallAllocator::XSmallAllocator):
2159         (bmalloc::XSmallAllocator::line):
2160         (bmalloc::XSmallAllocator::allocate):
2161         (bmalloc::XSmallAllocator::objectCount):
2162         (bmalloc::XSmallAllocator::derefCount):
2163         (bmalloc::XSmallAllocator::refill):
2164         * bmalloc/XSmallChunk.h: Added.
2165         * bmalloc/XSmallLine.h: Added.
2166         * bmalloc/XSmallPage.h: Added.
2167         * bmalloc/XSmallTraits.h: Added.
2168         * bmalloc/bmalloc.h:
2169         (bmalloc::api::realloc): Boiler-plate copy, as above.
2170
2171 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
2172
2173         MallocBench should scavenge explicitly instead of waiting
2174         https://bugs.webkit.org/show_bug.cgi?id=131661
2175
2176         Reviewed by Andreas Kling.
2177
2178         Added explicit scavenge support to bmalloc. This isn't a memory win,
2179         since bmalloc's per-thread cache is so small. But it makes testing
2180         simpler.
2181
2182         * bmalloc/Allocator.cpp:
2183         (bmalloc::Allocator::~Allocator):
2184         (bmalloc::Allocator::scavenge):
2185         * bmalloc/Allocator.h:
2186         * bmalloc/Cache.cpp:
2187         (bmalloc::Cache::operator new):
2188         (bmalloc::Cache::operator delete):
2189         (bmalloc::Cache::Cache):
2190         (bmalloc::Cache::scavenge):
2191         * bmalloc/Cache.h:
2192         * bmalloc/Deallocator.cpp:
2193         (bmalloc::Deallocator::~Deallocator):
2194         (bmalloc::Deallocator::scavenge):
2195         * bmalloc/Deallocator.h: Factored existing scavenging code into helper
2196         functions, for reuse.
2197
2198         * bmalloc/Heap.cpp:
2199         (bmalloc::sleep):
2200         (bmalloc::Heap::concurrentScavenge):
2201         (bmalloc::Heap::scavenge):
2202         (bmalloc::Heap::scavengeSmallPages):
2203         (bmalloc::Heap::scavengeMediumPages):
2204         (bmalloc::Heap::scavengeLargeRanges):
2205         * bmalloc/Heap.h: Made scavenge sleep duration a parameter. Forced
2206         scavenging -- in response to a benchmark or a low memory warning --
2207         wants to complete as soon as possible, so its sleep duration is 0.
2208
2209         * bmalloc/bmalloc.h:
2210         (bmalloc::api::scavenge):
2211         * bmalloc/mbmalloc.cpp: Exported the scavenge API for MallocBench's use.
2212
2213 2014-04-14  Geoffrey Garen  <ggaren@apple.com>
2214
2215         Use 4kB pages on Mac
2216         https://bugs.webkit.org/show_bug.cgi?id=131658
2217
2218         Reviewed by Sam Weinig.
2219
2220         This reduces memory use a lot on Membuster:
2221
2222                                                                   base                      patch                                Δ
2223                 Execution Time:
2224                     reddit_memory_warning                         18ms                       17ms                   ^ 1.06x faster
2225                     flickr_memory_warning                         34ms                       36ms                   ! 1.06x slower
2226                     theverge_memory_warning                       39ms                       41ms                   ! 1.05x slower
2227
2228                     <geometric mean>                              29ms                       29ms                   ! 1.02x slower
2229                     <arithmetic mean>                             30ms                       31ms                   ! 1.03x slower
2230                     <harmonic mean>                               27ms                       27ms                    ^ 1.0x faster
2231
2232                 Peak Memory:
2233                     reddit_memory_warning                     16,412kB                   16,436kB                    ! 1.0x bigger
2234                     flickr_memory_warning                     30,120kB                   30,184kB                    ! 1.0x bigger
2235                     theverge_memory_warning                   33,408kB                   33,420kB                    ! 1.0x bigger
2236
2237                     <geometric mean>                          25,466kB                   25,499kB                    ! 1.0x bigger
2238                     <arithmetic mean>                         26,647kB                   26,680kB                    ! 1.0x bigger
2239                     <harmonic mean>                           24,181kB                   24,214kB                    ! 1.0x bigger
2240
2241                 Memory at End:
2242                     reddit_memory_warning                      2,404kB                    1,920kB                  ^ 1.25x smaller
2243                     flickr_memory_warning                      3,764kB                    3,072kB                  ^ 1.23x smaller
2244                     theverge_memory_warning                    3,648kB                    3,132kB                  ^ 1.16x smaller
2245
2246                     <geometric mean>                           3,208kB                    2,644kB                  ^ 1.21x smaller
2247                     <arithmetic mean>                          3,272kB                    2,708kB                  ^ 1.21x smaller
2248                     <harmonic mean>                            3,139kB                    2,574kB                  ^ 1.22x smaller
2249
2250
2251         * bmalloc.xcodeproj/project.pbxproj:
2252         * bmalloc/BPlatform.h: Added.
2253         * bmalloc/VMAllocate.h: Only use 16kB pages on iOS because the page size
2254         is 4kB on Mac.
2255
2256 2014-04-14  Alexey Proskuryakov  <ap@apple.com>
2257
2258         Fixed svn:ignore on bmalloc.xcodeproj, it had erroneous leading spaces.
2259
2260         * bmalloc.xcodeproj: Modified property svn:ignore.
2261
2262 2014-04-13  Geoffrey Garen  <ggaren@apple.com>
2263
2264         Fixed some mbmalloc exports
2265         https://bugs.webkit.org/show_bug.cgi?id=131599
2266
2267         Reviewed by Ryosuke Niwa.
2268
2269         * bmalloc.xcodeproj/project.pbxproj: Made some headers a private part
2270         of the project, so we can call them from API.
2271
2272         * bmalloc/mbmalloc.cpp: Marked the mbmalloc functions with default
2273         visibility, so they show up as exported in the .dylib.
2274
2275 2014-04-09  Geoffrey Garen  <ggaren@apple.com>
2276
2277         Put bmalloc headers in the right place
2278         https://bugs.webkit.org/show_bug.cgi?id=131464
2279
2280         Reviewed by Mark Rowe.
2281
2282         * Configurations/bmalloc.xcconfig: Set PRIVATE_HEADERS_FOLDER_PATH to
2283         specify that we don't just want to dump all of our generically-named
2284         headers into /usr/local/include.
2285
2286 2014-04-08  Geoffrey Garen  <ggaren@apple.com>
2287
2288         Made bmalloc more #include friendly
2289         https://bugs.webkit.org/show_bug.cgi?id=131386
2290
2291         Reviewed by Andreas Kling.
2292
2293         Marked a bunch of headers private so they can be used from client code
2294         that #includes bmalloc.h.
2295
2296         Renamed ASSERT macros to BASSERT. This matches their header, which already
2297         had to be renamed, and fixes conflicts with WTF's ASSERT macros.
2298
2299         * bmalloc.xcodeproj/project.pbxproj:
2300         * bmalloc/Allocator.cpp:
2301         (bmalloc::Allocator::allocateSlowCase):
2302         * bmalloc/AsyncTask.h:
2303         (bmalloc::Function>::runSlowCase):
2304         * bmalloc/BAssert.h:
2305         * bmalloc/BoundaryTag.h:
2306         (bmalloc::BoundaryTag::setSize):
2307         * bmalloc/BoundaryTagInlines.h:
2308         (bmalloc::validate):
2309         (bmalloc::BoundaryTag::init):
2310         (bmalloc::BoundaryTag::deallocate):
2311         (bmalloc::BoundaryTag::splitLarge):
2312         (bmalloc::BoundaryTag::allocate):
2313         * bmalloc/Chunk.h:
2314         * bmalloc/Deallocator.cpp:
2315         (bmalloc::Deallocator::processObjectLog):
2316         (bmalloc::Deallocator::deallocateSlowCase):
2317         * bmalloc/Deallocator.h:
2318         (bmalloc::Deallocator::deallocateFastCase):
2319         * bmalloc/FixedVector.h:
2320         (bmalloc::Capacity>::operator):
2321         (bmalloc::Capacity>::push):
2322         (bmalloc::Capacity>::pop):
2323         (bmalloc::Capacity>::shrink):
2324         * bmalloc/Heap.cpp:
2325         (bmalloc::Heap::allocateLarge):
2326         * bmalloc/LargeChunk.h:
2327         (bmalloc::LargeChunk::get):
2328         (bmalloc::LargeChunk::endTag):
2329         * bmalloc/Line.h:
2330         (bmalloc::Line<Traits>::concurrentRef):
2331         (bmalloc::Line<Traits>::deref):
2332         * bmalloc/MediumAllocator.h:
2333         (bmalloc::MediumAllocator::allocate):
2334         * bmalloc/ObjectType.h:
2335         (bmalloc::isSmall):
2336         * bmalloc/Page.h:
2337         (bmalloc::Page<Traits>::ref):
2338         (bmalloc::Page<Traits>::deref):
2339         * bmalloc/PerThread.h:
2340         (bmalloc::PerThread<T>::getSlowCase):
2341         * bmalloc/SegregatedFreeList.cpp:
2342         (bmalloc::SegregatedFreeList::SegregatedFreeList):
2343         (bmalloc::SegregatedFreeList::insert):
2344         * bmalloc/SmallAllocator.h:
2345         (bmalloc::SmallAllocator::allocate):
2346         (bmalloc::SmallAllocator::refill):
2347         * bmalloc/Syscall.h:
2348         * bmalloc/VMAllocate.h:
2349         (bmalloc::vmValidate):
2350         (bmalloc::vmAllocate):
2351         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2352         * bmalloc/Vector.h:
2353         (bmalloc::Vector<T>::operator):
2354         (bmalloc::Vector<T>::pop):
2355         (bmalloc::Vector<T>::shrink):
2356         * bmalloc/XLargeChunk.h:
2357         (bmalloc::XLargeChunk::range):
2358         (bmalloc::XLargeChunk::size):
2359
2360 2014-04-08  Geoffrey Garen  <ggaren@apple.com>
2361
2362         Removed an unused file.
2363
2364         Unreviewed.
2365
2366         * bmalloc/AsyncTask.cpp: Removed.
2367
2368 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2369
2370         Build bmalloc on Mac
2371         https://bugs.webkit.org/show_bug.cgi?id=131333
2372
2373         Reviewed by Mark Rowe.
2374
2375         * Makefile: Added. For make clients.
2376
2377         These files are required for building any project in WebKit. I copied
2378         them from WTF:
2379         * Configurations: Added.
2380         * Configurations/Base.xcconfig: Added.
2381         * Configurations/DebugRelease.xcconfig: Added.
2382         * Configurations/bmalloc.xcconfig: Added.
2383         * Configurations/iOS.xcconfig: Added.
2384         * Configurations/mbmalloc.xcconfig: Added.
2385
2386         * bmalloc.xcodeproj/project.pbxproj: I removed per-project-file stuff
2387         from here because everything is in .xcconfig files now.
2388
2389         I had to fix a bunch of minor warnings, since they're enabled in our
2390         .xcconfig files:
2391
2392         * bmalloc/AsyncTask.h:
2393         (bmalloc::Function>::AsyncTask):
2394         * bmalloc/BAssert.h:
2395         * bmalloc/BoundaryTagInlines.h:
2396         (bmalloc::validate):
2397         * bmalloc/Heap.cpp:
2398         (bmalloc::Heap::Heap):
2399         (bmalloc::Heap::allocateLarge):
2400         (bmalloc::Heap::deallocateLarge):
2401         * bmalloc/Mutex.h:
2402         (bmalloc::Mutex::Mutex): Deleted.
2403         * bmalloc/VMAllocate.h:
2404         (bmalloc::vmValidate):
2405         * bmalloc/mbmalloc.cpp:
2406
2407 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2408
2409         bmalloc: Fixed a leak in the per-thread cache
2410         https://bugs.webkit.org/show_bug.cgi?id=131330
2411
2412         Reviewed by Andreas Kling.
2413
2414         Remember to deallocate our line caches upon thread exit.
2415
2416         * bmalloc/Deallocator.cpp:
2417         (bmalloc::Deallocator::~Deallocator):
2418
2419 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2420
2421         bmalloc: rolled out the tryLock experiment
2422         https://bugs.webkit.org/show_bug.cgi?id=131328
2423
2424         Reviewed by Andreas Kling.
2425
2426         It wasn't a speedup.
2427
2428         * bmalloc.xcodeproj/project.pbxproj:
2429         * bmalloc/Allocator.cpp:
2430         (bmalloc::Allocator::processSmallAllocatorLog):
2431         (bmalloc::Allocator::processMediumAllocatorLog):
2432         * bmalloc/Deallocator.cpp:
2433         (bmalloc::Deallocator::processObjectLog):
2434         (bmalloc::Deallocator::deallocateSlowCase):
2435         (bmalloc::Deallocator::deallocateSmallLine):
2436         (bmalloc::Deallocator::deallocateMediumLine):
2437         * bmalloc/Deallocator.h:
2438         (bmalloc::Deallocator::deallocateFastCase):
2439         * bmalloc/Heap.h:
2440         (bmalloc::Heap::deallocateSmallLine):
2441         (bmalloc::Heap::deallocateMediumLine):
2442         * bmalloc/Line.h:
2443         (bmalloc::Line<Traits>::deref):
2444         * bmalloc/Page.h:
2445         (bmalloc::Page<Traits>::deref):
2446
2447 2014-04-07  Geoffrey Garen  <ggaren@apple.com>
2448
2449         bmalloc
2450         https://bugs.webkit.org/show_bug.cgi?id=131170
2451
2452         Reviewed by Andreas Kling.
2453
2454         Initial commit.
2455
2456         * bmalloc: Added.
2457         * bmalloc.xcodeproj: Added.
2458         * bmalloc.xcodeproj/project.pbxproj: Added.
2459         * bmalloc/Algorithm.h: Added.
2460         (bmalloc::max):
2461         (bmalloc::min):
2462         (bmalloc::mask):
2463         (bmalloc::test):
2464         (bmalloc::roundUpToMultipleOf):
2465         (bmalloc::roundDownToMultipleOf):
2466         (bmalloc::sizeOf):
2467         (bmalloc::bitCount):
2468         (bmalloc::isPowerOfTwo):
2469         * bmalloc/Allocator.cpp: Added.
2470         (bmalloc::Allocator::Allocator):
2471         (bmalloc::Allocator::~Allocator):
2472         (bmalloc::Allocator::log):
2473         (bmalloc::Allocator::processSmallAllocatorLog):
2474         (bmalloc::Allocator::processMediumAllocatorLog):
2475         (bmalloc::Allocator::allocateLarge):
2476         (bmalloc::Allocator::allocateXLarge):
2477         (bmalloc::Allocator::allocateMedium):
2478         (bmalloc::Allocator::allocateSlowCase):
2479         * bmalloc/Allocator.h: Added.
2480         (bmalloc::Allocator::smallAllocatorFor):
2481         (bmalloc::Allocator::allocateFastCase):
2482         (bmalloc::Allocator::allocate):
2483         * bmalloc/AsyncTask.cpp: Added.
2484         (bmalloc::AsyncTask<Function>::runSlowCase):
2485         (bmalloc::AsyncTask<Function>::pthreadEntryPoint):
2486         (bmalloc::AsyncTask<Function>::entryPoint):
2487         * bmalloc/AsyncTask.h: Added.
2488         (bmalloc::Function>::AsyncTask):
2489         (bmalloc::Function>::join):
2490         (bmalloc::Function>::run):
2491         (bmalloc::Function>::runSlowCase):
2492         (bmalloc::Function>::pthreadEntryPoint):
2493         (bmalloc::Function>::entryPoint):
2494         * bmalloc/BAssert.h: Added.
2495         * bmalloc/BeginTag.h: Added.
2496         (bmalloc::BeginTag::isInFreeList):
2497         * bmalloc/BoundaryTag.h: Added.
2498         (bmalloc::BoundaryTag::isXLarge):
2499         (bmalloc::BoundaryTag::setXLarge):
2500         (bmalloc::BoundaryTag::isFree):
2501         (bmalloc::BoundaryTag::setFree):
2502         (bmalloc::BoundaryTag::isEnd):
2503         (bmalloc::BoundaryTag::setEnd):
2504         (bmalloc::BoundaryTag::hasPhysicalPages):
2505         (bmalloc::BoundaryTag::setHasPhysicalPages):
2506         (bmalloc::BoundaryTag::isNull):
2507         (bmalloc::BoundaryTag::clear):
2508         (bmalloc::BoundaryTag::size):
2509         (bmalloc::BoundaryTag::setSize):
2510         (bmalloc::BoundaryTag::prev):
2511         (bmalloc::BoundaryTag::next):
2512         * bmalloc/BoundaryTagInlines.h: Added.
2513         (bmalloc::validate):
2514         (bmalloc::validatePrev):
2515         (bmalloc::validateNext):
2516         (bmalloc::BoundaryTag::init):
2517         (bmalloc::BoundaryTag::mergeLargeLeft):
2518         (bmalloc::BoundaryTag::mergeLargeRight):
2519         (bmalloc::BoundaryTag::mergeLarge):
2520         (bmalloc::BoundaryTag::deallocate):
2521         (bmalloc::BoundaryTag::splitLarge):
2522         (bmalloc::BoundaryTag::allocate):
2523         * bmalloc/Cache.cpp: Added.
2524         (bmalloc::Cache::operator new):
2525         (bmalloc::Cache::operator delete):
2526         (bmalloc::Cache::Cache):
2527         (bmalloc::Cache::allocateSlowCase):
2528         (bmalloc::Cache::allocateSlowCaseNullCache):
2529         (bmalloc::Cache::deallocateSlowCase):
2530         (bmalloc::Cache::deallocateSlowCaseNullCache):
2531         * bmalloc/Cache.h: Added.
2532         (bmalloc::Cache::allocator):
2533         (bmalloc::Cache::deallocator):
2534         (bmalloc::Cache::allocateFastCase):
2535         (bmalloc::Cache::deallocateFastCase):
2536         (bmalloc::Cache::allocate):
2537         (bmalloc::Cache::deallocate):
2538         * bmalloc/Chunk.h: Added.
2539         (bmalloc::Chunk::begin):
2540         (bmalloc::Chunk::end):
2541         (bmalloc::Chunk::lines):
2542         (bmalloc::Chunk::pages):
2543         * bmalloc/Deallocator.cpp: Added.
2544         (bmalloc::Deallocator::Deallocator):
2545         (bmalloc::Deallocator::~Deallocator):
2546         (bmalloc::Deallocator::deallocateLarge):
2547         (bmalloc::Deallocator::deallocateXLarge):
2548         (bmalloc::Deallocator::processObjectLog):
2549         (bmalloc::Deallocator::deallocateSlowCase):
2550         (bmalloc::Deallocator::deallocateSmallLine):
2551         (bmalloc::Deallocator::allocateSmallLine):
2552         (bmalloc::Deallocator::deallocateMediumLine):
2553         (bmalloc::Deallocator::allocateMediumLine):
2554         * bmalloc/Deallocator.h: Added.
2555         (bmalloc::Deallocator::deallocateFastCase):
2556         (bmalloc::Deallocator::deallocate):
2557         * bmalloc/EndTag.h: Added.
2558         (bmalloc::EndTag::operator=):
2559         * bmalloc/FixedVector.h: Added.
2560         (bmalloc::FixedVector::begin):
2561         (bmalloc::FixedVector::end):
2562         (bmalloc::FixedVector::size):
2563         (bmalloc::FixedVector::capacity):
2564         (bmalloc::FixedVector::clear):
2565         (bmalloc::FixedVector::isEmpty):
2566         (bmalloc::Capacity>::FixedVector):
2567         (bmalloc::Capacity>::operator):
2568         (bmalloc::Capacity>::push):
2569         (bmalloc::Capacity>::pop):
2570         (bmalloc::Capacity>::shrink):
2571         * bmalloc/Heap.cpp: Added.
2572         (bmalloc::sleep):
2573         (bmalloc::Heap::Heap):
2574         (bmalloc::Heap::concurrentScavenge):
2575         (bmalloc::Heap::scavengeSmallPages):
2576         (bmalloc::Heap::scavengeMediumPages):
2577         (bmalloc::Heap::scavengeLargeRanges):
2578         (bmalloc::Heap::allocateSmallLineSlowCase):
2579         (bmalloc::Heap::allocateMediumLineSlowCase):
2580         (bmalloc::Heap::allocateXLarge):
2581         (bmalloc::Heap::deallocateXLarge):
2582         (bmalloc::Heap::allocateLarge):
2583         (bmalloc::Heap::deallocateLarge):
2584         * bmalloc/Heap.h: Added.
2585         (bmalloc::Heap::deallocateSmallLine):
2586         (bmalloc::Heap::allocateSmallLine):
2587         (bmalloc::Heap::deallocateMediumLine):
2588         (bmalloc::Heap::allocateMediumLine):
2589         * bmalloc/Inline.h: Added.
2590         * bmalloc/LargeChunk.h: Added.
2591         (bmalloc::LargeChunk::begin):
2592         (bmalloc::LargeChunk::end):
2593         (bmalloc::LargeChunk::create):
2594         (bmalloc::LargeChunk::get):
2595         (bmalloc::LargeChunk::beginTag):
2596         (bmalloc::LargeChunk::endTag):
2597         * bmalloc/Line.h: Added.
2598         (bmalloc::Line<Traits>::begin):
2599         (bmalloc::Line<Traits>::end):
2600         (bmalloc::Line<Traits>::concurrentRef):
2601         (bmalloc::Line<Traits>::deref):
2602         * bmalloc/MediumAllocator.h: Added.
2603         (bmalloc::MediumAllocator::isNull):
2604         (bmalloc::MediumAllocator::MediumAllocator):
2605         (bmalloc::MediumAllocator::line):
2606         (bmalloc::MediumAllocator::allocate):
2607         (bmalloc::MediumAllocator::derefCount):
2608         (bmalloc::MediumAllocator::refill):
2609         * bmalloc/MediumChunk.h: Added.
2610         * bmalloc/MediumLine.h: Added.
2611         * bmalloc/MediumPage.h: Added.
2612         * bmalloc/MediumTraits.h: Added.
2613         * bmalloc/Mutex.cpp: Added.
2614         (bmalloc::Mutex::lockSlowCase):
2615         * bmalloc/Mutex.h: Added.
2616         (bmalloc::Mutex::Mutex):
2617         (bmalloc::Mutex::try_lock):
2618         (bmalloc::Mutex::lock):
2619         (bmalloc::Mutex::unlock):
2620         * bmalloc/ObjectType.cpp: Added.
2621         (bmalloc::objectType):
2622         * bmalloc/ObjectType.h: Added.
2623         (bmalloc::isSmallOrMedium):
2624         (bmalloc::isSmall):
2625         * bmalloc/Page.h: Added.
2626         (bmalloc::Page<Traits>::ref):
2627         (bmalloc::Page<Traits>::deref):
2628         (bmalloc::Page<Traits>::refCount):
2629         * bmalloc/PerProcess.h: Added.
2630         (bmalloc::PerProcess::mutex):
2631         (bmalloc::PerProcess<T>::getFastCase):
2632         (bmalloc::PerProcess<T>::get):
2633         (bmalloc::PerProcess<T>::getSlowCase):
2634         * bmalloc/PerThread.h: Added.
2635         (bmalloc::PerThreadStorage<Cache>::get):
2636         (bmalloc::PerThreadStorage<Cache>::init):
2637         (bmalloc::PerThreadStorage::get):
2638         (bmalloc::PerThreadStorage::init):
2639         (bmalloc::PerThread<T>::getFastCase):
2640         (bmalloc::PerThread<T>::get):
2641         (bmalloc::PerThread<T>::destructor):
2642         (bmalloc::PerThread<T>::getSlowCase):
2643         * bmalloc/Range.h: Added.
2644         (bmalloc::Range::Range):
2645         (bmalloc::Range::begin):
2646         (bmalloc::Range::end):
2647         (bmalloc::Range::size):
2648         (bmalloc::Range::operator!):
2649         (bmalloc::Range::operator<):
2650         * bmalloc/SegregatedFreeList.cpp: Added.
2651         (bmalloc::SegregatedFreeList::SegregatedFreeList):
2652         (bmalloc::SegregatedFreeList::insert):
2653         (bmalloc::SegregatedFreeList::takeGreedy):
2654         (bmalloc::SegregatedFreeList::take):
2655         * bmalloc/SegregatedFreeList.h: Added.
2656         * bmalloc/Sizes.h: Added.
2657         * bmalloc/SmallAllocator.h: Added.
2658         (bmalloc::SmallAllocator::isNull):
2659         (bmalloc::SmallAllocator::canAllocate):
2660         (bmalloc::SmallAllocator::SmallAllocator):
2661         (bmalloc::SmallAllocator::line):
2662         (bmalloc::SmallAllocator::allocate):
2663         (bmalloc::SmallAllocator::objectCount):
2664         (bmalloc::SmallAllocator::derefCount):
2665         (bmalloc::SmallAllocator::refill):
2666         * bmalloc/SmallChunk.h: Added.
2667         * bmalloc/SmallLine.h: Added.
2668         * bmalloc/SmallPage.h: Added.
2669         * bmalloc/SmallTraits.h: Added.
2670         * bmalloc/Syscall.h: Added.
2671         * bmalloc/VMAllocate.h: Added.
2672         (bmalloc::vmSize):
2673         (bmalloc::vmValidate):
2674         (bmalloc::vmAllocate):
2675         (bmalloc::vmDeallocate):
2676         (bmalloc::vmDeallocatePhysicalPages):
2677         (bmalloc::vmAllocatePhysicalPages):
2678         (bmalloc::vmDeallocatePhysicalPagesSloppy):
2679         (bmalloc::vmAllocatePhysicalPagesSloppy):
2680         * bmalloc/VMHeap.cpp: Added.
2681         (bmalloc::VMHeap::VMHeap):
2682         (bmalloc::VMHeap::allocateSmallChunk):
2683         (bmalloc::VMHeap::allocateMediumChunk):
2684         (bmalloc::VMHeap::allocateLargeChunk):
2685         * bmalloc/VMHeap.h: Added.
2686         (bmalloc::VMHeap::allocateSmallPage):
2687         (bmalloc::VMHeap::allocateMediumPage):
2688         (bmalloc::VMHeap::allocateLargeRange):
2689         (bmalloc::VMHeap::deallocateSmallPage):
2690         (bmalloc::VMHeap::deallocateMediumPage):
2691         (bmalloc::VMHeap::deallocateLargeRange):
2692         * bmalloc/Vector.h: Added.
2693         (bmalloc::Vector::begin):
2694         (bmalloc::Vector::end):
2695         (bmalloc::Vector::size):
2696         (bmalloc::Vector::capacity):
2697         (bmalloc::Vector::last):
2698         (bmalloc::Vector::pop):
2699         (bmalloc::Vector<T>::Vector):
2700         (bmalloc::Vector<T>::~Vector):
2701         (bmalloc::Vector<T>::operator):
2702         (bmalloc::Vector<T>::push):
2703         (bmalloc::Vector<T>::pop):
2704         (bmalloc::Vector<T>::shrink):
2705         (bmalloc::Vector<T>::reallocateBuffer):
2706         (bmalloc::Vector<T>::shrinkCapacity):
2707         (bmalloc::Vector<T>::growCapacity):
2708         * bmalloc/XLargeChunk.h: Added.
2709         (bmalloc::XLargeChunk::get):
2710         (bmalloc::XLargeChunk::begin):
2711         (bmalloc::XLargeChunk::XLargeChunk):
2712         (bmalloc::XLargeChunk::create):
2713         (bmalloc::XLargeChunk::destroy):
2714         (bmalloc::XLargeChunk::range):
2715         (bmalloc::XLargeChunk::size):
2716         * bmalloc/bmalloc.h: Added.
2717         (bmalloc::api::malloc):
2718         (bmalloc::api::free):
2719         (bmalloc::api::realloc):
2720         * bmalloc/mbmalloc.cpp: Added.
2721