Order Files

Order file is a recent linker optimization technique. These order files are text files containing symbols representing functions. Linkers like lld use order files to layout functions in a specific order. These binaries or libraries with ordered symbols reduce page faults and improve a program's launch time due to the efficient loading of symbols during a program's cold-start.

Order file features can be added to your application by following three steps:

1. Generate profiles and mapping file
2. Create an order file from the profiles and mapping file
3. Use the order file during the Release build to layout the symbols

Generate Order File

Generating an order file require three steps:

1. Build an instrumented version of the app that writes the order file
2. Run the app to generate the profiles
3. Post-process the profiles and mapping file

Create an Instrumented Build

The profiles are generated by running an instrumented build of the application. An instrumented build requires adding -forder-file-instrumentation to both the compiler and linker flags with -mllvm -orderfile-write-mapping=<filename>-mapping.txt strictly being added to the compiler flags. The instrumentation flag enables order file instrumentation for profiling and loads the specific library needed for profiling. On the other hand, the mapping flag just outputs the mapping file that shows the MD5 hash for each function within the binary or library.

In addition, make sure to pass any optimization flag but -O0 because both the instrumentation flag and mapping flag require one. If no optimization flag is passed, the mapping file is not generated and the instrumented build might output wrong hashes to the profile file.

LOCAL_CFLAGS += \
    -forder-file-instrumentation \
    -mllvm -orderfile-write-mapping=mapping.txt \

LOCAL_LDFLAGS += -forder-file-instrumentation

target_compile_options(orderfiledemo PRIVATE
    -forder-file-instrumentation
    -mllvm -orderfile-write-mapping=mapping.txt
)
target_link_options(orderfiledemo PRIVATE -forder-file-instrumentation)

All these flags are not needed for a Release build so it should be controlled by a build variable. For simplicity, you can set this all up in the CMakeLists.txt like in our sample.

Create an Order File Library

In addition to the flags, the profile file needs to be set up and the instrumented binary needs to explicitly trigger a profile write during its execution.

• Call __llvm_profile_set_filename(PROFILE_DIR "/<filename>-%m.profraw") for setting up the profile path. Although the argument passed is <filename>-%m.profraw, the profile file is saved as <filename>-%m.profraw.order. Make sure PROFILE_DIR is writable by the app and you have access to the directory.
  • Due to many shared libraries being profiled, %m is useful because it expands to a unique module signature for the library, resulting in a separate profile per library. For more pattern specifiers, you can check out this link.
• Call __llvm_profile_initialize_file() to set up the profile file
• Call __llvm_orderfile_dump() to explicitly write to the profile file

The profiles are collected in memory and the dump function writes them to the file. You need to make sure the dump function is called at the end of startup so your profile file has all the symbols until the end of startup.

extern "C" {
extern int __llvm_profile_set_filename(const char*);
extern int __llvm_profile_initialize_file(void);
extern int __llvm_orderfile_dump(void);
}

#define PROFILE_DIR "<location-writable-from-app>"
void workload() {
  // ...
  // run workload
  // ...

  // set path and write profiles after workload execution
  __llvm_profile_set_filename(PROFILE_DIR "/default-%m.profraw");
  __llvm_profile_initialize_file();
  __llvm_orderfile_dump();
  return;
}

Run the Build for Profiles

Run the instrumented app on either a physical or virtual device to generate the profiles. You can extract the profile files using adb pull.

adb shell "run-as <package-name> sh -c 'cat /data/user/0/<package-name>/cache/default-%m.profraw.order' | cat > /data/local/tmp/default-%m.profraw.order"
adb pull /data/local/tmp/default-%m.profraw.order .

As mentioned before, make sure the folder containing the written profile file can be accessed by you. If it is a virtual device, you might want to avoid the emulators with Play Store due to not having access to many folders.

Postprocess the Profile and Mapping File

When you get the profiles, you need to find the mapping file and convert each profile into a hexadecimal format. Typically, you can find the mapping file in the build folder of the app. When you have both, you can use our script to take a profile file and the correct mapping file to generate an order file.

hexdump -C default-%m.profraw.order > default-%m.prof
python3 create_orderfile.py --profile-file default-%m.prof --mapping-file <filename>-mapping.txt

certutil -f -encodeHex default-%m.profraw.order default-%m.prof
python3 create_orderfile.py --profile-file default-%m.prof --mapping-file <filename>-mapping.txt

If you want to read more about the script, you can check out this README.

Use Order file to Build Application

After generating an order file, you should remove the earlier flags and the order file functions because those are just meant for generation steps. You just need to pass -Wl,--symbol-ordering-file=<filename>.orderfile to the compile and linker flags. Sometimes, symbols cannot be found or cannot move and give out warnings so you can pass -Wl,--no-warn-symbol-ordering to suppress these warnings.

LOCAL_CFLAGS += \
    -Wl,--symbol-ordering-file=<filename>.orderfile \
    -Wl,--no-warn-symbol-ordering \

LOCAL_LDFLAGS += \
    -Wl,--symbol-ordering-file=<filename>.orderfile \
    -Wl,--no-warn-symbol-ordering \

target_compile_options(orderfiledemo PRIVATE
    -Wl,--symbol-ordering-file=<filename>.orderfile
    -Wl,--no-warn-symbol-ordering
)
target_link_options(orderfiledemo PRIVATE
    -Wl,--symbol-ordering-file=<filename>.orderfile
    -Wl,--no-warn-symbol-ordering
)

For more information, check out the order file example.

Order file implementation details

There are many ways to generate order files and use them for building. The NDK uses LLVM's method so it is the most useful for your C or C++ shared libraries over the actual Java or Kotlin app. Clang takes every function name (symbol) and creates an MD5 hash of it and outputs this relation to a mapping file. A function's MD5 hash is written into the profile file (profraw format) when the function executes for the first time. Any subsequent executions of the function don't write its MD5 hash to the profile file because it wants to avoid duplicates. As a result, only the first execution of the function is recorded in the order. By going through the profile file and mapping file, you can take each MD5 hash and replace it with the corresponding function and get an order file.

Examples of both a profile file in hexadecimal format and a mapping file can be found as example.prof and example-mapping.txt respectively.