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
11static constexpr uint32_t RELOCATION_GROUPED_BY_INFO_FLAG = 1;
12static constexpr uint32_t RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2;
13static constexpr uint32_t RELOCATION_GROUPED_BY_ADDEND_FLAG = 4;
14static constexpr uint32_t RELOCATION_GROUP_HAS_ADDEND_FLAG = 8;
15
16static bool is_relocation_grouped_by_info(uint64_t flags) {
17  return (flags & RELOCATION_GROUPED_BY_INFO_FLAG) != 0;
18}
19
20static bool is_relocation_grouped_by_offset_delta(uint64_t flags) {
21  return (flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0;
22}
23
24static bool is_relocation_grouped_by_addend(uint64_t flags) {
25  return (flags & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0;
26}
27
28static bool is_relocation_group_has_addend(uint64_t flags) {
29  return (flags & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0;
30}
31
32namespace relocation_packer {
33
34// Encode relocations into a delta encoded (packed) representation.
35template <typename ELF>
36void 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.
116template <typename ELF>
117void 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.
185template <typename ELF>
186void 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.
228static 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
247template <typename ELF>
248void 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
304template class RelocationDeltaCodec<ELF32_traits>;
305template class RelocationDeltaCodec<ELF64_traits>;
306
307}  // namespace relocation_packer
308