calendar-scheduler.cc

Go to the documentation of this file.

/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
/*
 * Copyright (c) 2009 INRIA
 *
 * This 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;
 *
 * 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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 *
 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
 */

#include "calendar-scheduler.h"
#include "event-impl.h"
#include <utility>
#include <string>
#include <list>
#include "assert.h"
#include "log.h"

namespace ns3 {

NS_LOG_COMPONENT_DEFINE ("CalendarScheduler")
  ;

NS_OBJECT_ENSURE_REGISTERED (CalendarScheduler)
  ;

TypeId
CalendarScheduler::GetTypeId (void)
{
  static TypeId tid = TypeId ("ns3::CalendarScheduler")
    .SetParent<Scheduler> ()
    .AddConstructor<CalendarScheduler> ()
  ;
  return tid;
}

CalendarScheduler::CalendarScheduler ()
{
  NS_LOG_FUNCTION (this);
  Init (2, 1, 0);
  m_qSize = 0;
}
CalendarScheduler::~CalendarScheduler ()
{
  NS_LOG_FUNCTION (this);
  delete [] m_buckets;
  m_buckets = 0;
}
void
CalendarScheduler::Init (uint32_t nBuckets,
                         uint64_t width,
                         uint64_t startPrio)
{
  NS_LOG_FUNCTION (this << nBuckets << width << startPrio);
  m_buckets = new Bucket [nBuckets];
  m_nBuckets = nBuckets;
  m_width = width;
  m_lastPrio = startPrio;
  m_lastBucket = Hash (startPrio);
  m_bucketTop = (startPrio / width + 1) * width;
}
void
CalendarScheduler::PrintInfo (void)
{
  NS_LOG_FUNCTION (this);

  std::cout << "nBuckets=" << m_nBuckets << ", width=" << m_width << std::endl;
  std::cout << "Bucket Distribution ";
  for (uint32_t i = 0; i < m_nBuckets; i++)
    {
      std::cout << m_buckets[i].size () << " ";
    }
  std::cout << std::endl;
}
uint32_t
CalendarScheduler::Hash (uint64_t ts) const
{
  NS_LOG_FUNCTION (this);

  uint32_t bucket = (ts / m_width) % m_nBuckets;
  return bucket;
}

void
CalendarScheduler::DoInsert (const Event &ev)
{
  NS_LOG_FUNCTION (this << ev.key.m_ts << ev.key.m_uid);
  // calculate bucket index.
  uint32_t bucket = Hash (ev.key.m_ts);
  NS_LOG_LOGIC ("insert in bucket=" << bucket);

  // insert in bucket list.
  Bucket::iterator end = m_buckets[bucket].end ();
  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
    {
      if (ev.key < i->key)
        {
          m_buckets[bucket].insert (i, ev);
          return;
        }
    }
  m_buckets[bucket].push_back (ev);
}

void
CalendarScheduler::Insert (const Event &ev)
{
  NS_LOG_FUNCTION (this << &ev);
  DoInsert (ev);
  m_qSize++;
  ResizeUp ();
}
bool
CalendarScheduler::IsEmpty (void) const
{
  NS_LOG_FUNCTION (this);
  return m_qSize == 0;
}
Scheduler::Event
CalendarScheduler::PeekNext (void) const
{
  NS_LOG_FUNCTION (this);
  NS_ASSERT (!IsEmpty ());
  uint32_t i = m_lastBucket;
  uint64_t bucketTop = m_bucketTop;
  Scheduler::Event minEvent;
  minEvent.impl = 0;
  minEvent.key.m_ts = ~0;
  minEvent.key.m_uid = ~0;
  minEvent.key.m_context = 0;
  do
    {
      if (!m_buckets[i].empty ())
        {
          Scheduler::Event next = m_buckets[i].front ();
          if (next.key.m_ts < bucketTop)
            {
              return next;
            }
          if (next.key < minEvent.key)
            {
              minEvent = next;
            }
        }
      i++;
      i %= m_nBuckets;
      bucketTop += m_width;
    }
  while (i != m_lastBucket);

  return minEvent;
}

Scheduler::Event
CalendarScheduler::DoRemoveNext (void)
{
  NS_LOG_FUNCTION (this);

  uint32_t i = m_lastBucket;
  uint64_t bucketTop = m_bucketTop;
  int32_t minBucket = -1;
  Scheduler::EventKey minKey;
  NS_ASSERT(!IsEmpty());
  minKey.m_ts = uint64_t(-int64_t(1));
  minKey.m_uid = 0;
  minKey.m_context = 0xffffffff;
  do
    {
      if (!m_buckets[i].empty ())
        {
          Scheduler::Event next = m_buckets[i].front ();
          if (next.key.m_ts < bucketTop)
            {
              m_lastBucket = i;
              m_lastPrio = next.key.m_ts;
              m_bucketTop = bucketTop;
              m_buckets[i].pop_front ();
              return next;
            }
          if (next.key < minKey)
            {
              minKey = next.key;
              minBucket = i;
            }
        }
      i++;
      i %= m_nBuckets;
      bucketTop += m_width;
    }
  while (i != m_lastBucket);

  m_lastPrio = minKey.m_ts;
  m_lastBucket = Hash (minKey.m_ts);
  m_bucketTop = (minKey.m_ts / m_width + 1) * m_width;
  Scheduler::Event next = m_buckets[minBucket].front();
  m_buckets[minBucket].pop_front ();

  return next;
}

Scheduler::Event
CalendarScheduler::RemoveNext (void)
{
  NS_LOG_FUNCTION (this << m_lastBucket << m_bucketTop);
  NS_ASSERT (!IsEmpty ());

  Scheduler::Event ev = DoRemoveNext ();
  NS_LOG_LOGIC ("remove ts=" << ev.key.m_ts <<
                ", key=" << ev.key.m_uid <<
                ", from bucket=" << m_lastBucket);
  m_qSize--;
  ResizeDown ();
  return ev;
}

void
CalendarScheduler::Remove (const Event &ev)
{
  NS_LOG_FUNCTION (this << &ev);
  NS_ASSERT (!IsEmpty ());
  // bucket index of event
  uint32_t bucket = Hash (ev.key.m_ts);

  Bucket::iterator end = m_buckets[bucket].end ();
  for (Bucket::iterator i = m_buckets[bucket].begin (); i != end; ++i)
    {
      if (i->key.m_uid == ev.key.m_uid)
        {
          NS_ASSERT (ev.impl == i->impl);
          m_buckets[bucket].erase (i);

          m_qSize--;
          ResizeDown ();
          return;
        }
    }
  NS_ASSERT (false);
}

void
CalendarScheduler::ResizeUp (void)
{
  NS_LOG_FUNCTION (this);

  if (m_qSize > m_nBuckets * 2
      && m_nBuckets < 32768)
    {
      Resize (m_nBuckets * 2);
    }
}
void
CalendarScheduler::ResizeDown (void)
{
  NS_LOG_FUNCTION (this);

  if (m_qSize < m_nBuckets / 2)
    {
      Resize (m_nBuckets / 2);
    }
}

uint32_t
CalendarScheduler::CalculateNewWidth (void)
{
  NS_LOG_FUNCTION (this);

  if (m_qSize < 2)
    {
      return 1;
    }
  uint32_t nSamples;
  if (m_qSize <= 5)
    {
      nSamples = m_qSize;
    }
  else
    {
      nSamples = 5 + m_qSize / 10;
    }
  if (nSamples > 25)
    {
      nSamples = 25;
    }

  // we gather the first nSamples from the queue
  std::list<Scheduler::Event> samples;
  // save state
  uint32_t lastBucket = m_lastBucket;
  uint64_t bucketTop = m_bucketTop;
  uint64_t lastPrio = m_lastPrio;

  // gather requested events
  for (uint32_t i = 0; i < nSamples; i++)
    {
      samples.push_back (DoRemoveNext ());
    }
  // put them back
  for (std::list<Scheduler::Event>::const_iterator i = samples.begin ();
       i != samples.end (); ++i)
    {
      DoInsert (*i);
    }

  // restore state.
  m_lastBucket = lastBucket;
  m_bucketTop = bucketTop;
  m_lastPrio = lastPrio;

  // finally calculate inter-time average over samples.
  uint64_t totalSeparation = 0;
  std::list<Scheduler::Event>::const_iterator end = samples.end ();
  std::list<Scheduler::Event>::const_iterator cur = samples.begin ();
  std::list<Scheduler::Event>::const_iterator next = cur;
  next++;
  while (next != end)
    {
      totalSeparation += next->key.m_ts - cur->key.m_ts;
      cur++;
      next++;
    }
  uint64_t twiceAvg = totalSeparation / (nSamples - 1) * 2;
  totalSeparation = 0;
  cur = samples.begin ();
  next = cur;
  next++;
  while (next != end)
    {
      uint64_t diff = next->key.m_ts - cur->key.m_ts;
      if (diff <= twiceAvg)
        {
          totalSeparation += diff;
        }
      cur++;
      next++;
    }

  totalSeparation *= 3;
  totalSeparation = std::max (totalSeparation, (uint64_t)1);
  return totalSeparation;
}
void
CalendarScheduler::DoResize (uint32_t newSize, uint32_t newWidth)
{
  NS_LOG_FUNCTION (this << newSize << newWidth);

  Bucket *oldBuckets = m_buckets;
  uint32_t oldNBuckets = m_nBuckets;
  Init (newSize, newWidth, m_lastPrio);

  for (uint32_t i = 0; i < oldNBuckets; i++)
    {
      Bucket::iterator end = oldBuckets[i].end ();
      for (Bucket::iterator j = oldBuckets[i].begin (); j != end; ++j)
        {
          DoInsert (*j);
        }
    }
  delete [] oldBuckets;
}
void
CalendarScheduler::Resize (uint32_t newSize)
{
  NS_LOG_FUNCTION (this << newSize);

  // PrintInfo ();
  uint32_t newWidth = CalculateNewWidth ();
  DoResize (newSize, newWidth);
}

} // namespace ns3