.. _module-pw_tokenizer: ------------ pw_tokenizer ------------ Logging is critical, but developers are often forced to choose between additional logging or saving crucial flash space. The ``pw_tokenizer`` module helps address this by replacing printf-style strings with binary tokens during compilation. This enables extensive logging with substantially less memory usage. .. note:: This usage of the term "tokenizer" is not related to parsing! The module is called tokenizer because it replaces a whole string literal with an integer token. It does not parse strings into separate tokens. The most common application of ``pw_tokenizer`` is binary logging, and it is designed to integrate easily into existing logging systems. However, the tokenizer is general purpose and can be used to tokenize any strings, with or without printf-style arguments. **Why tokenize strings?** * Dramatically reduce binary size by removing string literals from binaries. * Reduce I/O traffic, RAM, and flash usage by sending and storing compact tokens instead of strings. We've seen over 50% reduction in encoded log contents. * Reduce CPU usage by replacing snprintf calls with simple tokenization code. * Remove potentially sensitive log, assert, and other strings from binaries. Basic overview ============== There are two sides to ``pw_tokenizer``, which we call tokenization and detokenization. * **Tokenization** converts string literals in the source code to binary tokens at compile time. If the string has printf-style arguments, these are encoded to compact binary form at runtime. * **Detokenization** converts tokenized strings back to the original human-readable strings. Here's an overview of what happens when ``pw_tokenizer`` is used: 1. During compilation, the ``pw_tokenizer`` module hashes string literals to generate stable 32-bit tokens. 2. The tokenization macro removes these strings by declaring them in an ELF section that is excluded from the final binary. 3. After compilation, strings are extracted from the ELF to build a database of tokenized strings for use by the detokenizer. The ELF file may also be used directly. 4. During operation, the device encodes the string token and its arguments, if any. 5. The encoded tokenized strings are sent off-device or stored. 6. Off-device, the detokenizer tools use the token database to decode the strings to human-readable form. Example: tokenized logging -------------------------- This example demonstrates using ``pw_tokenizer`` for logging. In this example, tokenized logging saves ~90% in binary size (41 → 4 bytes) and 70% in encoded size (49 → 15 bytes). **Before**: plain text logging +------------------+-------------------------------------------+---------------+ | Location | Logging Content | Size in bytes | +==================+===========================================+===============+ | Source contains | ``LOG("Battery state: %s; battery | | | | voltage: %d mV", state, voltage);`` | | +------------------+-------------------------------------------+---------------+ | Binary contains | ``"Battery state: %s; battery | 41 | | | voltage: %d mV"`` | | +------------------+-------------------------------------------+---------------+ | | (log statement is called with | | | | ``"CHARGING"`` and ``3989`` as arguments) | | +------------------+-------------------------------------------+---------------+ | Device transmits | ``"Battery state: CHARGING; battery | 49 | | | voltage: 3989 mV"`` | | +------------------+-------------------------------------------+---------------+ | When viewed | ``"Battery state: CHARGING; battery | | | | voltage: 3989 mV"`` | | +------------------+-------------------------------------------+---------------+ **After**: tokenized logging +------------------+-----------------------------------------------------------+---------+ | Location | Logging Content | Size in | | | | bytes | +==================+===========================================================+=========+ | Source contains | ``LOG("Battery state: %s; battery | | | | voltage: %d mV", state, voltage);`` | | +------------------+-----------------------------------------------------------+---------+ | Binary contains | ``d9 28 47 8e`` (0x8e4728d9) | 4 | +------------------+-----------------------------------------------------------+---------+ | | (log statement is called with | | | | ``"CHARGING"`` and ``3989`` as arguments) | | +------------------+-----------------------------------------------------------+---------+ | Device transmits | =============== ============================== ========== | 15 | | | ``d9 28 47 8e`` ``08 43 48 41 52 47 49 4E 47`` ``aa 3e`` | | | | --------------- ------------------------------ ---------- | | | | Token ``"CHARGING"`` argument ``3989``, | | | | as | | | | varint | | | | =============== ============================== ========== | | +------------------+-----------------------------------------------------------+---------+ | When viewed | ``"Battery state: CHARGING; battery voltage: 3989 mV"`` | | +------------------+-----------------------------------------------------------+---------+ Getting started =============== Integrating ``pw_tokenizer`` requires a few steps beyond building the code. This section describes one way ``pw_tokenizer`` might be integrated with a project. These steps can be adapted as needed. 1. Add ``pw_tokenizer`` to your build. Build files for GN, CMake, and Bazel are provided. For Make or other build systems, add the files specified in the BUILD.gn's ``pw_tokenizer`` target to the build. 2. Use the tokenization macros in your code. See `Tokenization`_. 3. Add the contents of ``pw_tokenizer_linker_sections.ld`` to your project's linker script. In GN and CMake, this step is done automatically. 4. Compile your code to produce an ELF file. 5. Run ``database.py create`` on the ELF file to generate a CSV token database. See `Managing token databases`_. 6. Commit the token database to your repository. See notes in `Database management`_. 7. Integrate a ``database.py add`` command to your build to automatically update the committed token database. In GN, use the ``pw_tokenizer_database`` template to do this. See `Update a database`_. 8. Integrate ``detokenize.py`` or the C++ detokenization library with your tools to decode tokenized logs. See `Detokenization`_. Tokenization ============ Tokenization converts a string literal to a token. If it's a printf-style string, its arguments are encoded along with it. The results of tokenization can be sent off device or stored in place of a full string. Tokenization macros ------------------- Adding tokenization to a project is simple. To tokenize a string, include ``pw_tokenizer/tokenize.h`` and invoke one of the ``PW_TOKENIZE_`` macros. Tokenize a string literal ^^^^^^^^^^^^^^^^^^^^^^^^^ The ``PW_TOKENIZE_STRING`` macro converts a string literal to a ``uint32_t`` token. .. code-block:: cpp constexpr uint32_t token = PW_TOKENIZE_STRING("Any string literal!"); .. admonition:: When to use this macro Use ``PW_TOKENIZE_STRING`` to tokenize string literals that do not have %-style arguments. Tokenize to a handler function ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ``PW_TOKENIZE_TO_GLOBAL_HANDLER`` is the most efficient tokenization function, since it takes the fewest arguments. It encodes a tokenized string to a buffer on the stack. The size of the buffer is set with ``PW_TOKENIZER_CFG_ENCODING_BUFFER_SIZE_BYTES``. This macro is provided by the ``pw_tokenizer:global_handler`` facade. The backend for this facade must define the ``pw_tokenizer_HandleEncodedMessage`` C-linkage function. .. code-block:: cpp PW_TOKENIZE_TO_GLOBAL_HANDLER(format_string_literal, arguments...); void pw_tokenizer_HandleEncodedMessage(const uint8_t encoded_message[], size_t size_bytes); ``PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD`` is similar, but passes a ``uintptr_t`` argument to the global handler function. Values like a log level can be packed into the ``uintptr_t``. This macro is provided by the ``pw_tokenizer:global_handler_with_payload`` facade. The backend for this facade must define the ``pw_tokenizer_HandleEncodedMessageWithPayload`` C-linkage function. .. code-block:: cpp PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD(payload, format_string_literal, arguments...); void pw_tokenizer_HandleEncodedMessageWithPayload( uintptr_t payload, const uint8_t encoded_message[], size_t size_bytes); .. admonition:: When to use these macros Use anytime a global handler is sufficient, particularly for widely expanded macros, like a logging macro. ``PW_TOKENIZE_TO_GLOBAL_HANDLER`` or ``PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD`` are the most efficient macros for tokenizing printf-style strings. Tokenize to a callback ^^^^^^^^^^^^^^^^^^^^^^ ``PW_TOKENIZE_TO_CALLBACK`` tokenizes to a buffer on the stack and calls a ``void(const uint8_t* buffer, size_t buffer_size)`` callback that is provided at the call site. The size of the buffer is set with ``PW_TOKENIZER_CFG_ENCODING_BUFFER_SIZE_BYTES``. .. code-block:: cpp PW_TOKENIZE_TO_CALLBACK(HandlerFunction, "Format string: %x", arguments...); .. admonition:: When to use this macro Use ``PW_TOKENIZE_TO_CALLBACK`` if the global handler version is already in use for another purpose or more flexibility is needed. Tokenize to a buffer ^^^^^^^^^^^^^^^^^^^^ The most flexible tokenization macro is ``PW_TOKENIZE_TO_BUFFER``, which encodes to a caller-provided buffer. .. code-block:: cpp uint8_t buffer[BUFFER_SIZE]; size_t size_bytes = sizeof(buffer); PW_TOKENIZE_TO_BUFFER(buffer, &size_bytes, format_string_literal, arguments...); While ``PW_TOKENIZE_TO_BUFFER`` is maximally flexible, it takes more arguments than the other macros, so its per-use code size overhead is larger. .. admonition:: When to use this macro Use ``PW_TOKENIZE_TO_BUFFER`` to encode to a custom-sized buffer or if the other macros are insufficient. Avoid using ``PW_TOKENIZE_TO_BUFFER`` in widely expanded macros, such as a logging macro, because it will result in larger code size than its alternatives. .. _module-pw_tokenizer-custom-macro: Tokenize with a custom macro ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Projects may need more flexbility than the standard ``pw_tokenizer`` macros provide. To support this, projects may define custom tokenization macros. This requires the use of two low-level ``pw_tokenizer`` macros: .. c:macro:: PW_TOKENIZE_FORMAT_STRING(domain, mask, format, ...) Tokenizes a format string and sets the ``_pw_tokenizer_token`` variable to the token. Must be used in its own scope, since the same variable is used in every invocation. The tokenized string uses the specified :ref:`tokenization domain `. Use ``PW_TOKENIZER_DEFAULT_DOMAIN`` for the default. The token also may be masked; use ``UINT32_MAX`` to keep all bits. .. c:macro:: PW_TOKENIZER_ARG_TYPES(...) Converts a series of arguments to a compact format that replaces the format string literal. Use these two macros within the custom tokenization macro to call a function that does the encoding. The following example implements a custom tokenization macro for use with :ref:`module-pw_log_tokenized`. .. code-block:: cpp #include "pw_tokenizer/tokenize.h" #ifndef __cplusplus extern "C" { #endif void EncodeTokenizedMessage(pw_tokenizer_Payload metadata, pw_tokenizer_Token token, pw_tokenizer_ArgTypes types, ...); #ifndef __cplusplus } // extern "C" #endif #define PW_LOG_TOKENIZED_ENCODE_MESSAGE(metadata, format, ...) \ do { \ PW_TOKENIZE_FORMAT_STRING( \ PW_TOKENIZER_DEFAULT_DOMAIN, UINT32_MAX, format, __VA_ARGS__); \ EncodeTokenizedMessage(payload, \ _pw_tokenizer_token, \ PW_TOKENIZER_ARG_TYPES(__VA_ARGS__) \ PW_COMMA_ARGS(__VA_ARGS__)); \ } while (0) In this example, the ``EncodeTokenizedMessage`` function would handle encoding and processing the message. Encoding is done by the ``pw::tokenizer::EncodedMessage`` class or ``pw::tokenizer::EncodeArgs`` function from ``pw_tokenizer/encode_args.h``. The encoded message can then be transmitted or stored as needed. .. code-block:: cpp #include "pw_log_tokenized/log_tokenized.h" #include "pw_tokenizer/encode_args.h" void HandleTokenizedMessage(pw::log_tokenized::Metadata metadata, std::span message); extern "C" void EncodeTokenizedMessage(const pw_tokenizer_Payload metadata, const pw_tokenizer_Token token, const pw_tokenizer_ArgTypes types, ...) { va_list args; va_start(args, types); pw::tokenizer::EncodedMessage encoded_message(token, types, args); va_end(args); HandleTokenizedMessage(metadata, encoded_message); } .. admonition:: When to use a custom macro Use existing tokenization macros whenever possible. A custom macro may be needed to support use cases like the following: * Variations of ``PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD`` that take different arguments. * Supporting global handler macros that use different handler functions. Binary logging with pw_tokenizer -------------------------------- String tokenization is perfect for logging. Consider the following log macro, which gathers the file, line number, and log message. It calls the ``RecordLog`` function, which formats the log string, collects a timestamp, and transmits the result. .. code-block:: cpp #define LOG_INFO(format, ...) \ RecordLog(LogLevel_INFO, __FILE_NAME__, __LINE__, format, ##__VA_ARGS__) void RecordLog(LogLevel level, const char* file, int line, const char* format, ...) { if (level < current_log_level) { return; } int bytes = snprintf(buffer, sizeof(buffer), "%s:%d ", file, line); va_list args; va_start(args, format); bytes += vsnprintf(&buffer[bytes], sizeof(buffer) - bytes, format, args); va_end(args); TransmitLog(TimeSinceBootMillis(), buffer, size); } It is trivial to convert this to a binary log using the tokenizer. The ``RecordLog`` call is replaced with a ``PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD`` invocation. The ``pw_tokenizer_HandleEncodedMessageWithPayload`` implementation collects the timestamp and transmits the message with ``TransmitLog``. .. code-block:: cpp #define LOG_INFO(format, ...) \ PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD( \ (pw_tokenizer_Payload)LogLevel_INFO, \ __FILE_NAME__ ":%d " format, \ __LINE__, \ __VA_ARGS__); \ extern "C" void pw_tokenizer_HandleEncodedMessageWithPayload( uintptr_t level, const uint8_t encoded_message[], size_t size_bytes) { if (static_cast(level) >= current_log_level) { TransmitLog(TimeSinceBootMillis(), encoded_message, size_bytes); } } Note that the ``__FILE_NAME__`` string is directly included in the log format string. Since the string is tokenized, this has no effect on binary size. A ``%d`` for the line number is added to the format string, so that changing the line of the log message does not generate a new token. There is no overhead for additional tokens, but it may not be desirable to fill a token database with duplicate log lines. Tokenizing function names ------------------------- The string literal tokenization functions support tokenizing string literals or constexpr character arrays (``constexpr const char[]``). In GCC and Clang, the special ``__func__`` variable and ``__PRETTY_FUNCTION__`` extension are declared as ``static constexpr char[]`` in C++ instead of the standard ``static const char[]``. This means that ``__func__`` and ``__PRETTY_FUNCTION__`` can be tokenized while compiling C++ with GCC or Clang. .. code-block:: cpp // Tokenize the special function name variables. constexpr uint32_t function = PW_TOKENIZE_STRING(__func__); constexpr uint32_t pretty_function = PW_TOKENIZE_STRING(__PRETTY_FUNCTION__); // Tokenize the function name variables to a handler function. PW_TOKENIZE_TO_GLOBAL_HANDLER(__func__) PW_TOKENIZE_TO_GLOBAL_HANDLER(__PRETTY_FUNCTION__) Note that ``__func__`` and ``__PRETTY_FUNCTION__`` are not string literals. They are defined as static character arrays, so they cannot be implicitly concatentated with string literals. For example, ``printf(__func__ ": %d", 123);`` will not compile. Tokenization in Python ---------------------- The Python ``pw_tokenizer.encode`` module has limited support for encoding tokenized messages with the ``encode_token_and_args`` function. .. autofunction:: pw_tokenizer.encode.encode_token_and_args Encoding -------- The token is a 32-bit hash calculated during compilation. The string is encoded little-endian with the token followed by arguments, if any. For example, the 31-byte string ``You can go about your business.`` hashes to 0xdac9a244. This is encoded as 4 bytes: ``44 a2 c9 da``. Arguments are encoded as follows: * **Integers** (1--10 bytes) -- `ZagZag and varint encoded `_, similarly to Protocol Buffers. Smaller values take fewer bytes. * **Floating point numbers** (4 bytes) -- Single precision floating point. * **Strings** (1--128 bytes) -- Length byte followed by the string contents. The top bit of the length whether the string was truncated or not. The remaining 7 bits encode the string length, with a maximum of 127 bytes. .. TODO: insert diagram here! .. tip:: ``%s`` arguments can quickly fill a tokenization buffer. Keep ``%s`` arguments short or avoid encoding them as strings (e.g. encode an enum as an integer instead of a string). See also `Tokenized strings as %s arguments`_. Token generation: fixed length hashing at compile time ------------------------------------------------------ String tokens are generated using a modified version of the x65599 hash used by the SDBM project. All hashing is done at compile time. In C code, strings are hashed with a preprocessor macro. For compatibility with macros, the hash must be limited to a fixed maximum number of characters. This value is set by ``PW_TOKENIZER_CFG_C_HASH_LENGTH``. Increasing ``PW_TOKENIZER_CFG_C_HASH_LENGTH`` increases the compilation time for C due to the complexity of the hashing macros. C++ macros use a constexpr function instead of a macro. This function works with any length of string and has lower compilation time impact than the C macros. For consistency, C++ tokenization uses the same hash algorithm, but the calculated values will differ between C and C++ for strings longer than ``PW_TOKENIZER_CFG_C_HASH_LENGTH`` characters. .. _module-pw_tokenizer-domains: Tokenization domains -------------------- ``pw_tokenizer`` supports having multiple tokenization domains. Domains are a string label associated with each tokenized string. This allows projects to keep tokens from different sources separate. Potential use cases include the following: * Keep large sets of tokenized strings separate to avoid collisions. * Create a separate database for a small number of strings that use truncated tokens, for example only 10 or 16 bits instead of the full 32 bits. If no domain is specified, the domain is empty (``""``). For many projects, this default domain is sufficient, so no additional configuration is required. .. code-block:: cpp // Tokenizes this string to the default ("") domain. PW_TOKENIZE_STRING("Hello, world!"); // Tokenizes this string to the "my_custom_domain" domain. PW_TOKENIZE_STRING_DOMAIN("my_custom_domain", "Hello, world!"); The database and detokenization command line tools default to reading from the default domain. The domain may be specified for ELF files by appending ``#DOMAIN_NAME`` to the file path. Use ``#.*`` to read from all domains. For example, the following reads strings in ``some_domain`` from ``my_image.elf``. .. code-block:: sh ./database.py create --database my_db.csv path/to/my_image.elf#some_domain See `Managing token databases`_ for information about the ``database.py`` command line tool. Smaller tokens with masking --------------------------- ``pw_tokenizer`` uses 32-bit tokens. On 32-bit or 64-bit architectures, using fewer than 32 bits does not improve runtime or code size efficiency. However, when tokens are packed into data structures or stored in arrays, the size of the token directly affects memory usage. In those cases, every bit counts, and it may be desireable to use fewer bits for the token. ``pw_tokenizer`` allows users to provide a mask to apply to the token. This masked token is used in both the token database and the code. The masked token is not a masked version of the full 32-bit token, the masked token is the token. This makes it trivial to decode tokens that use fewer than 32 bits. Masking functionality is provided through the ``*_MASK`` versions of the macros. For example, the following generates 16-bit tokens and packs them into an existing value. .. code-block:: cpp constexpr uint32_t token = PW_TOKENIZE_STRING_MASK("domain", 0xFFFF, "Pigweed!"); uint32_t packed_word = (other_bits << 16) | token; Tokens are hashes, so tokens of any size have a collision risk. The fewer bits used for tokens, the more likely two strings are to hash to the same token. See `token collisions`_. Token collisions ---------------- Tokens are calculated with a hash function. It is possible for different strings to hash to the same token. When this happens, multiple strings will have the same token in the database, and it may not be possible to unambiguously decode a token. The detokenization tools attempt to resolve collisions automatically. Collisions are resolved based on two things: - whether the tokenized data matches the strings arguments' (if any), and - if / when the string was marked as having been removed from the database. Working with collisions ^^^^^^^^^^^^^^^^^^^^^^^ Collisions may occur occasionally. Run the command ``python -m pw_tokenizer.database report `` to see information about a token database, including any collisions. If there are collisions, take the following steps to resolve them. - Change one of the colliding strings slightly to give it a new token. - In C (not C++), artificial collisions may occur if strings longer than ``PW_TOKENIZER_CFG_C_HASH_LENGTH`` are hashed. If this is happening, consider setting ``PW_TOKENIZER_CFG_C_HASH_LENGTH`` to a larger value. See ``pw_tokenizer/public/pw_tokenizer/config.h``. - Run the ``mark_removed`` command with the latest version of the build artifacts to mark missing strings as removed. This deprioritizes them in collision resolution. .. code-block:: sh python -m pw_tokenizer.database mark_removed --database The ``purge`` command may be used to delete these tokens from the database. Probability of collisions ^^^^^^^^^^^^^^^^^^^^^^^^^ Hashes of any size have a collision risk. The probability of one at least one collision occurring for a given number of strings is unintuitively high (this is known as the `birthday problem `_). If fewer than 32 bits are used for tokens, the probability of collisions increases substantially. This table shows the approximate number of strings that can be hashed to have a 1% or 50% probability of at least one collision (assuming a uniform, random hash). +-------+---------------------------------------+ | Token | Collision probability by string count | | bits +--------------------+------------------+ | | 50% | 1% | +=======+====================+==================+ | 32 | 77000 | 9300 | +-------+--------------------+------------------+ | 31 | 54000 | 6600 | +-------+--------------------+------------------+ | 24 | 4800 | 580 | +-------+--------------------+------------------+ | 16 | 300 | 36 | +-------+--------------------+------------------+ | 8 | 19 | 3 | +-------+--------------------+------------------+ Keep this table in mind when masking tokens (see `Smaller tokens with masking`_). 16 bits might be acceptable when tokenizing a small set of strings, such as module names, but won't be suitable for large sets of strings, like log messages. Token databases =============== Token databases store a mapping of tokens to the strings they represent. An ELF file can be used as a token database, but it only contains the strings for its exact build. A token database file aggregates tokens from multiple ELF files, so that a single database can decode tokenized strings from any known ELF. Token databases contain the token, removal date (if any), and string for each tokenized string. Two token database formats are supported: CSV and binary. CSV database format ------------------- The CSV database format has three columns: the token in hexadecimal, the removal date (if any) in year-month-day format, and the string literal, surrounded by quotes. Quote characters within the string are represented as two quote characters. This example database contains six strings, three of which have removal dates. .. code-block:: 141c35d5, ,"The answer: ""%s""" 2e668cd6,2019-12-25,"Jello, world!" 7b940e2a, ,"Hello %s! %hd %e" 851beeb6, ,"%u %d" 881436a0,2020-01-01,"The answer is: %s" e13b0f94,2020-04-01,"%llu" Binary database format ---------------------- The binary database format is comprised of a 16-byte header followed by a series of 8-byte entries. Each entry stores the token and the removal date, which is 0xFFFFFFFF if there is none. The string literals are stored next in the same order as the entries. Strings are stored with null terminators. See `token_database.h `_ for full details. The binary form of the CSV database is shown below. It contains the same information, but in a more compact and easily processed form. It takes 141 B compared with the CSV database's 211 B. .. code-block:: text [header] 0x00: 454b4f54 0000534e TOKENS.. 0x08: 00000006 00000000 ........ [entries] 0x10: 141c35d5 ffffffff .5...... 0x18: 2e668cd6 07e30c19 ..f..... 0x20: 7b940e2a ffffffff *..{.... 0x28: 851beeb6 ffffffff ........ 0x30: 881436a0 07e40101 .6...... 0x38: e13b0f94 07e40401 ..;..... [string table] 0x40: 54 68 65 20 61 6e 73 77 65 72 3a 20 22 25 73 22 The answer: "%s" 0x50: 00 4a 65 6c 6c 6f 2c 20 77 6f 72 6c 64 21 00 48 .Jello, world!.H 0x60: 65 6c 6c 6f 20 25 73 21 20 25 68 64 20 25 65 00 ello %s! %hd %e. 0x70: 25 75 20 25 64 00 54 68 65 20 61 6e 73 77 65 72 %u %d.The answer 0x80: 20 69 73 3a 20 25 73 00 25 6c 6c 75 00 is: %s.%llu. Managing token databases ------------------------ Token databases are managed with the ``database.py`` script. This script can be used to extract tokens from compilation artifacts and manage database files. Invoke ``database.py`` with ``-h`` for full usage information. An example ELF file with tokenized logs is provided at ``pw_tokenizer/py/example_binary_with_tokenized_strings.elf``. You can use that file to experiment with the ``database.py`` commands. Create a database ^^^^^^^^^^^^^^^^^ The ``create`` command makes a new token database from ELF files (.elf, .o, .so, etc.), archives (.a), or existing token databases (CSV or binary). .. code-block:: sh ./database.py create --database DATABASE_NAME ELF_OR_DATABASE_FILE... Two database formats are supported: CSV and binary. Provide ``--type binary`` to ``create`` to generate a binary database instead of the default CSV. CSV databases are great for checking into a source control or for human review. Binary databases are more compact and simpler to parse. The C++ detokenizer library only supports binary databases currently. Update a database ^^^^^^^^^^^^^^^^^ As new tokenized strings are added, update the database with the ``add`` command. .. code-block:: sh ./database.py add --database DATABASE_NAME ELF_OR_DATABASE_FILE... A CSV token database can be checked into a source repository and updated as code changes are made. The build system can invoke ``database.py`` to update the database after each build. GN integration ^^^^^^^^^^^^^^ Token databases may be updated or created as part of a GN build. The ``pw_tokenizer_database`` template provided by ``$dir_pw_tokenizer/database.gni`` automatically updates an in-source tokenized strings database or creates a new database with artifacts from one or more GN targets or other database files. To create a new database, set the ``create`` variable to the desired database type (``"csv"`` or ``"binary"``). The database will be created in the output directory. To update an existing database, provide the path to the database with the ``database`` variable. .. code-block:: import("//build_overrides/pigweed.gni") import("$dir_pw_tokenizer/database.gni") pw_tokenizer_database("my_database") { database = "database_in_the_source_tree.csv" targets = [ "//firmware/image:foo(//targets/my_board:some_toolchain)" ] input_databases = [ "other_database.csv" ] } Instead of specifying GN targets, paths or globs to output files may be provided with the ``paths`` option. .. code-block:: pw_tokenizer_database("my_database") { database = "database_in_the_source_tree.csv" deps = [ ":apps" ] optional_paths = [ "$root_build_dir/**/*.elf" ] } .. note:: The ``paths`` and ``optional_targets`` arguments do not add anything to ``deps``, so there is no guarantee that the referenced artifacts will exist when the database is updated. Provide ``targets`` or ``deps`` or build other GN targets first if this is a concern. Detokenization ============== Detokenization is the process of expanding a token to the string it represents and decoding its arguments. This module provides Python and C++ detokenization libraries. **Example: decoding tokenized logs** A project might tokenize its log messages with the `Base64 format`_. Consider the following log file, which has four tokenized logs and one plain text log: .. code-block:: text 20200229 14:38:58 INF $HL2VHA== 20200229 14:39:00 DBG $5IhTKg== 20200229 14:39:20 DBG Crunching numbers to calculate probability of success 20200229 14:39:21 INF $EgFj8lVVAUI= 20200229 14:39:23 ERR $DFRDNwlOT1RfUkVBRFk= The project's log strings are stored in a database like the following: .. code-block:: 1c95bd1c, ,"Initiating retrieval process for recovery object" 2a5388e4, ,"Determining optimal approach and coordinating vectors" 3743540c, ,"Recovery object retrieval failed with status %s" f2630112, ,"Calculated acceptable probability of success (%.2f%%)" Using the detokenizing tools with the database, the logs can be decoded: .. code-block:: text 20200229 14:38:58 INF Initiating retrieval process for recovery object 20200229 14:39:00 DBG Determining optimal algorithm and coordinating approach vectors 20200229 14:39:20 DBG Crunching numbers to calculate probability of success 20200229 14:39:21 INF Calculated acceptable probability of success (32.33%) 20200229 14:39:23 ERR Recovery object retrieval failed with status NOT_READY .. note:: This example uses the `Base64 format`_, which occupies about 4/3 (133%) as much space as the default binary format when encoded. For projects that wish to interleave tokenized with plain text, using Base64 is a worthwhile tradeoff. Python ------ To detokenize in Python, import ``Detokenizer`` from the ``pw_tokenizer`` package, and instantiate it with paths to token databases or ELF files. .. code-block:: python import pw_tokenizer detokenizer = pw_tokenizer.Detokenizer('path/to/database.csv', 'other/path.elf') def process_log_message(log_message): result = detokenizer.detokenize(log_message.payload) self._log(str(result)) The ``pw_tokenizer`` package also provides the ``AutoUpdatingDetokenizer`` class, which can be used in place of the standard ``Detokenizer``. This class monitors database files for changes and automatically reloads them when they change. This is helpful for long-running tools that use detokenization. C++ --- The C++ detokenization libraries can be used in C++ or any language that can call into C++ with a C-linkage wrapper, such as Java or Rust. A reference Java Native Interface (JNI) implementation is provided. The C++ detokenization library uses binary-format token databases (created with ``database.py create --type binary``). Read a binary format database from a file or include it in the source code. Pass the database array to ``TokenDatabase::Create``, and construct a detokenizer. .. code-block:: cpp Detokenizer detokenizer(TokenDatabase::Create(token_database_array)); std::string ProcessLog(span log_data) { return detokenizer.Detokenize(log_data).BestString(); } The ``TokenDatabase`` class verifies that its data is valid before using it. If it is invalid, the ``TokenDatabase::Create`` returns an empty database for which ``ok()`` returns false. If the token database is included in the source code, this check can be done at compile time. .. code-block:: cpp // This line fails to compile with a static_assert if the database is invalid. constexpr TokenDatabase kDefaultDatabase = TokenDatabase::Create(); Detokenizer OpenDatabase(std::string_view path) { std::vector data = ReadWholeFile(path); TokenDatabase database = TokenDatabase::Create(data); // This checks if the file contained a valid database. It is safe to use a // TokenDatabase that failed to load (it will be empty), but it may be // desirable to provide a default database or otherwise handle the error. if (database.ok()) { return Detokenizer(database); } return Detokenizer(kDefaultDatabase); } Base64 format ============= The tokenizer encodes messages to a compact binary representation. Applications may desire a textual representation of tokenized strings. This makes it easy to use tokenized messages alongside plain text messages, but comes at a small efficiency cost: encoded Base64 messages occupy about 4/3 (133%) as much memory as binary messages. The Base64 format is comprised of a ``$`` character followed by the Base64-encoded contents of the tokenized message. For example, consider tokenizing the string ``This is an example: %d!`` with the argument -1. The string's token is 0x4b016e66. .. code-block:: text Source code: PW_TOKENIZE_TO_GLOBAL_HANDLER("This is an example: %d!", -1); Plain text: This is an example: -1! [23 bytes] Binary: 66 6e 01 4b 01 [ 5 bytes] Base64: $Zm4BSwE= [ 9 bytes] Encoding -------- To encode with the Base64 format, add a call to ``pw::tokenizer::PrefixedBase64Encode`` or ``pw_tokenizer_PrefixedBase64Encode`` in the tokenizer handler function. For example, .. code-block:: cpp void pw_tokenizer_HandleEncodedMessage(const uint8_t encoded_message[], size_t size_bytes) { char base64_buffer[64]; size_t base64_size = pw::tokenizer::PrefixedBase64Encode( pw::span(encoded_message, size_bytes), base64_buffer); TransmitLogMessage(base64_buffer, base64_size); } Decoding -------- Base64 decoding and detokenizing is supported in the Python detokenizer through the ``detokenize_base64`` and related functions. .. tip:: The Python detokenization tools support recursive detokenization for prefixed Base64 text. Tokenized strings found in detokenized text are detokenized, so prefixed Base64 messages can be passed as ``%s`` arguments. For example, the tokenized string for "Wow!" is ``$RhYjmQ==``. This could be passed as an argument to the printf-style string ``Nested message: %s``, which encodes to ``$pEVTYQkkUmhZam1RPT0=``. The detokenizer would decode the message as follows: :: "$pEVTYQkkUmhZam1RPT0=" → "Nested message: $RhYjmQ==" → "Nested message: Wow!" Base64 decoding is supported in C++ or C with the ``pw::tokenizer::PrefixedBase64Decode`` or ``pw_tokenizer_PrefixedBase64Decode`` functions. .. code-block:: cpp void pw_tokenizer_HandleEncodedMessage(const uint8_t encoded_message[], size_t size_bytes) { char base64_buffer[64]; size_t base64_size = pw::tokenizer::PrefixedBase64Encode( pw::span(encoded_message, size_bytes), base64_buffer); TransmitLogMessage(base64_buffer, base64_size); } Command line utilities ^^^^^^^^^^^^^^^^^^^^^^ ``pw_tokenizer`` provides two standalone command line utilities for detokenizing Base64-encoded tokenized strings. * ``detokenize.py`` -- Detokenizes Base64-encoded strings in files or from stdin. * ``detokenize_serial.py`` -- Detokenizes Base64-encoded strings from a connected serial device. If the ``pw_tokenizer`` Python package is installed, these tools may be executed as runnable modules. For example: .. code-block:: # Detokenize Base64-encoded strings in a file python -m pw_tokenizer.detokenize -i input_file.txt # Detokenize Base64-encoded strings in output from a serial device python -m pw_tokenizer.detokenize_serial --device /dev/ttyACM0 See the ``--help`` options for these tools for full usage information. Deployment war story ==================== The tokenizer module was developed to bring tokenized logging to an in-development product. The product already had an established text-based logging system. Deploying tokenization was straightforward and had substantial benefits. Results ------- * Log contents shrunk by over 50%, even with Base64 encoding. * Significant size savings for encoded logs, even using the less-efficient Base64 encoding required for compatibility with the existing log system. * Freed valuable communication bandwidth. * Allowed storing many more logs in crash dumps. * Substantial flash savings. * Reduced the size firmware images by up to 18%. * Simpler logging code. * Removed CPU-heavy ``snprintf`` calls. * Removed complex code for forwarding log arguments to a low-priority task. This section describes the tokenizer deployment process and highlights key insights. Firmware deployment ------------------- * In the project's logging macro, calls to the underlying logging function were replaced with a ``PW_TOKENIZE_TO_GLOBAL_HANDLER_WITH_PAYLOAD`` invocation. * The log level was passed as the payload argument to facilitate runtime log level control. * For this project, it was necessary to encode the log messages as text. In ``pw_tokenizer_HandleEncodedMessageWithPayload``, the log messages were encoded in the $-prefixed `Base64 format`_, then dispatched as normal log messages. * Asserts were tokenized using ``PW_TOKENIZE_TO_CALLBACK``. .. attention:: Do not encode line numbers in tokenized strings. This results in a huge number of lines being added to the database, since every time code moves, new strings are tokenized. If line numbers are desired in a tokenized string, add a ``"%d"`` to the string and pass ``__LINE__`` as an argument. Database management ------------------- * The token database was stored as a CSV file in the project's Git repo. * The token database was automatically updated as part of the build, and developers were expected to check in the database changes alongside their code changes. * A presubmit check verified that all strings added by a change were added to the token database. * The token database included logs and asserts for all firmware images in the project. * No strings were purged from the token database. .. tip:: Merge conflicts may be a frequent occurrence with an in-source database. If the database is in-source, make sure there is a simple script to resolve any merge conflicts. The script could either keep both sets of lines or discard local changes and regenerate the database. Decoding tooling deployment --------------------------- * The Python detokenizer in ``pw_tokenizer`` was deployed to two places: * Product-specific Python command line tools, using ``pw_tokenizer.Detokenizer``. * Standalone script for decoding prefixed Base64 tokens in files or live output (e.g. from ``adb``), using ``detokenize.py``'s command line interface. * The C++ detokenizer library was deployed to two Android apps with a Java Native Interface (JNI) layer. * The binary token database was included as a raw resource in the APK. * In one app, the built-in token database could be overridden by copying a file to the phone. .. tip:: Make the tokenized logging tools simple to use for your project. * Provide simple wrapper shell scripts that fill in arguments for the project. For example, point ``detokenize.py`` to the project's token databases. * Use ``pw_tokenizer.AutoReloadingDetokenizer`` to decode in continuously-running tools, so that users don't have to restart the tool when the token database updates. * Integrate detokenization everywhere it is needed. Integrating the tools takes just a few lines of code, and token databases can be embedded in APKs or binaries. Limitations and future work =========================== GCC bug: tokenization in template functions ------------------------------------------- GCC incorrectly ignores the section attribute for template `functions `_ and `variables `_. Due to this bug, tokenized strings in template functions may be emitted into ``.rodata`` instead of the special tokenized string section. This causes two problems: 1. Tokenized strings will not be discovered by the token database tools. 2. Tokenized strings may not be removed from the final binary. clang does **not** have this issue! Use clang to avoid this. It is possible to work around this bug in GCC. One approach would be to tag format strings so that the database tools can find them in ``.rodata``. Then, to remove the strings, compile two binaries: one metadata binary with all tokenized strings and a second, final binary that removes the strings. The strings could be removed by providing the appropriate linker flags or by removing the ``used`` attribute from the tokenized string character array declaration. 64-bit tokenization ------------------- The Python and C++ detokenizing libraries currently assume that strings were tokenized on a system with 32-bit ``long``, ``size_t``, ``intptr_t``, and ``ptrdiff_t``. Decoding may not work correctly for these types if a 64-bit device performed the tokenization. Supporting detokenization of strings tokenized on 64-bit targets would be simple. This could be done by adding an option to switch the 32-bit types to 64-bit. The tokenizer stores the sizes of these types in the ``.pw_tokenizer.info`` ELF section, so the sizes of these types can be verified by checking the ELF file, if necessary. Tokenization in headers ----------------------- Tokenizing code in header files (inline functions or templates) may trigger warnings such as ``-Wlto-type-mismatch`` under certain conditions. That is because tokenization requires declaring a character array for each tokenized string. If the tokenized string includes macros that change value, the size of this character array changes, which means the same static variable is defined with different sizes. It should be safe to suppress these warnings, but, when possible, code that tokenizes strings with macros that can change value should be moved to source files rather than headers. Tokenized strings as ``%s`` arguments ------------------------------------- Encoding ``%s`` string arguments is inefficient, since ``%s`` strings are encoded 1:1, with no tokenization. It would be better to send a tokenized string literal as an integer instead of a string argument, but this is not yet supported. A string token could be sent by marking an integer % argument in a way recognized by the detokenization tools. The detokenizer would expand the argument to the string represented by the integer. .. code-block:: cpp #define PW_TOKEN_ARG PRIx32 "`` sections with one ``pw_tokenizer.entries`` section. The Python tooling continues to support the legacy tokenized string ELF format. Compatibility ============= * C11 * C++11 * Python 3 Dependencies ============ * ``pw_varint`` module * ``pw_preprocessor`` module * ``pw_span`` module