sam-t2/sam/cpus/vonk/ss/api/memsync/src/TsoChecker.h

/*
* ========== Copyright Header Begin ==========================================
*
* OpenSPARC T2 Processor File: TsoChecker.h
* Copyright (c) 2006 Sun Microsystems, Inc.  All Rights Reserved.
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES.
*
* The above named program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public
* License version 2 as published by the Free Software Foundation.
*
* The above named 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 work; if not, write to the Free Software
* Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA.
*
* ========== Copyright Header End ============================================
*/
#ifndef RIESLING_TSOCHECKER_H
#define RIESLING_TSOCHECKER_H
/************************************************************************
**
**  Copyright (C) 2002, Sun Microsystems, Inc.
**
**  Sun considers its source code as an unpublished, proprietary
**  trade secret and it is available only under strict license provisions.
**  This copyright notice is placed here only to protect Sun in the event
**  the source is deemed a published work. Disassembly, decompilation,
**  or other means of reducing the object code to human readable form
**  is prohibited by the license agreement under which this code is
**  provided to the user or company in possession of this copy."
**
*************************************************************************/
#include <iostream>
#include <fstream>
#include <list>
#include <vector>

#include "TsoCheckerDefs.h"
#include "TsoCheckerCmd.h"
#include "TsoNode.h"
#include "TsoEdge.h"
#include "MemoryAccessHistory.h"

namespace Tso {

  /**
   * TSOchecker is designed to perform on-the-fly TSO memory consistency model check
   * in the RTL-Riesling co-sim environment with no limiation on which diags can be
   * checked against TSO compliance. The kernel of the algorithm is a digraph which
   * is generated according to instruction's memory access order, program order, and
   * data dependence, and is constructed in a way that a cycle in the grpah indicates
   * a TSO violation.
   * <p>
   * Note that instructions that do not need to comply with TSO model are not included
   * in forming the digraph. These instructions include block load, block store, and
   * block init store, as well as those accessing to I/O address space. Membar is also
   * not considered in current algorithm, however, this can be in the enhancement plan.
   * <p>
   * The TSOchecker defines a single API to other program. The TsoChecker class is the
   * class where the API locates. It implements the service routines to handle this API.
   * The fields of this API are defined in the TsoCheckerCmd.h.
   * <p>
   * Whenever the API method is called, a node is created. If the entry belongs to the
   * type of instructions that have to comply with the TSO memory model, it is placed
   * into the digrpah. However, all entries for one instruction can appear as only one
   * node in the graph.  The routine then create edges between nodes based on their
   * data dependence and program order constraints. An edge can be a output-depednence
   * edge, a flow-dependece edge, an anti-dependence edge, a load-load program order
   * edge, a load-store program order edge, or a store-store program order edge. Finally,
   * the program checks if there is a cycle in the digraph, and prun the digraph.
   * <p>
   * If there is a TSO violation, the program throw an exception and print out the existing
   * digraph in a text file named TsoViolationDiGraph, which can be processed using the
   * dot program (as of this writing, it is in /net/suntools/export/tools/sparc/bin/dot).
   * <p>
   * @see TsoCheckerCmd.h
   * @see MemoryAccessHistory.h
   * @see MemoryAccessHistoryItem.h
   * @see TsoNode.h
   * @see TsoEdge.h
   */
  class TsoChecker {

  public:
    /**
     * Default constructor
     */
    TsoChecker();

    /**
     * Copy constructor
     *
     * @param orig The TsoChecker object to copy.
     */
    TsoChecker( const TsoChecker &orig );

    /**
     * Destructor
     */
    virtual ~TsoChecker();

    /**
     * Equality operator
     *
     * @param rhs The right hand side of the equality operator
     * @return Return true if this objec and rhs are equal,
     * otherwise return false
     */
    bool operator==( const TsoChecker &rhs ) const;

    /**
     * Assignment operator
     *
     * @param rhs The right hand side of the assignment operator.
     * @return The lvalue of the assignment.
     */
    const TsoChecker & operator=( const TsoChecker &rhs );

    /**
     * Return a string representation of this TsoChecker object.
     */
    std::string toString() const;

    /**
     * Initialize private data structures
     */
    void init(int nstrands);

    /**
     * Handle memory access registration and TSO violation check. <br>
     * This is the main method other program calls to perform TSO violation check.
     * It performs the following tasks:
     * - create TsoNode for an input request
     * - book-keep the content of a TsoNode, especially if a node's instruction
     *   contains multiple TSO node.
     * - maintain the node in the tmpList_ until they form a consecutive instruction
     *   sequence
     * - form data dependence edges of the node
     * - form program order edges of the nodes that is in consecutive instruction sequence
     * - check TSO violation and prun the TSO digraph
     * - report error and print out the TSO digraph if violating the TSO rules
     *
     * @param cmd TsoCheckerCmd data structure containing TSO API fields
     * @see TsoCheckerCmd.h
     */
    void input(TsoCheckerCmd& cmd);

    /**
     * Another form of input() method
     */
    void input(uint32_t tid, uint64_t iseq, enum INSTR_TYPE itype, enum MEM_CMD cmd,
               uint64_t addr, uint64_t data, uint8_t sizeV, enum DATA_SRC dsrc,
               uint64_t macc, uint64_t gobs, uint64_t time);

