/*
 * Copyright 2008-2010, Ingo Weinhold, ingo_weinhold@gmx.de.
 * Distributed under the terms of the MIT License.
 */


#include "EntryCache.h"

#include <new>
#include <vm/vm.h>
#include <slab/Slab.h>


static const int32 kEntryNotInArray = -1;
static const int32 kEntryRemoved = -2;


// #pragma mark - EntryCacheGeneration


EntryCacheGeneration::EntryCacheGeneration()
        :
        next_index(0),
        entries(NULL)
{
}


EntryCacheGeneration::~EntryCacheGeneration()
{
        delete[] entries;
}


status_t
EntryCacheGeneration::Init(int32 entriesSize)
{
        entries_size = entriesSize;
        entries = new(std::nothrow) EntryCacheEntry*[entries_size];
        if (entries == NULL)
                return B_NO_MEMORY;

        memset(entries, 0, sizeof(EntryCacheEntry*) * entries_size);
        return B_OK;
}


// #pragma mark - EntryCache


EntryCache::EntryCache()
        :
        fGenerationCount(0),
        fGenerations(NULL),
        fCurrentGeneration(0)
{
        rw_lock_init(&fLock, "entry cache");

        new(&fEntries) EntryTable;
}


EntryCache::~EntryCache()
{
        // delete entries
        EntryCacheEntry* entry = fEntries.Clear(true);
        while (entry != NULL) {
                EntryCacheEntry* next = entry->hash_link;
                free(entry);
                entry = next;
        }
        delete[] fGenerations;

        rw_lock_destroy(&fLock);
}


status_t
EntryCache::Init()
{
        WriteLocker locker(fLock);
        ASSERT(fGenerationCount == 0);

        status_t error = fEntries.Init();
        if (error != B_OK)
                return error;

        int32 entriesSize = 1024;
        fGenerationCount = 8;

        // TODO: Choose generation size/count more scientifically?
        // TODO: Add low_resource handler hook?
        if (vm_available_memory() >= (1024*1024*1024)) {
                entriesSize = 8192;
                fGenerationCount = 16;
        }

        fGenerations = new(std::nothrow) EntryCacheGeneration[fGenerationCount];
        for (int32 i = 0; i < fGenerationCount; i++) {
                error = fGenerations[i].Init(entriesSize);
                if (error != B_OK)
                        return error;
        }

        return B_OK;
}


status_t
EntryCache::Add(ino_t dirID, const char* name, ino_t nodeID, bool missing)
{
        EntryCacheKey key(dirID, name);

        const size_t nameLen = strlen(name);
        EntryCacheEntry* entry = (EntryCacheEntry*)malloc(sizeof(EntryCacheEntry) + nameLen);

        if (entry == NULL)
                return B_NO_MEMORY;

        entry->node_id = nodeID;
        entry->dir_id = dirID;
        entry->hash = key.hash;
        entry->missing = missing;
        entry->index = kEntryNotInArray;
        entry->generation = -1;
        memcpy(entry->name, name, nameLen + 1);

        ReadLocker readLocker(fLock);

        if (fGenerationCount == 0) {
                free(entry);
                return B_NO_MEMORY;
        }

        EntryCacheEntry* existingEntry = fEntries.InsertAtomic(entry);
        if (existingEntry != NULL) {
                free(entry);
                entry = existingEntry;

                entry->node_id = nodeID;
                entry->missing = missing;
        }

        readLocker.Detach();
        _AddEntryToCurrentGeneration(entry, entry == existingEntry);
        return B_OK;
}


status_t
EntryCache::Remove(ino_t dirID, const char* name)
{
        EntryCacheKey key(dirID, name);

        WriteLocker writeLocker(fLock);

        EntryCacheEntry* entry = fEntries.Lookup(key);
        if (entry == NULL)
                return B_ENTRY_NOT_FOUND;

        fEntries.Remove(entry);

        if (entry->index >= 0) {
                // remove the entry from its generation and delete it
                fGenerations[entry->generation].entries[entry->index] = NULL;
                writeLocker.Unlock();
                free(entry);
        } else {
                // We can't free it, since another thread is waiting to try to move it
                // to another generation. We mark it removed and the other thread will
                // take care of deleting it.
                entry->index = kEntryRemoved;
        }

        return B_OK;
}


