PartitionAlloc: simplify PartitionPage structure some more.

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 81 matching lines @@
         double wasteRatio = (double) waste / (double) pageSize;
         if (wasteRatio < bestWasteRatio) {
             bestWasteRatio = wasteRatio;
             bestPages = i;
         }
     }
     ASSERT(bestPages > 0);
     return bestPages;
 }
 
-static ALWAYS_INLINE void partitionPageMarkFree(PartitionPage* page)
-{
-    ASSERT(!partitionPageIsFree(page));
-    page->flags |= kPartitionPageFlagFree;
-}
-
 static void parititonAllocBaseInit(PartitionRootBase* root)
 {
     ASSERT(!root->initialized);
 
     spinLockLock(&PartitionRootBase::gInitializedLock);
     if (!PartitionRootBase::gInitialized) {
         PartitionRootBase::gInitialized = true;
         // We mark the seed page as free to make sure it is skipped by our
         // logic to find a new active page.
-        partitionPageMarkFree(&PartitionRootBase::gSeedPage);
         PartitionRootBase::gPagedBucket.activePagesHead = &PartitionRootGeneric::gSeedPage;
     }
     spinLockUnlock(&PartitionRootBase::gInitializedLock);
 
     root->initialized = true;
     root->totalSizeOfSuperPages = 0;
     root->nextSuperPage = 0;
     root->nextPartitionPage = 0;
     root->nextPartitionPageEnd = 0;
     root->firstExtent = 0;
@@ skipping 108 matching lines @@
     // which tries to overflow to a non-existant order.
     *bucketPtr = &PartitionRootGeneric::gPagedBucket;
 }
 
 static bool partitionAllocShutdownBucket(PartitionBucket* bucket)
 {
     // Failure here indicates a memory leak.
     bool noLeaks = !bucket->numFullPages;
     PartitionPage* page = bucket->activePagesHead;
     while (page) {
-        if (!partitionPageIsFree(page) && page->numAllocatedSlots)
+        if (page->numAllocatedSlots)
             noLeaks = false;
-        page = page->activePageNext;
+        page = page->next;
     }
 
     return noLeaks;
 }
 
 static void partitionAllocBaseShutdown(PartitionRootBase* root)
 {
     ASSERT(root->initialized);
     root->initialized = false;
 
@@ skipping 127 matching lines @@
 }
 
 static ALWAYS_INLINE size_t partitionBucketPartitionPages(const PartitionBucket* bucket)
 {
     return (bucket->numSystemPagesPerSlotSpan + (kNumSystemPagesPerPartitionPage - 1)) / kNumSystemPagesPerPartitionPage;
 }
 
 static ALWAYS_INLINE void partitionPageReset(PartitionPage* page, PartitionBucket* bucket)
 {
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
-    page->flags = 0;
     page->numAllocatedSlots = 0;
     page->numUnprovisionedSlots = partitionBucketSlots(bucket);
     ASSERT(page->numUnprovisionedSlots);
     page->bucket = bucket;
+    page->next = 0;
     // NULLing the freelist is not strictly necessary but it makes an ASSERT in partitionPageFillFreelist simpler.
-    partitionPageSetFreelistHead(page, 0);
+    page->freelistHead = 0;
     page->pageOffset = 0;
     size_t numPartitionPages = partitionBucketPartitionPages(bucket);
     size_t i;
     char* pageCharPtr = reinterpret_cast<char*>(page);
     for (i = 1; i < numPartitionPages; ++i) {
         pageCharPtr += kPageMetadataSize;
         PartitionPage* secondaryPage = reinterpret_cast<PartitionPage*>(pageCharPtr);
         secondaryPage->pageOffset = i;
     }
 }
 
 static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(PartitionPage* page)
 {
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
     size_t numSlots = page->numUnprovisionedSlots;
     ASSERT(numSlots);
     PartitionBucket* bucket = page->bucket;
     // We should only get here when _every_ slot is either used or unprovisioned.
     // (The third state is "on the freelist". If we have a non-empty freelist, we should not get here.)
     ASSERT(numSlots + page->numAllocatedSlots == partitionBucketSlots(bucket));
     // Similarly, make explicitly sure that the freelist is empty.
-    ASSERT(!partitionPageFreelistHead(page));
+    ASSERT(!page->freelistHead);
+    ASSERT(page->numAllocatedSlots >= 0);
 
     size_t size = bucket->slotSize;
     char* base = reinterpret_cast<char*>(partitionPageToPointer(page));
     char* returnObject = base + (size * page->numAllocatedSlots);
     char* firstFreelistPointer = returnObject + size;
     char* firstFreelistPointerExtent = firstFreelistPointer + sizeof(PartitionFreelistEntry*);
     // Our goal is to fault as few system pages as possible. We calculate the
     // page containing the "end" of the returned slot, and then allow freelist
     // pointers to be written up to the end of that page.
     char* subPageLimit = reinterpret_cast<char*>((reinterpret_cast<uintptr_t>(firstFreelistPointer) + kSystemPageOffsetMask) & kSystemPageBaseMask);
@@ skipping 16 matching lines @@
     // We always return an object slot -- that's the +1 below.
     // We do not neccessarily create any new freelist entries, because we cross sub page boundaries frequently for large bucket sizes.
     ASSERT(numNewFreelistEntries + 1 <= numSlots);
     numSlots -= (numNewFreelistEntries + 1);
     page->numUnprovisionedSlots = numSlots;
     page->numAllocatedSlots++;
 
     if (LIKELY(numNewFreelistEntries)) {
         char* freelistPointer = firstFreelistPointer;
         PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>(freelistPointer);
-        partitionPageSetFreelistHead(page, entry);
+        page->freelistHead = entry;
         while (--numNewFreelistEntries) {
             freelistPointer += size;
             PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreelistEntry*>(freelistPointer);
             entry->next = partitionFreelistMask(nextEntry);
             entry = nextEntry;
         }
         entry->next = partitionFreelistMask(0);
     } else {
-        partitionPageSetFreelistHead(page, 0);
+        page->freelistHead = 0;
     }
     return returnObject;
 }
 
 // This helper function scans the active page list for a suitable new active
 // page, starting at the current active page, and optionally skipping the
 // current active page as a candidate.
 // When it finds a suitable new active page (one that has free slots), it is
 // set as the new active page and true is returned. If there is no suitable new
 // active page, false is returned.
 static ALWAYS_INLINE bool partitionSetNewActivePage(PartitionBucket* bucket, bool currentPageOk)
 {
     PartitionPage* page = bucket->activePagesHead;
+    if (page == &PartitionRootBase::gSeedPage) {
+        ASSERT(!page->next);
+        return false;
+    }
+
     if (!currentPageOk)
-        page = page->activePageNext;
+        page = page->next;
 
-    for (; page; page = page->activePageNext) {
+    for (; page; page = page->next) {
         ASSERT(page->bucket == bucket->activePagesHead->bucket);
 
-        // Skip over free pages. We need this check first so that we can trust
-        // that the page union field really containts a freelist pointer.
-        if (UNLIKELY(partitionPageIsFree(page)))
-            continue;
-
         // Page is usable if it has something on the freelist, or unprovisioned
         // slots that can be turned into a freelist.
-        if (LIKELY(partitionPageFreelistHead(page) != 0) || LIKELY(page->numUnprovisionedSlots)) {
+        if (LIKELY(page->freelistHead != 0) || LIKELY(page->numUnprovisionedSlots)) {
             bucket->activePagesHead = page;
             return true;
         }
-        // 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 == static_cast<int>(partitionBucketSlots(bucket)));
-        page->numAllocatedSlots = -page->numAllocatedSlots;
-        ++bucket->numFullPages;
+
+        ASSERT(page->numAllocatedSlots >= 0);
+        if (LIKELY(page->numAllocatedSlots == 0)) {
+            // We hit a free page, so shepherd it on to the free page list.
+            page->next = bucket->freePagesHead;
+            bucket->freePagesHead = page;
+        } else {
+            // 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 == static_cast<int>(partitionBucketSlots(bucket)));
+            page->numAllocatedSlots = -page->numAllocatedSlots;
+            ++bucket->numFullPages;
+        }
     }
 
-    bucket->activePagesHead->activePageNext = 0;
+    bucket->activePagesHead->next = 0;
     return false;
 }
 
-static ALWAYS_INLINE void partitionPageSetFreePageNext(PartitionPage* page, PartitionPage* nextFree)
-{
-    ASSERT(partitionPageIsFree(page));
-    page->u.freePageNext = nextFree;
-}
-
-static ALWAYS_INLINE PartitionPage* partitionPageFreePageNext(PartitionPage* page)
-{
-    ASSERT(partitionPageIsFree(page));
-    return page->u.freePageNext;
-}
-
 static ALWAYS_INLINE bool partitionBucketIsPaged(PartitionBucket* bucket)
 {
     return !bucket->slotSize;
 }
 
 void* partitionAllocSlowPath(PartitionRootBase* root, size_t size, PartitionBucket* bucket)
 {
     // The slow path is called when the freelist is empty.
-    ASSERT(!partitionPageFreelistHead(bucket->activePagesHead));
+    ASSERT(!bucket->activePagesHead->freelistHead);
 
     // For the partitionAllocGeneric API, we have a bunch of buckets marked
     // as special cases. We bounce them through to the slow path so that we
     // can still have a blazing fast hot path due to lack of corner-case
     // branches.
     if (UNLIKELY(partitionBucketIsPaged(bucket))) {
         RELEASE_ASSERT(size <= INT_MAX);
         ASSERT(size > kGenericMaxBucketed);
         // This will be going away real soon now.
         return fastMalloc(size);
     }
 
     // First, look for a usable page in the existing active pages list.
     // Change active page, accepting the current page as a candidate.
     if (LIKELY(partitionSetNewActivePage(bucket, true))) {
         PartitionPage* newPage = bucket->activePagesHead;
-        if (LIKELY(partitionPageFreelistHead(newPage) != 0)) {
-            PartitionFreelistEntry* ret = partitionPageFreelistHead(newPage);
-            partitionPageSetFreelistHead(newPage, partitionFreelistMask(ret->next));
+        if (LIKELY(newPage->freelistHead != 0)) {
+            PartitionFreelistEntry* ret = newPage->freelistHead;
+            newPage->freelistHead = partitionFreelistMask(ret->next);
             newPage->numAllocatedSlots++;
             return ret;
         }
         ASSERT(newPage->numUnprovisionedSlots);
         return partitionPageAllocAndFillFreelist(newPage);
     }
 
     // Second, look in our list of freed but reserved pages.
     PartitionPage* newPage = bucket->freePagesHead;
     if (LIKELY(newPage != 0)) {
         ASSERT(newPage != &PartitionRootGeneric::gSeedPage);
-        bucket->freePagesHead = partitionPageFreePageNext(newPage);
+        ASSERT(!newPage->freelistHead);
+        ASSERT(!newPage->numAllocatedSlots);
+        ASSERT(!newPage->numUnprovisionedSlots);
+        bucket->freePagesHead = newPage->next;
     } else {
         // Third. If we get here, we need a brand new page.
         size_t numPartitionPages = partitionBucketPartitionPages(bucket);
         void* rawNewPage = partitionAllocPartitionPages(root, numPartitionPages);
         // Skip the alignment check because it depends on page->bucket, which is not yet set.
         newPage = partitionPointerToPageNoAlignmentCheck(rawNewPage);
     }
 
-    newPage->activePageNext = 0;
     partitionPageReset(newPage, bucket);
     bucket->activePagesHead = newPage;
     return partitionPageAllocAndFillFreelist(newPage);
 }
 
-static ALWAYS_INLINE void partitionPutPageOnFreelist(PartitionPage* page, PartitionBucket* bucket)
+static ALWAYS_INLINE void partitionFreePage(PartitionPage* page)
 {
+    ASSERT(page->freelistHead);
+    ASSERT(!page->numAllocatedSlots);
     partitionUnusePage(page);
-    // We actually leave the freed page in the active list as well as
-    // putting it on the free list. We'll evict it from the active list soon
-    // enough in partitionAllocSlowPath. 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.
-    partitionPageMarkFree(page);
-    partitionPageSetFreePageNext(page, bucket->freePagesHead);
-    bucket->freePagesHead = page;
+    // We actually leave the freed page in the active list. We'll sweep it on
+    // to the free 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;
 }
 
 void partitionFreeSlowPath(PartitionPage* page)
 {
     PartitionBucket* bucket = page->bucket;
     ASSERT(page != &PartitionRootGeneric::gSeedPage);
     ASSERT(bucket->activePagesHead != &PartitionRootGeneric::gSeedPage);
     if (LIKELY(page->numAllocatedSlots == 0)) {
         // Page became fully unused.
         // If it's the current page, change it!
         if (LIKELY(page == bucket->activePagesHead)) {
             // Change active page, rejecting the current page as a candidate.
             if (!partitionSetNewActivePage(bucket, false)) {
                 // We do not free the last active page in a bucket.
                 // To do so is a serious performance issue as we can get into
                 // a repeating state change between 0 and 1 objects of a given
                 // size allocated; and each state change incurs either a system
                 // call or a page fault, or more.
-                ASSERT(!page->activePageNext);
+                ASSERT(!page->next);
                 return;
             }
+            // Link the to-be-freed page back in after the new current page, to
+            // avoid losing a reference to it.
+            PartitionPage* currentPage = bucket->activePagesHead;
+            page->next = currentPage->next;
+            currentPage->next = page;
         }
-        partitionPutPageOnFreelist(page, bucket);
+        partitionFreePage(page);
     } else {
         // Ensure that the page is full. That's the only valid case if we
         // arrive here.
         ASSERT(page->numAllocatedSlots < 0);
         page->numAllocatedSlots = -page->numAllocatedSlots - 2;
         ASSERT(page->numAllocatedSlots == static_cast<int>(partitionBucketSlots(bucket) - 1));
         // Fully used page became partially used. It must be put back on the
         // non-full page list. Also make it the current page to increase the
         // chances of it being filled up again. The old current page will be
         // the next page.
-        page->activePageNext = bucket->activePagesHead;
+        page->next = bucket->activePagesHead;
         bucket->activePagesHead = page;
         --bucket->numFullPages;
         // Special case: for a partition page with just a single slot, it may
         // now be empty and we want to run it through the empty logic.
         if (UNLIKELY(page->numAllocatedSlots == 0))
             partitionFreeSlowPath(page);
         // Note: there's an opportunity here to look to see if the old active
         // page is now freeable.
     }
 }
@@ skipping 90 matching lines @@
     for (i = 0; i < root.numBuckets; ++i) {
         const PartitionBucket& bucket = root.buckets()[i];
         if (bucket.activePagesHead == &PartitionRootGeneric::gSeedPage && !bucket.freePagesHead && !bucket.numFullPages) {
             // Empty bucket with no freelist or full pages. Skip reporting it.
             continue;
         }
         size_t numFreePages = 0;
         PartitionPage* freePages = bucket.freePagesHead;
         while (freePages) {
             ++numFreePages;
-            freePages = partitionPageFreePageNext(freePages);
+            freePages = freePages->next;
         }
         size_t bucketSlotSize = bucket.slotSize;
         size_t bucketNumSlots = partitionBucketSlots(&bucket);
         size_t bucketUsefulStorage = bucketSlotSize * bucketNumSlots;
         size_t bucketPageSize = bucket.numSystemPagesPerSlotSpan * kSystemPageSize;
         size_t bucketWaste = bucketPageSize - bucketUsefulStorage;
         size_t numActiveBytes = bucket.numFullPages * bucketUsefulStorage;
         size_t numResidentBytes = bucket.numFullPages * bucketPageSize;
         size_t numFreeableBytes = 0;
         size_t numActivePages = 0;
         const PartitionPage* page = bucket.activePagesHead;
         do {
             if (page != &PartitionRootGeneric::gSeedPage) {
                 ++numActivePages;
                 numActiveBytes += (page->numAllocatedSlots * bucketSlotSize);
                 size_t pageBytesResident = (bucketNumSlots - page->numUnprovisionedSlots) * bucketSlotSize;
                 // Round up to system page size.
                 pageBytesResident = (pageBytesResident + kSystemPageOffsetMask) & kSystemPageBaseMask;
                 numResidentBytes += pageBytesResident;
                 if (!page->numAllocatedSlots)
                     numFreeableBytes += pageBytesResident;
             }
-            page = page->activePageNext;
+            page = page->next;
         } while (page != bucket.activePagesHead);
         totalLive += numActiveBytes;
         totalResident += numResidentBytes;
         totalFreeable += numFreeableBytes;
         printf("bucket size %zu (pageSize %zu waste %zu): %zu alloc/%zu commit/%zu freeable bytes, %zu/%zu/%zu full/active/free pages\n", bucketSlotSize, bucketPageSize, bucketWaste, numActiveBytes, numResidentBytes, numFreeableBytes, static_cast<size_t>(bucket.numFullPages), numActivePages, numFreePages);
     }
     printf("total live: %zu bytes\n", totalLive);
     printf("total resident: %zu bytes\n", totalResident);
     printf("total freeable: %zu bytes\n", totalFreeable);
     fflush(stdout);
 }
 
 #endif // !NDEBUG
 
 } // namespace WTF