reflow comments in wtf/allocator

third_party/WebKit/Source/wtf/allocator/PartitionAlloc.h

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 48 matching lines @@
 // And for partitionAllocGeneric():
 // - Multi-threaded use against a single partition is ok; locking is handled.
 // - Allocations of any arbitrary size can be handled (subject to a limit of
 // INT_MAX bytes for security reasons).
 // - Bucketing is by approximate size, for example an allocation of 4000 bytes
 // might be placed into a 4096-byte bucket. Bucket sizes are chosen to try and
 // keep worst-case waste to ~10%.
 //
 // The allocators are designed to be extremely fast, thanks to the following
 // properties and design:
-// - Just two single (reasonably predicatable) branches in the hot / fast path for
-// both allocating and (significantly) freeing.
+// - Just two single (reasonably predicatable) branches in the hot / fast path
+//   for both allocating and (significantly) freeing.
 // - A minimal number of operations in the hot / fast path, with the slow paths
-// in separate functions, leading to the possibility of inlining.
+//   in separate functions, leading to the possibility of inlining.
 // - Each partition page (which is usually multiple physical pages) has a
-// metadata structure which allows fast mapping of free() address to an
-// underlying bucket.
+//   metadata structure which allows fast mapping of free() address to an
+//   underlying bucket.
 // - Supports a lock-free API for fast performance in single-threaded cases.
 // - The freelist for a given bucket is split across a number of partition
-// pages, enabling various simple tricks to try and minimize fragmentation.
+//   pages, enabling various simple tricks to try and minimize fragmentation.
 // - Fine-grained bucket sizes leading to less waste and better packing.
 //
 // The following security properties could be investigated in the future:
 // - Per-object bucketing (instead of per-size) is mostly available at the API,
 // but not used yet.
 // - No randomness of freelist entries or bucket position.
 // - Better checking for wild pointers in free().
 // - Better freelist masking function to guarantee fault on 32-bit.
 
 #include "wtf/Assertions.h"
@@ skipping 53 matching lines @@
 
 // We reserve virtual address space in 2MB chunks (aligned to 2MB as well).
 // These chunks are called "super pages". We do this so that we can store
 // metadata in the first few pages of each 2MB aligned section. This leads to
 // a very fast free(). We specifically choose 2MB because this virtual address
 // block represents a full but single PTE allocation on ARM, ia32 and x64.
 //
 // The layout of the super page is as follows. The sizes below are the same
 // for 32 bit and 64 bit.
 //
-//   | Guard page (4KB) | Metadata page (4KB) | Guard pages (8KB) | Slot span | Slot span | ... | Slot span | Guard page (4KB) |
+//   | Guard page (4KB) | Metadata page (4KB) | Guard pages (8KB) | Slot span |
+//   Slot span | ... | Slot span | Guard page (4KB) |
 //
 //   - Each slot span is a contiguous range of one or more PartitionPages.
 //   - The metadata page has the following format. Note that the PartitionPage
 //     that is not at the head of a slot span is "unused". In other words,
 //     the metadata for the slot span is stored only in the first PartitionPage
 //     of the slot span. Metadata accesses to other PartitionPages are
 //     redirected to the first PartitionPage.
 //
-//     | SuperPageExtentEntry (32B) | PartitionPage of slot span 1 (32B, used) | PartitionPage of slot span 1 (32B, unused) | PartitionPage of slot span 1 (32B, unused) | PartitionPage of slot span 2 (32B, used) | PartitionPage of slot span 3 (32B, used) | ... | PartitionPage of slot span N (32B, unused) |
+//     | SuperPageExtentEntry (32B) |
+//     PartitionPage of slot span 1 (32B, used) |
+//     PartitionPage of slot span 1 (32B, unused) |
+//     PartitionPage of slot span 1 (32B, unused) |
+//     PartitionPage of slot span 2 (32B, used) |
+//     PartitionPage of slot span 3 (32B, used) | ... |
+//     PartitionPage of slot span N (32B, unused) |
 //
