// $Id: buffer_state.cpp 5188 2012-08-30 00:31:31Z dub $

/*
 Copyright (c) 2007-2012, Trustees of The Leland Stanford Junior University
 All rights reserved.

 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions are met:

 Redistributions of source code must retain the above copyright notice, this 
 list of conditions and the following disclaimer.
 Redistributions in binary form must reproduce the above copyright notice, this
 list of conditions and the following disclaimer in the documentation and/or
 other materials provided with the distribution.

 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 
 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
 ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
 ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/

/*buffer_state.cpp
 *
 * This class is the buffere state of the next router down the channel
 * tracks the credit and how much of the buffer is in use 
 */

#include <iostream>
#include <sstream>
#include <cstdlib>
#include <cassert>
#include <limits>

#include "booksim.hpp"
#include "buffer_state.hpp"
#include "random_utils.hpp"
#include "globals.hpp"

//#define DEBUG_FEEDBACK
//#define DEBUG_SIMPLEFEEDBACK

BufferState::BufferPolicy::BufferPolicy(Configuration const & config, BufferState * parent, const string & name)
: Module(parent, name), _buffer_state(parent)
{
}

void BufferState::BufferPolicy::TakeBuffer(int vc) {
}

void BufferState::BufferPolicy::SendingFlit(Flit const * const f) {
}

void BufferState::BufferPolicy::FreeSlotFor(int vc) {
}

BufferState::BufferPolicy * BufferState::BufferPolicy::New(Configuration const & config, BufferState * parent, const string & name)
{
  BufferPolicy * sp = NULL;
  string buffer_policy = config.GetStr("buffer_policy");
  if(buffer_policy == "private") {
    sp = new PrivateBufferPolicy(config, parent, name);
  } else if(buffer_policy == "shared") {
    sp = new SharedBufferPolicy(config, parent, name);
  } else if(buffer_policy == "limited") {
    sp = new LimitedSharedBufferPolicy(config, parent, name);
  } else if(buffer_policy == "dynamic") {
    sp = new DynamicLimitedSharedBufferPolicy(config, parent, name);
  } else if(buffer_policy == "shifting") {
    sp = new ShiftingDynamicLimitedSharedBufferPolicy(config, parent, name);
  } else if(buffer_policy == "feedback") {
    sp = new FeedbackSharedBufferPolicy(config, parent, name);
  } else if(buffer_policy == "simplefeedback") {
    sp = new SimpleFeedbackSharedBufferPolicy(config, parent, name);
  } else {
    cout << "Unknown buffer policy: " << buffer_policy << endl;
  }
  return sp;
}

BufferState::PrivateBufferPolicy::PrivateBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : BufferPolicy(config, parent, name)
{
  int const vcs = config.GetInt( "num_vcs" );
  int const buf_size = config.GetInt("buf_size");
  if(buf_size <= 0) {
    _vc_buf_size = config.GetInt("vc_buf_size");
  } else {
    _vc_buf_size = buf_size / vcs;
  }
  assert(_vc_buf_size > 0);
}

void BufferState::PrivateBufferPolicy::SendingFlit(Flit const * const f)
{
  int const vc = f->vc;
  if(_buffer_state->OccupancyFor(vc) > _vc_buf_size) {
    ostringstream err;
    err << "Buffer overflow for VC " << vc;
    Error(err.str());
  }
}

bool BufferState::PrivateBufferPolicy::IsFullFor(int vc) const
{
  return (_buffer_state->OccupancyFor(vc) >= _vc_buf_size);
}

int BufferState::PrivateBufferPolicy::AvailableFor(int vc) const
{
  return _vc_buf_size - _buffer_state->OccupancyFor(vc);
}

int BufferState::PrivateBufferPolicy::LimitFor(int vc) const
{
  return _vc_buf_size;
}

