coherent_xbar.cc revision 7523
1/*
2 * Copyright (c) 2006 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: Ali Saidi
29 */
30
31/**
32 * @file
33 * Definition of a bus object.
34 */
35
36#include <algorithm>
37#include <limits>
38
39#include "base/misc.hh"
40#include "base/trace.hh"
41#include "mem/bus.hh"
42
43Bus::Bus(const BusParams *p)
44    : MemObject(p), busId(p->bus_id), clock(p->clock),
45      headerCycles(p->header_cycles), width(p->width), tickNextIdle(0),
46      drainEvent(NULL), busIdle(this), inRetry(false), maxId(0),
47      defaultPort(NULL), funcPort(NULL), funcPortId(-4),
48      useDefaultRange(p->use_default_range), defaultBlockSize(p->block_size),
49      cachedBlockSize(0), cachedBlockSizeValid(false)
50{
51    //width, clock period, and header cycles must be positive
52    if (width <= 0)
53        fatal("Bus width must be positive\n");
54    if (clock <= 0)
55        fatal("Bus clock period must be positive\n");
56    if (headerCycles <= 0)
57        fatal("Number of header cycles must be positive\n");
58    clearBusCache();
59    clearPortCache();
60}
61
62Port *
63Bus::getPort(const std::string &if_name, int idx)
64{
65    if (if_name == "default") {
66        if (defaultPort == NULL) {
67            defaultPort = new BusPort(csprintf("%s-default",name()), this,
68                                      defaultId);
69            cachedBlockSizeValid = false;
70            return defaultPort;
71        } else
72            fatal("Default port already set\n");
73    }
74    int id;
75    if (if_name == "functional") {
76        if (!funcPort) {
77            id = maxId++;
78            funcPort = new BusPort(csprintf("%s-p%d-func", name(), id), this, id);
79            funcPortId = id;
80            interfaces[id] = funcPort;
81        }
82        return funcPort;
83    }
84
85    // if_name ignored?  forced to be empty?
86    id = maxId++;
87    assert(maxId < std::numeric_limits<typeof(maxId)>::max());
88    BusPort *bp = new BusPort(csprintf("%s-p%d", name(), id), this, id);
89    interfaces[id] = bp;
90    cachedBlockSizeValid = false;
91    return bp;
92}
93
94void
95Bus::deletePortRefs(Port *p)
96{
97
98    BusPort *bp =  dynamic_cast<BusPort*>(p);
99    if (bp == NULL)
100        panic("Couldn't convert Port* to BusPort*\n");
101    // If this is our one functional port
102    if (funcPort == bp)
103        return;
104    interfaces.erase(bp->getId());
105    clearBusCache();
106    delete bp;
107}
108
109/** Get the ranges of anyone other buses that we are connected to. */
110void
111Bus::init()
112{
113    m5::hash_map<short,BusPort*>::iterator intIter;
114
115    for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
116        intIter->second->sendStatusChange(Port::RangeChange);
117}
118
119Bus::BusFreeEvent::BusFreeEvent(Bus *_bus)
120    : bus(_bus)
121{}
122
123void
124Bus::BusFreeEvent::process()
125{
126    bus->recvRetry(-1);
127}
128
129const char *
130Bus::BusFreeEvent::description() const
131{
132    return "bus became available";
133}
134
135Tick
136Bus::calcPacketTiming(PacketPtr pkt)
137{
138    // Bring tickNextIdle up to the present tick.
139    // There is some potential ambiguity where a cycle starts, which
140    // might make a difference when devices are acting right around a
141    // cycle boundary. Using a < allows things which happen exactly on
142    // a cycle boundary to take up only the following cycle. Anything
143    // that happens later will have to "wait" for the end of that
144    // cycle, and then start using the bus after that.
145    if (tickNextIdle < curTick) {
146        tickNextIdle = curTick;
147        if (tickNextIdle % clock != 0)
148            tickNextIdle = curTick - (curTick % clock) + clock;
149    }
150
151    Tick headerTime = tickNextIdle + headerCycles * clock;
152
153    // The packet will be sent. Figure out how long it occupies the bus, and
154    // how much of that time is for the first "word", aka bus width.
155    int numCycles = 0;
156    if (pkt->hasData()) {
157        // If a packet has data, it needs ceil(size/width) cycles to send it
158        int dataSize = pkt->getSize();
159        numCycles += dataSize/width;
160        if (dataSize % width)
161            numCycles++;
162    }
163
164    // The first word will be delivered after the current tick, the delivery
165    // of the address if any, and one bus cycle to deliver the data
166    pkt->firstWordTime = headerTime + clock;
167
168    pkt->finishTime = headerTime + numCycles * clock;
169
170    return headerTime;
171}
172
173void Bus::occupyBus(Tick until)
174{
175    if (until == 0) {
176        // shortcut for express snoop packets
177        return;
178    }
179
180    tickNextIdle = until;
181    reschedule(busIdle, tickNextIdle, true);
182
183    DPRINTF(Bus, "The bus is now occupied from tick %d to %d\n",
184            curTick, tickNextIdle);
185}
186
187/** Function called by the port when the bus is receiving a Timing
188 * transaction.*/
189bool
190Bus::recvTiming(PacketPtr pkt)
191{
192    short src = pkt->getSrc();
193
194    BusPort *src_port;
195    if (src == defaultId)
196        src_port = defaultPort;
197    else {
198        src_port = checkBusCache(src);
199        if (src_port == NULL) {
200            src_port = interfaces[src];
201            updateBusCache(src, src_port);
202        }
203    }
204
205    // If the bus is busy, or other devices are in line ahead of the current
206    // one, put this device on the retry list.
207    if (!pkt->isExpressSnoop() &&
208        (tickNextIdle > curTick ||
209         (retryList.size() && (!inRetry || src_port != retryList.front()))))
210    {
211        addToRetryList(src_port);
212        DPRINTF(Bus, "recvTiming: src %d dst %d %s 0x%x BUSY\n",
213                src, pkt->getDest(), pkt->cmdString(), pkt->getAddr());
214        return false;
215    }
216
217    DPRINTF(Bus, "recvTiming: src %d dst %d %s 0x%x\n",
218            src, pkt->getDest(), pkt->cmdString(), pkt->getAddr());
219
220    Tick headerFinishTime = pkt->isExpressSnoop() ? 0 : calcPacketTiming(pkt);
221    Tick packetFinishTime = pkt->isExpressSnoop() ? 0 : pkt->finishTime;
222
223    short dest = pkt->getDest();
224    int dest_port_id;
225    Port *dest_port;
226
227    if (dest == Packet::Broadcast) {
228        dest_port_id = findPort(pkt->getAddr());
229        dest_port = (dest_port_id == defaultId) ?
230            defaultPort : interfaces[dest_port_id];
231        SnoopIter s_end = snoopPorts.end();
232        for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) {
233            BusPort *p = *s_iter;
234            if (p != dest_port && p != src_port) {
235                // cache is not allowed to refuse snoop
236                bool success M5_VAR_USED = p->sendTiming(pkt);
237                assert(success);
238            }
239        }
240    } else {
241        assert(dest < maxId);
242        assert(dest != src); // catch infinite loops
243        dest_port_id = dest;
244        if (dest_port_id == defaultId)
245            dest_port = defaultPort;
246        else {
247            dest_port = checkBusCache(dest);
248            if (dest_port == NULL) {
249                dest_port = interfaces[dest_port_id];
250            // updateBusCache(dest_port_id, dest_port);
251            }
252        }
253        dest_port = (dest_port_id == defaultId) ?
254            defaultPort : interfaces[dest_port_id];
255    }
256
257    if (dest_port_id == src) {
258        // Must be forwarded snoop up from below...
259        assert(dest == Packet::Broadcast);
260    } else {
261        // send to actual target
262        if (!dest_port->sendTiming(pkt))  {
263            // Packet not successfully sent. Leave or put it on the retry list.
264            // illegal to block responses... can lead to deadlock
265            assert(!pkt->isResponse());
266            // It's also illegal to force a transaction to retry after
267            // someone else has committed to respond.
268            assert(!pkt->memInhibitAsserted());
269            DPRINTF(Bus, "recvTiming: src %d dst %d %s 0x%x TGT RETRY\n",
270                    src, pkt->getDest(), pkt->cmdString(), pkt->getAddr());
271            addToRetryList(src_port);
272            occupyBus(headerFinishTime);
273            return false;
274        }
275        // send OK, fall through... pkt may have been deleted by
276        // target at this point, so it should *not* be referenced
277        // again.  We'll set it to NULL here just to be safe.
278        pkt = NULL;
279    }
280
281    occupyBus(packetFinishTime);
282
283    // Packet was successfully sent.
284    // Also take care of retries
285    if (inRetry) {
286        DPRINTF(Bus, "Remove retry from list %d\n", src);
287        retryList.front()->onRetryList(false);
288        retryList.pop_front();
289        inRetry = false;
290    }
291    return true;
292}
293
294void
295Bus::recvRetry(int id)
296{
297    // If there's anything waiting, and the bus isn't busy...
298    if (retryList.size() && curTick >= tickNextIdle) {
299        //retryingPort = retryList.front();
300        inRetry = true;
301        DPRINTF(Bus, "Sending a retry to %s\n", retryList.front()->getPeer()->name());
302        retryList.front()->sendRetry();
303        // If inRetry is still true, sendTiming wasn't called
304        if (inRetry)
305        {
306            retryList.front()->onRetryList(false);
307            retryList.pop_front();
308            inRetry = false;
309
310            //Bring tickNextIdle up to the present
311            while (tickNextIdle < curTick)
312                tickNextIdle += clock;
313
314            //Burn a cycle for the missed grant.
315            tickNextIdle += clock;
316
317            reschedule(busIdle, tickNextIdle, true);
318        }
319    }
320    //If we weren't able to drain before, we might be able to now.
321    if (drainEvent && retryList.size() == 0 && curTick >= tickNextIdle) {
322        drainEvent->process();
323        // Clear the drain event once we're done with it.
324        drainEvent = NULL;
325    }
326}
327
328int
329Bus::findPort(Addr addr)
330{
331    /* An interval tree would be a better way to do this. --ali. */
332    int dest_id;
333
334    dest_id = checkPortCache(addr);
335    if (dest_id != -1)
336        return dest_id;
337
338    // Check normal port ranges
339    PortIter i = portMap.find(RangeSize(addr,1));
340    if (i != portMap.end()) {
341        dest_id = i->second;
342        updatePortCache(dest_id, i->first.start, i->first.end);
343        return dest_id;
344    }
345
346    // Check if this matches the default range
347    if (useDefaultRange) {
348        AddrRangeIter a_end = defaultRange.end();
349        for (AddrRangeIter i = defaultRange.begin(); i != a_end; i++) {
350            if (*i == addr) {
351                DPRINTF(Bus, "  found addr %#llx on default\n", addr);
352                return defaultId;
353            }
354        }
355
356        panic("Unable to find destination for addr %#llx\n", addr);
357    }
358
359    DPRINTF(Bus, "Unable to find destination for addr %#llx, "
360            "will use default port\n", addr);
361    return defaultId;
362}
363
364
365/** Function called by the port when the bus is receiving a Atomic
366 * transaction.*/
367Tick
368Bus::recvAtomic(PacketPtr pkt)
369{
370    DPRINTF(Bus, "recvAtomic: packet src %d dest %d addr 0x%x cmd %s\n",
371            pkt->getSrc(), pkt->getDest(), pkt->getAddr(), pkt->cmdString());
372    assert(pkt->getDest() == Packet::Broadcast);
373    assert(pkt->isRequest());
374
375    // Variables for recording original command and snoop response (if
376    // any)... if a snooper respondes, we will need to restore
377    // original command so that additional snoops can take place
378    // properly
379    MemCmd orig_cmd = pkt->cmd;
380    MemCmd snoop_response_cmd = MemCmd::InvalidCmd;
381    Tick snoop_response_latency = 0;
382    int orig_src = pkt->getSrc();
383
384    int target_port_id = findPort(pkt->getAddr());
385    BusPort *target_port;
386    if (target_port_id == defaultId)
387        target_port = defaultPort;
388    else {
389      target_port = checkBusCache(target_port_id);
390      if (target_port == NULL) {
391          target_port = interfaces[target_port_id];
392          updateBusCache(target_port_id, target_port);
393      }
394    }
395
396    SnoopIter s_end = snoopPorts.end();
397    for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) {
398        BusPort *p = *s_iter;
399        // same port should not have both target addresses and snooping
400        assert(p != target_port);
401        if (p->getId() != pkt->getSrc()) {
402            Tick latency = p->sendAtomic(pkt);
403            if (pkt->isResponse()) {
404                // response from snoop agent
405                assert(pkt->cmd != orig_cmd);
406                assert(pkt->memInhibitAsserted());
407                // should only happen once
408                assert(snoop_response_cmd == MemCmd::InvalidCmd);
409                // save response state
410                snoop_response_cmd = pkt->cmd;
411                snoop_response_latency = latency;
412                // restore original packet state for remaining snoopers
413                pkt->cmd = orig_cmd;
414                pkt->setSrc(orig_src);
415                pkt->setDest(Packet::Broadcast);
416            }
417        }
418    }
419
420    Tick response_latency = 0;
421
422    // we can get requests sent up from the memory side of the bus for
423    // snooping... don't send them back down!
424    if (target_port_id != pkt->getSrc()) {
425        response_latency = target_port->sendAtomic(pkt);
426    }
427
428    // if we got a response from a snooper, restore it here
429    if (snoop_response_cmd != MemCmd::InvalidCmd) {
430        // no one else should have responded
431        assert(!pkt->isResponse());
432        assert(pkt->cmd == orig_cmd);
433        pkt->cmd = snoop_response_cmd;
434        response_latency = snoop_response_latency;
435    }
436
437    // why do we have this packet field and the return value both???
438    pkt->finishTime = curTick + response_latency;
439    return response_latency;
440}
441
442/** Function called by the port when the bus is receiving a Functional
443 * transaction.*/
444void
445Bus::recvFunctional(PacketPtr pkt)
446{
447    if (!pkt->isPrint()) {
448        // don't do DPRINTFs on PrintReq as it clutters up the output
449        DPRINTF(Bus,
450                "recvFunctional: packet src %d dest %d addr 0x%x cmd %s\n",
451                pkt->getSrc(), pkt->getDest(), pkt->getAddr(),
452                pkt->cmdString());
453    }
454    assert(pkt->getDest() == Packet::Broadcast);
455
456    int port_id = findPort(pkt->getAddr());
457    Port *port = (port_id == defaultId) ? defaultPort : interfaces[port_id];
458    // The packet may be changed by another bus on snoops, restore the
459    // id after each
460    int src_id = pkt->getSrc();
461
462    assert(pkt->isRequest()); // hasn't already been satisfied
463
464    SnoopIter s_end = snoopPorts.end();
465    for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) {
466        BusPort *p = *s_iter;
467        if (p != port && p->getId() != src_id) {
468            p->sendFunctional(pkt);
469        }
470        if (pkt->isResponse()) {
471            break;
472        }
473        pkt->setSrc(src_id);
474    }
475
476    // If the snooping hasn't found what we were looking for, keep going.
477    if (!pkt->isResponse() && port_id != pkt->getSrc()) {
478        port->sendFunctional(pkt);
479    }
480}
481
482/** Function called by the port when the bus is receiving a status change.*/
483void
484Bus::recvStatusChange(Port::Status status, int id)
485{
486    AddrRangeList ranges;
487    bool snoops;
488    AddrRangeIter iter;
489
490    if (inRecvStatusChange.count(id))
491        return;
492    inRecvStatusChange.insert(id);
493
494    assert(status == Port::RangeChange &&
495           "The other statuses need to be implemented.");
496
497    DPRINTF(BusAddrRanges, "received RangeChange from device id %d\n", id);
498
499    clearPortCache();
500    if (id == defaultId) {
501        defaultRange.clear();
502        // Only try to update these ranges if the user set a default responder.
503        if (useDefaultRange) {
504            defaultPort->getPeerAddressRanges(ranges, snoops);
505            assert(snoops == false);
506            for(iter = ranges.begin(); iter != ranges.end(); iter++) {
507                defaultRange.push_back(*iter);
508                DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for default range\n",
509                        iter->start, iter->end);
510            }
511        }
512    } else {
513
514        assert((id < maxId && id >= 0) || id == defaultId);
515        BusPort *port = interfaces[id];
516
517        // Clean out any previously existent ids
518        for (PortIter portIter = portMap.begin();
519             portIter != portMap.end(); ) {
520            if (portIter->second == id)
521                portMap.erase(portIter++);
522            else
523                portIter++;
524        }
525
526        for (SnoopIter s_iter = snoopPorts.begin();
527             s_iter != snoopPorts.end(); ) {
528            if ((*s_iter)->getId() == id)
529                s_iter = snoopPorts.erase(s_iter);
530            else
531                s_iter++;
532        }
533
534        port->getPeerAddressRanges(ranges, snoops);
535
536        if (snoops) {
537            DPRINTF(BusAddrRanges, "Adding id %d to snoop list\n", id);
538            snoopPorts.push_back(port);
539        }
540
541        for (iter = ranges.begin(); iter != ranges.end(); iter++) {
542            DPRINTF(BusAddrRanges, "Adding range %#llx - %#llx for id %d\n",
543                    iter->start, iter->end, id);
544            if (portMap.insert(*iter, id) == portMap.end()) {
545                int conflict_id = portMap.find(*iter)->second;
546                fatal("%s has two ports with same range:\n\t%s\n\t%s\n",
547                      name(), interfaces[id]->getPeer()->name(),
548                      interfaces[conflict_id]->getPeer()->name());
549            }
550        }
551    }
552    DPRINTF(MMU, "port list has %d entries\n", portMap.size());
553
554    // tell all our peers that our address range has changed.
555    // Don't tell the device that caused this change, it already knows
556    m5::hash_map<short,BusPort*>::iterator intIter;
557
558    for (intIter = interfaces.begin(); intIter != interfaces.end(); intIter++)
559        if (intIter->first != id && intIter->first != funcPortId)
560            intIter->second->sendStatusChange(Port::RangeChange);
561
562    if (id != defaultId && defaultPort)
563        defaultPort->sendStatusChange(Port::RangeChange);
564    inRecvStatusChange.erase(id);
565}
566
567void
568Bus::addressRanges(AddrRangeList &resp, bool &snoop, int id)
569{
570    resp.clear();
571    snoop = false;
572
573    DPRINTF(BusAddrRanges, "received address range request, returning:\n");
574
575    for (AddrRangeIter dflt_iter = defaultRange.begin();
576         dflt_iter != defaultRange.end(); dflt_iter++) {
577        resp.push_back(*dflt_iter);
578        DPRINTF(BusAddrRanges, "  -- Dflt: %#llx : %#llx\n",dflt_iter->start,
579                dflt_iter->end);
580    }
581    for (PortIter portIter = portMap.begin();
582         portIter != portMap.end(); portIter++) {
583        bool subset = false;
584        for (AddrRangeIter dflt_iter = defaultRange.begin();
585             dflt_iter != defaultRange.end(); dflt_iter++) {
586            if ((portIter->first.start < dflt_iter->start &&
587                portIter->first.end >= dflt_iter->start) ||
588               (portIter->first.start < dflt_iter->end &&
589                portIter->first.end >= dflt_iter->end))
590                fatal("Devices can not set ranges that itersect the default set\
591                        but are not a subset of the default set.\n");
592            if (portIter->first.start >= dflt_iter->start &&
593                portIter->first.end <= dflt_iter->end) {
594                subset = true;
595                DPRINTF(BusAddrRanges, "  -- %#llx : %#llx is a SUBSET\n",
596                    portIter->first.start, portIter->first.end);
597            }
598        }
599        if (portIter->second != id && !subset) {
600            resp.push_back(portIter->first);
601            DPRINTF(BusAddrRanges, "  -- %#llx : %#llx\n",
602                    portIter->first.start, portIter->first.end);
603        }
604    }
605
606    for (SnoopIter s_iter = snoopPorts.begin(); s_iter != snoopPorts.end();
607         s_iter++) {
608        if ((*s_iter)->getId() != id) {
609            snoop = true;
610            break;
611        }
612    }
613}
614
615unsigned
616Bus::findBlockSize(int id)
617{
618    if (cachedBlockSizeValid)
619        return cachedBlockSize;
620
621    unsigned max_bs = 0;
622
623    PortIter p_end = portMap.end();
624    for (PortIter p_iter = portMap.begin(); p_iter != p_end; p_iter++) {
625        unsigned tmp_bs = interfaces[p_iter->second]->peerBlockSize();
626        if (tmp_bs > max_bs)
627            max_bs = tmp_bs;
628    }
629    SnoopIter s_end = snoopPorts.end();
630    for (SnoopIter s_iter = snoopPorts.begin(); s_iter != s_end; s_iter++) {
631        unsigned tmp_bs = (*s_iter)->peerBlockSize();
632        if (tmp_bs > max_bs)
633            max_bs = tmp_bs;
634    }
635    if (max_bs == 0)
636        max_bs = defaultBlockSize;
637
638    if (max_bs != 64)
639        warn_once("Blocksize found to not be 64... hmm... probably not.\n");
640    cachedBlockSize = max_bs;
641    cachedBlockSizeValid = true;
642    return max_bs;
643}
644
645
646unsigned int
647Bus::drain(Event * de)
648{
649    //We should check that we're not "doing" anything, and that noone is
650    //waiting. We might be idle but have someone waiting if the device we
651    //contacted for a retry didn't actually retry.
652    if (retryList.size() || (curTick < tickNextIdle && busIdle.scheduled())) {
653        drainEvent = de;
654        return 1;
655    }
656    return 0;
657}
658
659void
660Bus::startup()
661{
662    if (tickNextIdle < curTick)
663        tickNextIdle = (curTick / clock) * clock + clock;
664}
665
666Bus *
667BusParams::create()
668{
669    return new Bus(this);
670}
671