Source/wtf/PartitionAllocTest.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
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "wtf/PartitionAlloc.h"

#include "wtf/CryptographicallyRandomNumber.h"
#include <gtest/gtest.h>
#include <stdlib.h>
#include <string.h>

#if OS(LINUX) && CPU(X86_64) && defined(NDEBUG)

namespace {

static PartitionRoot root;

static const int kTestAllocSize = sizeof(void*);

static void RandomNumberSource(unsigned char* buf, size_t len)
{
    memset(buf, '\0', len);
}

static void TestSetup()
{
    WTF::setRandomSource(RandomNumberSource);
    partitionAllocInit(&root);
}

static void TestShutdown()
{
    partitionAllocShutdown(&root);
}

static WTF::PartitionPageHeader* GetFullPage()
{
    size_t bucketIdx = kTestAllocSize >> WTF::kBucketShift;
    WTF::PartitionBucket* bucket = &root.buckets[bucketIdx];
    size_t numSlots = (WTF::kPageSize - sizeof(WTF::PartitionPageHeader)) / kTestAllocSize;
    void* first = 0;
    void* last = 0;
    size_t i;
    for (i = 0; i < numSlots; ++i) {
        void* ptr = partitionAlloc(&root, kTestAllocSize);
        EXPECT_TRUE(ptr);
        if (!i)
            first = ptr;
        else if (i == numSlots - 1)
            last = ptr;
    }
    EXPECT_EQ(reinterpret_cast<size_t>(first) & WTF::kPageMask, reinterpret_cast<size_t>(last) & WTF::kPageMask);
    EXPECT_EQ(numSlots, static_cast<size_t>(bucket->currPage->numAllocatedSlots));
    EXPECT_EQ(0, bucket->currPage->freelistHead);
    return bucket->currPage;
}

static void FreeFullPage(WTF::PartitionPageHeader* page)
{
    size_t numSlots = (WTF::kPageSize - sizeof(WTF::PartitionPageHeader)) / kTestAllocSize;
    EXPECT_EQ(numSlots, static_cast<size_t>(abs(page->numAllocatedSlots)));
    char* ptr = reinterpret_cast<char*>(page);
    ptr += sizeof(WTF::PartitionPageHeader);
    size_t i;
    for (i = 0; i < numSlots; ++i) {
        partitionFree(ptr);
        ptr += kTestAllocSize;
    }
    EXPECT_EQ(0, page->numAllocatedSlots);
}

// Check that the most basic of allocate / free pairs work.
TEST(WTF_PartitionAlloc, Basic)
{
    TestSetup();
    size_t bucketIdx = kTestAllocSize >> WTF::kBucketShift;
    WTF::PartitionBucket* bucket = &root.buckets[bucketIdx];

    EXPECT_EQ(0, bucket->freePages);
    EXPECT_EQ(&bucket->seedPage, bucket->currPage);
    EXPECT_EQ(&bucket->seedPage, bucket->currPage->next);
    EXPECT_EQ(&bucket->seedPage, bucket->currPage->prev);

    void* ptr = partitionAlloc(&root, kTestAllocSize);
    EXPECT_TRUE(ptr);
    EXPECT_EQ(sizeof(WTF::PartitionPageHeader), reinterpret_cast<size_t>(ptr) & ~WTF::kPageMask);

    partitionFree(ptr);
    // Expect that a just-freed page doesn't get tossed to the freelist.
    EXPECT_EQ(0, bucket->freePages);

    TestShutdown();
}

// Test multiple allocations, and freelist handling.
TEST(WTF_PartitionAlloc, MultiAlloc)
{
    TestSetup();

    char* ptr1 = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    char* ptr2 = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    EXPECT_TRUE(ptr1);
    EXPECT_TRUE(ptr2);
    ptrdiff_t diff = ptr2 - ptr1;
    EXPECT_EQ(kTestAllocSize, diff);

    // Check that we re-use the just-freed slot.
    partitionFree(ptr2);
    ptr2 = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    EXPECT_TRUE(ptr2);
    diff = ptr2 - ptr1;
    EXPECT_EQ(kTestAllocSize, diff);
    partitionFree(ptr1);
    ptr1 = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    EXPECT_TRUE(ptr1);
    diff = ptr2 - ptr1;
    EXPECT_EQ(kTestAllocSize, diff);

    char* ptr3 = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    EXPECT_TRUE(ptr3);
    diff = ptr3 - ptr1;
    EXPECT_EQ(kTestAllocSize * 2, diff);

    partitionFree(ptr1);
    partitionFree(ptr2);
    partitionFree(ptr3);

    TestShutdown();
}

// Test a bucket with multiple pages.
TEST(WTF_PartitionAlloc, MultiPages)
{
    TestSetup();
    size_t bucketIdx = kTestAllocSize >> WTF::kBucketShift;
    WTF::PartitionBucket* bucket = &root.buckets[bucketIdx];

    WTF::PartitionPageHeader* page = GetFullPage();
    FreeFullPage(page);
    EXPECT_EQ(0, bucket->freePages);

    page = GetFullPage();
    WTF::PartitionPageHeader* page2 = GetFullPage();

    EXPECT_EQ(page2, bucket->currPage);

    // Fully free the non-current page, it should be freelisted.
    FreeFullPage(page);
    EXPECT_EQ(0, page->numAllocatedSlots);
    EXPECT_TRUE(bucket->freePages);
    EXPECT_EQ(page, bucket->freePages->page);
    EXPECT_EQ(page2, bucket->currPage);

    // Allocate a new page, it should pull from the freelist.
    page = GetFullPage();
    EXPECT_FALSE(bucket->freePages);
    EXPECT_EQ(page, bucket->currPage);

    FreeFullPage(page);
    FreeFullPage(page2);
    EXPECT_EQ(0, page->numAllocatedSlots);
    EXPECT_EQ(0, page2->numAllocatedSlots);

    TestShutdown();
}

// Test some finer aspects of internal page transitions.
TEST(WTF_PartitionAlloc, PageTransitions)
{
    TestSetup();
    size_t bucketIdx = kTestAllocSize >> WTF::kBucketShift;
    WTF::PartitionBucket* bucket = &root.buckets[bucketIdx];

    WTF::PartitionPageHeader* page1 = GetFullPage();
    WTF::PartitionPageHeader* page2 = GetFullPage();
    EXPECT_EQ(page2, bucket->currPage);
    EXPECT_EQ(page1, bucket->seedPage.next);
    // Allocating another page at this point should cause us to scan over page1
    // (which is both full and NOT our current page), and evict it from the
    // freelist. Older code had a O(n^2) condition due to failure to do this.
    WTF::PartitionPageHeader* page3 = GetFullPage();
    EXPECT_EQ(page3, bucket->currPage);
    EXPECT_EQ(page2, bucket->seedPage.next);
    EXPECT_EQ(page3, bucket->seedPage.next->next);
    EXPECT_EQ(&bucket->seedPage, bucket->seedPage.next->next->next);

    // Work out a pointer into page2 and free it.
    char* ptr = reinterpret_cast<char*>(page2) + sizeof(WTF::PartitionPageHeader);
    partitionFree(ptr);
    // Trying to allocate at this time should cause us to cycle around to page2
    // and find the recently freed slot.
    char* newPtr = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    EXPECT_EQ(ptr, newPtr);
    EXPECT_EQ(page2, bucket->currPage);

    // Work out a pointer into page1 and free it. This should pull the page
    // back into the ring list of available pages.
    ptr = reinterpret_cast<char*>(page1) + sizeof(WTF::PartitionPageHeader);
    partitionFree(ptr);
    // This allocation should be satisfied by page1.
    newPtr = reinterpret_cast<char*>(partitionAlloc(&root, kTestAllocSize));
    EXPECT_EQ(ptr, newPtr);
    EXPECT_EQ(page1, bucket->currPage);

    FreeFullPage(page3);
    FreeFullPage(page2);
    FreeFullPage(page1);

    TestShutdown();
}

} // namespace

#endif // OS(LINUX) && CPU(X86_64)