/*
*  Licensed to the Apache Software Foundation (ASF) under one or more
*  contributor license agreements.  See the NOTICE file distributed with
*  this work for additional information regarding copyright ownership.
*  The ASF licenses this file to You under the Apache License, Version 2.0
*  (the "License"); you may not use this file except in compliance with
*  the License.  You may obtain a copy of the License at
*
*     http://www.apache.org/licenses/LICENSE-2.0
*
*  Unless required by applicable law or agreed to in writing, software
*  distributed under the License is distributed on an "AS IS" BASIS,
*  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
*  See the License for the specific language governing permissions and
*  limitations under the License.
*/
/**
* @author Yuri Kashnikov
*
* The idea of advanced Top-N-Value (with steady and clear parts, and clear
* interval) from <"Value profiling and optimization", B.Calder, P.Feller,
* Journal of Instruction-Level Parallelism, 1999>
*
*/
#define LOG_DOMAIN "em"
#include "cxxlog.h"
#include "NValueProfileCollector.h"

#include <algorithm>
#include <sstream>
#include "open/vm_class_info.h"
#include "open/vm_ee.h"

#include "port_threadunsafe.h"
#include "port_atomic.h"
#include "open/vm_class_manipulation.h"
#include "open/vm.h" // for vtable_get_class


VPInstructionProfileData* TNVTableManager::createProfileData()
{
    VPInstructionProfileData* data = new VPInstructionProfileData();
    data->TNV_Table =  new (struct Simple_TNV_Table[steadySize]);
    for (U_32 i = 0; i < steadySize; i++) {
        (data->TNV_Table[i]).frequency = 0;
        (data->TNV_Table[i]).value = 0;
    }
    if (clearSize > 0) {
        data->TNV_clear_part = new (struct Simple_TNV_Table[clearSize]);
        for (U_32 i = 0; i < clearSize; i++) {
            (data->TNV_clear_part[i]).frequency = 0;
            (data->TNV_clear_part[i]).value = 0;
        }
    }
    return data;
}

I_32 TNVTableManager::find(TableT* where, ValueT value_to_search, U_32 size)
{
    U_32 search_index;
    for (search_index = 0; search_index < size; search_index++){
        if (where[search_index].value == value_to_search)
            return (search_index);
    }
    return (-1);
}

void TNVTableManager::clearTopElements(TableT* where)
{
    U_32 temp_index;
    for (temp_index = 0; temp_index < clearSize; temp_index++) {
        where[temp_index].frequency = TNV_DEFAULT_CLEAR_VALUE;
    }
}

I_32 TNVTableManager::findMinIdx(TableT* where, U_32 size)
{
    U_32 temp_index;
    U_32 temp_min_index = 0;
    U_32 temp_min = where[temp_min_index].frequency;
    for (temp_index = 0; temp_index < size; temp_index++){
        if (where[temp_index].frequency == TNV_DEFAULT_CLEAR_VALUE) {
            return (temp_index); 
        }
        if (where[temp_index].frequency < temp_min){
            temp_min = where[temp_index].frequency;
            temp_min_index = temp_index;
        }
    }
    return (temp_min_index);
}

TNVTableManager::ValueT TNVTableManager::findMax(TableT *where)
{
    ValueT max_value = 0;
    U_32 temp_index, temp_max_frequency = 0;
    for (temp_index = 0; temp_index < steadySize; temp_index++) {
        TableT *current_tbl = &(where[temp_index]);
        if (current_tbl->frequency > temp_max_frequency){
            temp_max_frequency = current_tbl->frequency;
            max_value = current_tbl->value;
        }
    }
    return (max_value);
}

void TNVTableManager::flushLastValueCounter(VPData *instProfile)
{
    POINTER_SIZE_INT last_value = instProfile->last_value;
    U_32* num_times_profiled = &(instProfile->num_times_profiled);
    struct Simple_TNV_Table* clear_part = instProfile->TNV_clear_part;
    struct Simple_TNV_Table* steady_part = instProfile->TNV_Table;

    insert(steady_part, clear_part, last_value, *num_times_profiled);

    *num_times_profiled = 0;
}