BufferState::SharedBufferPolicy::SharedBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : BufferPolicy(config, parent, name), _shared_buf_occupancy(0)
{
  int const vcs = config.GetInt( "num_vcs" );
  int num_private_bufs = config.GetInt("private_bufs");
  if(num_private_bufs < 0) {
    num_private_bufs = vcs;
  } else if(num_private_bufs == 0) {
    num_private_bufs = 1;
  }
  
  _private_buf_occupancy.resize(num_private_bufs, 0);

  _buf_size = config.GetInt("buf_size");
  if(_buf_size < 0) {
    _buf_size = vcs * config.GetInt("vc_buf_size");
  }

  _private_buf_size = config.GetIntArray("private_buf_size");
  if(_private_buf_size.empty()) {
    int const bs = config.GetInt("private_buf_size");
    if(bs < 0) {
      _private_buf_size.push_back(_buf_size / num_private_bufs);
    } else {
      _private_buf_size.push_back(bs);
    }
  }
  _private_buf_size.resize(num_private_bufs, _private_buf_size.back());
  
  vector<int> start_vc = config.GetIntArray("private_buf_start_vc");
  if(start_vc.empty()) {
    int const sv = config.GetInt("private_buf_start_vc");
    if(sv < 0) {
      start_vc.resize(num_private_bufs);
      for(int i = 0; i < num_private_bufs; ++i) {
	start_vc[i] = i * vcs / num_private_bufs;
      }
    } else {
      start_vc.push_back(sv);
    }
  }
  
  vector<int> end_vc = config.GetIntArray("private_buf_end_vc");
  if(end_vc.empty()) {
    int const ev = config.GetInt("private_buf_end_vc");
    if(ev < 0) {
      end_vc.resize(num_private_bufs);
      for(int i = 0; i < num_private_bufs; ++i) {
	end_vc[i] = (i + 1) * vcs / num_private_bufs - 1;
      }
    } else {
      end_vc.push_back(ev);
    }
  }

  _private_buf_vc_map.resize(vcs, -1);
  _shared_buf_size = _buf_size;
  for(int i = 0; i < num_private_bufs; ++i) {
    _shared_buf_size -= _private_buf_size[i];
    assert(start_vc[i] <= end_vc[i]);
    for(int v = start_vc[i]; v <= end_vc[i]; ++v) {
      assert(_private_buf_vc_map[v] < 0);
      _private_buf_vc_map[v] = i;
    }
  }
  assert(_shared_buf_size >= 0);

  _reserved_slots.resize(vcs, 0);
}

void BufferState::SharedBufferPolicy::ProcessFreeSlot(int vc)
{
  int i = _private_buf_vc_map[vc];
  --_private_buf_occupancy[i];
  if(_private_buf_occupancy[i] < 0) {
    ostringstream err;
    err << "Private buffer occupancy fell below zero for buffer " << i;
    Error(err.str());
  } else if(_private_buf_occupancy[i] >= _private_buf_size[i]) {
    --_shared_buf_occupancy;
    if(_shared_buf_occupancy < 0) {
      Error("Shared buffer occupancy fell below zero.");
    }
  }
}

void BufferState::SharedBufferPolicy::SendingFlit(Flit const * const f)
{
  int const vc = f->vc;
  if(_reserved_slots[vc] > 0) {
    --_reserved_slots[vc];
  } else {
    int i = _private_buf_vc_map[vc];
    ++_private_buf_occupancy[i];
    if(_private_buf_occupancy[i] > _private_buf_size[i]) {
      ++_shared_buf_occupancy;
      if(_shared_buf_occupancy > _shared_buf_size) {
	Error("Shared buffer overflow.");
      }
    }
  }
  if(f->tail) {
    while(_reserved_slots[vc]) {
      --_reserved_slots[vc];
      ProcessFreeSlot(vc);
    }
  }
}

void BufferState::SharedBufferPolicy::FreeSlotFor(int vc)
{
  if(!_buffer_state->IsAvailableFor(vc) && _buffer_state->IsEmptyFor(vc)) {
    ++_reserved_slots[vc];
  } else {
    ProcessFreeSlot(vc);
  }
}

bool BufferState::SharedBufferPolicy::IsFullFor(int vc) const
{
  int i = _private_buf_vc_map[vc];
  return ((_reserved_slots[vc] == 0) &&
	  (_private_buf_occupancy[i] >= _private_buf_size[i]) &&
	  (_shared_buf_occupancy >= _shared_buf_size));
}

int BufferState::SharedBufferPolicy::AvailableFor(int vc) const
{
  int i = _private_buf_vc_map[vc];
  return (_reserved_slots[vc] + 
	  max(_private_buf_size[i] - _private_buf_occupancy[i], 0) +
	  (_shared_buf_size - _shared_buf_occupancy));
}

int BufferState::SharedBufferPolicy::LimitFor(int vc) const
{
  int i = _private_buf_vc_map[vc];
  return (_private_buf_size[i] + _shared_buf_size);
}

BufferState::LimitedSharedBufferPolicy::LimitedSharedBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : SharedBufferPolicy(config, parent, name), _active_vcs(0)
{
  _vcs = config.GetInt("num_vcs");
  _max_held_slots = config.GetInt("max_held_slots");
  if(_max_held_slots < 0) {
    _max_held_slots = _buf_size;
  }
}

