PartitionAlloc: improve clarity of page state checks.

Source/wtf/PartitionAlloc.cpp

 /*
  * 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 303 matching lines @@
 static NEVER_INLINE void partitionExcessiveAllocationSize()
 {
     IMMEDIATE_CRASH();
 }
 
 static NEVER_INLINE void partitionBucketFull()
 {
     IMMEDIATE_CRASH();
 }
 
-static bool partitionPageStateIsEmpty(const PartitionPage* page)
+static bool ALWAYS_INLINE partitionPageStateIsActive(const PartitionPage* page)
 {
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
-    return !page->numAllocatedSlots;
+    ASSERT(!page->pageOffset);
+    return (page->numAllocatedSlots && (page->freelistHead || page->numUnprovisionedSlots));

[haraken, 2015/06/24 00:51:52]

page->numAllocatedSlots => page->numAllocatedSlots > 0

Just to confirm: If page->numAllocatedSlots > 0 but 'page->freelistHead ||
page->numUnprovisionedSlots' is false, it is a full page, right?

 }
 
-static bool partitionPageStateIsDecommitted(const PartitionPage* page)
+static bool ALWAYS_INLINE partitionPageStateIsFull(const PartitionPage* page)

[haraken, 2015/06/24 00:51:51]

This method is a bit confusing, since it returns false for a full page that has
already been removed from the active page list.

I'm OK in this CL, but it would be great if we can clean up the page state
transitions a bit more in the future. For example, it looks hacky to represent a
full page by storing a negative value in numAllocatedSlots.

struct PartitionPage {
  ...;
  uint16_t pageOffset;  // We won't need 16 bit for this.
  int16_t emptyCacheIndex;  // Ditto.
};

By saving the bits, we'll be able to have space to explicitly represent the
PageState.

 {
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
-    bool ret = !page->numAllocatedSlots && !page->freelistHead;
+    ASSERT(!page->pageOffset);
+    bool ret = (page->numAllocatedSlots == partitionBucketSlots(page->bucket));
+    if (ret) {
+        ASSERT(!page->freelistHead);
+        ASSERT(!page->numUnprovisionedSlots);
+    }
+    return ret;
+}
+
+static bool ALWAYS_INLINE partitionPageStateIsEmpty(const PartitionPage* page)
+{
+    ASSERT(page != &PartitionRootGeneric::gSeedPage);
+    ASSERT(!page->pageOffset);
+    return (!page->numAllocatedSlots && page->freelistHead);
+}
+
+static bool ALWAYS_INLINE partitionPageStateIsDecommitted(const PartitionPage* page)
+{
+    ASSERT(page != &PartitionRootGeneric::gSeedPage);
+    ASSERT(!page->pageOffset);
+    bool ret = (!page->numAllocatedSlots && !page->freelistHead);
     if (ret) {
         ASSERT(!page->numUnprovisionedSlots);
         ASSERT(page->emptyCacheIndex == -1);
-        ASSERT(!page->pageOffset);
     }
     return ret;
 }
 
 static void partitionIncreaseCommittedPages(PartitionRootBase* root, size_t len)
 {
     root->totalSizeOfCommittedPages += len;
     ASSERT(root->totalSizeOfCommittedPages <= root->totalSizeOfSuperPages + root->totalSizeOfDirectMappedPages);
 }
 
@@ skipping 97 matching lines @@
         ASSERT(ret >= currentExtent->superPageBase && ret < currentExtent->superPagesEnd);
     }
     return ret;
 }
 
 static ALWAYS_INLINE uint16_t partitionBucketPartitionPages(const PartitionBucket* bucket)
 {
     return (bucket->numSystemPagesPerSlotSpan + (kNumSystemPagesPerPartitionPage - 1)) / kNumSystemPagesPerPartitionPage;
 }
 
-static ALWAYS_INLINE void partitionPageReset(PartitionPage* page, PartitionBucket* bucket)
+static ALWAYS_INLINE void partitionPageReset(PartitionPage* page)
 {
-    ASSERT(page->bucket == bucket);
     ASSERT(partitionPageStateIsDecommitted(page));
 
-    page->numUnprovisionedSlots = partitionBucketSlots(bucket);
+    page->numUnprovisionedSlots = partitionBucketSlots(page->bucket);
     ASSERT(page->numUnprovisionedSlots);
 
     page->nextPage = nullptr;
 }
 
 static ALWAYS_INLINE void partitionPageSetup(PartitionPage* page, PartitionBucket* bucket)
 {
     // The bucket never changes. We set it up once.
     page->bucket = bucket;
     page->emptyCacheIndex = -1;
 
-    partitionPageReset(page, bucket);
+    partitionPageReset(page);
 
     // If this page has just a single slot, do not set up page offsets for any
     // page metadata other than the first one. This ensures that attempts to
     // touch invalid page metadata fail.
     if (page->numUnprovisionedSlots == 1)
         return;
 
     uint16_t numPartitionPages = partitionBucketPartitionPages(bucket);
     char* pageCharPtr = reinterpret_cast<char*>(page);
     for (uint16_t i = 1; i < numPartitionPages; ++i) {
@@ skipping 91 matching lines @@
 
     PartitionPage* nextPage;
 
     for (; page; page = nextPage) {
         nextPage = page->nextPage;
         ASSERT(page->bucket == bucket);
         ASSERT(page != bucket->emptyPagesHead);
         ASSERT(page != bucket->decommittedPagesHead);
 
         // Deal with empty and decommitted pages.
-        if (UNLIKELY(!page->numAllocatedSlots)) {
-            ASSERT(partitionPageStateIsEmpty(page));
-            if (UNLIKELY(!page->freelistHead)) {
-                ASSERT(partitionPageStateIsDecommitted(page));
-                page->nextPage = bucket->decommittedPagesHead;
-                bucket->decommittedPagesHead = page;
-            } else {
-                page->nextPage = bucket->emptyPagesHead;
-                bucket->emptyPagesHead = page;
-            }
-        } else if (LIKELY(page->freelistHead != 0) || LIKELY(page->numUnprovisionedSlots)) {
+        if (LIKELY(partitionPageStateIsActive(page))) {
             // This page is usable because it has freelist entries, or has
             // unprovisioned slots we can create freelist entries from.
             bucket->activePagesHead = page;
             return true;
+        }
+        if (LIKELY(partitionPageStateIsEmpty(page))) {
+            page->nextPage = bucket->emptyPagesHead;
+            bucket->emptyPagesHead = page;
+        } else if (LIKELY(partitionPageStateIsDecommitted(page))) {
+            page->nextPage = bucket->decommittedPagesHead;
+            bucket->decommittedPagesHead = page;
         } else {
+            ASSERT(partitionPageStateIsFull(page));
             // If we get here, we found a full page. Skip over it too, and also
             // tag it as full (via a negative value). We need it tagged so that
             // free'ing can tell, and move it back into the active page list.
-            ASSERT(page->numAllocatedSlots == partitionBucketSlots(bucket));
             page->numAllocatedSlots = -page->numAllocatedSlots;
             ++bucket->numFullPages;
             // numFullPages is a uint16_t for efficient packing so guard against
             // overflow to be safe.
             if (UNLIKELY(!bucket->numFullPages))
                 partitionBucketFull();
             // Not necessary but might help stop accidents.
             page->nextPage = 0;
         }
     }
@@ skipping 146 matching lines @@
         ASSERT(bucket->activePagesHead == &PartitionRootGeneric::gSeedPage);
         if (size > kGenericMaxDirectMapped) {
             if (returnNull)
                 return nullptr;
             partitionExcessiveAllocationSize();
         }
         newPage = partitionDirectMap(root, flags, size);
     } else if (LIKELY(partitionSetNewActivePage(bucket))) {
         // First, did we find an active page in the active pages list?
         newPage = bucket->activePagesHead;
-        ASSERT(newPage != &PartitionRootGeneric::gSeedPage);
+        ASSERT(partitionPageStateIsActive(newPage));
     } else if (LIKELY(bucket->emptyPagesHead != nullptr) || LIKELY(bucket->decommittedPagesHead != nullptr)) {
         // Second, look in our lists of empty and decommitted pages.
         // Check empty pages first, which are preferred, but beware that an
         // empty page might have been decommitted.
         while (LIKELY((newPage = bucket->emptyPagesHead) != nullptr)) {
-            ASSERT(partitionPageStateIsEmpty(newPage));
+            ASSERT(newPage->bucket == bucket);
+            ASSERT(partitionPageStateIsEmpty(newPage) || partitionPageStateIsDecommitted(newPage));
             bucket->emptyPagesHead = newPage->nextPage;
             // Accept the empty page unless it got decommitted.
             if (newPage->freelistHead) {
                 newPage->nextPage = nullptr;
                 break;
             }
             ASSERT(partitionPageStateIsDecommitted(newPage));
             newPage->nextPage = bucket->decommittedPagesHead;
             bucket->decommittedPagesHead = newPage;
         }
         if (UNLIKELY(!newPage) && LIKELY(bucket->decommittedPagesHead != nullptr)) {
             newPage = bucket->decommittedPagesHead;
+            ASSERT(newPage->bucket == bucket);
+            ASSERT(partitionPageStateIsDecommitted(newPage));
             bucket->decommittedPagesHead = newPage->nextPage;
-            ASSERT(partitionPageStateIsDecommitted(newPage));
             void* addr = partitionPageToPointer(newPage);
             partitionRecommitSystemPages(root, addr, partitionBucketBytes(newPage->bucket));
-            partitionPageReset(newPage, bucket);
+            partitionPageReset(newPage);
         }
         ASSERT(newPage);
     } else {
         // Third. If we get here, we need a brand new page.
         uint16_t numPartitionPages = partitionBucketPartitionPages(bucket);
         void* rawPages = partitionAllocPartitionPages(root, flags, numPartitionPages);
         if (LIKELY(rawPages != nullptr)) {
             newPage = partitionPointerToPageNoAlignmentCheck(rawPages);
             partitionPageSetup(newPage, bucket);
         }
@@ skipping 22 matching lines @@
         return entry;
     }
     // Otherwise, we need to build the freelist.
     ASSERT(newPage->numUnprovisionedSlots);
     return partitionPageAllocAndFillFreelist(newPage);
 }
 
 static ALWAYS_INLINE void partitionDecommitPage(PartitionRootBase* root, PartitionPage* page)
 {
     ASSERT(partitionPageStateIsEmpty(page));
-    ASSERT(page->freelistHead);
     ASSERT(!partitionBucketIsDirectMapped(page->bucket));
     void* addr = partitionPageToPointer(page);
     partitionDecommitSystemPages(root, addr, partitionBucketBytes(page->bucket));
 
     // We actually leave the decommitted page in the active list. We'll sweep
     // it on to the decommitted page list when we next walk the active page
     // list.
     // Pulling this trick enables us to use a singly-linked page list for all
     // cases, which is critical in keeping the page metadata structure down to
     // 32 bytes in size.
     page->freelistHead = 0;
     page->numUnprovisionedSlots = 0;

[haraken, 2015/06/24 00:51:52]

Shall we add ASSERT(partitionPageStateIsDecommitted(page)) ?

 }
 
 static void partitionDecommitPageIfPossible(PartitionRootBase* root, PartitionPage* page)
 {
     ASSERT(page->emptyCacheIndex >= 0);
     ASSERT(static_cast<unsigned>(page->emptyCacheIndex) < kMaxFreeableSpans);
     ASSERT(page == root->globalEmptyPageRing[page->emptyCacheIndex]);
-    if (!page->numAllocatedSlots && page->freelistHead) {
-        // The page is still empty, and not decommitted, so _really_ decommit
-        // it.
+    if (partitionPageStateIsEmpty(page))
         partitionDecommitPage(root, page);
-    }
+
     page->emptyCacheIndex = -1;
 }
 
 static ALWAYS_INLINE void partitionRegisterEmptyPage(PartitionPage* page)
 {
     ASSERT(partitionPageStateIsEmpty(page));
     PartitionRootBase* root = partitionPageToRoot(page);
 
     // If the page is already registered as empty, give it another life.
     if (page->emptyCacheIndex != -1) {
@@ skipping 312 matching lines @@
     if (rawSize)
         statsOut->activeBytes += static_cast<uint32_t>(rawSize);
     else
         statsOut->activeBytes += (page->numAllocatedSlots * statsOut->bucketSlotSize);
 
     size_t pageBytesResident = partitionRoundUpToSystemPage((bucketNumSlots - page->numUnprovisionedSlots) * statsOut->bucketSlotSize);
     statsOut->residentBytes += pageBytesResident;
     if (partitionPageStateIsEmpty(page)) {
         statsOut->decommittableBytes += pageBytesResident;
         ++statsOut->numEmptyPages;
-    } else if (page->numAllocatedSlots == bucketNumSlots) {
+    } else if (partitionPageStateIsFull(page)) {
         ++statsOut->numFullPages;
     } else {
-        ASSERT(page->numAllocatedSlots > 0);
+        ASSERT(partitionPageStateIsActive(page));
         ++statsOut->numActivePages;
     }
 }
 
 static void partitionDumpBucketStats(PartitionBucketMemoryStats* statsOut, const PartitionBucket* bucket)
 {
     ASSERT(!partitionBucketIsDirectMapped(bucket));
     statsOut->isValid = false;
     // If the active page list is empty (== &PartitionRootGeneric::gSeedPage),
     // the bucket might still need to be reported if it has a list of empty,
     // decommitted or full pages.
     if (bucket->activePagesHead == &PartitionRootGeneric::gSeedPage && !bucket->emptyPagesHead && !bucket->decommittedPagesHead && !bucket->numFullPages)
         return;
 
     memset(statsOut, '\0', sizeof(*statsOut));
     statsOut->isValid = true;
     statsOut->isDirectMap = false;
     statsOut->numFullPages = static_cast<size_t>(bucket->numFullPages);
     statsOut->bucketSlotSize = bucket->slotSize;
     uint16_t bucketNumSlots = partitionBucketSlots(bucket);
     size_t bucketUsefulStorage = statsOut->bucketSlotSize * bucketNumSlots;
     statsOut->allocatedPageSize = partitionBucketBytes(bucket);
     statsOut->activeBytes = bucket->numFullPages * bucketUsefulStorage;
     statsOut->residentBytes = bucket->numFullPages * statsOut->allocatedPageSize;
 
     for (const PartitionPage* page = bucket->emptyPagesHead; page; page = page->nextPage) {
-        ASSERT(partitionPageStateIsEmpty(page));
+        ASSERT(partitionPageStateIsEmpty(page) || partitionPageStateIsDecommitted(page));
         partitionDumpPageStats(statsOut, page);
     }
     for (const PartitionPage* page = bucket->decommittedPagesHead; page; page = page->nextPage) {
         ASSERT(partitionPageStateIsDecommitted(page));
         partitionDumpPageStats(statsOut, page);
     }
 
     if (bucket->activePagesHead != &PartitionRootGeneric::gSeedPage) {
         for (const PartitionPage* page = bucket->activePagesHead; page; page = page->nextPage) {
             ASSERT(page != &PartitionRootGeneric::gSeedPage);
@@ skipping 67 matching lines @@
     // partitionsDumpBucketStats is called after collecting stats because it
     // can use PartitionAlloc to allocate and this can affect the statistics.
     for (size_t i = 0; i < partitionNumBuckets; ++i) {
         if (memoryStats[i].isValid)
             partitionStatsDumper->partitionsDumpBucketStats(partitionName, &memoryStats[i]);
     }
 }
 
 } // namespace WTF