src/base/addr_range.test.cc

   1 /*
   2  * Copyright (c) 2019 The Regents of the University of California
   3  * Copyright (c) 2018-2019 ARM Limited
   4  * All rights reserved
   5  *
   6  * The license below extends only to copyright in the software and shall
   7  * not be construed as granting a license to any other intellectual
   8  * property including but not limited to intellectual property relating
   9  * to a hardware implementation of the functionality of the software
  10  * licensed hereunder.  You may use the software subject to the license
  11  * terms below provided that you ensure that this notice is replicated
  12  * unmodified and in its entirety in all distributions of the software,
  13  * modified or unmodified, in source code or in binary form.
  14  *
  15  * Redistribution and use in source and binary forms, with or without
  16  * modification, are permitted provided that the following conditions are
  17  * met: redistributions of source code must retain the above copyright
  18  * notice, this list of conditions and the following disclaimer;
  19  * redistributions in binary form must reproduce the above copyright
  20  * notice, this list of conditions and the following disclaimer in the
  21  * documentation and/or other materials provided with the distribution;
  22  * neither the name of the copyright holders nor the names of its
  23  * contributors may be used to endorse or promote products derived from
  24  * this software without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  27  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  28  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  29  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  30  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  31  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  32  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  33  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  34  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  35  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  36  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37  *
  38  * Authors: Nikos Nikoleris
  39  *          Bobby R. Bruce
  40  */
  41
  42 #include <gtest/gtest.h>
  43
  44 #include <cmath>
  45
  46 #include "base/addr_range.hh"
  47 #include "base/bitfield.hh"
  48
  49 TEST(AddrRangeTest, ValidRange)
  50 {
  51     AddrRange r;
  52     EXPECT_FALSE(r.valid());
  53 }
  54
  55 /*
  56  * This following tests check the behavior of AddrRange when initialized with
  57  * a start and end address. The expected behavior is that the first address
  58  * within the range will be the start address, and the last address in the
  59  * range will be the (end - 1) address.
  60  */
  61 TEST(AddrRangeTest, EmptyRange)
  62 {
  63     AddrRange r(0x0, 0x0);
  64
  65     /*
  66      * Empty ranges are valid.
  67      */
  68     EXPECT_TRUE(r.valid());
  69     EXPECT_EQ(0x0, r.start());
  70     EXPECT_EQ(0x0, r.end());
  71     EXPECT_EQ(0, r.size());
  72
  73     /*
  74      * With no masks, granularity equals the size of the range.
  75      */
  76     EXPECT_EQ(0, r.granularity());
  77
  78     /*
  79      * With no masks, "interleaved()" returns false.
  80      */
  81     EXPECT_FALSE(r.interleaved());
  82
  83     /*
  84      * With no masks, "stripes()" returns ULL(1).
  85      */
  86     EXPECT_EQ(ULL(1), r.stripes());
  87     EXPECT_EQ("[0:0]", r.to_string());
  88 }
  89
  90 TEST(AddrRangeTest, RangeSizeOfOne)
  91 {
  92     AddrRange r(0x0, 0x1);
  93     EXPECT_TRUE(r.valid());
  94     EXPECT_EQ(0x0, r.start());
  95     EXPECT_EQ(0x1, r.end());
  96     EXPECT_EQ(1, r.size());
  97     EXPECT_EQ(1, r.granularity());
  98     EXPECT_FALSE(r.interleaved());
  99     EXPECT_EQ(ULL(1), r.stripes());
 100     EXPECT_EQ("[0:0x1]", r.to_string());
 101 }
 102
 103 TEST(AddrRangeTest, Range16Bit)
 104 {
 105     AddrRange r(0xF000, 0xFFFF);
 106     EXPECT_TRUE(r.valid());
 107     EXPECT_EQ(0xF000, r.start());
 108     EXPECT_EQ(0xFFFF, r.end());
 109     EXPECT_EQ(0x0FFF, r.size());
 110     EXPECT_EQ(0x0FFF, r.granularity());
 111     EXPECT_FALSE(r.interleaved());
 112     EXPECT_EQ(ULL(1), r.stripes());
 113     EXPECT_EQ("[0xf000:0xffff]", r.to_string());
 114 }
 115
 116 TEST(AddrRangeTest, InvalidRange)
 117 {
 118     AddrRange r(0x1, 0x0);
 119     EXPECT_FALSE(r.valid());
 120 }
 121
 122 TEST(AddrRangeTest, LessThan)
 123 {
 124     /*
 125      * The less-than override is a bit unintuitive and does not have a
 126      * corresponding greater than. It compares the AddrRange.start() values.
 127      * If they are equal, the "intlvMatch" values are compared. This is
 128      * zero when AddRange is initialized with a just a start and end address.
 129      */
 130     AddrRange r1(0xF000, 0xFFFF);
 131     AddrRange r2(0xF001, 0xFFFF);
 132     AddrRange r3(0xF000, 0xFFFF);
 133
 134     EXPECT_TRUE(r1 < r2);
 135     EXPECT_FALSE(r2 < r1);
 136     EXPECT_FALSE(r1 < r3);
 137     EXPECT_FALSE(r3 < r1);
 138 }
 139
 140 TEST(AddrRangeTest, EqualToNotEqualTo)
 141 {
 142     AddrRange r1(0x1234, 0x5678);
 143     AddrRange r2(0x1234, 0x5678);
 144     AddrRange r3(0x1234, 0x5679);
 145
 146     EXPECT_TRUE(r1 == r2);
 147     EXPECT_FALSE(r1 == r3);
 148     EXPECT_FALSE(r1 != r2);
 149     EXPECT_TRUE(r1 != r3);
 150
 151     EXPECT_TRUE(r2 == r1);
 152     EXPECT_FALSE(r3 == r1);
 153     EXPECT_FALSE(r2 != r1);
 154     EXPECT_TRUE(r3 != r1);
 155 }
 156
 157 TEST(AddrRangeTest, MergesWith)
 158 {
 159     /*
 160      * AddrRange.mergesWith will return true if the start, end, and masks
 161      * are the same.
 162      */
 163     AddrRange r1(0x10, 0x1F);
 164     AddrRange r2(0x10, 0x1F);
 165
 166     EXPECT_TRUE(r1.mergesWith(r2));
 167     EXPECT_TRUE(r2.mergesWith(r1));
 168 }
 169
 170 TEST(AddrRangeTest, DoesNotMergeWith)
 171 {
 172     AddrRange r1(0x10, 0x1E);
 173     AddrRange r2(0x10, 0x1F);
 174
 175     EXPECT_FALSE(r1.mergesWith(r2));
 176     EXPECT_FALSE(r2.mergesWith(r1));
 177 }
 178
 179 TEST(AddrRangeTest, IntersectsCompleteOverlap)
 180 {
 181     AddrRange r1(0x21, 0x30);
 182     AddrRange r2(0x21, 0x30);
 183
 184     EXPECT_TRUE(r1.intersects(r2));
 185     EXPECT_TRUE(r2.intersects(r1));
 186 }
 187
 188 TEST(AddrRangeTest, IntersectsAddressWithin)
 189 {
 190     AddrRange r1(0x0, 0xF);
 191     AddrRange r2(0x1, 0xE);
 192
 193     EXPECT_TRUE(r1.intersects(r2));
 194     EXPECT_TRUE(r2.intersects(r1));
 195 }
 196
 197 TEST(AddrRangeTest, IntersectsPartialOverlap)
 198 {
 199     AddrRange r1(0x0F0, 0x0FF);
 200     AddrRange r2(0x0F5, 0xF00);
 201
 202     EXPECT_TRUE(r1.intersects(r2));
 203     EXPECT_TRUE(r2.intersects(r1));
 204 }
 205
 206 TEST(AddrRangeTest, IntersectsNoOverlap)
 207 {
 208     AddrRange r1(0x00, 0x10);
 209     AddrRange r2(0x11, 0xFF);
 210
 211     EXPECT_FALSE(r1.intersects(r2));
 212     EXPECT_FALSE(r2.intersects(r1));
 213 }
 214
 215 TEST(AddrRangeTest, IntersectsFirstLastAddressOverlap)
 216 {
 217     AddrRange r1(0x0, 0xF);
 218     AddrRange r2(0xF, 0xF0);
 219
 220     /*
 221      * The "end address" is not in the range. Therefore, if
 222      * r1.end() == r2.start(), the ranges do not intersect.
 223      */
 224     EXPECT_FALSE(r1.intersects(r2));
 225     EXPECT_FALSE(r2.intersects(r1));
 226 }
 227
 228 TEST(AddrRangeTest, isSubsetCompleteOverlap)
 229 {
 230     AddrRange r1(0x10, 0x20);
 231     AddrRange r2(0x10, 0x20);
 232
 233     EXPECT_TRUE(r1.isSubset(r2));
 234     EXPECT_TRUE(r2.isSubset(r1));
 235 }
 236
 237 TEST(AddrRangeTest, isSubsetNoOverlap)
 238 {
 239     AddrRange r1(0x10, 0x20);
 240     AddrRange r2(0x20, 0x22);
 241
 242     EXPECT_FALSE(r1.isSubset(r2));
 243     EXPECT_FALSE(r2.isSubset(r1));
 244 }
 245
 246 TEST(AddrRangeTest, isSubsetTrueSubset)
 247 {
 248     AddrRange r1(0x10, 0x20);
 249     AddrRange r2(0x15, 0x17);
 250
 251     EXPECT_TRUE(r2.isSubset(r1));
 252     EXPECT_FALSE(r1.isSubset(r2));
 253 }
 254
 255 TEST(AddrRangeTest, isSubsetPartialSubset)
 256 {
 257     AddrRange r1(0x20, 0x30);
 258     AddrRange r2(0x26, 0xF0);
 259
 260     EXPECT_FALSE(r1.isSubset(r2));
 261     EXPECT_FALSE(r2.isSubset(r1));
 262 }
 263
 264 TEST(AddrRangeTest, isSubsetInterleavedCompleteOverlap)
 265 {
 266     AddrRange r1(0x00, 0x100, {0x40}, 0);
 267     AddrRange r2(0x00, 0x40);
 268
 269     EXPECT_TRUE(r2.isSubset(r1));
 270 }
 271
 272 TEST(AddrRangeTest, isSubsetInterleavedNoOverlap)
 273 {
 274     AddrRange r1(0x00, 0x100, {0x40}, 1);
 275     AddrRange r2(0x00, 0x40);
 276
 277     EXPECT_FALSE(r2.isSubset(r1));
 278 }
 279
 280 TEST(AddrRangeTest, isSubsetInterleavedPartialOverlap)
 281 {
 282     AddrRange r1(0x00, 0x100, {0x40}, 0);
 283     AddrRange r2(0x10, 0x50);
 284
 285     EXPECT_FALSE(r2.isSubset(r1));
 286 }
 287
 288 TEST(AddrRangeTest, Contains)
 289 {
 290     AddrRange r(0xF0, 0xF5);
 291
 292     EXPECT_FALSE(r.contains(0xEF));
 293     EXPECT_TRUE(r.contains(0xF0));
 294     EXPECT_TRUE(r.contains(0xF1));
 295     EXPECT_TRUE(r.contains(0xF2));
 296     EXPECT_TRUE(r.contains(0xF3));
 297     EXPECT_TRUE(r.contains(0xF4));
 298     EXPECT_FALSE(r.contains(0xF5));
 299     EXPECT_FALSE(r.contains(0xF6));
 300 }
 301
 302 TEST(AddrRangeTest, ContainsInAnEmptyRange)
 303 {
 304     AddrRange r(0x1, 0x1);
 305
 306     EXPECT_FALSE(r.contains(0x1));
 307 }
 308
 309 TEST(AddrRangeTest, RemoveIntlvBits)
 310 {
 311     AddrRange r(0x01, 0x10);
 312
 313     /*
 314      * When there are no masks, AddrRange.removeIntlBits just returns the
 315      * address parameter.
 316      */
 317     Addr a(56);
 318     a = r.removeIntlvBits(a);
 319     EXPECT_EQ(56, a);
 320 }
 321
 322 TEST(AddrRangeTest, addIntlvBits)
 323 {
 324     AddrRange r(0x01, 0x10);
 325
 326     /*
 327      * As with AddrRange.removeIntlBits, when there are no masks,
 328      * AddrRange.addIntlvBits just returns the address parameter.
 329      */
 330     Addr a(56);
 331     a = r.addIntlvBits(a);
 332     EXPECT_EQ(56, a);
 333 }
 334
 335 TEST(AddrRangeTest, OffsetInRange)
 336 {
 337     AddrRange r(0x01, 0xF0);
 338     EXPECT_EQ(0x04, r.getOffset(0x5));
 339 }
 340
 341 TEST(AddrRangeTest, OffsetOutOfRangeAfter)
 342 {
 343     /*
 344      * If the address is less than the range, MaxAddr is returned.
 345      */
 346     AddrRange r(0x01, 0xF0);
 347     EXPECT_EQ(MaxAddr, r.getOffset(0xF0));
 348 }
 349
 350 TEST(AddrRangeTest, OffsetOutOfRangeBefore)
 351 {
 352     AddrRange r(0x05, 0xF0);
 353     EXPECT_EQ(MaxAddr, r.getOffset(0x04));
 354 }
 355
 356 /*
 357  * The following tests check the behavior of AddrRange when initialized with
 358  * a start and end address, as well as masks to distinguish interleaving bits.
 359  */
 360 TEST(AddrRangeTest, LsbInterleavingMask)
 361 {
 362     Addr start = 0x00;
 363     Addr end   = 0xFF;
 364     std::vector<Addr> masks;
 365     /*
 366      * The address is in range if the LSB is set, i.e. is the value is odd.
 367      */
 368     masks.push_back(1);
 369     uint8_t intlv_match = 1;
 370
 371     AddrRange r(start, end, masks, intlv_match);
 372     EXPECT_TRUE(r.valid());
 373     EXPECT_EQ(start, r.start());
 374     EXPECT_EQ(end, r.end());
 375     /*
 376      * With interleaving, it's assumed the size is equal to
 377      * start - end >> [number of masks].
 378      */
 379     EXPECT_EQ(0x7F, r.size());
 380     /*
 381      * The Granularity, the size of regions created by the interleaving bits,
 382      * which, in this case, is one.
 383      */
 384     EXPECT_EQ(1, r.granularity());
 385     EXPECT_TRUE(r.interleaved());
 386     EXPECT_EQ(ULL(2), r.stripes());
 387     EXPECT_EQ("[0:0xff] a[0]^\b=1", r.to_string());
 388 }
 389
 390 TEST(AddrRangeTest, TwoInterleavingMasks)
 391 {
 392     Addr start = 0x0000;
 393     Addr end   = 0xFFFF;
 394     std::vector<Addr> masks;
 395     /*
 396      * There are two marks, the two LSBs.
 397      */
 398     masks.push_back(1);
 399     masks.push_back((1 << 1));
 400     uint8_t intlv_match = (1 << 1) | 1;
 401
 402     AddrRange r(start, end, masks, intlv_match);
 403     EXPECT_TRUE(r.valid());
 404     EXPECT_EQ(start, r.start());
 405     EXPECT_EQ(end, r.end());
 406
 407     EXPECT_EQ(0x3FFF, r.size());
 408     EXPECT_TRUE(r.interleaved());
 409     EXPECT_EQ(ULL(4), r.stripes());
 410     EXPECT_EQ("[0:0xffff] a[0]^\b=1 a[1]^\b=1", r.to_string());
 411 }
 412
 413 TEST(AddrRangeTest, ComplexInterleavingMasks)
 414 {
 415     Addr start = 0x0000;
 416     Addr end   = 0xFFFF;
 417     std::vector<Addr> masks;
 418     masks.push_back((1 << 1) | 1);
 419     masks.push_back((ULL(1) << 63) | (ULL(1) << 62));
 420     uint8_t intlv_match = 0;
 421
 422     AddrRange r(start, end, masks, intlv_match);
 423     EXPECT_TRUE(r.valid());
 424     EXPECT_EQ(start, r.start());
 425     EXPECT_EQ(end, r.end());
 426
 427     EXPECT_EQ(0x3FFF, r.size());
 428     EXPECT_TRUE(r.interleaved());
 429     EXPECT_EQ(ULL(4), r.stripes());
 430     EXPECT_EQ("[0:0xffff] a[0]^a[1]^\b=0 a[62]^a[63]^\b=0", r.to_string());
 431 }
 432
 433 TEST(AddrRangeTest, InterleavingAddressesMergesWith)
 434 {
 435     Addr start1 = 0x0000;
 436     Addr end1   = 0xFFFF;
 437     std::vector<Addr> masks;
 438     masks.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 439     masks.push_back((1 << 2));
 440     uint8_t intlv_match1 = 0;
 441     AddrRange r1(start1, end1, masks, intlv_match1);
 442
 443     Addr start2 = 0x0000;
 444     Addr end2   = 0xFFFF;
 445     uint8_t intlv_match2 = 1; // intlv_match may differ.
 446     AddrRange r2(start2, end2, masks, intlv_match2);
 447
 448     EXPECT_TRUE(r1.mergesWith(r2));
 449     EXPECT_TRUE(r2.mergesWith(r1));
 450 }
 451
 452 TEST(AddrRangeTest, InterleavingAddressesDoNotMergeWith)
 453 {
 454     Addr start1 = 0x0000;
 455     Addr end1   = 0xFFFF;
 456     std::vector<Addr> masks1;
 457     masks1.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 458     masks1.push_back((1 << 2));
 459     uint8_t intlv_match1 = 0;
 460     AddrRange r1(start1, end1, masks1, intlv_match1);
 461
 462     Addr start2 = 0x0000;
 463     Addr end2   = 0xFFFF;
 464     std::vector<Addr> masks2;
 465     masks2.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 466     masks2.push_back((1 << 3)); // Different mask here.
 467     uint8_t intlv_match2 = 1; // intlv_match may differ.
 468     AddrRange r2(start2, end2, masks2, intlv_match2);
 469
 470     EXPECT_FALSE(r1.mergesWith(r2));
 471     EXPECT_FALSE(r2.mergesWith(r1));
 472 }
 473
 474 TEST(AddrRangeTest, InterleavingAddressesDoNotIntersect)
 475 {
 476     /*
 477      * Range 1: all the odd addresses between 0x0000 and 0xFFFF.
 478      */
 479     Addr start1 = 0x0000;
 480     Addr end1   = 0xFFFF;
 481     std::vector<Addr> masks1;
 482     masks1.push_back(1);
 483     uint8_t intlv_match1 = 1;
 484     AddrRange r1(start1, end1, masks1, intlv_match1);
 485
 486     /*
 487      * Range 2: all the even addresses between 0x0000 and 0xFFFF. These
 488      * addresses should thereby not intersect.
 489      */
 490     Addr start2 = 0x0000;
 491     Addr end2   = 0xFFFF;
 492     std::vector<Addr> masks2;
 493     masks2.push_back(1);
 494     uint8_t intv_match2 = 0;
 495     AddrRange r2(start2, end2, masks2, intv_match2);
 496
 497     EXPECT_FALSE(r1.intersects(r2));
 498     EXPECT_FALSE(r2.intersects(r1));
 499 }
 500
 501 TEST(AddrRangeTest, InterleavingAddressesIntersectsViaMerging)
 502 {
 503     Addr start1 = 0x0000;
 504     Addr end1   = 0xFFFF;
 505     std::vector<Addr> masks1;
 506     masks1.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 507     masks1.push_back((1 << 2));
 508     uint8_t intlv_match1 = 0;
 509     AddrRange r1(start1, end1, masks1, intlv_match1);
 510
 511     Addr start2 = 0x0000;
 512     Addr end2   = 0xFFFF;
 513     std::vector<Addr> masks2;
 514     masks2.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 515     masks2.push_back((1 << 2));
 516     uint8_t intlv_match2 = 0;
 517     AddrRange r2(start2, end2, masks2, intlv_match2);
 518
 519     EXPECT_TRUE(r1.intersects(r2));
 520     EXPECT_TRUE(r2.intersects(r1));
 521 }
 522
 523 TEST(AddrRangeTest, InterleavingAddressesDoesNotIntersectViaMerging)
 524 {
 525     Addr start1 = 0x0000;
 526     Addr end1   = 0xFFFF;
 527     std::vector<Addr> masks1;
 528     masks1.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 529     masks1.push_back((1 << 2));
 530     uint8_t intlv_match1 = 0;
 531     AddrRange r1(start1, end1, masks1, intlv_match1);
 532
 533     Addr start2 = 0x0000;
 534     Addr end2   = 0xFFFF;
 535     std::vector<Addr> masks2;
 536     masks2.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 537     masks2.push_back((1 << 2));
 538     /*
 539      * These addresses can merge, but their intlv_match values differ. They
 540      * therefore do not intersect.
 541      */
 542     uint8_t intlv_match2 = 1;
 543     AddrRange r2(start2, end2, masks2, intlv_match2);
 544
 545     EXPECT_FALSE(r1.intersects(r2));
 546     EXPECT_FALSE(r2.intersects(r1));
 547 }
 548
 549 /*
 550  * The following tests were created to test more complex cases where
 551  * interleaving addresses may intersect. However, the "intersects" function
 552  * does not cover all cases (a "Cannot test intersection..." exception will
 553  * be thrown outside of very simple checks to see if an intersection occurs).
 554  * The tests below accurately test whether two ranges intersect but, for now,
 555  * code has yet to be implemented to utilize these tests. They are therefore
 556  * disabled, but may be enabled at a later date if/when the "intersects"
 557  * function is enhanced.
 558  */
 559 TEST(AddrRangeTest, DISABLED_InterleavingAddressesIntersect)
 560 {
 561     /*
 562      * Range 1: all the odd addresses between 0x0000 and 0xFFFF.
 563      */
 564     Addr start1 = 0x0000;
 565     Addr end1   = 0xFFFF;
 566     std::vector<Addr> masks1;
 567     masks1.push_back(1);
 568     uint8_t intlv_match1 = 0;
 569     AddrRange r1(start1, end1, masks1, intlv_match1);
 570
 571     /*
 572      * Range 2: all the addresses divisible by 4 between 0x0000 and
 573      * 0xFFFF. These addresses should thereby intersect.
 574      */
 575     Addr start2 = 0x0000;
 576     Addr end2   = 0xFFFF;
 577     std::vector<Addr> masks2;
 578     masks2.push_back(1 << 2);
 579     uint8_t intlv_match2 = 1;
 580     AddrRange r2(start2, end2, masks2, intlv_match2);
 581
 582     EXPECT_TRUE(r1.intersects(r2));
 583     EXPECT_TRUE(r2.intersects(r1));
 584 }
 585
 586 TEST(AddrRangeTest, DISABLED_InterleavingAddressesIntersectsOnOneByteAddress)
 587 {
 588     /*
 589      * Range: all the odd addresses between 0x0000 and 0xFFFF.
 590      */
 591     Addr start = 0x0000;
 592     Addr end   = 0xFFFF;
 593     std::vector<Addr> masks;
 594     masks.push_back(1);
 595     uint8_t intlv_match = 1;
 596     AddrRange r1(start, end, masks, intlv_match);
 597
 598     AddrRange r2(0x0000, 0x0001);
 599
 600     EXPECT_FALSE(r1.intersects(r2));
 601     EXPECT_FALSE(r2.intersects(r1));
 602 }
 603
 604 TEST(AddrRangeTest,
 605     DISABLED_InterleavingAddressesDoesNotIntersectOnOneByteAddress)
 606 {
 607     /*
 608      * Range: all the odd addresses between 0x0000 and 0xFFFF.
 609      */
 610     Addr start = 0x0000;
 611     Addr end   = 0xFFFF;
 612     std::vector<Addr> masks;
 613     masks.push_back(1);
 614     uint8_t intlv_match = 1;
 615     AddrRange r1(start, end, masks, intlv_match);
 616
 617     AddrRange r2(0x0001, 0x0002);
 618
 619     EXPECT_TRUE(r1.intersects(r2));
 620     EXPECT_TRUE(r2.intersects(r1));
 621 }
 622
 623
 624 /*
 625  * The following three tests were created to test the addr_range.isSubset
 626  * function for Interleaving address ranges. However, for now, this
 627  * functionality has not been implemented. These tests are therefore disabled.
 628  */
 629 TEST(AddrRangeTest, DISABLED_InterleavingAddressIsSubset)
 630 {
 631     // Range 1: all the even addresses between 0x0000 and 0xFFFF.
 632     Addr start1 = 0x0000;
 633     Addr end1   = 0xFFFF;
 634     std::vector<Addr> masks1;
 635     masks1.push_back(1);
 636     uint8_t intlv_match1 = 0;
 637     AddrRange r1(start1, end1, masks1, intlv_match1);
 638
 639     // Range 2: all the even addresses between 0xF000 and 0x0FFF, this is
 640     // a subset of Range 1.
 641     Addr start2 = 0xF000;
 642     Addr end2   = 0x0FFF;
 643     std::vector<Addr> masks2;
 644     masks2.push_back(1);
 645     uint8_t intlv_match2 = 0;
 646     AddrRange r2(start2, end2, masks2, intlv_match2);
 647
 648     EXPECT_TRUE(r1.isSubset(r2));
 649     EXPECT_TRUE(r2.isSubset(r1));
 650 }
 651
 652 TEST(AddrRangeTest, DISABLED_InterleavingAddressIsNotSubset)
 653 {
 654     //Range 1: all the even addresses between 0x0000 and 0xFFFF.
 655     Addr start1 = 0x0000;
 656     Addr end1   = 0xFFFF;
 657     std::vector<Addr> masks1;
 658     masks1.push_back(1);
 659     uint8_t intlv_match1 = 0;
 660     AddrRange r1(start1, end1, masks1, intlv_match1);
 661
 662
 663     // Range 2: all the odd addresses between 0xF000 and 0x0FFF, this is
 664     //a subset of Range 1.
 665     Addr start2 = 0xF000;
 666     Addr end2   = 0x0FFF;
 667     std::vector<Addr> masks2;
 668     masks2.push_back(1);
 669     uint8_t intlv_match2 = 1;
 670     AddrRange r2(start2, end2, masks2, intlv_match2);
 671
 672     EXPECT_FALSE(r1.isSubset(r2));
 673     EXPECT_FALSE(r2.isSubset(r1));
 674 }
 675
 676 TEST(AddrRangeTest, DISABLED_InterleavingAddressContains)
 677 {
 678     /*
 679      * Range: all the address between 0x0 and 0xFF which have both the 1st
 680      * and 5th bits 1, or both are 0
 681      */
 682     Addr start = 0x00;
 683     Addr end   = 0xFF;
 684     std::vector<Addr> masks;
 685     masks.push_back((1 << 4) | 1);
 686     uint8_t intlv_match = 0;
 687     AddrRange r(start, end, masks, intlv_match);
 688
 689     for (Addr addr = start; addr < end; addr++) {
 690         if (((addr & 1) && ((1 << 4) & addr)) || // addr[0] && addr[4]
 691             (!(addr & 1) && !((1 << 4) & addr))) { //!addr[0] && !addr[4]
 692             EXPECT_TRUE(r.contains(addr));
 693         } else {
 694             EXPECT_FALSE(r.contains(addr));
 695         }
 696     }
 697 }
 698
 699 TEST(AddrRangeTest, InterleavingAddressAddRemoveInterlvBits)
 700 {
 701     Addr start = 0x00000;
 702     Addr end   = 0x10000;
 703     std::vector<Addr> masks;
 704     masks.push_back(1);
 705     uint8_t intlv_match = 1;
 706     AddrRange r(start, end, masks, intlv_match);
 707
 708     Addr input = 0xFFFF;
 709     Addr output = r.removeIntlvBits(input);
 710
 711     /*
 712      * The removeIntlvBits function removes the LSB from each mask from the
 713      * input address. For example, two masks:
 714      * 00000001 and,
 715      * 10000100
 716      * with an input address of:
 717      * 10101010
 718      *
 719      * we would remove bit at position 0, and at position 2, resulting in:
 720      * 00101011
 721      *
 722      * In this test there is is one mask, with a LSB at position 0.
 723      * Therefore, removing the interleaving bits is equivilant to bitshifting
 724      * the input to the right.
 725      */
 726     EXPECT_EQ(input >> 1, output);
 727
 728     /*
 729      * The addIntlvBits function will re-insert bits at the removed locations
 730      */
 731     EXPECT_EQ(input, r.addIntlvBits(output));
 732 }
 733
 734 TEST(AddrRangeTest, InterleavingAddressAddRemoveInterlvBitsTwoMasks)
 735 {
 736     Addr start = 0x00000;
 737     Addr end   = 0x10000;
 738     std::vector<Addr> masks;
 739     masks.push_back((1 << 3) | (1 << 2) | (1 << 1) | 1);
 740     masks.push_back((1 << 11) | (1 << 10) | (1 << 9) | (1 << 8));
 741     uint8_t intlv_match = 1;
 742     AddrRange r(start, end, masks, intlv_match);
 743
 744     Addr input = (1 << 9) | (1 << 8) | 1;
 745     /*
 746      * (1 << 8) and 1 are interleaving bits to be removed.
 747      */
 748     Addr output = r.removeIntlvBits(input);
 749
 750     /*
 751      * The bit, formally at position 9, is now at 7.
 752      */
 753     EXPECT_EQ((1 << 7), output);
 754
 755     /*
 756      * Re-adding the interleaving.
 757      */
 758     EXPECT_EQ(input, r.addIntlvBits(output));
 759 }
 760
 761 TEST(AddrRangeTest, AddRemoveInterleavBitsAcrossRange)
 762 {
 763     /*
 764      * This purpose of this test is to ensure that removing then adding
 765      * interleaving bits has no net effect.
 766      * E.g.:
 767      * addr_range.addIntlvBits(add_range.removeIntlvBits(an_address)) should
 768      * always return an_address.
 769      */
 770     Addr start = 0x00000;
 771     Addr end   = 0x10000;
 772     std::vector<Addr> masks;
 773     masks.push_back(1 << 2);
 774     masks.push_back(1 << 3);
 775     masks.push_back(1 << 16);
 776     masks.push_back(1 << 30);
 777     uint8_t intlv_match = 0xF;
 778     AddrRange r(start, end, masks, intlv_match);
 779
 780     for (Addr i = 0; i < 0xFFF; i++) {
 781         Addr removedBits = r.removeIntlvBits(i);
 782         /*
 783          * As intlv_match = 0xF, all the interleaved bits should be set.
 784          */
 785         EXPECT_EQ(i | (1 << 2) | (1 << 3) | (1 << 16) | (1 << 30),
 786                   r.addIntlvBits(removedBits));
 787     }
 788 }
 789
 790 TEST(AddrRangeTest, InterleavingAddressesGetOffset)
 791 {
 792     Addr start = 0x0002;
 793     Addr end   = 0xFFFF;
 794     std::vector<Addr> masks;
 795     masks.push_back((1 << 4) | (1 << 2));
 796     uint8_t intlv_match = 0;
 797     AddrRange r(start, end, masks, intlv_match);
 798
 799     Addr value = ((1 << 10) | (1 << 9) | (1 <<  8) | (1 << 2) | (1 << 1) | 1);
 800     Addr value_interleaving_bits_removed =
 801                             ((1 << 9) | (1 << 8) | (1 << 7) | (1 << 1) | 1);
 802
 803     Addr expected_output = value_interleaving_bits_removed - start;
 804
 805     EXPECT_EQ(expected_output, r.getOffset(value));
 806 }
 807
 808 TEST(AddrRangeTest, InterleavingLessThanStartEquals)
 809 {
 810     Addr start1 = 0x0000FFFF;
 811     Addr end1   = 0xFFFF0000;
 812     std::vector<Addr> masks1;
 813     masks1.push_back((1 << 4) | (1 << 2));
 814     uint8_t intlv_match1 = 0;
 815     AddrRange r1(start1, end1, masks1, intlv_match1);
 816
 817     Addr start2 = 0x0000FFFF;
 818     Addr end2   = 0x000F0000;
 819     std::vector<Addr> masks2;
 820     masks2.push_back((1 << 4) | (1 << 2));
 821     masks2.push_back((1 << 10));
 822     uint8_t intlv_match2 = 2;
 823     AddrRange r2(start2, end2, masks2, intlv_match2);
 824
 825     /*
 826      * When The start addresses are equal, the intlv_match values are
 827      * compared.
 828      */
 829     EXPECT_TRUE(r1 < r2);
 830     EXPECT_FALSE(r2 < r1);
 831 }
 832
 833 TEST(AddrRangeTest, InterleavingLessThanStartNotEquals)
 834 {
 835     Addr start1 = 0x0000FFFF;
 836     Addr end1   = 0xFFFF0000;
 837     std::vector<Addr> masks1;
 838     masks1.push_back((1 << 4) | (1 << 2));
 839     uint8_t intlv_match1 = 0;
 840     AddrRange r1(start1, end1, masks1, intlv_match1);
 841
 842     Addr start2 = 0x0000FFFE;
 843     Addr end2   = 0x000F0000;
 844     std::vector<Addr> masks2;
 845     masks2.push_back((1 << 4) | (1 << 2));
 846     masks2.push_back((1 << 10));
 847     uint8_t intlv_match2 = 2;
 848     AddrRange r2(start2, end2, masks2, intlv_match2);
 849
 850     EXPECT_TRUE(r2 < r1);
 851     EXPECT_FALSE(r1 < r2);
 852 }
 853
 854 TEST(AddrRangeTest, InterleavingEqualTo)
 855 {
 856     Addr start1 = 0x0000FFFF;
 857     Addr end1   = 0xFFFF0000;
 858     std::vector<Addr> masks1;
 859     masks1.push_back((1 << 4) | (1 << 2));
 860     uint8_t intlv_match1 = 0;
 861     AddrRange r1(start1, end1, masks1, intlv_match1);
 862
 863     Addr start2 = 0x0000FFFF;
 864     Addr end2   = 0xFFFF0000;
 865     std::vector<Addr> masks2;
 866     masks2.push_back((1 << 4) | (1 << 2));
 867     uint8_t intlv_match2 = 0;
 868     AddrRange r2(start2, end2, masks2, intlv_match2);
 869
 870     EXPECT_TRUE(r1 == r2);
 871 }
 872
 873 TEST(AddrRangeTest, InterleavingNotEqualTo)
 874 {
 875     Addr start1 = 0x0000FFFF;
 876     Addr end1   = 0xFFFF0000;
 877     std::vector<Addr> masks1;
 878     masks1.push_back((1 << 4) | (1 << 2));
 879     uint8_t intlv_match1 = 0;
 880     AddrRange r1(start1, end1, masks1, intlv_match1);
 881
 882     Addr start2 = 0x0000FFFF;
 883     Addr end2   = 0xFFFF0000;
 884     std::vector<Addr> masks2;
 885     masks2.push_back((1 << 4) | (1 << 2));
 886     masks2.push_back((1 << 10));
 887     uint8_t intlv_match2 = 2;
 888     AddrRange r2(start2, end2, masks2, intlv_match2);
 889
 890     /*
 891      * These ranges are not equal due to having different masks.
 892      */
 893     EXPECT_FALSE(r1 == r2);
 894 }
 895
 896 /*
 897  * The AddrRange(std::vector<AddrRange>) constructor "merges" the interleaving
 898  * address ranges. It should be noted that this constructor simply checks that
 899  * these interleaving addresses can be merged then creates a new address from
 900  * the start and end addresses of the first address range in the vector.
 901  */
 902 TEST(AddrRangeTest, MergingInterleavingAddressRanges)
 903 {
 904     Addr start1 = 0x0000;
 905     Addr end1   = 0xFFFF;
 906     std::vector<Addr> masks1;
 907     masks1.push_back((1 << 4) | (1 << 2));
 908     uint8_t intlv_match1 = 0;
 909     AddrRange r1(start1, end1, masks1, intlv_match1);
 910
 911     Addr start2 = 0x0000;
 912     Addr end2   = 0xFFFF;
 913     std::vector<Addr> masks2;
 914     masks2.push_back((1 << 4) | (1 << 2));
 915     uint8_t intlv_match2 = 1;
 916     AddrRange r2(start2, end2, masks2, intlv_match2);
 917
 918     std::vector<AddrRange> to_merge;
 919     to_merge.push_back(r1);
 920     to_merge.push_back(r2);
 921
 922     AddrRange output(to_merge);
 923
 924     EXPECT_EQ(0x0000, output.start());
 925     EXPECT_EQ(0xFFFF, output.end());
 926     EXPECT_FALSE(output.interleaved());
 927 }
 928
 929 TEST(AddrRangeTest, MergingInterleavingAddressRangesOneRange)
 930 {
 931     /*
 932      * In the case where there is just one range in the vector, the merged
 933      * address range is equal to that range.
 934      */
 935     Addr start = 0x0000;
 936     Addr end   = 0xFFFF;
 937     std::vector<Addr> masks;
 938     masks.push_back((1 << 4) | (1 << 2));
 939     uint8_t intlv_match = 0;
 940     AddrRange r(start, end, masks, intlv_match);
 941
 942     std::vector<AddrRange> to_merge;
 943     to_merge.push_back(r);
 944
 945     AddrRange output(to_merge);
 946
 947     EXPECT_EQ(r, output);
 948 }
 949
 950 /*
 951  * The following tests verify the soundness of the "legacy constructor",
 952  * AddrRange(Addr, Addr, uint8_t, uint8_t, uint8_t, uint8_t).
 953  *
 954  * The address is assumed to contain two ranges; the interleaving bits, and
 955  * the xor bits. The first two arguments of this constructor specify the
 956  * start and end addresses. The third argument specifies the MSB of the
 957  * interleaving bits. The fourth argument specifies the MSB of the xor bits.
 958  * The firth argument specifies the size (in bits) of the xor and interleaving
 959  * bits. These cannot overlap. The sixth argument specifies the value the
 960  * XORing of the xor and interleaving bits should equal to be considered in
 961  * range.
 962  *
 963  * This constructor does a lot of complex translation to migrate this
 964  * constructor to the masks/intlv_match format.
 965  */
 966 TEST(AddrRangeTest, LegacyConstructorNoInterleaving)
 967 {
 968     /*
 969      * This constructor should create a range with no interleaving.
 970      */
 971     AddrRange range(0x0000, 0xFFFF, 0, 0, 0 ,0);
 972     AddrRange expected(0x0000, 0xFFFF);
 973
 974     EXPECT_EQ(expected, range);
 975 }
 976
 977 TEST(AddrRangeTest, LegacyConstructorOneBitMask)
 978 {
 979     /*
 980      * In this test, the LSB of the address determines whether an address is
 981      * in range. If even, it's in range, if not, it's out of range. the XOR
 982      * bit range is not used.
 983      */
 984     AddrRange range(0x00000000, 0xFFFFFFFF, 0, 0, 1, 0);
 985
 986     std::vector<Addr> masks;
 987     masks.push_back(1);
 988     AddrRange expected(0x00000000, 0xFFFFFFFF, masks, 0);
 989
 990     EXPECT_TRUE(expected == range);
 991 }
 992
 993 TEST(AddrRangeTest, LegacyConstructorTwoBitMask)
 994 {
 995     /*
 996      * In this test, the two LSBs of the address determines whether an address
 997      * is in range. If the two are set, the address is in range. The XOR bit
 998      * range is not used.
 999      */
1000     AddrRange range(0x00000000, 0xFFFFFFFF, 1, 0, 2, 3);
1001
1002     std::vector<Addr> masks;
1003     masks.push_back(1);
1004     masks.push_back((1 << 1));
1005     AddrRange expected(0x00000000, 0xFFFFFFFF, masks, 3);
1006
1007     EXPECT_TRUE(expected == range);
1008 }
1009
1010 TEST(AddrRangeTest, LegacyConstructorTwoBitMaskWithXOR)
1011 {
1012     /*
1013      * In this test, the two LSBs of the address determine wether an address
1014      * is in range. They are XORed to the 10th and 11th bits in the address.
1015      * If XORed value is equal to 3, then the address is in range.
1016      */
1017
1018     AddrRange range(0x00000000, 0xFFFFFFFF, 1, 11, 2,  3);
1019
1020     /*
1021      * The easiest way to ensure this range is correct is to iterate throguh
1022      * the address range and ensure the correct set of addresses are contained
1023      * within the range.
1024      *
1025      * We start with the xor_mask: a mask to select the 10th and 11th bits.
1026      */
1027     Addr xor_mask = (1 << 11) | (1 << 10);
1028     for (Addr i = 0; i < 0x0000FFFF; i++) {
1029         // Get xor bits.
1030         Addr xor_value = (xor_mask & i) >> 10;
1031         /* If the XOR of xor_bits and the intlv bits (the 0th and 1st bits) is
1032          * equal to intlv_match (3, i.e., the 0th and 1st bit is set),then the
1033          * address is within range.
1034          */
1035         if (((xor_value ^ i) & 3) == 3) {
1036             EXPECT_TRUE(range.contains(i));
1037         } else {
1038             EXPECT_FALSE(range.contains(i));
1039         }
1040     }
1041 }
1042
1043 /*
1044  * addr_range.hh contains some convenience constructors. The following tests
1045  * verify they construct AddrRange correctly.
1046  */
1047 TEST(AddrRangeTest, RangeExConstruction)
1048 {
1049     AddrRange r = RangeEx(0x6, 0xE);
1050     EXPECT_EQ(0x6, r.start());
1051     EXPECT_EQ(0xE, r.end());
1052 }
1053
1054 TEST(AddrRangeTest, RangeInConstruction)
1055 {
1056     AddrRange r = RangeIn(0x6, 0xE);
1057     EXPECT_EQ(0x6, r.start());
1058     EXPECT_EQ(0xF, r.end());
1059 }
1060
1061 TEST(AddrRangeTest, RangeSizeConstruction){
1062     AddrRange r = RangeSize(0x5, 5);
1063     EXPECT_EQ(0x5, r.start());
1064     EXPECT_EQ(0xA, r.end());
1065 }