void BufferState::LimitedSharedBufferPolicy::TakeBuffer(int vc)
{
  ++_active_vcs;
  if(_active_vcs > _vcs) {
    Error("Number of active VCs is too large.");
  }
}

void BufferState::LimitedSharedBufferPolicy::SendingFlit(Flit const * const f)
{
  SharedBufferPolicy::SendingFlit(f);
  if(f->tail) {
    --_active_vcs;
    if(_active_vcs < 0) {
      Error("Number of active VCs fell below zero.");
    }
  }
}

bool BufferState::LimitedSharedBufferPolicy::IsFullFor(int vc) const
{
  return (SharedBufferPolicy::IsFullFor(vc) ||
	  (_buffer_state->OccupancyFor(vc) >= _max_held_slots));
}

int BufferState::LimitedSharedBufferPolicy::AvailableFor(int vc) const
{
  return min(SharedBufferPolicy::AvailableFor(vc), 
	     _max_held_slots - _buffer_state->OccupancyFor(vc));
}

int BufferState::LimitedSharedBufferPolicy::LimitFor(int vc) const
{
  return min(SharedBufferPolicy::LimitFor(vc), _max_held_slots);
}

BufferState::DynamicLimitedSharedBufferPolicy::DynamicLimitedSharedBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : LimitedSharedBufferPolicy(config, parent, name)
{
  _max_held_slots = _buf_size;
}

void BufferState::DynamicLimitedSharedBufferPolicy::TakeBuffer(int vc)
{
  LimitedSharedBufferPolicy::TakeBuffer(vc);
  assert(_active_vcs > 0);
  _max_held_slots = _buf_size / _active_vcs;
  assert(_max_held_slots > 0);
}

void BufferState::DynamicLimitedSharedBufferPolicy::SendingFlit(Flit const * const f)
{
  LimitedSharedBufferPolicy::SendingFlit(f);
  if(f->tail && _active_vcs) {
    _max_held_slots = _buf_size / _active_vcs;
  }
  assert(_max_held_slots > 0);
}

BufferState::ShiftingDynamicLimitedSharedBufferPolicy::ShiftingDynamicLimitedSharedBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : DynamicLimitedSharedBufferPolicy(config, parent, name)
{

}

void BufferState::ShiftingDynamicLimitedSharedBufferPolicy::TakeBuffer(int vc)
{
  LimitedSharedBufferPolicy::TakeBuffer(vc);
  assert(_active_vcs);
  int i = _active_vcs - 1;
  _max_held_slots = _buf_size;
  while(i) {
    _max_held_slots >>= 1;
    i >>= 1;
  }
  assert(_max_held_slots > 0);
}

void BufferState::ShiftingDynamicLimitedSharedBufferPolicy::SendingFlit(Flit const * const f)
{
  LimitedSharedBufferPolicy::SendingFlit(f);
  if(f->tail && _active_vcs) {
    int i = _active_vcs - 1;
    _max_held_slots = _buf_size;
    while(i) {
      _max_held_slots >>= 1;
      i >>= 1;
    }
  }
  assert(_max_held_slots > 0);
}

BufferState::FeedbackSharedBufferPolicy::FeedbackSharedBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : SharedBufferPolicy(config, parent, name)
{
  _aging_scale = config.GetInt("feedback_aging_scale");
  _offset = config.GetInt("feedback_offset");
  _vcs = config.GetInt("num_vcs");

  _occupancy_limit.resize(_vcs, _buf_size);
  _round_trip_time.resize(_vcs, -1);
  _flit_sent_time.resize(_vcs);
  _total_mapped_size = _buf_size * _vcs;
  _min_latency = -1;
}

void BufferState::FeedbackSharedBufferPolicy::SetMinLatency(int min_latency)
{
#ifdef DEBUG_FEEDBACK
  cerr << FullName() << ": Setting minimum latency to "
       << min_latency << "." << endl;
#endif
  _min_latency = min_latency;
}

void BufferState::FeedbackSharedBufferPolicy::SendingFlit(Flit const * const f)
{
  SharedBufferPolicy::SendingFlit(f);
  _flit_sent_time[f->vc].push(GetSimTime());
}

int BufferState::FeedbackSharedBufferPolicy::_ComputeRTT(int vc, int last_rtt) const
{
  // compute moving average of round-trip time
  int rtt = _round_trip_time[vc];
  if(rtt < 0) {
    return last_rtt;
  }
  return ((rtt << _aging_scale) + last_rtt - rtt) >> _aging_scale;
}

