1 // Copyright 2014 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #include "delta_encoder.h" 6 7 #include <vector> 8 9 #include "debug.h" 10 11 static constexpr uint32_t RELOCATION_GROUPED_BY_INFO_FLAG = 1; 12 static constexpr uint32_t RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2; 13 static constexpr uint32_t RELOCATION_GROUPED_BY_ADDEND_FLAG = 4; 14 static constexpr uint32_t RELOCATION_GROUP_HAS_ADDEND_FLAG = 8; 15 16 static bool is_relocation_grouped_by_info(uint64_t flags) { 17 return (flags & RELOCATION_GROUPED_BY_INFO_FLAG) != 0; 18 } 19 20 static bool is_relocation_grouped_by_offset_delta(uint64_t flags) { 21 return (flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0; 22 } 23 24 static bool is_relocation_grouped_by_addend(uint64_t flags) { 25 return (flags & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0; 26 } 27 28 static bool is_relocation_group_has_addend(uint64_t flags) { 29 return (flags & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0; 30 } 31 32 namespace relocation_packer { 33 34 // Encode relocations into a delta encoded (packed) representation. 35 template <typename ELF> 36 void RelocationDeltaCodec<ELF>::Encode(const std::vector<ElfRela>& relocations, 37 std::vector<ElfAddr>* packed) { 38 if (relocations.size() == 0) 39 return; 40 41 // Start with the relocation count, then append groups 42 // TODO(dimitry): we might want to move it to DT_ANDROID_RELCOUNT section 43 packed->push_back(static_cast<ElfAddr>(relocations.size())); 44 45 // lets write starting offset (offset of the first reloc - first delta) 46 ElfAddr start_offset = relocations.size() > 1 ? 47 relocations[0].r_offset - (relocations[1].r_offset - relocations[0].r_offset) : 48 relocations[0].r_offset; 49 50 packed->push_back(start_offset); 51 52 // this one is used to calculate delta 53 ElfAddr previous_addend = 0; 54 ElfAddr previous_offset = start_offset; 55 56 for (size_t group_start = 0; group_start < relocations.size(); ) { 57 ElfAddr group_flags = 0; 58 ElfAddr group_offset_delta = 0; 59 ElfAddr group_addend = 0; 60 ElfAddr group_info = 0; 61 62 ElfAddr group_size = 0; 63 64 DetectGroup(relocations, group_start, previous_offset, &group_size, &group_flags, 65 &group_offset_delta, &group_info, &group_addend); 66 67 // write the group header 68 packed->push_back(group_size); 69 packed->push_back(group_flags); 70 71 if (is_relocation_grouped_by_offset_delta(group_flags)) { 72 packed->push_back(group_offset_delta); 73 } 74 75 if (is_relocation_grouped_by_info(group_flags)) { 76 packed->push_back(group_info); 77 } 78 79 if (is_relocation_group_has_addend(group_flags) && 80 is_relocation_grouped_by_addend(group_flags)) { 81 packed->push_back(group_addend - previous_addend); 82 previous_addend = group_addend; 83 } 84 85 for (size_t i = 0; i < static_cast<size_t>(group_size); ++i) { 86 CHECK((group_start + i) < relocations.size()); 87 const ElfRela* relocation = &relocations[group_start + i]; 88 89 if (!is_relocation_grouped_by_offset_delta(group_flags)) { 90 packed->push_back(relocation->r_offset - previous_offset); 91 } 92 previous_offset = relocation->r_offset; 93 94 if (!is_relocation_grouped_by_info(group_flags)) { 95 packed->push_back(relocation->r_info); 96 } 97 98 if (is_relocation_group_has_addend(group_flags) && 99 !is_relocation_grouped_by_addend(group_flags)) { 100 packed->push_back(relocation->r_addend - previous_addend); 101 previous_addend = relocation->r_addend; 102 } 103 } 104 105 // If the relocation group does not have an addend - reset it to 0 106 // to simplify addend computation for the group following this one. 107 if (!is_relocation_group_has_addend(group_flags)) { 108 previous_addend = 0; 109 } 110 111 group_start += group_size; 112 } 113 } 114 115 // Decode relocations from a delta encoded (packed) representation. 116 template <typename ELF> 117 void RelocationDeltaCodec<ELF>::Decode(const std::vector<ElfAddr>& packed, 118 std::vector<ElfRela>* relocations) { 119 if (packed.size() < 5) { 120 return; 121 } 122 123 size_t ndx = 0; 124 ElfAddr current_count = 0; 125 ElfAddr total_count = packed[ndx++]; 126 127 ElfAddr offset = packed[ndx++]; 128 ElfAddr info = 0; 129 ElfAddr addend = 0; 130 131 while(current_count < total_count) { 132 // read group 133 ElfAddr group_size = packed[ndx++]; 134 ElfAddr group_flags = packed[ndx++]; 135 ElfAddr group_offset_delta = 0; 136 137 if (is_relocation_grouped_by_offset_delta(group_flags)) { 138 group_offset_delta = packed[ndx++]; 139 } 140 141 if (is_relocation_grouped_by_info(group_flags)) { 142 info = packed[ndx++]; 143 } 144 145 if (is_relocation_group_has_addend(group_flags) && 146 is_relocation_grouped_by_addend(group_flags)) { 147 addend += packed[ndx++]; 148 } 149 150 // now read not grouped info 151 for (ElfAddr i = 0; i<group_size; ++i) { 152 if (is_relocation_grouped_by_offset_delta(group_flags)) { 153 offset += group_offset_delta; 154 } else { 155 offset += packed[ndx++]; 156 } 157 158 if (!is_relocation_grouped_by_info(group_flags)) { 159 info = packed[ndx++]; 160 } 161 162 if (is_relocation_group_has_addend(group_flags) && 163 !is_relocation_grouped_by_addend(group_flags)) { 164 addend += packed[ndx++]; 165 } 166 167 ElfRela reloc; 168 reloc.r_offset = offset; 169 reloc.r_info = info; 170 reloc.r_addend = is_relocation_group_has_addend(group_flags) ? addend : 0; 171 relocations->push_back(reloc); 172 } 173 174 if (!is_relocation_group_has_addend(group_flags)) { 175 addend = 0; 176 } 177 178 current_count += group_size; 179 } 180 } 181 182 // This function detects a way to group reloc_one and reloc_two, sets up group_flags 183 // and initializes values for corresponding group_ fields. For example if relocations 184 // can be grouped by r_info the function will set group_info variable. 185 template <typename ELF> 186 void RelocationDeltaCodec<ELF>::DetectGroupFields(const ElfRela& reloc_one, 187 const ElfRela& reloc_two, 188 ElfAddr current_offset_delta, 189 ElfAddr* group_flags, 190 ElfAddr* group_offset_delta, 191 ElfAddr* group_info, 192 ElfAddr* group_addend) { 193 *group_flags = 0; 194 195 const ElfAddr offset_delta = static_cast<ElfAddr>(reloc_two.r_offset) - 196 static_cast<ElfAddr>(reloc_one.r_offset); 197 198 if (offset_delta == current_offset_delta) { 199 *group_flags |= RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG; 200 if (group_offset_delta != nullptr) { 201 *group_offset_delta = current_offset_delta; 202 } 203 } 204 205 if (reloc_one.r_info == reloc_two.r_info) { 206 *group_flags |= RELOCATION_GROUPED_BY_INFO_FLAG; 207 if (group_info != nullptr) { 208 *group_info = reloc_one.r_info; 209 } 210 } 211 212 if (reloc_one.r_addend != 0 || reloc_two.r_addend != 0) { 213 *group_flags |= RELOCATION_GROUP_HAS_ADDEND_FLAG; 214 if (reloc_one.r_addend == reloc_two.r_addend) { 215 *group_flags |= RELOCATION_GROUPED_BY_ADDEND_FLAG; 216 if (group_addend != nullptr) { 217 *group_addend = reloc_one.r_addend; 218 } 219 } 220 } 221 } 222 223 // This function is used to detect if there is better group available 224 // during RelocationDeltaCodec<ELF>::DetectGroup processing. 225 // Current implementation prefers having groups without addend (== zero addend) 226 // to any other groups field with the ratio 3:1. This is because addend tends 227 // to be more unevenly distributed than other fields. 228 static uint32_t group_weight(uint64_t flags) { 229 uint32_t weight = 0; 230 if (!is_relocation_group_has_addend(flags)) { 231 weight += 3; 232 } else if (is_relocation_grouped_by_addend(flags)) { 233 weight += 1; 234 } 235 236 if (is_relocation_grouped_by_offset_delta(flags)) { 237 weight += 1; 238 } 239 240 if (is_relocation_grouped_by_info(flags)) { 241 weight += 1; 242 } 243 244 return weight; 245 } 246 247 template <typename ELF> 248 void RelocationDeltaCodec<ELF>::DetectGroup(const std::vector<ElfRela>& relocations, 249 size_t group_starts_with, ElfAddr previous_offset, 250 ElfAddr* group_size, ElfAddr* group_flags, 251 ElfAddr* group_offset_delta, ElfAddr* group_info, 252 ElfAddr* group_addend) { 253 CHECK(group_starts_with < relocations.size()); 254 CHECK(group_flags != nullptr); 255 256 const ElfRela& reloc_one = relocations[group_starts_with++]; 257 if (group_starts_with == relocations.size()) { 258 *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG; 259 *group_size = 1; 260 return; 261 } 262 263 const ElfAddr offset_delta = reloc_one.r_offset - previous_offset; 264 265 // detect group_flags 266 DetectGroupFields(reloc_one, relocations[group_starts_with], offset_delta, group_flags, 267 group_offset_delta, group_info, group_addend); 268 269 if (group_starts_with + 1 == relocations.size()) { 270 *group_size = 2; 271 return; 272 } 273 274 ElfAddr cnt = 1; 275 for (size_t i = group_starts_with; i < relocations.size() - 1; ++i) { 276 ElfAddr candidate_flags; 277 // check if next group (reloc_current; reloc_next) has better grouped_by flags 278 DetectGroupFields(relocations[i], relocations[i+1], offset_delta, &candidate_flags, 279 nullptr, nullptr, nullptr); 280 281 if (group_weight(*group_flags) < group_weight(candidate_flags)) { 282 break; 283 } 284 cnt++; 285 286 if (candidate_flags != *group_flags) { 287 break; 288 } 289 290 if (i + 1 == relocations.size() - 1) { // last one 291 cnt++; 292 } 293 } 294 295 // if as a result of checking candidates we ended up with cnt == 1 296 // reset flags to the default state 297 if (cnt == 1) { 298 *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG; 299 } 300 301 *group_size = cnt; 302 } 303 304 template class RelocationDeltaCodec<ELF32_traits>; 305 template class RelocationDeltaCodec<ELF64_traits>; 306 307 } // namespace relocation_packer 308
