Oilpan: Try to allocate from a smaller FreeListEntry.

Source/platform/heap/Heap.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 711 matching lines @@
     ensureCurrentAllocation(allocationSize, gcInfo);
     return allocate(size, gcInfo);
 }
 
 template<typename Header>
 bool ThreadHeap<Header>::allocateFromFreeList(size_t minSize)
 {
     size_t bucketSize = 1 << m_freeList.m_biggestFreeListIndex;
     int i = m_freeList.m_biggestFreeListIndex;
     for (; i > 0; i--, bucketSize >>= 1) {
-        if (bucketSize < minSize)
-            break;
+        if (bucketSize < minSize) {
+            // A FreeListEntry for bucketSize might be larger than minSize.
+            // FIXME: We check only the first FreeListEntry because searching
+            // the entire list is costly.
+            if (!m_freeList.m_freeLists[i] || m_freeList.m_freeLists[i]->size() < minSize)
+                break;
+        }
         FreeListEntry* entry = m_freeList.m_freeLists[i];
         if (entry) {
             m_freeList.m_biggestFreeListIndex = i;
             entry->unlink(&m_freeList.m_freeLists[i]);
             setAllocationPoint(entry->address(), entry->size());
             ASSERT(currentAllocationPoint() && remainingAllocationSize() >= minSize);
             return true;
         }
     }
     m_freeList.m_biggestFreeListIndex = i;

[sof, 2014/11/11 08:29:36]

I don't understand m_biggestFreeListIndex and this update; I must be missing
some detail..?

If you call allocateFromFreeList(17) and it fails as there are no entries in its
bucket, then m_biggestFreeListIndex will be set to 4. If you then call
allocateFromFreeList(65534), and there are free list entries at that bucket,
these will never be considered afaict.

[tkent, 2014/11/11 08:46:59]

We always allocate from a FreeListEntry in the largest bucket.
If we hit the |break| in the loop, it means we have no FreeListEntries in
m_freeLists[i+1 or greater].

     return false;
 }
 
 template<typename Header>
 void ThreadHeap<Header>::ensureCurrentAllocation(size_t minSize, const GCInfo* gcInfo)
 {
     ASSERT(minSize >= allocationGranularity);
     if (allocateFromFreeList(minSize))
         return;
     if (coalesce(minSize) && allocateFromFreeList(minSize))
@@ skipping 2207 matching lines @@
 CallbackStack* Heap::s_weakCallbackStack;
 CallbackStack* Heap::s_ephemeronStack;
 HeapDoesNotContainCache* Heap::s_heapDoesNotContainCache;
 bool Heap::s_shutdownCalled = false;
 bool Heap::s_lastGCWasConservative = false;
 FreePagePool* Heap::s_freePagePool;
 OrphanedPagePool* Heap::s_orphanedPagePool;
 Heap::RegionTree* Heap::s_regionTree = 0;
 
 } // namespace blink