diff options
| author | Dmitriy Ivanov <dimitry@google.com> | 2015-01-27 19:32:56 -0800 |
|---|---|---|
| committer | Dmitriy Ivanov <dimitry@google.com> | 2015-03-06 13:01:08 -0800 |
| commit | f8ff6b103bde3433d6f7dbf762fc7bf657d7de5f (patch) | |
| tree | fbff9b4213a98a600b559a67f3fc4da8b972294c /tools | |
| parent | 87a0617ebe7561bf28d3a19fbe192372598969b8 (diff) | |
| download | bionic-f8ff6b103bde3433d6f7dbf762fc7bf657d7de5f.zip bionic-f8ff6b103bde3433d6f7dbf762fc7bf657d7de5f.tar.gz bionic-f8ff6b103bde3433d6f7dbf762fc7bf657d7de5f.tar.bz2 | |
Generalize compression tool
1. One binary for all architectures
2. Generalize (and slightly improve) compression
2.1 works on all relocation types (rela?.dyn section only so far)
2.2 Uses same format to encode ElfW(Rel) as well as ElfW(Rela) tables
Bug: 18051137
Change-Id: I66c95d9076954ca115816fc577d0f5ef274e5e72
Diffstat (limited to 'tools')
28 files changed, 1599 insertions, 2091 deletions
diff --git a/tools/Android.mk b/tools/Android.mk new file mode 100644 index 0000000..4dd66fe --- /dev/null +++ b/tools/Android.mk @@ -0,0 +1,19 @@ +# +# Copyright (C) 2015 The Android Open Source Project +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +# + +LOCAL_PATH := $(call my-dir) + +include $(call all-subdir-makefiles) diff --git a/tools/relocation_packer/Android.mk b/tools/relocation_packer/Android.mk new file mode 100644 index 0000000..99a39c0 --- /dev/null +++ b/tools/relocation_packer/Android.mk @@ -0,0 +1,96 @@ +# +# Copyright (C) 2015 The Android Open Source Project +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. +# + +common_cppflags := -Wall -Wextra -Wunused -Werror -Wold-style-cast + +LOCAL_PATH := $(call my-dir) + +include $(CLEAR_VARS) + +LOCAL_CPP_EXTENSION := .cc + +LOCAL_SRC_FILES := \ + src/debug.cc \ + src/delta_encoder.cc \ + src/elf_file.cc \ + src/leb128.cc \ + src/packer.cc \ + src/sleb128.cc \ + +LOCAL_STATIC_LIBRARIES := libelf +LOCAL_C_INCLUDES := external/elfutils/src/libelf +LOCAL_MODULE := lib_relocation_packer + +LOCAL_CPPFLAGS := $(common_cppflags) + +LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk + +include $(BUILD_HOST_STATIC_LIBRARY) + +include $(CLEAR_VARS) + +LOCAL_CPP_EXTENSION := .cc + +LOCAL_SRC_FILES := src/main.cc +LOCAL_STATIC_LIBRARIES := lib_relocation_packer libelf +LOCAL_C_INCLUDES := external/elfutils/src/libelf libnativehelper/include + +LOCAL_MODULE := relocation_packer + +LOCAL_CPPFLAGS := $(common_cppflags) + +LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk + +include $(BUILD_HOST_EXECUTABLE) + +include $(CLEAR_VARS) + +LOCAL_CPP_EXTENSION := .cc + +LOCAL_SRC_FILES := \ + src/debug_unittest.cc \ + src/delta_encoder_unittest.cc \ + src/elf_file_unittest.cc \ + src/leb128_unittest.cc \ + src/sleb128_unittest.cc \ + src/packer_unittest.cc \ + +LOCAL_STATIC_LIBRARIES := lib_relocation_packer libelf +LOCAL_C_INCLUDES := external/elfutils/src/libelf + +LOCAL_CPPFLAGS := $(common_cppflags) + +LOCAL_MODULE := relocation_packer_unit_tests +LOCAL_ADDITIONAL_DEPENDENCIES := $(LOCAL_PATH)/Android.mk + +include $(BUILD_HOST_NATIVE_TEST) + +# $(1) library name +define copy-test-library +include $(CLEAR_VARS) +LOCAL_IS_HOST_MODULE := true +LOCAL_MODULE := $(1) +LOCAL_MODULE_CLASS := SHARED_LIBRARIES +LOCAL_MODULE_PATH := $(HOST_OUT_EXECUTABLES) +LOCAL_STRIP_MODULE := false +LOCAL_SRC_FILES := test_data/$(1) +include $(BUILD_PREBUILT) +endef + +$(eval $(call copy-test-library,elf_file_unittest_relocs_arm32.so)) +$(eval $(call copy-test-library,elf_file_unittest_relocs_arm32_packed.so)) +$(eval $(call copy-test-library,elf_file_unittest_relocs_arm64.so)) +$(eval $(call copy-test-library,elf_file_unittest_relocs_arm64_packed.so)) diff --git a/tools/relocation_packer/BUILD.gn b/tools/relocation_packer/BUILD.gn deleted file mode 100644 index 0b29c91..0000000 --- a/tools/relocation_packer/BUILD.gn +++ /dev/null @@ -1,148 +0,0 @@ -# Copyright 2014 The Chromium Authors. All rights reserved. -# Use of this source code is governed by a BSD-style license that can be -# found in the LICENSE file. - -import("config.gni") -import("//testing/test.gni") - -assert(relocation_packing_supported) - -if (target_arch == "arm") { - target_define = "TARGET_ARM" -} else if (target_arch == "arm64") { - target_define = "TARGET_ARM64" -} - -if (current_toolchain == host_toolchain) { - # GYP: //tools/relocation_packer/relocation_packer.gyp:lib_relocation_packer - source_set("lib_relocation_packer") { - defines = [ target_define ] - deps = [ - "//third_party/elfutils:libelf", - ] - configs -= [ "//build/config/compiler:chromium_code" ] - configs += [ "//build/config/compiler:no_chromium_code" ] - sources = [ - "src/debug.cc", - "src/delta_encoder.cc", - "src/elf_file.cc", - "src/leb128.cc", - "src/packer.cc", - "src/sleb128.cc", - "src/run_length_encoder.cc", - ] - } - - # GYP: //tools/relocation_packer/relocation_packer.gyp:relocation_packer - executable("relocation_packer") { - defines = [ target_define ] - deps = [ - ":lib_relocation_packer", - "//third_party/elfutils:libelf", - ] - sources = [ - "src/main.cc", - ] - } - - # GYP: //tools/relocation_packer/relocation_packer.gyp:relocation_packer_unittests - test("relocation_packer_unittests") { - sources = [ - "src/debug_unittest.cc", - "src/delta_encoder_unittest.cc", - "src/elf_file_unittest.cc", - "src/leb128_unittest.cc", - "src/packer_unittest.cc", - "src/sleb128_unittest.cc", - "src/run_length_encoder_unittest.cc", - "src/run_all_unittests.cc", - ] - rebased_test_data = rebase_path("test_data", root_build_dir) - data = [ - "test_data/elf_file_unittest_relocs_arm32.so", - "test_data/elf_file_unittest_relocs_arm32_packed.so", - "test_data/elf_file_unittest_relocs_arm64.so", - "test_data/elf_file_unittest_relocs_arm64_packed.so", - ] - defines = [ - target_define, - "INTERMEDIATE_DIR=\"$rebased_test_data\"", - ] - include_dirs = [ "//" ] - deps = [ - ":lib_relocation_packer", - ":relocation_packer_test_data", - "//testing:gtest", - ] - } -} - -if (current_toolchain == default_toolchain && - (target_arch == "arm" || target_arch == "arm64")) { - # Targets to build test data. These participate only in building test - # data for use with elf_file_unittest.cc, and are not part of the main - # relocation packer build. Unit test data files are checked in to the - # source tree as 'golden' data, and are not generated 'on the fly' by - # the build. - # - # See test_data/generate_elf_file_unittest_relocs.sh for instructions. - - # GYP: //tools/relocation_packer/relocation_packer.gyp:relocation_packer_test_data - shared_library("relocation_packer_test_data") { - cflags = [ - "-O0", - "-g0", - ] - sources = [ - "test_data/elf_file_unittest_relocs.cc", - ] - } - - # GYP: //tools/relocation_packer/relocation_packer.gyp:relocation_packer_unittests_test_data - action("relocation_packer_unittests_test_data") { - script = "test_data/generate_elf_file_unittest_relocs.py" - test_file = "$root_build_dir/librelocation_packer_test_data.so" - if (target_arch == "arm") { - added_section = ".android.rel.dyn" - packed_output = "elf_file_unittest_relocs_arm32_packed.so" - unpacked_output = "elf_file_unittest_relocs_arm32.so" - } else if (target_arch == "arm64") { - added_section = ".android.rela.dyn" - packed_output = "elf_file_unittest_relocs_arm64_packed.so" - unpacked_output = "elf_file_unittest_relocs_arm64.so" - } else { - assert(false, "Unsupported target arch for relocation packer") - } - - packed_output = "$root_build_dir/$packed_output" - unpacked_output = "$root_build_dir/$unpacked_output" - - inputs = [ - test_file, - ] - - deps = [ - ":relocation_packer_test_data", - ":relocation_packer($host_toolchain)", - ] - - outputs = [ - packed_output, - unpacked_output, - ] - - args = [ - "--android-pack-relocations", - rebase_path(relocation_packer_exe, root_build_dir), - "--android-objcopy", - rebase_path(android_objcopy, root_build_dir), - "--added-section=$added_section", - "--test-file", - rebase_path(test_file, root_build_dir), - "--packed-output", - rebase_path(packed_output, root_build_dir), - "--unpacked-output", - rebase_path(unpacked_output, root_build_dir), - ] - } -} diff --git a/tools/relocation_packer/config.gni b/tools/relocation_packer/config.gni deleted file mode 100644 index 90e3979..0000000 --- a/tools/relocation_packer/config.gni +++ /dev/null @@ -1,21 +0,0 @@ -# Copyright 2014 The Chromium Authors. All rights reserved. -# Use of this source code is governed by a BSD-style license that can be -# found in the LICENSE file. - -relocation_packing_supported = target_arch == "arm" || target_arch == "arm64" - -if (relocation_packing_supported) { - relocation_packer_target = "//tools/relocation_packer($host_toolchain)" - relocation_packer_dir = - get_label_info("$relocation_packer_target", "root_out_dir") - relocation_packer_exe = "${relocation_packer_dir}/relocation_packer" - - if (target_arch == "arm") { - relocations_have_addends = 0 - } else if (target_arch == "arm64") { - relocations_have_addends = 1 - } -} else { - relocations_have_addends = 0 - relocation_packer_exe = "" -} diff --git a/tools/relocation_packer/relocation_packer.gyp b/tools/relocation_packer/relocation_packer.gyp deleted file mode 100644 index 1e9c1b9..0000000 --- a/tools/relocation_packer/relocation_packer.gyp +++ /dev/null @@ -1,161 +0,0 @@ -# Copyright 2014 The Chromium Authors. All rights reserved. -# Use of this source code is governed by a BSD-style license that can be -# found in the LICENSE file. - -{ - 'variables': { - 'target_define%': 'TARGET_UNSUPPORTED', - 'conditions': [ - [ 'target_arch == "arm"', { - 'target_define': 'TARGET_ARM', - }], - [ 'target_arch == "arm64"', { - 'target_define': 'TARGET_ARM64', - }], - ], - }, - 'targets': [ - { - # GN: //tools/relocation_packer:lib_relocation_packer - 'target_name': 'lib_relocation_packer', - 'toolsets': ['host'], - 'type': 'static_library', - 'defines': [ - '<(target_define)', - ], - 'dependencies': [ - '../../third_party/elfutils/elfutils.gyp:libelf', - ], - 'sources': [ - 'src/debug.cc', - 'src/delta_encoder.cc', - 'src/elf_file.cc', - 'src/leb128.cc', - 'src/packer.cc', - 'src/sleb128.cc', - 'src/run_length_encoder.cc', - ], - }, - { - # GN: //tools/relocation_packer:relocation_packer - 'target_name': 'relocation_packer', - 'toolsets': ['host'], - 'type': 'executable', - 'defines': [ - '<(target_define)', - ], - 'dependencies': [ - '../../third_party/elfutils/elfutils.gyp:libelf', - 'lib_relocation_packer', - ], - 'sources': [ - 'src/main.cc', - ], - }, - { - # GN: //tools/relocation_packer:relocation_packer_unittests - 'target_name': 'relocation_packer_unittests', - 'toolsets': ['host'], - 'type': 'executable', - 'defines': [ - '<(target_define)', - ], - 'cflags': [ - '-DINTERMEDIATE_DIR="<(INTERMEDIATE_DIR)"', - ], - 'dependencies': [ - '../../testing/gtest.gyp:gtest', - 'lib_relocation_packer', - ], - 'include_dirs': [ - '../..', - ], - 'sources': [ - 'src/debug_unittest.cc', - 'src/delta_encoder_unittest.cc', - 'src/elf_file_unittest.cc', - 'src/leb128_unittest.cc', - 'src/packer_unittest.cc', - 'src/sleb128_unittest.cc', - 'src/run_length_encoder_unittest.cc', - 'src/run_all_unittests.cc', - ], - 'copies': [ - { - 'destination': '<(INTERMEDIATE_DIR)', - 'files': [ - 'test_data/elf_file_unittest_relocs_arm32.so', - 'test_data/elf_file_unittest_relocs_arm32_packed.so', - 'test_data/elf_file_unittest_relocs_arm64.so', - 'test_data/elf_file_unittest_relocs_arm64_packed.so', - ], - }, - ], - }, - - # Targets to build test data. These participate only in building test - # data for use with elf_file_unittest.cc, and are not part of the main - # relocation packer build. Unit test data files are checked in to the - # source tree as 'golden' data, and are not generated 'on the fly' by - # the build. - # - # See test_data/generate_elf_file_unittest_relocs.sh for instructions. - { - # GN: //tools/relocation_packer:relocation_packer_test_data - 'target_name': 'relocation_packer_test_data', - 'toolsets': ['target'], - 'type': 'shared_library', - 'cflags': [ - '-O0', - '-g0', - ], - 'sources': [ - 'test_data/elf_file_unittest_relocs.cc', - ], - }, - { - # GN: //tools/relocation_packer:relocation_packer_unittests_test_data - 'target_name': 'relocation_packer_unittests_test_data', - 'toolsets': ['target'], - 'type': 'none', - 'actions': [ - { - 'variables': { - 'test_file': '<(SHARED_LIB_DIR)/librelocation_packer_test_data.so', - 'conditions': [ - [ 'target_arch == "arm"', { - 'added_section': '.android.rel.dyn', - 'unpacked_output': 'elf_file_unittest_relocs_arm32.so', - 'packed_output': 'elf_file_unittest_relocs_arm32_packed.so', - }], - [ 'target_arch == "arm64"', { - 'added_section': '.android.rela.dyn', - 'unpacked_output': 'elf_file_unittest_relocs_arm64.so', - 'packed_output': 'elf_file_unittest_relocs_arm64_packed.so', - }], - ], - }, - 'action_name': 'generate_relocation_packer_test_data', - 'inputs': [ - 'test_data/generate_elf_file_unittest_relocs.py', - '<(PRODUCT_DIR)/relocation_packer', - '<(test_file)', - ], - 'outputs': [ - '<(INTERMEDIATE_DIR)/<(unpacked_output)', - '<(INTERMEDIATE_DIR)/<(packed_output)', - ], - 'action': [ - 'python', 'test_data/generate_elf_file_unittest_relocs.py', - '--android-pack-relocations=<(PRODUCT_DIR)/relocation_packer', - '--android-objcopy=<(android_objcopy)', - '--added-section=<(added_section)', - '--test-file=<(test_file)', - '--unpacked-output=<(INTERMEDIATE_DIR)/<(unpacked_output)', - '--packed-output=<(INTERMEDIATE_DIR)/<(packed_output)', - ], - }, - ], - }, - ], -} diff --git a/tools/relocation_packer/src/debug_unittest.cc b/tools/relocation_packer/src/debug_unittest.cc index 1b65cd1..b31e2ae 100644 --- a/tools/relocation_packer/src/debug_unittest.cc +++ b/tools/relocation_packer/src/debug_unittest.cc @@ -5,7 +5,7 @@ #include "debug.h" #include <sstream> -#include "testing/gtest/include/gtest/gtest.h" +#include "gtest/gtest.h" namespace relocation_packer { diff --git a/tools/relocation_packer/src/delta_encoder.cc b/tools/relocation_packer/src/delta_encoder.cc index 69cc91a..8349d7c 100644 --- a/tools/relocation_packer/src/delta_encoder.cc +++ b/tools/relocation_packer/src/delta_encoder.cc @@ -7,66 +7,301 @@ #include <vector> #include "debug.h" -#include "elf_traits.h" + +static constexpr uint32_t RELOCATION_GROUPED_BY_INFO_FLAG = 1; +static constexpr uint32_t RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG = 2; +static constexpr uint32_t RELOCATION_GROUPED_BY_ADDEND_FLAG = 4; +static constexpr uint32_t RELOCATION_GROUP_HAS_ADDEND_FLAG = 8; + +static bool is_relocation_grouped_by_info(uint64_t flags) { + return (flags & RELOCATION_GROUPED_BY_INFO_FLAG) != 0; +} + +static bool is_relocation_grouped_by_offset_delta(uint64_t flags) { + return (flags & RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG) != 0; +} + +static bool is_relocation_grouped_by_addend(uint64_t flags) { + return (flags & RELOCATION_GROUPED_BY_ADDEND_FLAG) != 0; +} + +static bool is_relocation_group_has_addend(uint64_t flags) { + return (flags & RELOCATION_GROUP_HAS_ADDEND_FLAG) != 0; +} namespace relocation_packer { -// Encode relative relocations with addends into a delta encoded (packed) -// representation. Represented as simple r_offset and r_addend delta pairs, -// with an implicit neutral element at the start. -void RelocationDeltaCodec::Encode(const std::vector<ELF::Rela>& relocations, - std::vector<ELF::Sxword>* packed) { - // One relocation is sufficient for delta encoding. - if (relocations.size() < 1) +// Encode relocations into a delta encoded (packed) representation. +template <typename ELF> +void RelocationDeltaCodec<ELF>::Encode(const std::vector<ElfRela>& relocations, + std::vector<ElfAddr>* packed) { + if (relocations.size() == 0) return; - // Start with the element count, then append the delta pairs. - packed->push_back(relocations.size()); + // Start with the relocation count, then append groups + // TODO(dimitry): we might want to move it to DT_ANDROID_RELCOUNT section + packed->push_back(static_cast<ElfAddr>(relocations.size())); + + // lets write starting offset (offset of the first reloc - first delta) + ElfAddr start_offset = relocations.size() > 1 ? + relocations[0].r_offset - (relocations[1].r_offset - relocations[0].r_offset) : + relocations[0].r_offset; + + packed->push_back(start_offset); + + // this one is used to calculate delta + ElfAddr previous_addend = 0; + ElfAddr previous_offset = start_offset; + + for (size_t group_start = 0; group_start < relocations.size(); ) { + ElfAddr group_flags = 0; + ElfAddr group_offset_delta = 0; + ElfAddr group_addend = 0; + ElfAddr group_info = 0; + + ElfAddr group_size = 0; + + DetectGroup(relocations, group_start, previous_offset, &group_size, &group_flags, + &group_offset_delta, &group_info, &group_addend); + + // write the group header + packed->push_back(group_size); + packed->push_back(group_flags); + + if (is_relocation_grouped_by_offset_delta(group_flags)) { + packed->push_back(group_offset_delta); + } + + if (is_relocation_grouped_by_info(group_flags)) { + packed->push_back(group_info); + } + + if (is_relocation_group_has_addend(group_flags) && + is_relocation_grouped_by_addend(group_flags)) { + packed->push_back(group_addend - previous_addend); + previous_addend = group_addend; + } + + for (size_t i = 0; i < static_cast<size_t>(group_size); ++i) { + CHECK((group_start + i) < relocations.size()); + const ElfRela* relocation = &relocations[group_start + i]; + + if (!is_relocation_grouped_by_offset_delta(group_flags)) { + packed->push_back(relocation->r_offset - previous_offset); + } + previous_offset = relocation->r_offset; + + if (!is_relocation_grouped_by_info(group_flags)) { + packed->push_back(relocation->r_info); + } + + if (is_relocation_group_has_addend(group_flags) && + !is_relocation_grouped_by_addend(group_flags)) { + packed->push_back(relocation->r_addend - previous_addend); + previous_addend = relocation->r_addend; + } + } + + // If the relocation group does not have an addend - reset it to 0 + // to simplify addend computation for the group following this one. + if (!is_relocation_group_has_addend(group_flags)) { + previous_addend = 0; + } + + group_start += group_size; + } +} + +// Decode relocations from a delta encoded (packed) representation. +template <typename ELF> +void RelocationDeltaCodec<ELF>::Decode(const std::vector<ElfAddr>& packed, + std::vector<ElfRela>* relocations) { + if (packed.size() < 5) { + return; + } + + size_t ndx = 0; + ElfAddr current_count = 0; + ElfAddr total_count = packed[ndx++]; + + ElfAddr offset = packed[ndx++]; + ElfAddr info = 0; + ElfAddr addend = 0; + + while(current_count < total_count) { + // read group + ElfAddr group_size = packed[ndx++]; + ElfAddr group_flags = packed[ndx++]; + ElfAddr group_offset_delta = 0; + + if (is_relocation_grouped_by_offset_delta(group_flags)) { + group_offset_delta = packed[ndx++]; + } + + if (is_relocation_grouped_by_info(group_flags)) { + info = packed[ndx++]; + } - ELF::Addr offset = 0; - ELF::Sxword addend = 0; + if (is_relocation_group_has_addend(group_flags) && + is_relocation_grouped_by_addend(group_flags)) { + addend += packed[ndx++]; + } - for (size_t i = 0; i < relocations.size(); ++i) { - const ELF::Rela* relocation = &relocations[i]; - CHECK(ELF_R_TYPE(relocation->r_info) == ELF::kRelativeRelocationCode); + // now read not grouped info + for (ElfAddr i = 0; i<group_size; ++i) { + if (is_relocation_grouped_by_offset_delta(group_flags)) { + offset += group_offset_delta; + } else { + offset += packed[ndx++]; + } - packed->push_back(relocation->r_offset - offset); - offset = relocation->r_offset; - packed->push_back(relocation->r_addend - addend); - addend = relocation->r_addend; + if (!is_relocation_grouped_by_info(group_flags)) { + info = packed[ndx++]; + } + + if (is_relocation_group_has_addend(group_flags) && + !is_relocation_grouped_by_addend(group_flags)) { + addend += packed[ndx++]; + } + + ElfRela reloc; + reloc.r_offset = offset; + reloc.r_info = info; + reloc.r_addend = is_relocation_group_has_addend(group_flags) ? addend : 0; + relocations->push_back(reloc); + } + + if (!is_relocation_group_has_addend(group_flags)) { + addend = 0; + } + + current_count += group_size; + } +} + +// This function detects a way to group reloc_one and reloc_two, sets up group_flags +// and initializes values for corresponding group_ fields. For example if relocations +// can be grouped by r_info the function will set group_info variable. +template <typename ELF> +void RelocationDeltaCodec<ELF>::DetectGroupFields(const ElfRela& reloc_one, + const ElfRela& reloc_two, + ElfAddr current_offset_delta, + ElfAddr* group_flags, + ElfAddr* group_offset_delta, + ElfAddr* group_info, + ElfAddr* group_addend) { + *group_flags = 0; + + const ElfAddr offset_delta = static_cast<ElfAddr>(reloc_two.r_offset) - + static_cast<ElfAddr>(reloc_one.r_offset); + + if (offset_delta == current_offset_delta) { + *group_flags |= RELOCATION_GROUPED_BY_OFFSET_DELTA_FLAG; + if (group_offset_delta != nullptr) { + *group_offset_delta = current_offset_delta; + } + } + + if (reloc_one.r_info == reloc_two.r_info) { + *group_flags |= RELOCATION_GROUPED_BY_INFO_FLAG; + if (group_info != nullptr) { + *group_info = reloc_one.r_info; + } + } + + if (reloc_one.r_addend != 0 || reloc_two.r_addend != 0) { + *group_flags |= RELOCATION_GROUP_HAS_ADDEND_FLAG; + if (reloc_one.r_addend == reloc_two.r_addend) { + *group_flags |= RELOCATION_GROUPED_BY_ADDEND_FLAG; + if (group_addend != nullptr) { + *group_addend = reloc_one.r_addend; + } + } } } -// Decode relative relocations with addends from a delta encoded (packed) -// representation. -void RelocationDeltaCodec::Decode(const std::vector<ELF::Sxword>& packed, - std::vector<ELF::Rela>* relocations) { - // We need at least one packed pair after the packed pair count to be - // able to unpack. - if (packed.size() < 3) +// This function is used to detect if there is better group available +// during RelocationDeltaCodec<ELF>::DetectGroup processing. +// Current implementation prefers having groups without addend (== zero addend) +// to any other groups field with the ratio 3:1. This is because addend tends +// to be more unevenly distributed than other fields. +static uint32_t group_weight(uint64_t flags) { + uint32_t weight = 0; + if (!is_relocation_group_has_addend(flags)) { + weight += 3; + } else if (is_relocation_grouped_by_addend(flags)) { + weight += 1; + } + + if (is_relocation_grouped_by_offset_delta(flags)) { + weight += 1; + } + + if (is_relocation_grouped_by_info(flags)) { + weight += 1; + } + + return weight; +} + +template <typename ELF> +void RelocationDeltaCodec<ELF>::DetectGroup(const std::vector<ElfRela>& relocations, + size_t group_starts_with, ElfAddr previous_offset, + ElfAddr* group_size, ElfAddr* group_flags, + ElfAddr* group_offset_delta, ElfAddr* group_info, + ElfAddr* group_addend) { + CHECK(group_starts_with < relocations.size()); + CHECK(group_flags != nullptr); + + const ElfRela& reloc_one = relocations[group_starts_with++]; + if (group_starts_with == relocations.size()) { + *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG; + *group_size = 1; return; + } - // Ensure that the packed data offers enough pairs. There may be zero - // padding on it that we ignore. - CHECK(static_cast<size_t>(packed[0]) <= (packed.size() - 1) >> 1); - - ELF::Addr offset = 0; - ELF::Sxword addend = 0; - - // The first packed vector element is the pairs count. Start uncondensing - // pairs at the second, and finish at the end of the pairs data. - const size_t pairs_count = packed[0]; - for (size_t i = 1; i < 1 + (pairs_count << 1); i += 2) { - offset += packed[i]; - addend += packed[i + 1]; - - // Generate a relocation for this offset and addend pair. - ELF::Rela relocation; - relocation.r_offset = offset; - relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); - relocation.r_addend = addend; - relocations->push_back(relocation); + const ElfAddr offset_delta = reloc_one.r_offset - previous_offset; + + // detect group_flags + DetectGroupFields(reloc_one, relocations[group_starts_with], offset_delta, group_flags, + group_offset_delta, group_info, group_addend); + + if (group_starts_with + 1 == relocations.size()) { + *group_size = 2; + return; } + + ElfAddr cnt = 1; + for (size_t i = group_starts_with; i < relocations.size() - 1; ++i) { + ElfAddr candidate_flags; + // check if next group (reloc_current; reloc_next) has better grouped_by flags + DetectGroupFields(relocations[i], relocations[i+1], offset_delta, &candidate_flags, + nullptr, nullptr, nullptr); + + if (group_weight(*group_flags) < group_weight(candidate_flags)) { + break; + } + cnt++; + + if (candidate_flags != *group_flags) { + break; + } + + if (i + 1 == relocations.size() - 1) { // last one + cnt++; + } + } + + // if as a result of checking candidates we ended up with cnt == 1 + // reset flags to the default state + if (cnt == 1) { + *group_flags = reloc_one.r_addend == 0 ? 0 : RELOCATION_GROUP_HAS_ADDEND_FLAG; + } + + *group_size = cnt; } +template class RelocationDeltaCodec<ELF32_traits>; +template class RelocationDeltaCodec<ELF64_traits>; + } // namespace relocation_packer diff --git a/tools/relocation_packer/src/delta_encoder.h b/tools/relocation_packer/src/delta_encoder.h index 498b6d1..46c324c 100644 --- a/tools/relocation_packer/src/delta_encoder.h +++ b/tools/relocation_packer/src/delta_encoder.h @@ -2,50 +2,86 @@ // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. -// Delta encode and decode relative relocations with addends. +// Delta encode and decode REL/RELA section of elf file. // -// Relative relocations are the bulk of dynamic relocations (the -// .rel.dyn or .rela.dyn sections) in libchrome.<version>.so, and the ELF -// standard representation of them is wasteful. .rel.dyn contains -// relocations without addends, .rela.dyn relocations with addends. +// The encoded data format is sequence of elements of ElfAddr type (unsigned long): // -// A relocation with an addend is 12 bytes on 32 bit platforms and 24 bytes -// on 64 bit plaforms. It is split into offset, info, and addend fields. -// Offsets strictly increase, and each is commonly a few bytes different -// from its predecessor. Addends are less well behaved. The info field is -// constant. Example, from 'readelf -x4 libchrome.<version>.so' 64 bit: +// [00] relocation_count - the total count of relocations +// [01] initial r_offset - this is initial r_offset for the +// relocation table. +// followed by group structures: +// [02] group +// ... +// [nn] group + +// the generalized format of the group is (! - always present ? - depends on group_flags): +// -------------- +// ! group_size +// ! group_flags +// ? group_r_offset_delta when RELOCATION_GROUPED_BY_OFFSET_DELTA flag is set +// ? group_r_info when RELOCATION_GROUPED_BY_INFO flag is set +// ? group_r_addend_group_delta when RELOCATION_GROUP_HAS_ADDEND and RELOCATION_GROUPED_BY_ADDEND +// flag is set // -// offset info -// 80949303 00000000 03040000 00000000 ................ -// addend offset -// fc015b00 00000000 88949303 00000000 ..[............. -// info addend -// 03040000 00000000 24025b00 00000000 ........$.[..... -// offset info -// 90949303 00000000 03040000 00000000 ................ -// addend offset -// 3c025b00 00000000 98949303 00000000 <.[............. -// info addend -// 03040000 00000000 50025b00 00000000 ........P.[..... +// The group description is followed by individual relocations. +// please note that there is a case when individual relocation +// section could be empty - that is if every field ends up grouped. // -// The offset strictly increases, but the addend is unpredictable, so run -// length encoding will not work well with this data. We can however pack -// with delta encoding. The upper four bytes of the eight byte offset and -// addend are invariably zeroes. The difference between adjacent offsets -// is almost always small, and between adjacent addends is often small. And -// info is constant and can be eliminated. +// The format for individual relocations section is: +// ? r_offset_delta - when RELOCATION_GROUPED_BY_OFFSET_DELTA is not set +// ? r_info - when RELOCATION_GROUPED_BY_INFO flag is not set +// ? r_addend_delta - RELOCATION_GROUP_HAS_ADDEND is set and RELOCATION_GROUPED_BY_ADDEND is not set // -// Delta encoding reduces the size of the data modestly, so that the first -// three relocations above can be represented as: +// For example lets pack the following relocations: // -// initial offset initial addend offset delta addend delta -// 00000000 03939480 00000000 005b01fc 00000000 00000008 00000000 00000028 -// offset delta addend delta ... -// 00000000 00000008 00000000 0000009f +// Relocation section '.rela.dyn' at offset 0xbf58 contains 939 entries: +// Offset Info Type Symbol's Value Symbol's Name + Addend +// 00000000000a2178 0000000000000403 R_AARCH64_RELATIVE 177a8 +// 00000000000a2180 0000000000000403 R_AARCH64_RELATIVE 177cc +// 00000000000a2188 0000000000000403 R_AARCH64_RELATIVE 177e0 +// 00000000000a2190 0000000000000403 R_AARCH64_RELATIVE 177f4 +// 00000000000a2198 0000000000000403 R_AARCH64_RELATIVE 17804 +// 00000000000a21a0 0000000000000403 R_AARCH64_RELATIVE 17818 +// 00000000000a21a8 0000000000000403 R_AARCH64_RELATIVE 1782c +// 00000000000a21b0 0000000000000403 R_AARCH64_RELATIVE 17840 +// 00000000000a21b8 0000000000000403 R_AARCH64_RELATIVE 17854 +// 00000000000a21c0 0000000000000403 R_AARCH64_RELATIVE 17868 +// 00000000000a21c8 0000000000000403 R_AARCH64_RELATIVE 1787c +// 00000000000a21d0 0000000000000403 R_AARCH64_RELATIVE 17890 +// 00000000000a21d8 0000000000000403 R_AARCH64_RELATIVE 178a4 +// 00000000000a21e8 0000000000000403 R_AARCH64_RELATIVE 178b8 // -// The addend delta can be negative as well as positive, but overall the -// deltas have a much smaller range than the input data. When encoded as -// signed LEB128 the total data reduction becomes useful. +// The header is going to be +// [00] 14 <- count +// [01] 0x00000000000a2170 <- initial relocation (first relocation - delta, +// the delta is 8 in this case) +// -- starting the first and only group +// [03] 14 <- group size +// [03] 0xb <- flags RELOCATION_GROUP_HAS_ADDEND | RELOCATION_GROUPED_BY_OFFSET_DELTA +// | RELOCATION_GROUPED_BY_INFO +// [04] 8 <- offset delta +// [05] 0x403 <- r_info +// -- end of group definition, starting list of r_addend deltas +// [06] 0x177a8 +// [07] 0x24 = 177cc - 177a8 +// [08] 0x14 = 177e0 - 177cc +// [09] 0x14 = 177f4 - 177e0 +// [10] 0x10 = 17804 - 177f4 +// [11] 0x14 = 17818 - 17804 +// [12] 0x14 = 1782c - 17818 +// [13] 0x14 = 17840 - 1782c +// [14] 0x14 = 17854 - 17840 +// [15] 0x14 = 17868 - 17854 +// [16] 0x14 = 1787c - 17868 +// [17] 0x14 = 17890 - 1787c +// [18] 0x14 = 178a4 - 17890 +// [19] 0x14 = 178b8 - 178a4 +// -- the end. + +// TODO (dimitry): consider using r_addend_group_delta in the way we use group offset delta, it can +// save us more bytes... + +// The input ends when sum(group_size) == relocation_count #ifndef TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_ #define TOOLS_RELOCATION_PACKER_SRC_DELTA_ENCODER_H_ @@ -60,19 +96,35 @@ namespace relocation_packer { // A RelocationDeltaCodec packs vectors of relative relocations with // addends into more compact forms, and unpacks them to reproduce the // pre-packed data. +template <typename ELF> class RelocationDeltaCodec { public: - // Encode relative relocations with addends into a more compact form. + typedef typename ELF::Addr ElfAddr; + typedef typename ELF::Rela ElfRela; + + // Encode relocations with addends into a more compact form. // |relocations| is a vector of relative relocation with addend structs. // |packed| is the vector of packed words into which relocations are packed. - static void Encode(const std::vector<ELF::Rela>& relocations, - std::vector<ELF::Sxword>* packed); + static void Encode(const std::vector<ElfRela>& relocations, + std::vector<ElfAddr>* packed); // Decode relative relocations with addends from their more compact form. // |packed| is the vector of packed relocations. // |relocations| is a vector of unpacked relative relocations. - static void Decode(const std::vector<ELF::Sxword>& packed, - std::vector<ELF::Rela>* relocations); + static void Decode(const std::vector<ElfAddr>& packed, + std::vector<ElfRela>* relocations); + + private: + static void DetectGroup(const std::vector<ElfRela>& relocations, + size_t group_starts_with, ElfAddr previous_offset, + ElfAddr* group_size, ElfAddr* group_flags, + ElfAddr* group_offset_delta, ElfAddr* group_info, + ElfAddr* group_addend); + + static void DetectGroupFields(const ElfRela& reloc_one, const ElfRela& reloc_two, + ElfAddr current_offset_delta, ElfAddr* group_flags, + ElfAddr* group_offset_delta, ElfAddr* group_info, + ElfAddr* group_addend); }; } // namespace relocation_packer diff --git a/tools/relocation_packer/src/delta_encoder_unittest.cc b/tools/relocation_packer/src/delta_encoder_unittest.cc index b9bf39a..06d9c96 100644 --- a/tools/relocation_packer/src/delta_encoder_unittest.cc +++ b/tools/relocation_packer/src/delta_encoder_unittest.cc @@ -6,27 +6,29 @@ #include <vector> #include "elf.h" -#include "elf_traits.h" -#include "testing/gtest/include/gtest/gtest.h" +#include "gtest/gtest.h" namespace { -void AddRelocation(ELF::Addr addr, - ELF::Sxword addend, - std::vector<ELF::Rela>* relocations) { - ELF::Rela relocation; +template <typename T> +void AddRelocation(uint32_t addr, + uint32_t info, + int32_t addend, + std::vector<T>* relocations) { + T relocation; relocation.r_offset = addr; - relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); + relocation.r_info = info; relocation.r_addend = addend; relocations->push_back(relocation); } -bool CheckRelocation(ELF::Addr addr, - ELF::Sxword addend, - const ELF::Rela& relocation) { +template <typename T> +bool CheckRelocation(uint32_t addr, + uint32_t info, + int32_t addend, + const T& relocation) { return relocation.r_offset == addr && - ELF_R_SYM(relocation.r_info) == 0 && - ELF_R_TYPE(relocation.r_info) == ELF::kRelativeRelocationCode && + relocation.r_info == info && relocation.r_addend == addend; } @@ -34,117 +36,188 @@ bool CheckRelocation(ELF::Addr addr, namespace relocation_packer { -TEST(Delta, Encode) { - std::vector<ELF::Rela> relocations; - std::vector<ELF::Sxword> packed; +template <typename ELF> +static void encode() { + std::vector<typename ELF::Rela> relocations; + std::vector<typename ELF::Addr> packed; - RelocationDeltaCodec codec; + RelocationDeltaCodec<ELF> codec; - packed.clear(); codec.Encode(relocations, &packed); - EXPECT_EQ(0, packed.size()); + ASSERT_EQ(0U, packed.size()); // Initial relocation. - AddRelocation(0xf00d0000, 10000, &relocations); + AddRelocation(0xf00d0000, 11U, 10000, &relocations); - packed.clear(); codec.Encode(relocations, &packed); - EXPECT_EQ(3, packed.size()); + // size of reloc table, size of group, flags, 3 fields, zero + EXPECT_EQ(7U, packed.size()); // One pair present. - EXPECT_EQ(1, packed[0]); - // Delta from the neutral element is the initial relocation. - EXPECT_EQ(0xf00d0000, packed[1]); - EXPECT_EQ(10000, packed[2]); + size_t ndx = 0; + EXPECT_EQ(1U, packed[ndx++]); + EXPECT_EQ(0xf00d0000, packed[ndx++]); + EXPECT_EQ(1U, packed[ndx++]); // group_size + EXPECT_EQ(8U, packed[ndx++]); // flags + // Delta from the neutral element is zero + EXPECT_EQ(0U, packed[ndx++]); // offset_delta + EXPECT_EQ(11U, packed[ndx++]); // info + EXPECT_EQ(10000U, packed[ndx++]); // addend_delta // Add a second relocation, 4 byte offset delta, 12 byte addend delta. - AddRelocation(0xf00d0004, 10012, &relocations); + // same info + AddRelocation(0xf00d0004, 11U, 10012, &relocations); packed.clear(); codec.Encode(relocations, &packed); - EXPECT_EQ(5, packed.size()); - // Two pairs present. - EXPECT_EQ(2, packed[0]); - // Delta from the neutral element is the initial relocation. - EXPECT_EQ(0xf00d0000, packed[1]); - EXPECT_EQ(10000, packed[2]); - // 4 byte offset delta, 12 byte addend delta. - EXPECT_EQ(4, packed[3]); - EXPECT_EQ(12, packed[4]); + ndx = 0; + EXPECT_EQ(8U, packed.size()); + + EXPECT_EQ(2U, packed[ndx++]); // relocs count + EXPECT_EQ(0xf00cfffc, packed[ndx++]); // initial offset + EXPECT_EQ(2U, packed[ndx++]); // group count + EXPECT_EQ(11U, packed[ndx++]); // flags + EXPECT_EQ(4U, packed[ndx++]); // group offset delta + EXPECT_EQ(11U, packed[ndx++]); // info + + EXPECT_EQ(10000U, packed[ndx++]); // addend delta + EXPECT_EQ(12U, packed[ndx++]); // addend delta // Add a third relocation, 4 byte offset delta, 12 byte addend delta. - AddRelocation(0xf00d0008, 10024, &relocations); + // different info + AddRelocation(0xf00d0008, 41U, 10024, &relocations); // Add three more relocations, 8 byte offset deltas, -24 byte addend deltas. - AddRelocation(0xf00d0010, 10000, &relocations); - AddRelocation(0xf00d0018, 9976, &relocations); - AddRelocation(0xf00d0020, 9952, &relocations); + AddRelocation(0xf00d0010, 42U, 10000, &relocations); + AddRelocation(0xf00d0018, 42U, 9976, &relocations); + AddRelocation(0xf00d0020, 42U, 9952, &relocations); + + AddRelocation(0xf00d2028, 1042U, 0, &relocations); + AddRelocation(0xf00d2030, 3442U, 0, &relocations); packed.clear(); codec.Encode(relocations, &packed); - EXPECT_EQ(13, packed.size()); - // Six pairs present. - EXPECT_EQ(6, packed[0]); + ndx = 0; + EXPECT_EQ(26U, packed.size()); + // Total number of relocs + EXPECT_EQ(8U, packed[ndx++]); + EXPECT_EQ(0xf00cfffc, packed[ndx++]); + // 2 in first group + EXPECT_EQ(2U, packed[ndx++]); + EXPECT_EQ(11U, packed[ndx++]); //flags + EXPECT_EQ(4U, packed[ndx++]); // group offset delta + EXPECT_EQ(11U, packed[ndx++]); // info + // Initial relocation. - EXPECT_EQ(0xf00d0000, packed[1]); - EXPECT_EQ(10000, packed[2]); + EXPECT_EQ(10000U, packed[ndx++]); // addend delta // Two relocations, 4 byte offset deltas, 12 byte addend deltas. - EXPECT_EQ(4, packed[3]); - EXPECT_EQ(12, packed[4]); - EXPECT_EQ(4, packed[5]); - EXPECT_EQ(12, packed[6]); + EXPECT_EQ(12U, packed[ndx++]); // addend delta + + // second group has only one reloc + EXPECT_EQ(1U, packed[ndx++]); // count + EXPECT_EQ(8U, packed[ndx++]); // flags + + EXPECT_EQ(4U, packed[ndx++]); // offset delta + EXPECT_EQ(41U, packed[ndx++]); // info + EXPECT_EQ(12U, packed[ndx++]); // addend delta + + // next - 3 relocs grouped by info + EXPECT_EQ(3U, packed[ndx++]); // count + EXPECT_EQ(11U, packed[ndx++]); // flags + EXPECT_EQ(8U, packed[ndx++]); // group offset delta + EXPECT_EQ(42U, packed[ndx++]); // info // Three relocations, 8 byte offset deltas, -24 byte addend deltas. - EXPECT_EQ(8, packed[7]); - EXPECT_EQ(-24, packed[8]); - EXPECT_EQ(8, packed[9]); - EXPECT_EQ(-24, packed[10]); - EXPECT_EQ(8, packed[11]); - EXPECT_EQ(-24, packed[12]); + EXPECT_EQ(static_cast<typename ELF::Addr>(-24), packed[ndx++]); + EXPECT_EQ(static_cast<typename ELF::Addr>(-24), packed[ndx++]); + EXPECT_EQ(static_cast<typename ELF::Addr>(-24), packed[ndx++]); + + // and last - 2 relocations without addend + EXPECT_EQ(2U, packed[ndx++]); + EXPECT_EQ(0U, packed[ndx++]); // flags + // offset_deltas and r_infos for next 2 relocations + EXPECT_EQ(0x2008U, packed[ndx++]); // offset delta + EXPECT_EQ(1042U, packed[ndx++]); // r_info + EXPECT_EQ(0x8U, packed[ndx++]); // offset delta + EXPECT_EQ(3442U, packed[ndx++]); // r_info + + EXPECT_EQ(packed.size(), ndx); } -TEST(Delta, Decode) { - std::vector<ELF::Sxword> packed; - std::vector<ELF::Rela> relocations; +TEST(Delta, Encode32) { + encode<ELF32_traits>(); +} - RelocationDeltaCodec codec; +TEST(Delta, Encode64) { + encode<ELF64_traits>(); +} + +template <typename ELF> +static void decode() { + std::vector<typename ELF::Addr> packed; + std::vector<typename ELF::Rela> relocations; + + RelocationDeltaCodec<ELF> codec; codec.Decode(packed, &relocations); - EXPECT_EQ(0, relocations.size()); + EXPECT_EQ(0U, relocations.size()); // Six pairs. - packed.push_back(6); + packed.push_back(6U); // count + packed.push_back(0xc0ddfffc); // base offset + packed.push_back(3U); // group count + packed.push_back(11U); // flags + packed.push_back(4U); // offset delta + packed.push_back(11U); // info // Initial relocation. - packed.push_back(0xc0de0000); - packed.push_back(10000); + packed.push_back(10000U); // Two relocations, 4 byte offset deltas, 12 byte addend deltas. - packed.push_back(4); - packed.push_back(12); - packed.push_back(4); - packed.push_back(12); + packed.push_back(12U); // addend + packed.push_back(12U); // addend + // Three relocations, 8 byte offset deltas, -24 byte addend deltas. - packed.push_back(8); - packed.push_back(-24); - packed.push_back(8); - packed.push_back(-24); - packed.push_back(8); - packed.push_back(-24); + packed.push_back(1U); // group count + packed.push_back(9U); // flags + packed.push_back(11U); // info + + packed.push_back(8U); + packed.push_back(static_cast<typename ELF::Addr>(-24)); + // next group with 2 relocs + packed.push_back(2U); // group count + packed.push_back(11U); // flags + packed.push_back(8U); // offset + packed.push_back(42U); // info + + packed.push_back(static_cast<typename ELF::Addr>(-24)); // addend + packed.push_back(static_cast<typename ELF::Addr>(-24)); // addend relocations.clear(); codec.Decode(packed, &relocations); - EXPECT_EQ(6, relocations.size()); + EXPECT_EQ(6U, relocations.size()); // Initial relocation. - EXPECT_TRUE(CheckRelocation(0xc0de0000, 10000, relocations[0])); + EXPECT_TRUE(CheckRelocation(0xc0de0000, 11U, 10000, relocations[0])); // Two relocations, 4 byte offset deltas, 12 byte addend deltas. - EXPECT_TRUE(CheckRelocation(0xc0de0004, 10012, relocations[1])); - EXPECT_TRUE(CheckRelocation(0xc0de0008, 10024, relocations[2])); + EXPECT_TRUE(CheckRelocation(0xc0de0004, 11U, 10012, relocations[1])); + EXPECT_TRUE(CheckRelocation(0xc0de0008, 11U, 10024, relocations[2])); // Three relocations, 8 byte offset deltas, -24 byte addend deltas. - EXPECT_TRUE(CheckRelocation(0xc0de0010, 10000, relocations[3])); - EXPECT_TRUE(CheckRelocation(0xc0de0018, 9976, relocations[4])); - EXPECT_TRUE(CheckRelocation(0xc0de0020, 9952, relocations[5])); + EXPECT_TRUE(CheckRelocation(0xc0de0010, 11U, 10000, relocations[3])); + EXPECT_TRUE(CheckRelocation(0xc0de0018, 42U, 9976, relocations[4])); + EXPECT_TRUE(CheckRelocation(0xc0de0020, 42U, 9952, relocations[5])); } +TEST(Delta, Decode32) { + decode<ELF32_traits>(); +} + +TEST(Delta, Decode64) { + decode<ELF64_traits>(); +} + +// TODO (dimitry): add more tests (fix by 19 January 2038 03:14:07 UTC) +// TODO (dimtiry): 1. Incorrect packed array for decode +// TODO (dimtiry): 2. Try to catch situation where it is likely to get series of groups with size 1 + } // namespace relocation_packer diff --git a/tools/relocation_packer/src/elf_file.cc b/tools/relocation_packer/src/elf_file.cc index 3ffccec..20b25ef 100644 --- a/tools/relocation_packer/src/elf_file.cc +++ b/tools/relocation_packer/src/elf_file.cc @@ -5,26 +5,10 @@ // Implementation notes: // // We need to remove a piece from the ELF shared library. However, we also -// want to ensure that code and data loads at the same addresses as before -// packing, so that tools like breakpad can still match up addresses found -// in any crash dumps with data extracted from the pre-packed version of -// the shared library. -// -// Arranging this means that we have to split one of the LOAD segments into -// two. Unfortunately, the program headers are located at the very start -// of the shared library file, so expanding the program header section -// would cause a lot of consequent changes to files offsets that we don't -// really want to have to handle. -// -// Luckily, though, there is a segment that is always present and always -// unused on Android; the GNU_STACK segment. What we do is to steal that -// and repurpose it to be one of the split LOAD segments. We then have to -// sort LOAD segments by offset to keep the crazy linker happy. -// -// All of this takes place in SplitProgramHeadersForHole(), used on packing, -// and is unraveled on unpacking in CoalesceProgramHeadersForHole(). See -// commentary on those functions for an example of this segment stealing -// in action. +// want to avoid fixing DWARF cfi data and relative relocation addresses. +// So after packing we shift offets and starting address of the RX segment +// while preserving code/data vaddrs location. +// This requires some fixups for symtab/hash/gnu_hash dynamic section addresses. #include "elf_file.h" @@ -42,28 +26,29 @@ namespace relocation_packer { -// Stub identifier written to 'null out' packed data, "NULL". -static const uint32_t kStubIdentifier = 0x4c4c554eu; - // Out-of-band dynamic tags used to indicate the offset and size of the // android packed relocations section. -static const ELF::Sword DT_ANDROID_REL_OFFSET = DT_LOOS; -static const ELF::Sword DT_ANDROID_REL_SIZE = DT_LOOS + 1; +static constexpr int32_t DT_ANDROID_REL = DT_LOOS + 2; +static constexpr int32_t DT_ANDROID_RELSZ = DT_LOOS + 3; + +static constexpr int32_t DT_ANDROID_RELA = DT_LOOS + 4; +static constexpr int32_t DT_ANDROID_RELASZ = DT_LOOS + 5; + +static constexpr uint32_t SHT_ANDROID_REL = SHT_LOOS + 1; +static constexpr uint32_t SHT_ANDROID_RELA = SHT_LOOS + 2; // Alignment to preserve, in bytes. This must be at least as large as the // largest d_align and sh_addralign values found in the loaded file. // Out of caution for RELRO page alignment, we preserve to a complete target // page. See http://www.airs.com/blog/archives/189. -static const size_t kPreserveAlignment = 4096; - -namespace { +static constexpr size_t kPreserveAlignment = 4096; // Get section data. Checks that the section has exactly one data entry, // so that the section size and the data size are the same. True in // practice for all sections we resize when packing or unpacking. Done // by ensuring that a call to elf_getdata(section, data) returns NULL as // the next data entry. -Elf_Data* GetSectionData(Elf_Scn* section) { +static Elf_Data* GetSectionData(Elf_Scn* section) { Elf_Data* data = elf_getdata(section, NULL); CHECK(data && elf_getdata(section, data) == NULL); return data; @@ -71,9 +56,9 @@ Elf_Data* GetSectionData(Elf_Scn* section) { // Rewrite section data. Allocates new data and makes it the data element's // buffer. Relies on program exit to free allocated data. -void RewriteSectionData(Elf_Scn* section, - const void* section_data, - size_t size) { +static void RewriteSectionData(Elf_Scn* section, + const void* section_data, + size_t size) { Elf_Data* data = GetSectionData(section); CHECK(size == data->d_size); uint8_t* area = new uint8_t[size]; @@ -82,7 +67,8 @@ void RewriteSectionData(Elf_Scn* section, } // Verbose ELF header logging. -void VerboseLogElfHeader(const ELF::Ehdr* elf_header) { +template <typename Ehdr> +static void VerboseLogElfHeader(const Ehdr* elf_header) { VLOG(1) << "e_phoff = " << elf_header->e_phoff; VLOG(1) << "e_shoff = " << elf_header->e_shoff; VLOG(1) << "e_ehsize = " << elf_header->e_ehsize; @@ -93,8 +79,9 @@ void VerboseLogElfHeader(const ELF::Ehdr* elf_header) { } // Verbose ELF program header logging. -void VerboseLogProgramHeader(size_t program_header_index, - const ELF::Phdr* program_header) { +template <typename Phdr> +static void VerboseLogProgramHeader(size_t program_header_index, + const Phdr* program_header) { std::string type; switch (program_header->p_type) { case PT_NULL: type = "NULL"; break; @@ -118,17 +105,19 @@ void VerboseLogProgramHeader(size_t program_header_index, } // Verbose ELF section header logging. -void VerboseLogSectionHeader(const std::string& section_name, - const ELF::Shdr* section_header) { +template <typename Shdr> +static void VerboseLogSectionHeader(const std::string& section_name, + const Shdr* section_header) { VLOG(1) << "section " << section_name; VLOG(1) << " sh_addr = " << section_header->sh_addr; VLOG(1) << " sh_offset = " << section_header->sh_offset; VLOG(1) << " sh_size = " << section_header->sh_size; + VLOG(1) << " sh_entsize = " << section_header->sh_entsize; VLOG(1) << " sh_addralign = " << section_header->sh_addralign; } // Verbose ELF section data logging. -void VerboseLogSectionData(const Elf_Data* data) { +static void VerboseLogSectionData(const Elf_Data* data) { VLOG(1) << " data"; VLOG(1) << " d_buf = " << data->d_buf; VLOG(1) << " d_off = " << data->d_off; @@ -136,12 +125,11 @@ void VerboseLogSectionData(const Elf_Data* data) { VLOG(1) << " d_align = " << data->d_align; } -} // namespace - // Load the complete ELF file into a memory image in libelf, and identify // the .rel.dyn or .rela.dyn, .dynamic, and .android.rel.dyn or // .android.rela.dyn sections. No-op if the ELF file has already been loaded. -bool ElfFile::Load() { +template <typename ELF> +bool ElfFile<ELF>::Load() { if (elf_) return true; @@ -153,15 +141,12 @@ bool ElfFile::Load() { return false; } - ELF::Ehdr* elf_header = ELF::getehdr(elf); + auto elf_header = ELF::getehdr(elf); if (!elf_header) { LOG(ERROR) << "Failed to load ELF header: " << elf_errmsg(elf_errno()); return false; } - if (elf_header->e_machine != ELF::kMachine) { - LOG(ERROR) << "ELF file architecture is not " << ELF::Machine(); - return false; - } + if (elf_header->e_type != ET_DYN) { LOG(ERROR) << "ELF file is not a shared object"; return false; @@ -173,19 +158,16 @@ bool ElfFile::Load() { CHECK(endian == ELFDATA2LSB); CHECK(__BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__); - // Also require that the file class is as expected. const int file_class = elf_header->e_ident[EI_CLASS]; - CHECK(file_class == ELF::kFileClass); - VLOG(1) << "endian = " << endian << ", file class = " << file_class; VerboseLogElfHeader(elf_header); - const ELF::Phdr* elf_program_header = ELF::getphdr(elf); - CHECK(elf_program_header); + auto elf_program_header = ELF::getphdr(elf); + CHECK(elf_program_header != nullptr); - const ELF::Phdr* dynamic_program_header = NULL; + const typename ELF::Phdr* dynamic_program_header = NULL; for (size_t i = 0; i < elf_header->e_phnum; ++i) { - const ELF::Phdr* program_header = &elf_program_header[i]; + auto program_header = &elf_program_header[i]; VerboseLogProgramHeader(i, program_header); if (program_header->p_type == PT_DYNAMIC) { @@ -193,7 +175,7 @@ bool ElfFile::Load() { dynamic_program_header = program_header; } } - CHECK(dynamic_program_header != NULL); + CHECK(dynamic_program_header != nullptr); size_t string_index; elf_getshdrstrndx(elf, &string_index); @@ -201,9 +183,8 @@ bool ElfFile::Load() { // Notes of the dynamic relocations, packed relocations, and .dynamic // sections. Found while iterating sections, and later stored in class // attributes. - Elf_Scn* found_relocations_section = NULL; - Elf_Scn* found_android_relocations_section = NULL; - Elf_Scn* found_dynamic_section = NULL; + Elf_Scn* found_relocations_section = nullptr; + Elf_Scn* found_dynamic_section = nullptr; // Notes of relocation section types seen. We require one or the other of // these; both is unsupported. @@ -211,16 +192,16 @@ bool ElfFile::Load() { bool has_rela_relocations = false; Elf_Scn* section = NULL; - while ((section = elf_nextscn(elf, section)) != NULL) { - const ELF::Shdr* section_header = ELF::getshdr(section); + while ((section = elf_nextscn(elf, section)) != nullptr) { + auto section_header = ELF::getshdr(section); std::string name = elf_strptr(elf, string_index, section_header->sh_name); VerboseLogSectionHeader(name, section_header); // Note relocation section types. - if (section_header->sh_type == SHT_REL) { + if (section_header->sh_type == SHT_REL || section_header->sh_type == SHT_ANDROID_REL) { has_rel_relocations = true; } - if (section_header->sh_type == SHT_RELA) { + if (section_header->sh_type == SHT_RELA || section_header->sh_type == SHT_ANDROID_RELA) { has_rela_relocations = true; } @@ -229,10 +210,7 @@ bool ElfFile::Load() { section_header->sh_size > 0) { found_relocations_section = section; } - if ((name == ".android.rel.dyn" || name == ".android.rela.dyn") && - section_header->sh_size > 0) { - found_android_relocations_section = section; - } + if (section_header->sh_offset == dynamic_program_header->p_offset) { found_dynamic_section = section; } @@ -252,12 +230,6 @@ bool ElfFile::Load() { LOG(ERROR) << "Missing or empty .rel.dyn or .rela.dyn section"; return false; } - if (!found_android_relocations_section) { - LOG(ERROR) << "Missing or empty .android.rel.dyn or .android.rela.dyn " - << "section (to fix, run with --help and follow the " - << "pre-packing instructions)"; - return false; - } if (!found_dynamic_section) { LOG(ERROR) << "Missing .dynamic section"; return false; @@ -277,17 +249,15 @@ bool ElfFile::Load() { elf_ = elf; relocations_section_ = found_relocations_section; dynamic_section_ = found_dynamic_section; - android_relocations_section_ = found_android_relocations_section; relocations_type_ = has_rel_relocations ? REL : RELA; return true; } -namespace { - // Helper for ResizeSection(). Adjust the main ELF header for the hole. -void AdjustElfHeaderForHole(ELF::Ehdr* elf_header, - ELF::Off hole_start, - ssize_t hole_size) { +template <typename ELF> +static void AdjustElfHeaderForHole(typename ELF::Ehdr* elf_header, + typename ELF::Off hole_start, + ssize_t hole_size) { if (elf_header->e_phoff > hole_start) { elf_header->e_phoff += hole_size; VLOG(1) << "e_phoff adjusted to " << elf_header->e_phoff; @@ -299,437 +269,119 @@ void AdjustElfHeaderForHole(ELF::Ehdr* elf_header, } // Helper for ResizeSection(). Adjust all section headers for the hole. -void AdjustSectionHeadersForHole(Elf* elf, - ELF::Off hole_start, - ssize_t hole_size) { +template <typename ELF> +static void AdjustSectionHeadersForHole(Elf* elf, + typename ELF::Off hole_start, + ssize_t hole_size) { size_t string_index; elf_getshdrstrndx(elf, &string_index); Elf_Scn* section = NULL; while ((section = elf_nextscn(elf, section)) != NULL) { - ELF::Shdr* section_header = ELF::getshdr(section); + auto section_header = ELF::getshdr(section); std::string name = elf_strptr(elf, string_index, section_header->sh_name); if (section_header->sh_offset > hole_start) { section_header->sh_offset += hole_size; VLOG(1) << "section " << name << " sh_offset adjusted to " << section_header->sh_offset; + } else { + section_header->sh_addr -= hole_size; + VLOG(1) << "section " << name + << " sh_addr adjusted to " << section_header->sh_addr; } } } // Helper for ResizeSection(). Adjust the offsets of any program headers // that have offsets currently beyond the hole start. -void AdjustProgramHeaderOffsets(ELF::Phdr* program_headers, - size_t count, - ELF::Phdr* ignored_1, - ELF::Phdr* ignored_2, - ELF::Off hole_start, - ssize_t hole_size) { +template <typename ELF> +static void AdjustProgramHeaderOffsets(typename ELF::Phdr* program_headers, + size_t count, + typename ELF::Off hole_start, + ssize_t hole_size) { for (size_t i = 0; i < count; ++i) { - ELF::Phdr* program_header = &program_headers[i]; - - if (program_header == ignored_1 || program_header == ignored_2) - continue; + typename ELF::Phdr* program_header = &program_headers[i]; if (program_header->p_offset > hole_start) { // The hole start is past this segment, so adjust offset. program_header->p_offset += hole_size; VLOG(1) << "phdr[" << i << "] p_offset adjusted to "<< program_header->p_offset; + } else { + program_header->p_vaddr -= hole_size; + program_header->p_paddr -= hole_size; + VLOG(1) << "phdr[" << i + << "] p_vaddr adjusted to "<< program_header->p_vaddr + << "; p_paddr adjusted to "<< program_header->p_paddr; } } } // Helper for ResizeSection(). Find the first loadable segment in the // file. We expect it to map from file offset zero. -ELF::Phdr* FindFirstLoadSegment(ELF::Phdr* program_headers, - size_t count) { - ELF::Phdr* first_loadable_segment = NULL; - - for (size_t i = 0; i < count; ++i) { - ELF::Phdr* program_header = &program_headers[i]; - - if (program_header->p_type == PT_LOAD && - program_header->p_offset == 0 && - program_header->p_vaddr == 0 && - program_header->p_paddr == 0) { - first_loadable_segment = program_header; - } - } - LOG_IF(FATAL, !first_loadable_segment) - << "Cannot locate a LOAD segment with address and offset zero"; - - return first_loadable_segment; -} - -// Helper for ResizeSection(). Find the PT_GNU_STACK segment, and check -// that it contains what we expect so we can restore it on unpack if needed. -ELF::Phdr* FindUnusedGnuStackSegment(ELF::Phdr* program_headers, - size_t count) { - ELF::Phdr* unused_segment = NULL; - - for (size_t i = 0; i < count; ++i) { - ELF::Phdr* program_header = &program_headers[i]; - - if (program_header->p_type == PT_GNU_STACK && - program_header->p_offset == 0 && - program_header->p_vaddr == 0 && - program_header->p_paddr == 0 && - program_header->p_filesz == 0 && - program_header->p_memsz == 0 && - program_header->p_flags == (PF_R | PF_W) && - program_header->p_align == ELF::kGnuStackSegmentAlignment) { - unused_segment = program_header; - } - } - LOG_IF(FATAL, !unused_segment) - << "Cannot locate the expected GNU_STACK segment"; - - return unused_segment; -} - -// Helper for ResizeSection(). Find the segment that was the first loadable -// one before we split it into two. This is the one into which we coalesce -// the split segments on unpacking. -ELF::Phdr* FindOriginalFirstLoadSegment(ELF::Phdr* program_headers, - size_t count) { - const ELF::Phdr* first_loadable_segment = - FindFirstLoadSegment(program_headers, count); - - ELF::Phdr* original_first_loadable_segment = NULL; - +template <typename ELF> +static typename ELF::Phdr* FindLoadSegmentForHole(typename ELF::Phdr* program_headers, + size_t count, + typename ELF::Off hole_start) { for (size_t i = 0; i < count; ++i) { - ELF::Phdr* program_header = &program_headers[i]; + typename ELF::Phdr* program_header = &program_headers[i]; - // The original first loadable segment is the one that follows on from - // the one we wrote on split to be the current first loadable segment. if (program_header->p_type == PT_LOAD && - program_header->p_offset == first_loadable_segment->p_filesz) { - original_first_loadable_segment = program_header; - } - } - LOG_IF(FATAL, !original_first_loadable_segment) - << "Cannot locate the LOAD segment that follows a LOAD at offset zero"; - - return original_first_loadable_segment; -} - -// Helper for ResizeSection(). Find the segment that contains the hole. -Elf_Scn* FindSectionContainingHole(Elf* elf, - ELF::Off hole_start, - ssize_t hole_size) { - Elf_Scn* section = NULL; - Elf_Scn* last_unholed_section = NULL; - - while ((section = elf_nextscn(elf, section)) != NULL) { - const ELF::Shdr* section_header = ELF::getshdr(section); - - // Because we get here after section headers have been adjusted for the - // hole, we need to 'undo' that adjustment to give a view of the original - // sections layout. - ELF::Off offset = section_header->sh_offset; - if (section_header->sh_offset >= hole_start) { - offset -= hole_size; - } - - if (offset <= hole_start) { - last_unholed_section = section; - } - } - LOG_IF(FATAL, !last_unholed_section) - << "Cannot identify the section before the one containing the hole"; - - // The section containing the hole is the one after the last one found - // by the loop above. - Elf_Scn* holed_section = elf_nextscn(elf, last_unholed_section); - LOG_IF(FATAL, !holed_section) - << "Cannot identify the section containing the hole"; - - return holed_section; -} - -// Helper for ResizeSection(). Find the last section contained in a segment. -Elf_Scn* FindLastSectionInSegment(Elf* elf, - ELF::Phdr* program_header, - ELF::Off hole_start, - ssize_t hole_size) { - const ELF::Off segment_end = - program_header->p_offset + program_header->p_filesz; - - Elf_Scn* section = NULL; - Elf_Scn* last_section = NULL; - - while ((section = elf_nextscn(elf, section)) != NULL) { - const ELF::Shdr* section_header = ELF::getshdr(section); - - // As above, 'undo' any section offset adjustment to give a view of the - // original sections layout. - ELF::Off offset = section_header->sh_offset; - if (section_header->sh_offset >= hole_start) { - offset -= hole_size; - } - - if (offset < segment_end) { - last_section = section; - } - } - LOG_IF(FATAL, !last_section) - << "Cannot identify the last section in the given segment"; - - return last_section; -} - -// Helper for ResizeSection(). Order loadable segments by their offsets. -// The crazy linker contains assumptions about loadable segment ordering, -// and it is better if we do not break them. -void SortOrderSensitiveProgramHeaders(ELF::Phdr* program_headers, - size_t count) { - std::vector<ELF::Phdr*> orderable; - - // Collect together orderable program headers. These are all the LOAD - // segments, and any GNU_STACK that may be present (removed on packing, - // but replaced on unpacking). - for (size_t i = 0; i < count; ++i) { - ELF::Phdr* program_header = &program_headers[i]; - - if (program_header->p_type == PT_LOAD || - program_header->p_type == PT_GNU_STACK) { - orderable.push_back(program_header); + program_header->p_offset <= hole_start && + (program_header->p_offset + program_header->p_filesz) >= hole_start ) { + return program_header; } } + LOG(FATAL) << "Cannot locate a LOAD segment with hole_start=0x" << std::hex << hole_start; + NOTREACHED(); - // Order these program headers so that any PT_GNU_STACK is last, and - // the LOAD segments that precede it appear in offset order. Uses - // insertion sort. - for (size_t i = 1; i < orderable.size(); ++i) { - for (size_t j = i; j > 0; --j) { - ELF::Phdr* first = orderable[j - 1]; - ELF::Phdr* second = orderable[j]; - - if (!(first->p_type == PT_GNU_STACK || - first->p_offset > second->p_offset)) { - break; - } - std::swap(*first, *second); - } - } + return nullptr; } -// Helper for ResizeSection(). The GNU_STACK program header is unused in -// Android, so we can repurpose it here. Before packing, the program header -// table contains something like: -// -// Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align -// LOAD 0x000000 0x00000000 0x00000000 0x1efc818 0x1efc818 R E 0x1000 -// LOAD 0x1efd008 0x01efe008 0x01efe008 0x17ec3c 0x1a0324 RW 0x1000 -// DYNAMIC 0x205ec50 0x0205fc50 0x0205fc50 0x00108 0x00108 RW 0x4 -// GNU_STACK 0x000000 0x00000000 0x00000000 0x00000 0x00000 RW 0 -// -// The hole in the file is in the first of these. In order to preserve all -// load addresses, what we do is to turn the GNU_STACK into a new LOAD entry -// that maps segments up to where we created the hole, adjust the first LOAD -// entry so that it maps segments after that, adjust any other program -// headers whose offset is after the hole start, and finally order the LOAD -// segments by offset, to give: -// -// Type Offset VirtAddr PhysAddr FileSiz MemSiz Flg Align -// LOAD 0x000000 0x00000000 0x00000000 0x14ea4 0x14ea4 R E 0x1000 -// LOAD 0x014ea4 0x00212ea4 0x00212ea4 0x1cea164 0x1cea164 R E 0x1000 -// DYNAMIC 0x1e60c50 0x0205fc50 0x0205fc50 0x00108 0x00108 RW 0x4 -// LOAD 0x1cff008 0x01efe008 0x01efe008 0x17ec3c 0x1a0324 RW 0x1000 -// -// We work out the split points by finding the .rel.dyn or .rela.dyn section -// that contains the hole, and by finding the last section in a given segment. -// -// To unpack, we reverse the above to leave the file as it was originally. -void SplitProgramHeadersForHole(Elf* elf, - ELF::Off hole_start, - ssize_t hole_size) { - CHECK(hole_size < 0); - const ELF::Ehdr* elf_header = ELF::getehdr(elf); +// Helper for ResizeSection(). Rewrite program headers. +template <typename ELF> +static void RewriteProgramHeadersForHole(Elf* elf, + typename ELF::Off hole_start, + ssize_t hole_size) { + const typename ELF::Ehdr* elf_header = ELF::getehdr(elf); CHECK(elf_header); - ELF::Phdr* elf_program_header = ELF::getphdr(elf); + typename ELF::Phdr* elf_program_header = ELF::getphdr(elf); CHECK(elf_program_header); const size_t program_header_count = elf_header->e_phnum; // Locate the segment that we can overwrite to form the new LOAD entry, // and the segment that we are going to split into two parts. - ELF::Phdr* spliced_header = - FindUnusedGnuStackSegment(elf_program_header, program_header_count); - ELF::Phdr* split_header = - FindFirstLoadSegment(elf_program_header, program_header_count); - - VLOG(1) << "phdr[" << split_header - elf_program_header << "] split"; - VLOG(1) << "phdr[" << spliced_header - elf_program_header << "] new LOAD"; - - // Find the section that contains the hole. We split on the section that - // follows it. - Elf_Scn* holed_section = - FindSectionContainingHole(elf, hole_start, hole_size); - - size_t string_index; - elf_getshdrstrndx(elf, &string_index); - - ELF::Shdr* section_header = ELF::getshdr(holed_section); - std::string name = elf_strptr(elf, string_index, section_header->sh_name); - VLOG(1) << "section " << name << " split after"; - - // Find the last section in the segment we are splitting. - Elf_Scn* last_section = - FindLastSectionInSegment(elf, split_header, hole_start, hole_size); - - section_header = ELF::getshdr(last_section); - name = elf_strptr(elf, string_index, section_header->sh_name); - VLOG(1) << "section " << name << " split end"; - - // Split on the section following the holed one, and up to (but not - // including) the section following the last one in the split segment. - Elf_Scn* split_section = elf_nextscn(elf, holed_section); - LOG_IF(FATAL, !split_section) - << "No section follows the section that contains the hole"; - Elf_Scn* end_section = elf_nextscn(elf, last_section); - LOG_IF(FATAL, !end_section) - << "No section follows the last section in the segment being split"; - - // Split the first portion of split_header into spliced_header. - const ELF::Shdr* split_section_header = ELF::getshdr(split_section); - spliced_header->p_type = split_header->p_type; - spliced_header->p_offset = split_header->p_offset; - spliced_header->p_vaddr = split_header->p_vaddr; - spliced_header->p_paddr = split_header->p_paddr; - CHECK(split_header->p_filesz == split_header->p_memsz); - spliced_header->p_filesz = split_section_header->sh_offset; - spliced_header->p_memsz = split_section_header->sh_offset; - spliced_header->p_flags = split_header->p_flags; - spliced_header->p_align = split_header->p_align; - - // Now rewrite split_header to remove the part we spliced from it. - const ELF::Shdr* end_section_header = ELF::getshdr(end_section); - split_header->p_offset = spliced_header->p_filesz; - CHECK(split_header->p_vaddr == split_header->p_paddr); - split_header->p_vaddr = split_section_header->sh_addr; - split_header->p_paddr = split_section_header->sh_addr; - CHECK(split_header->p_filesz == split_header->p_memsz); - split_header->p_filesz = - end_section_header->sh_offset - spliced_header->p_filesz; - split_header->p_memsz = - end_section_header->sh_offset - spliced_header->p_filesz; - - // Adjust the offsets of all program headers that are not one of the pair - // we just created by splitting. - AdjustProgramHeaderOffsets(elf_program_header, - program_header_count, - spliced_header, - split_header, - hole_start, - hole_size); - - // Finally, order loadable segments by offset/address. The crazy linker - // contains assumptions about loadable segment ordering. - SortOrderSensitiveProgramHeaders(elf_program_header, - program_header_count); -} - -// Helper for ResizeSection(). Undo the work of SplitProgramHeadersForHole(). -void CoalesceProgramHeadersForHole(Elf* elf, - ELF::Off hole_start, - ssize_t hole_size) { - CHECK(hole_size > 0); - const ELF::Ehdr* elf_header = ELF::getehdr(elf); - CHECK(elf_header); - - ELF::Phdr* elf_program_header = ELF::getphdr(elf); - CHECK(elf_program_header); - - const size_t program_header_count = elf_header->e_phnum; - - // Locate the segment that we overwrote to form the new LOAD entry, and - // the segment that we split into two parts on packing. - ELF::Phdr* spliced_header = - FindFirstLoadSegment(elf_program_header, program_header_count); - ELF::Phdr* split_header = - FindOriginalFirstLoadSegment(elf_program_header, program_header_count); - - VLOG(1) << "phdr[" << spliced_header - elf_program_header << "] stack"; - VLOG(1) << "phdr[" << split_header - elf_program_header << "] coalesce"; - - // Find the last section in the second segment we are coalescing. - Elf_Scn* last_section = - FindLastSectionInSegment(elf, split_header, hole_start, hole_size); - - size_t string_index; - elf_getshdrstrndx(elf, &string_index); + typename ELF::Phdr* target_load_header = + FindLoadSegmentForHole<ELF>(elf_program_header, program_header_count, hole_start); - const ELF::Shdr* section_header = ELF::getshdr(last_section); - std::string name = elf_strptr(elf, string_index, section_header->sh_name); - VLOG(1) << "section " << name << " coalesced"; - - // Rewrite the coalesced segment into split_header. - const ELF::Shdr* last_section_header = ELF::getshdr(last_section); - split_header->p_offset = spliced_header->p_offset; - CHECK(split_header->p_vaddr == split_header->p_paddr); - split_header->p_vaddr = spliced_header->p_vaddr; - split_header->p_paddr = spliced_header->p_vaddr; - CHECK(split_header->p_filesz == split_header->p_memsz); - split_header->p_filesz = - last_section_header->sh_offset + last_section_header->sh_size; - split_header->p_memsz = - last_section_header->sh_offset + last_section_header->sh_size; - - // Reconstruct the original GNU_STACK segment into spliced_header. - spliced_header->p_type = PT_GNU_STACK; - spliced_header->p_offset = 0; - spliced_header->p_vaddr = 0; - spliced_header->p_paddr = 0; - spliced_header->p_filesz = 0; - spliced_header->p_memsz = 0; - spliced_header->p_flags = PF_R | PF_W; - spliced_header->p_align = ELF::kGnuStackSegmentAlignment; - - // Adjust the offsets of all program headers that are not one of the pair - // we just coalesced. - AdjustProgramHeaderOffsets(elf_program_header, - program_header_count, - spliced_header, - split_header, - hole_start, - hole_size); - - // Finally, order loadable segments by offset/address. The crazy linker - // contains assumptions about loadable segment ordering. - SortOrderSensitiveProgramHeaders(elf_program_header, - program_header_count); -} + VLOG(1) << "phdr[" << target_load_header - elf_program_header << "] adjust"; + // Adjust PT_LOAD program header memsz and filesz + target_load_header->p_filesz += hole_size; + target_load_header->p_memsz += hole_size; -// Helper for ResizeSection(). Rewrite program headers. -void RewriteProgramHeadersForHole(Elf* elf, - ELF::Off hole_start, - ssize_t hole_size) { - // If hole_size is negative then we are removing a piece of the file, and - // we want to split program headers so that we keep the same addresses - // for text and data. If positive, then we are putting that piece of the - // file back in, so we coalesce the previously split program headers. - if (hole_size < 0) - SplitProgramHeadersForHole(elf, hole_start, hole_size); - else if (hole_size > 0) - CoalesceProgramHeadersForHole(elf, hole_start, hole_size); + // Adjust the offsets and p_vaddrs + AdjustProgramHeaderOffsets<ELF>(elf_program_header, + program_header_count, + hole_start, + hole_size); } // Helper for ResizeSection(). Locate and return the dynamic section. -Elf_Scn* GetDynamicSection(Elf* elf) { - const ELF::Ehdr* elf_header = ELF::getehdr(elf); +template <typename ELF> +static Elf_Scn* GetDynamicSection(Elf* elf) { + const typename ELF::Ehdr* elf_header = ELF::getehdr(elf); CHECK(elf_header); - const ELF::Phdr* elf_program_header = ELF::getphdr(elf); + const typename ELF::Phdr* elf_program_header = ELF::getphdr(elf); CHECK(elf_program_header); // Find the program header that describes the dynamic section. - const ELF::Phdr* dynamic_program_header = NULL; + const typename ELF::Phdr* dynamic_program_header = NULL; for (size_t i = 0; i < elf_header->e_phnum; ++i) { - const ELF::Phdr* program_header = &elf_program_header[i]; + const typename ELF::Phdr* program_header = &elf_program_header[i]; if (program_header->p_type == PT_DYNAMIC) { dynamic_program_header = program_header; @@ -741,7 +393,7 @@ Elf_Scn* GetDynamicSection(Elf* elf) { Elf_Scn* dynamic_section = NULL; Elf_Scn* section = NULL; while ((section = elf_nextscn(elf, section)) != NULL) { - ELF::Shdr* section_header = ELF::getshdr(section); + typename ELF::Shdr* section_header = ELF::getshdr(section); if (section_header->sh_offset == dynamic_program_header->p_offset) { dynamic_section = section; @@ -753,47 +405,61 @@ Elf_Scn* GetDynamicSection(Elf* elf) { } // Helper for ResizeSection(). Adjust the .dynamic section for the hole. -template <typename Rel> -void AdjustDynamicSectionForHole(Elf_Scn* dynamic_section, - ELF::Off hole_start, - ssize_t hole_size) { +template <typename ELF> +void ElfFile<ELF>::AdjustDynamicSectionForHole(Elf_Scn* dynamic_section, + typename ELF::Off hole_start, + ssize_t hole_size, + relocations_type_t relocations_type) { + CHECK(relocations_type != NONE); Elf_Data* data = GetSectionData(dynamic_section); - const ELF::Dyn* dynamic_base = reinterpret_cast<ELF::Dyn*>(data->d_buf); - std::vector<ELF::Dyn> dynamics( + auto dynamic_base = reinterpret_cast<typename ELF::Dyn*>(data->d_buf); + std::vector<typename ELF::Dyn> dynamics( dynamic_base, dynamic_base + data->d_size / sizeof(dynamics[0])); + if (hole_size > 0) { // expanding + hole_start += hole_size; + } + for (size_t i = 0; i < dynamics.size(); ++i) { - ELF::Dyn* dynamic = &dynamics[i]; - const ELF::Sword tag = dynamic->d_tag; + typename ELF::Dyn* dynamic = &dynamics[i]; + const typename ELF::Sword tag = dynamic->d_tag; + + // Any tags that hold offsets are adjustment candidates. + const bool is_adjustable = (tag == DT_PLTGOT || + tag == DT_HASH || + tag == DT_GNU_HASH || + tag == DT_STRTAB || + tag == DT_SYMTAB || + tag == DT_RELA || + tag == DT_INIT || + tag == DT_FINI || + tag == DT_REL || + tag == DT_JMPREL || + tag == DT_INIT_ARRAY || + tag == DT_FINI_ARRAY || + tag == DT_ANDROID_REL|| + tag == DT_ANDROID_RELA); + + if (is_adjustable && dynamic->d_un.d_ptr <= hole_start) { + dynamic->d_un.d_ptr -= hole_size; + VLOG(1) << "dynamic[" << i << "] " << dynamic->d_tag + << " d_ptr adjusted to " << dynamic->d_un.d_ptr; + } // DT_RELSZ or DT_RELASZ indicate the overall size of relocations. // Only one will be present. Adjust by hole size. - if (tag == DT_RELSZ || tag == DT_RELASZ) { + if (tag == DT_RELSZ || tag == DT_RELASZ || tag == DT_ANDROID_RELSZ || tag == DT_ANDROID_RELASZ) { dynamic->d_un.d_val += hole_size; VLOG(1) << "dynamic[" << i << "] " << dynamic->d_tag << " d_val adjusted to " << dynamic->d_un.d_val; } - // DT_RELCOUNT or DT_RELACOUNT hold the count of relative relocations. - // Only one will be present. Packing reduces it to the alignment - // padding, if any; unpacking restores it to its former value. The - // crazy linker does not use it, but we update it anyway. - if (tag == DT_RELCOUNT || tag == DT_RELACOUNT) { - // Cast sizeof to a signed type to avoid the division result being - // promoted into an unsigned size_t. - const ssize_t sizeof_rel = static_cast<ssize_t>(sizeof(Rel)); - dynamic->d_un.d_val += hole_size / sizeof_rel; - VLOG(1) << "dynamic[" << i << "] " << dynamic->d_tag - << " d_val adjusted to " << dynamic->d_un.d_val; - } + // Ignore DT_RELCOUNT and DT_RELACOUNT: (1) nobody uses them and + // technically (2) the relative relocation count is not changed. - // DT_RELENT and DT_RELAENT do not change, but make sure they are what - // we expect. Only one will be present. - if (tag == DT_RELENT || tag == DT_RELAENT) { - CHECK(dynamic->d_un.d_val == sizeof(Rel)); - } + // DT_RELENT and DT_RELAENT don't change, ignore them as well. } void* section_data = &dynamics[0]; @@ -804,19 +470,19 @@ void AdjustDynamicSectionForHole(Elf_Scn* dynamic_section, // Resize a section. If the new size is larger than the current size, open // up a hole by increasing file offsets that come after the hole. If smaller // than the current size, remove the hole by decreasing those offsets. -template <typename Rel> -void ResizeSection(Elf* elf, Elf_Scn* section, size_t new_size) { - ELF::Shdr* section_header = ELF::getshdr(section); - if (section_header->sh_size == new_size) - return; +template <typename ELF> +void ElfFile<ELF>::ResizeSection(Elf* elf, Elf_Scn* section, size_t new_size, + typename ELF::Word new_sh_type, + relocations_type_t relocations_type) { - // Note if we are resizing the real dyn relocations. size_t string_index; elf_getshdrstrndx(elf, &string_index); - const std::string section_name = - elf_strptr(elf, string_index, section_header->sh_name); - const bool is_relocations_resize = - (section_name == ".rel.dyn" || section_name == ".rela.dyn"); + auto section_header = ELF::getshdr(section); + std::string name = elf_strptr(elf, string_index, section_header->sh_name); + + if (section_header->sh_size == new_size) { + return; + } // Require that the section size and the data size are the same. True // in practice for all sections we resize when packing or unpacking. @@ -827,61 +493,72 @@ void ResizeSection(Elf* elf, Elf_Scn* section, size_t new_size) { // data that we can validly expand). CHECK(data->d_size && data->d_buf); - const ELF::Off hole_start = section_header->sh_offset; + const auto hole_start = section_header->sh_offset; const ssize_t hole_size = new_size - data->d_size; - VLOG_IF(1, (hole_size > 0)) << "expand section size = " << data->d_size; - VLOG_IF(1, (hole_size < 0)) << "shrink section size = " << data->d_size; + VLOG_IF(1, (hole_size > 0)) << "expand section (" << name << ") size: " << + data->d_size << " -> " << (data->d_size + hole_size); + VLOG_IF(1, (hole_size < 0)) << "shrink section (" << name << ") size: " << + data->d_size << " -> " << (data->d_size + hole_size); + + // libelf overrides sh_entsize for known sh_types, so it does not matter what we set + // for SHT_REL/SHT_RELA. + typename ELF::Xword new_entsize = + (new_sh_type == SHT_ANDROID_REL || new_sh_type == SHT_ANDROID_RELA) ? 1 : 0; + + VLOG(1) << "Update section (" << name << ") entry size: " << + section_header->sh_entsize << " -> " << new_entsize; // Resize the data and the section header. data->d_size += hole_size; section_header->sh_size += hole_size; + section_header->sh_entsize = new_entsize; + section_header->sh_type = new_sh_type; // Add the hole size to all offsets in the ELF file that are after the // start of the hole. If the hole size is positive we are expanding the // section to create a new hole; if negative, we are closing up a hole. // Start with the main ELF header. - ELF::Ehdr* elf_header = ELF::getehdr(elf); - AdjustElfHeaderForHole(elf_header, hole_start, hole_size); + typename ELF::Ehdr* elf_header = ELF::getehdr(elf); + AdjustElfHeaderForHole<ELF>(elf_header, hole_start, hole_size); // Adjust all section headers. - AdjustSectionHeadersForHole(elf, hole_start, hole_size); + AdjustSectionHeadersForHole<ELF>(elf, hole_start, hole_size); - // If resizing the dynamic relocations, rewrite the program headers to - // either split or coalesce segments, and adjust dynamic entries to match. - if (is_relocations_resize) { - RewriteProgramHeadersForHole(elf, hole_start, hole_size); + // Rewrite the program headers to either split or coalesce segments, + // and adjust dynamic entries to match. + RewriteProgramHeadersForHole<ELF>(elf, hole_start, hole_size); - Elf_Scn* dynamic_section = GetDynamicSection(elf); - AdjustDynamicSectionForHole<Rel>(dynamic_section, hole_start, hole_size); - } + Elf_Scn* dynamic_section = GetDynamicSection<ELF>(elf); + AdjustDynamicSectionForHole(dynamic_section, hole_start, hole_size, relocations_type); } // Find the first slot in a dynamics array with the given tag. The array // always ends with a free (unused) element, and which we exclude from the // search. Returns dynamics->size() if not found. -size_t FindDynamicEntry(ELF::Sword tag, - std::vector<ELF::Dyn>* dynamics) { +template <typename ELF> +static size_t FindDynamicEntry(typename ELF::Sword tag, + std::vector<typename ELF::Dyn>* dynamics) { // Loop until the penultimate entry. We exclude the end sentinel. for (size_t i = 0; i < dynamics->size() - 1; ++i) { - if (dynamics->at(i).d_tag == tag) + if (dynamics->at(i).d_tag == tag) { return i; + } } // The tag was not found. return dynamics->size(); } -// Replace the first free (unused) slot in a dynamics vector with the given -// value. The vector always ends with a free (unused) element, so the slot -// found cannot be the last one in the vector. -void AddDynamicEntry(const ELF::Dyn& dyn, - std::vector<ELF::Dyn>* dynamics) { - const size_t slot = FindDynamicEntry(DT_NULL, dynamics); +// Replace dynamic entry. +template <typename ELF> +static void ReplaceDynamicEntry(typename ELF::Sword tag, + const typename ELF::Dyn& dyn, + std::vector<typename ELF::Dyn>* dynamics) { + const size_t slot = FindDynamicEntry<ELF>(tag, dynamics); if (slot == dynamics->size()) { - LOG(FATAL) << "No spare dynamic array slots found " - << "(to fix, increase gold's --spare-dynamic-tags value)"; + LOG(FATAL) << "Dynamic slot is not found for tag=" << tag; } // Replace this entry with the one supplied. @@ -889,53 +566,10 @@ void AddDynamicEntry(const ELF::Dyn& dyn, VLOG(1) << "dynamic[" << slot << "] overwritten with " << dyn.d_tag; } -// Remove the element in the dynamics vector that matches the given tag with -// unused slot data. Shuffle the following elements up, and ensure that the -// last is the null sentinel. -void RemoveDynamicEntry(ELF::Sword tag, - std::vector<ELF::Dyn>* dynamics) { - const size_t slot = FindDynamicEntry(tag, dynamics); - CHECK(slot != dynamics->size()); - - // Remove this entry by shuffling up everything that follows. - for (size_t i = slot; i < dynamics->size() - 1; ++i) { - dynamics->at(i) = dynamics->at(i + 1); - VLOG(1) << "dynamic[" << i - << "] overwritten with dynamic[" << i + 1 << "]"; - } - - // Ensure that the end sentinel is still present. - CHECK(dynamics->at(dynamics->size() - 1).d_tag == DT_NULL); -} - -// Construct a null relocation without addend. -void NullRelocation(ELF::Rel* relocation) { - relocation->r_offset = 0; - relocation->r_info = ELF_R_INFO(0, ELF::kNoRelocationCode); -} - -// Construct a null relocation with addend. -void NullRelocation(ELF::Rela* relocation) { - relocation->r_offset = 0; - relocation->r_info = ELF_R_INFO(0, ELF::kNoRelocationCode); - relocation->r_addend = 0; -} - -// Pad relocations with the given number of null entries. Generates its -// null entry with the appropriate NullRelocation() invocation. -template <typename Rel> -void PadRelocations(size_t count, std::vector<Rel>* relocations) { - Rel null_relocation; - NullRelocation(&null_relocation); - std::vector<Rel> padding(count, null_relocation); - relocations->insert(relocations->end(), padding.begin(), padding.end()); -} - -} // namespace - // Remove relative entries from dynamic relocations and write as packed // data into android packed relocations. -bool ElfFile::PackRelocations() { +template <typename ELF> +bool ElfFile<ELF>::PackRelocations() { // Load the ELF file into libelf. if (!Load()) { LOG(ERROR) << "Failed to load as ELF"; @@ -944,175 +578,129 @@ bool ElfFile::PackRelocations() { // Retrieve the current dynamic relocations section data. Elf_Data* data = GetSectionData(relocations_section_); + // we always pack rela, because packed format is pretty much the same + std::vector<typename ELF::Rela> relocations; if (relocations_type_ == REL) { // Convert data to a vector of relocations. - const ELF::Rel* relocations_base = reinterpret_cast<ELF::Rel*>(data->d_buf); - std::vector<ELF::Rel> relocations( - relocations_base, - relocations_base + data->d_size / sizeof(relocations[0])); - + const typename ELF::Rel* relocations_base = reinterpret_cast<typename ELF::Rel*>(data->d_buf); + ConvertRelArrayToRelaVector(relocations_base, + data->d_size / sizeof(typename ELF::Rel), &relocations); LOG(INFO) << "Relocations : REL"; - return PackTypedRelocations<ELF::Rel>(relocations); - } - - if (relocations_type_ == RELA) { + } else if (relocations_type_ == RELA) { // Convert data to a vector of relocations with addends. - const ELF::Rela* relocations_base = - reinterpret_cast<ELF::Rela*>(data->d_buf); - std::vector<ELF::Rela> relocations( + const typename ELF::Rela* relocations_base = reinterpret_cast<typename ELF::Rela*>(data->d_buf); + relocations = std::vector<typename ELF::Rela>( relocations_base, relocations_base + data->d_size / sizeof(relocations[0])); LOG(INFO) << "Relocations : RELA"; - return PackTypedRelocations<ELF::Rela>(relocations); + } else { + NOTREACHED(); } - NOTREACHED(); - return false; + return PackTypedRelocations(&relocations); } // Helper for PackRelocations(). Rel type is one of ELF::Rel or ELF::Rela. -template <typename Rel> -bool ElfFile::PackTypedRelocations(const std::vector<Rel>& relocations) { - // Filter relocations into those that are relative and others. - std::vector<Rel> relative_relocations; - std::vector<Rel> other_relocations; - - for (size_t i = 0; i < relocations.size(); ++i) { - const Rel& relocation = relocations[i]; - if (ELF_R_TYPE(relocation.r_info) == ELF::kRelativeRelocationCode) { - CHECK(ELF_R_SYM(relocation.r_info) == 0); - relative_relocations.push_back(relocation); - } else { - other_relocations.push_back(relocation); - } - } - LOG(INFO) << "Relative : " << relative_relocations.size() << " entries"; - LOG(INFO) << "Other : " << other_relocations.size() << " entries"; - LOG(INFO) << "Total : " << relocations.size() << " entries"; +template <typename ELF> +bool ElfFile<ELF>::PackTypedRelocations(std::vector<typename ELF::Rela>* relocations) { + typedef typename ELF::Rela Rela; - // If no relative relocations then we have nothing packable. Perhaps + // If no relocations then we have nothing packable. Perhaps // the shared object has already been packed? - if (relative_relocations.empty()) { - LOG(ERROR) << "No relative relocations found (already packed?)"; + if (relocations->empty()) { + LOG(ERROR) << "No relocations found (already packed?)"; return false; } - // If not padding fully, apply only enough padding to preserve alignment. - // Otherwise, pad so that we do not shrink the relocations section at all. - if (!is_padding_relocations_) { - // Calculate the size of the hole we will close up when we rewrite - // dynamic relocations. - ssize_t hole_size = - relative_relocations.size() * sizeof(relative_relocations[0]); - const ssize_t unaligned_hole_size = hole_size; - - // Adjust the actual hole size to preserve alignment. We always adjust - // by a whole number of NONE-type relocations. - while (hole_size % kPreserveAlignment) - hole_size -= sizeof(relative_relocations[0]); - LOG(INFO) << "Compaction : " << hole_size << " bytes"; - - // Adjusting for alignment may have removed any packing benefit. - if (hole_size == 0) { - LOG(INFO) << "Too few relative relocations to pack after alignment"; - return false; - } + const size_t rel_size = + relocations_type_ == RELA ? sizeof(typename ELF::Rela) : sizeof(typename ELF::Rel); + const size_t initial_bytes = relocations->size() * rel_size; - // Find the padding needed in other_relocations to preserve alignment. - // Ensure that we never completely empty the real relocations section. - size_t padding_bytes = unaligned_hole_size - hole_size; - if (padding_bytes == 0 && other_relocations.size() == 0) { - do { - padding_bytes += sizeof(relative_relocations[0]); - } while (padding_bytes % kPreserveAlignment); - } - CHECK(padding_bytes % sizeof(other_relocations[0]) == 0); - const size_t padding = padding_bytes / sizeof(other_relocations[0]); + LOG(INFO) << "Unpacked : " << initial_bytes << " bytes"; + std::vector<uint8_t> packed; + RelocationPacker<ELF> packer; - // Padding may have removed any packing benefit. - if (padding >= relative_relocations.size()) { - LOG(INFO) << "Too few relative relocations to pack after padding"; - return false; - } + // Pack relocations: dry run to estimate memory savings. + packer.PackRelocations(*relocations, &packed); + const size_t packed_bytes_estimate = packed.size() * sizeof(packed[0]); + LOG(INFO) << "Packed (no padding): " << packed_bytes_estimate << " bytes"; - // Add null relocations to other_relocations to preserve alignment. - PadRelocations<Rel>(padding, &other_relocations); - LOG(INFO) << "Alignment pad : " << padding << " relocations"; - } else { - // If padding, add NONE-type relocations to other_relocations to make it - // the same size as the the original relocations we read in. This makes - // the ResizeSection() below a no-op. - const size_t padding = relocations.size() - other_relocations.size(); - PadRelocations<Rel>(padding, &other_relocations); + if (packed.empty()) { + LOG(INFO) << "Too few relocations to pack"; + return false; } - // Pack relative relocations. - const size_t initial_bytes = - relative_relocations.size() * sizeof(relative_relocations[0]); - LOG(INFO) << "Unpacked relative: " << initial_bytes << " bytes"; - std::vector<uint8_t> packed; - RelocationPacker packer; - packer.PackRelativeRelocations(relative_relocations, &packed); - const void* packed_data = &packed[0]; - const size_t packed_bytes = packed.size() * sizeof(packed[0]); - LOG(INFO) << "Packed relative: " << packed_bytes << " bytes"; + // Pre-calculate the size of the hole we will close up when we rewrite + // dynamic relocations. We have to adjust relocation addresses to + // account for this. + typename ELF::Shdr* section_header = ELF::getshdr(relocations_section_); + ssize_t hole_size = initial_bytes - packed_bytes_estimate; - // If we have insufficient relative relocations to form a run then - // packing fails. - if (packed.empty()) { - LOG(INFO) << "Too few relative relocations to pack"; + // hole_size needs to be page_aligned. + hole_size -= hole_size % kPreserveAlignment; + + LOG(INFO) << "Compaction : " << hole_size << " bytes"; + + // Adjusting for alignment may have removed any packing benefit. + if (hole_size == 0) { + LOG(INFO) << "Too few relocations to pack after alignment"; return false; } + if (hole_size <= 0) { + LOG(INFO) << "Packing relocations saves no space"; + return false; + } + + size_t data_padding_bytes = is_padding_relocations_ ? + initial_bytes - packed_bytes_estimate : + initial_bytes - hole_size - packed_bytes_estimate; + + // pad data + std::vector<uint8_t> padding(data_padding_bytes, 0); + packed.insert(packed.end(), padding.begin(), padding.end()); + + const void* packed_data = &packed[0]; + // Run a loopback self-test as a check that packing is lossless. - std::vector<Rel> unpacked; - packer.UnpackRelativeRelocations(packed, &unpacked); - CHECK(unpacked.size() == relative_relocations.size()); + std::vector<Rela> unpacked; + packer.UnpackRelocations(packed, &unpacked); + CHECK(unpacked.size() == relocations->size()); CHECK(!memcmp(&unpacked[0], - &relative_relocations[0], + &relocations->at(0), unpacked.size() * sizeof(unpacked[0]))); - // Make sure packing saved some space. - if (packed_bytes >= initial_bytes) { - LOG(INFO) << "Packing relative relocations saves no space"; - return false; - } - - // Rewrite the current dynamic relocations section to be only the ARM - // non-relative relocations, then shrink it to size. - const void* section_data = &other_relocations[0]; - const size_t bytes = other_relocations.size() * sizeof(other_relocations[0]); - ResizeSection<Rel>(elf_, relocations_section_, bytes); - RewriteSectionData(relocations_section_, section_data, bytes); + // Rewrite the current dynamic relocations section with packed one then shrink it to size. + const size_t bytes = packed.size() * sizeof(packed[0]); + ResizeSection(elf_, relocations_section_, bytes, + relocations_type_ == REL ? SHT_ANDROID_REL : SHT_ANDROID_RELA, relocations_type_); + RewriteSectionData(relocations_section_, packed_data, bytes); - // Rewrite the current packed android relocations section to hold the packed - // relative relocations. - ResizeSection<Rel>(elf_, android_relocations_section_, packed_bytes); - RewriteSectionData(android_relocations_section_, packed_data, packed_bytes); + // TODO (dimitry): fix string table and replace .rel.dyn/plt with .android.rel.dyn/plt - // Rewrite .dynamic to include two new tags describing the packed android + // Rewrite .dynamic and rename relocation tags describing the packed android // relocations. Elf_Data* data = GetSectionData(dynamic_section_); - const ELF::Dyn* dynamic_base = reinterpret_cast<ELF::Dyn*>(data->d_buf); - std::vector<ELF::Dyn> dynamics( + const typename ELF::Dyn* dynamic_base = reinterpret_cast<typename ELF::Dyn*>(data->d_buf); + std::vector<typename ELF::Dyn> dynamics( dynamic_base, dynamic_base + data->d_size / sizeof(dynamics[0])); - // Use two of the spare slots to describe the packed section. - ELF::Shdr* section_header = ELF::getshdr(android_relocations_section_); + section_header = ELF::getshdr(relocations_section_); { - ELF::Dyn dyn; - dyn.d_tag = DT_ANDROID_REL_OFFSET; - dyn.d_un.d_ptr = section_header->sh_offset; - AddDynamicEntry(dyn, &dynamics); + typename ELF::Dyn dyn; + dyn.d_tag = relocations_type_ == REL ? DT_ANDROID_REL : DT_ANDROID_RELA; + dyn.d_un.d_ptr = section_header->sh_addr; + ReplaceDynamicEntry<ELF>(relocations_type_ == REL ? DT_REL : DT_RELA, dyn, &dynamics); } { - ELF::Dyn dyn; - dyn.d_tag = DT_ANDROID_REL_SIZE; + typename ELF::Dyn dyn; + dyn.d_tag = relocations_type_ == REL ? DT_ANDROID_RELSZ : DT_ANDROID_RELASZ; dyn.d_un.d_val = section_header->sh_size; - AddDynamicEntry(dyn, &dynamics); + ReplaceDynamicEntry<ELF>(relocations_type_ == REL ? DT_RELSZ : DT_RELASZ, dyn, &dynamics); } + const void* dynamics_data = &dynamics[0]; const size_t dynamics_bytes = dynamics.size() * sizeof(dynamics[0]); RewriteSectionData(dynamic_section_, dynamics_data, dynamics_bytes); @@ -1124,15 +712,17 @@ bool ElfFile::PackTypedRelocations(const std::vector<Rel>& relocations) { // Find packed relative relocations in the packed android relocations // section, unpack them, and rewrite the dynamic relocations section to // contain unpacked data. -bool ElfFile::UnpackRelocations() { +template <typename ELF> +bool ElfFile<ELF>::UnpackRelocations() { // Load the ELF file into libelf. if (!Load()) { LOG(ERROR) << "Failed to load as ELF"; return false; } + typename ELF::Shdr* section_header = ELF::getshdr(relocations_section_); // Retrieve the current packed android relocations section data. - Elf_Data* data = GetSectionData(android_relocations_section_); + Elf_Data* data = GetSectionData(relocations_section_); // Convert data to a vector of bytes. const uint8_t* packed_base = reinterpret_cast<uint8_t*>(data->d_buf); @@ -1140,118 +730,94 @@ bool ElfFile::UnpackRelocations() { packed_base, packed_base + data->d_size / sizeof(packed[0])); - if (packed.size() > 3 && + if ((section_header->sh_type == SHT_ANDROID_RELA || section_header->sh_type == SHT_ANDROID_REL) && + packed.size() > 3 && packed[0] == 'A' && packed[1] == 'P' && - packed[2] == 'R' && - packed[3] == '1') { - // Signature is APR1, unpack relocations. - CHECK(relocations_type_ == REL); - LOG(INFO) << "Relocations : REL"; - return UnpackTypedRelocations<ELF::Rel>(packed); - } - - if (packed.size() > 3 && - packed[0] == 'A' && - packed[1] == 'P' && - packed[2] == 'A' && - packed[3] == '1') { - // Signature is APA1, unpack relocations with addends. - CHECK(relocations_type_ == RELA); - LOG(INFO) << "Relocations : RELA"; - return UnpackTypedRelocations<ELF::Rela>(packed); + (packed[2] == 'U' || packed[2] == 'S') && + packed[3] == '2') { + LOG(INFO) << "Relocations : " << (relocations_type_ == REL ? "REL" : "RELA"); + } else { + LOG(ERROR) << "Packed relocations not found (not packed?)"; + return false; } - LOG(ERROR) << "Packed relative relocations not found (not packed?)"; - return false; + return UnpackTypedRelocations(packed); } // Helper for UnpackRelocations(). Rel type is one of ELF::Rel or ELF::Rela. -template <typename Rel> -bool ElfFile::UnpackTypedRelocations(const std::vector<uint8_t>& packed) { +template <typename ELF> +bool ElfFile<ELF>::UnpackTypedRelocations(const std::vector<uint8_t>& packed) { // Unpack the data to re-materialize the relative relocations. const size_t packed_bytes = packed.size() * sizeof(packed[0]); - LOG(INFO) << "Packed relative: " << packed_bytes << " bytes"; - std::vector<Rel> relative_relocations; - RelocationPacker packer; - packer.UnpackRelativeRelocations(packed, &relative_relocations); - const size_t unpacked_bytes = - relative_relocations.size() * sizeof(relative_relocations[0]); - LOG(INFO) << "Unpacked relative: " << unpacked_bytes << " bytes"; + LOG(INFO) << "Packed : " << packed_bytes << " bytes"; + std::vector<typename ELF::Rela> unpacked_relocations; + RelocationPacker<ELF> packer; + packer.UnpackRelocations(packed, &unpacked_relocations); + + const size_t relocation_entry_size = + relocations_type_ == REL ? sizeof(typename ELF::Rel) : sizeof(typename ELF::Rela); + const size_t unpacked_bytes = unpacked_relocations.size() * relocation_entry_size; + LOG(INFO) << "Unpacked : " << unpacked_bytes << " bytes"; // Retrieve the current dynamic relocations section data. Elf_Data* data = GetSectionData(relocations_section_); - // Interpret data as relocations. - const Rel* relocations_base = reinterpret_cast<Rel*>(data->d_buf); - std::vector<Rel> relocations( - relocations_base, - relocations_base + data->d_size / sizeof(relocations[0])); - - std::vector<Rel> other_relocations; - size_t padding = 0; - - // Filter relocations to locate any that are NONE-type. These will occur - // if padding was turned on for packing. - for (size_t i = 0; i < relocations.size(); ++i) { - const Rel& relocation = relocations[i]; - if (ELF_R_TYPE(relocation.r_info) != ELF::kNoRelocationCode) { - other_relocations.push_back(relocation); - } else { - ++padding; - } - } - LOG(INFO) << "Relative : " << relative_relocations.size() << " entries"; - LOG(INFO) << "Other : " << other_relocations.size() << " entries"; + LOG(INFO) << "Relocations : " << unpacked_relocations.size() << " entries"; // If we found the same number of null relocation entries in the dynamic // relocations section as we hold as unpacked relative relocations, then // this is a padded file. - const bool is_padded = padding == relative_relocations.size(); - // Unless padded, report by how much we expand the file. + const bool is_padded = packed_bytes == unpacked_bytes; + + // Unless padded, pre-apply relative relocations to account for the + // hole, and pre-adjust all relocation offsets accordingly. + typename ELF::Shdr* section_header = ELF::getshdr(relocations_section_); + if (!is_padded) { - // Calculate the size of the hole we will open up when we rewrite - // dynamic relocations. - ssize_t hole_size = - relative_relocations.size() * sizeof(relative_relocations[0]); - - // Adjust the hole size for the padding added to preserve alignment. - hole_size -= padding * sizeof(other_relocations[0]); - LOG(INFO) << "Expansion : " << hole_size << " bytes"; + LOG(INFO) << "Expansion : " << unpacked_bytes - packed_bytes << " bytes"; } - // Rewrite the current dynamic relocations section to be the relative - // relocations followed by other relocations. This is the usual order in - // which we find them after linking, so this action will normally put the - // entire dynamic relocations section back to its pre-split-and-packed state. - relocations.assign(relative_relocations.begin(), relative_relocations.end()); - relocations.insert(relocations.end(), - other_relocations.begin(), other_relocations.end()); - const void* section_data = &relocations[0]; - const size_t bytes = relocations.size() * sizeof(relocations[0]); - LOG(INFO) << "Total : " << relocations.size() << " entries"; - ResizeSection<Rel>(elf_, relocations_section_, bytes); - RewriteSectionData(relocations_section_, section_data, bytes); - - // Nearly empty the current packed android relocations section. Leaves a - // four-byte stub so that some data remains allocated to the section. - // This is a convenience which allows us to re-pack this file again without - // having to remove the section and then add a new small one with objcopy. - // The way we resize sections relies on there being some data in a section. - ResizeSection<Rel>( - elf_, android_relocations_section_, sizeof(kStubIdentifier)); - RewriteSectionData( - android_relocations_section_, &kStubIdentifier, sizeof(kStubIdentifier)); + // Rewrite the current dynamic relocations section with unpacked version of + // relocations. + const void* section_data = nullptr; + std::vector<typename ELF::Rel> unpacked_rel_relocations; + if (relocations_type_ == RELA) { + section_data = &unpacked_relocations[0]; + } else if (relocations_type_ == REL) { + ConvertRelaVectorToRelVector(unpacked_relocations, &unpacked_rel_relocations); + section_data = &unpacked_rel_relocations[0]; + } else { + NOTREACHED(); + } + + ResizeSection(elf_, relocations_section_, unpacked_bytes, + relocations_type_ == REL ? SHT_REL : SHT_RELA, relocations_type_); + RewriteSectionData(relocations_section_, section_data, unpacked_bytes); // Rewrite .dynamic to remove two tags describing packed android relocations. data = GetSectionData(dynamic_section_); - const ELF::Dyn* dynamic_base = reinterpret_cast<ELF::Dyn*>(data->d_buf); - std::vector<ELF::Dyn> dynamics( + const typename ELF::Dyn* dynamic_base = reinterpret_cast<typename ELF::Dyn*>(data->d_buf); + std::vector<typename ELF::Dyn> dynamics( dynamic_base, dynamic_base + data->d_size / sizeof(dynamics[0])); - RemoveDynamicEntry(DT_ANDROID_REL_OFFSET, &dynamics); - RemoveDynamicEntry(DT_ANDROID_REL_SIZE, &dynamics); + { + typename ELF::Dyn dyn; + dyn.d_tag = relocations_type_ == REL ? DT_REL : DT_RELA; + dyn.d_un.d_ptr = section_header->sh_addr; + ReplaceDynamicEntry<ELF>(relocations_type_ == REL ? DT_ANDROID_REL : DT_ANDROID_RELA, + dyn, &dynamics); + } + + { + typename ELF::Dyn dyn; + dyn.d_tag = relocations_type_ == REL ? DT_RELSZ : DT_RELASZ; + dyn.d_un.d_val = section_header->sh_size; + ReplaceDynamicEntry<ELF>(relocations_type_ == REL ? DT_ANDROID_RELSZ : DT_ANDROID_RELASZ, + dyn, &dynamics); + } + const void* dynamics_data = &dynamics[0]; const size_t dynamics_bytes = dynamics.size() * sizeof(dynamics[0]); RewriteSectionData(dynamic_section_, dynamics_data, dynamics_bytes); @@ -1261,7 +827,8 @@ bool ElfFile::UnpackTypedRelocations(const std::vector<uint8_t>& packed) { } // Flush rewritten shared object file data. -void ElfFile::Flush() { +template <typename ELF> +void ElfFile<ELF>::Flush() { // Flag all ELF data held in memory as needing to be written back to the // file, and tell libelf that we have controlled the file layout. elf_flagelf(elf_, ELF_C_SET, ELF_F_DIRTY); @@ -1269,6 +836,10 @@ void ElfFile::Flush() { // Write ELF data back to disk. const off_t file_bytes = elf_update(elf_, ELF_C_WRITE); + if (file_bytes == -1) { + LOG(ERROR) << "elf_update failed: " << elf_errmsg(elf_errno()); + } + CHECK(file_bytes > 0); VLOG(1) << "elf_update returned: " << file_bytes; @@ -1280,4 +851,32 @@ void ElfFile::Flush() { CHECK(truncate == 0); } +template <typename ELF> +void ElfFile<ELF>::ConvertRelArrayToRelaVector(const typename ELF::Rel* rel_array, + size_t rel_array_size, + std::vector<typename ELF::Rela>* rela_vector) { + for (size_t i = 0; i<rel_array_size; ++i) { + typename ELF::Rela rela; + rela.r_offset = rel_array[i].r_offset; + rela.r_info = rel_array[i].r_info; + rela.r_addend = 0; + rela_vector->push_back(rela); + } +} + +template <typename ELF> +void ElfFile<ELF>::ConvertRelaVectorToRelVector(const std::vector<typename ELF::Rela>& rela_vector, + std::vector<typename ELF::Rel>* rel_vector) { + for (auto rela : rela_vector) { + typename ELF::Rel rel; + rel.r_offset = rela.r_offset; + rel.r_info = rela.r_info; + CHECK(rela.r_addend == 0); + rel_vector->push_back(rel); + } +} + +template class ElfFile<ELF32_traits>; +template class ElfFile<ELF64_traits>; + } // namespace relocation_packer diff --git a/tools/relocation_packer/src/elf_file.h b/tools/relocation_packer/src/elf_file.h index 6550274..73c3192 100644 --- a/tools/relocation_packer/src/elf_file.h +++ b/tools/relocation_packer/src/elf_file.h @@ -67,12 +67,13 @@ namespace relocation_packer { // An ElfFile reads shared objects, and shuttles relative relocations // between .rel.dyn or .rela.dyn and .android.rel.dyn or .android.rela.dyn // sections. +template <typename ELF> class ElfFile { public: explicit ElfFile(int fd) : fd_(fd), is_padding_relocations_(false), elf_(NULL), relocations_section_(NULL), dynamic_section_(NULL), - android_relocations_section_(NULL), relocations_type_(NONE) {} + relocations_type_(NONE) {} ~ElfFile() {} // Set padding mode. When padding, PackRelocations() will not shrink @@ -92,6 +93,10 @@ class ElfFile { bool UnpackRelocations(); private: + enum relocations_type_t { + NONE = 0, REL, RELA + }; + // Load a new ElfFile from a filedescriptor. If flushing, the file must // be open for read/write. Returns true on successful ELF file load. // |fd| is an open file descriptor for the shared object. @@ -99,17 +104,34 @@ class ElfFile { // Templated packer, helper for PackRelocations(). Rel type is one of // ELF::Rel or ELF::Rela. - template <typename Rel> - bool PackTypedRelocations(const std::vector<Rel>& relocations); + bool PackTypedRelocations(std::vector<typename ELF::Rela>* relocations); // Templated unpacker, helper for UnpackRelocations(). Rel type is one of // ELF::Rel or ELF::Rela. - template <typename Rel> bool UnpackTypedRelocations(const std::vector<uint8_t>& packed); // Write ELF file changes. void Flush(); + void AdjustRelativeRelocationTargets(typename ELF::Off hole_start, + ssize_t hole_size, + std::vector<typename ELF::Rela>* relocations); + + static void ResizeSection(Elf* elf, Elf_Scn* section, size_t new_size, + typename ELF::Word new_sh_type, relocations_type_t relocations_type); + + static void AdjustDynamicSectionForHole(Elf_Scn* dynamic_section, + typename ELF::Off hole_start, + ssize_t hole_size, + relocations_type_t relocations_type); + + static void ConvertRelArrayToRelaVector(const typename ELF::Rel* rel_array, size_t rel_array_size, + std::vector<typename ELF::Rela>* rela_vector); + + static void ConvertRelaVectorToRelVector(const std::vector<typename ELF::Rela>& rela_vector, + std::vector<typename ELF::Rel>* rel_vector); + + // File descriptor opened on the shared object. int fd_; @@ -123,10 +145,9 @@ class ElfFile { // Sections that we manipulate, assigned by Load(). Elf_Scn* relocations_section_; Elf_Scn* dynamic_section_; - Elf_Scn* android_relocations_section_; // Relocation type found, assigned by Load(). - enum { NONE = 0, REL, RELA } relocations_type_; + relocations_type_t relocations_type_; }; } // namespace relocation_packer diff --git a/tools/relocation_packer/src/elf_file_unittest.cc b/tools/relocation_packer/src/elf_file_unittest.cc index 37abd0d..434f101 100644 --- a/tools/relocation_packer/src/elf_file_unittest.cc +++ b/tools/relocation_packer/src/elf_file_unittest.cc @@ -11,12 +11,7 @@ #include <vector> #include "debug.h" #include "elf_traits.h" -#include "testing/gtest/include/gtest/gtest.h" - -// Macro stringification. -// https://gcc.gnu.org/onlinedocs/cpp/Stringification.html -#define XSTR(S) STR(S) -#define STR(S) #S +#include "gtest/gtest.h" namespace { @@ -27,8 +22,6 @@ void GetDataFilePath(const char* name, std::string* path) { if (bindir) { data_dir = std::string(bindir); } else { - // Test data is in the gyp INTERMEDIATE_DIR subdirectory of the directory - // that contains the current binary. char path[PATH_MAX]; memset(path, 0, sizeof(path)); ASSERT_NE(-1, readlink("/proc/self/exe", path, sizeof(path) - 1)); @@ -37,8 +30,7 @@ void GetDataFilePath(const char* name, std::string* path) { size_t pos = data_dir.rfind('/'); ASSERT_NE(std::string::npos, pos); - data_dir.erase(pos + 1); - data_dir += std::string(XSTR(INTERMEDIATE_DIR)); + data_dir.erase(pos); } *path = data_dir + "/" + name; @@ -49,7 +41,7 @@ void OpenRelocsTestFile(const char* name, FILE** stream) { GetDataFilePath(name, &path); FILE* testfile = fopen(path.c_str(), "rb"); - ASSERT_FALSE(testfile == NULL); + ASSERT_FALSE(testfile == NULL) << "Error opening '" << path << "'"; FILE* temporary = tmpfile(); ASSERT_FALSE(temporary == NULL); @@ -70,15 +62,7 @@ void OpenRelocsTestFile(const char* name, FILE** stream) { *stream = temporary; } -void OpenRelocsTestFiles(FILE** relocs_so, FILE** packed_relocs_so) { - const char* arch = NULL; - if (ELF::kMachine == EM_ARM) { - arch = "arm32"; - } else if (ELF::kMachine == EM_AARCH64) { - arch = "arm64"; - } - ASSERT_FALSE(arch == NULL); - +void OpenRelocsTestFiles(const std::string& arch, FILE** relocs_so, FILE** packed_relocs_so) { const std::string base = std::string("elf_file_unittest_relocs_") + arch; const std::string relocs = base + ".so"; const std::string packed_relocs = base + "_packed.so"; @@ -115,20 +99,45 @@ void CheckFileContentsEqual(FILE* first, FILE* second) { EXPECT_TRUE(feof(first) && feof(second)); } -} // namespace +template <typename ELF> +static void ProcessUnpack(FILE* relocs_so, FILE* packed_relocs_so) { + relocation_packer::ElfFile<ELF> elf_file(fileno(packed_relocs_so)); -namespace relocation_packer { + // Ensure packing fails (already packed). + EXPECT_FALSE(elf_file.PackRelocations()); -TEST(ElfFile, PackRelocations) { - ASSERT_NE(EV_NONE, elf_version(EV_CURRENT)); + // Unpack golden relocations, and check files are now identical. + EXPECT_TRUE(elf_file.UnpackRelocations()); + CheckFileContentsEqual(packed_relocs_so, relocs_so); + + CloseRelocsTestFiles(relocs_so, packed_relocs_so); +} + +static void RunUnpackRelocationsTestFor(const std::string& arch) { + ASSERT_NE(static_cast<uint32_t>(EV_NONE), elf_version(EV_CURRENT)); FILE* relocs_so = NULL; FILE* packed_relocs_so = NULL; - OpenRelocsTestFiles(&relocs_so, &packed_relocs_so); - if (HasFatalFailure()) - return; + OpenRelocsTestFiles(arch, &relocs_so, &packed_relocs_so); + + if (relocs_so != NULL && packed_relocs_so != NULL) { + // lets detect elf class + ASSERT_EQ(0, fseek(relocs_so, EI_CLASS, SEEK_SET)) + << "Invalid file length: " << strerror(errno); + uint8_t elf_class = 0; + ASSERT_EQ(1U, fread(&elf_class, 1, 1, relocs_so)); + ASSERT_EQ(0, fseek(relocs_so, 0, SEEK_SET)); + if (elf_class == ELFCLASS32) { + ProcessUnpack<ELF32_traits>(relocs_so, packed_relocs_so); + } else { + ProcessUnpack<ELF64_traits>(relocs_so, packed_relocs_so); + } + } +} - ElfFile elf_file(fileno(relocs_so)); +template <typename ELF> +static void ProcessPack(FILE* relocs_so, FILE* packed_relocs_so) { + relocation_packer::ElfFile<ELF> elf_file(fileno(relocs_so)); // Ensure unpacking fails (not packed). EXPECT_FALSE(elf_file.UnpackRelocations()); @@ -140,25 +149,40 @@ TEST(ElfFile, PackRelocations) { CloseRelocsTestFiles(relocs_so, packed_relocs_so); } -TEST(ElfFile, UnpackRelocations) { - ASSERT_NE(EV_NONE, elf_version(EV_CURRENT)); +static void RunPackRelocationsTestFor(const std::string& arch) { + ASSERT_NE(static_cast<uint32_t>(EV_NONE), elf_version(EV_CURRENT)); FILE* relocs_so = NULL; FILE* packed_relocs_so = NULL; - OpenRelocsTestFiles(&relocs_so, &packed_relocs_so); - if (HasFatalFailure()) - return; + OpenRelocsTestFiles(arch, &relocs_so, &packed_relocs_so); + + if (relocs_so != NULL && packed_relocs_so != NULL) { + // lets detect elf class + ASSERT_EQ(0, fseek(packed_relocs_so, EI_CLASS, SEEK_SET)) + << "Invalid file length: " << strerror(errno); + uint8_t elf_class = 0; + ASSERT_EQ(1U, fread(&elf_class, 1, 1, packed_relocs_so)); + fseek(packed_relocs_so, 0, SEEK_SET); + if (elf_class == ELFCLASS32) { + ProcessPack<ELF32_traits>(relocs_so, packed_relocs_so); + } else { + ProcessPack<ELF64_traits>(relocs_so, packed_relocs_so); + } + } +} - ElfFile elf_file(fileno(packed_relocs_so)); +} // namespace - // Ensure packing fails (already packed). - EXPECT_FALSE(elf_file.PackRelocations()); +namespace relocation_packer { - // Unpack golden relocations, and check files are now identical. - EXPECT_TRUE(elf_file.UnpackRelocations()); - CheckFileContentsEqual(packed_relocs_so, relocs_so); +TEST(ElfFile, PackRelocations) { + RunPackRelocationsTestFor("arm32"); + RunPackRelocationsTestFor("arm64"); +} - CloseRelocsTestFiles(relocs_so, packed_relocs_so); +TEST(ElfFile, UnpackRelocations) { + RunUnpackRelocationsTestFor("arm32"); + RunUnpackRelocationsTestFor("arm64"); } } // namespace relocation_packer diff --git a/tools/relocation_packer/src/elf_traits.h b/tools/relocation_packer/src/elf_traits.h index f099bab..41b06c8 100644 --- a/tools/relocation_packer/src/elf_traits.h +++ b/tools/relocation_packer/src/elf_traits.h @@ -10,31 +10,10 @@ #include "elf.h" #include "libelf.h" -// The TARGET_ macro controls which Elf types we expect and handle. -// Either TARGET_ARM or TARGET_ARM64 must be defined, but not both. - -#if !defined(TARGET_ARM) && !defined(TARGET_ARM64) -# error "Unsupported target, define one of TARGET_ARM or TARGET_ARM64" -#elif defined(TARGET_ARM) && defined(TARGET_ARM64) -# error "Define one of TARGET_ARM or TARGET_ARM64, but not both" -#endif - -// TODO(simonb): Eliminate these once AARCH64 appears reliably in elf.h. -#ifndef EM_AARCH64 -#define EM_AARCH64 183 -#endif -#ifndef R_AARCH64_RELATIVE -#define R_AARCH64_RELATIVE 1027 -#endif -#ifndef R_AARCH64_NONE -#define R_AARCH64_NONE 0 -#endif - // ELF is a traits structure used to provide convenient aliases for -// 32/64 bit Elf types and functions, depending on the target specified. +// 32/64 bit Elf types and functions, depending on the target file. -#if defined(TARGET_ARM) -struct ELF { +struct ELF32_traits { typedef Elf32_Addr Addr; typedef Elf32_Dyn Dyn; typedef Elf32_Ehdr Ehdr; @@ -48,27 +27,17 @@ struct ELF { typedef Elf32_Sym Sym; typedef Elf32_Word Word; typedef Elf32_Xword Xword; + typedef Elf32_Half Half; static inline Ehdr* getehdr(Elf* elf) { return elf32_getehdr(elf); } static inline Phdr* getphdr(Elf* elf) { return elf32_getphdr(elf); } static inline Shdr* getshdr(Elf_Scn* scn) { return elf32_getshdr(scn); } - - enum { kMachine = EM_ARM }; - enum { kFileClass = ELFCLASS32 }; - enum { kRelativeRelocationCode = R_ARM_RELATIVE }; - enum { kNoRelocationCode = R_ARM_NONE }; - enum { kGnuStackSegmentAlignment = 0 }; - - static inline const char* Machine() { return "ARM"; } - -# define ELF_R_SYM(val) ELF32_R_SYM(val) -# define ELF_R_TYPE(val) ELF32_R_TYPE(val) -# define ELF_R_INFO(sym, type) ELF32_R_INFO(sym, type) -# define ELF_ST_TYPE(val) ELF32_ST_TYPE(val) + static inline Word elf_r_type(Word info) { return ELF32_R_TYPE(info); } + static inline int elf_st_type(uint8_t info) { return ELF32_ST_TYPE(info); } + static inline Word elf_r_sym(Word info) { return ELF32_R_SYM(info); } }; -#elif defined(TARGET_ARM64) -struct ELF { +struct ELF64_traits { typedef Elf64_Addr Addr; typedef Elf64_Dyn Dyn; typedef Elf64_Ehdr Ehdr; @@ -82,24 +51,14 @@ struct ELF { typedef Elf64_Sym Sym; typedef Elf64_Word Word; typedef Elf64_Xword Xword; + typedef Elf64_Half Half; static inline Ehdr* getehdr(Elf* elf) { return elf64_getehdr(elf); } static inline Phdr* getphdr(Elf* elf) { return elf64_getphdr(elf); } static inline Shdr* getshdr(Elf_Scn* scn) { return elf64_getshdr(scn); } - - enum { kMachine = EM_AARCH64 }; - enum { kFileClass = ELFCLASS64 }; - enum { kRelativeRelocationCode = R_AARCH64_RELATIVE }; - enum { kNoRelocationCode = R_AARCH64_NONE }; - enum { kGnuStackSegmentAlignment = 16 }; - - static inline const char* Machine() { return "ARM64"; } - -# define ELF_R_SYM(val) ELF64_R_SYM(val) -# define ELF_R_TYPE(val) ELF64_R_TYPE(val) -# define ELF_R_INFO(sym, type) ELF64_R_INFO(sym, type) -# define ELF_ST_TYPE(val) ELF64_ST_TYPE(val) + static inline Xword elf_r_type(Xword info) { return ELF64_R_TYPE(info); } + static inline int elf_st_type(uint8_t info) { return ELF64_ST_TYPE(info); } + static inline Word elf_r_sym(Xword info) { return ELF64_R_SYM(info); } }; -#endif #endif // TOOLS_RELOCATION_PACKER_SRC_ELF_TRAITS_H_ diff --git a/tools/relocation_packer/src/leb128.cc b/tools/relocation_packer/src/leb128.cc index b48739c..101c557 100644 --- a/tools/relocation_packer/src/leb128.cc +++ b/tools/relocation_packer/src/leb128.cc @@ -12,40 +12,50 @@ namespace relocation_packer { // Empty constructor and destructor to silence chromium-style. -Leb128Encoder::Leb128Encoder() { } -Leb128Encoder::~Leb128Encoder() { } +template <typename uint_t> +Leb128Encoder<uint_t>::Leb128Encoder() { } + +template <typename uint_t> +Leb128Encoder<uint_t>::~Leb128Encoder() { } // Add a single value to the encoding. Values are encoded with variable // length. The least significant 7 bits of each byte hold 7 bits of data, // and the most significant bit is set on each byte except the last. -void Leb128Encoder::Enqueue(ELF::Xword value) { +template <typename uint_t> +void Leb128Encoder<uint_t>::Enqueue(uint_t value) { + uint_t uvalue = static_cast<uint_t>(value); do { - const uint8_t byte = value & 127; - value >>= 7; - encoding_.push_back((value ? 128 : 0) | byte); - } while (value); + const uint8_t byte = uvalue & 127; + uvalue >>= 7; + encoding_.push_back((uvalue ? 128 : 0) | byte); + } while (uvalue); } // Add a vector of values to the encoding. -void Leb128Encoder::EnqueueAll(const std::vector<ELF::Xword>& values) { - for (size_t i = 0; i < values.size(); ++i) +template <typename uint_t> +void Leb128Encoder<uint_t>::EnqueueAll(const std::vector<uint_t>& values) { + for (size_t i = 0; i < values.size(); ++i) { Enqueue(values[i]); + } } // Create a new decoder for the given encoded stream. -Leb128Decoder::Leb128Decoder(const std::vector<uint8_t>& encoding) { +template <typename uint_t> +Leb128Decoder<uint_t>::Leb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with) { encoding_ = encoding; - cursor_ = 0; + cursor_ = start_with; } // Empty destructor to silence chromium-style. -Leb128Decoder::~Leb128Decoder() { } +template <typename uint_t> +Leb128Decoder<uint_t>::~Leb128Decoder() { } // Decode and retrieve a single value from the encoding. Read forwards until // a byte without its most significant bit is found, then read the 7 bit // fields of the bytes spanned to re-form the value. -ELF::Xword Leb128Decoder::Dequeue() { - ELF::Xword value = 0; +template <typename uint_t> +uint_t Leb128Decoder<uint_t>::Dequeue() { + uint_t value = 0; size_t shift = 0; uint8_t byte; @@ -53,7 +63,7 @@ ELF::Xword Leb128Decoder::Dequeue() { // Loop until we reach a byte with its high order bit clear. do { byte = encoding_[cursor_++]; - value |= static_cast<ELF::Xword>(byte & 127) << shift; + value |= static_cast<uint_t>(byte & 127) << shift; shift += 7; } while (byte & 128); @@ -61,9 +71,17 @@ ELF::Xword Leb128Decoder::Dequeue() { } // Decode and retrieve all remaining values from the encoding. -void Leb128Decoder::DequeueAll(std::vector<ELF::Xword>* values) { - while (cursor_ < encoding_.size()) +template <typename uint_t> +void Leb128Decoder<uint_t>::DequeueAll(std::vector<uint_t>* values) { + while (cursor_ < encoding_.size()) { values->push_back(Dequeue()); + } } +template class Leb128Encoder<uint32_t>; +template class Leb128Encoder<uint64_t>; + +template class Leb128Decoder<uint32_t>; +template class Leb128Decoder<uint64_t>; + } // namespace relocation_packer diff --git a/tools/relocation_packer/src/leb128.h b/tools/relocation_packer/src/leb128.h index 6cc2d7c..2c5b5d0 100644 --- a/tools/relocation_packer/src/leb128.h +++ b/tools/relocation_packer/src/leb128.h @@ -21,6 +21,7 @@ namespace relocation_packer { // Encode packed words as a LEB128 byte stream. +template <typename uint_t> class Leb128Encoder { public: // Explicit (but empty) constructor and destructor, for chromium-style. @@ -29,11 +30,11 @@ class Leb128Encoder { // Add a value to the encoding stream. // |value| is the unsigned int to add. - void Enqueue(ELF::Xword value); + void Enqueue(uint_t value); // Add a vector of values to the encoding stream. // |values| is the vector of unsigned ints to add. - void EnqueueAll(const std::vector<ELF::Xword>& values); + void EnqueueAll(const std::vector<uint_t>& values); // Retrieve the encoded representation of the values. // |encoding| is the returned vector of encoded data. @@ -45,21 +46,22 @@ class Leb128Encoder { }; // Decode a LEB128 byte stream to produce packed words. +template <typename uint_t> class Leb128Decoder { public: // Create a new decoder for the given encoded stream. // |encoding| is the vector of encoded data. - explicit Leb128Decoder(const std::vector<uint8_t>& encoding); + explicit Leb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with); // Explicit (but empty) destructor, for chromium-style. ~Leb128Decoder(); // Retrieve the next value from the encoded stream. - ELF::Xword Dequeue(); + uint_t Dequeue(); // Retrieve all remaining values from the encoded stream. // |values| is the vector of decoded data. - void DequeueAll(std::vector<ELF::Xword>* values); + void DequeueAll(std::vector<uint_t>* values); private: // Encoded LEB128 stream. diff --git a/tools/relocation_packer/src/leb128_unittest.cc b/tools/relocation_packer/src/leb128_unittest.cc index bd607b7..8a7028c 100644 --- a/tools/relocation_packer/src/leb128_unittest.cc +++ b/tools/relocation_packer/src/leb128_unittest.cc @@ -5,19 +5,19 @@ #include "leb128.h" #include <vector> -#include "testing/gtest/include/gtest/gtest.h" +#include "gtest/gtest.h" namespace relocation_packer { -TEST(Leb128, Encoder) { - std::vector<ELF::Xword> values; +TEST(Leb128, Encoder64) { + std::vector<uint64_t> values; values.push_back(624485); values.push_back(0); values.push_back(1); values.push_back(127); values.push_back(128); - Leb128Encoder encoder; + Leb128Encoder<uint64_t> encoder; encoder.EnqueueAll(values); encoder.Enqueue(4294967295); @@ -26,7 +26,7 @@ TEST(Leb128, Encoder) { std::vector<uint8_t> encoding; encoder.GetEncoding(&encoding); - EXPECT_EQ(23, encoding.size()); + EXPECT_EQ(23U, encoding.size()); // 624485 EXPECT_EQ(0xe5, encoding[0]); EXPECT_EQ(0x8e, encoding[1]); @@ -59,7 +59,7 @@ TEST(Leb128, Encoder) { EXPECT_EQ(0x01, encoding[22]); } -TEST(Leb128, Decoder) { +TEST(Leb128, Decoder64) { std::vector<uint8_t> encoding; // 624485 encoding.push_back(0xe5); @@ -92,20 +92,20 @@ TEST(Leb128, Decoder) { encoding.push_back(0xff); encoding.push_back(0x01); - Leb128Decoder decoder(encoding); + Leb128Decoder<uint64_t> decoder(encoding, 0); - EXPECT_EQ(624485, decoder.Dequeue()); + EXPECT_EQ(624485U, decoder.Dequeue()); - std::vector<ELF::Xword> dequeued; + std::vector<uint64_t> dequeued; decoder.DequeueAll(&dequeued); - EXPECT_EQ(6, dequeued.size()); - EXPECT_EQ(0, dequeued[0]); - EXPECT_EQ(1, dequeued[1]); - EXPECT_EQ(127, dequeued[2]); - EXPECT_EQ(128, dequeued[3]); - EXPECT_EQ(4294967295, dequeued[4]); - EXPECT_EQ(18446744073709551615ul, dequeued[5]); + EXPECT_EQ(6U, dequeued.size()); + EXPECT_EQ(0U, dequeued[0]); + EXPECT_EQ(1U, dequeued[1]); + EXPECT_EQ(127U, dequeued[2]); + EXPECT_EQ(128U, dequeued[3]); + EXPECT_EQ(4294967295U, dequeued[4]); + EXPECT_EQ(18446744073709551615UL, dequeued[5]); } } // namespace relocation_packer diff --git a/tools/relocation_packer/src/main.cc b/tools/relocation_packer/src/main.cc index 28f5b04..3f784e4 100644 --- a/tools/relocation_packer/src/main.cc +++ b/tools/relocation_packer/src/main.cc @@ -25,11 +25,12 @@ #include "debug.h" #include "elf_file.h" +#include "elf_traits.h" #include "libelf.h" -namespace { +#include "nativehelper/ScopedFd.h" -void PrintUsage(const char* argv0) { +static void PrintUsage(const char* argv0) { std::string temporary = argv0; const size_t last_slash = temporary.find_last_of("/"); if (last_slash != temporary.npos) { @@ -45,59 +46,11 @@ void PrintUsage(const char* argv0) { " -p, --pad do not shrink relocations, but pad (for debugging)\n\n", basename); - if (ELF::kMachine == EM_ARM) { - printf( - "Extracts relative relocations from the .rel.dyn section, packs them\n" - "into a more compact format, and stores the packed relocations in\n" - ".android.rel.dyn. Expands .android.rel.dyn to hold the packed\n" - "data, and shrinks .rel.dyn by the amount of unpacked data removed\n" - "from it.\n\n" - "Before being packed, a shared library needs to be prepared by adding\n" - "a null .android.rel.dyn section.\n\n" - "To pack relocations in a shared library:\n\n" - " echo -n 'NULL' >/tmp/small\n" - " arm-linux-androideabi-objcopy \\\n" - " --add-section .android.rel.dyn=/tmp/small \\\n" - " libchrome.<version>.so\n" - " rm /tmp/small\n" - " %s libchrome.<version>.so\n\n" - "To unpack and restore the shared library to its original state:\n\n" - " %s -u libchrome.<version>.so\n" - " arm-linux-androideabi-objcopy \\\n" - " --remove-section=.android.rel.dyn libchrome.<version>.so\n\n", - basename, basename); - } else if (ELF::kMachine == EM_AARCH64) { - printf( - "Extracts relative relocations from the .rela.dyn section, packs them\n" - "into a more compact format, and stores the packed relocations in\n" - ".android.rela.dyn. Expands .android.rela.dyn to hold the packed\n" - "data, and shrinks .rela.dyn by the amount of unpacked data removed\n" - "from it.\n\n" - "Before being packed, a shared library needs to be prepared by adding\n" - "a null .android.rela.dyn section.\n\n" - "To pack relocations in a shared library:\n\n" - " echo -n 'NULL' >/tmp/small\n" - " aarch64-linux-android-objcopy \\\n" - " --add-section .android.rela.dyn=/tmp/small \\\n" - " libchrome.<version>.so\n" - " rm /tmp/small\n" - " %s libchrome.<version>.so\n\n" - "To unpack and restore the shared library to its original state:\n\n" - " %s -u libchrome.<version>.so\n" - " aarch64-linux-android-objcopy \\\n" - " --remove-section=.android.rela.dyn libchrome.<version>.so\n\n", - basename, basename); - } else { - NOTREACHED(); - } - printf( "Debug sections are not handled, so packing should not be used on\n" "shared libraries compiled for debugging or otherwise unstripped.\n"); } -} // namespace - int main(int argc, char* argv[]) { bool is_unpacking = false; bool is_verbose = false; @@ -143,11 +96,9 @@ int main(int argc, char* argv[]) { LOG(WARNING) << "Elf Library is out of date!"; } - LOG(INFO) << "Configured for " << ELF::Machine(); - const char* file = argv[argc - 1]; - const int fd = open(file, O_RDWR); - if (fd == -1) { + ScopedFd fd(open(file, O_RDWR)); + if (fd.get() == -1) { LOG(ERROR) << file << ": " << strerror(errno); return 1; } @@ -155,16 +106,43 @@ int main(int argc, char* argv[]) { if (is_verbose) relocation_packer::Logger::SetVerbose(1); - relocation_packer::ElfFile elf_file(fd); - elf_file.SetPadding(is_padding); + // We need to detect elf class in order to create + // correct implementation + uint8_t e_ident[EI_NIDENT]; + if (TEMP_FAILURE_RETRY(read(fd.get(), e_ident, EI_NIDENT) != EI_NIDENT)) { + LOG(ERROR) << file << ": failed to read elf header:" << strerror(errno); + return 1; + } + + if (TEMP_FAILURE_RETRY(lseek(fd.get(), 0, SEEK_SET)) != 0) { + LOG(ERROR) << file << ": lseek to 0 failed:" << strerror(errno); + return 1; + } - bool status; - if (is_unpacking) - status = elf_file.UnpackRelocations(); - else - status = elf_file.PackRelocations(); + bool status = false; - close(fd); + if (e_ident[EI_CLASS] == ELFCLASS32) { + relocation_packer::ElfFile<ELF32_traits> elf_file(fd.get()); + elf_file.SetPadding(is_padding); + + if (is_unpacking) { + status = elf_file.UnpackRelocations(); + } else { + status = elf_file.PackRelocations(); + } + } else if (e_ident[EI_CLASS] == ELFCLASS64) { + relocation_packer::ElfFile<ELF64_traits> elf_file(fd.get()); + elf_file.SetPadding(is_padding); + + if (is_unpacking) { + status = elf_file.UnpackRelocations(); + } else { + status = elf_file.PackRelocations(); + } + } else { + LOG(ERROR) << file << ": unknown ELFCLASS: " << e_ident[EI_CLASS]; + return 1; + } if (!status) { LOG(ERROR) << file << ": failed to pack/unpack file"; diff --git a/tools/relocation_packer/src/packer.cc b/tools/relocation_packer/src/packer.cc index 29bec1e..8e30612 100644 --- a/tools/relocation_packer/src/packer.cc +++ b/tools/relocation_packer/src/packer.cc @@ -10,115 +10,79 @@ #include "delta_encoder.h" #include "elf_traits.h" #include "leb128.h" -#include "run_length_encoder.h" #include "sleb128.h" namespace relocation_packer { -// Pack relative relocations into a run-length encoded packed -// representation. -void RelocationPacker::PackRelativeRelocations( - const std::vector<ELF::Rel>& relocations, - std::vector<uint8_t>* packed) { +// Pack relocations into a group encoded packed representation. +template <typename ELF> +void RelocationPacker<ELF>::PackRelocations(const std::vector<typename ELF::Rela>& relocations, + std::vector<uint8_t>* packed) { // Run-length encode. - std::vector<ELF::Xword> packed_words; - RelocationRunLengthCodec codec; + std::vector<typename ELF::Addr> packed_words; + RelocationDeltaCodec<ELF> codec; codec.Encode(relocations, &packed_words); - // If insufficient data to run-length encode, do nothing. + // If insufficient data do nothing. if (packed_words.empty()) return; - // LEB128 encode, with "APR1" prefix. - Leb128Encoder encoder; - encoder.Enqueue('A'); - encoder.Enqueue('P'); - encoder.Enqueue('R'); - encoder.Enqueue('1'); - encoder.EnqueueAll(packed_words); - - encoder.GetEncoding(packed); - - // Pad packed to a whole number of words. This padding will decode as - // LEB128 zeroes. Run-length decoding ignores it because encoding - // embeds the pairs count in the stream itself. - while (packed->size() % sizeof(ELF::Word)) - packed->push_back(0); + Sleb128Encoder<typename ELF::Addr> sleb128_encoder; + Leb128Encoder<typename ELF::Addr> leb128_encoder; + + std::vector<uint8_t> leb128_packed; + std::vector<uint8_t> sleb128_packed; + + leb128_encoder.EnqueueAll(packed_words); + leb128_encoder.GetEncoding(&leb128_packed); + + sleb128_encoder.EnqueueAll(packed_words); + sleb128_encoder.GetEncoding(&sleb128_packed); + + // TODO (simonb): Estimate savings on current android system image and consider using + // one encoder for all packed relocations to reduce complexity. + if (leb128_packed.size() <= sleb128_packed.size()) { + packed->push_back('A'); + packed->push_back('P'); + packed->push_back('U'); + packed->push_back('2'); + packed->insert(packed->end(), leb128_packed.begin(), leb128_packed.end()); + } else { + packed->push_back('A'); + packed->push_back('P'); + packed->push_back('S'); + packed->push_back('2'); + packed->insert(packed->end(), sleb128_packed.begin(), sleb128_packed.end()); + } } // Unpack relative relocations from a run-length encoded packed // representation. -void RelocationPacker::UnpackRelativeRelocations( +template <typename ELF> +void RelocationPacker<ELF>::UnpackRelocations( const std::vector<uint8_t>& packed, - std::vector<ELF::Rel>* relocations) { - // LEB128 decode, after checking and stripping "APR1" prefix. - std::vector<ELF::Xword> packed_words; - Leb128Decoder decoder(packed); - CHECK(decoder.Dequeue() == 'A' && - decoder.Dequeue() == 'P' && - decoder.Dequeue() == 'R' && - decoder.Dequeue() == '1'); - decoder.DequeueAll(&packed_words); - - // Run-length decode. - RelocationRunLengthCodec codec; + std::vector<typename ELF::Rela>* relocations) { + + std::vector<typename ELF::Addr> packed_words; + CHECK(packed.size() > 4 && + packed[0] == 'A' && + packed[1] == 'P' && + (packed[2] == 'U' || packed[2] == 'S') && + packed[3] == '2'); + + if (packed[2] == 'U') { + Leb128Decoder<typename ELF::Addr> decoder(packed, 4); + decoder.DequeueAll(&packed_words); + } else { + Sleb128Decoder<typename ELF::Addr> decoder(packed, 4); + decoder.DequeueAll(&packed_words); + } + + RelocationDeltaCodec<ELF> codec; codec.Decode(packed_words, relocations); } -// Pack relative relocations with addends into a delta encoded packed -// representation. -void RelocationPacker::PackRelativeRelocations( - const std::vector<ELF::Rela>& relocations, - std::vector<uint8_t>* packed) { - // Delta encode. - std::vector<ELF::Sxword> packed_words; - RelocationDeltaCodec codec; - codec.Encode(relocations, &packed_words); - - // If insufficient data to delta encode, do nothing. - if (packed_words.empty()) - return; - - // Signed LEB128 encode, with "APA1" prefix. ASCII does not encode as - // itself under signed LEB128, so we have to treat it specially. - Sleb128Encoder encoder; - encoder.EnqueueAll(packed_words); - std::vector<uint8_t> encoded; - encoder.GetEncoding(&encoded); - - packed->push_back('A'); - packed->push_back('P'); - packed->push_back('A'); - packed->push_back('1'); - packed->insert(packed->end(), encoded.begin(), encoded.end()); - - // Pad packed to a whole number of words. This padding will decode as - // signed LEB128 zeroes. Delta decoding ignores it because encoding - // embeds the pairs count in the stream itself. - while (packed->size() % sizeof(ELF::Word)) - packed->push_back(0); -} - -// Unpack relative relocations with addends from a delta encoded -// packed representation. -void RelocationPacker::UnpackRelativeRelocations( - const std::vector<uint8_t>& packed, - std::vector<ELF::Rela>* relocations) { - // Check "APA1" prefix. - CHECK(packed.at(0) == 'A' && - packed.at(1) == 'P' && - packed.at(2) == 'A' && - packed.at(3) == '1'); - - // Signed LEB128 decode, after stripping "APA1" prefix. - std::vector<ELF::Sxword> packed_words; - std::vector<uint8_t> stripped(packed.begin() + 4, packed.end()); - Sleb128Decoder decoder(stripped); - decoder.DequeueAll(&packed_words); - - // Delta decode. - RelocationDeltaCodec codec; - codec.Decode(packed_words, relocations); -} +template class RelocationPacker<ELF32_traits>; +template class RelocationPacker<ELF64_traits>; } // namespace relocation_packer diff --git a/tools/relocation_packer/src/packer.h b/tools/relocation_packer/src/packer.h index db09ce8..8a57e62 100644 --- a/tools/relocation_packer/src/packer.h +++ b/tools/relocation_packer/src/packer.h @@ -48,29 +48,25 @@ #include <vector> #include "elf.h" -#include "elf_traits.h" namespace relocation_packer { -// A RelocationPacker packs vectors of relative relocations into more +// A RelocationPacker packs vectors of relocations into more // compact forms, and unpacks them to reproduce the pre-packed data. +template <typename ELF> class RelocationPacker { public: - // Pack relative relocations into a more compact form. - // |relocations| is a vector of relative relocation structs. + // Pack relocations into a more compact form. + // |relocations| is a vector of relocation structs. // |packed| is the vector of packed bytes into which relocations are packed. - static void PackRelativeRelocations(const std::vector<ELF::Rel>& relocations, - std::vector<uint8_t>* packed); - static void PackRelativeRelocations(const std::vector<ELF::Rela>& relocations, - std::vector<uint8_t>* packed); + static void PackRelocations(const std::vector<typename ELF::Rela>& relocations, + std::vector<uint8_t>* packed); - // Unpack relative relocations from their more compact form. + // Unpack relocations from their more compact form. // |packed| is the vector of packed relocations. - // |relocations| is a vector of unpacked relative relocation structs. - static void UnpackRelativeRelocations(const std::vector<uint8_t>& packed, - std::vector<ELF::Rel>* relocations); - static void UnpackRelativeRelocations(const std::vector<uint8_t>& packed, - std::vector<ELF::Rela>* relocations); + // |relocations| is a vector of unpacked relocation structs. + static void UnpackRelocations(const std::vector<uint8_t>& packed, + std::vector<typename ELF::Rela>* relocations); }; } // namespace relocation_packer diff --git a/tools/relocation_packer/src/packer_unittest.cc b/tools/relocation_packer/src/packer_unittest.cc index de5be79..8dddd8b 100644 --- a/tools/relocation_packer/src/packer_unittest.cc +++ b/tools/relocation_packer/src/packer_unittest.cc @@ -7,244 +7,286 @@ #include <vector> #include "elf.h" #include "elf_traits.h" -#include "testing/gtest/include/gtest/gtest.h" +#include "gtest/gtest.h" -namespace { -void AddRelocation(ELF::Addr addr, std::vector<ELF::Rel>* relocations) { - ELF::Rel relocation; +template <typename ELF> +static void AddRelocation(typename ELF::Addr addr, + typename ELF::Xword info, + typename ELF::Sxword addend, + std::vector<typename ELF::Rela>* relocations) { + typename ELF::Rela relocation; relocation.r_offset = addr; - relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); - relocations->push_back(relocation); -} - -bool CheckRelocation(ELF::Addr addr, const ELF::Rel& relocation) { - return relocation.r_offset == addr && - ELF_R_SYM(relocation.r_info) == 0 && - ELF_R_TYPE(relocation.r_info) == ELF::kRelativeRelocationCode; -} - -void AddRelocation(ELF::Addr addr, - ELF::Sxword addend, - std::vector<ELF::Rela>* relocations) { - ELF::Rela relocation; - relocation.r_offset = addr; - relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); + relocation.r_info = info; relocation.r_addend = addend; + relocations->push_back(relocation); } -bool CheckRelocation(ELF::Addr addr, - ELF::Sxword addend, - const ELF::Rela& relocation) { +template <typename ELF> +static bool CheckRelocation(typename ELF::Addr addr, + typename ELF::Xword info, + typename ELF::Sxword addend, + const typename ELF::Rela& relocation) { return relocation.r_offset == addr && - ELF_R_SYM(relocation.r_info) == 0 && - ELF_R_TYPE(relocation.r_info) == ELF::kRelativeRelocationCode && + relocation.r_info == info && relocation.r_addend == addend; } -} // namespace - namespace relocation_packer { -TEST(Packer, PackRel) { - std::vector<ELF::Rel> relocations; +template <typename ELF> +static void DoPackNoAddend() { + std::vector<typename ELF::Rela> relocations; std::vector<uint8_t> packed; - - RelocationPacker packer; - // Initial relocation. - AddRelocation(0xd1ce0000, &relocations); + AddRelocation<ELF>(0xd1ce0000, 0x11, 0, &relocations); // Two more relocations, 4 byte deltas. - AddRelocation(0xd1ce0004, &relocations); - AddRelocation(0xd1ce0008, &relocations); + AddRelocation<ELF>(0xd1ce0004, 0x11, 0, &relocations); + AddRelocation<ELF>(0xd1ce0008, 0x11, 0, &relocations); // Three more relocations, 8 byte deltas. - AddRelocation(0xd1ce0010, &relocations); - AddRelocation(0xd1ce0018, &relocations); - AddRelocation(0xd1ce0020, &relocations); + AddRelocation<ELF>(0xd1ce0010, 0x11, 0, &relocations); + AddRelocation<ELF>(0xd1ce0018, 0x11, 0, &relocations); + AddRelocation<ELF>(0xd1ce0020, 0x11, 0, &relocations); + + RelocationPacker<ELF> packer; packed.clear(); - packer.PackRelativeRelocations(relocations, &packed); + packer.PackRelocations(relocations, &packed); - EXPECT_EQ(16, packed.size()); + ASSERT_EQ(18U, packed.size()); // Identifier. - EXPECT_EQ('A', packed[0]); - EXPECT_EQ('P', packed[1]); - EXPECT_EQ('R', packed[2]); - EXPECT_EQ('1', packed[3]); - // Count-delta pairs count. - EXPECT_EQ(2, packed[4]); - // 0xd1ce0000 - EXPECT_EQ(128, packed[5]); - EXPECT_EQ(128, packed[6]); - EXPECT_EQ(184, packed[7]); - EXPECT_EQ(142, packed[8]); - EXPECT_EQ(13, packed[9]); - // Run of two relocations, 4 byte deltas. - EXPECT_EQ(2, packed[10]); - EXPECT_EQ(4, packed[11]); - // Run of three relocations, 8 byte deltas. - EXPECT_EQ(3, packed[12]); - EXPECT_EQ(8, packed[13]); - // Padding. - EXPECT_EQ(0, packed[14]); - EXPECT_EQ(0, packed[15]); -} + size_t ndx = 0; + EXPECT_EQ('A', packed[ndx++]); + EXPECT_EQ('P', packed[ndx++]); + EXPECT_EQ('U', packed[ndx++]); + EXPECT_EQ('2', packed[ndx++]); + // relocation count + EXPECT_EQ(6, packed[ndx++]); + // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 0d + EXPECT_EQ(0xfc, packed[ndx++]); + EXPECT_EQ(0xff, packed[ndx++]); + EXPECT_EQ(0xb7, packed[ndx++]); + EXPECT_EQ(0x8e, packed[ndx++]); + EXPECT_EQ(0x0d, packed[ndx++]); + // first group + EXPECT_EQ(3, packed[ndx++]); // size + EXPECT_EQ(3, packed[ndx++]); // flags + EXPECT_EQ(4, packed[ndx++]); // r_offset_delta + EXPECT_EQ(0x11, packed[ndx++]); // r_info + // second group + EXPECT_EQ(3, packed[ndx++]); // size + EXPECT_EQ(3, packed[ndx++]); // flags + EXPECT_EQ(8, packed[ndx++]); // r_offset_delta + EXPECT_EQ(0x11, packed[ndx++]); // r_info -TEST(Packer, UnpackRel) { - std::vector<uint8_t> packed; - std::vector<ELF::Rel> relocations; + EXPECT_EQ(ndx, packed.size()); +} - RelocationPacker packer; +TEST(Packer, PackNoAddend) { + DoPackNoAddend<ELF32_traits>(); + DoPackNoAddend<ELF64_traits>(); +} - // Identifier. +template <typename ELF> +static void DoUnpackNoAddend() { + std::vector<typename ELF::Rela> relocations; + std::vector<uint8_t> packed; packed.push_back('A'); packed.push_back('P'); - packed.push_back('R'); - packed.push_back('1'); - // Count-delta pairs count. - packed.push_back(2); - // 0xd1ce0000 - packed.push_back(128); - packed.push_back(128); - packed.push_back(184); - packed.push_back(142); - packed.push_back(13); - // Run of two relocations, 4 byte deltas. - packed.push_back(2); - packed.push_back(4); - // Run of three relocations, 8 byte deltas. - packed.push_back(3); - packed.push_back(8); - // Padding. - packed.push_back(0); - packed.push_back(0); + packed.push_back('U'); + packed.push_back('2'); + // relocation count + packed.push_back(6); + // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 0d + packed.push_back(0xfc); + packed.push_back(0xff); + packed.push_back(0xb7); + packed.push_back(0x8e); + packed.push_back(0x0d); + // first group + packed.push_back(3); // size + packed.push_back(3); // flags + packed.push_back(4); // r_offset_delta + packed.push_back(0x11); // r_info + // second group + packed.push_back(3); // size + packed.push_back(3); // flags + packed.push_back(8); // r_offset_delta + packed.push_back(0x11); // r_info - relocations.clear(); - packer.UnpackRelativeRelocations(packed, &relocations); + RelocationPacker<ELF> packer; + packer.UnpackRelocations(packed, &relocations); - EXPECT_EQ(6, relocations.size()); - // Initial relocation. - EXPECT_TRUE(CheckRelocation(0xd1ce0000, relocations[0])); - // Two relocations, 4 byte deltas. - EXPECT_TRUE(CheckRelocation(0xd1ce0004, relocations[1])); - EXPECT_TRUE(CheckRelocation(0xd1ce0008, relocations[2])); - // Three relocations, 8 byte deltas. - EXPECT_TRUE(CheckRelocation(0xd1ce0010, relocations[3])); - EXPECT_TRUE(CheckRelocation(0xd1ce0018, relocations[4])); - EXPECT_TRUE(CheckRelocation(0xd1ce0020, relocations[5])); + size_t ndx = 0; + EXPECT_EQ(6U, relocations.size()); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0000, 0x11, 0, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0004, 0x11, 0, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0008, 0x11, 0, relocations[ndx++])); + + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0010, 0x11, 0, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0018, 0x11, 0, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0020, 0x11, 0, relocations[ndx++])); + + EXPECT_EQ(ndx, relocations.size()); } -TEST(Packer, PackRela) { - std::vector<ELF::Rela> relocations; - std::vector<uint8_t> packed; +TEST(Packer, UnpackNoAddend) { + DoUnpackNoAddend<ELF32_traits>(); + DoUnpackNoAddend<ELF64_traits>(); +} - RelocationPacker packer; +template <typename ELF> +static void DoPackWithAddend() { + std::vector<typename ELF::Rela> relocations; // Initial relocation. - AddRelocation(0xd1ce0000, 10000, &relocations); + AddRelocation<ELF>(0xd1ce0000, 0x01, 10024, &relocations); // Two more relocations, 4 byte offset deltas, 12 byte addend deltas. - AddRelocation(0xd1ce0004, 10012, &relocations); - AddRelocation(0xd1ce0008, 10024, &relocations); + AddRelocation<ELF>(0xd1ce0004, 0x01, 10012, &relocations); + AddRelocation<ELF>(0xd1ce0008, 0x01, 10024, &relocations); // Three more relocations, 8 byte deltas, -24 byte addend deltas. - AddRelocation(0xd1ce0010, 10000, &relocations); - AddRelocation(0xd1ce0018, 9976, &relocations); - AddRelocation(0xd1ce0020, 9952, &relocations); + AddRelocation<ELF>(0xd1ce0010, 0x01, 10000, &relocations); + AddRelocation<ELF>(0xd1ce0018, 0x01, 9976, &relocations); + AddRelocation<ELF>(0xd1ce0020, 0x01, 9952, &relocations); + + std::vector<uint8_t> packed; + + RelocationPacker<ELF> packer; packed.clear(); - packer.PackRelativeRelocations(relocations, &packed); + packer.PackRelocations(relocations, &packed); - EXPECT_EQ(24, packed.size()); + EXPECT_EQ(26U, packed.size()); + size_t ndx = 0; // Identifier. - EXPECT_EQ('A', packed[0]); - EXPECT_EQ('P', packed[1]); - EXPECT_EQ('A', packed[2]); - EXPECT_EQ('1', packed[3]); - // Delta pairs count. - EXPECT_EQ(6, packed[4]); - // 0xd1ce0000 - EXPECT_EQ(128, packed[5]); - EXPECT_EQ(128, packed[6]); - EXPECT_EQ(184, packed[7]); - EXPECT_EQ(142, packed[8]); - EXPECT_EQ(13, packed[9]); - // 10000 - EXPECT_EQ(144, packed[10]); - EXPECT_EQ(206, packed[11]); - EXPECT_EQ(0, packed[12]); - // 4, 12 - EXPECT_EQ(4, packed[13]); - EXPECT_EQ(12, packed[14]); - // 4, 12 - EXPECT_EQ(4, packed[15]); - EXPECT_EQ(12, packed[16]); - // 8, -24 - EXPECT_EQ(8, packed[17]); - EXPECT_EQ(104, packed[18]); - // 8, -24 - EXPECT_EQ(8, packed[19]); - EXPECT_EQ(104, packed[20]); - // 8, -24 - EXPECT_EQ(8, packed[21]); - EXPECT_EQ(104, packed[22]); - // Padding. - EXPECT_EQ(0, packed[23]); -} + EXPECT_EQ('A', packed[ndx++]); + EXPECT_EQ('P', packed[ndx++]); + EXPECT_EQ('S', packed[ndx++]); + EXPECT_EQ('2', packed[ndx++]); + // Relocation count + EXPECT_EQ(6U, packed[ndx++]); + // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 0d/7d (depending on ELF::Addr) + EXPECT_EQ(0xfc, packed[ndx++]); + EXPECT_EQ(0xff, packed[ndx++]); + EXPECT_EQ(0xb7, packed[ndx++]); + EXPECT_EQ(0x8e, packed[ndx++]); + if (sizeof(typename ELF::Addr) == 8) { + // positive for uint64_t + EXPECT_EQ(0x0d, packed[ndx++]); + } else { + // negative for uint32_t + EXPECT_EQ(0x7d, packed[ndx++]); + } + // group 1 + EXPECT_EQ(0x03, packed[ndx++]); // size + EXPECT_EQ(0x0b, packed[ndx++]); // flags + EXPECT_EQ(0x04, packed[ndx++]); // r_offset_delta + EXPECT_EQ(0x01, packed[ndx++]); // r_info + // group 1 - addend 1: 10024 = 0xa8, 0xce, 0x80 + EXPECT_EQ(0xa8, packed[ndx++]); + EXPECT_EQ(0xce, packed[ndx++]); + EXPECT_EQ(0x00, packed[ndx++]); + // group 1 - addend 2: -12 = 0x74 + EXPECT_EQ(0x74, packed[ndx++]); + // group 1 - addend 3: +12 = 0x0c + EXPECT_EQ(0x0c, packed[ndx++]); -TEST(Packer, UnpackRela) { - std::vector<uint8_t> packed; - std::vector<ELF::Rela> relocations; + // group 2 + EXPECT_EQ(0x03, packed[ndx++]); // size + EXPECT_EQ(0x0b, packed[ndx++]); // flags + EXPECT_EQ(0x08, packed[ndx++]); // r_offset_delta + EXPECT_EQ(0x01, packed[ndx++]); // r_info + + // group 2 - addend 1: -24 = 0x68 + EXPECT_EQ(0x68, packed[ndx++]); + // group 2 - addend 2: -24 = 0x68 + EXPECT_EQ(0x68, packed[ndx++]); + // group 2 - addend 3: -24 = 0x68 + EXPECT_EQ(0x68, packed[ndx++]); + + EXPECT_EQ(ndx, packed.size()); +} - RelocationPacker packer; +TEST(Packer, PackWithAddend) { + DoPackWithAddend<ELF32_traits>(); + DoPackWithAddend<ELF64_traits>(); +} +template <typename ELF> +static void DoUnpackWithAddend() { + std::vector<uint8_t> packed; // Identifier. packed.push_back('A'); packed.push_back('P'); - packed.push_back('A'); - packed.push_back('1'); - // Delta pairs count. - packed.push_back(6); - // 0xd1ce0000 - packed.push_back(128); - packed.push_back(128); - packed.push_back(184); - packed.push_back(142); - packed.push_back(13); - // 10000 - packed.push_back(144); - packed.push_back(206); - packed.push_back(0); - // 4, 12 - packed.push_back(4); - packed.push_back(12); - // 4, 12 - packed.push_back(4); - packed.push_back(12); - // 8, -24 - packed.push_back(8); - packed.push_back(104); - // 8, -24 - packed.push_back(8); - packed.push_back(104); - // 8, -24 - packed.push_back(8); - packed.push_back(104); - // Padding. - packed.push_back(0); + packed.push_back('S'); + packed.push_back('2'); + // Relocation count + packed.push_back(6U); + // base relocation = 0xd1cdfffc -> fc, ff, b7, 8e, 0d + packed.push_back(0xfc); + packed.push_back(0xff); + packed.push_back(0xb7); + packed.push_back(0x8e); + if (sizeof(typename ELF::Addr) == 8) { + // positive for uint64_t + packed.push_back(0x0d); + } else { + // negative for uint32_t + packed.push_back(0x7d); + } + // group 1 + packed.push_back(0x03); // size + packed.push_back(0x0b); // flags + packed.push_back(0x04); // r_offset_delta + packed.push_back(0x01); // r_info + // group 1 - addend 1: 10024 = 0xa8, 0xce, 0x80 + packed.push_back(0xa8); + packed.push_back(0xce); + packed.push_back(0x00); + // group 1 - addend 2: -12 = 0x74 + packed.push_back(0x74); + // group 1 - addend 3: +12 = 0x0c + packed.push_back(0x0c); + + // group 2 + packed.push_back(0x03); // size + packed.push_back(0x0b); // flags + packed.push_back(0x08); // r_offset_delta + packed.push_back(0x01); // r_info + + // group 2 - addend 1: -24 = 0x68 + packed.push_back(0x68); + // group 2 - addend 2: -24 = 0x68 + packed.push_back(0x68); + // group 2 - addend 3: -24 = 0x68 + packed.push_back(0x68); + + std::vector<typename ELF::Rela> relocations; + + RelocationPacker<ELF> packer; relocations.clear(); - packer.UnpackRelativeRelocations(packed, &relocations); + packer.UnpackRelocations(packed, &relocations); - EXPECT_EQ(6, relocations.size()); + EXPECT_EQ(6U, relocations.size()); + size_t ndx = 0; // Initial relocation. - EXPECT_TRUE(CheckRelocation(0xd1ce0000, 10000, relocations[0])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0000, 0x01, 10024, relocations[ndx++])); // Two more relocations, 4 byte offset deltas, 12 byte addend deltas. - EXPECT_TRUE(CheckRelocation(0xd1ce0004, 10012, relocations[1])); - EXPECT_TRUE(CheckRelocation(0xd1ce0008, 10024, relocations[2])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0004, 0x01, 10012, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0008, 0x01, 10024, relocations[ndx++])); // Three more relocations, 8 byte offset deltas, -24 byte addend deltas. - EXPECT_TRUE(CheckRelocation(0xd1ce0010, 10000, relocations[3])); - EXPECT_TRUE(CheckRelocation(0xd1ce0018, 9976, relocations[4])); - EXPECT_TRUE(CheckRelocation(0xd1ce0020, 9952, relocations[5])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0010, 0x01, 10000, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0018, 0x01, 9976, relocations[ndx++])); + EXPECT_TRUE(CheckRelocation<ELF>(0xd1ce0020, 0x01, 9952, relocations[ndx++])); + + EXPECT_EQ(ndx, relocations.size()); +} + +TEST(Packer, UnpackWithAddend) { + DoUnpackWithAddend<ELF32_traits>(); + DoUnpackWithAddend<ELF64_traits>(); } } // namespace relocation_packer diff --git a/tools/relocation_packer/src/run_all_unittests.cc b/tools/relocation_packer/src/run_all_unittests.cc deleted file mode 100644 index 4122be1..0000000 --- a/tools/relocation_packer/src/run_all_unittests.cc +++ /dev/null @@ -1,10 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "testing/gtest/include/gtest/gtest.h" - -int main(int argc, char** argv) { - testing::InitGoogleTest(&argc, argv); - return RUN_ALL_TESTS(); -} diff --git a/tools/relocation_packer/src/run_length_encoder.cc b/tools/relocation_packer/src/run_length_encoder.cc deleted file mode 100644 index 2f2e1c3..0000000 --- a/tools/relocation_packer/src/run_length_encoder.cc +++ /dev/null @@ -1,144 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "run_length_encoder.h" - -#include <vector> - -#include "debug.h" -#include "elf_traits.h" - -namespace relocation_packer { - -namespace { - -// Generate a vector of deltas between the r_offset fields of adjacent -// relative relocations. -void GetDeltas(const std::vector<ELF::Rel>& relocations, - std::vector<ELF::Addr>* deltas) { - CHECK(relocations.size() >= 2); - - for (size_t i = 0; i < relocations.size() - 1; ++i) { - const ELF::Rel* first = &relocations[i]; - CHECK(ELF_R_TYPE(first->r_info) == ELF::kRelativeRelocationCode); - - const ELF::Rel* second = &relocations[i + 1]; - CHECK(ELF_R_TYPE(second->r_info) == ELF::kRelativeRelocationCode); - - // Requires that offsets are 'strictly increasing'. The packing - // algorithm fails if this does not hold. - CHECK(second->r_offset > first->r_offset); - deltas->push_back(second->r_offset - first->r_offset); - } -} - -// Condense a set of r_offset deltas into a run-length encoded packing. -// Represented as count-delta pairs, where count is the run length and -// delta the common difference between adjacent r_offsets. -void Condense(const std::vector<ELF::Addr>& deltas, - std::vector<ELF::Xword>* packed) { - CHECK(!deltas.empty()); - size_t count = 0; - ELF::Addr current = deltas[0]; - - // Identify spans of identically valued deltas. - for (size_t i = 0; i < deltas.size(); ++i) { - const ELF::Addr delta = deltas[i]; - if (delta == current) { - count++; - } else { - // We reached the end of a span of identically valued deltas. - packed->push_back(count); - packed->push_back(current); - current = delta; - count = 1; - } - } - - // Write the final span. - packed->push_back(count); - packed->push_back(current); -} - -// Uncondense a set of r_offset deltas from a run-length encoded packing. -// The initial address for uncondensing, the start index for the first -// condensed slot in packed, and the count of pairs are provided. -void Uncondense(ELF::Addr addr, - const std::vector<ELF::Xword>& packed, - size_t start_index, - size_t end_index, - std::vector<ELF::Rel>* relocations) { - // The first relocation is just one created from the initial address. - ELF::Rel initial; - initial.r_offset = addr; - initial.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); - relocations->push_back(initial); - - // Read each count and delta pair, beginning at the start index and - // finishing at the end index. - for (size_t i = start_index; i < end_index; i += 2) { - size_t count = packed[i]; - const ELF::Addr delta = packed[i + 1]; - CHECK(count > 0 && delta > 0); - - // Generate relocations for this count and delta pair. - while (count) { - addr += delta; - ELF::Rel relocation; - relocation.r_offset = addr; - relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); - relocations->push_back(relocation); - count--; - } - } -} - -} // namespace - -// Encode relative relocations into a run-length encoded (packed) -// representation. -void RelocationRunLengthCodec::Encode(const std::vector<ELF::Rel>& relocations, - std::vector<ELF::Xword>* packed) { - // If we have zero or one relocation only then there is no packing - // possible; a run-length encoding needs a run. - if (relocations.size() < 2) - return; - - std::vector<ELF::Addr> deltas; - GetDeltas(relocations, &deltas); - - // Reserve space for the element count. - packed->push_back(0); - - // Initialize the packed data with the first offset, then follow up with - // the condensed deltas vector. - packed->push_back(relocations[0].r_offset); - Condense(deltas, packed); - - // Fill in the packed pair count. - packed->at(0) = (packed->size() - 2) >> 1; -} - -// Decode relative relocations from a run-length encoded (packed) -// representation. -void RelocationRunLengthCodec::Decode(const std::vector<ELF::Xword>& packed, - std::vector<ELF::Rel>* relocations) { - // We need at least one packed pair after the packed pair count and start - // address to be able to unpack. - if (packed.size() < 4) - return; - - // Ensure that the packed data offers enough pairs. There may be zero - // padding on it that we ignore. - CHECK(packed[0] <= (packed.size() - 2) >> 1); - - // The first packed vector element is the pairs count and the second the - // initial address. Start uncondensing pairs at the third, and finish - // at the end of the pairs data. - const size_t pairs_count = packed[0]; - const ELF::Addr addr = packed[1]; - Uncondense(addr, packed, 2, 2 + (pairs_count << 1), relocations); -} - -} // namespace relocation_packer diff --git a/tools/relocation_packer/src/run_length_encoder_unittest.cc b/tools/relocation_packer/src/run_length_encoder_unittest.cc deleted file mode 100644 index 83370f2..0000000 --- a/tools/relocation_packer/src/run_length_encoder_unittest.cc +++ /dev/null @@ -1,124 +0,0 @@ -// Copyright 2014 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "run_length_encoder.h" - -#include <vector> -#include "elf.h" -#include "elf_traits.h" -#include "testing/gtest/include/gtest/gtest.h" - -namespace { - -void AddRelocation(ELF::Addr addr, std::vector<ELF::Rel>* relocations) { - ELF::Rel relocation; - relocation.r_offset = addr; - relocation.r_info = ELF_R_INFO(0, ELF::kRelativeRelocationCode); - relocations->push_back(relocation); -} - -bool CheckRelocation(ELF::Addr addr, const ELF::Rel& relocation) { - return relocation.r_offset == addr && - ELF_R_SYM(relocation.r_info) == 0 && - ELF_R_TYPE(relocation.r_info) == ELF::kRelativeRelocationCode; -} - -} // namespace - -namespace relocation_packer { - -TEST(RunLength, Encode) { - std::vector<ELF::Rel> relocations; - std::vector<ELF::Xword> packed; - - RelocationRunLengthCodec codec; - - packed.clear(); - codec.Encode(relocations, &packed); - - EXPECT_EQ(0, packed.size()); - - // Add one relocation (insufficient data to encode). - AddRelocation(0xf00d0000, &relocations); - - packed.clear(); - codec.Encode(relocations, &packed); - - EXPECT_EQ(0, packed.size()); - - // Add a second relocation, 4 byte delta (minimum data to encode). - AddRelocation(0xf00d0004, &relocations); - - packed.clear(); - codec.Encode(relocations, &packed); - - EXPECT_EQ(4, packed.size()); - // One count-delta pair present. - EXPECT_EQ(1, packed[0]); - // Initial relocation. - EXPECT_EQ(0xf00d0000, packed[1]); - // Run of a single relocation, 4 byte delta. - EXPECT_EQ(1, packed[2]); - EXPECT_EQ(4, packed[3]); - - // Add a third relocation, 4 byte delta. - AddRelocation(0xf00d0008, &relocations); - - // Add three more relocations, 8 byte deltas. - AddRelocation(0xf00d0010, &relocations); - AddRelocation(0xf00d0018, &relocations); - AddRelocation(0xf00d0020, &relocations); - - packed.clear(); - codec.Encode(relocations, &packed); - - EXPECT_EQ(6, packed.size()); - // Two count-delta pairs present. - EXPECT_EQ(2, packed[0]); - // Initial relocation. - EXPECT_EQ(0xf00d0000, packed[1]); - // Run of two relocations, 4 byte deltas. - EXPECT_EQ(2, packed[2]); - EXPECT_EQ(4, packed[3]); - // Run of three relocations, 8 byte deltas. - EXPECT_EQ(3, packed[4]); - EXPECT_EQ(8, packed[5]); -} - -TEST(RunLength, Decode) { - std::vector<ELF::Xword> packed; - std::vector<ELF::Rel> relocations; - - RelocationRunLengthCodec codec; - codec.Decode(packed, &relocations); - - EXPECT_EQ(0, relocations.size()); - - // Two count-delta pairs. - packed.push_back(2); - // Initial relocation. - packed.push_back(0xc0de0000); - // Run of two relocations, 4 byte deltas. - packed.push_back(2); - packed.push_back(4); - // Run of three relocations, 8 byte deltas. - packed.push_back(3); - packed.push_back(8); - - relocations.clear(); - codec.Decode(packed, &relocations); - - EXPECT_EQ(6, relocations.size()); - // Initial relocation. - EXPECT_TRUE(CheckRelocation(0xc0de0000, relocations[0])); - // Two relocations, 4 byte deltas. - EXPECT_TRUE(CheckRelocation(0xc0de0004, relocations[1])); - EXPECT_TRUE(CheckRelocation(0xc0de0008, relocations[2])); - // Three relocations, 8 byte deltas. - EXPECT_TRUE(CheckRelocation(0xc0de0010, relocations[3])); - EXPECT_TRUE(CheckRelocation(0xc0de0018, relocations[4])); - EXPECT_TRUE(CheckRelocation(0xc0de0020, relocations[5])); -} - -} // namespace relocation_packer diff --git a/tools/relocation_packer/src/sleb128.cc b/tools/relocation_packer/src/sleb128.cc index a10bd79..12c21e3 100644 --- a/tools/relocation_packer/src/sleb128.cc +++ b/tools/relocation_packer/src/sleb128.cc @@ -10,11 +10,33 @@ #include "elf_traits.h" +namespace { + +template <typename T> +class uint_traits {}; + +template <> +class uint_traits<uint64_t> { + public: + typedef int64_t int_t; +}; + +template <> +class uint_traits<uint32_t> { + public: + typedef int32_t int_t; +}; + +} + namespace relocation_packer { // Empty constructor and destructor to silence chromium-style. -Sleb128Encoder::Sleb128Encoder() { } -Sleb128Encoder::~Sleb128Encoder() { } +template <typename uint_t> +Sleb128Encoder<uint_t>::Sleb128Encoder() { } + +template <typename uint_t> +Sleb128Encoder<uint_t>::~Sleb128Encoder() { } // Add a single value to the encoding. Values are encoded with variable // length. The least significant 7 bits of each byte hold 7 bits of data, @@ -22,11 +44,13 @@ Sleb128Encoder::~Sleb128Encoder() { } // value is sign extended up to a multiple of 7 bits (ensuring that the // most significant bit is zero for a positive number and one for a // negative number). -void Sleb128Encoder::Enqueue(ELF::Sxword value) { +template <typename uint_t> +void Sleb128Encoder<uint_t>::Enqueue(uint_t value) { + typedef typename uint_traits<uint_t>::int_t int_t; static const size_t size = CHAR_BIT * sizeof(value); bool more = true; - const bool negative = value < 0; + const bool negative = static_cast<int_t>(value) < 0; while (more) { uint8_t byte = value & 127; @@ -34,11 +58,11 @@ void Sleb128Encoder::Enqueue(ELF::Sxword value) { // Sign extend if encoding a -ve value. if (negative) - value |= -(static_cast<ELF::Sxword>(1) << (size - 7)); + value |= -(static_cast<uint_t>(1) << (size - 7)); // The sign bit of byte is second high order bit. const bool sign_bit = byte & 64; - if ((value == 0 && !sign_bit) || (value == -1 && sign_bit)) + if ((value == 0 && !sign_bit) || (value == static_cast<uint_t>(-1) && sign_bit)) more = false; else byte |= 128; @@ -47,25 +71,30 @@ void Sleb128Encoder::Enqueue(ELF::Sxword value) { } // Add a vector of values to the encoding. -void Sleb128Encoder::EnqueueAll(const std::vector<ELF::Sxword>& values) { - for (size_t i = 0; i < values.size(); ++i) +template <typename uint_t> +void Sleb128Encoder<uint_t>::EnqueueAll(const std::vector<uint_t>& values) { + for (size_t i = 0; i < values.size(); ++i) { Enqueue(values[i]); + } } // Create a new decoder for the given encoded stream. -Sleb128Decoder::Sleb128Decoder(const std::vector<uint8_t>& encoding) { +template <typename uint_t> +Sleb128Decoder<uint_t>::Sleb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with) { encoding_ = encoding; - cursor_ = 0; + cursor_ = start_with; } // Empty destructor to silence chromium-style. -Sleb128Decoder::~Sleb128Decoder() { } +template <typename uint_t> +Sleb128Decoder<uint_t>::~Sleb128Decoder() { } // Decode and retrieve a single value from the encoding. Consume bytes // until one without its most significant bit is found, and re-form the // value from the 7 bit fields of the bytes consumed. -ELF::Sxword Sleb128Decoder::Dequeue() { - ELF::Sxword value = 0; +template <typename uint_t> +uint_t Sleb128Decoder<uint_t>::Dequeue() { + uint_t value = 0; static const size_t size = CHAR_BIT * sizeof(value); size_t shift = 0; @@ -74,22 +103,29 @@ ELF::Sxword Sleb128Decoder::Dequeue() { // Loop until we reach a byte with its high order bit clear. do { byte = encoding_[cursor_++]; - value |= (static_cast<ELF::Sxword>(byte & 127) << shift); + value |= (static_cast<uint_t>(byte & 127) << shift); shift += 7; } while (byte & 128); // The sign bit is second high order bit of the final byte decoded. // Sign extend if value is -ve and we did not shift all of it. if (shift < size && (byte & 64)) - value |= -(static_cast<ELF::Sxword>(1) << shift); + value |= -(static_cast<uint_t>(1) << shift); - return value; + return static_cast<uint_t>(value); } // Decode and retrieve all remaining values from the encoding. -void Sleb128Decoder::DequeueAll(std::vector<ELF::Sxword>* values) { - while (cursor_ < encoding_.size()) +template <typename uint_t> +void Sleb128Decoder<uint_t>::DequeueAll(std::vector<uint_t>* values) { + while (cursor_ < encoding_.size()) { values->push_back(Dequeue()); + } } +template class Sleb128Encoder<uint32_t>; +template class Sleb128Encoder<uint64_t>; +template class Sleb128Decoder<uint32_t>; +template class Sleb128Decoder<uint64_t>; + } // namespace relocation_packer diff --git a/tools/relocation_packer/src/sleb128.h b/tools/relocation_packer/src/sleb128.h index 3544543..fa0a246 100644 --- a/tools/relocation_packer/src/sleb128.h +++ b/tools/relocation_packer/src/sleb128.h @@ -22,6 +22,7 @@ namespace relocation_packer { // Encode packed words as a signed LEB128 byte stream. +template<typename int_t> class Sleb128Encoder { public: // Explicit (but empty) constructor and destructor, for chromium-style. @@ -30,11 +31,11 @@ class Sleb128Encoder { // Add a value to the encoding stream. // |value| is the signed int to add. - void Enqueue(ELF::Sxword value); + void Enqueue(int_t value); // Add a vector of values to the encoding stream. // |values| is the vector of signed ints to add. - void EnqueueAll(const std::vector<ELF::Sxword>& values); + void EnqueueAll(const std::vector<int_t>& values); // Retrieve the encoded representation of the values. // |encoding| is the returned vector of encoded data. @@ -46,21 +47,22 @@ class Sleb128Encoder { }; // Decode a LEB128 byte stream to produce packed words. +template <typename int_t> class Sleb128Decoder { public: // Create a new decoder for the given encoded stream. // |encoding| is the vector of encoded data. - explicit Sleb128Decoder(const std::vector<uint8_t>& encoding); + explicit Sleb128Decoder(const std::vector<uint8_t>& encoding, size_t start_with); // Explicit (but empty) destructor, for chromium-style. ~Sleb128Decoder(); // Retrieve the next value from the encoded stream. - ELF::Sxword Dequeue(); + int_t Dequeue(); // Retrieve all remaining values from the encoded stream. // |values| is the vector of decoded data. - void DequeueAll(std::vector<ELF::Sxword>* values); + void DequeueAll(std::vector<int_t>* values); private: // Encoded LEB128 stream. diff --git a/tools/relocation_packer/src/sleb128_unittest.cc b/tools/relocation_packer/src/sleb128_unittest.cc index 60a5d0d..49a553c 100644 --- a/tools/relocation_packer/src/sleb128_unittest.cc +++ b/tools/relocation_packer/src/sleb128_unittest.cc @@ -6,27 +6,27 @@ #include <vector> #include "elf_traits.h" -#include "testing/gtest/include/gtest/gtest.h" +#include "gtest/gtest.h" namespace relocation_packer { -TEST(Sleb128, Encoder) { - std::vector<ELF::Sxword> values; - values.push_back(624485); - values.push_back(0); - values.push_back(1); - values.push_back(63); - values.push_back(64); - values.push_back(-1); - values.push_back(-624485); +TEST(Sleb128, Encoder64) { + std::vector<uint64_t> values; + values.push_back(624485U); + values.push_back(0U); + values.push_back(1U); + values.push_back(63U); + values.push_back(64U); + values.push_back(static_cast<uint64_t>(-1)); + values.push_back(static_cast<uint64_t>(-624485)); - Sleb128Encoder encoder; + Sleb128Encoder<uint64_t> encoder; encoder.EnqueueAll(values); - encoder.Enqueue(2147483647); - encoder.Enqueue(-2147483648); - encoder.Enqueue(9223372036854775807ll); - encoder.Enqueue(-9223372036854775807ll - 1); + encoder.Enqueue(2147483647U); + encoder.Enqueue(static_cast<uint64_t>(-2147483648)); + encoder.Enqueue(9223372036854775807ULL); + encoder.Enqueue(static_cast<uint64_t>(-9223372036854775807LL - 1)); std::vector<uint8_t> encoding; encoder.GetEncoding(&encoding); @@ -143,24 +143,24 @@ TEST(Sleb128, Decoder) { encoding.push_back(0x80); encoding.push_back(0x7f); - Sleb128Decoder decoder(encoding); + Sleb128Decoder<uint64_t> decoder(encoding, 0); - EXPECT_EQ(624485, decoder.Dequeue()); + EXPECT_EQ(624485U, decoder.Dequeue()); - std::vector<ELF::Sxword> dequeued; + std::vector<uint64_t> dequeued; decoder.DequeueAll(&dequeued); - EXPECT_EQ(10u, dequeued.size()); - EXPECT_EQ(0, dequeued[0]); - EXPECT_EQ(1, dequeued[1]); - EXPECT_EQ(63, dequeued[2]); - EXPECT_EQ(64, dequeued[3]); - EXPECT_EQ(-1, dequeued[4]); - EXPECT_EQ(-624485, dequeued[5]); - EXPECT_EQ(2147483647, dequeued[6]); - EXPECT_EQ(-2147483648, dequeued[7]); - EXPECT_EQ(9223372036854775807ll, dequeued[8]); - EXPECT_EQ(-9223372036854775807ll - 1, dequeued[9]); + EXPECT_EQ(10U, dequeued.size()); + EXPECT_EQ(0U, dequeued[0]); + EXPECT_EQ(1U, dequeued[1]); + EXPECT_EQ(63U, dequeued[2]); + EXPECT_EQ(64U, dequeued[3]); + EXPECT_EQ(static_cast<uint64_t>(-1), dequeued[4]); + EXPECT_EQ(static_cast<uint64_t>(-624485), dequeued[5]); + EXPECT_EQ(2147483647U, dequeued[6]); + EXPECT_EQ(static_cast<uint64_t>(-2147483648), dequeued[7]); + EXPECT_EQ(9223372036854775807ULL, dequeued[8]); + EXPECT_EQ(static_cast<uint64_t>(-9223372036854775807LL - 1), dequeued[9]); } } // namespace relocation_packer diff --git a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so Binary files differindex 7cfdd60..d97ef82 100755 --- a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so +++ b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm32_packed.so diff --git a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so Binary files differindex 532beac..e44e459 100755 --- a/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so +++ b/tools/relocation_packer/test_data/elf_file_unittest_relocs_arm64_packed.so |