1 /*
2 * Copyright (C) 2019 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "deploy_patch_generator.h"
18
19 #include <inttypes.h>
20 #include <stdio.h>
21
22 #include <algorithm>
23 #include <fstream>
24 #include <functional>
25 #include <iostream>
26 #include <sstream>
27 #include <string>
28 #include <unordered_map>
29
30 #include <openssl/md5.h>
31
32 #include "adb_unique_fd.h"
33 #include "adb_utils.h"
34 #include "android-base/file.h"
35 #include "patch_utils.h"
36 #include "sysdeps.h"
37
38 using namespace com::android::fastdeploy;
39
Log(const char * fmt,...)40 void DeployPatchGenerator::Log(const char* fmt, ...) {
41 va_list ap;
42 va_start(ap, fmt);
43 vprintf(fmt, ap);
44 printf("\n");
45 va_end(ap);
46 }
47
HexEncode(const void * in_buffer,unsigned int size)48 static std::string HexEncode(const void* in_buffer, unsigned int size) {
49 static const char kHexChars[] = "0123456789ABCDEF";
50
51 // Each input byte creates two output hex characters.
52 std::string out_buffer(size * 2, '\0');
53
54 for (unsigned int i = 0; i < size; ++i) {
55 char byte = ((const uint8_t*)in_buffer)[i];
56 out_buffer[(i << 1)] = kHexChars[(byte >> 4) & 0xf];
57 out_buffer[(i << 1) + 1] = kHexChars[byte & 0xf];
58 }
59 return out_buffer;
60 }
61
APKEntryToLog(const APKEntry & entry)62 void DeployPatchGenerator::APKEntryToLog(const APKEntry& entry) {
63 if (!is_verbose_) {
64 return;
65 }
66 Log("MD5: %s", HexEncode(entry.md5().data(), entry.md5().size()).c_str());
67 Log("Data Offset: %" PRId64, entry.dataoffset());
68 Log("Data Size: %" PRId64, entry.datasize());
69 }
70
APKMetaDataToLog(const APKMetaData & metadata)71 void DeployPatchGenerator::APKMetaDataToLog(const APKMetaData& metadata) {
72 if (!is_verbose_) {
73 return;
74 }
75 Log("APK Metadata: %s", metadata.absolute_path().c_str());
76 for (int i = 0; i < metadata.entries_size(); i++) {
77 const APKEntry& entry = metadata.entries(i);
78 APKEntryToLog(entry);
79 }
80 }
81
ReportSavings(const std::vector<SimpleEntry> & identicalEntries,uint64_t totalSize)82 void DeployPatchGenerator::ReportSavings(const std::vector<SimpleEntry>& identicalEntries,
83 uint64_t totalSize) {
84 uint64_t totalEqualBytes = 0;
85 uint64_t totalEqualFiles = 0;
86 for (size_t i = 0; i < identicalEntries.size(); i++) {
87 if (identicalEntries[i].deviceEntry != nullptr) {
88 totalEqualBytes += identicalEntries[i].localEntry->datasize();
89 totalEqualFiles++;
90 }
91 }
92 double savingPercent = (totalEqualBytes * 100.0f) / totalSize;
93 fprintf(stderr, "Detected %" PRIu64 " equal APK entries\n", totalEqualFiles);
94 fprintf(stderr, "%" PRIu64 " bytes are equal out of %" PRIu64 " (%.2f%%)\n", totalEqualBytes,
95 totalSize, savingPercent);
96 }
97
98 struct PatchEntry {
99 int64_t deltaFromDeviceDataStart = 0;
100 int64_t deviceDataOffset = 0;
101 int64_t deviceDataLength = 0;
102 };
WritePatchEntry(const PatchEntry & patchEntry,borrowed_fd input,borrowed_fd output,size_t * realSizeOut)103 static void WritePatchEntry(const PatchEntry& patchEntry, borrowed_fd input, borrowed_fd output,
104 size_t* realSizeOut) {
105 if (!(patchEntry.deltaFromDeviceDataStart | patchEntry.deviceDataOffset |
106 patchEntry.deviceDataLength)) {
107 return;
108 }
109
110 PatchUtils::WriteLong(patchEntry.deltaFromDeviceDataStart, output);
111 if (patchEntry.deltaFromDeviceDataStart > 0) {
112 PatchUtils::Pipe(input, output, patchEntry.deltaFromDeviceDataStart);
113 }
114 auto hostDataLength = patchEntry.deviceDataLength;
115 adb_lseek(input, hostDataLength, SEEK_CUR);
116
117 PatchUtils::WriteLong(patchEntry.deviceDataOffset, output);
118 PatchUtils::WriteLong(patchEntry.deviceDataLength, output);
119
120 *realSizeOut += patchEntry.deltaFromDeviceDataStart + hostDataLength;
121 }
122
GeneratePatch(const std::vector<SimpleEntry> & entriesToUseOnDevice,const std::string & localApkPath,const std::string & deviceApkPath,borrowed_fd output)123 void DeployPatchGenerator::GeneratePatch(const std::vector<SimpleEntry>& entriesToUseOnDevice,
124 const std::string& localApkPath,
125 const std::string& deviceApkPath, borrowed_fd output) {
126 unique_fd input(adb_open(localApkPath.c_str(), O_RDONLY | O_CLOEXEC));
127 size_t newApkSize = adb_lseek(input, 0L, SEEK_END);
128 adb_lseek(input, 0L, SEEK_SET);
129
130 // Header.
131 PatchUtils::WriteSignature(output);
132 PatchUtils::WriteLong(newApkSize, output);
133 PatchUtils::WriteString(deviceApkPath, output);
134
135 size_t currentSizeOut = 0;
136 size_t realSizeOut = 0;
137 // Write data from the host upto the first entry we have that matches a device entry. Then write
138 // the metadata about the device entry and repeat for all entries that match on device. Finally
139 // write out any data left. If the device and host APKs are exactly the same this ends up
140 // writing out zip metadata from the local APK followed by offsets to the data to use from the
141 // device APK.
142 PatchEntry patchEntry;
143 for (size_t i = 0, size = entriesToUseOnDevice.size(); i < size; ++i) {
144 auto&& entry = entriesToUseOnDevice[i];
145 int64_t hostDataOffset = entry.localEntry->dataoffset();
146 int64_t hostDataLength = entry.localEntry->datasize();
147 int64_t deviceDataOffset = entry.deviceEntry->dataoffset();
148 // Both entries are the same, using host data length.
149 int64_t deviceDataLength = hostDataLength;
150
151 int64_t deltaFromDeviceDataStart = hostDataOffset - currentSizeOut;
152 if (deltaFromDeviceDataStart > 0) {
153 WritePatchEntry(patchEntry, input, output, &realSizeOut);
154 patchEntry.deltaFromDeviceDataStart = deltaFromDeviceDataStart;
155 patchEntry.deviceDataOffset = deviceDataOffset;
156 patchEntry.deviceDataLength = deviceDataLength;
157 } else {
158 patchEntry.deviceDataLength += deviceDataLength;
159 }
160
161 currentSizeOut += deltaFromDeviceDataStart + hostDataLength;
162 }
163 WritePatchEntry(patchEntry, input, output, &realSizeOut);
164 if (realSizeOut != currentSizeOut) {
165 fprintf(stderr, "Size mismatch current %lld vs real %lld\n",
166 static_cast<long long>(currentSizeOut), static_cast<long long>(realSizeOut));
167 error_exit("Aborting");
168 }
169
170 if (newApkSize > currentSizeOut) {
171 PatchUtils::WriteLong(newApkSize - currentSizeOut, output);
172 PatchUtils::Pipe(input, output, newApkSize - currentSizeOut);
173 PatchUtils::WriteLong(0, output);
174 PatchUtils::WriteLong(0, output);
175 }
176 }
177
CreatePatch(const char * localApkPath,APKMetaData deviceApkMetadata,android::base::borrowed_fd output)178 bool DeployPatchGenerator::CreatePatch(const char* localApkPath, APKMetaData deviceApkMetadata,
179 android::base::borrowed_fd output) {
180 return CreatePatch(PatchUtils::GetHostAPKMetaData(localApkPath), std::move(deviceApkMetadata),
181 output);
182 }
183
CreatePatch(APKMetaData localApkMetadata,APKMetaData deviceApkMetadata,borrowed_fd output)184 bool DeployPatchGenerator::CreatePatch(APKMetaData localApkMetadata, APKMetaData deviceApkMetadata,
185 borrowed_fd output) {
186 // Log metadata info.
187 APKMetaDataToLog(deviceApkMetadata);
188 APKMetaDataToLog(localApkMetadata);
189
190 const std::string localApkPath = localApkMetadata.absolute_path();
191 const std::string deviceApkPath = deviceApkMetadata.absolute_path();
192
193 std::vector<SimpleEntry> identicalEntries;
194 uint64_t totalSize =
195 BuildIdenticalEntries(identicalEntries, localApkMetadata, deviceApkMetadata);
196 ReportSavings(identicalEntries, totalSize);
197 GeneratePatch(identicalEntries, localApkPath, deviceApkPath, output);
198
199 return true;
200 }
201
BuildIdenticalEntries(std::vector<SimpleEntry> & outIdenticalEntries,const APKMetaData & localApkMetadata,const APKMetaData & deviceApkMetadata)202 uint64_t DeployPatchGenerator::BuildIdenticalEntries(std::vector<SimpleEntry>& outIdenticalEntries,
203 const APKMetaData& localApkMetadata,
204 const APKMetaData& deviceApkMetadata) {
205 outIdenticalEntries.reserve(
206 std::min(localApkMetadata.entries_size(), deviceApkMetadata.entries_size()));
207
208 using md5Digest = std::pair<uint64_t, uint64_t>;
209 struct md5Hash {
210 size_t operator()(const md5Digest& digest) const {
211 std::hash<uint64_t> hasher;
212 size_t seed = 0;
213 seed ^= hasher(digest.first) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
214 seed ^= hasher(digest.second) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
215 return seed;
216 }
217 };
218 static_assert(sizeof(md5Digest) == MD5_DIGEST_LENGTH);
219 std::unordered_map<md5Digest, std::vector<const APKEntry*>, md5Hash> deviceEntries;
220 for (const auto& deviceEntry : deviceApkMetadata.entries()) {
221 md5Digest md5;
222 memcpy(&md5, deviceEntry.md5().data(), deviceEntry.md5().size());
223
224 deviceEntries[md5].push_back(&deviceEntry);
225 }
226
227 uint64_t totalSize = 0;
228 for (const auto& localEntry : localApkMetadata.entries()) {
229 totalSize += localEntry.datasize();
230
231 md5Digest md5;
232 memcpy(&md5, localEntry.md5().data(), localEntry.md5().size());
233
234 auto deviceEntriesIt = deviceEntries.find(md5);
235 if (deviceEntriesIt == deviceEntries.end()) {
236 continue;
237 }
238
239 for (const auto* deviceEntry : deviceEntriesIt->second) {
240 if (deviceEntry->md5() == localEntry.md5()) {
241 SimpleEntry simpleEntry;
242 simpleEntry.localEntry = &localEntry;
243 simpleEntry.deviceEntry = deviceEntry;
244 APKEntryToLog(localEntry);
245 outIdenticalEntries.push_back(simpleEntry);
246 break;
247 }
248 }
249 }
250 std::sort(outIdenticalEntries.begin(), outIdenticalEntries.end(),
251 [](const SimpleEntry& lhs, const SimpleEntry& rhs) {
252 return lhs.localEntry->dataoffset() < rhs.localEntry->dataoffset();
253 });
254 return totalSize;
255 }
256