/*!
 * \file deadlockFinder.cpp
 * \brief This file is used by find deadlock.
 * Copyright (C) 2011-2015 Nippon Telegraph and Telephone Corporation
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 *
 */

#include <jvmti.h>
#include <jni.h>
#include <stdlib.h>
#include <sys/syscall.h>
#include <unistd.h>

#include "deadlockFinder.hpp"
#include "util.hpp"
#include "oopUtil.hpp"
#include "vmStructScanner.hpp"
#include "symbolFinder.hpp"

/* Defines. */

/*!
 * \brief Thread state macro.<br>
 *        This value means the thread is existing on native code.<br>
 *        Definition of "enum JavaThreadState".
 *        (_thread_in_native state is used in JVMTI:JvmtiThreadEventTransition)
 * \sa hotspot/src/share/vm/utilities/globalDefinitions.hpp
 */
#define THREAD_IN_NATIVE 4

/*!
 * \brief Thread state macro.<br>
 *        This value means the thread is existing on VM.<br>
 *        Definition of "enum JavaThreadState".
 * \sa hotspot/src/share/vm/utilities/globalDefinitions.hpp
 */
#define THREAD_IN_VM     6
/*!
 * \brief Thread state macro.<br>
 *        This value means the thread is existing on Java.<br>
 *        Definition of "enum JavaThreadState".
 * \sa hotspot/src/share/vm/utilities/globalDefinitions.hpp
 */
#define THREAD_IN_JAVA   8

/*!
 * \brief String of symbol which is function getting monitor's owner.
 */
#define GETLOCKOWNER_SYMBOL "_ZN18ObjectSynchronizer14get_lock_ownerE6Handleb"

/*!
 * \brief String of symbol which is function getting this thread.
 */
#define GETTHISTHREAD_SYMBOL "_ZN18ThreadLocalStorage15get_thread_slowEv"

/*!
 * \brief String of symbol which is function create ThreadSafepointState.
 */
#define THREADSAFEPOINTSTATE_CREATE_SYMBOL \
  "_ZN20ThreadSafepointState6createEP10JavaThread"

/*!
 * \brief String of symbol which is function destroy ThreadSafepointState.
 */
#define THREADSAFEPOINTSTATE_DESTROY_SYMBOL \
  "_ZN20ThreadSafepointState7destroyEP10JavaThread"

/*!
 * \brief String of symbol which is function monitor locking.
 */
#define MONITOR_LOCK_SYMBOL "_ZN7Monitor4lockEv"

/*!
 * \brief String of symbol which is function monitor locking.
 */
#define MONITOR_LOCK_WTIHOUT_CHECK_SYMBOL \
  "_ZN7Monitor28lock_without_safepoint_checkEv"

/*!
 * \brief String of symbol which is function monitor unlocking.
 */
#define MONITOR_UNLOCK_SYMBOL "_ZN7Monitor6unlockEv"

/*!
 * \brief String of symbol which is function monitor owned by self.
 */
#define MONITOR_OWNED_BY_SELF_SYMBOL "_ZNK7Monitor13owned_by_selfEv"

/*!
 * \brief String of symbol which is function "Threads_lock" monitor.
 */
#define THREADS_LOCK_SYMBOL "Threads_lock"

/* Class static variables. */

/*!
 * \brief Flag of deadlock is checkable now.
 */
bool TDeadlockFinder::flagCheckableDeadlock = false;

/*!
 * \brief Offset of field "osthread" in class "JavaThread".
 */
off_t TDeadlockFinder::ofsJavaThreadOsthread = -1;

/*!
 * \brief Offset of field "_threadObj" in class "JavaThread".
 */
off_t TDeadlockFinder::ofsJavaThreadThreadObj = -1;

/*!
 * \brief Offset of field "_thread_state" in class "JavaThread".
 */
off_t TDeadlockFinder::ofsJavaThreadThreadState = -1;

/*!
 * \brief Offset of field "_current_pending_monitor" in class "Thread".
 */
off_t TDeadlockFinder::ofsThreadCurrentPendingMonitor = -1;

/*!
 * \brief Offset of field "_thread_id" in class "OSThread".
 */
off_t TDeadlockFinder::ofsOSThreadThreadId = -1;

/*!
 * \brief Offset of field "_object" in class "ObjectMonitor".
 */
off_t TDeadlockFinder::ofsObjectMonitorObject = -1;

/*!
 * \brief Function pointer of "ObjectSynchronizer::get_lock_owner".
 */
TVMGetLockOwnerFunction TDeadlockFinder::get_lock_owner = NULL;