void TNVTableManager::dumpValues
    (VPInstructionProfileData* data, std::ostream& os)
{
    os << ", num_times_profiled: " << data->num_times_profiled 
        << ", profile_tick: " << data->profile_tick << std::endl;
    struct Simple_TNV_Table * TNV_steady_part = data->TNV_Table;
    if (TNV_steady_part != NULL) {
        U_32 size = steadySize;
        os << "= TNV_steady_part, size = " << size << std::endl;
        for (U_32 i = 0; i < size; i++) {
            os << "== Frequency: " << TNV_steady_part[i].frequency << " = Value: ";
            POINTER_SIZE_INT value = TNV_steady_part[i].value;
            if (value != 0) {
                os << class_get_name(vtable_get_class((VTable_Handle)value));
            } else {
                os << "NULL";
            }
            os << " ==" << std::endl;
        }
    }
    struct Simple_TNV_Table * TNV_clear_part = data->TNV_clear_part;
    if (TNV_clear_part != NULL) {
        U_32 size = clearSize;
        os << "= TNV_clear_part, size = " << size << std::endl;
        for (U_32 i = 0; i < size; i++) {
            os << "== " << TNV_clear_part[i].frequency << " = Value: ";
            POINTER_SIZE_INT value = TNV_clear_part[i].value;
            if (value != 0) {
                os << class_get_name(vtable_get_class((VTable_Handle)value));
            } else {
                os << "NULL";
            }
            os << " ==" << std::endl;
        }
    }
}
//------------------------------------------------------------------------------

void TNVTableFirstNManager::insert(TableT* where, TableT* clear_part,
        ValueT value_to_insert, U_32 times_met)
{
    U_32 insert_index = find(where, value_to_insert, steadySize);
    if ((insert_index != -1) &&
        (where[insert_index].frequency != TNV_DEFAULT_CLEAR_VALUE)){
        where[insert_index].frequency += times_met;
    } else {
        insert_index = findMinIdx(where, steadySize);
        if (times_met > where[insert_index].frequency){
            where[insert_index].value = value_to_insert;
            where[insert_index].frequency = times_met;
        }
    }
}

void TNVTableFirstNManager::addNewValue(ValueMethodProfile* methProfile,
            VPData* instProfile, ValueT curr_value)
{
    U_8* updating_ptr = methProfile->getUpdatingStatePtr();
    if (updateStrategy == UPDATE_LOCKED) {
        methProfile->lockProfile();
    } else if (updateStrategy == UPDATE_FLAGGED_ALL) {
        // Checking a flag and modifying it atomically must be faster than
        // locking because it skips simultaneous updates. Faster but sacrifices
        // profile precision.
        if (port_atomic_cas8(updating_ptr, 1, 0) != 0) {
            return;
        }
    }
    UNSAFE_REGION_START
    ValueT* last_value = &(instProfile->last_value);
    U_32* num_times_profiled = &(instProfile->num_times_profiled);
    if (curr_value == *last_value){
        // We increment the counter safely with UPDATE_FLAGGED_ALL and
        // UPDATE_LOCKED
        (*num_times_profiled)++;
    } else {
        if (updateStrategy == UPDATE_LOCKED_INSERT) {
            methProfile->lockProfile();
        }else if (updateStrategy == UPDATE_FLAGGED_INSERT) {
            if (port_atomic_cas8(updating_ptr, 1, 0) != 0) {
                return;
            }
        }
        struct Simple_TNV_Table* clear_part = instProfile->TNV_clear_part;
        struct Simple_TNV_Table* steady_part = instProfile->TNV_Table;
        flushLastValueCounter(instProfile);
        *num_times_profiled = 1;
        insert(steady_part, clear_part, curr_value, *num_times_profiled);
        *last_value = curr_value;
        if (updateStrategy == UPDATE_LOCKED_INSERT) {
            methProfile->unlockProfile();
        }else if (updateStrategy == UPDATE_FLAGGED_INSERT) {
            *updating_ptr = 0;
        }
    }
    UNSAFE_REGION_END
    if (updateStrategy == UPDATE_LOCKED) {
        methProfile->unlockProfile();
    } else if (updateStrategy == UPDATE_FLAGGED_ALL) {
        *updating_ptr = 0;
    }
}
//------------------------------------------------------------------------------

