aboutsummaryrefslogtreecommitdiffstats
path: root/tests
diff options
context:
space:
mode:
authorTianjie Xu2017-08-18 20:15:47 -0500
committerTianjie Xu2017-09-05 17:09:58 -0500
commit2903cddb58f6ee99116e0751a2305f75f9a86461 (patch)
tree22ad221cc46d846313c5ee4e83c36a6494b05beb /tests
parentdeb5de0bc144de9f62b0621d8a23db3415e4ac78 (diff)
downloadplatform-bootable-recovery-2903cddb58f6ee99116e0751a2305f75f9a86461.tar.gz
platform-bootable-recovery-2903cddb58f6ee99116e0751a2305f75f9a86461.tar.xz
platform-bootable-recovery-2903cddb58f6ee99116e0751a2305f75f9a86461.zip
Improve imgdiff for large zip files
Due to the cache size limit for OTA generation, we used to split large zip files linearly into pieces and do bsdiff on them. As a result, i) we lose the advantage of imgdiff; ii) if there's an accidental order change of some huge files inside the zip, we'll create an insanely large patch. This patch splits the src&tgt more smartly based on the zip entry_name. If the entry_name is empty or no matching source is found for a target chunk, we'll skip adding its source and later do a bsdiff against the whole split source image (this rarely happens in our use cases except for the metadata inside a ziparchive). After the split, the target pieces are continuous and block aligned, while the sources pieces are mutually exclusive. (Some of the source blocks may not be used if there's no matching entry_name in the target.) Then we will generate patches accordingly between each split image pairs. Afterwards, if we apply imgpatch to each pair of split source/target images and add up the patched result, we can get back the original target image. For example: Input: [src_image, tgt_image] Split: [src-0,tgt-0; src-1,tgt-1, src-2,tgt-2] Diff: [ patch-0; patch-1; patch-2] Patch: [(src-0,patch-0)=tgt-0; (src-1,patch-1)=tgt-1; (src-2,patch-2)=tgt-2;] Append: [tgt-0 + tgt-1 + tgt-2 = tgt_image] Peformance: For the small package in b/34220646, we decrease the patch size of chrome.apk dramatically from 30M to 400K due to the order change of two big .so files. On two versions of angler, I also observe decent patch size decrease. For chrome.apk, we reduced the size from 5.9M to 3.2M; and for vevlet.apk from 8.0M to 6.5M. Bug: 34220646 Test: recovery component test && apply imgdiff & imgpatch on two chrome.apk Change-Id: I145d802984fa805efbbac9d01a2e64d82ef9728b
Diffstat (limited to 'tests')
-rw-r--r--tests/component/imgdiff_test.cpp339
1 files changed, 334 insertions, 5 deletions
diff --git a/tests/component/imgdiff_test.cpp b/tests/component/imgdiff_test.cpp
index bf25aebb..3163a57c 100644
--- a/tests/component/imgdiff_test.cpp
+++ b/tests/component/imgdiff_test.cpp
@@ -16,13 +16,17 @@
16 16
17#include <stdio.h> 17#include <stdio.h>
18 18
19#include <algorithm>
19#include <string> 20#include <string>
21#include <tuple>
20#include <vector> 22#include <vector>
21 23
22#include <android-base/file.h> 24#include <android-base/file.h>
23#include <android-base/memory.h> 25#include <android-base/memory.h>
26#include <android-base/stringprintf.h>
24#include <android-base/test_utils.h> 27#include <android-base/test_utils.h>
25#include <applypatch/imgdiff.h> 28#include <applypatch/imgdiff.h>
29#include <applypatch/imgdiff_image.h>
26#include <applypatch/imgpatch.h> 30#include <applypatch/imgpatch.h>
27#include <gtest/gtest.h> 31#include <gtest/gtest.h>
28#include <ziparchive/zip_writer.h> 32#include <ziparchive/zip_writer.h>
@@ -75,15 +79,20 @@ static void verify_patch_header(const std::string& patch, size_t* num_normal, si
75 if (num_deflate != nullptr) *num_deflate = deflate; 79 if (num_deflate != nullptr) *num_deflate = deflate;
76} 80}
77 81
78static void verify_patched_image(const std::string& src, const std::string& patch, 82static void GenerateTarget(const std::string& src, const std::string& patch, std::string* patched) {
79 const std::string& tgt) { 83 patched->clear();
80 std::string patched;
81 ASSERT_EQ(0, ApplyImagePatch(reinterpret_cast<const unsigned char*>(src.data()), src.size(), 84 ASSERT_EQ(0, ApplyImagePatch(reinterpret_cast<const unsigned char*>(src.data()), src.size(),
82 reinterpret_cast<const unsigned char*>(patch.data()), patch.size(), 85 reinterpret_cast<const unsigned char*>(patch.data()), patch.size(),
83 [&patched](const unsigned char* data, size_t len) { 86 [&](const unsigned char* data, size_t len) {
84 patched.append(reinterpret_cast<const char*>(data), len); 87 patched->append(reinterpret_cast<const char*>(data), len);
85 return len; 88 return len;
86 })); 89 }));
90}
91
92static void verify_patched_image(const std::string& src, const std::string& patch,
93 const std::string& tgt) {
94 std::string patched;
95 GenerateTarget(src, patch, &patched);
87 ASSERT_EQ(tgt, patched); 96 ASSERT_EQ(tgt, patched);
88} 97}
89 98
@@ -623,3 +632,323 @@ TEST(ImgpatchTest, image_mode_patch_corruption) {
623 reinterpret_cast<const unsigned char*>(patch.data()), patch.size(), 632 reinterpret_cast<const unsigned char*>(patch.data()), patch.size(),
624 [](const unsigned char* /*data*/, size_t len) { return len; })); 633 [](const unsigned char* /*data*/, size_t len) { return len; }));
625} 634}
635
636static void construct_store_entry(const std::vector<std::tuple<std::string, size_t, char>>& info,
637 ZipWriter* writer) {
638 for (auto& t : info) {
639 // Create t(1) blocks of t(2), and write the data to t(0)
640 ASSERT_EQ(0, writer->StartEntry(std::get<0>(t).c_str(), 0));
641 const std::string content(std::get<1>(t) * 4096, std::get<2>(t));
642 ASSERT_EQ(0, writer->WriteBytes(content.data(), content.size()));
643 ASSERT_EQ(0, writer->FinishEntry());
644 }
645}
646
647static void construct_deflate_entry(const std::vector<std::tuple<std::string, size_t, size_t>>& info,
648 ZipWriter* writer, const std::string& data) {
649 for (auto& t : info) {
650 // t(0): entry_name; t(1): block offset; t(2) length in blocks.
651 ASSERT_EQ(0, writer->StartEntry(std::get<0>(t).c_str(), ZipWriter::kCompress));
652 ASSERT_EQ(0, writer->WriteBytes(data.data() + std::get<1>(t) * 4096, std::get<2>(t) * 4096));
653 ASSERT_EQ(0, writer->FinishEntry());
654 }
655}
656
657// Look for the generated source and patch pieces in the debug_dir and generate the target on
658// each pair. Concatenate the split target and match against the orignal one.
659static void GenerateAndCheckSplitTarget(const std::string& debug_dir, size_t count,
660 const std::string& tgt) {
661 std::string patched;
662 for (size_t i = 0; i < count; i++) {
663 std::string split_src_path = android::base::StringPrintf("%s/src-%zu", debug_dir.c_str(), i);
664 std::string split_patch_path = android::base::StringPrintf("%s/patch-%zu", debug_dir.c_str(), i);
665
666 std::string split_src;
667 std::string split_patch;
668 ASSERT_TRUE(android::base::ReadFileToString(split_src_path, &split_src));
669 ASSERT_TRUE(android::base::ReadFileToString(split_patch_path, &split_patch));
670
671 std::string split_tgt;
672 GenerateTarget(split_src, split_patch, &split_tgt);
673 patched += split_tgt;
674 }
675
676 // Verify we can get back the original target image.
677 ASSERT_EQ(tgt, patched);
678}
679
680std::vector<ImageChunk> ConstructImageChunks(
681 const std::vector<uint8_t>& content, const std::vector<std::tuple<std::string, size_t>>& info) {
682 std::vector<ImageChunk> chunks;
683 size_t start = 0;
684 for (const auto& t : info) {
685 size_t length = std::get<1>(t);
686 chunks.emplace_back(CHUNK_NORMAL, start, &content, length, std::get<0>(t));
687 start += length;
688 }
689
690 return chunks;
691}
692
693TEST(ImgdiffTest, zip_mode_split_image_smoke) {
694 std::vector<uint8_t> content;
695 content.reserve(4096 * 50);
696 uint8_t n = 0;
697 generate_n(back_inserter(content), 4096 * 50, [&n]() { return n++ / 4096; });
698
699 ZipModeImage tgt_image(false, 4096 * 10);
700 std::vector<ImageChunk> tgt_chunks = ConstructImageChunks(content, { { "a", 100 },
701 { "b", 4096 * 2 },
702 { "c", 4096 * 3 },
703 { "d", 300 },
704 { "e-0", 4096 * 10 },
705 { "e-1", 4096 * 5 },
706 { "CD", 200 } });
707 tgt_image.Initialize(std::move(tgt_chunks),
708 std::vector<uint8_t>(content.begin(), content.begin() + 82520));
709
710 tgt_image.DumpChunks();
711
712 ZipModeImage src_image(true, 4096 * 10);
713 std::vector<ImageChunk> src_chunks = ConstructImageChunks(content, { { "b", 4096 * 3 },
714 { "c-0", 4096 * 10 },
715 { "c-1", 4096 * 2 },
716 { "a", 4096 * 5 },
717 { "e-0", 4096 * 10 },
718 { "e-1", 10000 },
719 { "CD", 5000 } });
720 src_image.Initialize(std::move(src_chunks),
721 std::vector<uint8_t>(content.begin(), content.begin() + 137880));
722
723 std::vector<ZipModeImage> split_tgt_images;
724 std::vector<ZipModeImage> split_src_images;
725 std::vector<SortedRangeSet> split_src_ranges;
726
727 ZipModeImage::SplitZipModeImageWithLimit(tgt_image, src_image, &split_tgt_images,
728 &split_src_images, &split_src_ranges);
729
730 // src_piece 1: a 5 blocks, b 3 blocks
731 // src_piece 2: c-0 10 blocks
732 // src_piece 3: d 0 block, e-0 10 blocks
733 // src_piece 4: e-1 2 blocks; CD 2 blocks
734 ASSERT_EQ(split_tgt_images.size(), split_src_images.size());
735 ASSERT_EQ(static_cast<size_t>(4), split_tgt_images.size());
736
737 ASSERT_EQ(static_cast<size_t>(1), split_tgt_images[0].NumOfChunks());
738 ASSERT_EQ(static_cast<size_t>(12288), split_tgt_images[0][0].DataLengthForPatch());
739 ASSERT_EQ("4,0,3,15,20", split_src_ranges[0].ToString());
740
741 ASSERT_EQ(static_cast<size_t>(1), split_tgt_images[1].NumOfChunks());
742 ASSERT_EQ(static_cast<size_t>(12288), split_tgt_images[1][0].DataLengthForPatch());
743 ASSERT_EQ("2,3,13", split_src_ranges[1].ToString());
744
745 ASSERT_EQ(static_cast<size_t>(1), split_tgt_images[2].NumOfChunks());
746 ASSERT_EQ(static_cast<size_t>(40960), split_tgt_images[2][0].DataLengthForPatch());
747 ASSERT_EQ("2,20,30", split_src_ranges[2].ToString());
748
749 ASSERT_EQ(static_cast<size_t>(1), split_tgt_images[3].NumOfChunks());
750 ASSERT_EQ(static_cast<size_t>(16984), split_tgt_images[3][0].DataLengthForPatch());
751 ASSERT_EQ("2,30,34", split_src_ranges[3].ToString());
752}
753
754TEST(ImgdiffTest, zip_mode_store_large_apk) {
755 // Construct src and tgt zip files with limit = 10 blocks.
756 // src tgt
757 // 12 blocks 'd' 3 blocks 'a'
758 // 8 blocks 'c' 3 blocks 'b'
759 // 3 blocks 'b' 8 blocks 'c' (exceeds limit)
760 // 3 blocks 'a' 12 blocks 'd' (exceeds limit)
761 // 3 blocks 'e'
762 TemporaryFile tgt_file;
763 FILE* tgt_file_ptr = fdopen(tgt_file.fd, "wb");
764 ZipWriter tgt_writer(tgt_file_ptr);
765 construct_store_entry(
766 { { "a", 3, 'a' }, { "b", 3, 'b' }, { "c", 8, 'c' }, { "d", 12, 'd' }, { "e", 3, 'e' } },
767 &tgt_writer);
768 ASSERT_EQ(0, tgt_writer.Finish());
769 ASSERT_EQ(0, fclose(tgt_file_ptr));
770
771 TemporaryFile src_file;
772 FILE* src_file_ptr = fdopen(src_file.fd, "wb");
773 ZipWriter src_writer(src_file_ptr);
774 construct_store_entry({ { "d", 12, 'd' }, { "c", 8, 'c' }, { "b", 3, 'b' }, { "a", 3, 'a' } },
775 &src_writer);
776 ASSERT_EQ(0, src_writer.Finish());
777 ASSERT_EQ(0, fclose(src_file_ptr));
778
779 // Compute patch.
780 TemporaryFile patch_file;
781 TemporaryDir debug_dir;
782 std::vector<const char*> args = {
783 "imgdiff", "-z", "--block-limit=10", android::base::StringPrintf(
784 "--debug-dir=%s", debug_dir.path).c_str(), src_file.path, tgt_file.path, patch_file.path,
785 };
786 ASSERT_EQ(0, imgdiff(args.size(), args.data()));
787
788 std::string tgt;
789 ASSERT_TRUE(android::base::ReadFileToString(tgt_file.path, &tgt));
790
791 // Expect 4 pieces of patch.(Rougly 3'a',3'b'; 8'c'; 10'd'; 2'd'3'e')
792 GenerateAndCheckSplitTarget(debug_dir.path, 4, tgt);
793}
794
795TEST(ImgdiffTest, zip_mode_deflate_large_apk) {
796 // Generate 50 blocks of random data.
797 std::string random_data;
798 random_data.reserve(4096 * 50);
799 generate_n(back_inserter(random_data), 4096 * 50, []() { return rand() % 256; });
800
801 // Construct src and tgt zip files with limit = 10 blocks.
802 // src tgt
803 // 22 blocks, "d" 4 blocks, "a"
804 // 5 blocks, "b" 4 blocks, "b"
805 // 3 blocks, "a" 7 blocks, "c" (exceeds limit)
806 // 8 blocks, "c" 20 blocks, "d" (exceeds limit)
807 // 1 block, "f" 2 blocks, "e"
808 TemporaryFile tgt_file;
809 FILE* tgt_file_ptr = fdopen(tgt_file.fd, "wb");
810 ZipWriter tgt_writer(tgt_file_ptr);
811
812 construct_deflate_entry(
813 { { "a", 0, 4 }, { "b", 5, 4 }, { "c", 12, 8 }, { "d", 21, 20 }, { "e", 45, 2 },
814 { "f", 48, 1 } }, &tgt_writer, random_data);
815
816 ASSERT_EQ(0, tgt_writer.Finish());
817 ASSERT_EQ(0, fclose(tgt_file_ptr));
818
819 TemporaryFile src_file;
820 FILE* src_file_ptr = fdopen(src_file.fd, "wb");
821 ZipWriter src_writer(src_file_ptr);
822
823 construct_deflate_entry(
824 { { "d", 21, 22 }, { "b", 5, 5 }, { "a", 0, 3 }, { "g", 9, 1 }, { "c", 11, 8 },
825 { "f", 45, 1 } }, &src_writer, random_data);
826
827 ASSERT_EQ(0, src_writer.Finish());
828 ASSERT_EQ(0, fclose(src_file_ptr));
829
830 ZipModeImage src_image(true, 10 * 4096);
831 ZipModeImage tgt_image(false, 10 * 4096);
832 ASSERT_TRUE(src_image.Initialize(src_file.path));
833 ASSERT_TRUE(tgt_image.Initialize(tgt_file.path));
834 ASSERT_TRUE(ZipModeImage::CheckAndProcessChunks(&tgt_image, &src_image));
835
836 src_image.DumpChunks();
837 tgt_image.DumpChunks();
838
839 std::vector<ZipModeImage> split_tgt_images;
840 std::vector<ZipModeImage> split_src_images;
841 std::vector<SortedRangeSet> split_src_ranges;
842 ZipModeImage::SplitZipModeImageWithLimit(tgt_image, src_image, &split_tgt_images,
843 &split_src_images, &split_src_ranges);
844
845 // src_piece 1: a 3 blocks, b 5 blocks
846 // src_piece 2: c 8 blocks
847 // src_piece 3: d-0 10 block
848 // src_piece 4: d-1 10 blocks
849 // src_piece 5: e 1 block, CD
850 ASSERT_EQ(split_tgt_images.size(), split_src_images.size());
851 ASSERT_EQ(static_cast<size_t>(5), split_tgt_images.size());
852
853 ASSERT_EQ(static_cast<size_t>(2), split_src_images[0].NumOfChunks());
854 ASSERT_EQ("a", split_src_images[0][0].GetEntryName());
855 ASSERT_EQ("b", split_src_images[0][1].GetEntryName());
856
857 ASSERT_EQ(static_cast<size_t>(1), split_src_images[1].NumOfChunks());
858 ASSERT_EQ("c", split_src_images[1][0].GetEntryName());
859
860 ASSERT_EQ(static_cast<size_t>(0), split_src_images[2].NumOfChunks());
861 ASSERT_EQ(static_cast<size_t>(0), split_src_images[3].NumOfChunks());
862 ASSERT_EQ(static_cast<size_t>(0), split_src_images[4].NumOfChunks());
863
864 // Compute patch.
865 TemporaryFile patch_file;
866 TemporaryDir debug_dir;
867 ASSERT_TRUE(ZipModeImage::GeneratePatches(split_tgt_images, split_src_images, split_src_ranges,
868 patch_file.path, debug_dir.path));
869
870 std::string tgt;
871 ASSERT_TRUE(android::base::ReadFileToString(tgt_file.path, &tgt));
872
873 // Expect 5 pieces of patch. ["a","b"; "c"; "d-0"; "d-1"; "e"]
874 GenerateAndCheckSplitTarget(debug_dir.path, 5, tgt);
875}
876
877TEST(ImgdiffTest, zip_mode_no_match_source) {
878 // Generate 20 blocks of random data.
879 std::string random_data;
880 random_data.reserve(4096 * 20);
881 generate_n(back_inserter(random_data), 4096 * 20, []() { return rand() % 256; });
882
883 TemporaryFile tgt_file;
884 FILE* tgt_file_ptr = fdopen(tgt_file.fd, "wb");
885 ZipWriter tgt_writer(tgt_file_ptr);
886
887 construct_deflate_entry({ { "a", 0, 4 }, { "b", 5, 5 }, { "c", 11, 5 } }, &tgt_writer,
888 random_data);
889
890 ASSERT_EQ(0, tgt_writer.Finish());
891 ASSERT_EQ(0, fclose(tgt_file_ptr));
892
893 // We don't have a matching source entry.
894 TemporaryFile src_file;
895 FILE* src_file_ptr = fdopen(src_file.fd, "wb");
896 ZipWriter src_writer(src_file_ptr);
897 construct_store_entry({ { "d", 1, 'd' } }, &src_writer);
898 ASSERT_EQ(0, src_writer.Finish());
899 ASSERT_EQ(0, fclose(src_file_ptr));
900
901 // Compute patch.
902 TemporaryFile patch_file;
903 TemporaryDir debug_dir;
904 std::vector<const char*> args = {
905 "imgdiff", "-z", "--block-limit=10", android::base::StringPrintf(
906 "--debug-dir=%s", debug_dir.path).c_str(), src_file.path, tgt_file.path, patch_file.path,
907 };
908 ASSERT_EQ(0, imgdiff(args.size(), args.data()));
909
910 std::string tgt;
911 ASSERT_TRUE(android::base::ReadFileToString(tgt_file.path, &tgt));
912
913 // Expect 1 pieces of patch due to no matching source entry.
914 GenerateAndCheckSplitTarget(debug_dir.path, 1, tgt);
915}
916
917TEST(ImgdiffTest, zip_mode_large_enough_limit) {
918 // Generate 20 blocks of random data.
919 std::string random_data;
920 random_data.reserve(4096 * 20);
921 generate_n(back_inserter(random_data), 4096 * 20, []() { return rand() % 256; });
922
923 TemporaryFile tgt_file;
924 FILE* tgt_file_ptr = fdopen(tgt_file.fd, "wb");
925 ZipWriter tgt_writer(tgt_file_ptr);
926
927 construct_deflate_entry({ { "a", 0, 10 }, { "b", 10, 5 } }, &tgt_writer, random_data);
928
929 ASSERT_EQ(0, tgt_writer.Finish());
930 ASSERT_EQ(0, fclose(tgt_file_ptr));
931
932 // Construct 10 blocks of source.
933 TemporaryFile src_file;
934 FILE* src_file_ptr = fdopen(src_file.fd, "wb");
935 ZipWriter src_writer(src_file_ptr);
936 construct_deflate_entry({ { "a", 1, 10 } }, &src_writer, random_data);
937 ASSERT_EQ(0, src_writer.Finish());
938 ASSERT_EQ(0, fclose(src_file_ptr));
939
940 // Compute patch with a limit of 20 blocks.
941 TemporaryFile patch_file;
942 TemporaryDir debug_dir;
943 std::vector<const char*> args = {
944 "imgdiff", "-z", "--block-limit=20", android::base::StringPrintf(
945 "--debug-dir=%s", debug_dir.path).c_str(), src_file.path, tgt_file.path, patch_file.path,
946 };
947 ASSERT_EQ(0, imgdiff(args.size(), args.data()));
948
949 std::string tgt;
950 ASSERT_TRUE(android::base::ReadFileToString(tgt_file.path, &tgt));
951
952 // Expect 1 pieces of patch since limit is larger than the zip file size.
953 GenerateAndCheckSplitTarget(debug_dir.path, 1, tgt);
954}