-// A direct mapped page has a similar layout to fake it looking like a super page:
+// A direct mapped page has a similar layout to fake it looking like a super
+// page:
 //
-//     | Guard page (4KB) | Metadata page (4KB) | Guard pages (8KB) | Direct mapped object | Guard page (4KB) |
+//     | Guard page (4KB) | Metadata page (4KB) | Guard pages (8KB) | Direct
+//     mapped object | Guard page (4KB) |
 //
 //    - The metadata page has the following layout:
 //
-//     | SuperPageExtentEntry (32B) | PartitionPage (32B) | PartitionBucket (32B) | PartitionDirectMapExtent (8B) |
+//     | SuperPageExtentEntry (32B) | PartitionPage (32B) |
+//     PartitionBucket (32B) | PartitionDirectMapExtent (8B) |

[dcheng, 2016/10/01 17:55:23]

Nit: I feel like this is kind of hard to read once it's wrapped, it almost looks
like it's ORing flags together.

Though it's a more extensive change, maybe we could put the wrapped things in
boxes?

   ,------------------------------------------.
   |        SuperPageExtentEntry(32B)         |
   |------------------------------------------|
   | PartitionPage of slot span 1 (32B, used) |


etc?

[Nico, 2016/10/01 19:47:01]

Did that but without the ----- lines. wdty?

 static const size_t kSuperPageShift = 21;  // 2MB
 static const size_t kSuperPageSize = 1 << kSuperPageShift;
 static const size_t kSuperPageOffsetMask = kSuperPageSize - 1;
 static const size_t kSuperPageBaseMask = ~kSuperPageOffsetMask;
 static const size_t kNumPartitionPagesPerSuperPage =
     kSuperPageSize / kPartitionPageSize;
 
 static const size_t kPageMetadataShift = 5;  // 32 bytes per partition page.
 static const size_t kPageMetadataSize = 1 << kPageMetadataShift;
 
 // The following kGeneric* constants apply to the generic variants of the API.
 // The "order" of an allocation is closely related to the power-of-two size of
 // the allocation. More precisely, the order is the bit index of the
 // most-significant-bit in the allocation size, where the bit numbers starts
 // at index 1 for the least-significant-bit.
 // In terms of allocation sizes, order 0 covers 0, order 1 covers 1, order 2
 // covers 2->3, order 3 covers 4->7, order 4 covers 8->15.
 static const size_t kGenericMinBucketedOrder = 4;  // 8 bytes.
 static const size_t kGenericMaxBucketedOrder =
     20;  // Largest bucketed order is 1<<(20-1) (storing 512KB -> almost 1MB)
 static const size_t kGenericNumBucketedOrders =
     (kGenericMaxBucketedOrder - kGenericMinBucketedOrder) + 1;
-static const size_t kGenericNumBucketsPerOrderBits =
-    3;  // Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144, 160, ..., 240
+// Eight buckets per order (for the higher orders), e.g. order 8 is 128, 144,
+// 160, ..., 240:
+static const size_t kGenericNumBucketsPerOrderBits = 3;
 static const size_t kGenericNumBucketsPerOrder =
     1 << kGenericNumBucketsPerOrderBits;
 static const size_t kGenericNumBuckets =
     kGenericNumBucketedOrders * kGenericNumBucketsPerOrder;
 static const size_t kGenericSmallestBucket = 1
                                              << (kGenericMinBucketedOrder - 1);
 static const size_t kGenericMaxBucketSpacing =
     1 << ((kGenericMaxBucketedOrder - 1) - kGenericNumBucketsPerOrderBits);
 static const size_t kGenericMaxBucketed =
     (1 << (kGenericMaxBucketedOrder - 1)) +
