snoop_filter.hh revision 11168:f98eb2da15a4
12810SN/A/* 29614Srene.dejong@arm.com * Copyright (c) 2013-2015 ARM Limited 38856Sandreas.hansson@arm.com * All rights reserved 48856Sandreas.hansson@arm.com * 58856Sandreas.hansson@arm.com * The license below extends only to copyright in the software and shall 68856Sandreas.hansson@arm.com * not be construed as granting a license to any other intellectual 78856Sandreas.hansson@arm.com * property including but not limited to intellectual property relating 88856Sandreas.hansson@arm.com * to a hardware implementation of the functionality of the software 98856Sandreas.hansson@arm.com * licensed hereunder. You may use the software subject to the license 108856Sandreas.hansson@arm.com * terms below provided that you ensure that this notice is replicated 118856Sandreas.hansson@arm.com * unmodified and in its entirety in all distributions of the software, 128856Sandreas.hansson@arm.com * modified or unmodified, in source code or in binary form. 138856Sandreas.hansson@arm.com * 142810SN/A * Redistribution and use in source and binary forms, with or without 152810SN/A * modification, are permitted provided that the following conditions are 162810SN/A * met: redistributions of source code must retain the above copyright 172810SN/A * notice, this list of conditions and the following disclaimer; 182810SN/A * redistributions in binary form must reproduce the above copyright 192810SN/A * notice, this list of conditions and the following disclaimer in the 202810SN/A * documentation and/or other materials provided with the distribution; 212810SN/A * neither the name of the copyright holders nor the names of its 222810SN/A * contributors may be used to endorse or promote products derived from 232810SN/A * this software without specific prior written permission. 242810SN/A * 252810SN/A * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 262810SN/A * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 272810SN/A * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 282810SN/A * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 292810SN/A * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 302810SN/A * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 312810SN/A * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 322810SN/A * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 332810SN/A * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 342810SN/A * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 352810SN/A * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 362810SN/A * 372810SN/A * Authors: Stephan Diestelhorst 382810SN/A */ 392810SN/A 402810SN/A/** 412810SN/A * @file 422810SN/A * Definition of a snoop filter. 432810SN/A */ 442810SN/A 452810SN/A#ifndef __MEM_SNOOP_FILTER_HH__ 462810SN/A#define __MEM_SNOOP_FILTER_HH__ 472810SN/A 4811486Snikos.nikoleris@arm.com#include <unordered_map> 4911486Snikos.nikoleris@arm.com#include <utility> 508232Snate@binkert.org 519152Satgutier@umich.edu#include "mem/packet.hh" 5211486Snikos.nikoleris@arm.com#include "mem/port.hh" 5311486Snikos.nikoleris@arm.com#include "mem/qport.hh" 549795Sandreas.hansson@arm.com#include "params/SnoopFilter.hh" 559795Sandreas.hansson@arm.com#include "sim/sim_object.hh" 5610263Satgutier@umich.edu#include "sim/system.hh" 578786Sgblack@eecs.umich.edu 582810SN/A/** 592810SN/A * This snoop filter keeps track of which connected port has a 602810SN/A * particular line of data. It can be queried (through lookup*) on 618856Sandreas.hansson@arm.com * memory requests from above (reads / writes / ...); and also from 628856Sandreas.hansson@arm.com * below (snoops). The snoop filter precisely knows about the location 638856Sandreas.hansson@arm.com * of lines "above" it through a map from cache line address to 648922Swilliam.wang@arm.com * sharers/ports. The snoop filter ties into the flows of requests 6512084Sspwilson2@wisc.edu * (when they succeed at the lower interface), regular responses from 6612084Sspwilson2@wisc.edu * below and also responses from sideway's caches (in update*). This 678856Sandreas.hansson@arm.com * allows the snoop filter to model cache-line residency by snooping 688856Sandreas.hansson@arm.com * the messages. 694475SN/A * 7011053Sandreas.hansson@arm.com * The tracking happens in two fields to be able to distinguish 715034SN/A * between in-flight requests (in requested) and already pulled in 7210360Sandreas.hansson@arm.com * lines (in holder). This distinction is used for producing tighter 7311377Sandreas.hansson@arm.com * assertions and tracking request completion. For safety, (requested 7411377Sandreas.hansson@arm.com * | holder) should be notified and the requesting MSHRs will take 7511053Sandreas.hansson@arm.com * care of ordering. 7611722Ssophiane.senni@gmail.com * 7711722Ssophiane.senni@gmail.com * Overall, some trickery is required because: 7811722Ssophiane.senni@gmail.com * (1) snoops are not followed by an ACK, but only evoke a response if 7911722Ssophiane.senni@gmail.com * they need to (hit dirty) 809263Smrinmoy.ghosh@arm.com * (2) side-channel information is funnelled through direct modifications of 815034SN/A * pkt, instead of proper messages through the bus 8211331Sandreas.hansson@arm.com * (3) there are no clean evict messages telling the snoop filter that a local, 8310884Sandreas.hansson@arm.com * upper cache dropped a line, making the snoop filter pessimistic for now 844626SN/A * (4) ordering: there is no single point of order in the system. Instead, 8510360Sandreas.hansson@arm.com * requesting MSHRs track order between local requests and remote snoops 8611484Snikos.nikoleris@arm.com */ 875034SN/Aclass SnoopFilter : public SimObject { 888883SAli.Saidi@ARM.com public: 898833Sdam.sunwoo@arm.com typedef std::vector<QueuedSlavePort*> SnoopList; 904458SN/A 9111377Sandreas.hansson@arm.com SnoopFilter (const SnoopFilterParams *p) : 9211377Sandreas.hansson@arm.com SimObject(p), reqLookupResult(cachedLocations.end()), retryItem{0, 0}, 9311377Sandreas.hansson@arm.com linesize(p->system->cacheLineSize()), lookupLatency(p->lookup_latency), 9411377Sandreas.hansson@arm.com maxEntryCount(p->max_capacity / p->system->cacheLineSize()) 9511377Sandreas.hansson@arm.com { 9611377Sandreas.hansson@arm.com } 9711331Sandreas.hansson@arm.com 9811331Sandreas.hansson@arm.com /** 992810SN/A * Init a new snoop filter and tell it about all the slave ports 1002810SN/A * of the enclosing bus. 1013013SN/A * 1028856Sandreas.hansson@arm.com * @param slave_ports Slave ports that the bus is attached to. 1032810SN/A */ 1043013SN/A void setSlavePorts(const SnoopList& slave_ports) { 10510714Sandreas.hansson@arm.com localSlavePortIds.resize(slave_ports.size(), InvalidPortID); 1062810SN/A 1079614Srene.dejong@arm.com PortID id = 0; 1089614Srene.dejong@arm.com for (const auto& p : slave_ports) { 1099614Srene.dejong@arm.com // no need to track this port if it is not snooping 11010345SCurtis.Dunham@arm.com if (p->isSnooping()) { 11110714Sandreas.hansson@arm.com slavePorts.push_back(p); 11210345SCurtis.Dunham@arm.com localSlavePortIds[p->getId()] = id++; 1139614Srene.dejong@arm.com } 1142810SN/A } 1152810SN/A 1162810SN/A // make sure we can deal with this many ports 1178856Sandreas.hansson@arm.com fatal_if(id > 8 * sizeof(SnoopMask), 1182810SN/A "Snoop filter only supports %d snooping ports, got %d\n", 1193013SN/A 8 * sizeof(SnoopMask), id); 12010714Sandreas.hansson@arm.com } 1213013SN/A 1228856Sandreas.hansson@arm.com /** 12310714Sandreas.hansson@arm.com * Lookup a request (from a slave port) in the snoop filter and 1248922Swilliam.wang@arm.com * return a list of other slave ports that need forwarding of the 1252897SN/A * resulting snoops. Additionally, update the tracking structures 1262810SN/A * with new request information. Note that the caller must also 1272810SN/A * call finishRequest once it is known if the request needs to 12810344Sandreas.hansson@arm.com * retry or not. 12910344Sandreas.hansson@arm.com * 13010344Sandreas.hansson@arm.com * @param cpkt Pointer to the request packet. Not changed. 13110714Sandreas.hansson@arm.com * @param slave_port Slave port where the request came from. 13210344Sandreas.hansson@arm.com * @return Pair of a vector of snoop target ports and lookup latency. 13310344Sandreas.hansson@arm.com */ 13410344Sandreas.hansson@arm.com std::pair<SnoopList, Cycles> lookupRequest(const Packet* cpkt, 13510713Sandreas.hansson@arm.com const SlavePort& slave_port); 13610344Sandreas.hansson@arm.com 1372844SN/A /** 1382810SN/A * For an un-successful request, revert the change to the snoop 1392858SN/A * filter. Also take care of erasing any null entries. This method 1402858SN/A * relies on the result from lookupRequest being stored in 1418856Sandreas.hansson@arm.com * reqLookupResult. 1428922Swilliam.wang@arm.com * 1438711Sandreas.hansson@arm.com * @param will_retry This request will retry on this bus / snoop filter 14411331Sandreas.hansson@arm.com * @param cpkt Request packet, merely for sanity checking 1452858SN/A */ 1462858SN/A void finishRequest(bool will_retry, const Packet* cpkt); 1479294Sandreas.hansson@arm.com 1489294Sandreas.hansson@arm.com /** 1498922Swilliam.wang@arm.com * Handle an incoming snoop from below (the master port). These 1508922Swilliam.wang@arm.com * can upgrade the tracking logic and may also benefit from 1518922Swilliam.wang@arm.com * additional steering thanks to the snoop filter. 1528922Swilliam.wang@arm.com * 1538922Swilliam.wang@arm.com * @param cpkt Pointer to const Packet containing the snoop. 1548922Swilliam.wang@arm.com * @return Pair with a vector of SlavePorts that need snooping and a lookup 1558922Swilliam.wang@arm.com * latency. 1568922Swilliam.wang@arm.com */ 1579294Sandreas.hansson@arm.com std::pair<SnoopList, Cycles> lookupSnoop(const Packet* cpkt); 1589294Sandreas.hansson@arm.com 1598922Swilliam.wang@arm.com /** 1608922Swilliam.wang@arm.com * Let the snoop filter see any snoop responses that turn into 1618922Swilliam.wang@arm.com * request responses and indicate cache to cache transfers. These 1628922Swilliam.wang@arm.com * will update the corresponding state in the filter. 1638922Swilliam.wang@arm.com * 1648922Swilliam.wang@arm.com * @param cpkt Pointer to const Packet holding the snoop response. 1658922Swilliam.wang@arm.com * @param rsp_port SlavePort that sends the response. 1664628SN/A * @param req_port SlavePort that made the original request and is the 16710821Sandreas.hansson@arm.com * destination of the snoop response. 16810821Sandreas.hansson@arm.com */ 16910821Sandreas.hansson@arm.com void updateSnoopResponse(const Packet *cpkt, const SlavePort& rsp_port, 17010821Sandreas.hansson@arm.com const SlavePort& req_port); 17110821Sandreas.hansson@arm.com 17210821Sandreas.hansson@arm.com /** 17310821Sandreas.hansson@arm.com * Pass snoop responses that travel downward through the snoop 17410821Sandreas.hansson@arm.com * filter and let them update the snoop filter state. No 17510821Sandreas.hansson@arm.com * additional routing happens. 17610821Sandreas.hansson@arm.com * 17710821Sandreas.hansson@arm.com * @param cpkt Pointer to const Packet holding the snoop response. 1782858SN/A * @param rsp_port SlavePort that sends the response. 1792810SN/A * @param req_port MasterPort through which the response is forwarded. 1802810SN/A */ 18111522Sstephan.diestelhorst@arm.com void updateSnoopForward(const Packet *cpkt, const SlavePort& rsp_port, 18211522Sstephan.diestelhorst@arm.com const MasterPort& req_port); 1832810SN/A 1842810SN/A /** 1852810SN/A * Update the snoop filter with a response from below (outer / 1864022SN/A * other cache, or memory) and update the tracking information in 1874022SN/A * the snoop filter. 1884022SN/A * 1892810SN/A * @param cpkt Pointer to const Packet holding the snoop response. 1902810SN/A * @param slave_port SlavePort that made the original request and 1918833Sdam.sunwoo@arm.com * is the target of this response. 1922810SN/A */ 1932810SN/A void updateResponse(const Packet *cpkt, const SlavePort& slave_port); 1942810SN/A 1952810SN/A virtual void regStats(); 1968833Sdam.sunwoo@arm.com 1978833Sdam.sunwoo@arm.com protected: 1988833Sdam.sunwoo@arm.com 1992810SN/A /** 2002810SN/A * The underlying type for the bitmask we use for tracking. This 2014871SN/A * limits the number of snooping ports supported per crossbar. For 2024871SN/A * the moment it is an uint64_t to offer maximum 2034871SN/A * scalability. However, it is possible to use e.g. a uint16_t or 2044871SN/A * uint32_to slim down the footprint of the hash map (and 20511455Sandreas.hansson@arm.com * ultimately improve the simulation performance). 20610885Sandreas.hansson@arm.com */ 2074871SN/A typedef uint64_t SnoopMask; 2084871SN/A 2094871SN/A /** 2104871SN/A * Per cache line item tracking a bitmask of SlavePorts who have an 2114871SN/A * outstanding request to this line (requested) or already share a 2122810SN/A * cache line with this address (holder). 2132810SN/A */ 2142810SN/A struct SnoopItem { 2158833Sdam.sunwoo@arm.com SnoopMask requested; 2162810SN/A SnoopMask holder; 2174871SN/A }; 2188833Sdam.sunwoo@arm.com /** 2198833Sdam.sunwoo@arm.com * HashMap of SnoopItems indexed by line address 2208833Sdam.sunwoo@arm.com */ 2212810SN/A typedef std::unordered_map<Addr, SnoopItem> SnoopFilterCache; 2222810SN/A 2232810SN/A /** 2242810SN/A * Simple factory methods for standard return values. 2258833Sdam.sunwoo@arm.com */ 2262810SN/A std::pair<SnoopList, Cycles> snoopAll(Cycles latency) const 2274871SN/A { 2288833Sdam.sunwoo@arm.com return std::make_pair(slavePorts, latency); 2298833Sdam.sunwoo@arm.com } 2308833Sdam.sunwoo@arm.com std::pair<SnoopList, Cycles> snoopSelected(const SnoopList& slave_ports, 2312810SN/A Cycles latency) const 2322810SN/A { 2334022SN/A return std::make_pair(slave_ports, latency); 2344022SN/A } 2354022SN/A std::pair<SnoopList, Cycles> snoopDown(Cycles latency) const 2362810SN/A { 2372810SN/A SnoopList empty; 2388833Sdam.sunwoo@arm.com return std::make_pair(empty , latency); 2392810SN/A } 2402810SN/A 2412810SN/A /** 2422810SN/A * Convert a single port to a corresponding, one-hot bitmask 2438833Sdam.sunwoo@arm.com * @param port SlavePort that should be converted. 2448833Sdam.sunwoo@arm.com * @return One-hot bitmask corresponding to the port. 2458833Sdam.sunwoo@arm.com */ 2462810SN/A SnoopMask portToMask(const SlavePort& port) const; 2472810SN/A /** 2482810SN/A * Converts a bitmask of ports into the corresponing list of ports 2492810SN/A * @param ports SnoopMask of the requested ports 2502810SN/A * @return SnoopList containing all the requested SlavePorts 2518833Sdam.sunwoo@arm.com */ 2522810SN/A SnoopList maskToPortList(SnoopMask ports) const; 2534871SN/A 2548833Sdam.sunwoo@arm.com private: 2558833Sdam.sunwoo@arm.com 2568833Sdam.sunwoo@arm.com /** 2572810SN/A * Removes snoop filter items which have no requesters and no holders. 2582810SN/A */ 2592810SN/A void eraseIfNullEntry(SnoopFilterCache::iterator& sf_it); 2602810SN/A 2618833Sdam.sunwoo@arm.com /** Simple hash set of cached addresses. */ 2622810SN/A SnoopFilterCache cachedLocations; 2634871SN/A /** 2648833Sdam.sunwoo@arm.com * Iterator used to store the result from lookupRequest until we 2658833Sdam.sunwoo@arm.com * call finishRequest. 2668833Sdam.sunwoo@arm.com */ 2672810SN/A SnoopFilterCache::iterator reqLookupResult; 2682810SN/A /** 2694022SN/A * Variable to temporarily store value of snoopfilter entry 2704022SN/A * incase finishRequest needs to undo changes made in lookupRequest 2714022SN/A * (because of crossbar retry) 2722810SN/A */ 2732810SN/A SnoopItem retryItem; 2748833Sdam.sunwoo@arm.com /** List of all attached snooping slave ports. */ 2752810SN/A SnoopList slavePorts; 2762810SN/A /** Track the mapping from port ids to the local mask ids. */ 2772810SN/A std::vector<PortID> localSlavePortIds; 2782810SN/A /** Cache line size. */ 2798833Sdam.sunwoo@arm.com const unsigned linesize; 2808833Sdam.sunwoo@arm.com /** Latency for doing a lookup in the filter */ 2818833Sdam.sunwoo@arm.com const Cycles lookupLatency; 2822810SN/A /** Max capacity in terms of cache blocks tracked, for sanity checking */ 2832810SN/A const unsigned maxEntryCount; 2842810SN/A 2852810SN/A /** Statistics */ 2862810SN/A Stats::Scalar totRequests; 2878833Sdam.sunwoo@arm.com Stats::Scalar hitSingleRequests; 2882810SN/A Stats::Scalar hitMultiRequests; 2894871SN/A 2908833Sdam.sunwoo@arm.com Stats::Scalar totSnoops; 2918833Sdam.sunwoo@arm.com Stats::Scalar hitSingleSnoops; 2928833Sdam.sunwoo@arm.com Stats::Scalar hitMultiSnoops; 2932810SN/A}; 2942810SN/A 2952810SN/Ainline SnoopFilter::SnoopMask 2962810SN/ASnoopFilter::portToMask(const SlavePort& port) const 2978833Sdam.sunwoo@arm.com{ 2982810SN/A assert(port.getId() != InvalidPortID); 2994871SN/A // if this is not a snooping port, return a zero mask 3008833Sdam.sunwoo@arm.com return !port.isSnooping() ? 0 : 3018833Sdam.sunwoo@arm.com ((SnoopMask)1) << localSlavePortIds[port.getId()]; 3028833Sdam.sunwoo@arm.com} 3032810SN/A 3042810SN/Ainline SnoopFilter::SnoopList 3054022SN/ASnoopFilter::maskToPortList(SnoopMask port_mask) const 3064022SN/A{ 3074022SN/A SnoopList res; 3082810SN/A for (const auto& p : slavePorts) 3092810SN/A if (port_mask & portToMask(*p)) 3102810SN/A res.push_back(p); 3112810SN/A return res; 3122810SN/A} 3132810SN/A 3148833Sdam.sunwoo@arm.com#endif // __MEM_SNOOP_FILTER_HH__ 3152810SN/A