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:

During compilation, the pw_tokenizer module hashes string literals to generate stable 32-bit tokens.

The tokenization macro removes these strings by declaring them in an ELF section that is excluded from the final binary.

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.

During operation, the device encodes the string token and its arguments, if any.

The encoded tokenized strings are sent off-device or stored.

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 voltage: %d mV"`	41
	(log statement is called with `"CHARGING"` and `3989` as arguments)
Device transmits	`"Battery state: CHARGING; battery voltage: 3989 mV"`	49
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

`d9 28 47 8e`	`08 43 48 41 52 47 49 4E 47`	`aa 3e`
Token	`"CHARGING"` argument	`3989`, as varint

15

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.

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.

Use the tokenization macros in your code. See Tokenization.

Add the contents of pw_tokenizer_linker_sections.ld to your project’s linker script. In GN and CMake, this step is done automatically.

Compile your code to produce an ELF file.

Run database.py create on the ELF file to generate a CSV token database. See Managing token databases.

Commit the token database to your repository. See notes in Database management.

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.

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.

constexpr uint32_t token = PW_TOKENIZE_STRING("Any string literal!");

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.

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.

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);

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.

PW_TOKENIZE_TO_CALLBACK(HandlerFunction, "Format string: %x", arguments...);

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.

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.

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.

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:

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 tokenization domain. Use PW_TOKENIZER_DEFAULT_DOMAIN for the default. The token also may be masked; use UINT32_MAX to keep all bits.

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 pw_log_tokenized.

#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.

#include "pw_log_tokenized/log_tokenized.h"
#include "pw_tokenizer/encode_args.h"

void HandleTokenizedMessage(pw::log_tokenized::Metadata metadata,
                            std::span<std::byte> 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);
}

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.

#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.

#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<LogLevel>(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.

// 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.

pw_tokenizer.encode.encode_token_and_args(token: int, *args: Union[int, float, bytes, str]) → bytes¶

Encodes a tokenized message given its token and arguments.

This function assumes that the token represents a format string with conversion specifiers that correspond with the provided argument types. Currently, only 32-bit integers are supported.

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.

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.

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.

// 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.

./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.

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 <database> 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.
python -m pw_tokenizer.database mark_removed --database <database> <ELF files>
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 bits	Collision probability by string count
Token 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.

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.

[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).

./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.

./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.

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.

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:

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:

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:

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.

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.

Detokenizer detokenizer(TokenDatabase::Create(token_database_array));

std::string ProcessLog(span<uint8_t> 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.

// This line fails to compile with a static_assert if the database is invalid.
constexpr TokenDatabase kDefaultDatabase =  TokenDatabase::Create<kData>();

Detokenizer OpenDatabase(std::string_view path) {
  std::vector<uint8_t> 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.

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,

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.

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:

# 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:

Tokenized strings will not be discovered by the token database tools.

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.

#define PW_TOKEN_ARG PRIx32 "<PW_TOKEN]"

constexpr uint32_t answer_token = PW_TOKENIZE_STRING("Uh, who is there");

PW_TOKENIZE_TO_GLOBAL_HANDLER("Knock knock: %" PW_TOKEN_ARG "?", answer_token);

Strings with arguments could be encoded to a buffer, but since printf strings are null-terminated, a binary encoding would not work. These strings can be prefixed Base64-encoded and sent as %s instead. See Base64 format.

Another possibility: encode strings with arguments to a uint64_t and send them as an integer. This would be efficient and simple, but only support a small number of arguments.

Legacy tokenized string ELF format¶

The original version of pw_tokenizer stored tokenized stored as plain C strings in the ELF file instead of structured tokenized string entries. Strings in different domains were stored in different linker sections. The Python script that parsed the ELF file would re-calculate the tokens.

In the current version of pw_tokenizer, tokenized strings are stored in a structured entry containing a token, domain, and length-delimited string. This has several advantages over the legacy format:

The Python script does not have to recalculate the token, so any hash algorithm may be used in the firmware.
In C++, the tokenization hash no longer has a length limitation.
Strings with null terminators in them are properly handled.
Only one linker section is required in the linker script, instead of a separate section for each domain.

To migrate to the new format, all that is required is update the linker sections to match those in pw_tokenizer_linker_sections.ld. Replace all pw_tokenized.<DOMAIN> 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

pw_tokenizer¶

Basic overview¶

Example: tokenized logging¶

Getting started¶

Tokenization¶

Tokenization macros¶

Tokenize a string literal¶

Tokenize to a handler function¶

Tokenize to a callback¶

Tokenize to a buffer¶

Tokenize with a custom macro¶

Binary logging with pw_tokenizer¶

Tokenizing function names¶

Tokenization in Python¶

Encoding¶

Token generation: fixed length hashing at compile time¶

Tokenization domains¶

Smaller tokens with masking¶

Token collisions¶

Working with collisions¶

Probability of collisions¶

Token databases¶

CSV database format¶

Binary database format¶

Managing token databases¶

Create a database¶

Update a database¶

GN integration¶

Detokenization¶

Python¶

C++¶

Base64 format¶

Encoding¶

Decoding¶

Command line utilities¶

Deployment war story¶

Results¶

Firmware deployment¶

Database management¶

Decoding tooling deployment¶

Limitations and future work¶

GCC bug: tokenization in template functions¶

64-bit tokenization¶

Tokenization in headers¶

Tokenized strings as %s arguments¶

Legacy tokenized string ELF format¶

Compatibility¶

Dependencies¶

Tokenized strings as `%s` arguments¶