PartitionAlloc randomization of the freelist and double free protection

partition_alloc_freelist_randomize_dbl_free.patch

diff --git a/PartitionAlloc.cpp b/PartitionAlloc.cpp
index 1215713..3b249e2 100644
--- a/PartitionAlloc.cpp
+++ b/PartitionAlloc.cpp
@@ -32,6 +32,7 @@
 #include "PartitionAlloc.h"
 
 #include <string.h>
+#include <vector>
 
 #ifndef NDEBUG
 #include <stdio.h>
@@ -142,6 +143,10 @@ void partitionAllocInit(PartitionRoot* root, size_t numBuckets, size_t maxAlloca
 {
     parititonAllocBaseInit(root);
 
+    // Reseed the RNG using time() with some bits
+    // from the current random pool
+    srand(time(NULL) + (rand() % 100000));
+
     root->numBuckets = numBuckets;
     root->maxAllocation = maxAllocation;
     size_t i;
@@ -564,16 +569,31 @@ static ALWAYS_INLINE char* partitionPageAllocAndFillFreelist(PartitionPage* page
     page->numUnprovisionedSlots = numSlots;
     page->numAllocatedSlots++;
 
+    std::vector<PartitionFreelistEntry *> vfreelist;
+
     if (LIKELY(numNewFreelistEntries)) {
         char* freelistPointer = firstFreelistPointer;
         PartitionFreelistEntry* entry = reinterpret_cast<PartitionFreelistEntry*>(freelistPointer);
         page->freelistHead = entry;
+        vfreelist.push_back(entry);
+
         while (--numNewFreelistEntries) {
             freelistPointer += size;
-            PartitionFreelistEntry* nextEntry = reinterpret_cast<PartitionFreelistEntry*>(freelistPointer);
+            vfreelist.push_back(reinterpret_cast<PartitionFreelistEntry*>(freelistPointer));
+        }
+
+        std::random_shuffle(vfreelist.begin(), vfreelist.end());
+
+        entry = vfreelist[vfreelist.size()-1];
+        vfreelist.pop_back();
+        page->freelistHead = entry;
+
+        for(int i=0;i<vfreelist.size();i++) {
+            PartitionFreelistEntry* nextEntry = vfreelist[i];
             entry->next = partitionFreelistMask(nextEntry);
             entry = nextEntry;
         }
+
         entry->next = partitionFreelistMask(0);
     } else {
         page->freelistHead = 0;
@@ -842,9 +862,30 @@ void* partitionAllocSlowPath(PartitionRootBase* root, int flags, size_t size, Pa
     // usable freelist head.
     if (LIKELY(newPage->freelistHead != nullptr)) {
         PartitionFreelistEntry* entry = newPage->freelistHead;
-        PartitionFreelistEntry* newHead = partitionFreelistMask(entry->next);
-        newPage->freelistHead = newHead;
+        PartitionFreelistEntry* z = entry;
+
+        while(entry) {
+            if((rand() % 10) == 1) {
+                break;
+            }
+
+            z = entry;
+            entry = partitionFreelistMask(entry->next);
+        }
+
+        if(entry == nullptr) {
+            entry = newPage->freelistHead;
+        }
+
+        if(entry == newPage->freelistHead) {
+            PartitionFreelistEntry* newHead = partitionFreelistMask(entry->next);
+            newPage->freelistHead = newHead;
+        } else {
+            z->next = entry->next;
+        }
+
         newPage->numAllocatedSlots++;
+
         return entry;
     }
     // Otherwise, we need to build the freelist.
diff --git a/PartitionAlloc.h b/PartitionAlloc.h
index 2458d5a..7b13e40 100644
--- a/PartitionAlloc.h
+++ b/PartitionAlloc.h
@@ -1,3 +1,6 @@
+#include <stdio.h>
+#include <stdlib.h>
+
 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
@@ -579,13 +582,37 @@ ALWAYS_INLINE void* partitionBucketAlloc(PartitionRootBase* root, int flags, siz
     ASSERT(page->numAllocatedSlots >= 0);
     void* ret = page->freelistHead;
     if (LIKELY(ret != 0)) {
+        PartitionFreelistEntry* t = page->freelistHead;
+        PartitionFreelistEntry* z = t;
+
+        while(t) {
+            if((rand() % 10) == 1) {
+                break;
+            }
+
+            z = t;
+            t = partitionFreelistMask(t->next);
+        }
+
+        if(t) {
+            ret = t;
+        } else {
+            ret = page->freelistHead;
+        }
+
         // If these asserts fire, you probably corrupted memory.
         ASSERT(partitionPointerIsValid(ret));
         // All large allocations must go through the slow path to correctly
         // update the size metadata.
         ASSERT(partitionPageGetRawSize(page) == 0);
-        PartitionFreelistEntry* newHead = partitionFreelistMask(static_cast<PartitionFreelistEntry*>(ret)->next);
-        page->freelistHead = newHead;
+
+        if(ret == page->freelistHead) {
+            PartitionFreelistEntry* newHead = partitionFreelistMask(static_cast<PartitionFreelistEntry*>(ret)->next);
+            page->freelistHead = newHead;
+        } else {
+            z->next = t->next;
+        }
+
         page->numAllocatedSlots++;
     } else {
         ret = partitionAllocSlowPath(root, flags, size, bucket);
@@ -647,6 +674,14 @@ ALWAYS_INLINE void partitionFreeWithPage(void* ptr, PartitionPage* page)
     ASSERT(!freelistHead || partitionPointerIsValid(freelistHead));
     RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(ptr != freelistHead); // Catches an immediate double free.
     ASSERT_WITH_SECURITY_IMPLICATION(!freelistHead || ptr != partitionFreelistMask(freelistHead->next)); // Look for double free one level deeper in debug.
+
+    PartitionFreelistEntry* f = freelistHead;
+
+    while(f != NULL) {
+        RELEASE_ASSERT_WITH_SECURITY_IMPLICATION(f != ptr);
+        f = partitionFreelistMask(f->next);
+    }
+
     PartitionFreelistEntry* entry = static_cast<PartitionFreelistEntry*>(ptr);
     entry->next = partitionFreelistMask(freelistHead);
     page->freelistHead = entry;