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

#include <debug_paranoia.h>

#include <sys/param.h>

#include <new>

#include <OS.h>

#include <tracing.h>
#include <util/AutoLock.h>


#if ENABLE_PARANOIA_CHECKS


// #pragma mark - CRC-32


static const uint32 kCRC32Polynom = 0x04c11db7;
static uint32 sCRC32Table[256];


static uint32
crc32_reflect(uint32 value, int32 bits)
{
        uint32 result = 0;
        for (int32 i = 1; i <= bits; i++) {
                if (value & 1)
                        result |= 1 << (bits - i);
                value >>= 1;
        }

        return result;
}


static void
init_crc32_table()
{
        for (int32 i = 0; i < 256; i++) {
                sCRC32Table[i] = crc32_reflect(i, 8) << 24;
                for (int32 k = 0; k < 8; k++) {
                        sCRC32Table[i] = (sCRC32Table[i] << 1)
                                ^ (sCRC32Table[i] & (1 << 31) ? kCRC32Polynom : 0);
                }
                sCRC32Table[i] = crc32_reflect(sCRC32Table[i], 32);
        }
}


static uint32
crc32(const void* _data, size_t size)
{
        uint8* data = (uint8*)_data;
        uint32 crc = 0xffffffff;

        while (size-- > 0) {
                crc = (crc >> 8) ^ sCRC32Table[(crc & 0xff) ^ *data];
                data++;
        }

        return crc;
}


// #pragma mark - ParanoiaCheck[Set]


class ParanoiaCheckSet;

class ParanoiaCheck {
public:
        ParanoiaCheck(const void* address, size_t size)
                :
                fAddress(address),
                fSize(size)
        {
                Update();
        }

        const void*             Address() const { return fAddress; }
        size_t                  Size() const    { return fSize; }

        void Update()
        {
                fCheckSum = crc32(fAddress, fSize);
        }

        bool Check() const
        {
                return crc32(fAddress, fSize) == fCheckSum;
        }

private:
        const void*             fAddress;
        size_t                  fSize;
        uint32                  fCheckSum;
        ParanoiaCheck*  fNext;

        friend class ParanoiaCheckSet;
};


class ParanoiaCheckSet {
public:
        ParanoiaCheckSet(const void* object, const char* description)
                :
                fObject(object),
                fDescription(description),
                fChecks(NULL)
        {
        }

        const void* Object() const              { return fObject; }
        const char* Description() const { return fDescription; }

        ParanoiaCheck* FirstCheck() const
        {
                return fChecks;
        }

        ParanoiaCheck* NextCheck(ParanoiaCheck* check) const
        {
                return check->fNext;
        }

        ParanoiaCheck* FindCheck(const void* address) const
        {
                ParanoiaCheck* check = fChecks;
                while (check != NULL && check->Address() != address)
                        check = check->fNext;
                return check;
        }

        void AddCheck(ParanoiaCheck* check)
        {
                check->fNext = fChecks;
                fChecks = check;
        }

        void RemoveCheck(ParanoiaCheck* check)
        {
                if (check == fChecks) {
                        fChecks = check->fNext;
                        return;
                }

                ParanoiaCheck* previous = fChecks;
                while (previous != NULL && previous->fNext != check)
                        previous = previous->fNext;

                // if previous is NULL (which it shouldn't be), just crash here
                previous->fNext = check->fNext;
        }

        ParanoiaCheck* RemoveFirstCheck()
        {
                ParanoiaCheck* check = fChecks;
                if (check == NULL)
                        return NULL;

                fChecks = check->fNext;
                return check;
        }

        void SetHashNext(ParanoiaCheckSet* next)
        {
                fHashNext = next;
        }

        ParanoiaCheckSet* HashNext() const
        {
                return fHashNext;
        }

private:
        const void*                     fObject;
        const char*                     fDescription;
        ParanoiaCheck*          fChecks;
        ParanoiaCheckSet*       fHashNext;
};


union paranoia_slot {
        uint8                   check[sizeof(ParanoiaCheck)];
        uint8                   checkSet[sizeof(ParanoiaCheckSet)];
        paranoia_slot*  nextFree;
};


// #pragma mark - Tracing


#if PARANOIA_TRACING


namespace ParanoiaTracing {

class ParanoiaTraceEntry : public AbstractTraceEntry {
        public:
                ParanoiaTraceEntry(const void* object)
                        :
                        fObject(object)
                {
#if PARANOIA_TRACING_STACK_TRACE
                fStackTrace = capture_tracing_stack_trace(PARANOIA_TRACING_STACK_TRACE,
                        1, false);
#endif
                }

#if PARANOIA_TRACING_STACK_TRACE
                virtual void DumpStackTrace(TraceOutput& out)
                {
                        out.PrintStackTrace(fStackTrace);
                }
#endif

