1// Copyright (C) 2019 The Android Open Source Project 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15import {mergeCallsites} from './flamegraph_util'; 16import {CallsiteInfo} from './state'; 17 18test('zeroCallsitesMerged', () => { 19 const callsites: CallsiteInfo[] = [ 20 { 21 id: 1, 22 parentId: -1, 23 name: 'A', 24 depth: 0, 25 totalSize: 10, 26 selfSize: 0, 27 mapping: 'x', 28 merged: false 29 }, 30 { 31 id: 2, 32 parentId: -1, 33 name: 'B', 34 depth: 0, 35 totalSize: 8, 36 selfSize: 0, 37 mapping: 'x', 38 merged: false 39 }, 40 { 41 id: 3, 42 parentId: 1, 43 name: 'A3', 44 depth: 1, 45 totalSize: 4, 46 selfSize: 0, 47 mapping: 'x', 48 merged: false 49 }, 50 { 51 id: 4, 52 parentId: 2, 53 name: 'B4', 54 depth: 1, 55 totalSize: 4, 56 selfSize: 0, 57 mapping: 'x', 58 merged: false 59 }, 60 ]; 61 62 const mergedCallsites = mergeCallsites(callsites, 5); 63 64 // Small callsites are not next ot each other, nothing should be changed. 65 expect(mergedCallsites).toEqual(callsites); 66}); 67 68test('zeroCallsitesMerged2', () => { 69 const callsites: CallsiteInfo[] = [ 70 { 71 id: 1, 72 parentId: -1, 73 name: 'A', 74 depth: 0, 75 totalSize: 10, 76 selfSize: 0, 77 mapping: 'x', 78 merged: false 79 }, 80 { 81 id: 2, 82 parentId: -1, 83 name: 'B', 84 depth: 0, 85 totalSize: 8, 86 selfSize: 0, 87 mapping: 'x', 88 merged: false 89 }, 90 { 91 id: 3, 92 parentId: 1, 93 name: 'A3', 94 depth: 1, 95 totalSize: 6, 96 selfSize: 0, 97 mapping: 'x', 98 merged: false 99 }, 100 { 101 id: 4, 102 parentId: 1, 103 name: 'A4', 104 depth: 1, 105 totalSize: 4, 106 selfSize: 0, 107 mapping: 'x', 108 merged: false 109 }, 110 { 111 id: 5, 112 parentId: 2, 113 name: 'B5', 114 depth: 1, 115 totalSize: 8, 116 selfSize: 0, 117 mapping: 'x', 118 merged: false 119 }, 120 ]; 121 122 const mergedCallsites = mergeCallsites(callsites, 5); 123 124 // Small callsites are not next ot each other, nothing should be changed. 125 expect(mergedCallsites).toEqual(callsites); 126}); 127 128test('twoCallsitesMerged', () => { 129 const callsites: CallsiteInfo[] = [ 130 { 131 id: 1, 132 parentId: -1, 133 name: 'A', 134 depth: 0, 135 totalSize: 10, 136 selfSize: 0, 137 mapping: 'x', 138 merged: false 139 }, 140 { 141 id: 2, 142 parentId: 1, 143 name: 'A2', 144 depth: 1, 145 totalSize: 5, 146 selfSize: 0, 147 mapping: 'x', 148 merged: false 149 }, 150 { 151 id: 3, 152 parentId: 1, 153 name: 'A3', 154 depth: 1, 155 totalSize: 5, 156 selfSize: 0, 157 mapping: 'x', 158 merged: false 159 }, 160 ]; 161 162 const mergedCallsites = mergeCallsites(callsites, 6); 163 164 expect(mergedCallsites).toEqual([ 165 { 166 id: 1, 167 parentId: -1, 168 name: 'A', 169 depth: 0, 170 totalSize: 10, 171 selfSize: 0, 172 mapping: 'x', 173 merged: false 174 }, 175 { 176 id: 2, 177 parentId: 1, 178 name: '[merged]', 179 depth: 1, 180 totalSize: 10, 181 selfSize: 0, 182 mapping: 'x', 183 merged: true 184 }, 185 ]); 186}); 187 188test('manyCallsitesMerged', () => { 189 const callsites: CallsiteInfo[] = [ 190 { 191 id: 1, 192 parentId: -1, 193 name: 'A', 194 depth: 0, 195 totalSize: 10, 196 selfSize: 0, 197 mapping: 'x', 198 merged: false 199 }, 200 { 201 id: 2, 202 parentId: 1, 203 name: 'A2', 204 depth: 1, 205 totalSize: 5, 206 selfSize: 0, 207 mapping: 'x', 208 merged: false 209 }, 210 { 211 id: 3, 212 parentId: 1, 213 name: 'A3', 214 depth: 1, 215 totalSize: 3, 216 selfSize: 0, 217 mapping: 'x', 218 merged: false 219 }, 220 { 221 id: 4, 222 parentId: 1, 223 name: 'A4', 224 depth: 1, 225 totalSize: 1, 226 selfSize: 0, 227 mapping: 'x', 228 merged: false 229 }, 230 { 231 id: 5, 232 parentId: 1, 233 name: 'A5', 234 depth: 1, 235 totalSize: 1, 236 selfSize: 0, 237 mapping: 'x', 238 merged: false 239 }, 240 { 241 id: 6, 242 parentId: 3, 243 name: 'A36', 244 depth: 2, 245 totalSize: 1, 246 selfSize: 0, 247 mapping: 'x', 248 merged: false 249 }, 250 { 251 id: 7, 252 parentId: 4, 253 name: 'A47', 254 depth: 2, 255 totalSize: 1, 256 selfSize: 0, 257 mapping: 'x', 258 merged: false 259 }, 260 { 261 id: 8, 262 parentId: 5, 263 name: 'A58', 264 depth: 2, 265 totalSize: 1, 266 selfSize: 0, 267 mapping: 'x', 268 merged: false 269 }, 270 ]; 271 272 const expectedMergedCallsites: CallsiteInfo[] = [ 273 { 274 id: 1, 275 parentId: -1, 276 name: 'A', 277 depth: 0, 278 totalSize: 10, 279 selfSize: 0, 280 mapping: 'x', 281 merged: false 282 }, 283 { 284 id: 2, 285 parentId: 1, 286 name: 'A2', 287 depth: 1, 288 totalSize: 5, 289 selfSize: 0, 290 mapping: 'x', 291 merged: false 292 }, 293 { 294 id: 3, 295 parentId: 1, 296 name: '[merged]', 297 depth: 1, 298 totalSize: 5, 299 selfSize: 0, 300 mapping: 'x', 301 merged: true 302 }, 303 { 304 id: 6, 305 parentId: 3, 306 name: '[merged]', 307 depth: 2, 308 totalSize: 3, 309 selfSize: 0, 310 mapping: 'x', 311 merged: true 312 }, 313 ]; 314 315 const mergedCallsites = mergeCallsites(callsites, 4); 316 317 // In this case, callsites A3, A4 and A5 should be merged since they are 318 // smaller then 4 and are on same depth with same parent. Callsites A36, A47 319 // and A58 should also be merged since their parents are merged. 320 expect(mergedCallsites).toEqual(expectedMergedCallsites); 321}); 322 323test('manyCallsitesMergedWithoutChildren', () => { 324 const callsites: CallsiteInfo[] = [ 325 { 326 id: 1, 327 parentId: -1, 328 name: 'A', 329 depth: 0, 330 totalSize: 5, 331 selfSize: 0, 332 mapping: 'x', 333 merged: false 334 }, 335 { 336 id: 2, 337 parentId: -1, 338 name: 'B', 339 depth: 0, 340 totalSize: 5, 341 selfSize: 0, 342 mapping: 'x', 343 merged: false 344 }, 345 { 346 id: 3, 347 parentId: 1, 348 name: 'A3', 349 depth: 1, 350 totalSize: 3, 351 selfSize: 0, 352 mapping: 'x', 353 merged: false 354 }, 355 { 356 id: 4, 357 parentId: 1, 358 name: 'A4', 359 depth: 1, 360 totalSize: 1, 361 selfSize: 0, 362 mapping: 'x', 363 merged: false 364 }, 365 { 366 id: 5, 367 parentId: 1, 368 name: 'A5', 369 depth: 1, 370 totalSize: 1, 371 selfSize: 0, 372 mapping: 'x', 373 merged: false 374 }, 375 { 376 id: 6, 377 parentId: 2, 378 name: 'B6', 379 depth: 1, 380 totalSize: 5, 381 selfSize: 0, 382 mapping: 'x', 383 merged: false 384 }, 385 { 386 id: 7, 387 parentId: 4, 388 name: 'A47', 389 depth: 2, 390 totalSize: 1, 391 selfSize: 0, 392 mapping: 'x', 393 merged: false 394 }, 395 { 396 id: 8, 397 parentId: 6, 398 name: 'B68', 399 depth: 2, 400 totalSize: 1, 401 selfSize: 0, 402 mapping: 'x', 403 merged: false 404 }, 405 ]; 406 407 const expectedMergedCallsites: CallsiteInfo[] = [ 408 { 409 id: 1, 410 parentId: -1, 411 name: 'A', 412 depth: 0, 413 totalSize: 5, 414 selfSize: 0, 415 mapping: 'x', 416 merged: false 417 }, 418 { 419 id: 2, 420 parentId: -1, 421 name: 'B', 422 depth: 0, 423 totalSize: 5, 424 selfSize: 0, 425 mapping: 'x', 426 merged: false 427 }, 428 { 429 id: 3, 430 parentId: 1, 431 name: '[merged]', 432 depth: 1, 433 totalSize: 5, 434 selfSize: 0, 435 mapping: 'x', 436 merged: true 437 }, 438 { 439 id: 6, 440 parentId: 2, 441 name: 'B6', 442 depth: 1, 443 totalSize: 5, 444 selfSize: 0, 445 mapping: 'x', 446 merged: false 447 }, 448 { 449 id: 7, 450 parentId: 3, 451 name: 'A47', 452 depth: 2, 453 totalSize: 1, 454 selfSize: 0, 455 mapping: 'x', 456 merged: false 457 }, 458 { 459 id: 8, 460 parentId: 6, 461 name: 'B68', 462 depth: 2, 463 totalSize: 1, 464 selfSize: 0, 465 mapping: 'x', 466 merged: false 467 }, 468 ]; 469 470 const mergedCallsites = mergeCallsites(callsites, 4); 471 472 // In this case, callsites A3, A4 and A5 should be merged since they are 473 // smaller then 4 and are on same depth with same parent. Callsite A47 474 // should not be merged with B68 althought they are small because they don't 475 // have sam parent. A47 should now have parent A3 because A4 is merged. 476 expect(mergedCallsites).toEqual(expectedMergedCallsites); 477}); 478 479test('smallCallsitesNotNextToEachOtherInArray', () => { 480 const callsites: CallsiteInfo[] = [ 481 { 482 id: 1, 483 parentId: -1, 484 name: 'A', 485 depth: 0, 486 totalSize: 20, 487 selfSize: 0, 488 mapping: 'x', 489 merged: false 490 }, 491 { 492 id: 2, 493 parentId: 1, 494 name: 'A2', 495 depth: 1, 496 totalSize: 8, 497 selfSize: 0, 498 mapping: 'x', 499 merged: false 500 }, 501 { 502 id: 3, 503 parentId: 1, 504 name: 'A3', 505 depth: 1, 506 totalSize: 1, 507 selfSize: 0, 508 mapping: 'x', 509 merged: false 510 }, 511 { 512 id: 4, 513 parentId: 1, 514 name: 'A4', 515 depth: 1, 516 totalSize: 8, 517 selfSize: 0, 518 mapping: 'x', 519 merged: false 520 }, 521 { 522 id: 5, 523 parentId: 1, 524 name: 'A5', 525 depth: 1, 526 totalSize: 3, 527 selfSize: 0, 528 mapping: 'x', 529 merged: false 530 }, 531 ]; 532 533 const expectedMergedCallsites: CallsiteInfo[] = [ 534 { 535 id: 1, 536 parentId: -1, 537 name: 'A', 538 depth: 0, 539 totalSize: 20, 540 selfSize: 0, 541 mapping: 'x', 542 merged: false 543 }, 544 { 545 id: 2, 546 parentId: 1, 547 name: 'A2', 548 depth: 1, 549 totalSize: 8, 550 selfSize: 0, 551 mapping: 'x', 552 merged: false 553 }, 554 { 555 id: 3, 556 parentId: 1, 557 name: '[merged]', 558 depth: 1, 559 totalSize: 4, 560 selfSize: 0, 561 mapping: 'x', 562 merged: true 563 }, 564 { 565 id: 4, 566 parentId: 1, 567 name: 'A4', 568 depth: 1, 569 totalSize: 8, 570 selfSize: 0, 571 mapping: 'x', 572 merged: false 573 }, 574 ]; 575 576 const mergedCallsites = mergeCallsites(callsites, 4); 577 578 // In this case, callsites A3, A4 and A5 should be merged since they are 579 // smaller then 4 and are on same depth with same parent. Callsite A47 580 // should not be merged with B68 althought they are small because they don't 581 // have sam parent. A47 should now have parent A3 because A4 is merged. 582 expect(mergedCallsites).toEqual(expectedMergedCallsites); 583}); 584 585test('smallCallsitesNotMerged', () => { 586 const callsites: CallsiteInfo[] = [ 587 { 588 id: 1, 589 parentId: -1, 590 name: 'A', 591 depth: 0, 592 totalSize: 10, 593 selfSize: 0, 594 mapping: 'x', 595 merged: false 596 }, 597 { 598 id: 2, 599 parentId: 1, 600 name: 'A2', 601 depth: 1, 602 totalSize: 2, 603 selfSize: 0, 604 mapping: 'x', 605 merged: false 606 }, 607 { 608 id: 3, 609 parentId: 1, 610 name: 'A3', 611 depth: 1, 612 totalSize: 2, 613 selfSize: 0, 614 mapping: 'x', 615 merged: false 616 }, 617 ]; 618 619 const mergedCallsites = mergeCallsites(callsites, 1); 620 621 expect(mergedCallsites).toEqual(callsites); 622}); 623 624test('mergingRootCallsites', () => { 625 const callsites: CallsiteInfo[] = [ 626 { 627 id: 1, 628 parentId: -1, 629 name: 'A', 630 depth: 0, 631 totalSize: 10, 632 selfSize: 0, 633 mapping: 'x', 634 merged: false 635 }, 636 { 637 id: 2, 638 parentId: -1, 639 name: 'B', 640 depth: 0, 641 totalSize: 2, 642 selfSize: 0, 643 mapping: 'x', 644 merged: false 645 }, 646 ]; 647 648 const mergedCallsites = mergeCallsites(callsites, 20); 649 650 expect(mergedCallsites).toEqual([ 651 { 652 id: 1, 653 parentId: -1, 654 name: '[merged]', 655 depth: 0, 656 totalSize: 12, 657 selfSize: 0, 658 mapping: 'x', 659 merged: true 660 }, 661 ]); 662}); 663 664test('largerFlamegraph', () => { 665 const data: CallsiteInfo[] = [ 666 { 667 id: 1, 668 parentId: -1, 669 name: 'A', 670 depth: 0, 671 totalSize: 60, 672 selfSize: 0, 673 mapping: 'x', 674 merged: false 675 }, 676 { 677 id: 2, 678 parentId: -1, 679 name: 'B', 680 depth: 0, 681 totalSize: 40, 682 selfSize: 0, 683 mapping: 'x', 684 merged: false 685 }, 686 { 687 id: 3, 688 parentId: 1, 689 name: 'A3', 690 depth: 1, 691 totalSize: 25, 692 selfSize: 0, 693 mapping: 'x', 694 merged: false 695 }, 696 { 697 id: 4, 698 parentId: 1, 699 name: 'A4', 700 depth: 1, 701 totalSize: 15, 702 selfSize: 0, 703 mapping: 'x', 704 merged: false 705 }, 706 { 707 id: 5, 708 parentId: 1, 709 name: 'A5', 710 depth: 1, 711 totalSize: 10, 712 selfSize: 0, 713 mapping: 'x', 714 merged: false 715 }, 716 { 717 id: 6, 718 parentId: 1, 719 name: 'A6', 720 depth: 1, 721 totalSize: 10, 722 selfSize: 0, 723 mapping: 'x', 724 merged: false 725 }, 726 { 727 id: 7, 728 parentId: 2, 729 name: 'B7', 730 depth: 1, 731 totalSize: 30, 732 selfSize: 0, 733 mapping: 'x', 734 merged: false 735 }, 736 { 737 id: 8, 738 parentId: 2, 739 name: 'B8', 740 depth: 1, 741 totalSize: 10, 742 selfSize: 0, 743 mapping: 'x', 744 merged: false 745 }, 746 { 747 id: 9, 748 parentId: 3, 749 name: 'A39', 750 depth: 2, 751 totalSize: 20, 752 selfSize: 0, 753 mapping: 'x', 754 merged: false 755 }, 756 { 757 id: 10, 758 parentId: 4, 759 name: 'A410', 760 depth: 2, 761 totalSize: 10, 762 selfSize: 0, 763 mapping: 'x', 764 merged: false 765 }, 766 { 767 id: 11, 768 parentId: 4, 769 name: 'A411', 770 depth: 2, 771 totalSize: 3, 772 selfSize: 0, 773 mapping: 'x', 774 merged: false 775 }, 776 { 777 id: 12, 778 parentId: 4, 779 name: 'A412', 780 depth: 2, 781 totalSize: 2, 782 selfSize: 0, 783 mapping: 'x', 784 merged: false 785 }, 786 { 787 id: 13, 788 parentId: 5, 789 name: 'A513', 790 depth: 2, 791 totalSize: 5, 792 selfSize: 0, 793 mapping: 'x', 794 merged: false 795 }, 796 { 797 id: 14, 798 parentId: 5, 799 name: 'A514', 800 depth: 2, 801 totalSize: 5, 802 selfSize: 0, 803 mapping: 'x', 804 merged: false 805 }, 806 { 807 id: 15, 808 parentId: 7, 809 name: 'A715', 810 depth: 2, 811 totalSize: 10, 812 selfSize: 0, 813 mapping: 'x', 814 merged: false 815 }, 816 { 817 id: 16, 818 parentId: 7, 819 name: 'A716', 820 depth: 2, 821 totalSize: 5, 822 selfSize: 0, 823 mapping: 'x', 824 merged: false 825 }, 826 { 827 id: 17, 828 parentId: 7, 829 name: 'A717', 830 depth: 2, 831 totalSize: 5, 832 selfSize: 0, 833 mapping: 'x', 834 merged: false 835 }, 836 { 837 id: 18, 838 parentId: 7, 839 name: 'A718', 840 depth: 2, 841 totalSize: 5, 842 selfSize: 0, 843 mapping: 'x', 844 merged: false 845 }, 846 { 847 id: 19, 848 parentId: 9, 849 name: 'A919', 850 depth: 3, 851 totalSize: 10, 852 selfSize: 0, 853 mapping: 'x', 854 merged: false 855 }, 856 { 857 id: 20, 858 parentId: 17, 859 name: 'A1720', 860 depth: 3, 861 totalSize: 2, 862 selfSize: 0, 863 mapping: 'x', 864 merged: false 865 }, 866 ]; 867 868 const expectedData: CallsiteInfo[] = [ 869 { 870 id: 1, 871 parentId: -1, 872 name: 'A', 873 depth: 0, 874 totalSize: 60, 875 selfSize: 0, 876 mapping: 'x', 877 merged: false 878 }, 879 { 880 id: 2, 881 parentId: -1, 882 name: 'B', 883 depth: 0, 884 totalSize: 40, 885 selfSize: 0, 886 mapping: 'x', 887 merged: false 888 }, 889 { 890 id: 3, 891 parentId: 1, 892 name: 'A3', 893 depth: 1, 894 totalSize: 25, 895 selfSize: 0, 896 mapping: 'x', 897 merged: false 898 }, 899 { 900 id: 4, 901 parentId: 1, 902 name: '[merged]', 903 depth: 1, 904 totalSize: 35, 905 selfSize: 0, 906 mapping: 'x', 907 merged: true 908 }, 909 { 910 id: 7, 911 parentId: 2, 912 name: 'B7', 913 depth: 1, 914 totalSize: 30, 915 selfSize: 0, 916 mapping: 'x', 917 merged: false 918 }, 919 { 920 id: 8, 921 parentId: 2, 922 name: 'B8', 923 depth: 1, 924 totalSize: 10, 925 selfSize: 0, 926 mapping: 'x', 927 merged: false 928 }, 929 { 930 id: 9, 931 parentId: 3, 932 name: 'A39', 933 depth: 2, 934 totalSize: 20, 935 selfSize: 0, 936 mapping: 'x', 937 merged: false 938 }, 939 { 940 id: 10, 941 parentId: 4, 942 name: '[merged]', 943 depth: 2, 944 totalSize: 25, 945 selfSize: 0, 946 mapping: 'x', 947 merged: true 948 }, 949 { 950 id: 15, 951 parentId: 7, 952 name: '[merged]', 953 depth: 2, 954 totalSize: 25, 955 selfSize: 0, 956 mapping: 'x', 957 merged: true 958 }, 959 { 960 id: 19, 961 parentId: 9, 962 name: 'A919', 963 depth: 3, 964 totalSize: 10, 965 selfSize: 0, 966 mapping: 'x', 967 merged: false 968 }, 969 { 970 id: 20, 971 parentId: 15, 972 name: 'A1720', 973 depth: 3, 974 totalSize: 2, 975 selfSize: 0, 976 mapping: 'x', 977 merged: false 978 }, 979 ]; 980 981 // In this case, on depth 1, callsites A4, A5 and A6 should be merged and 982 // initiate merging of their children A410, A411, A412, A513, A514. On depth2, 983 // callsites A715, A716, A717 and A718 should be merged. 984 const actualData = mergeCallsites(data, 16); 985 986 expect(actualData).toEqual(expectedData); 987}); 988