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

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <algorithm>

#include <OS.h>

#include <AutoDeleter.h>

#include <scheduler_defs.h>
#include <syscalls.h>
#include <thread_defs.h>

#include "time_stats.h"


struct wait_object_group {
        scheduling_analysis_thread_wait_object**        objects;
        int32                                                                           count;
        bigtime_t                                                                       wait_time;
        int64                                                                           waits;
};


struct ThreadRunTimeComparator {
        inline bool operator()(const scheduling_analysis_thread* a,
                const scheduling_analysis_thread* b)
        {
                return a->total_run_time > b->total_run_time;
        }
};


struct WaitObjectGroupingComparator {
        inline bool operator()(const scheduling_analysis_thread_wait_object* a,
                const scheduling_analysis_thread_wait_object* b)
        {
                return a->wait_object->type < b->wait_object->type
                        || (a->wait_object->type == b->wait_object->type
                                && strcmp(a->wait_object->name, b->wait_object->name) < 0);
        }
};


struct WaitObjectTimeComparator {
        inline bool operator()(const scheduling_analysis_thread_wait_object* a,
                const scheduling_analysis_thread_wait_object* b)
        {
                return a->wait_time > b->wait_time;
        }
};


struct WaitObjectGroupTimeComparator {
        inline bool operator()(const wait_object_group& a,
                const wait_object_group& b)
        {
                return a.wait_time > b.wait_time;
        }
};


static const char*
wait_object_to_string(scheduling_analysis_wait_object* waitObject, char* buffer,
        bool nameOnly = false)
{
        uint32 type = waitObject->type;
        void* object = waitObject->object;

        switch (type) {
                case THREAD_BLOCK_TYPE_SEMAPHORE:
                        if (nameOnly) {
                                sprintf(buffer, "sem \"%s\"", waitObject->name);
                        } else {
                                sprintf(buffer, "sem %ld (%s)", (sem_id)(addr_t)object,
                                        waitObject->name);
                        }
                        break;
                case THREAD_BLOCK_TYPE_CONDITION_VARIABLE:
                        if (nameOnly) {
                                sprintf(buffer, "cvar \"%s\"", waitObject->name);
                        } else {
                                sprintf(buffer, "cvar %p (%s %p)", object, waitObject->name,
                                        waitObject->referenced_object);
                        }
                        break;
                case THREAD_BLOCK_TYPE_SNOOZE:
                        strcpy(buffer, "snooze");
                        break;
                case THREAD_BLOCK_TYPE_SIGNAL:
                        strcpy(buffer, "signal");
                        break;
                case THREAD_BLOCK_TYPE_MUTEX:
                        if (nameOnly)
                                sprintf(buffer, "mutex \"%s\"", waitObject->name);
                        else
                                sprintf(buffer, "mutex %p (%s)", object, waitObject->name);
                        break;
                case THREAD_BLOCK_TYPE_RW_LOCK:
                        if (nameOnly)
                                sprintf(buffer, "rwlock \"%s\"", waitObject->name);
                        else
                                sprintf(buffer, "rwlock %p (%s)", object, waitObject->name);
                        break;
                case THREAD_BLOCK_TYPE_USER:
                        strcpy(buffer, "user");
                        break;
                case THREAD_BLOCK_TYPE_OTHER:
                        sprintf(buffer, "other %p (%s)", object, waitObject->name);
                        break;
                case THREAD_BLOCK_TYPE_OTHER_OBJECT:
                        sprintf(buffer, "other object %p", object);
                        break;
                default:
                        sprintf(buffer, "unknown %p", object);
                        break;
        }

        return buffer;
}