        protected:
                const void*     fObject;
#if PARANOIA_TRACING_STACK_TRACE
                tracing_stack_trace* fStackTrace;
#endif
};


class CreateCheckSet : public ParanoiaTraceEntry {
        public:
                CreateCheckSet(const void* object, const char* description)
                        :
                        ParanoiaTraceEntry(object)
                {
                        fDescription = alloc_tracing_buffer_strcpy(description, 64, false);
                        Initialized();
                }

                virtual void AddDump(TraceOutput& out)
                {
                        out.Print("paranoia create check set: object: %p, "
                                "description: \"%s\"", fObject, fDescription);
                }

        private:
                const char*     fDescription;
};


class DeleteCheckSet : public ParanoiaTraceEntry {
        public:
                DeleteCheckSet(const void* object)
                        :
                        ParanoiaTraceEntry(object)
                {
                        Initialized();
                }

                virtual void AddDump(TraceOutput& out)
                {
                        out.Print("paranoia delete check set: object: %p", fObject);
                }
};


class SetCheck : public ParanoiaTraceEntry {
        public:
                SetCheck(const void* object, const void* address, size_t size,
                                paranoia_set_check_mode mode)
                        :
                        ParanoiaTraceEntry(object),
                        fAddress(address),
                        fSize(size),
                        fMode(mode)
                {
                        Initialized();
                }

                virtual void AddDump(TraceOutput& out)
                {
                        const char* mode = "??? op:";
                        switch (fMode) {
                                case PARANOIA_DONT_FAIL:
                                        mode = "set:   ";
                                        break;
                                case PARANOIA_FAIL_IF_EXISTS:
                                        mode = "add:   ";
                                        break;
                                case PARANOIA_FAIL_IF_MISSING:
                                        mode = "update:";
                                        break;
                        }
                        out.Print("paranoia check %s object: %p, address: %p, size: %lu",
                                mode, fObject, fAddress, fSize);
                }

        private:
                const void*                             fAddress;
                size_t                                  fSize;
                paranoia_set_check_mode fMode;
};


class RemoveCheck : public ParanoiaTraceEntry {
        public:
                RemoveCheck(const void* object, const void* address, size_t size)
                        :
                        ParanoiaTraceEntry(object),
                        fAddress(address),
                        fSize(size)
                {
                        Initialized();
                }

                virtual void AddDump(TraceOutput& out)
                {
                        out.Print("paranoia check remove: object: %p, address: %p, size: "
                                "%lu", fObject, fAddress, fSize);
                }

        private:
                const void*                             fAddress;
                size_t                                  fSize;
                paranoia_set_check_mode fMode;
};


}       // namespace ParanoiaTracing

#       define T(x)     new(std::nothrow) ParanoiaTracing::x

#else
#       define T(x)
#endif  // PARANOIA_TRACING


// #pragma mark -


#define PARANOIA_HASH_SIZE      PARANOIA_SLOT_COUNT

static paranoia_slot            sSlots[PARANOIA_SLOT_COUNT];
static paranoia_slot*           sSlotFreeList;
static ParanoiaCheckSet*        sCheckSetHash[PARANOIA_HASH_SIZE];
static spinlock                         sParanoiaLock;


static paranoia_slot*
allocate_slot()
{
        if (sSlotFreeList == NULL)
                return NULL;

        paranoia_slot* slot = sSlotFreeList;
        sSlotFreeList = slot->nextFree;
        return slot;
}


static void
free_slot(paranoia_slot* slot)
{
        slot->nextFree = sSlotFreeList;
        sSlotFreeList = slot;
}


static void
add_check_set(ParanoiaCheckSet* set)
{
        int slot = (addr_t)set->Object() % PARANOIA_HASH_SIZE;
        set->SetHashNext(sCheckSetHash[slot]);
        sCheckSetHash[slot] = set;
}


static void
remove_check_set(ParanoiaCheckSet* set)
{
        int slot = (addr_t)set->Object() % PARANOIA_HASH_SIZE;
        if (set == sCheckSetHash[slot]) {
                sCheckSetHash[slot] = set->HashNext();
                return;
        }

        ParanoiaCheckSet* previousSet = sCheckSetHash[slot];
        while (previousSet != NULL && previousSet->HashNext() != set)
                previousSet = previousSet->HashNext();

        // if previousSet is NULL (which it shouldn't be), just crash here
        previousSet->SetHashNext(set->HashNext());
}


static ParanoiaCheckSet*
lookup_check_set(const void* object)
{
        int slot = (addr_t)object % PARANOIA_HASH_SIZE;
        ParanoiaCheckSet* set = sCheckSetHash[slot];
        while (set != NULL && set->Object() != object)
                set = set->HashNext();

        return set;
}

// #pragma mark - public interface


