addr_range.hh revision 9411:22e15f9c3fda 
1/*
2 * Copyright (c) 2012 ARM Limited
3 * All rights reserved
4 *
5 * The license below extends only to copyright in the software and shall
6 * not be construed as granting a license to any other intellectual
7 * property including but not limited to intellectual property relating
8 * to a hardware implementation of the functionality of the software
9 * licensed hereunder.  You may use the software subject to the license
10 * terms below provided that you ensure that this notice is replicated
11 * unmodified and in its entirety in all distributions of the software,
12 * modified or unmodified, in source code or in binary form.
13 *
14 * Copyright (c) 2002-2005 The Regents of The University of Michigan
15 * All rights reserved.
16 *
17 * Redistribution and use in source and binary forms, with or without
18 * modification, are permitted provided that the following conditions are
19 * met: redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer;
21 * redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution;
24 * neither the name of the copyright holders nor the names of its
25 * contributors may be used to endorse or promote products derived from
26 * this software without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
29 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
30 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
31 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
32 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
33 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
34 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
35 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
36 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
37 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
38 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
39 *
40 * Authors: Nathan Binkert
41 *          Steve Reinhardt
42 *          Andreas Hansson
43 */
44
45#ifndef __BASE_ADDR_RANGE_HH__
46#define __BASE_ADDR_RANGE_HH__
47
48#include "base/bitfield.hh"
49#include "base/cprintf.hh"
50#include "base/misc.hh"
51#include "base/types.hh"
52
53class AddrRange
54{
55
56  private:
57
58    /// Private fields for the start and end of the range
59    Addr _start;
60    Addr _end;
61
62    /// The high bit of the slice that is used for interleaving
63    uint8_t intlvHighBit;
64
65    /// The number of bits used for interleaving, set to 0 to disable
66    uint8_t intlvBits;
67
68    /// The value to compare the slice addr[high:(high - bits + 1)]
69    /// with.
70    uint8_t intlvMatch;
71
72  public:
73
74    AddrRange()
75        : _start(1), _end(0), intlvHighBit(0), intlvBits(0), intlvMatch(0)
76    {}
77
78    AddrRange(Addr _start, Addr _end, uint8_t _intlv_high_bit,
79              uint8_t _intlv_bits, uint8_t _intlv_match)
80        : _start(_start), _end(_end), intlvHighBit(_intlv_high_bit),
81          intlvBits(_intlv_bits), intlvMatch(_intlv_match)
82    {}
83
84    AddrRange(Addr _start, Addr _end)
85        : _start(_start), _end(_end), intlvHighBit(0), intlvBits(0),
86          intlvMatch(0)
87    {}
88
89    /**
90     * Determine if the range is interleaved or not.
91     *
92     * @return true if interleaved
93     */
94    bool interleaved() const { return intlvBits != 0; }
95
96    /**
97     * Determing the interleaving granularity of the range.
98     *
99     * @return The size of the regions created by the interleaving bits
100     */
101    uint64_t granularity() const { return ULL(1) << intlvHighBit; }
102
103    /**
104     * Determine the number of interleaved address stripes this range
105     * is part of.
106     *
107     * @return The number of stripes spanned by the interleaving bits
108     */
109    uint32_t stripes() const { return ULL(1) << intlvBits; }
110
111    /**
112     * Get the size of the address range. For a case where
113     * interleaving is used we make the simplifying assumption that
114     * the size is a divisible by the size of the interleaving slice.
115     */
116    Addr size() const
117    {
118        return (_end - _start + 1) >> intlvBits;
119    }
120
121    /**
122     * Determine if the range is valid.
123     */
124    bool valid() const { return _start < _end; }
125
126    /**
127     * Get the start address of the range.
128     */
129    Addr start() const { return _start; }
130
131    /**
132     * Get a string representation of the range. This could
133     * alternatively be implemented as a operator<<, but at the moment
134     * that seems like overkill.
135     */
136    std::string to_string() const
137    {
138        if (interleaved())
139            return csprintf("[%#llx : %#llx], [%d : %d] = %d", _start, _end,
140                            intlvHighBit, intlvHighBit - intlvBits + 1,
141                            intlvMatch);
142        else
143            return csprintf("[%#llx : %#llx]", _start, _end);
144    }
145
146    /**
147     * Determine if another range merges with the current one, i.e. if
148     * they are part of the same contigous range and have the same
149     * interleaving bits.
150     *
151     * @param r Range to evaluate merging with
152     * @return true if the two ranges would merge
153     */
154    bool mergesWith(const AddrRange& r) const
155    {
156        return r._start == _start && r._end == _end &&
157            r.intlvHighBit == intlvHighBit &&
158            r.intlvBits == intlvBits;
159    }
160
161    /**
162     * Determine if another range intersects this one, i.e. if there
163     * is an address that is both in this range and the other
164     * range. No check is made to ensure either range is valid.
165     *
166     * @param r Range to intersect with
167     * @return true if the intersection of the two ranges is not empty
168     */
169    bool intersects(const AddrRange& r) const
170    {
171        if (!interleaved()) {
172            return _start <= r._end && _end >= r._start;
173        }
174
175        // the current range is interleaved, split the check up in
176        // three cases
177        if (r.size() == 1)
178            // keep it simple and check if the address is within
179            // this range
180            return contains(r.start());
181        else if (!r.interleaved())
182            // be conservative and ignore the interleaving
183            return _start <= r._end && _end >= r._start;
184        else if (mergesWith(r))
185            // restrict the check to ranges that belong to the
186            // same chunk
187            return intlvMatch == r.intlvMatch;
188        else
189            panic("Cannot test intersection of interleaved range %s\n",
190                  to_string());
191    }
192
193    /**
194     * Determine if this range is a subset of another range, i.e. if
195     * every address in this range is also in the other range. No
196     * check is made to ensure either range is valid.
197     *
198     * @param r Range to compare with
199     * @return true if the this range is a subset of the other one
200     */
201    bool isSubset(const AddrRange& r) const
202    {
203        if (interleaved())
204            panic("Cannot test subset of interleaved range %s\n", to_string());
205        return _start >= r._start && _end <= r._end;
206    }
207
208    /**
209     * Determine if the range contains an address.
210     *
211     * @param a Address to compare with
212     * @return true if the address is in the range
213     */
214    bool contains(const Addr& a) const
215    {
216        // check if the address is in the range and if there is either
217        // no interleaving, or with interleaving also if the selected
218        // bits from the address match the interleaving value
219        return a >= _start && a <= _end &&
220            (interleaved() ||
221             (bits(a, intlvHighBit, intlvHighBit - intlvBits + 1) ==
222              intlvMatch));
223    }
224
225/**
226 * Keep the operators away from SWIG.
227 */
228#ifndef SWIG
229
230    /**
231     * Less-than operator used to turn an STL map into a binary search
232     * tree of non-overlapping address ranges.
233     *
234     * @param r Range to compare with
235     * @return true if the start address is less than that of the other range
236     */
237    bool operator<(const AddrRange& r) const
238    {
239        if (_start != r._start)
240            return _start < r._start;
241        else
242            // for now assume that the end is also the same, and that
243            // we are looking at the same interleaving bits
244            return intlvMatch < r.intlvMatch;
245    }
246
247#endif // SWIG
248};
249
250inline AddrRange
251RangeEx(Addr start, Addr end)
252{ return AddrRange(start, end - 1); }
253
254inline AddrRange
255RangeIn(Addr start, Addr end)
256{ return AddrRange(start, end); }
257
258inline AddrRange
259RangeSize(Addr start, Addr size)
260{ return AddrRange(start, start + size - 1); }
261
262#endif // __BASE_ADDR_RANGE_HH__
263