    /**
     * Find the node in tmpList_ that belongs to the same instruction
     * @param cmd The entry TsoCheckerCmd data structure
     * @return matched TSO node pointer or NULL
     */
    TsoNode* findNode(TsoCheckerCmd& cmd);

    /**
     * Find the prvious TSO node in the nodeList_
     * @param ntype TSO node type, TSO_LOAD or TSO_STORE
     * @param tid Thread ID used to select nodeList_
     * @return matched TSO node pointer or NULL
     * @see TsoCheckerDefs.h
     */
    TsoNode* findPrev(enum TSO_NODE_TYPE ntype, uint32_t tid);

    /**
     * Insert a node into tmpList_ in is iseq ascending order
     * @param tid Thread ID to select tmpList_
     * @param np Node pointer to be inserted
     */
    void tmpListInsert(uint32_t tid, TsoNode *np);

    /**
     * Form data dependence edge for the node. The types of data dependence edges
     * include flow, anti, and output. Two methods, storeCommit() and loadAccess()
     * in the MemoryAccessHistory class are called depending on the input node type.
     * @param np Pointer of the node
     * @see MemoryAccessHistory.h
     */
    void formDataDependenceEdges(TsoNode *np);

    /**
     * Form program order edge for the node. <br>
     * If the node is a load, then
     * - a load-load program order edge is created from the previous TSO load to this load.
     * If the node is a store, then
     * - a load-store program order edge is created from the provious TSO load to this store,
     * - a store-store program order edge is created from the provious TSO store to this store
     */
    void formProgramOrderEdges(uint32_t tid);

    /**
     * Check to see if a node can be removed. A node does not check for TSO violation
     * unless it is removable. <br>
     * A load node can be removed as long as it is not the last load node in the nodeList_. <br>
     * A store node cannot be removed unless the following conditions are all met:
     * - not the last store node in the nodeList_
     * - all nodes corresponding to its valid bytes of data all become old
     * - its retire time has passed
     * @param np Pointer of node to be checked
     * @return a boolean
     */
    bool canRemove(TsoNode *np);

    /**
     * Check if there is a path from nodeP to startNodeP in the digraph consisting of
     * TSO nodes, data dependence edges, and program order edges. <br>
     * Checking TSO violation in this algorithm is equivalen to check if there is a cycle
     * in the digraph. checkCycle(&n1, &n1) can be used to check if a cycle is formed for
     * node n1.
     * @param nodeP Pointer of node to be checked
     * @param startNodeP Pointer of node that begins the check
     * @return a boolean
     */
    bool checkCycle(TsoNode *nodeP, TsoNode *startNodeP);

    /**
     * Remove a node in the MemoryAccessHistory and all its edges.
     * @param np Pointer of the node
     */
    void removeNode(TsoNode *np);

    /**
     * Return a string of a node's output edge in the format of dot program
     * @param node Pointer of the node
     * @return the string
     */
    std::string printOutEdges(TsoNode* node);

    /**
     * Print the digraph for the nodes in the nodeList_ to output file named
     * TsoViolationDiGraph (flag=ERROR) or TsoDigraph (flag=NORMAL) in the
     * dot-processable text format.
     * <p>
     * - Use "dot -Tps TsoViolationDigraph -o TsoViolationDigraph.ps" to
     *   generate ps file for TSO violation nodes
     * - Use "dot -Tps TsoDigraph -o TsoDigraph.ps" to
     *   generate ps file for remaining TSO nodes
     * - goto http://www.research.att.com/sw/tools/graphviz for more info
     *   about the dot program
     * @param flag Flag determines which output file name to be used
     */
    void printNodeList(int flag);

    /**
     * This method is the same as printNodeList(NORMAL).
     */
    void printNodeList();

    /******************************************************************
     * Private variable get/set methods
     ******************************************************************/
    void setTime(uint64_t time) { time_ = time; }
    uint64_t getTime() const { return time_; }

  protected:

  private:
    /**
     * maccHist_ contains the memory update history based on the store instructions
     * @see MemoryAccessHistory.h
     */
    MemoryAccessHistory  maccHist_;

    /**
     * nodeList_ is a pointer to an array of TsoNode pointer lists: one list per thread. <br>
     * The list contains nodes that have been in program order, and are candidates
     * for TSO vialation check and prun
     */
    std::list<TsoNode*>  *nodeList_;

    /**
     * tmpList_ is a pointer to an array of TsoNode pointer lists: one list per thread. <br>
     * The list contains node that have not yet been in program order.
     */
    std::list<TsoNode*>  *tmpList_;

    /**
     * lastPoIseq_ is a pointer to an uint64_t array: one field per thread. <br>
     * It indicates the last Instruction sequence number that is in the nodeList_.
     */
    uint64_t             *lastPoIseq_; // last Program Order Iseq

    /**
     * time_ indicates the time when the access happens
     */
    uint64_t             time_;
    int listSize_;
  };
} /* namespace Tso */

#endif /* _TSOCHECKER_H */