/*!
 * \brief Function pointer of "ThreadLocalStorage::get_thread_slow".
 */
TVMGetThisThreadFunction TDeadlockFinder::get_this_thread = NULL;

/*!
 * \brief Function pointer of "void ThreadSafepointState::create".
 */
TVMThreadFunction TDeadlockFinder::threadSafepointStateCreate = NULL;

/*!
 * \brief Function pointer of "void ThreadSafepointState::destroy".
 */
TVMThreadFunction TDeadlockFinder::threadSafepointStateDestroy = NULL;

/*!
 * \brief Function pointer of "void Monitor::lock()".
 */
TVMMonitorFunction TDeadlockFinder::monitor_lock = NULL;

/*!
 * \brief Function pointer of
 *        "void Monitor::lock_without_safepoint_check()".
 */
TVMMonitorFunction TDeadlockFinder::monitor_lock_without_check = NULL;

/*!
 * \brief Function pointer of "void Monitor::unlock()".
 */
TVMMonitorFunction TDeadlockFinder::monitor_unlock = NULL;

/*!
 * \brief Function pointer of "bool Monitor::owned_by_self()".
 */
TVMOwnedBySelfFunction TDeadlockFinder::monitor_owned_by_self = NULL;

/*!
 * \brief Variable pointer of "Threads_lock" monitor.
 */
void* TDeadlockFinder::threads_lock = NULL;

/* Common methods. */

/* Class methods. */

/*!
 * \brief Global initialization.
 * \return Process result.
 * \warning Please call only once from main thread.
 */
bool TDeadlockFinder::globalInitialize(void) {
  
  /* Variable for return code. */
  bool result = true;
  
  /* Get function of ObjectSynchronizer::get_lock_owner(). */
  get_lock_owner = (TVMGetLockOwnerFunction)symFinder->findSymbol(
                                                            GETLOCKOWNER_SYMBOL);
  
  /* Get function of this thread with JVM inner class instance. */
  get_this_thread = (TVMGetThisThreadFunction)symFinder->findSymbol(
                                                           GETTHISTHREAD_SYMBOL);
  
  /* Get function of thread operation. */
  threadSafepointStateCreate = (TVMThreadFunction)symFinder->findSymbol(
                                             THREADSAFEPOINTSTATE_CREATE_SYMBOL);
  threadSafepointStateDestroy = (TVMThreadFunction)symFinder->findSymbol(
                                            THREADSAFEPOINTSTATE_DESTROY_SYMBOL);
  
  /* Get function of monitor operation. */
  monitor_lock = (TVMMonitorFunction)symFinder->findSymbol(MONITOR_LOCK_SYMBOL);
  monitor_lock_without_check = (TVMMonitorFunction)symFinder->findSymbol(
                                              MONITOR_LOCK_WTIHOUT_CHECK_SYMBOL);
  monitor_unlock = (TVMMonitorFunction)symFinder->findSymbol(
                                                          MONITOR_UNLOCK_SYMBOL);
  monitor_owned_by_self = (TVMOwnedBySelfFunction)symFinder->findSymbol(
                                                   MONITOR_OWNED_BY_SELF_SYMBOL);
  
  /* Get function of "Threads_lock" monitor. */
  threads_lock = symFinder->findSymbol(THREADS_LOCK_SYMBOL);
  
  /* if failure get function pointer "get_lock_owner()". */
  if (unlikely(get_lock_owner == NULL || get_this_thread == NULL
    || threadSafepointStateCreate == NULL
    || threadSafepointStateDestroy == NULL
    || monitor_lock == NULL || monitor_lock_without_check == NULL
    || monitor_unlock == NULL || monitor_owned_by_self == NULL
    || threads_lock == NULL)) {
    
    PRINT_WARN_MSG("Failure search deadlock function's symbol.");
    result = false;
  }
  
  /* Symbol offsets. */
  TOffsetNameMap symOffsetList[] = {
    {"JavaThread",    "_osthread",
      &ofsJavaThreadOsthread,          NULL},
    {"JavaThread",    "_threadObj",
      &ofsJavaThreadThreadObj,         NULL},
    {"JavaThread",    "_thread_state",
      &ofsJavaThreadThreadState,       NULL},
    {"Thread",        "_current_pending_monitor",
      &ofsThreadCurrentPendingMonitor, NULL},
    {"OSThread",      "_thread_id",
      &ofsOSThreadThreadId,            NULL},
    {"ObjectMonitor", "_object",
      &ofsObjectMonitorObject,         NULL},
    /* End marker. */
    {NULL, NULL, NULL}
  };
  
  /* Search offset. */
  vmScanner->GetDataFromVMStructs(symOffsetList);
  
  /* If failure get offset information. */
  if (unlikely(ofsJavaThreadOsthread  == -1
    || ofsJavaThreadThreadObj         == -1
    || ofsJavaThreadThreadState       == -1
    || ofsThreadCurrentPendingMonitor == -1
    || ofsOSThreadThreadId            == -1
    || ofsObjectMonitorObject         == -1)) {
    
    PRINT_WARN_MSG("Failure search offset in VMStructs.");
    result = false;
  }
  
  flagCheckableDeadlock = result;
  return result;
}