@@ skipping 54 matching lines @@
 // empty list or it _may_ leave it on the active list until a future list scan.
 // - malloc() _may_ scan the active page list in order to fulfil the request.
 // If it does this, full, empty and decommitted pages encountered will be
 // booted out of the active list. If there are no suitable active pages found,
 // an empty or decommitted page (if one exists) will be pulled from the empty
 // list on to the active list.
 struct PartitionPage {
   PartitionFreelistEntry* freelistHead;
   PartitionPage* nextPage;
   PartitionBucket* bucket;
-  int16_t
-      numAllocatedSlots;  // Deliberately signed, 0 for empty or decommitted page, -n for full pages.

[dcheng, 2016/10/01 17:55:23]

Nit: just place this on the prior line?

[Nico, 2016/10/01 19:47:00]

Done.

[Nico, 2016/10/01 19:47:00]

Done.

+  int16_t numAllocatedSlots;  // Deliberately signed, 0 for empty or decommitted
+                              // page, -n for full pages.
   uint16_t numUnprovisionedSlots;
   uint16_t pageOffset;
   int16_t emptyCacheIndex;  // -1 if not in the empty cache.
 };
 
 struct PartitionBucket {
   PartitionPage* activePagesHead;  // Accessed most in hot path => goes first.
   PartitionPage* emptyPagesHead;
   PartitionPage* decommittedPagesHead;
   uint32_t slotSize;
@@ skipping 15 matching lines @@
   PartitionDirectMapExtent* nextExtent;
   PartitionDirectMapExtent* prevExtent;
   PartitionBucket* bucket;
   size_t mapSize;  // Mapped size, not including guard pages and meta-data.
 };
 
 struct WTF_EXPORT PartitionRootBase {
   size_t totalSizeOfCommittedPages;
   size_t totalSizeOfSuperPages;
   size_t totalSizeOfDirectMappedPages;
-  // Invariant: totalSizeOfCommittedPages <= totalSizeOfSuperPages + totalSizeOfDirectMappedPages.
+  // Invariant: totalSizeOfCommittedPages <=
+  //                totalSizeOfSuperPages + totalSizeOfDirectMappedPages.
   unsigned numBuckets;
   unsigned maxAllocation;
   bool initialized;
   char* nextSuperPage;
   char* nextPartitionPage;
   char* nextPartitionPageEnd;
   PartitionSuperPageExtentEntry* currentExtent;
   PartitionSuperPageExtentEntry* firstExtent;
   PartitionDirectMapExtent* directMapList;
   PartitionPage* globalEmptyPageRing[kMaxFreeableSpans];
@@ skipping 16 matching lines @@
 struct PartitionRoot : public PartitionRootBase {
   // The PartitionAlloc templated class ensures the following is correct.
   ALWAYS_INLINE PartitionBucket* buckets() {
     return reinterpret_cast<PartitionBucket*>(this + 1);
   }
   ALWAYS_INLINE const PartitionBucket* buckets() const {
     return reinterpret_cast<const PartitionBucket*>(this + 1);
   }
 };
 
-// Never instantiate a PartitionRootGeneric directly, instead use PartitionAllocatorGeneric.
+// Never instantiate a PartitionRootGeneric directly, instead use
+// PartitionAllocatorGeneric.
 struct PartitionRootGeneric : public PartitionRootBase {
   SpinLock lock;
   // Some pre-computed constants.
   size_t orderIndexShifts[kBitsPerSizet + 1];
   size_t orderSubIndexMasks[kBitsPerSizet + 1];
   // The bucket lookup table lets us map a size_t to a bucket quickly.
-  // The trailing +1 caters for the overflow case for very large allocation sizes.
+  // The trailing +1 caters for the overflow case for very large allocation
+  // sizes.

[dcheng, 2016/10/01 17:55:23]

Nit: Merge the next line

[Nico, 2016/10/01 19:47:00]

Done.

   // It is one flat array instead of a 2D array because in the 2D world, we'd
   // need to index array[blah][max+1] which risks undefined behavior.
   PartitionBucket*
       bucketLookups[((kBitsPerSizet + 1) * kGenericNumBucketsPerOrder) + 1];
   PartitionBucket buckets[kGenericNumBuckets];
 };
 
 // Flags for partitionAllocGenericFlags.
 enum PartitionAllocFlags {
   PartitionAllocReturnNull = 1 << 0,
 };
 
 // Struct used to retrieve total memory usage of a partition. Used by
 // PartitionStatsDumper implementation.
 struct PartitionMemoryStats {
   size_t totalMmappedBytes;        // Total bytes mmaped from the system.
   size_t totalCommittedBytes;      // Total size of commmitted pages.
   size_t totalResidentBytes;       // Total bytes provisioned by the partition.
   size_t totalActiveBytes;         // Total active bytes in the partition.
   size_t totalDecommittableBytes;  // Total bytes that could be decommitted.
   size_t totalDiscardableBytes;    // Total bytes that could be discarded.
 };
 
 // Struct used to retrieve memory statistics about a partition bucket. Used by
 // PartitionStatsDumper implementation.
 struct PartitionBucketMemoryStats {
-  bool isValid;  // Used to check if the stats is valid.
-  bool
-      isDirectMap;  // True if this is a direct mapping; size will not be unique.
-  uint32_t bucketSlotSize;  // The size of the slot in bytes.
-  uint32_t
-      allocatedPageSize;  // Total size the partition page allocated from the system.
-  uint32_t activeBytes;         // Total active bytes used in the bucket.
-  uint32_t residentBytes;       // Total bytes provisioned in the bucket.
-  uint32_t decommittableBytes;  // Total bytes that could be decommitted.
-  uint32_t discardableBytes;    // Total bytes that could be discarded.
-  uint32_t numFullPages;        // Number of pages with all slots allocated.
-  uint32_t
-      numActivePages;  // Number of pages that have at least one provisioned slot.
-  uint32_t
-      numEmptyPages;  // Number of pages that are empty but not decommitted.
-  uint32_t
-      numDecommittedPages;  // Number of pages that are empty and decommitted.
+  bool isValid;      // Used to check if the stats is valid.
+  bool isDirectMap;  // True if this is a direct mapping; size will not be
+                     // unique.
+  uint32_t bucketSlotSize;       // The size of the slot in bytes.
+  uint32_t allocatedPageSize;    // Total size the partition page allocated from
+                                 // the system.
+  uint32_t activeBytes;          // Total active bytes used in the bucket.
+  uint32_t residentBytes;        // Total bytes provisioned in the bucket.
+  uint32_t decommittableBytes;   // Total bytes that could be decommitted.
+  uint32_t discardableBytes;     // Total bytes that could be discarded.
+  uint32_t numFullPages;         // Number of pages with all slots allocated.
+  uint32_t numActivePages;       // Number of pages that have at least one
+                                 // provisioned slot.
+  uint32_t numEmptyPages;        // Number of pages that are empty
+                                 // but not decommitted.
+  uint32_t numDecommittedPages;  // Number of pages that are empty
+                                 // and decommitted.
 };
 
 // Interface that is passed to partitionDumpStats and
 // partitionDumpStatsGeneric for using the memory statistics.
 class WTF_EXPORT PartitionStatsDumper {
  public:
   // Called to dump total memory used by partition, once per partition.
   virtual void partitionDumpTotals(const char* partitionName,
                                    const PartitionMemoryStats*) = 0;
 
@@ skipping 168 matching lines @@
       reinterpret_cast<char*>(pointerAsUint & kSuperPageBaseMask);
   uintptr_t partitionPageIndex =
       (pointerAsUint & kSuperPageOffsetMask) >> kPartitionPageShift;
   // Index 0 is invalid because it is the metadata and guard area and
   // the last index is invalid because it is a guard page.
   ASSERT(partitionPageIndex);
   ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1);
   PartitionPage* page = reinterpret_cast<PartitionPage*>(
       partitionSuperPageToMetadataArea(superPagePtr) +
       (partitionPageIndex << kPageMetadataShift));
-  // Partition pages in the same slot span can share the same page object. Adjust for that.
+  // Partition pages in the same slot span can share the same page object.
+  // Adjust for that.
   size_t delta = page->pageOffset << kPageMetadataShift;
   page =
       reinterpret_cast<PartitionPage*>(reinterpret_cast<char*>(page) - delta);
   return page;
 }
 
 ALWAYS_INLINE void* partitionPageToPointer(const PartitionPage* page) {
   uintptr_t pointerAsUint = reinterpret_cast<uintptr_t>(page);
   uintptr_t superPageOffset = (pointerAsUint & kSuperPageOffsetMask);
   ASSERT(superPageOffset > kSystemPageSize);
   ASSERT(superPageOffset < kSystemPageSize + (kNumPartitionPagesPerSuperPage *
                                               kPageMetadataSize));
   uintptr_t partitionPageIndex =
       (superPageOffset - kSystemPageSize) >> kPageMetadataShift;
-  // Index 0 is invalid because it is the metadata area and the last index is invalid because it is a guard page.
+  // Index 0 is invalid because it is the metadata area and the last index is
+  // invalid because it is a guard page.
   ASSERT(partitionPageIndex);
   ASSERT(partitionPageIndex < kNumPartitionPagesPerSuperPage - 1);
   uintptr_t superPageBase = (pointerAsUint & kSuperPageBaseMask);
   void* ret = reinterpret_cast<void*>(
       superPageBase + (partitionPageIndex << kPartitionPageShift));
   return ret;
 }
 
 ALWAYS_INLINE PartitionPage* partitionPointerToPage(void* ptr) {
   PartitionPage* page = partitionPointerToPageNoAlignmentCheck(ptr);
@@ skipping 126 matching lines @@
     slotSize = rawSize;
   partitionCookieCheckValue(ptr);
   partitionCookieCheckValue(reinterpret_cast<char*>(ptr) + slotSize -
                             kCookieSize);
   memset(ptr, kFreedByte, slotSize);
 #endif
   ASSERT(page->numAllocatedSlots);
   PartitionFreelistEntry* freelistHead = page->freelistHead;
   ASSERT(!freelistHead || partitionPointerIsValid(freelistHead));
   SECURITY_CHECK(ptr != freelistHead);  // Catches an immediate double free.
+  // Look for double free one level deeper in debug.
   ASSERT_WITH_SECURITY_IMPLICATION(
-      !freelistHead ||
-      ptr !=
-          partitionFreelistMask(
-              freelistHead
-                  ->next));  // Look for double free one level deeper in debug.
+      !freelistHead || ptr != partitionFreelistMask(freelistHead->next));
   PartitionFreelistEntry* entry = static_cast<PartitionFreelistEntry*>(ptr);
   entry->next = partitionFreelistMask(freelistHead);
   page->freelistHead = entry;
   --page->numAllocatedSlots;
   if (UNLIKELY(page->numAllocatedSlots <= 0)) {
     partitionFreeSlowPath(page);
   } else {
     // All single-slot allocations must go through the slow path to
     // correctly update the size metadata.
     ASSERT(partitionPageGetRawSize(page) == 0);
@@ skipping 173 matching lines @@
 using WTF::partitionAlloc;
 using WTF::partitionFree;
 using WTF::partitionAllocGeneric;
 using WTF::partitionFreeGeneric;
 using WTF::partitionReallocGeneric;
 using WTF::partitionAllocActualSize;
 using WTF::partitionAllocSupportsGetSize;
 using WTF::partitionAllocGetSize;
 
 #endif  // WTF_PartitionAlloc_h