bool
EntryCache::Lookup(ino_t dirID, const char* name, ino_t& _nodeID,
        bool& _missing)
{
        EntryCacheKey key(dirID, name);

        ReadLocker readLocker(fLock);

        EntryCacheEntry* entry = fEntries.Lookup(key);
        if (entry == NULL)
                return false;

        _nodeID = entry->node_id;
        _missing = entry->missing;

        readLocker.Detach();
        return _AddEntryToCurrentGeneration(entry, true);
}


const char*
EntryCache::DebugReverseLookup(ino_t nodeID, ino_t& _dirID)
{
        for (EntryTable::Iterator it = fEntries.GetIterator();
                        EntryCacheEntry* entry = it.Next();) {
                if (nodeID == entry->node_id && strcmp(entry->name, ".") != 0
                                && strcmp(entry->name, "..") != 0) {
                        _dirID = entry->dir_id;
                        return entry->name;
                }
        }

        return NULL;
}


bool
EntryCache::_AddEntryToCurrentGeneration(EntryCacheEntry* entry, bool move)
{
        ReadLocker readLocker(fLock, true);

        if (move) {
                const int32 oldGeneration = atomic_get_and_set(&entry->generation,
                        fCurrentGeneration);
                if (oldGeneration == fCurrentGeneration || entry->index < 0) {
                        // The entry is already in the current generation or is being moved to
                        // it by another thread.
                        return true;
                }

                // remove from old generation array
                fGenerations[oldGeneration].entries[entry->index] = NULL;
                entry->index = kEntryNotInArray;
        } else {
                entry->generation = fCurrentGeneration;
        }

        // add to the current generation
        int32 index = atomic_add(&fGenerations[fCurrentGeneration].next_index, 1);
        if (index < fGenerations[fCurrentGeneration].entries_size) {
                fGenerations[fCurrentGeneration].entries[index] = entry;
                entry->index = index;
                return true;
        }

        // The current generation is full, so the oldest one needs to be cleared
        // in order to make room. The write lock is needed for that.
        readLocker.Unlock();
        WriteLocker writeLocker(fLock);

        // Resize the table if needed, no matter what. (The only other place it can
        // be resized is Remove(), so this is important.)
        fEntries.ResizeIfNeeded();

        if (entry->index == kEntryRemoved) {
                // The entry was removed while we were waiting. Nothing else has a
                // reference to it at this point besides us, so we free it.
                writeLocker.Unlock();
                free(entry);
                return false;
        }

        index = fGenerations[fCurrentGeneration].next_index++;
        if (index < fGenerations[fCurrentGeneration].entries_size) {
                // the current generation has already been changed
                fGenerations[fCurrentGeneration].entries[index] = entry;
                entry->generation = fCurrentGeneration;
                entry->index = index;
                return true;
        }

        // We have to clear the oldest generation.
        EntryCacheEntry* entriesToFree = NULL;
        const int32 newGeneration = (fCurrentGeneration + 1) % fGenerationCount;
        for (int32 i = 0; i < fGenerations[newGeneration].entries_size; i++) {
                EntryCacheEntry* otherEntry = fGenerations[newGeneration].entries[i];
                if (otherEntry == NULL)
                        continue;

                fGenerations[newGeneration].entries[i] = NULL;
                fEntries.RemoveUnchecked(otherEntry);

                otherEntry->hash_link = entriesToFree;
                entriesToFree = otherEntry;
        }

        // set the new generation and add the entry
        fCurrentGeneration = newGeneration;
        fGenerations[newGeneration].entries[0] = entry;
        fGenerations[newGeneration].next_index = 1;
        entry->generation = newGeneration;
        entry->index = 0;

        // free the old entries
        writeLocker.Unlock();
        while (entriesToFree != NULL) {
                EntryCacheEntry* next = entriesToFree->hash_link;
                free(entriesToFree);
                entriesToFree = next;
        }

        return true;
}