/*!
 * \brief TDeadlockFinder constructor.
 * \param event [in] Callback is used on deadlock occurred.
 */
TDeadlockFinder::TDeadlockFinder(TDeadlockEventFunc event)
                   : TAgentThread("HeapStats Deadlock Finder"), occurTime(0) {
  
  /* Sanity check. */
  if (unlikely(event == NULL)) {
    throw "Event callback is NULL.";
  }
  callFunc = event;
}

/*!
 * \brief TDeadlockFinder destructor.
 */
TDeadlockFinder::~TDeadlockFinder(void) {
  /* none. */
}

/*!
 * \brief Check deadlock.
 * \param monitor [in]  Monitor object of thread contended.
 * \param list    [out] List of deadlock occurred threads.
 * \return Number of deadlock occurred threads.<br>
 *         Value is 0, if deadlock isn't occurred.
 */
int TDeadlockFinder::checkDeadlock(jobject monitor, TDeadlockList **list) {
  
  /* Sanity check. */
  if (unlikely(monitor == NULL || list == NULL)) {
    return 0;
  }
  
  int deadlockCount = 0;
  if (likely(flagCheckableDeadlock)) {
    
    void *thisThreadPtr = get_this_thread();
    void *thread_lock = *(void**)threads_lock;
    if (unlikely(thisThreadPtr == NULL || thread_lock == NULL)) {
      /*
       * Thread class in JVM and thread lock should be set.
       * TDeadlockFinder::checkDeadlock() is called by MonitorContendedEnter
       * JVMTI event. If this event is fired, current (this) thread must be
       * live.
       */
      PRINT_WARN_MSG("Deadlock detection failed: Cannot get current thread info.");
      return 0;
    }
    
    /* Get self thread id. */
    pid_t threadId = syscall(SYS_gettid);
    
    int *status = (int *)incAddress(thisThreadPtr, ofsJavaThreadThreadState);
    int original_status = *status;
    
    /*
     * Normally thread status is "_thread_in_native"
     * when thread is running in JVMTI event.
     * But thread status maybe changed "_thread_in_vm",
     * if call "get_lock_owner" and set true to paramter "doLock".
     * If VMThread found this thread has such status
     * when call "examine_state_of_thread" at synchronizing safepoint,
     * By JVM decided that the thread is waiting VM and callback,
     * thread state at safepoint set "_call_back" flag.
     * Besides, at end of JVMTI envent callback,
     * thread was changed thread status to "_thread_in_native_trans"
     * from "_thread_in_vm"
     * and JVM check thread about running status at safepoint.
     * JVM misunderstand deadlock occurred, so JVM abort by self.
     * Why JVM misunderstood.
     *  1, Safepoint code wait "_thread_in_native_trans" thread.
     *  2, "_call_back" flag means wait VM and callback.
     *  -> VMThread wait the thread and the thread wait VMThread.
     * 
     * So thread status reset here by force.
     */
    *status = THREAD_IN_VM;

    /* Check deadlock. */
    bool foundDeadlock = findDeadLock(threadId, monitor);

    if (unlikely(foundDeadlock)) {

      /* Get threads. */
      getLockedThreads(threadId, monitor, list);

      /* Count list item. */
      for (TDeadlockList *item = (*list); item != NULL; item = item->next) {
        deadlockCount++;
      }

    }

    if (*status == THREAD_IN_VM) {
      bool needLock = !monitor_owned_by_self(thread_lock);
      
      /*
       * Lock monitor to avoiding a collision
       * with safepoint operation to "ThreadSafepointState".
       * E.g. "examine_state_of_thread".
       */
      if (likely(needLock)) {
        if (isAtSafepoint()) {
          monitor_lock_without_check(thread_lock);
        } else {
          monitor_lock(thread_lock);
        }
      }
      
      /* Reset "_thread_state". */
      *status = original_status;
      /* Reset "_safepoint_state". */
      threadSafepointStateDestroy(thisThreadPtr);
      threadSafepointStateCreate(thisThreadPtr);
      
      /* Release monitor. */
      if (likely(needLock)) {
        monitor_unlock(thread_lock);
      }
    }
  }
  
  return deadlockCount;
}