void
do_scheduling_analysis(bigtime_t startTime, bigtime_t endTime,
        size_t bufferSize)
{
        printf("\n");

        // allocate a chunk of memory for the scheduling analysis
        void* buffer = malloc(bufferSize);
        if (buffer == NULL) {
                fprintf(stderr, "Error: Failed to allocate memory for the scheduling "
                        "analysis.\n");
                exit(1);
        }
        MemoryDeleter _(buffer);

        // do the scheduling analysis
        scheduling_analysis analysis;
        status_t error = _kern_analyze_scheduling(startTime, endTime, buffer,
                bufferSize, &analysis);
        if (error != B_OK) {
                fprintf(stderr, "Error: Scheduling analysis failed: %s\n",
                        strerror(error));
                exit(1);
        }

        // allocate arrays for grouping and sorting the wait objects
        scheduling_analysis_thread_wait_object** waitObjects
                = new(std::nothrow) scheduling_analysis_thread_wait_object*[
                        analysis.thread_wait_object_count];
        ArrayDeleter<scheduling_analysis_thread_wait_object*> _2(waitObjects);

        wait_object_group* waitObjectGroups = new(std::nothrow) wait_object_group[
                analysis.thread_wait_object_count];
        ArrayDeleter<wait_object_group> _3(waitObjectGroups);

        if (waitObjects == NULL || waitObjectGroups == NULL) {
                fprintf(stderr, "Error: Out of memory\n");
                exit(1);
        }

        printf("scheduling analysis: %lu threads, %llu wait objects, "
                "%llu thread wait objects\n", analysis.thread_count,
                analysis.wait_object_count, analysis.thread_wait_object_count);

        // sort the thread by run time
        std::sort(analysis.threads, analysis.threads + analysis.thread_count,
                ThreadRunTimeComparator());

        for (uint32 i = 0; i < analysis.thread_count; i++) {
                scheduling_analysis_thread* thread = analysis.threads[i];

                // compute total wait time and prepare the objects for sorting
                int32 waitObjectCount = 0;
                bigtime_t waitTime = 0;
                scheduling_analysis_thread_wait_object* threadWaitObject
                        = thread->wait_objects;
                while (threadWaitObject != NULL) {
                        waitObjects[waitObjectCount++] = threadWaitObject;
                        waitTime += threadWaitObject->wait_time;
                        threadWaitObject = threadWaitObject->next_in_list;
                }

                // sort the wait objects by type + name
                std::sort(waitObjects, waitObjects + waitObjectCount,
                        WaitObjectGroupingComparator());

                // create the groups
                wait_object_group* group = NULL;
                int32 groupCount = 0;
                for (int32 i = 0; i < waitObjectCount; i++) {
                        scheduling_analysis_thread_wait_object* threadWaitObject
                                = waitObjects[i];
                        scheduling_analysis_wait_object* waitObject
                                = threadWaitObject->wait_object;

                        if (groupCount == 0 || strcmp(waitObject->name, "?") == 0
                                || waitObject->type != group->objects[0]->wait_object->type
                                || strcmp(waitObject->name,
                                                group->objects[0]->wait_object->name) != 0) {
                                // create a new group
                                group = &waitObjectGroups[groupCount++];
                                group->objects = waitObjects + i;
                                group->count = 0;
                                group->wait_time = 0;
                                group->waits = 0;
                        }

                        group->count++;
                        group->wait_time += threadWaitObject->wait_time;
                        group->waits += threadWaitObject->waits;
                }

                // sort the groups by wait time
                std::sort(waitObjectGroups, waitObjectGroups + groupCount,
                        WaitObjectGroupTimeComparator());

                printf("\nthread %ld \"%s\":\n", thread->id, thread->name);
                printf("  run time:    %lld us (%lld runs)\n", thread->total_run_time,
                        thread->runs);
                printf("  wait time:   %lld us\n", waitTime);
                printf("  latencies:   %lld us (%lld)\n", thread->total_latency,
                        thread->latencies);
                printf("  preemptions: %lld us (%lld)\n", thread->total_rerun_time,
                        thread->reruns);
                printf("  unspecified: %lld us\n", thread->unspecified_wait_time);

                printf("  waited on:\n");
                for (int32 i = 0; i < groupCount; i++) {
                        wait_object_group& group = waitObjectGroups[i];
                        char buffer[1024];

                        if (group.count == 1) {
                                // only one element -- just print it
                                scheduling_analysis_thread_wait_object* threadWaitObject
                                        = group.objects[0];
                                scheduling_analysis_wait_object* waitObject
                                        = threadWaitObject->wait_object;
                                wait_object_to_string(waitObject, buffer);
                                printf("    %s: %lld us (%lld)\n", buffer,
                                        threadWaitObject->wait_time, threadWaitObject->waits);
                        } else {
                                // sort the wait objects by wait time
                                std::sort(group.objects, group.objects + group.count,
                                        WaitObjectTimeComparator());

                                // print the group line
                                wait_object_to_string(group.objects[0]->wait_object, buffer,
                                        true);
                                printf("    group %s: %lld us (%lld)\n", buffer,
                                        group.wait_time, group.waits);

                                // print the wait objects
                                for (int32 k = 0; k < group.count; k++) {
                                        scheduling_analysis_thread_wait_object* threadWaitObject
                                                = group.objects[k];
                                        scheduling_analysis_wait_object* waitObject
                                                = threadWaitObject->wait_object;
                                        wait_object_to_string(waitObject, buffer);
                                        printf("      %s: %lld us (%lld)\n", buffer,
                                                threadWaitObject->wait_time, threadWaitObject->waits);
                                }
                        }
                }
        }
}