int BufferState::FeedbackSharedBufferPolicy::_ComputeLimit(int rtt) const
{
  // for every cycle that the measured average round trip time exceeded the 
  // observed minimum round trip time, reduce buffer occupancy limit by one
  assert(_min_latency >= 0);
  return max((_min_latency << 1) - rtt + _offset, 1);
}

int BufferState::FeedbackSharedBufferPolicy::_ComputeMaxSlots(int vc) const
{
  int max_slots = _occupancy_limit[vc];
  if(!_flit_sent_time[vc].empty()) {
    int min_rtt = GetSimTime() - _flit_sent_time[vc].front();
    int rtt = _ComputeRTT(vc, min_rtt);
    int limit = _ComputeLimit(rtt);
    max_slots = min(max_slots, limit);
  }
  return max_slots;
}

void BufferState::FeedbackSharedBufferPolicy::FreeSlotFor(int vc)
{
  SharedBufferPolicy::FreeSlotFor(vc);
  assert(!_flit_sent_time[vc].empty());
  int const last_rtt = GetSimTime() - _flit_sent_time[vc].front();
#ifdef DEBUG_FEEDBACK
  cerr << FullName() << ": Probe for VC "
       << vc << " came back after "
       << last_rtt << " cycles."
       << endl;
#endif
  _flit_sent_time[vc].pop();
  
  int rtt = _ComputeRTT(vc, last_rtt);
#ifdef DEBUG_FEEDBACK
  int old_rtt = _round_trip_time[vc];
  if(rtt != old_rtt) {
    cerr << FullName() << ": Updating RTT estimate for VC "
	 << vc << " from "
	 << old_rtt << " to "
	 << rtt << " cycles."
	 << endl;
  }
#endif
  _round_trip_time[vc] = rtt;

  int limit = _ComputeLimit(rtt);
#ifdef DEBUG_FEEDBACK
  int old_limit = _occupancy_limit[vc];
  int old_mapped_size = _total_mapped_size;
#endif
  _total_mapped_size += (limit - _occupancy_limit[vc]);
  _occupancy_limit[vc] = limit;
#ifdef DEBUG_FEEDBACK
  if(limit != old_limit) {
    cerr << FullName() << ": Occupancy limit for VC "
	 << vc << " changed from "
	 << old_limit << " to "
	 << limit << " slots."
	 << endl;
    cerr << FullName() << ": Total mapped buffer space changed from "
	 << old_mapped_size << " to "
	 << _total_mapped_size << " slots."
	 << endl;
  }
#endif
}

bool BufferState::FeedbackSharedBufferPolicy::IsFullFor(int vc) const
{
  if(SharedBufferPolicy::IsFullFor(vc)) {
    return true;
  }
  return (_buffer_state->OccupancyFor(vc) >= _ComputeMaxSlots(vc));
}

int BufferState::FeedbackSharedBufferPolicy::AvailableFor(int vc) const
{
  return min(SharedBufferPolicy::AvailableFor(vc), 
	     _ComputeMaxSlots(vc) - _buffer_state->OccupancyFor(vc));
}

int BufferState::FeedbackSharedBufferPolicy::LimitFor(int vc) const
{
  return min(SharedBufferPolicy::LimitFor(vc), _ComputeMaxSlots(vc));
}

BufferState::SimpleFeedbackSharedBufferPolicy::SimpleFeedbackSharedBufferPolicy(Configuration const & config, BufferState * parent, const string & name)
  : FeedbackSharedBufferPolicy(config, parent, name)
{
  _pending_credits.resize(_vcs, 0);
}

void BufferState::SimpleFeedbackSharedBufferPolicy::SendingFlit(Flit const * const f)
{
  int const & vc = f->vc;
  if(_flit_sent_time[vc].empty()) {
    assert(_buffer_state->OccupancyFor(vc) > 0);
    _pending_credits[vc] = _buffer_state->OccupancyFor(vc) - 1;
#ifdef DEBUG_SIMPLEFEEDBACK
    cerr << FullName() << ": Sending probe flit for VC "
	 << vc << "; "
	 << _pending_credits[vc] << " non-probe flits in flight."
	 << endl;
#endif
    FeedbackSharedBufferPolicy::SendingFlit(f);
    return;
  }
  SharedBufferPolicy::SendingFlit(f);
}