/*!
 * \brief JThread entry point.
 * \param jvmti [in] JVMTI environment object.
 * \param jni   [in] JNI environment object.
 * \param data  [in] Pointer of TDeadlockFinder.
 */
void JNICALL TDeadlockFinder::entryPoint(jvmtiEnv *jvmti,
                                             JNIEnv *jni, void *data) {
  
  /* Get self. */
  TDeadlockFinder *controller = (TDeadlockFinder *)data;
  /* Change running state. */
  controller->_isRunning = true;
  
  /* Loop for agent run. */
  while (!controller->_terminateRequest) {
    /* Variable for notification flag. */
    bool needProcess = false;
    
    ENTER_PTHREAD_SECTION(&controller->mutex) {
      
      /* If no exists request. */
      if (likely(controller->_numRequests == 0)) {
        
        /* Wait for notification or termination. */
        pthread_cond_wait(&controller->mutexCond, &controller->mutex);
      }
      
      /* If exists request. */
      if (likely(controller->_numRequests > 0)) {
        controller->_numRequests--;
        needProcess = true;
        
        /* Load and pop last deadlock datetime. */
        controller->occurTime = controller->timeList.front();
        controller->timeList.pop();
      }
    } EXIT_PTHREAD_SECTION(&controller->mutex)
    
    /* If get notification. */
    if (likely(needProcess)) {
      
      /* Call event callback. */
      (*controller->callFunc)(jvmti, jni, OccurredDeadlock);
    }
  }
  
  /* Change running state */
  controller->_isRunning = false;
}

/*!
 * \brief Make and begin Jthread.
 * \param jvmti [in] JVMTI environment object.
 * \param env   [in] JNI environment object.
 */
void TDeadlockFinder::start(jvmtiEnv *jvmti, JNIEnv *env) {
  
  /* Call super class's method. */
  TAgentThread::start(jvmti, env, TDeadlockFinder::entryPoint,
                                              this, JVMTI_THREAD_MIN_PRIORITY);

}

/*!
 * \brief Notify occurred deadlock to this thread from other thread.
 * \param aTime [in] Time of occurred deadlock.
 */
void TDeadlockFinder::notify(jlong aTime) {
  
  /* Send notification and count notify. */
  ENTER_PTHREAD_SECTION(&this->mutex) {
    
    /* Count and store data. */
    this->_numRequests++;
    timeList.push(aTime);
    
    /* Notify occurred deadlock. */
    pthread_cond_signal(&this->mutexCond);
    
  } EXIT_PTHREAD_SECTION(&this->mutex)
}

/*!
 * \brief DeadLock search (recursive call).
 * \param startId [in] Thread id of TDeadlockFinder caller.
 * \param monitor [in] Monitor object of thread contended.
 */
FASTCALL bool TDeadlockFinder::findDeadLock(pid_t startId, jobject monitor) {
  
  void *threadPtr        = NULL;
  int *status            = NULL;
  void *nativeThread     = NULL;
  pid_t *ownerId         = NULL;
  void *contendedMonitor = NULL;
  jobject monitorOop     = NULL;
  
  /* Get owner thread of this monitor. */
  threadPtr = get_lock_owner(monitor, !isAtSafepoint());
  
  /* No deadlock (no owner thread of this monitor). */
  if (unlikely(threadPtr == NULL)) {
    return false;
  }
  
  /* Go deadlock check!!! */
  /* Is owner thread is self ? */
  
  /* Get OSThread ptr related to JavaThread. */
  nativeThread =
              (void *)*(ptrdiff_t *)incAddress(threadPtr, ofsJavaThreadOsthread);
  
  /* If failure get native thread. */
  if (unlikely(nativeThread == NULL)) {
    return false;
  }
  
  /* Get nid (LWP ID). */
  ownerId = (pid_t *)incAddress(nativeThread, ofsOSThreadThreadId);
  
  /* If occurred deadlock. */
  if (unlikely(*ownerId == startId)) {
    
    /* DeadLock !!! */
    return true;
  }
  
  /* Thread status check. */
  status = (int *)incAddress(threadPtr, ofsJavaThreadThreadState);
  if ((*status == THREAD_IN_JAVA) || (*status == THREAD_IN_VM)) {
    
    /* Owner thread is running. */
    return false;
  }
  
  /* Get ObjectMonitor pointer. */
  contendedMonitor =
     (void *)*(ptrdiff_t *)incAddress(threadPtr, ofsThreadCurrentPendingMonitor);
  /* If pointer is illegal. */
  if (unlikely(contendedMonitor == NULL)) {
    return false;
  }
  
  monitorOop = (jobject)incAddress(contendedMonitor, ofsObjectMonitorObject);
  /* If java thread already has monitor. */
  if (unlikely((monitorOop == NULL) || (monitorOop == monitor))) {
    return false;
  }
  
  /* No deadlock in "this" thread. */
  
  /* Execute recursive call. */
  return findDeadLock(startId, monitorOop);
}