status_t
create_paranoia_check_set(const void* object, const char* description)
{
        T(CreateCheckSet(object, description));

        if (object == NULL) {
                panic("create_paranoia_check_set(): NULL object");
                return B_BAD_VALUE;
        }

        InterruptsSpinLocker _(sParanoiaLock);

        // check, if object is already registered
        ParanoiaCheckSet* set = lookup_check_set(object);
        if (set != NULL) {
                panic("create_paranoia_check_set(): object %p already has a check set",
                        object);
                return B_BAD_VALUE;
        }

        // allocate slot
        paranoia_slot* slot = allocate_slot();
        if (slot == NULL) {
                panic("create_paranoia_check_set(): out of free slots");
                return B_NO_MEMORY;
        }

        set = new(slot) ParanoiaCheckSet(object, description);
        add_check_set(set);

        return B_OK;
}


status_t
delete_paranoia_check_set(const void* object)
{
        T(DeleteCheckSet(object));

        InterruptsSpinLocker _(sParanoiaLock);

        // get check set
        ParanoiaCheckSet* set = lookup_check_set(object);
        if (set == NULL) {
                panic("delete_paranoia_check_set(): object %p doesn't have a check set",
                        object);
                return B_BAD_VALUE;
        }

        // free all checks
        while (ParanoiaCheck* check = set->RemoveFirstCheck())
                free_slot((paranoia_slot*)check);

        // free check set
        remove_check_set(set);
        free_slot((paranoia_slot*)set);

        return B_OK;
}


status_t
run_paranoia_checks(const void* object)
{
        InterruptsSpinLocker _(sParanoiaLock);

        // get check set
        ParanoiaCheckSet* set = lookup_check_set(object);
        if (set == NULL) {
                panic("run_paranoia_checks(): object %p doesn't have a check set",
                        object);
                return B_BAD_VALUE;
        }
        
        status_t error = B_OK;

        ParanoiaCheck* check = set->FirstCheck();
        while (check != NULL) {
                if (!check->Check()) {
                        panic("paranoia check failed for object %p (%s), address: %p, "
                                "size: %lu", set->Object(), set->Description(),
                                check->Address(), check->Size());
                        error = B_BAD_DATA;
                }

                check = set->NextCheck(check);
        }

        return error;
}


status_t
set_paranoia_check(const void* object, const void* address, size_t size,
        paranoia_set_check_mode mode)
{
        T(SetCheck(object, address, size, mode));

        InterruptsSpinLocker _(sParanoiaLock);

        // get check set
        ParanoiaCheckSet* set = lookup_check_set(object);
        if (set == NULL) {
                panic("set_paranoia_check(): object %p doesn't have a check set",
                        object);
                return B_BAD_VALUE;
        }

        // update check, if already existing
        ParanoiaCheck* check = set->FindCheck(address);
        if (check != NULL) {
                if (mode == PARANOIA_FAIL_IF_EXISTS) {
                        panic("set_paranoia_check(): object %p already has a check for "
                                "address %p", object, address);
                        return B_BAD_VALUE;
                }

                if (check->Size() != size) {
                        panic("set_paranoia_check(): changing check sizes not supported");
                        return B_BAD_VALUE;
                }

                check->Update();
                return B_OK;
        }

        if (mode == PARANOIA_FAIL_IF_MISSING) {
                panic("set_paranoia_check(): object %p doesn't have a check for "
                        "address %p yet", object, address);
                return B_BAD_VALUE;
        }

        // allocate slot
        paranoia_slot* slot = allocate_slot();
        if (slot == NULL) {
                panic("set_paranoia_check(): out of free slots");
                return B_NO_MEMORY;
        }

        check = new(slot) ParanoiaCheck(address, size);
        set->AddCheck(check);

        return B_OK;
}


status_t
remove_paranoia_check(const void* object, const void* address, size_t size)
{
        T(RemoveCheck(object, address, size));

        InterruptsSpinLocker _(sParanoiaLock);

        // get check set
        ParanoiaCheckSet* set = lookup_check_set(object);
        if (set == NULL) {
                panic("remove_paranoia_check(): object %p doesn't have a check set",
                        object);
                return B_BAD_VALUE;
        }

        // get check
        ParanoiaCheck* check = set->FindCheck(address);
        if (check == NULL) {
                panic("remove_paranoia_check(): no check for address %p "
                        "(object %p (%s))", address, object, set->Description());
                return B_BAD_VALUE;
        }

        if (check->Size() != size) {
                panic("remove_paranoia_check(): changing check sizes not "
                        "supported");
                return B_BAD_VALUE;
        }

        set->RemoveCheck(check);
        return B_OK;
}


#endif  // ENABLE_PARANOIA_CHECKS


void
debug_paranoia_init()
{
#if ENABLE_PARANOIA_CHECKS
        // init CRC-32 table
        init_crc32_table();

        // init paranoia slot free list
        for (int32 i = 0; i < PARANOIA_SLOT_COUNT; i++)
                free_slot(&sSlots[i]);
#endif
}