1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */

     2 /*

     3  * Copyright (c) 2006 INRIA

     4  *

     5  * This program is free software; you can redistribute it and/or modify

     6  * it under the terms of the GNU General Public License version 2 as

     7  * published by the Free Software Foundation;

     8  *

     9  * This program is distributed in the hope that it will be useful,

    10  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    12  * GNU General Public License for more details.

    13  *

    14  * You should have received a copy of the GNU General Public License

    15  * along with this program; if not, write to the Free Software

    16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    17  *

    18  * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>

    19  */

    20 

    21 #include "ns3/simulator-module.h"

    22 #include "ns3/core-module.h"

    23 #include <vector>

    24 #include <deque>

    25 #include <fstream>

    26 #include <iostream>

    27 

    28 using namespace ns3;

    29 

    30 class LogReader {

    31 public:

    32   void ReadFromFilename (char const *filename);

    33   void Run (void);

    34   void PrintStats (void);

    35 private:

    36   struct Command {

    37       enum {

    38           REMOVE = 100,

    39           INSERT,

    40           INSERT_LATER,

    41           INSERT_REMOVE

    42       } m_type;

    43       // uid at which this command is supposed to be executed.

    44       uint32_t m_uid;

    45       union {

    46           struct {

    47             // time at which the event is supposed to expire

    48             uint64_t m_evNs;

    49             uint32_t m_evUid;

    50           } insert;

    51           struct {

    52             // location in the array of events to remove where

    53             // to insert this event once it is inserted in 

    54             // the scheduler.

    55             uint32_t m_evLoc; 

    56             // time at which the event is supposed to expire

    57             uint64_t m_evNs;

    58           } insertRemove;

    59       };

    60   };

    61   void ExecuteLogCommands (uint32_t uid);

    62 

    63   typedef std::vector<struct Command> Commands;

    64   typedef std::vector<struct Command>::iterator CommandsI;

    65   typedef std::vector<EventId> RemoveEvents;

    66   typedef std::vector<EventId>::iterator RemoveEventsI;

    67   

    68 

    69   Commands m_commands;

    70   CommandsI m_command;

    71   RemoveEvents m_removeEvents;

    72   uint32_t m_uid;

    73 };

    74 

    75 typedef std::vector<std::pair<uint32_t, uint32_t> > Removes;

    76 typedef std::vector<std::pair<uint32_t, uint32_t> >::iterator RemovesI;

    77 

    78 void

    79 LogReader::ReadFromFilename (char const *filename)

    80 {

    81   std::ifstream log;

    82   std::cout << "read log..." << std::endl;

    83   Removes removes;

    84   log.open (filename);

    85   while (!log.eof ()) 

    86     {

    87       std::string type;

    88       log >> type;

    89       if (type == "i") 

    90         {

    91           uint32_t nowUid, evUid;

    92           uint64_t nowNs, evNs;

    93           log >> nowUid >> nowNs >> evUid >> evNs;

    94           struct Command cmd;

    95           cmd.m_type = Command::INSERT;

    96           cmd.m_uid = nowUid;

    97           cmd.insert.m_evNs = evNs;

    98           cmd.insert.m_evUid = evUid;

    99           m_commands.push_back (cmd);

   100         } 

   101       else if (type == "r") 

   102         {

   103           uint32_t nowUid, evUid;

   104           uint64_t nowNs, evNs;

   105           log >> nowUid >> nowNs >> evUid >> evNs;

   106           struct Command cmd;

   107           cmd.m_type = Command::REMOVE;

   108           cmd.m_uid = nowUid;

   109           m_commands.push_back (cmd);

   110           removes.push_back (std::make_pair (nowUid, evUid));

   111         } 

   112       else if (type == "il") 

   113         {

   114           uint32_t nowUid, evUid;

   115           uint64_t nowNs, evNs;

   116           log >> nowUid >> nowNs >> evUid >> evNs;

   117           struct Command cmd;

   118           cmd.m_type = Command::INSERT_LATER;

   119           cmd.m_uid = nowUid;

   120           m_commands.push_back (cmd);

   121         }

   122     }

   123   log.close ();

   124 

   125   std::cout << "gather insert/removes, commands="<<m_commands.size () 

   126             << ", removes=" << removes.size () << "..." << std::endl;

   127   for (CommandsI i = m_commands.begin (); i != m_commands.end (); i++) 

   128     {

   129       if (i->m_type == Command::INSERT) 

   130         {

   131           for (RemovesI j = removes.begin (); j != removes.end (); j++) 

   132             {

   133               if (j->second == i->insert.m_evUid) 

   134                 {

   135                   // this insert will be removed later.

   136                   uint64_t ns = i->insert.m_evNs;

   137                   uint32_t uid = i->m_uid;

   138                   i->m_type = Command::INSERT_REMOVE;

   139                   i->m_uid = uid;

   140                   i->insertRemove.m_evNs = ns;

   141                   i->insertRemove.m_evLoc = j->first;

   142                   break;

   143                 }

   144             }

   145         }

   146     }

   147   std::cout << "calculate remove locations..." << std::endl;

   148   // calculate the final insert/remove location.

   149   for (CommandsI i = m_commands.begin (); i != m_commands.end (); i++) 

   150     {

   151       if (i->m_type == Command::INSERT_REMOVE) 

   152         {

   153           uint32_t loc = 0;

   154           for (CommandsI tmp = i; tmp != m_commands.end (); tmp++) 

   155             {

   156               if (tmp->m_type == Command::REMOVE) 

   157                 {

   158                   if (tmp->m_uid == i->insertRemove.m_evLoc) 

   159                     {

   160                       i->insertRemove.m_evLoc = loc;

   161                       break;

   162                     }

   163                   loc++;

   164                 }

   165             }

   166         }

   167     }

   168 }

   169 void

   170 LogReader::ExecuteLogCommands (uint32_t uid)

   171 {

   172   if (m_command == m_commands.end ()) 

   173     {

   174       return;

   175     }

   176   //std::cout << "one event, uid=" <<m_uid<< std::endl;

   177   struct Command cmd = *m_command;

   178   //std::cout << "cmd uid=" <<cmd.m_uid<< std::endl;

   179   while (cmd.m_uid == uid) 

   180     {

   181       m_command++;

   182       switch (cmd.m_type) {

   183       case Command::INSERT:

   184         //std::Cout << "exec insert now=" << Simulator::Now ().GetNanoSeconds ()

   185         //<< ", time=" << cmd.insert.m_evNs << std::endl;

   186         Simulator::Schedule (NanoSeconds (cmd.insert.m_evNs) - Now (), 

   187                              &LogReader::ExecuteLogCommands, this, m_uid);

   188         m_uid++;

   189         break;

   190       case Command::INSERT_LATER:

   191           //std::cout << "exec insert later" << std::endl;

   192           Simulator::ScheduleNow (&LogReader::ExecuteLogCommands, this, m_uid);

   193           m_uid++;

   194           break;

   195       case Command::REMOVE: 

   196         {

   197           //std::cout << "exec remove" << std::endl;

   198           EventId id = m_removeEvents.back ();

   199           m_removeEvents.pop_back ();

   200           Simulator::Remove (id);

   201         } break;

   202       case Command::INSERT_REMOVE: 

   203         {

   204           //std::cout << "exec insert remove" << std::endl;

   205           EventId id = Simulator::Schedule (NanoSeconds (cmd.insertRemove.m_evNs) - Now (),

   206                                             &LogReader::ExecuteLogCommands, this, m_uid);

   207           NS_ASSERT (id.GetUid () == m_uid);

   208           if (cmd.insertRemove.m_evLoc + 1 > m_removeEvents.size ())

   209             {

   210               uint32_t missing = cmd.insertRemove.m_evLoc + 1 - m_removeEvents.size ();

   211               m_removeEvents.insert (m_removeEvents.begin (),

   212                                      missing, id);

   213             }

   214           uint32_t index = m_removeEvents.size () - cmd.insertRemove.m_evLoc - 1;

   215           m_removeEvents[index] = id;

   216           m_uid++;

   217         } break;

   218       default:

   219         NS_ASSERT (false);

   220         break;

   221       }

   222       cmd = *m_command;

   223   }

   224 }

   225 

   226 void

   227 LogReader::PrintStats (void)

   228 {

   229   uint32_t nInserts = 0;

   230   uint32_t nRemoves = 0;

   231   for (CommandsI i = m_commands.begin (); i != m_commands.end (); i++) 

   232     {

   233       switch (i->m_type) {

   234       case Command::INSERT:

   235           nInserts++;

   236           break;

   237       case Command::INSERT_LATER:

   238           nInserts++;

   239           break;

   240       case Command::INSERT_REMOVE:

   241           nInserts++;

   242           break;

   243       case Command::REMOVE:

   244           nRemoves++;

   245           break;

   246       }

   247     }

   248   std::cout << "inserts="<<nInserts<<", removes="<<nRemoves<<std::endl;

   249   std::cout << "run simulation..."<<std::endl;

   250 }

   251 

   252 void

   253 LogReader::Run (void)

   254 {

   255   m_uid = 1;

   256   SystemWallClockMs time;

   257   time.Start ();

   258   m_command = m_commands.begin ();

   259   ExecuteLogCommands (0);

   260   Simulator::Run ();

   261   unsigned long long delta = time.End ();

   262   double delay = ((double)delta)/1000;

   263   std::cout << "runtime="<<delay<<"s"<<std::endl;

   264 }

   265 

   266 

   267 int main (int argc, char *argv[])

   268 {

   269   char const *input = 0;

   270   uint32_t n = 1;

   271   bool is_map = false;

   272   bool is_list = false;

   273   bool is_heap = false;

   274   while (argc > 0) 

   275     {

   276       if (strcmp ("--list", argv[0]) == 0) 

   277         {

   278           is_list = true;

   279         } 

   280       else if (strcmp ("--heap", argv[0]) == 0) 

   281         {

   282           is_heap = true;

   283         } 

   284       else if (strcmp ("--map", argv[0]) == 0) 

   285         {

   286           is_map = true;

   287         } 

   288       else if (strncmp ("--n=", argv[0], strlen("--n=")) == 0) 

   289         {

   290           n = atoi (argv[0]+strlen ("--n="));

   291         } 

   292       else if (strncmp ("--input=", argv[0],strlen ("--input=")) == 0) 

   293         {

   294           input = argv[0] + strlen ("--input=");

   295         } 

   296       else if (strncmp ("--log=", argv[0],strlen ("--log=")) == 0) 

   297         {

   298           char const *filename = argv[0] + strlen ("--log=");

   299           Simulator::EnableLogTo (filename);

   300         }

   301       argc--;

   302       argv++;

   303     }

   304   if (input == 0) 

   305     {

   306       std::cerr << "need --input=[filename] option" << std::endl;

   307       return 1;

   308     }

   309   LogReader log;

   310   log.ReadFromFilename (input);

   311   std::cout << "start runs..." << std::endl;

   312   for (uint32_t i = 0; i < n; i++) 

   313     {

   314       if (is_map)

   315         {

   316           Simulator::SetScheduler (CreateObject<MapScheduler> ());

   317         }

   318       else if (is_list)

   319         {

   320           Simulator::SetScheduler (CreateObject<ListScheduler> ());

   321         }

   322       else if (is_heap)

   323         {

   324           Simulator::SetScheduler (CreateObject<HeapScheduler> ());

   325         }

   326       log.Run ();

   327       Simulator::Destroy ();

   328     }

   329 }