/*!
 * \brief Get threads which has occurred deadlock.
 * \param startId [in]  Thread id of TDeadlockFinder caller.
 * \param monitor [in]  Monitor object of thread contended.
 * \param list    [out] List of deadlock occurred threads.
 */
void TDeadlockFinder::getLockedThreads(pid_t startId,
                                        jobject monitor, TDeadlockList **list) {
  
  pid_t *ownerId = NULL;
  TDeadlockList *listHead = NULL;
  TDeadlockList *oldRec   = NULL;
  bool flagFailure = false;
  
  /* Infinite loop. */
  while (true) {
    void *threadPtr        = NULL;
    void *nativeThread     = NULL;
    void *contendedMonitor = NULL;
    jthread jThreadObj     = NULL;
    TDeadlockList *threadRec = NULL;
    
    /* Get owner thread of this monitor. */
    threadPtr = get_lock_owner(monitor, !isAtSafepoint());
    
    if (unlikely(threadPtr == NULL)) {
      /* Shouldn't reach to here. */
      PRINT_DEBUG_MSG("Deadlock detection failed: Cannot get lock owner thread.");
      flagFailure = true;
      break;
    }
    
    /* Convert to jni object. */
    jThreadObj = (jthread)incAddress(threadPtr, ofsJavaThreadThreadObj);
    
    /* Create list item. */
    threadRec = (TDeadlockList*)malloc(sizeof(TDeadlockList));
    if (unlikely(threadRec == NULL)) {
      /* Shouldn't reach to here. */
      PRINT_WARN_MSG(
         "Deadlock detection failed: Cannot allocate memory for TDeadLockList.");
      flagFailure = true;
      break;
    }
    
    /* Store thread. */
    threadRec->thread = jThreadObj;
    threadRec->next   = NULL;
    if (likely(oldRec != NULL)) {
      oldRec->next = threadRec;
    } else {
      listHead = threadRec;
    }
    oldRec = threadRec;
    
    /* Get OSThread ptr related to JavaThread. */
    nativeThread =
              (void *)*(ptrdiff_t *)incAddress(threadPtr, ofsJavaThreadOsthread);
    
    if (unlikely(nativeThread == NULL)) {
      /* Shouldn't reach to here. */
      PRINT_DEBUG_MSG("Deadlock detection failed: Cannot get native thread.");
      flagFailure = true;
      break;
    }
    
    /* Get nid (LWP ID). */
    ownerId = (pid_t *)incAddress(nativeThread, ofsOSThreadThreadId);
    
    /* If all thread already has collected. */
    if (*ownerId == startId) {
      break;
    }
    
    /* Get ObjectMonitor pointer. */
    contendedMonitor =
     (void *)*(ptrdiff_t *)incAddress(threadPtr, ofsThreadCurrentPendingMonitor);
    
    if (unlikely(contendedMonitor == NULL)) {
      /* Shouldn't reach to here. */
      PRINT_DEBUG_MSG("Deadlock detection failed: Cannot get contended monitor.");
      flagFailure = true;
      break;
    }
    
    monitor = (jobject)incAddress(contendedMonitor, ofsObjectMonitorObject);
    
    /* If illegal state. */
    if (unlikely(monitor == NULL)) {
      /* Shouldn't reach to here. */
      PRINT_DEBUG_MSG("Deadlock detection failed: Cannot get monitor object.");
      flagFailure = true;
      break;
    }
  }
  
  /* If failure get deadlock threads. */
  if (unlikely(flagFailure)) {
    freeDeadlockList(listHead);
  } else {
    (*list) = listHead;
  }
  
  return;
}

/*!
 * \brief Deallocate deadlock thread list.
 * \param list [in] List of deadlock occurred threads.
 */
void TDeadlockFinder::freeDeadlockList(TDeadlockList *list) {
  
  /* Sanity check. */
  if (unlikely(list == NULL)) {
    return;
  }
  
  /* Cleanup. */
  for (TDeadlockList *next = list->next; next != NULL; ) {
    TDeadlockList *listItem = next;
    next = next->next;
    
    free(listItem);
  }
  free(list);
}