void TNVTableDividedManager::insert(TableT* where, TableT* clear_part,
        ValueT value_to_insert, U_32 times_met)
{
    U_32 insert_index = find(where, value_to_insert, steadySize);
    if ((insert_index != -1) &&
        (where[insert_index].frequency != TNV_DEFAULT_CLEAR_VALUE)){
        where[insert_index].frequency += times_met;
    }else{
        ValueT temp_min_value;
        U_32 temp_min_index, temp_min_freq;
        insert_index = find(clear_part, value_to_insert, clearSize);
        if (insert_index != -1){
            clear_part[insert_index].frequency = clear_part[insert_index].frequency + times_met;
            temp_min_index = findMinIdx(where, steadySize);
            if (clear_part[insert_index].frequency > where[temp_min_index].frequency){
                temp_min_value = where[temp_min_index].value;
                temp_min_freq = where[temp_min_index].frequency;
                where[temp_min_index].value = clear_part[insert_index].value;
                where[temp_min_index].frequency = clear_part[insert_index].frequency;
                clear_part[insert_index].frequency = TNV_DEFAULT_CLEAR_VALUE;
                temp_min_index = findMinIdx(clear_part, clearSize);
                if (temp_min_freq > clear_part[temp_min_index].frequency){
                    clear_part[temp_min_index].value = temp_min_value;
                    clear_part[temp_min_index].frequency = temp_min_freq;
                }
            }
        } else {
            temp_min_index = findMinIdx(where, steadySize);
            if (times_met > where[temp_min_index].frequency)
            {
                temp_min_value = where[temp_min_index].value;
                temp_min_freq = where[temp_min_index].frequency;
                where[temp_min_index].value = value_to_insert;
                where[temp_min_index].frequency = times_met;
                temp_min_index = findMinIdx(clear_part, clearSize);
                if (temp_min_freq > clear_part[temp_min_index].frequency)
                {
                    clear_part[temp_min_index].value = temp_min_value;
                    clear_part[temp_min_index].frequency = temp_min_freq;
                }
            } else {
                temp_min_index = findMinIdx(clear_part, clearSize);
                if (times_met > clear_part[temp_min_index].frequency){
                    clear_part[temp_min_index].value = value_to_insert;
                    clear_part[temp_min_index].frequency = times_met;
                }
            }
        }
    }
}

void TNVTableDividedManager::addNewValue(ValueMethodProfile* methProfile,
            VPData* instProfile, ValueT curr_value)
{
    methProfile->lockProfile();
    struct Simple_TNV_Table* clear_part = instProfile->TNV_clear_part;
    U_32* profile_tick = &(instProfile->profile_tick);
    if (*profile_tick == clearInterval){
        *profile_tick = 0;
        clearTopElements(clear_part);
    }
    (*profile_tick)++;

    ValueT* last_value = &(instProfile->last_value);
    U_32* num_times_profiled = &(instProfile->num_times_profiled);
    if (curr_value == *last_value){
        (*num_times_profiled)++;
    } else {
        flushLastValueCounter(instProfile);
        *num_times_profiled = 1;
        struct Simple_TNV_Table* steady_part = instProfile->TNV_Table;
        insert(steady_part, clear_part, curr_value, *num_times_profiled);
        *last_value = curr_value;
    }
    methProfile->unlockProfile();
}
//------------------------------------------------------------------------------

ValueMethodProfile* ValueProfileCollector::createProfile
    (Method_Handle mh, U_32 numkeys, U_32 keys[])
{
    port_mutex_lock(&profilesLock);
    ValueMethodProfile* profile = new ValueMethodProfile(this, mh);
    // Allocate space for value maps
    for (U_32 index = 0; index < numkeys; index++){
        VPInstructionProfileData* profileData =
            getTnvMgr()->createProfileData();
        U_32 key = keys[index];
        (profile->ValueMap)[key] = profileData;
    }
    assert(profilesByMethod.find(mh) == profilesByMethod.end());
    profilesByMethod[mh] = profile;
    port_mutex_unlock(&profilesLock);
    return profile;
}

ValueProfileCollector::ValueProfileCollector(EM_PC_Interface* em, const std::string& name, JIT_Handle genJit, 
                                             U_32 _TNV_steady_size, U_32 _TNV_clear_size,
                                             U_32 _clear_interval, algotypes _TNV_algo_type,
                                             ProfileUpdateStrategy update_strategy)
                                           : ProfileCollector(em, name, EM_PCTYPE_VALUE, genJit),
                                             updateStrategy(update_strategy)
{
    port_mutex_create(&profilesLock, APR_THREAD_MUTEX_NESTED);
    if (_TNV_algo_type == TNV_DIVIDED) {
        tnvTableManager = new TNVTableDividedManager
            (_TNV_steady_size, _TNV_clear_size, _clear_interval, update_strategy);
    }else if (_TNV_algo_type == TNV_FIRST_N) {
        tnvTableManager = new TNVTableFirstNManager
            (_TNV_steady_size, _TNV_clear_size, _clear_interval, update_strategy);
    }
    catName = std::string(LOG_DOMAIN) + ".profiler." + name;
    loggingEnabled =  log_is_info_enabled(LOG_DOMAIN) || log_is_info_enabled(catName.c_str());
    INFO2(catName.c_str(), "EM: value profiler intialized: " << name.c_str());
}


ValueProfileCollector::~ValueProfileCollector()
{
    ValueProfilesMap::iterator it;
    for( it = profilesByMethod.begin(); it != profilesByMethod.end(); it++ ){
        ValueMethodProfile* profile = it->second;
        delete profile;
    }
    delete tnvTableManager;
    port_mutex_destroy(&profilesLock);
}

