src/dev/net/etherswitch.cc

   1 /*
   2  * Copyright (c) 2014 The Regents of The University of Michigan
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Anthony Gutierrez
  29  *          Mohammad Alian
  30  */
  31
  32 /* @file
  33  * Device model for an ethernet switch
  34  */
  35
  36 #include "dev/net/etherswitch.hh"
  37
  38 #include "base/random.hh"
  39 #include "base/trace.hh"
  40 #include "debug/EthernetAll.hh"
  41 #include "sim/core.hh"
  42
  43 using namespace std;
  44
  45 EtherSwitch::EtherSwitch(const Params *p)
  46     : SimObject(p), ttl(p->time_to_live)
  47 {
  48     for (int i = 0; i < p->port_interface_connection_count; ++i) {
  49         std::string interfaceName = csprintf("%s.interface%d", name(), i);
  50         Interface *interface = new Interface(interfaceName, this,
  51                                         p->output_buffer_size, p->delay,
  52                                         p->delay_var, p->fabric_speed, i);
  53         interfaces.push_back(interface);
  54     }
  55 }
  56
  57 EtherSwitch::~EtherSwitch()
  58 {
  59     for (auto it : interfaces)
  60         delete it;
  61
  62     interfaces.clear();
  63 }
  64
  65 Port &
  66 EtherSwitch::getPort(const std::string &if_name, PortID idx)
  67 {
  68     if (if_name == "interface") {
  69         panic_if(idx < 0 || idx >= interfaces.size(), "index out of bounds");
  70         return *interfaces.at(idx);
  71     }
  72
  73     return SimObject::getPort(if_name, idx);
  74 }
  75
  76 bool
  77 EtherSwitch::Interface::PortFifo::push(EthPacketPtr ptr, unsigned senderId)
  78 {
  79     assert(ptr->length);
  80
  81     _size += ptr->length;
  82     fifo.emplace_hint(fifo.end(), ptr, curTick(), senderId);
  83
  84     // Drop the extra pushed packets from end of the fifo
  85     while (avail() < 0) {
  86         DPRINTF(Ethernet, "Fifo is full. Drop packet: len=%d\n",
  87                 std::prev(fifo.end())->packet->length);
  88
  89         _size -= std::prev(fifo.end())->packet->length;
  90         fifo.erase(std::prev(fifo.end()));
  91     }
  92
  93     if (empty()) {
  94         warn("EtherSwitch: Packet length (%d) exceeds the maximum storage "
  95              "capacity of port fifo (%d)", ptr->length, _maxsize);
  96     }
  97
  98     // Return true if the newly pushed packet gets inserted
  99     // at the head of the queue, otherwise return false
 100     // We need this information to deschedule the event that has been
 101     // scheduled for the old head of queue packet and schedule a new one
 102     if (!empty() && fifo.begin()->packet == ptr) {
 103         return true;
 104     }
 105     return false;
 106 }
 107
 108 void
 109 EtherSwitch::Interface::PortFifo::pop()
 110 {
 111     if (empty())
 112         return;
 113
 114     assert(_size >= fifo.begin()->packet->length);
 115     // Erase the packet at the head of the queue
 116     _size -= fifo.begin()->packet->length;
 117     fifo.erase(fifo.begin());
 118 }
 119
 120 void
 121 EtherSwitch::Interface::PortFifo::clear()
 122 {
 123     fifo.clear();
 124     _size = 0;
 125 }
 126
 127 EtherSwitch::Interface::Interface(const std::string &name,
 128                                   EtherSwitch *etherSwitch,
 129                                   uint64_t outputBufferSize, Tick delay,
 130                                   Tick delay_var, double rate, unsigned id)
 131     : EtherInt(name), ticksPerByte(rate), switchDelay(delay),
 132       delayVar(delay_var), interfaceId(id), parent(etherSwitch),
 133       outputFifo(name + ".outputFifo", outputBufferSize),
 134       txEvent([this]{ transmit(); }, name)
 135 {
 136 }
 137
 138 bool
 139 EtherSwitch::Interface::recvPacket(EthPacketPtr packet)
 140 {
 141     Net::EthAddr destMacAddr(packet->data);
 142     Net::EthAddr srcMacAddr(&packet->data[6]);
 143
 144     learnSenderAddr(srcMacAddr, this);
 145     Interface *receiver = lookupDestPort(destMacAddr);
 146
 147     if (!receiver || destMacAddr.multicast() || destMacAddr.broadcast()) {
 148         for (auto it : parent->interfaces)
 149             if (it != this)
 150                 it->enqueue(packet, interfaceId);
 151     } else {
 152         DPRINTF(Ethernet, "sending packet from MAC %x on port "
 153                 "%s to MAC %x on port %s\n", uint64_t(srcMacAddr),
 154                 this->name(), uint64_t(destMacAddr), receiver->name());
 155
 156         receiver->enqueue(packet, interfaceId);
 157     }
 158     // At the output port, we either have buffer space (no drop) or
 159     // don't (drop packet); in both cases packet is received on
 160     // the interface successfully and there is no notion of busy
 161     // interface here (as we don't have inputFifo)
 162     return true;
 163 }
 164
 165 void
 166 EtherSwitch::Interface::enqueue(EthPacketPtr packet, unsigned senderId)
 167 {
 168     // assuming per-interface transmission events,
 169     // if the newly push packet gets inserted at the head of the queue
 170     // (either there was nothing in the queue or the priority of the new
 171     // packet was higher than the packets already in the fifo)
 172     // then we need to schedule an event at
 173     // "curTick" + "switchingDelay of the packet at the head of the fifo"
 174     // to send this packet out the external link
 175     // otherwise, there is already a txEvent scheduled
 176     if (outputFifo.push(packet, senderId)) {
 177         parent->reschedule(txEvent, curTick() + switchingDelay(), true);
 178     }
 179 }
 180
 181 void
 182 EtherSwitch::Interface::transmit()
 183 {
 184     // there should be something in the output queue
 185     assert(!outputFifo.empty());
 186
 187     if (!sendPacket(outputFifo.front())) {
 188         DPRINTF(Ethernet, "output port busy...retry later\n");
 189         if (!txEvent.scheduled())
 190             parent->schedule(txEvent, curTick() + retryTime);
 191     } else {
 192         DPRINTF(Ethernet, "packet sent: len=%d\n", outputFifo.front()->length);
 193         outputFifo.pop();
 194         // schedule an event to send the pkt at
 195         // the head of queue, if there is any
 196         if (!outputFifo.empty()) {
 197             parent->schedule(txEvent, curTick() + switchingDelay());
 198         }
 199     }
 200 }
 201
 202 Tick
 203 EtherSwitch::Interface::switchingDelay()
 204 {
 205     Tick delay = (Tick)ceil(((double)outputFifo.front()->simLength
 206                                      * ticksPerByte) + 1.0);
 207     if (delayVar != 0)
 208                 delay += random_mt.random<Tick>(0, delayVar);
 209     delay += switchDelay;
 210     return delay;
 211 }
 212
 213 EtherSwitch::Interface*
 214 EtherSwitch::Interface::lookupDestPort(Net::EthAddr destMacAddr)
 215 {
 216     auto it = parent->forwardingTable.find(uint64_t(destMacAddr));
 217
 218     if (it == parent->forwardingTable.end()) {
 219         DPRINTF(Ethernet, "no entry in forwaring table for MAC: "
 220                 "%x\n", uint64_t(destMacAddr));
 221         return nullptr;
 222     }
 223
 224     // check if this entry is valid based on TTL and lastUseTime
 225     if ((curTick() - it->second.lastUseTime) > parent->ttl) {
 226         // TTL for this mapping has been expired, so this item is not
 227         // valide anymore, let's remove it from the map
 228         parent->forwardingTable.erase(it);
 229         return nullptr;
 230     }
 231
 232     DPRINTF(Ethernet, "found entry for MAC address %x on port %s\n",
 233             uint64_t(destMacAddr), it->second.interface->name());
 234     return it->second.interface;
 235 }
 236
 237 void
 238 EtherSwitch::Interface::learnSenderAddr(Net::EthAddr srcMacAddr,
 239                                           Interface *sender)
 240 {
 241     // learn the port for the sending MAC address
 242     auto it = parent->forwardingTable.find(uint64_t(srcMacAddr));
 243
 244     // if the port for sender's MAC address is not cached,
 245     // cache it now, otherwise just update lastUseTime time
 246     if (it == parent->forwardingTable.end()) {
 247         DPRINTF(Ethernet, "adding forwarding table entry for MAC "
 248                 " address %x on port %s\n", uint64_t(srcMacAddr),
 249                 sender->name());
 250         EtherSwitch::SwitchTableEntry forwardingTableEntry;
 251         forwardingTableEntry.interface = sender;
 252         forwardingTableEntry.lastUseTime = curTick();
 253         parent->forwardingTable.insert(std::make_pair(uint64_t(srcMacAddr),
 254             forwardingTableEntry));
 255     } else {
 256         it->second.lastUseTime = curTick();
 257     }
 258 }
 259
 260 void
 261 EtherSwitch::serialize(CheckpointOut &cp) const
 262 {
 263     for (auto it : interfaces)
 264         it->serializeSection(cp, it->name());
 265
 266 }
 267
 268 void
 269 EtherSwitch::unserialize(CheckpointIn &cp)
 270 {
 271     for (auto it : interfaces)
 272         it->unserializeSection(cp, it->name());
 273
 274 }
 275
 276 void
 277 EtherSwitch::Interface::serialize(CheckpointOut &cp) const
 278 {
 279     bool event_scheduled = txEvent.scheduled();
 280     SERIALIZE_SCALAR(event_scheduled);
 281
 282     if (event_scheduled) {
 283         Tick event_time = txEvent.when();
 284         SERIALIZE_SCALAR(event_time);
 285     }
 286     outputFifo.serializeSection(cp, "outputFifo");
 287 }
 288
 289 void
 290 EtherSwitch::Interface::unserialize(CheckpointIn &cp)
 291 {
 292     bool event_scheduled;
 293     UNSERIALIZE_SCALAR(event_scheduled);
 294
 295     if (event_scheduled) {
 296         Tick event_time;
 297         UNSERIALIZE_SCALAR(event_time);
 298         parent->schedule(txEvent, event_time);
 299     }
 300     outputFifo.unserializeSection(cp, "outputFifo");
 301 }
 302
 303 void
 304 EtherSwitch::Interface::PortFifoEntry::serialize(CheckpointOut &cp) const
 305 {
 306     packet->serialize("packet", cp);
 307     SERIALIZE_SCALAR(recvTick);
 308     SERIALIZE_SCALAR(srcId);
 309 }
 310
 311 void
 312 EtherSwitch::Interface::PortFifoEntry::unserialize(CheckpointIn &cp)
 313 {
 314     packet = make_shared<EthPacketData>(16384);
 315     packet->unserialize("packet", cp);
 316     UNSERIALIZE_SCALAR(recvTick);
 317     UNSERIALIZE_SCALAR(srcId);
 318 }
 319
 320 void
 321 EtherSwitch::Interface::PortFifo::serialize(CheckpointOut &cp) const
 322 {
 323     SERIALIZE_SCALAR(_size);
 324     int fifosize = fifo.size();
 325
 326     SERIALIZE_SCALAR(fifosize);
 327
 328     int i = 0;
 329     for (const auto &entry : fifo)
 330         entry.serializeSection(cp, csprintf("entry%d", i++));
 331 }
 332
 333 void
 334 EtherSwitch::Interface::PortFifo::unserialize(CheckpointIn &cp)
 335 {
 336     UNSERIALIZE_SCALAR(_size);
 337     int fifosize;
 338
 339     UNSERIALIZE_SCALAR(fifosize);
 340     fifo.clear();
 341
 342     for (int i = 0; i < fifosize; ++i) {
 343         PortFifoEntry entry(nullptr, 0, 0);
 344
 345         entry.unserializeSection(cp, csprintf("entry%d", i));
 346
 347         fifo.insert(entry);
 348
 349     }
 350 }
 351
 352 EtherSwitch *
 353 EtherSwitchParams::create()
 354 {
 355     return new EtherSwitch(this);
 356 }