1 // 2 // Copyright (c) 2010-2018 Antmicro 3 // Copyright (c) 2011-2015 Realtime Embedded 4 // 5 // This file is licensed under the MIT License. 6 // Full license text is available in 'licenses/MIT.txt'. 7 // 8 using NUnit.Framework; 9 using Antmicro.Renode.Core; 10 using System.Collections.Generic; 11 12 using System.Linq; 13 14 namespace Antmicro.Renode.UnitTests.SymbolLookupTests 15 { 16 [TestFixture] 17 public class ElfMergeTests 18 { 19 [Test] ShouldMergeTrimEndAndBeginning()20 public void ShouldMergeTrimEndAndBeginning() 21 { 22 var symbols1 = new List<Symbol> 23 { 24 new Symbol(0, 50, "一"), 25 new Symbol(50, 100, "三"), 26 }; 27 var symbols2 = new List<Symbol> 28 { 29 new Symbol(30, 70, "二"), 30 }; 31 var expectedSymbols = new List<Symbol> 32 { 33 new Symbol(0, 30, "一"), 34 new Symbol(30, 70, "二"), 35 new Symbol(70, 100, "三"), 36 }; 37 var addressesToQuery = new List<uint>{25, 35, 75}; 38 var lookup = new SymbolLookup(); 39 lookup.InsertSymbols(symbols1); 40 lookup.InsertSymbols(symbols2); 41 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 42 } 43 44 [Test] ShouldSortedIntervalsHaveExpectedLayout()45 public void ShouldSortedIntervalsHaveExpectedLayout() 46 { 47 var symbols1 = new List<Symbol> 48 { 49 new Symbol(0, 100, "一"), 50 new Symbol(1, 85, "四"), 51 new Symbol(2, 70, "国"), 52 new Symbol(80, 85, "猫"), 53 new Symbol(3, 60, "中"), 54 new Symbol(70, 75, "私"), 55 new Symbol(4, 15, "五"), 56 new Symbol(20, 35, "三"), 57 }; 58 var symbols2 = new List<Symbol> 59 { 60 new Symbol(5, 25, "糞"), 61 new Symbol(40, 82, "二"), 62 new Symbol(50, 55, "ICantSpeekJapaneese"), 63 new Symbol(45, 50, "ICantSpeekKorean"), 64 }; 65 var expectedSymbols = new List<Symbol> 66 { 67 new Symbol(0, 5, "一"), 68 new Symbol(1, 5, "四"), 69 new Symbol(2, 5, "国"), 70 new Symbol(3, 5, "中"), 71 new Symbol(4, 5, "五"), 72 new Symbol(5, 25, "糞"), 73 new Symbol(25, 40, "中"), 74 new Symbol(25, 35, "三"), 75 new Symbol(40, 82, "二"), 76 new Symbol(45, 50, "ICantSpeekKorean"), 77 new Symbol(50, 55, "ICantSpeekJapaneese"), 78 new Symbol(82, 100, "一"), 79 new Symbol(82, 85, "猫"), 80 }; 81 var addressesToQuery = new List<uint>{0, 1, 2, 3, 4, 10, 37, 30, 42, 47, 53, 90, 83}; 82 var lookup = new SymbolLookup(); 83 lookup.InsertSymbols(symbols1); 84 lookup.InsertSymbols(symbols2); 85 CollectionAssert.AreEqual( 86 expectedSymbols, 87 addressesToQuery.Select(address => lookup.GetSymbolByAddress(address)) 88 ); 89 } 90 91 [Test] ShouldTrimEndAndBeginning2()92 public void ShouldTrimEndAndBeginning2() 93 { 94 var symbols1 = new List<Symbol> 95 { 96 new Symbol(30, 70, "二"), 97 }; 98 var symbols2 = new List<Symbol> 99 { 100 new Symbol(0, 40, "一"), 101 new Symbol(60, 100, "三"), 102 }; 103 var expectedSymbols = new List<Symbol> 104 { 105 new Symbol(0, 40, "一"), 106 new Symbol(40, 60, "二"), 107 new Symbol(60, 100, "三"), 108 }; 109 var addressesToQuery = new List<uint>{25, 59, 60}; 110 var lookup = new SymbolLookup(); 111 lookup.InsertSymbols(symbols1); 112 lookup.InsertSymbols(symbols2); 113 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 114 115 } 116 117 [Test] ShouldTrimCakeEnds()118 public void ShouldTrimCakeEnds() 119 { 120 var symbols1 = new List<Symbol> 121 { 122 new Symbol(0, 100, "一"), 123 new Symbol(1, 85, "四"), 124 new Symbol(2, 70, "国"), 125 new Symbol(3, 60, "中"), 126 new Symbol(4, 60, "五"), 127 new Symbol(20, 50, "三"), 128 }; 129 var symbols2 = new List<Symbol> 130 { 131 new Symbol(50, 100, "猫"), 132 }; 133 var expectedSymbols = new List<Symbol> 134 { 135 new Symbol(0, 50, "一"), 136 new Symbol(1, 50, "四"), 137 new Symbol(2, 50, "国"), 138 new Symbol(3, 50, "中"), 139 new Symbol(4, 50, "五"), 140 new Symbol(20, 50, "三"), 141 new Symbol(50, 100, "猫"), 142 }; 143 var addressesToQuery = new List<uint>{0, 1, 2, 3, 15, 35, 99}; 144 var lookup = new SymbolLookup(); 145 lookup.InsertSymbols(symbols1); 146 lookup.InsertSymbols(symbols2); 147 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 148 } 149 150 [Test] ShouldTrimCakeBeginnings()151 public void ShouldTrimCakeBeginnings() 152 { 153 var symbols1 = new List<Symbol> 154 { 155 new Symbol(0, 100, "一"), 156 new Symbol(1, 85, "四"), 157 new Symbol(2, 70, "国"), 158 new Symbol(3, 60, "中"), 159 new Symbol(20, 50, "三"), 160 }; 161 var symbols2 = new List<Symbol> 162 { 163 new Symbol(0, 30, "猫"), 164 }; 165 var expectedSymbols = new List<Symbol> { 166 new Symbol(0, 30, "猫"), 167 new Symbol(30, 100, "一"), 168 new Symbol(30, 85, "四"), 169 new Symbol(30, 70, "国"), 170 new Symbol(30, 60, "中"), 171 new Symbol(30, 50, "三"), 172 }; 173 var addressesToQuery = new List<uint>{10, 95, 80, 65, 55, 45}; 174 var lookup = new SymbolLookup(); 175 lookup.InsertSymbols(symbols1); 176 lookup.InsertSymbols(symbols2); 177 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 178 } 179 180 [Test] ShouldCutIntoCake()181 public void ShouldCutIntoCake() 182 { 183 var symbols1 = new List<Symbol> 184 { 185 new Symbol(0, 100, "一"), 186 new Symbol(1, 85, "四"), 187 new Symbol(2, 70, "国"), 188 new Symbol(3, 60, "中"), 189 new Symbol(20, 50, "三"), 190 }; 191 var symbols2 = new List<Symbol> 192 { 193 new Symbol(35, 40, "猫"), 194 }; 195 var expectedSymbols = new List<Symbol> { 196 new Symbol(0, 35, "一"), 197 new Symbol(1, 35, "四"), 198 new Symbol(2, 35, "国"), 199 new Symbol(3, 35, "中"), 200 new Symbol(20, 35, "三"), 201 new Symbol(35, 40, "猫"), 202 new Symbol(40, 100, "一"), 203 new Symbol(40, 85, "四"), 204 new Symbol(40, 70, "国"), 205 new Symbol(40, 60, "中"), 206 new Symbol(40, 50, "三"), 207 }; 208 var addressesToQuery = new List<uint>{0, 1, 2, 10, 25, 37, 90, 80, 65, 55, 45}; 209 var lookup = new SymbolLookup(); 210 lookup.InsertSymbols(symbols1); 211 lookup.InsertSymbols(symbols2); 212 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 213 } 214 215 [Test] ShouldTrimCakeToTopSymbol()216 public void ShouldTrimCakeToTopSymbol() 217 { 218 var symbols1 = new List<Symbol> 219 { 220 new Symbol(0, 100, "一"), 221 new Symbol(1, 85, "四"), 222 new Symbol(2, 70, "国"), 223 new Symbol(3, 60, "中"), 224 new Symbol(4, 60, "五"), 225 new Symbol(20, 50, "三"), 226 }; 227 var symbols2 = new List<Symbol> 228 { 229 new Symbol(0, 30, "猫"), 230 new Symbol(40, 100, "糞"), 231 }; 232 var expectedSymbols = new List<Symbol> { 233 new Symbol(0, 30, "猫"), 234 new Symbol(30, 40, "三"), 235 new Symbol(40, 100, "糞"), 236 }; 237 var addressesToQuery = new List<uint>{10, 37, 80}; 238 var lookup = new SymbolLookup(); 239 lookup.InsertSymbols(symbols1); 240 lookup.InsertSymbols(symbols2); 241 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 242 } 243 244 [Test] ShouldTrimAndOvershadow()245 public void ShouldTrimAndOvershadow() 246 { 247 var symbols1 = new List<Symbol> 248 { 249 new Symbol(0, 10, "一"), 250 new Symbol(1, 8, "四"), 251 new Symbol(20, 40, "国"), 252 new Symbol(30, 40, "中"), 253 new Symbol(40, 60, "五"), 254 new Symbol(45, 55, "三"), 255 }; 256 var symbols2 = new List<Symbol> 257 { 258 new Symbol(5, 50, "猫"), 259 new Symbol(10, 15, "糞"), 260 }; 261 var expectedSymbols = new List<Symbol> { 262 new Symbol(0, 5, "一"), 263 new Symbol(1, 5, "四"), 264 new Symbol(5, 50, "猫"), 265 new Symbol(10, 15, "糞"), 266 new Symbol(50, 60, "五"), 267 new Symbol(50, 55, "三"), 268 }; 269 var addressesToQuery = new List<uint>{0, 1, 45, 12, 59, 52}; 270 var lookup = new SymbolLookup(); 271 lookup.InsertSymbols(symbols1); 272 lookup.InsertSymbols(symbols2); 273 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 274 } 275 276 [Test] ShouldSplitCake()277 public void ShouldSplitCake() 278 { 279 var symbols1 = new List<Symbol> 280 { 281 new Symbol(0, 5, "一"), 282 new Symbol(1, 4, "四"), 283 }; 284 var symbols2 = new List<Symbol> 285 { 286 new Symbol(2, 2, "猫"), 287 }; 288 var expectedSymbols = new List<Symbol> { 289 new Symbol(0, 2, "一"), 290 new Symbol(1, 2, "四"), 291 new Symbol(2, 2, "猫"), 292 new Symbol(2, 4, "四"), 293 new Symbol(2, 5, "一"), 294 }; 295 var addressesToQuery = new List<uint>{0, 1, 2, 3, 4}; 296 var lookup = new SymbolLookup(); 297 lookup.InsertSymbols(symbols1); 298 lookup.InsertSymbols(symbols2); 299 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 300 } 301 302 [Test] ShouldTrimAndOverShadowOnABase()303 public void ShouldTrimAndOverShadowOnABase() 304 { 305 var symbols1 = new List<Symbol> 306 { 307 new Symbol(0, 100, "一"), 308 new Symbol(1, 8, "四"), 309 new Symbol(20, 40, "国"), 310 new Symbol(30, 40, "中"), 311 new Symbol(40, 60, "五"), 312 new Symbol(45, 55, "三"), 313 }; 314 var symbols2 = new List<Symbol> 315 { 316 new Symbol(5, 50, "猫"), 317 new Symbol(10, 15, "糞"), 318 }; 319 var expectedSymbols = new List<Symbol> { 320 new Symbol(0, 5, "一"), 321 new Symbol(1, 5, "四"), 322 new Symbol(5, 50, "猫"), 323 new Symbol(10, 15, "糞"), 324 new Symbol(50, 100, "一"), 325 new Symbol(50, 60, "五"), 326 new Symbol(50, 55, "三"), 327 }; 328 var addressesToQuery = new List<uint>{0, 3, 5, 14, 60, 59, 51}; 329 var lookup = new SymbolLookup(); 330 lookup.InsertSymbols(symbols1); 331 lookup.InsertSymbols(symbols2); 332 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 333 } 334 335 [Test] ShouldSplitCakeAfterSecondTower()336 public void ShouldSplitCakeAfterSecondTower() 337 { 338 var symbols1 = new List<Symbol> 339 { 340 new Symbol(0, 100, "一"), 341 new Symbol(1, 8, "四"), 342 new Symbol(20, 40, "国"), 343 new Symbol(30, 40, "中"), 344 new Symbol(50, 60, "五"), 345 new Symbol(50, 55, "三"), 346 }; 347 var symbols2 = new List<Symbol> 348 { 349 new Symbol(42, 47, "猫"), 350 new Symbol(43, 43, "糞"), 351 }; 352 var expectedSymbols = new List<Symbol> { 353 new Symbol(0, 42, "一"), 354 new Symbol(1, 8, "四"), 355 new Symbol(20, 40, "国"), 356 new Symbol(30, 40, "中"), 357 new Symbol(42, 47, "猫"), 358 new Symbol(43, 43, "糞"), 359 new Symbol(47, 100, "一"), 360 new Symbol(50, 60, "五"), 361 new Symbol(50, 55, "三"), 362 }; 363 var addressesToQuery = new List<uint>{41, 5, 25, 35, 45, 43, 48, 58, 50}; 364 var lookup = new SymbolLookup(); 365 lookup.InsertSymbols(symbols1); 366 lookup.InsertSymbols(symbols2); 367 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 368 } 369 370 [Test] ShouldHaveSlicedSymbolInNameLookup()371 public void ShouldHaveSlicedSymbolInNameLookup() 372 { 373 var symbols1 = new List<Symbol> 374 { 375 new Symbol(20, 40, "国"), 376 new Symbol(30, 40, "中"), 377 new Symbol(50, 60, "五"), 378 new Symbol(50, 55, "三"), 379 }; 380 var symbols2 = new List<Symbol> 381 { 382 new Symbol(30, 35, "中"), 383 }; 384 var expectedSymbols = new List<Symbol> { 385 new Symbol(20, 30, "国"), 386 new Symbol(30, 35, "中"), 387 new Symbol(35, 40, "中"), 388 new Symbol(50, 60, "五"), 389 new Symbol(50, 55, "三"), 390 }; 391 var addressesToQuery = new List<uint>{20, 30, 35, 58, 50}; 392 var lookup = new SymbolLookup(); 393 lookup.InsertSymbols(symbols1); 394 lookup.InsertSymbols(symbols2); 395 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 396 var name = expectedSymbols[1].Name; 397 Assert.AreEqual(expectedSymbols[1], lookup.GetSymbolsByName(name).ElementAt(0)); 398 Assert.AreEqual(expectedSymbols[2], lookup.GetSymbolsByName(name).ElementAt(1)); 399 } 400 401 [Test] ShouldPlaceZeroLenghtSymbolBeforeCake()402 public void ShouldPlaceZeroLenghtSymbolBeforeCake() 403 { 404 var symbols1 = new List<Symbol> 405 { 406 new Symbol(50, 100, "一"), 407 new Symbol(50, 75, "三"), 408 }; 409 var symbols2 = new List<Symbol> 410 { 411 new Symbol(50, 50, "二"), 412 }; 413 var expectedSymbols = new List<Symbol> 414 { 415 new Symbol(50, 100, "一"), 416 new Symbol(50, 75, "三"), 417 new Symbol(50, 50, "二"), 418 }; 419 var addressesToQuery = new List<uint>{90, 55, 50}; 420 var lookup = new SymbolLookup(); 421 lookup.InsertSymbols(symbols1); 422 lookup.InsertSymbols(symbols2); 423 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 424 } 425 426 [Test] ShouldCoverZeroLenghtSymbol()427 public void ShouldCoverZeroLenghtSymbol() 428 { 429 var symbols1 = new List<Symbol> 430 { 431 new Symbol(50, 50, "二"), 432 }; 433 var symbols2 = new List<Symbol> 434 { 435 new Symbol(50, 100, "一"), 436 new Symbol(50, 75, "三"), 437 }; 438 var expectedSymbols = new List<Symbol> 439 { 440 new Symbol(50, 100, "一"), 441 new Symbol(50, 75, "三"), 442 }; 443 var addressesToQuery = new List<uint>{90, 55}; 444 var lookup = new SymbolLookup(); 445 lookup.InsertSymbols(symbols1); 446 lookup.InsertSymbols(symbols2); 447 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 448 IReadOnlyCollection<Symbol> symbols; 449 Assert.IsFalse(lookup.TryGetSymbolsByName("二", out symbols), "Symbol \"二\"should not be present."); 450 } 451 452 [Test] ShouldZeroLenghtSymbolCutAfterCake()453 public void ShouldZeroLenghtSymbolCutAfterCake() 454 { 455 var symbols1 = new List<Symbol> 456 { 457 new Symbol(0, 50, "一"), 458 new Symbol(10, 50, "三"), 459 }; 460 var symbols2 = new List<Symbol> 461 { 462 new Symbol(50, 50, "二"), 463 }; 464 var expectedSymbols = new List<Symbol> 465 { 466 new Symbol(0, 50, "一"), 467 new Symbol(10, 50, "三"), 468 new Symbol(50, 50, "二"), 469 }; 470 var addressesToQuery = new List<uint>{0, 15, 50}; 471 var lookup = new SymbolLookup(); 472 lookup.InsertSymbols(symbols1); 473 lookup.InsertSymbols(symbols2); 474 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 475 } 476 477 [Test] ShouldNotDestroyOtherSymbolLookupCache()478 public void ShouldNotDestroyOtherSymbolLookupCache() 479 { 480 var symbols1 = new List<Symbol> 481 { 482 new Symbol(0, 100, "一"), 483 new Symbol(1, 85, "四"), 484 new Symbol(2, 70, "国"), 485 new Symbol(80, 85, "猫"), 486 new Symbol(3, 60, "中"), 487 new Symbol(70, 75, "私"), 488 new Symbol(4, 15, "五"), 489 new Symbol(20, 35, "三"), 490 }; 491 var symbols2 = new List<Symbol> 492 { 493 new Symbol(5, 25, "糞"), 494 new Symbol(40, 82, "二"), 495 new Symbol(50, 55, "ICantSpeekJapaneese"), 496 new Symbol(45, 50, "ICantSpeekKorean"), 497 }; 498 var mergedSymbols = new List<Symbol> 499 { 500 new Symbol(0, 5, "一"), 501 new Symbol(1, 5, "四"), 502 new Symbol(2, 5, "国"), 503 new Symbol(3, 5, "中"), 504 new Symbol(4, 5, "五"), 505 new Symbol(5, 25, "糞"), 506 new Symbol(25, 40, "中"), 507 new Symbol(25, 35, "三"), 508 new Symbol(40, 82, "二"), 509 new Symbol(45, 50, "ICantSpeekKorean"), 510 new Symbol(50, 55, "ICantSpeekJapaneese"), 511 new Symbol(82, 100, "一"), 512 new Symbol(82, 85, "猫"), 513 }; 514 var addressesToQuery = new List<uint>{0, 1, 2, 3, 4, 10, 37, 30, 42, 47, 53, 90, 83}; 515 var lookup = new List<SymbolLookup> {new SymbolLookup(), new SymbolLookup()}; 516 lookup[0].InsertSymbols(symbols1); 517 lookup[1].InsertSymbols(symbols1); 518 lookup[0].InsertSymbols(symbols2); 519 CollectionAssert.AreEqual( 520 mergedSymbols, 521 addressesToQuery.Select(address => lookup[0].GetSymbolByAddress(address)) 522 ); 523 CollectionAssert.AreEqual( 524 symbols1, 525 symbols1.Select(symbol => lookup[1].GetSymbolByAddress(symbol.Start)) 526 ); 527 } 528 529 /// <summary> 530 /// Regression test. "三" was removed and wasn't added. 531 /// </summary> 532 [Test] ShouldPerserveSymbol()533 public void ShouldPerserveSymbol() 534 { 535 var symbols1 = new List<Symbol> 536 { 537 new Symbol(0, 100, "一"), 538 new Symbol(20, 35, "三"), 539 new Symbol(100, 105, "猫"), 540 }; 541 var symbols2 = new List<Symbol> 542 { 543 new Symbol(15, 25, "私"), 544 }; 545 var lookup = new SymbolLookup(); 546 lookup.InsertSymbols(symbols1); 547 lookup.InsertSymbols(symbols2); 548 549 var symbol = symbols1[1]; 550 IReadOnlyCollection<Symbol> symbols; 551 Assert.IsTrue( 552 lookup.TryGetSymbolsByName(symbol.Name, out symbols), 553 string.Format("Symbol {0} has NOT been deduplicated.", symbol) 554 ); 555 } 556 557 /// <summary> 558 /// This is a regression test. Previously such inserts resulted in infinite loop. 559 /// </summary> 560 [Test] ShouldMergeOverlappingThumbSymbols()561 public void ShouldMergeOverlappingThumbSymbols() 562 { 563 var symbols1 = new List<Symbol> 564 { 565 new Symbol(10, 20, "一", ELFSharp.ELF.Sections.SymbolType.NotSpecified, ELFSharp.ELF.Sections.SymbolBinding.Global, true), 566 }; 567 var symbols2 = new List<Symbol> 568 { 569 new Symbol(5, 15, "悪魔", ELFSharp.ELF.Sections.SymbolType.NotSpecified, ELFSharp.ELF.Sections.SymbolBinding.Global, true), 570 }; 571 var lookup = new SymbolLookup(); 572 lookup.InsertSymbols(symbols1); 573 lookup.InsertSymbols(symbols2); 574 } 575 576 [Test] ShouldFavorUnempty()577 public void ShouldFavorUnempty() 578 { 579 var symbols = new List<Symbol> 580 { 581 new Symbol(0, 10, "Unempty"), 582 new Symbol(0, 10, ""), 583 new Symbol(10, 20, "Other"), 584 }; 585 586 var expectedSymbols = new List<Symbol> 587 { 588 new Symbol(0, 10, "Unempty"), 589 new Symbol(10, 20, "Other"), 590 }; 591 592 var addressesToQuery = new List<uint>{0, 10}; 593 var lookup = new SymbolLookup(); 594 lookup.InsertSymbols(symbols); 595 CollectionAssert.AreEqual(expectedSymbols, addressesToQuery.Select(address => lookup.GetSymbolByAddress(address))); 596 } 597 } 598 } 599