void BufferState::SimpleFeedbackSharedBufferPolicy::FreeSlotFor(int vc)
{
  if(!_flit_sent_time[vc].empty() && _pending_credits[vc] == 0) {
#ifdef DEBUG_SIMPLEFEEDBACK
    cerr << FullName() << ": Probe credit for VC "
	 << vc << " came back." << endl;
#endif
    FeedbackSharedBufferPolicy::FreeSlotFor(vc);
    return;
  }
  if(_pending_credits[vc] > 0) {
    assert(!_flit_sent_time[vc].empty());
    --_pending_credits[vc];
#ifdef DEBUG_SIMPLEFEEDBACK
    cerr << FullName() << ": Ignoring non-probe credit for VC "
	 << vc << "; "
	 << _pending_credits[vc] << " remaining."
	 << endl;
#endif
  }
  SharedBufferPolicy::FreeSlotFor(vc);
}

BufferState::BufferState( const Configuration& config, Module *parent, const string& name ) : 
  Module( parent, name ), _occupancy(0)
{
  _vcs = config.GetInt( "num_vcs" );
  _size = config.GetInt("buf_size");
  if(_size < 0) {
    _size = _vcs * config.GetInt("vc_buf_size");
  }

  _buffer_policy = BufferPolicy::New(config, this, "policy");

  _wait_for_tail_credit = config.GetInt( "wait_for_tail_credit" );

  _vc_occupancy.resize(_vcs, 0);

  _in_use_by.resize(_vcs, -1);
  _tail_sent.resize(_vcs, false);

  _last_id.resize(_vcs, -1);
  _last_pid.resize(_vcs, -1);

#ifdef TRACK_BUFFERS
  _classes = config.GetInt("classes");
  _outstanding_classes.resize(_vcs);
  _class_occupancy.resize(_classes, 0);
#endif
}

BufferState::~BufferState()
{
  delete _buffer_policy;
}

void BufferState::ProcessCredit( Credit const * const c )
{
  assert( c );

  set<int>::iterator iter = c->vc.begin();
  while(iter != c->vc.end()) {

    int const vc = *iter;

    assert( ( vc >= 0 ) && ( vc < _vcs ) );

    if ( ( _wait_for_tail_credit ) && 
	 ( _in_use_by[vc] < 0 ) ) {
      ostringstream err;
      err << "Received credit for idle VC " << vc;
      Error( err.str() );
    }
    --_occupancy;
    if(_occupancy < 0) {
      Error("Buffer occupancy fell below zero.");
    }
    --_vc_occupancy[vc];
    if(_vc_occupancy[vc] < 0) {
      ostringstream err;
      err << "Buffer occupancy fell below zero for VC " << vc;
      Error(err.str());
    }
    if(_wait_for_tail_credit && !_vc_occupancy[vc] && _tail_sent[vc]) {
      assert(_in_use_by[vc] >= 0);
      _in_use_by[vc] = -1;
    }

#ifdef TRACK_BUFFERS
    assert(!_outstanding_classes[vc].empty());
    int cl = _outstanding_classes[vc].front();
    _outstanding_classes[vc].pop();
    assert((cl >= 0) && (cl < _classes));
    assert(_class_occupancy[cl] > 0);
    --_class_occupancy[cl];
#endif

    _buffer_policy->FreeSlotFor(vc);

    ++iter;
  }
}


void BufferState::SendingFlit( Flit const * const f )
{
  int const vc = f->vc;

  assert( f && ( vc >= 0 ) && ( vc < _vcs ) );

  ++_occupancy;
  if(_occupancy > _size) {
    Error("Buffer overflow.");
  }

  ++_vc_occupancy[vc];
  
  _buffer_policy->SendingFlit(f);
  
#ifdef TRACK_BUFFERS
  _outstanding_classes[vc].push(f->cl);
  ++_class_occupancy[f->cl];
#endif

  if ( f->tail ) {
    _tail_sent[vc] = true;
    
    if ( !_wait_for_tail_credit ) {
      assert(_in_use_by[vc] >= 0);
      _in_use_by[vc] = -1;
    }
  }
  _last_id[vc] = f->id;
  _last_pid[vc] = f->pid;
}

void BufferState::TakeBuffer( int vc, int tag )
{
  assert( ( vc >= 0 ) && ( vc < _vcs ) );

  if ( _in_use_by[vc] >= 0 ) {
    ostringstream err;
    err << "Buffer taken while in use for VC " << vc;
    Error( err.str() );
  }
  _in_use_by[vc] = tag;
  _tail_sent[vc] = false;
  _buffer_policy->TakeBuffer(vc);
}

void BufferState::Display( ostream & os ) const
{
  os << FullName() << " :" << endl;
  os << " occupied = " << _occupancy << endl;
  for ( int v = 0; v < _vcs; ++v ) {
    os << "  VC " << v << ": ";
    os << "in_use_by = " << _in_use_by[v] 
       << ", tail_sent = " << _tail_sent[v]
       << ", occupied = " << _vc_occupancy[v] << endl;
  }
}