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, Contains)
 265 {
 266     AddrRange r(0xF0, 0xF5);
 267
 268     EXPECT_FALSE(r.contains(0xEF));
 269     EXPECT_TRUE(r.contains(0xF0));
 270     EXPECT_TRUE(r.contains(0xF1));
 271     EXPECT_TRUE(r.contains(0xF2));
 272     EXPECT_TRUE(r.contains(0xF3));
 273     EXPECT_TRUE(r.contains(0xF4));
 274     EXPECT_FALSE(r.contains(0xF5));
 275     EXPECT_FALSE(r.contains(0xF6));
 276 }
 277
 278 TEST(AddrRangeTest, ContainsInAnEmptyRange)
 279 {
 280     AddrRange r(0x1, 0x1);
 281
 282     EXPECT_FALSE(r.contains(0x1));
 283 }
 284
 285 TEST(AddrRangeTest, RemoveIntlvBits)
 286 {
 287     AddrRange r(0x01, 0x10);
 288
 289     /*
 290      * When there are no masks, AddrRange.removeIntlBits just returns the
 291      * address parameter.
 292      */
 293     Addr a(56);
 294     a = r.removeIntlvBits(a);
 295     EXPECT_EQ(56, a);
 296 }
 297
 298 TEST(AddrRangeTest, addIntlvBits)
 299 {
 300     AddrRange r(0x01, 0x10);
 301
 302     /*
 303      * As with AddrRange.removeIntlBits, when there are no masks,
 304      * AddrRange.addIntlvBits just returns the address parameter.
 305      */
 306     Addr a(56);
 307     a = r.addIntlvBits(a);
 308     EXPECT_EQ(56, a);
 309 }
 310
 311 TEST(AddrRangeTest, OffsetInRange)
 312 {
 313     AddrRange r(0x01, 0xF0);
 314     EXPECT_EQ(0x04, r.getOffset(0x5));
 315 }
 316
 317 TEST(AddrRangeTest, OffsetOutOfRangeAfter)
 318 {
 319     /*
 320      * If the address is less than the range, MaxAddr is returned.
 321      */
 322     AddrRange r(0x01, 0xF0);
 323     EXPECT_EQ(MaxAddr, r.getOffset(0xF0));
 324 }
 325
 326 TEST(AddrRangeTest, OffsetOutOfRangeBefore)
 327 {
 328     AddrRange r(0x05, 0xF0);
 329     EXPECT_EQ(MaxAddr, r.getOffset(0x04));
 330 }
 331
 332 /*
 333  * The following tests check the behavior of AddrRange when initialized with
 334  * a start and end address, as well as masks to distinguish interleaving bits.
 335  */
 336 TEST(AddrRangeTest, LsbInterleavingMask)
 337 {
 338     Addr start = 0x00;
 339     Addr end   = 0xFF;
 340     std::vector<Addr> masks;
 341     /*
 342      * The address is in range if the LSB is set, i.e. is the value is odd.
 343      */
 344     masks.push_back(1);
 345     uint8_t intlv_match = 1;
 346
 347     AddrRange r(start, end, masks, intlv_match);
 348     EXPECT_TRUE(r.valid());
 349     EXPECT_EQ(start, r.start());
 350     EXPECT_EQ(end, r.end());
 351     /*
 352      * With interleaving, it's assumed the size is equal to
 353      * start - end >> [number of masks].
 354      */
 355     EXPECT_EQ(0x7F, r.size());
 356     /*
 357      * The Granularity, the size of regions created by the interleaving bits,
 358      * which, in this case, is one.
 359      */
 360     EXPECT_EQ(1, r.granularity());
 361     EXPECT_TRUE(r.interleaved());
 362     EXPECT_EQ(ULL(2), r.stripes());
 363     EXPECT_EQ("[0:0xff] a[0]^\b=1", r.to_string());
 364 }
 365
 366 TEST(AddrRangeTest, TwoInterleavingMasks)
 367 {
 368     Addr start = 0x0000;
 369     Addr end   = 0xFFFF;
 370     std::vector<Addr> masks;
 371     /*
 372      * There are two marks, the two LSBs.
 373      */
 374     masks.push_back(1);
 375     masks.push_back((1 << 1));
 376     uint8_t intlv_match = (1 << 1) | 1;
 377
 378     AddrRange r(start, end, masks, intlv_match);
 379     EXPECT_TRUE(r.valid());
 380     EXPECT_EQ(start, r.start());
 381     EXPECT_EQ(end, r.end());
 382
 383     EXPECT_EQ(0x3FFF, r.size());
 384     EXPECT_TRUE(r.interleaved());
 385     EXPECT_EQ(ULL(4), r.stripes());
 386     EXPECT_EQ("[0:0xffff] a[0]^\b=1 a[1]^\b=1", r.to_string());
 387 }
 388
 389 TEST(AddrRangeTest, ComplexInterleavingMasks)
 390 {
 391     Addr start = 0x0000;
 392     Addr end   = 0xFFFF;
 393     std::vector<Addr> masks;
 394     masks.push_back((1 << 1) | 1);
 395     masks.push_back((ULL(1) << 63) | (ULL(1) << 62));
 396     uint8_t intlv_match = 0;
 397
 398     AddrRange r(start, end, masks, intlv_match);
 399     EXPECT_TRUE(r.valid());
 400     EXPECT_EQ(start, r.start());
 401     EXPECT_EQ(end, r.end());
 402
 403     EXPECT_EQ(0x3FFF, r.size());
 404     EXPECT_TRUE(r.interleaved());
 405     EXPECT_EQ(ULL(4), r.stripes());
 406     EXPECT_EQ("[0:0xffff] a[0]^a[1]^\b=0 a[62]^a[63]^\b=0", r.to_string());
 407 }
 408
 409 TEST(AddrRangeTest, InterleavingAddressesMergesWith)
 410 {
 411     Addr start1 = 0x0000;
 412     Addr end1   = 0xFFFF;
 413     std::vector<Addr> masks;
 414     masks.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 415     masks.push_back((1 << 2));
 416     uint8_t intlv_match1 = 0;
 417     AddrRange r1(start1, end1, masks, intlv_match1);
 418
 419     Addr start2 = 0x0000;
 420     Addr end2   = 0xFFFF;
 421     uint8_t intlv_match2 = 1; // intlv_match may differ.
 422     AddrRange r2(start2, end2, masks, intlv_match2);
 423
 424     EXPECT_TRUE(r1.mergesWith(r2));
 425     EXPECT_TRUE(r2.mergesWith(r1));
 426 }
 427
 428 TEST(AddrRangeTest, InterleavingAddressesDoNotMergeWith)
 429 {
 430     Addr start1 = 0x0000;
 431     Addr end1   = 0xFFFF;
 432     std::vector<Addr> masks1;
 433     masks1.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 434     masks1.push_back((1 << 2));
 435     uint8_t intlv_match1 = 0;
 436     AddrRange r1(start1, end1, masks1, intlv_match1);
 437
 438     Addr start2 = 0x0000;
 439     Addr end2   = 0xFFFF;
 440     std::vector<Addr> masks2;
 441     masks2.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 442     masks2.push_back((1 << 3)); // Different mask here.
 443     uint8_t intlv_match2 = 1; // intlv_match may differ.
 444     AddrRange r2(start2, end2, masks2, intlv_match2);
 445
 446     EXPECT_FALSE(r1.mergesWith(r2));
 447     EXPECT_FALSE(r2.mergesWith(r1));
 448 }
 449
 450 TEST(AddrRangeTest, InterleavingAddressesDoNotIntersect)
 451 {
 452     /*
 453      * Range 1: all the odd addresses between 0x0000 and 0xFFFF.
 454      */
 455     Addr start1 = 0x0000;
 456     Addr end1   = 0xFFFF;
 457     std::vector<Addr> masks1;
 458     masks1.push_back(1);
 459     uint8_t intlv_match1 = 1;
 460     AddrRange r1(start1, end1, masks1, intlv_match1);
 461
 462     /*
 463      * Range 2: all the even addresses between 0x0000 and 0xFFFF. These
 464      * addresses should thereby not intersect.
 465      */
 466     Addr start2 = 0x0000;
 467     Addr end2   = 0xFFFF;
 468     std::vector<Addr> masks2;
 469     masks2.push_back(1);
 470     uint8_t intv_match2 = 0;
 471     AddrRange r2(start2, end2, masks2, intv_match2);
 472
 473     EXPECT_FALSE(r1.intersects(r2));
 474     EXPECT_FALSE(r2.intersects(r1));
 475 }
 476
 477 TEST(AddrRangeTest, InterleavingAddressesIntersectsViaMerging)
 478 {
 479     Addr start1 = 0x0000;
 480     Addr end1   = 0xFFFF;
 481     std::vector<Addr> masks1;
 482     masks1.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 483     masks1.push_back((1 << 2));
 484     uint8_t intlv_match1 = 0;
 485     AddrRange r1(start1, end1, masks1, intlv_match1);
 486
 487     Addr start2 = 0x0000;
 488     Addr end2   = 0xFFFF;
 489     std::vector<Addr> masks2;
 490     masks2.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 491     masks2.push_back((1 << 2));
 492     uint8_t intlv_match2 = 0;
 493     AddrRange r2(start2, end2, masks2, intlv_match2);
 494
 495     EXPECT_TRUE(r1.intersects(r2));
 496     EXPECT_TRUE(r2.intersects(r1));
 497 }
 498
 499 TEST(AddrRangeTest, InterleavingAddressesDoesNotIntersectViaMerging)
 500 {
 501     Addr start1 = 0x0000;
 502     Addr end1   = 0xFFFF;
 503     std::vector<Addr> masks1;
 504     masks1.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 505     masks1.push_back((1 << 2));
 506     uint8_t intlv_match1 = 0;
 507     AddrRange r1(start1, end1, masks1, intlv_match1);
 508
 509     Addr start2 = 0x0000;
 510     Addr end2   = 0xFFFF;
 511     std::vector<Addr> masks2;
 512     masks2.push_back((1 << 29) | (1 << 20) | (1 << 10) | 1);
 513     masks2.push_back((1 << 2));
 514     /*
 515      * These addresses can merge, but their intlv_match values differ. They
 516      * therefore do not intersect.
 517      */
 518     uint8_t intlv_match2 = 1;
 519     AddrRange r2(start2, end2, masks2, intlv_match2);
 520
 521     EXPECT_FALSE(r1.intersects(r2));
 522     EXPECT_FALSE(r2.intersects(r1));
 523 }
 524
 525 /*
 526  * The following tests were created to test more complex cases where
 527  * interleaving addresses may intersect. However, the "intersects" function
 528  * does not cover all cases (a "Cannot test intersection..." exception will
 529  * be thrown outside of very simple checks to see if an intersection occurs).
 530  * The tests below accurately test whether two ranges intersect but, for now,
 531  * code has yet to be implemented to utilize these tests. They are therefore
 532  * disabled, but may be enabled at a later date if/when the "intersects"
 533  * function is enhanced.
 534  */
 535 TEST(AddrRangeTest, DISABLED_InterleavingAddressesIntersect)
 536 {
 537     /*
 538      * Range 1: all the odd addresses between 0x0000 and 0xFFFF.
 539      */
 540     Addr start1 = 0x0000;
 541     Addr end1   = 0xFFFF;
 542     std::vector<Addr> masks1;
 543     masks1.push_back(1);
 544     uint8_t intlv_match1 = 0;
 545     AddrRange r1(start1, end1, masks1, intlv_match1);
 546
 547     /*
 548      * Range 2: all the addresses divisible by 4 between 0x0000 and
 549      * 0xFFFF. These addresses should thereby intersect.
 550      */
 551     Addr start2 = 0x0000;
 552     Addr end2   = 0xFFFF;
 553     std::vector<Addr> masks2;
 554     masks2.push_back(1 << 2);
 555     uint8_t intlv_match2 = 1;
 556     AddrRange r2(start2, end2, masks2, intlv_match2);
 557
 558     EXPECT_TRUE(r1.intersects(r2));
 559     EXPECT_TRUE(r2.intersects(r1));
 560 }
 561
 562 TEST(AddrRangeTest, DISABLED_InterleavingAddressesIntersectsOnOneByteAddress)
 563 {
 564     /*
 565      * Range: all the odd addresses between 0x0000 and 0xFFFF.
 566      */
 567     Addr start = 0x0000;
 568     Addr end   = 0xFFFF;
 569     std::vector<Addr> masks;
 570     masks.push_back(1);
 571     uint8_t intlv_match = 1;
 572     AddrRange r1(start, end, masks, intlv_match);
 573
 574     AddrRange r2(0x0000, 0x0001);
 575
 576     EXPECT_FALSE(r1.intersects(r2));
 577     EXPECT_FALSE(r2.intersects(r1));
 578 }
 579
 580 TEST(AddrRangeTest,
 581     DISABLED_InterleavingAddressesDoesNotIntersectOnOneByteAddress)
 582 {
 583     /*
 584      * Range: all the odd addresses between 0x0000 and 0xFFFF.
 585      */
 586     Addr start = 0x0000;
 587     Addr end   = 0xFFFF;
 588     std::vector<Addr> masks;
 589     masks.push_back(1);
 590     uint8_t intlv_match = 1;
 591     AddrRange r1(start, end, masks, intlv_match);
 592
 593     AddrRange r2(0x0001, 0x0002);
 594
 595     EXPECT_TRUE(r1.intersects(r2));
 596     EXPECT_TRUE(r2.intersects(r1));
 597 }
 598
 599
 600 /*
 601  * The following three tests were created to test the addr_range.isSubset
 602  * function for Interleaving address ranges. However, for now, this
 603  * functionality has not been implemented. These tests are therefore disabled.
 604  */
 605 TEST(AddrRangeTest, DISABLED_InterleavingAddressIsSubset)
 606 {
 607     // Range 1: all the even addresses between 0x0000 and 0xFFFF.
 608     Addr start1 = 0x0000;
 609     Addr end1   = 0xFFFF;
 610     std::vector<Addr> masks1;
 611     masks1.push_back(1);
 612     uint8_t intlv_match1 = 0;
 613     AddrRange r1(start1, end1, masks1, intlv_match1);
 614
 615     // Range 2: all the even addresses between 0xF000 and 0x0FFF, this is
 616     // a subset of Range 1.
 617     Addr start2 = 0xF000;
 618     Addr end2   = 0x0FFF;
 619     std::vector<Addr> masks2;
 620     masks2.push_back(1);
 621     uint8_t intlv_match2 = 0;
 622     AddrRange r2(start2, end2, masks2, intlv_match2);
 623
 624     EXPECT_TRUE(r1.isSubset(r2));
 625     EXPECT_TRUE(r2.isSubset(r1));
 626 }
 627
 628 TEST(AddrRangeTest, DISABLED_InterleavingAddressIsNotSubset)
 629 {
 630     //Range 1: all the even addresses between 0x0000 and 0xFFFF.
 631     Addr start1 = 0x0000;
 632     Addr end1   = 0xFFFF;
 633     std::vector<Addr> masks1;
 634     masks1.push_back(1);
 635     uint8_t intlv_match1 = 0;
 636     AddrRange r1(start1, end1, masks1, intlv_match1);
 637
 638
 639     // Range 2: all the odd 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 = 1;
 646     AddrRange r2(start2, end2, masks2, intlv_match2);
 647
 648     EXPECT_FALSE(r1.isSubset(r2));
 649     EXPECT_FALSE(r2.isSubset(r1));
 650 }
 651
 652 TEST(AddrRangeTest, DISABLED_InterleavingAddressContains)
 653 {
 654     /*
 655      * Range: all the address between 0x0 and 0xFF which have both the 1st
 656      * and 5th bits 1, or both are 0
 657      */
 658     Addr start = 0x00;
 659     Addr end   = 0xFF;
 660     std::vector<Addr> masks;
 661     masks.push_back((1 << 4) | 1);
 662     uint8_t intlv_match = 0;
 663     AddrRange r(start, end, masks, intlv_match);
 664
 665     for (Addr addr = start; addr < end; addr++) {
 666         if (((addr & 1) && ((1 << 4) & addr)) || // addr[0] && addr[4]
 667             (!(addr & 1) && !((1 << 4) & addr))) { //!addr[0] && !addr[4]
 668             EXPECT_TRUE(r.contains(addr));
 669         } else {
 670             EXPECT_FALSE(r.contains(addr));
 671         }
 672     }
 673 }
 674
 675 TEST(AddrRangeTest, InterleavingAddressAddRemoveInterlvBits)
 676 {
 677     Addr start = 0x00000;
 678     Addr end   = 0x10000;
 679     std::vector<Addr> masks;
 680     masks.push_back(1);
 681     uint8_t intlv_match = 1;
 682     AddrRange r(start, end, masks, intlv_match);
 683
 684     Addr input = 0xFFFF;
 685     Addr output = r.removeIntlvBits(input);
 686
 687     /*
 688      * The removeIntlvBits function removes the LSB from each mask from the
 689      * input address. For example, two masks:
 690      * 00000001 and,
 691      * 10000100
 692      * with an input address of:
 693      * 10101010
 694      *
 695      * we would remove bit at position 0, and at position 2, resulting in:
 696      * 00101011
 697      *
 698      * In this test there is is one mask, with a LSB at position 0.
 699      * Therefore, removing the interleaving bits is equivilant to bitshifting
 700      * the input to the right.
 701      */
 702     EXPECT_EQ(input >> 1, output);
 703
 704     /*
 705      * The addIntlvBits function will re-insert bits at the removed locations
 706      */
 707     EXPECT_EQ(input, r.addIntlvBits(output));
 708 }
 709
 710 TEST(AddrRangeTest, InterleavingAddressAddRemoveInterlvBitsTwoMasks)
 711 {
 712     Addr start = 0x00000;
 713     Addr end   = 0x10000;
 714     std::vector<Addr> masks;
 715     masks.push_back((1 << 3) | (1 << 2) | (1 << 1) | 1);
 716     masks.push_back((1 << 11) | (1 << 10) | (1 << 9) | (1 << 8));
 717     uint8_t intlv_match = 1;
 718     AddrRange r(start, end, masks, intlv_match);
 719
 720     Addr input = (1 << 9) | (1 << 8) | 1;
 721     /*
 722      * (1 << 8) and 1 are interleaving bits to be removed.
 723      */
 724     Addr output = r.removeIntlvBits(input);
 725
 726     /*
 727      * The bit, formally at position 9, is now at 7.
 728      */
 729     EXPECT_EQ((1 << 7), output);
 730
 731     /*
 732      * Re-adding the interleaving.
 733      */
 734     EXPECT_EQ(input, r.addIntlvBits(output));
 735 }
 736
 737 TEST(AddrRangeTest, AddRemoveInterleavBitsAcrossRange)
 738 {
 739     /*
 740      * This purpose of this test is to ensure that removing then adding
 741      * interleaving bits has no net effect.
 742      * E.g.:
 743      * addr_range.addIntlvBits(add_range.removeIntlvBits(an_address)) should
 744      * always return an_address.
 745      */
 746     Addr start = 0x00000;
 747     Addr end   = 0x10000;
 748     std::vector<Addr> masks;
 749     masks.push_back(1 << 2);
 750     masks.push_back(1 << 3);
 751     masks.push_back(1 << 16);
 752     masks.push_back(1 << 30);
 753     uint8_t intlv_match = 0xF;
 754     AddrRange r(start, end, masks, intlv_match);
 755
 756     for (Addr i = 0; i < 0xFFF; i++) {
 757         Addr removedBits = r.removeIntlvBits(i);
 758         /*
 759          * As intlv_match = 0xF, all the interleaved bits should be set.
 760          */
 761         EXPECT_EQ(i | (1 << 2) | (1 << 3) | (1 << 16) | (1 << 30),
 762                   r.addIntlvBits(removedBits));
 763     }
 764 }
 765
 766 TEST(AddrRangeTest, InterleavingAddressesGetOffset)
 767 {
 768     Addr start = 0x0002;
 769     Addr end   = 0xFFFF;
 770     std::vector<Addr> masks;
 771     masks.push_back((1 << 4) | (1 << 2));
 772     uint8_t intlv_match = 0;
 773     AddrRange r(start, end, masks, intlv_match);
 774
 775     Addr value = ((1 << 10) | (1 << 9) | (1 <<  8) | (1 << 2) | (1 << 1) | 1);
 776     Addr value_interleaving_bits_removed =
 777                             ((1 << 9) | (1 << 8) | (1 << 7) | (1 << 1) | 1);
 778
 779     Addr expected_output = value_interleaving_bits_removed - start;
 780
 781     EXPECT_EQ(expected_output, r.getOffset(value));
 782 }
 783
 784 TEST(AddrRangeTest, InterleavingLessThanStartEquals)
 785 {
 786     Addr start1 = 0x0000FFFF;
 787     Addr end1   = 0xFFFF0000;
 788     std::vector<Addr> masks1;
 789     masks1.push_back((1 << 4) | (1 << 2));
 790     uint8_t intlv_match1 = 0;
 791     AddrRange r1(start1, end1, masks1, intlv_match1);
 792
 793     Addr start2 = 0x0000FFFF;
 794     Addr end2   = 0x000F0000;
 795     std::vector<Addr> masks2;
 796     masks2.push_back((1 << 4) | (1 << 2));
 797     masks2.push_back((1 << 10));
 798     uint8_t intlv_match2 = 2;
 799     AddrRange r2(start2, end2, masks2, intlv_match2);
 800
 801     /*
 802      * When The start addresses are equal, the intlv_match values are
 803      * compared.
 804      */
 805     EXPECT_TRUE(r1 < r2);
 806     EXPECT_FALSE(r2 < r1);
 807 }
 808
 809 TEST(AddrRangeTest, InterleavingLessThanStartNotEquals)
 810 {
 811     Addr start1 = 0x0000FFFF;
 812     Addr end1   = 0xFFFF0000;
 813     std::vector<Addr> masks1;
 814     masks1.push_back((1 << 4) | (1 << 2));
 815     uint8_t intlv_match1 = 0;
 816     AddrRange r1(start1, end1, masks1, intlv_match1);
 817
 818     Addr start2 = 0x0000FFFE;
 819     Addr end2   = 0x000F0000;
 820     std::vector<Addr> masks2;
 821     masks2.push_back((1 << 4) | (1 << 2));
 822     masks2.push_back((1 << 10));
 823     uint8_t intlv_match2 = 2;
 824     AddrRange r2(start2, end2, masks2, intlv_match2);
 825
 826     EXPECT_TRUE(r2 < r1);
 827     EXPECT_FALSE(r1 < r2);
 828 }
 829
 830 TEST(AddrRangeTest, InterleavingEqualTo)
 831 {
 832     Addr start1 = 0x0000FFFF;
 833     Addr end1   = 0xFFFF0000;
 834     std::vector<Addr> masks1;
 835     masks1.push_back((1 << 4) | (1 << 2));
 836     uint8_t intlv_match1 = 0;
 837     AddrRange r1(start1, end1, masks1, intlv_match1);
 838
 839     Addr start2 = 0x0000FFFF;
 840     Addr end2   = 0xFFFF0000;
 841     std::vector<Addr> masks2;
 842     masks2.push_back((1 << 4) | (1 << 2));
 843     uint8_t intlv_match2 = 0;
 844     AddrRange r2(start2, end2, masks2, intlv_match2);
 845
 846     EXPECT_TRUE(r1 == r2);
 847 }
 848
 849 TEST(AddrRangeTest, InterleavingNotEqualTo)
 850 {
 851     Addr start1 = 0x0000FFFF;
 852     Addr end1   = 0xFFFF0000;
 853     std::vector<Addr> masks1;
 854     masks1.push_back((1 << 4) | (1 << 2));
 855     uint8_t intlv_match1 = 0;
 856     AddrRange r1(start1, end1, masks1, intlv_match1);
 857
 858     Addr start2 = 0x0000FFFF;
 859     Addr end2   = 0xFFFF0000;
 860     std::vector<Addr> masks2;
 861     masks2.push_back((1 << 4) | (1 << 2));
 862     masks2.push_back((1 << 10));
 863     uint8_t intlv_match2 = 2;
 864     AddrRange r2(start2, end2, masks2, intlv_match2);
 865
 866     /*
 867      * These ranges are not equal due to having different masks.
 868      */
 869     EXPECT_FALSE(r1 == r2);
 870 }
 871
 872 /*
 873  * The AddrRange(std::vector<AddrRange>) constructor "merges" the interleaving
 874  * address ranges. It should be noted that this constructor simply checks that
 875  * these interleaving addresses can be merged then creates a new address from
 876  * the start and end addresses of the first address range in the vector.
 877  */
 878 TEST(AddrRangeTest, MergingInterleavingAddressRanges)
 879 {
 880     Addr start1 = 0x0000;
 881     Addr end1   = 0xFFFF;
 882     std::vector<Addr> masks1;
 883     masks1.push_back((1 << 4) | (1 << 2));
 884     uint8_t intlv_match1 = 0;
 885     AddrRange r1(start1, end1, masks1, intlv_match1);
 886
 887     Addr start2 = 0x0000;
 888     Addr end2   = 0xFFFF;
 889     std::vector<Addr> masks2;
 890     masks2.push_back((1 << 4) | (1 << 2));
 891     uint8_t intlv_match2 = 1;
 892     AddrRange r2(start2, end2, masks2, intlv_match2);
 893
 894     std::vector<AddrRange> to_merge;
 895     to_merge.push_back(r1);
 896     to_merge.push_back(r2);
 897
 898     AddrRange output(to_merge);
 899
 900     EXPECT_EQ(0x0000, output.start());
 901     EXPECT_EQ(0xFFFF, output.end());
 902     EXPECT_FALSE(output.interleaved());
 903 }
 904
 905 TEST(AddrRangeTest, MergingInterleavingAddressRangesOneRange)
 906 {
 907     /*
 908      * In the case where there is just one range in the vector, the merged
 909      * address range is equal to that range.
 910      */
 911     Addr start = 0x0000;
 912     Addr end   = 0xFFFF;
 913     std::vector<Addr> masks;
 914     masks.push_back((1 << 4) | (1 << 2));
 915     uint8_t intlv_match = 0;
 916     AddrRange r(start, end, masks, intlv_match);
 917
 918     std::vector<AddrRange> to_merge;
 919     to_merge.push_back(r);
 920
 921     AddrRange output(to_merge);
 922
 923     EXPECT_EQ(r, output);
 924 }
 925
 926 /*
 927  * The following tests verify the soundness of the "legacy constructor",
 928  * AddrRange(Addr, Addr, uint8_t, uint8_t, uint8_t, uint8_t).
 929  *
 930  * The address is assumed to contain two ranges; the interleaving bits, and
 931  * the xor bits. The first two arguments of this constructor specify the
 932  * start and end addresses. The third argument specifies the MSB of the
 933  * interleaving bits. The fourth argument specifies the MSB of the xor bits.
 934  * The firth argument specifies the size (in bits) of the xor and interleaving
 935  * bits. These cannot overlap. The sixth argument specifies the value the
 936  * XORing of the xor and interleaving bits should equal to be considered in
 937  * range.
 938  *
 939  * This constructor does a lot of complex translation to migrate this
 940  * constructor to the masks/intlv_match format.
 941  */
 942 TEST(AddrRangeTest, LegacyConstructorNoInterleaving)
 943 {
 944     /*
 945      * This constructor should create a range with no interleaving.
 946      */
 947     AddrRange range(0x0000, 0xFFFF, 0, 0, 0 ,0);
 948     AddrRange expected(0x0000, 0xFFFF);
 949
 950     EXPECT_EQ(expected, range);
 951 }
 952
 953 TEST(AddrRangeTest, LegacyConstructorOneBitMask)
 954 {
 955     /*
 956      * In this test, the LSB of the address determines whether an address is
 957      * in range. If even, it's in range, if not, it's out of range. the XOR
 958      * bit range is not used.
 959      */
 960     AddrRange range(0x00000000, 0xFFFFFFFF, 0, 0, 1, 0);
 961
 962     std::vector<Addr> masks;
 963     masks.push_back(1);
 964     AddrRange expected(0x00000000, 0xFFFFFFFF, masks, 0);
 965
 966     EXPECT_TRUE(expected == range);
 967 }
 968
 969 TEST(AddrRangeTest, LegacyConstructorTwoBitMask)
 970 {
 971     /*
 972      * In this test, the two LSBs of the address determines whether an address
 973      * is in range. If the two are set, the address is in range. The XOR bit
 974      * range is not used.
 975      */
 976     AddrRange range(0x00000000, 0xFFFFFFFF, 1, 0, 2, 3);
 977
 978     std::vector<Addr> masks;
 979     masks.push_back(1);
 980     masks.push_back((1 << 1));
 981     AddrRange expected(0x00000000, 0xFFFFFFFF, masks, 3);
 982
 983     EXPECT_TRUE(expected == range);
 984 }
 985
 986 TEST(AddrRangeTest, LegacyConstructorTwoBitMaskWithXOR)
 987 {
 988     /*
 989      * In this test, the two LSBs of the address determine wether an address
 990      * is in range. They are XORed to the 10th and 11th bits in the address.
 991      * If XORed value is equal to 3, then the address is in range.
 992      */
 993
 994     AddrRange range(0x00000000, 0xFFFFFFFF, 1, 11, 2,  3);
 995
 996     /*
 997      * The easiest way to ensure this range is correct is to iterate throguh
 998      * the address range and ensure the correct set of addresses are contained
 999      * within the range.
1000      *
1001      * We start with the xor_mask: a mask to select the 10th and 11th bits.
1002      */
1003     Addr xor_mask = (1 << 11) | (1 << 10);
1004     for (Addr i = 0; i < 0x0000FFFF; i++) {
1005         // Get xor bits.
1006         Addr xor_value = (xor_mask & i) >> 10;
1007         /* If the XOR of xor_bits and the intlv bits (the 0th and 1st bits) is
1008          * equal to intlv_match (3, i.e., the 0th and 1st bit is set),then the
1009          * address is within range.
1010          */
1011         if (((xor_value ^ i) & 3) == 3) {
1012             EXPECT_TRUE(range.contains(i));
1013         } else {
1014             EXPECT_FALSE(range.contains(i));
1015         }
1016     }
1017 }
1018
1019 /*
1020  * addr_range.hh contains some convenience constructors. The following tests
1021  * verify they construct AddrRange correctly.
1022  */
1023 TEST(AddrRangeTest, RangeExConstruction)
1024 {
1025     AddrRange r = RangeEx(0x6, 0xE);
1026     EXPECT_EQ(0x6, r.start());
1027     EXPECT_EQ(0xE, r.end());
1028 }
1029
1030 TEST(AddrRangeTest, RangeInConstruction)
1031 {
1032     AddrRange r = RangeIn(0x6, 0xE);
1033     EXPECT_EQ(0x6, r.start());
1034     EXPECT_EQ(0xF, r.end());
1035 }
1036
1037 TEST(AddrRangeTest, RangeSizeConstruction){
1038     AddrRange r = RangeSize(0x5, 5);
1039     EXPECT_EQ(0x5, r.start());
1040     EXPECT_EQ(0xA, r.end());
1041 }