MethodProfile* ValueProfileCollector::getMethodProfile(Method_Handle mh) const
{
    MethodProfile* res = NULL;
    port_mutex_lock(&profilesLock);
    ValueProfilesMap::const_iterator it = profilesByMethod.find(mh);
    if (it != profilesByMethod.end()) {
        res =  it->second;
    }
    port_mutex_unlock(&profilesLock);
    return res;
}
//------------------------------------------------------------------------------

ValueMethodProfile::ValueMethodProfile(ValueProfileCollector* pc, Method_Handle mh)
    : MethodProfile(pc, mh), updatingState(0)
{
    port_mutex_create(&lock, APR_THREAD_MUTEX_DEFAULT);
}

ValueMethodProfile::~ValueMethodProfile()
{
    port_mutex_destroy(&lock);
}

void ValueMethodProfile::addNewValue
    (U_32 instructionKey, POINTER_SIZE_INT valueToAdd)
{
    VPDataMap::const_iterator it =  ValueMap.find(instructionKey);
    assert(it != ValueMap.end());

    getVPC()->getTnvMgr()->addNewValue(this, it->second, valueToAdd);
}

POINTER_SIZE_INT ValueMethodProfile::getResult(U_32 instructionKey)
{
    lockProfile();
    VPDataMap::const_iterator it =  ValueMap.find(instructionKey);
    if (it == ValueMap.end()) {
        unlockProfile();
        return 0;
    }
    VPInstructionProfileData* _temp_vp = it->second;
    assert(_temp_vp);
    if (_temp_vp == NULL) {
        unlockProfile();
        return 0;
    }
    getVPC()->getTnvMgr()->flushLastValueCounter(_temp_vp);
    POINTER_SIZE_INT result = getVPC()->getTnvMgr()->findMax(_temp_vp->TNV_Table);
    unlockProfile();
    return result; 
}

void ValueMethodProfile::dumpValues(std::ostream& os)
{
    VPDataMap::const_iterator mapIter;
    assert(pc->type == EM_PCTYPE_VALUE);
    lockProfile();
    os << "===== Value profile dump, " << ValueMap.size() << " element(s) ===" << std::endl;
    for (mapIter = ValueMap.begin(); mapIter != ValueMap.end(); mapIter++) {
        os << "=== Instruction key: " << mapIter->first;
        VPInstructionProfileData* _temp_vp = mapIter->second;
        TNVTableManager* tnvMgr = getVPC()->getTnvMgr();
        tnvMgr->flushLastValueCounter(_temp_vp);
        tnvMgr->dumpValues(_temp_vp, os);
    }
    unlockProfile();
    os << "====== End of dump ======================" << std::endl;
}

ValueProfileCollector* ValueMethodProfile::getVPC() const {
    assert(pc->type == EM_PCTYPE_VALUE);
    return ((ValueProfileCollector*)pc);
}
//------------------------------------------------------------------------------

POINTER_SIZE_INT value_profiler_get_top_value(Method_Profile_Handle mph, U_32 instructionKey)
{
    assert(mph != NULL);
    MethodProfile* mp = (MethodProfile*)mph;
    assert(mp->pc->type == EM_PCTYPE_VALUE);
    ValueMethodProfile* vmp = (ValueMethodProfile*)mp;
    return vmp->getResult(instructionKey);
}

void value_profiler_add_value(Method_Profile_Handle mph, U_32 instructionKey, POINTER_SIZE_INT valueToAdd)
{
    assert(mph != NULL);
    MethodProfile* mp = (MethodProfile*)mph;
    assert(mp->pc->type == EM_PCTYPE_VALUE);
    ValueMethodProfile* vmp = (ValueMethodProfile*)mp;
    return vmp->addNewValue(instructionKey, valueToAdd);
}

void value_profiler_dump_values(Method_Profile_Handle mph, std::ostream& os)
{
    assert(mph != NULL);
    MethodProfile* mp = (MethodProfile*)mph;
    assert(mp->pc->type == EM_PCTYPE_VALUE);
    ValueMethodProfile* vmp = (ValueMethodProfile*)mp;
    vmp->dumpValues(os);
}

Method_Profile_Handle value_profiler_create_profile(PC_Handle pch, Method_Handle mh, U_32 numkeys, U_32 keys[])
{
    assert(pch!=NULL);
    ProfileCollector* pc = (ProfileCollector*)pch;
    assert(pc->type == EM_PCTYPE_VALUE);
    ValueMethodProfile* profile = ((ValueProfileCollector*)pc)->createProfile(mh, numkeys, keys);
    return (Method_Profile_Handle)profile;
}