[BMalloc] Scavenger should react to recent memory activity
[WebKit-https.git] / Source / bmalloc / bmalloc / Chunk.h
index fc5c3e1..17ebeb5 100644 (file)
 #ifndef Chunk_h
 #define Chunk_h
 
-#include "BeginTag.h"
-#include "EndTag.h"
 #include "Object.h"
-#include "ObjectType.h"
 #include "Sizes.h"
 #include "SmallLine.h"
 #include "SmallPage.h"
 
 namespace bmalloc {
 
-class Chunk {
+class Chunk : public ListNode<Chunk> {
 public:
     static Chunk* get(void*);
 
-    static BeginTag* beginTag(void*);
-    static EndTag* endTag(void*, size_t);
+    Chunk(size_t pageSize);
+    
+    void ref() { ++m_refCount; }
+    void deref() { BASSERT(m_refCount); --m_refCount; }
+    unsigned refCount() { return m_refCount; }
 
-    Chunk(std::lock_guard<StaticMutex>&);
+    bool usedSinceLastScavenge() { return m_usedSinceLastScavenge; }
+    void clearUsedSinceLastScavenge() { m_usedSinceLastScavenge = false; }
+    void setUsedSinceLastScavenge() { m_usedSinceLastScavenge = true; }
 
     size_t offset(void*);
 
-    void* object(size_t offset);
+    char* address(size_t offset);
     SmallPage* page(size_t offset);
     SmallLine* line(size_t offset);
 
-    SmallPage* pageBegin() { return Object(m_memory).page(); }
-    SmallPage* pageEnd() { return m_pages.end(); }
+    char* bytes() { return reinterpret_cast<char*>(this); }
+    SmallLine* lines() { return &m_lines[0]; }
+    SmallPage* pages() { return &m_pages[0]; }
     
-    SmallLine* lines() { return m_lines.begin(); }
-    SmallPage* pages() { return m_pages.begin(); }
-
-    char* begin() { return m_memory; }
-    char* end() { return reinterpret_cast<char*>(this) + chunkSize; }
+    List<SmallPage>& freePages() { return m_freePages; }
 
 private:
-    static const size_t boundaryTagCount = chunkSize / largeMin;
-    static_assert(boundaryTagCount > 2, "Chunk must have space for two sentinel boundary tags");
-
-    // Our metadata layout includes a left and right edge sentinel.
-    // Metadata takes up enough space to leave at least the first two
-    // boundary tag slots unused.
-    //
-    //      So, boundary tag space looks like this:
-    //
-    //          [OOXXXXX...]
-    //
-    //      And BoundaryTag::get subtracts one, producing:
-    //
-    //          [OXXXXX...O].
-    //
-    // We use the X's for boundary tags and the O's for edge sentinels.
-
-    std::array<SmallLine, chunkSize / smallLineSize> m_lines;
-    std::array<SmallPage, chunkSize / vmPageSize> m_pages;
-    std::array<BoundaryTag, boundaryTagCount> m_boundaryTags;
-    char m_memory[] __attribute__((aligned(2 * smallMax + 0)));
-};
+    size_t m_refCount { };
+    bool m_usedSinceLastScavenge: 1;
+    List<SmallPage> m_freePages { };
 
-static_assert(sizeof(Chunk) + largeMax <= chunkSize, "largeMax is too big");
-static_assert(
-    sizeof(Chunk) % vmPageSize + 2 * smallMax <= vmPageSize,
-    "the first page of object memory in a small chunk must be able to allocate smallMax");
+    std::array<SmallLine, chunkSize / smallLineSize> m_lines { };
+    std::array<SmallPage, chunkSize / smallPageSize> m_pages { };
+};
 
-inline Chunk::Chunk(std::lock_guard<StaticMutex>& lock)
-{
-    Range range(begin(), end() - begin());
-    BASSERT(range.size() <= largeObjectMax);
-
-    BeginTag* beginTag = Chunk::beginTag(range.begin());
-    beginTag->setRange(range);
-    beginTag->setFree(true);
-    beginTag->setVMState(VMState::Virtual);
-
-    EndTag* endTag = Chunk::endTag(range.begin(), range.size());
-    endTag->init(beginTag);
-
-    // Mark the left and right edges of our range as allocated. This naturally
-    // prevents merging logic from overflowing left (into metadata) or right
-    // (beyond our chunk), without requiring special-case checks.
-
-    EndTag* leftSentinel = beginTag->prev();
-    BASSERT(leftSentinel >= m_boundaryTags.begin());
-    BASSERT(leftSentinel < m_boundaryTags.end());
-    leftSentinel->initSentinel();
-
-    BeginTag* rightSentinel = endTag->next();
-    BASSERT(rightSentinel >= m_boundaryTags.begin());
-    BASSERT(rightSentinel < m_boundaryTags.end());
-    rightSentinel->initSentinel();
-
-    // Track the memory used for metadata by allocating imaginary objects.
-    for (char* it = reinterpret_cast<char*>(this); it < m_memory; it += smallLineSize) {
-        Object object(it);
-        object.line()->ref(lock);
-        object.page()->ref(lock);
+struct ChunkHash {
+    static unsigned hash(Chunk* key)
+    {
+        return static_cast<unsigned>(
+            reinterpret_cast<uintptr_t>(key) / chunkSize);
     }
-}
+};
 
-inline Chunk* Chunk::get(void* object)
+template<typename Function> void forEachPage(Chunk* chunk, size_t pageSize, Function function)
 {
-    return static_cast<Chunk*>(mask(object, chunkMask));
+    // We align to at least the page size so we can service aligned allocations
+    // at equal and smaller powers of two, and also so we can vmDeallocatePhysicalPages().
+    size_t metadataSize = roundUpToMultipleOfNonPowerOfTwo(pageSize, sizeof(Chunk));
+
+    Object begin(chunk, metadataSize);
+    Object end(chunk, chunkSize);
+
+    for (auto it = begin; it + pageSize <= end; it = it + pageSize)
+        function(it.page());
 }
 
-inline BeginTag* Chunk::beginTag(void* object)
+inline Chunk::Chunk(size_t pageSize)
 {
-    Chunk* chunk = get(object);
-    size_t boundaryTagNumber = (static_cast<char*>(object) - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
-    return static_cast<BeginTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
+    size_t smallPageCount = pageSize / smallPageSize;
+    forEachPage(this, pageSize, [&](SmallPage* page) {
+        for (size_t i = 0; i < smallPageCount; ++i)
+            page[i].setSlide(i);
+    });
 }
 
-inline EndTag* Chunk::endTag(void* object, size_t size)
+inline Chunk* Chunk::get(void* address)
 {
-    Chunk* chunk = get(object);
-    char* end = static_cast<char*>(object) + size;
-
-    // We subtract largeMin before computing the end pointer's boundary tag. An
-    // object's size need not be an even multiple of largeMin. Subtracting
-    // largeMin rounds down to the last boundary tag prior to our neighbor.
-
-    size_t boundaryTagNumber = (end - largeMin - reinterpret_cast<char*>(chunk)) / largeMin - 1; // - 1 to offset from the right sentinel.
-    return static_cast<EndTag*>(&chunk->m_boundaryTags[boundaryTagNumber]);
+    return static_cast<Chunk*>(mask(address, chunkMask));
 }
 
-inline size_t Chunk::offset(void* object)
+inline size_t Chunk::offset(void* address)
 {
-    BASSERT(object >= this);
-    BASSERT(object < reinterpret_cast<char*>(this) + chunkSize);
-    return static_cast<char*>(object) - reinterpret_cast<char*>(this);
+    BASSERT(address >= this);
+    BASSERT(address < bytes() + chunkSize);
+    return static_cast<char*>(address) - bytes();
 }
 
-inline void* Chunk::object(size_t offset)
+inline char* Chunk::address(size_t offset)
 {
-    return reinterpret_cast<char*>(this) + offset;
+    return bytes() + offset;
 }
 
 inline SmallPage* Chunk::page(size_t offset)
 {
-    size_t pageNumber = offset / vmPageSize;
-    return &m_pages[pageNumber];
+    size_t pageNumber = offset / smallPageSize;
+    SmallPage* page = &m_pages[pageNumber];
+    return page - page->slide();
 }
 
 inline SmallLine* Chunk::line(size_t offset)
@@ -190,17 +145,13 @@ inline char* SmallLine::end()
 
 inline SmallLine* SmallPage::begin()
 {
+    BASSERT(!m_slide);
     Chunk* chunk = Chunk::get(this);
     size_t pageNumber = this - chunk->pages();
-    size_t lineNumber = pageNumber * smallLineCount;
+    size_t lineNumber = pageNumber * smallPageLineCount;
     return &chunk->lines()[lineNumber];
 }
 
-inline SmallLine* SmallPage::end()
-{
-    return begin() + smallLineCount;
-}
-
 inline Object::Object(void* object)
     : m_chunk(Chunk::get(object))
     , m_offset(m_chunk->offset(object))
@@ -214,14 +165,9 @@ inline Object::Object(Chunk* chunk, void* object)
     BASSERT(chunk == Chunk::get(object));
 }
 
-inline void* Object::begin()
-{
-    return m_chunk->object(m_offset);
-}
-
-inline void* Object::pageBegin()
+inline char* Object::address()
 {
-    return m_chunk->object(roundDownToMultipleOf(vmPageSize, m_offset));
+    return m_chunk->address(m_offset);
 }
 
 inline SmallLine* Object::line()