DEV Community: Benjamin Kampmann

Fighting the Client Spaghetti Monster with Rust Traits

Benjamin Kampmann — Tue, 09 Dec 2025 00:00:00 +0000

tl;dr: In Rust, "trait composition" are a neat way to keep code, where a lot of components come together and need to be piped up, clean and avoid spaghettification.

Originally posted on my blog

Introduction

A major part of my almost two decade long career in programming has been spent working on “SDKs” in Rust. By which I mean building and maintaining complex systems as libraries used by other developers to implement applications on top of. I did this back at Immmer (now defunct), for Parity with Substrate Core/Client as well as its inner on-chain application SDK to the matrix-rust-sdk and last but not least at Acter for the Acter App and then the Zoe (relay) system.

For a while, but especially during latest iteration, I have been wondering about that highest layer architecture. How to design that client, where all these subcomponents are piped together. How to design it in a way that stays flexible for yourself as well as others, yet robust and ideally testable. How to avoid spaghettification of the client, even if the underlying components are complex trait-based systems themselves.

As we have to cover a lot of surface area itself, I will not be discussing trait themselves too much – check the corresponding chapter in the excellent Rust book, if you are looking for that – but assume you have an understanding of traits, trait bounds and have implemented them in Rust. I will throw around some almost-real code and examples without asking and expect the reader to be able to parse and understand them without much help. As I want to focus on the higher level “how do we use this”-architecture perspective.

Traits in SDKs

As with any big task, the best way to tackle it is by splitting them into smaller, manageable tasks and implement these one by one. The same is true for building up large SDKs. Often times they contain various components, like a storage layer; network or communication components; some internal state machine for the actual domain specific logic; and maybe some developer-front facing API or even UI components. To make implementing more manageable, it is common place to split them up into the separate independent components, sometimes even as separate crates, and provide an outer interface.

In the SDK world you often find that these components internally need to be plugable themselves though. Like a storage component might be implemented with an embedded SQLite for mobile Apps, with some SQL-backend-service or NoSQL-Database on the Server and with IndexDB in the Browser (with Wasm). Generally, the outer composed system doesn’t really have to care which of these is being used and thus it can be up to that component to define that. A common way to provide this abstraction is by defining a trait for that lowest layer and have these various specific parts implement them. Then the higher layer and also the layers on top can focus on their specific side of things.

This also nicely allows for these implementations that come with their own implementations to be only pulled. Or only compile for the targets that actually use them, as well as introduce new implementations via feature-flags gradually into production. It’s a pretty neat way of organizing the code. In the Matrix SDK we have that layer for implementing storage for example, and though not strictly because of the trait, the SDK even provides a macro to generate the entire test suite against your custom implementation that you can use.

To the mock

Having these traits brings in another nice benefit: Mocking. As the higher level components might have their own logic (like caching or ordering or something) testing often requires to set up the lower level component(s) as well. If instead, you defined that interface in a trait, you can implement various Mock-types to test a range of scenarios for your functions and focus on this specific logic. What sounds tedious at first becomes a breeze with the help of crates like mockall. It’s a lot easier and often faster than setting up that lower level layer just to test that the component pulls the objects from the store and returns them sorted regardless of the underlying order.

Middleware-ing

Similarly, by having the traits define the interfaces, you can add functionally nicely in a middleware-kinda fashion similar to what is done many web servers. Think of a caching layer on top of the database as an example. That caching layer can wrap anything implementing the trait while also implementing the trait itself. That way you can implement a LRU cache or something, regardless of the underlying storage types. As the interface is just the same trait again, you can mock the lower layer, ensuring a good test coverage on exactly what this layer does. Further you can just plug this “middleware” into the higher level layer without any further changes. This is how we implemented a storage layer for the Rust SDK that splits off media storage (before that was added to the SDK itself) and keeps them at different path (in the mobile’s “cache” directory), for example while passing along everything else to whatever inner database system was being used otherwise (e.g., SQLite).

But specific, sometimes

Now, for the traits you only want to expose the common interface of course. But specific implementation sometimes still have APIs to fine tune or configure certain things - like the path for the sqlite database. You don’t want to put these on the traits as they are implementation specific and pointless for other implementations. But as traits are implemented on specific types, your concrete types can still add these helper functions and as the higher level API / SDK you often just use feature-flags to then expose them or not.

Composing over many traits

Now that you understand the complexity and usage of these subcomponents, think about how you tie them all together in the Client. This needs to connect these components, move messages from one component to another, for e.g. to get that messages that just came in from the network to the internal state machine. And a results from the state machine which triggers the storage layer to persist some of these changes. Of course you want the client to be as flexible over the specific implementations as possible – most of that higher level code doesn’t really differ whether the message comes from LoRa, over QUIC or libP2P. It doesn’t matter to the client whether it will be stored in an SQlite database or IndexDB either.

But at times you have interdependencies, so the Rust compiler need to make sure that the type that the network layer message returns is the one that the state machine accepts. This is where things often spaghettify.

At the beginning that feels reasonable, but over time it grows, and the more things are pluggable, the more generics you need to add. The client needs one generic, then another, then another… Moving from single letter to entire words, running out of words. Sooner than you think it becomes incomprehensible to follow. Not even mentioning that ever increasing tree of trait bounds you have to keep around everywhere you expose that client. Which is your main external API surface area, so you expose it a lot. Brave are those, who then need to add another bound (like Send) to any of the lower traits…

“There must be a better way”, you think to yourself …

The three paths of the enlightenment

As always, you have a few options with its various benefits and trade offs to manage this nicer. You can Box<dyn Trait> it, use type aliases or compose a Trait with associated types. Let’s look at them one by one, in order of increasing complexity.

Type alias

The first thing that probably comes to mind, is alias some of the types definitions to make it a bit cleaner. So you’d still have some components that are generic of some sub traits struct GenericStateMachine<S: StateT, M: MessageT> that implements most of the concrete logic, but then for the production environment you have an alias type NativeClientStateMachine = GenericStateMachine<NativeState, TcpMessage>; that you could use.

Depending how you organize your code, the final client could really end up being a type NativeTcpClient = GenericClient<NativeClientStateMachine, NativeClientStorage, TcpProtocol>; itself. And you could even have a builder that depending on the target returns one or the other type, but both have the same API implemented via the traits.

impl Builder {
    #[cfg(target_arch = "wasm")]
    pub fn build() -> Result<WasmClient>{
        //
    }

    #[cfg(not(target_arch = "wasm"))]
    pub fn build() -> Result<NativeTcpClient>{
        //
    }
}

impl GenericClient<StateMachine, Storage, Protocol> {
    pub fn state_machine(&self) -> &StateMachine {
        //
    }

    pub fn storage(&self) -> &Storage {
        //
    }
}

Giving you all the benefits of having the concrete types, including access to the actual types, so the consumers code could even do implementation specific calls and its compile would fail if they tried to do that against a type that doesn’t implement those (e.g. because they picked a different target arch). Of course this only works as long as the compiler doesn’t force you to specify which exact type you are expecting but can still infer that itself.

However, you end up with rather lengthy type alias lists you need to manage, especially if you do the wrapping of middlewares I described before, which can be hard to parse and follow, just check this ZoeClientAppManager, which itself wraps a bunch of aliases.

pub type ZoeClientStorage = SqliteMessageStorage;
pub type ZoeClientSessionManager = SessionManager<ZoeClientStorage, ZoeClientMessageManager>;
pub type ZoeClientGroupManager = GroupManager<ZoeClientMessageManager>;
pub type ZoeClientAppManager =
    AppManager<ZoeClientMessageManager, ZoeClientGroupManager, ZoeClientStorage>;
pub type ZoeClientMessageManager = MultiRelayMessageManager<ZoeClientStorage>;
pub type ZoeClientBlobService = MultiRelayBlobService<ZoeClientStorage>;
pub type ZoeClientFileStorage = FileStorage<ZoeClientBlobService>;

Navigating this tree isn’t easy. Especially when debugging you can easily end up at the wrong layer and wonder why your changes aren’t showing up.

`dyn Trait`s

A common idea that might come to mind is to wrap the specific implementation in a new type that holds it internally in a dyn Trait, if the trait can be made dyn compatible (formerly known as “object safety”). In practice the type most likely must be wrapped in either Box, Arc or similar - if that is what is happening already anyways then this might not be a problem. If dynamic dispatching is not too much of an overhead, this could be a viable solution.

This is exactly how the Matrix Rust SDK implements the storage layer: by wrapping the specific implementation into a Arc<dyn StateStore> and then exposing a StateStore interface without any generics.

But dyns come with another drawback: the compiler forgets all notion of the concrete type. While this can be cheaper in terms of code size (as generic functions aren’t repeated for each type), it also means that our specific type “is gone”. Any other methods that this type implements outside of the trait become inaccessible. In the Matrix SDK for storage, that seems to be acceptable, as the only implementations specific tuning happens in the builder setup before it is passed to the StateStore.

But something as simple as getting implementation-specific configuration parameters returned from that type at runtime is now impossible, even if the type in question implemented it and it can be asserted that the type is the one.

Trait Composition

If dynamic dispatching isn’t feasible or the specific types needs to still be available, that alias list grows too long and becomes to tedious to update, you might come up with: a trait combining all the types – I call them composing trait. Rather than having a generic client with an increasingly growing list of generics, you define a trait that defines the specific types via associated types. This is what we have been doing in the Parity SDK and on-chain wasm state machine.

The idea is to create a new trait Configuration that defines all the requirements as associated types and have a client only reference that trait now. It can still return aliased or sub-types that are generic, but are then for that specific configuration. Like this:

pub trait Configuration {
    type Storage: StorageC;
    type Network: NetworkC;
    type StateMachine: StateMachineC;
}

impl<C> Client<C: Configuration> {
    pub fn state_machine(&self) -> &GenericStateMachine<C::StateMachineC> {
        //
    }
    pub fn storage(&self) -> &GenericStorage<C::StorageC> {
        //
    }
}

Unfortunately, in reality this is rarely as clean. Often you find yourself needing to define the interdependencies as well. For example: the network needs to give you a specific MessageT that the state machine also actually understands. Even if you use a trait here, the compiler will enforce that you use the same type. As a result, you end up with even very low-level trait definitions popping up on your highest level configuration so that you can cross reference them via the associated types:

trait MessageT: Sized {}
trait StorageC {
    type Message: MessageT;

    fn store(&self, message: &Self::Message) -> bool;
}
trait NetworkC {
    type Message: MessageT;

    fn next_message(&self) -> Option<Self::Message>;
}
trait StateMachineC {
    type Message: MessageT;
    type Storage: StorageC<Message = Self::Message>;

    fn process(self, message: &Self::Message);
}

trait Configuration {
    type Message: MessageT;
    type Storage: StorageC<Message = Self::Message>;
    type Network: NetworkC<Message = Self::Message>;
    type StateMachine: StateMachineC<Storage = Self::Storage, Message = Self::Message>;

    fn network(&self) -> &GenericNetwork<Self::Network>;
    fn storage(&self) -> &GenericStorage<Self::Storage>;
    fn state_machine(&self) -> &GenericStateMachine<Self::StateMachine>;
}

Nice, and clean, but you can already see how it will become more complex when these traits grow in complexity. In particular when you have to do changes to some of them, it ripples through the entire system quickly with rather hairy and complex bounds that are failing in very verbose error messages. Let’s just add an ErrorT type that our client might yield, when any of the inner yield an error. So the client is meant to wrap all the inner types. We add

trait ErrorT {}

trait StorageC {
    type Message: MessageT;
    type Error: ErrorT;
//.. to all types
}

// and on the config:
//
//
trait Configuration {
    // ...

    // gee, this is verbose...
    type Error: ErrorT +
        From<<Self::Storage as StorageC>::Error> +
        From<<Self::StateMachine as StateMachineC>::Error> +
        From<<Self::Network as NetworkC>::Error>;
}

It’s a bit verbose, but reasonable overall. It becomes more tricky when you actually try to implement these types as you need to make sure all the types also match up correctly. That way we are able to reduce the generics on client from many to just one. Nice. But dragging around this massive Configuration is a pain, especially for the mock-test-ability as we described before, as we have to mock all the associated types, creating a lot of glue code.

So instead, what I end up doing is have anything with actual logic still be referring to the generics directly, so you can mock and test these specific ones, and have the final Client<C: Configuration> just be a holder that then passes along to the specific internal type with the associated types passed in as generics.

In practice it can become even more tricky if you have some of these configuration on several layers. Like in the Parity Substrate Codebase, to allow all clients to build on reusable CLI tooling there is a Service that can construct your client. That service requires a Configuration for Network and alike, but only a subset of what a Full Node needs and as result, that second needs to be a super set of the first. But that is a really advanced scenario, and if you have any good ideas to improve that situation, I am all ears.

Conclusion: Combined Composition

As so often, enlightenment isn’t picking one solution but combining wisely.

What you probably end up doing is a combination of these compositions types. Like in the Rust Matrix SDK, where in a lower level, the plugable storage is then held via a dyn Trait, while on a higher level, you might compose a client with an “trait composition” that allows any other (rust) developer to plug and replace any of the components as they please, including yourself for platform or target specific implementations.

By keeping any actual logic in the separate components with specific traits for easy mocked testing and using the “client” merely as the place were all these pipes come and plug together, you can rely on the compilers type checks as a means to ensure the correctness of the types being piped, while you have the mock tests for all the actual logic. And integration tests should cover the end-to-end functionality of the client regardless.

To wrap things up nicely, you can hide that Client<C> inside a type alias that itself is held by a struct FfiClient(NativeClient); on which you expose a completely typed no-generics rust-external API. Put on a bow and ship it :) .

Credits: Photo taken by Gabriel (who is available for hire) and published on unsplash.com under a free license

Beware of the DashMap deadlock

Benjamin Kampmann — Fri, 29 Mar 2024 23:00:00 +0000

Rust is famously build for the multi-threaded-processor world. From its core ownership-enforcement-model up to the type-based Sync + Send-types, all is around allowing the compiler to ensure memory safety and consistency across thread boundaries. And though the std also has collections (like HashMap and BTreeSet), Atomics and Locks, once you start building real programs with Rust, probably some tokio for async-support as well, these are not always sufficient.

DashMap for the Win

No wonder that you can pick from a handful of libraries helping you achieve this feat, and quite a feat that is, with DashMap being among the most popular with a whopping 52million downloads on crates.io at the time of this writing:

52million downloads, years since publication, updated just a few months ago. That looks like a reasonably sound library. So, you start playing with it and find that its API is convenient, seems to work across awaits and async and all the things you've ever dreamed of. So you implement it as the main caching layer for the transient state machine of models within the core business logic of your application.

Deadlocks? Really?

I is only a long while later, until the first reports come in. Sparse at first and unclear in its origin, but sometimes, it seems, your state machine processing doesn't process the events coming in. Or, better - as you learn when digging into it - their futures never resolve.

You see, already known since at least December 2022 is that you can use DashMap in a way that can cause deadlocks and without the compiler detecting them.

A primer on dead locks

If you have no further knowledge about locks and have never heard of deadlocks, let me give you a minimal rough cut of the problem (overly simplified): Sometimes you have memory that is accessed by multiple threads, but clearly if both write at the same time this can cause problems. Thus, the concept of "locks" was created: small pieces around the memory that you need to have hold of first before you can write to that memory. While it is locked no other thread can write to it and thus have to wait for their turn. Ensuring they all write-one-at-a-time and not in between one another.

Now, how ever long you hold that lock is your prerogative and there are several problems with holding a lock very long. For example: what if your thread panics while you hold the lock? This in rust is usually referred to as a "poisoned lock", you might have seen that Error in the std, and how to deal with that depends on the specific code.

In this case, we are looking into a so called dead-lock situation. This can even be cause by a single thread easily: when you hold the lock and your code, running on the same thread, for whatever reason, tries to acquire the same lock while still holding the lock. This stops the execution as the thread is waiting on the lock it itself is holding and thus preventing from being released.

This type of scenario can be and in the std-cases is detected by the rust compiler (yay), but not in the case of DashMap. As DashMap actively allows for locks to be held over await-points (that is kinda its jam ... that it allows the user to do that), it isn't possible for the compiler to figure out that this might lead to a dead lock.

How to avoid that problem

The best advice is the one given from [Alice in her post from January 2022] already:

It is especially important to follow the advice about never locking it in async code when using dashmap for this reason.

While this is good advice, this isn't really mentioned on the docs of DashMap and considering there is nothing detectable wrong with the examples showing the problem when looking at the code this is quite the foot gun.

However, the code in question in our case doesn't even hold any locks over await-points, yet it seems to deadlock in some race condition scenarios.

Then you only find out about it after some long debugging and researching the github issues of that dependency. Taking all that into account, and then that there is no real way for you to create tests or otherwise automatically ensure it isn't reintroduced by any further update the code ... I consider this pretty harmful.

What to do about it?

Well, supposedly, this is fixed the in next big iteration of DashMap, which is said to have async support by getting rid of locks entirely, but with the issue open since 2021 and most of the ideas of how to avoid the locks being discounted for now, there is no telling when this come - if ever. What I have seen most people do referencing that issue, and what we also ended up doing is: replace or at least remove DashMap from the code base.

In our case we replaced it with the up and coming scc, which uses a different locking concept and has the additional benefit of being faster. Others have opted for cachemap2 or replaced it with the std lock & hashmap: there at least the compiler will tell you if you accidentally created a dead-lock-scenario.

No disrespect

I am not writing this post to shit on the authors of DashMap, nor its contributors or maintainers. Building a async-safe lock-free-ish collection is a hard task. One that I wouldn't even really want to attempt myself. I still personally don't even understand why this deadlocks internally myself, nor would I consider trying to patch it either - considering that they haven't done it yet makes leads me to believe this isn't an easy thing to do. As such I don't think anyone should be mad about them either, call them names or do any of the other nasty things the internet can do to people that lost its favor.

I am raising this issue because this is a pretty widely spread library, probably the most popular for the concurrent hashmaps and this is a severe problem that you should know about when using it. That's why I spent a significant amount of this post explaining the core problem and how to avoid it. So, if you use DashMap and want to continue using it, you know what to look out for now.

Edit 2024-04-01: Edited for clarity, based on corresponding feedback and removed a misleading quote.

Adding a new Ghost via docker-compose to your traefik setup

Benjamin Kampmann — Fri, 02 Feb 2024 19:31:30 +0000

Sometimes the easiest and quickest way to try (or even deploy) a new service is by using the recommended docker-compose-setup that they often have as an example. But if you have an existing infrastructure, like we do with the great mother of all self-hosting ansible playbooks, this isn't always easy to integrate. In particular when that infrastructure is managed and started and stopped independently from the additional docker-compose you intend to add. Lucky, who is running their out-most proxy using traefik, because with just a few extra labels your docker-compose becomes available TLS-certs included.

Fortunately for us the MASH-playbook uses traefik and so adding a Ghost setup for testing was quick and easy. Let's look at the docker-compose (for our fictional blog.example.org-address) and then we'll explain some of the specific aspects to address:

version: '3.1'

services:

  ghost:
    image: ghost:5-alpine
    restart: unless-stopped
    environment:
      # see https://ghost.org/docs/config/#configuration-options
      database__client: mysql
      database__connection__host: db
      database__connection__user: root
      database__connection__password: SOME_PRIVATE_ROOT_PASSWORD
      database__connection__database: ghost
      # this url value is just an example, and is likely wrong for your environment!
      url: https://blog.example.org
    volumes:
      - ./data/ghost:/var/lib/ghost/content
    networks:
      default:
      traefik:
        aliases:
         - blog-example-org

    labels:
      - traefik.enable=true
      - traefik.docker.network=traefik
      - traefik.http.routers.blog-example-org.rule=Host(`blog.example.org`)
      - traefik.http.services.blog-example-org.loadbalancer.server.port=2368
      - traefik.http.routers.blog-example-org.entrypoints=web-secure
      - traefik.http.routers.blog-example-org.tls=true
      - traefik.http.routers.blog-example-org.tls.certResolver=default
      - traefik.http.routers.blog-example-org.service=blog-example-org
  db:
    image: mysql:8.0
    restart: unless-stopped
    networks:
     - default
    environment:
      MYSQL_ROOT_PASSWORD: SOME_PRIVATE_ROOT_PASSWORD
      MYSQL_DATABASE: ghost
    volumes:
      - ./data/db:/var/lib/mysql


networks:
  traefik:
    external: true
  default:
    external: false

Alright, there's a few things here that have changes compared to the default example from ghost. We will be ignoring the specific Ghost and MySQL changes as they aren't that relevant but are only included for completeness.

The networks

First and foremost, we have the additional networks-section a the bottom of the configuration with two networks: default which we will use for this specific service and the other that is bridging to the traefik-service, which is marked as external: true telling docker to use the existing set up network. This must the the network the dockerized traefik is using. In the case of MASH this is just called traefik as well.

Secondly we need to the networks-section to both our services, where any internal service is only on the default network and the exposed service must also be on the traefik-network. Here we also give it some specific DNS name within that network for traefik to route the traffic to.

the `traefik` labels

When traefik is set up to use docker-labels, which is the case in our MASH setup, we can just label our service with a view fields and the traefik service will automatically recognize and configure the routing appropriately. Let's go through them one by one:

traefik.enable=true: to configure traefik to route this one. Depending on your setup this might not be needed
traefik.docker.network=traefik: the network traefik is on
traefik.http.routers.blog-example-org.rule=Host(\blog.example.org): the actual hostname we want this service to be available under between the final ticks. Note that we are creating a custom traefik-router for this called blog-example-org, all the following configuration is also using that router prefix:
traefik.http.services.blog-example-org.loadbalancer.server.port=2368: the port on this service the traffic should be routed to
traefik.http.routers.blog-example-org.entrypoints=web-secure: if the traefik has multiple outsid eendpoints, which ones to serve - in the MASH case we want this to be available at https, which is named web-secure in our setup.
traefik.http.routers.blog-example-org.tls=true: to enable TLS for this router
traefik.http.routers.blog-example-org.tls.certResolver=default: use the default DNS cert resolving functionality. In MASH this means we are using lets-encrypt certification
traefik.http.routers.blog-example-org.service=blog-example-org: the service to route the traffic to. The value is the dns-alias we gave in the network configuration before.

up and go

And that's about it. Assuming the DNS name already resolves to your server and your traefik is already running just doing a docker compose up -d and a short time later (if it needs to fetch the certificates for the first time), the service will be routed through and be available at blog.example.org. Neat!

Six niche tips for shipping Flutter MacOS builds

Benjamin Kampmann — Thu, 11 Jan 2024 11:00:00 +0000

Ever since we started shipping Acter to the Apple iOS AppStore, we wanted to have it on the Apple MacOS Store as well. With us building it on Rust and Flutter this should have been quite an easy feat as both have native support for MacOS. Yet actually shipping it was multiple months of try and error—with the last month spent on just a tiny problem caused by the Github Actions Runners. these are six niche tips we wished someone had told us before, that would have saved us months of work.

Nightly builds as the baseline

For testing and internal distribution we had nightly builds in Acter for a few months already. They would automatically be created every night at 3am (hence the name) if changes had been found on the main branch. Our build here consists of two parts: the internal Rust library and then we follow with a simple flutter build $target. So obviously, we have created a nice Github Actions Matrix to reuse as much as possible. I am not going into too much detail here and the latest action setup probably already changed when you read this, but I have linked the specific sections for record. the

1. MacOS is iOS but different—and Google won’t tell you

For the release build of iOS to work, we needed to sign the app. As a matter of fact, the flutter build won’t really work if you don’t have the necessary signatures set up. For iOS nightly we use an Ad-Hoc setup with a few pre-configured internal devices, for the release we used the distribution profiles, both stored as environment secrets as is so commonly used in many tutorials. For MacOS signatures aren’t necessary to build and distribute the App - presumably because MacOS App development pre-dates signed builds. Thus our nightly builds didn’t have any setup for that yet.

Another important difference to note is on the flutter side. While flutters build ipa offer the options --export-options-plist=PATH allowing you to specify certain plist information overrides for that specific build, no such option exists in flutter build macos. Meaning that all the configuration setup inside the macos-folder is and must be used as-is. That is a bit annoying as it means we can’t easily make a local release build without the signatures now but that’s what it is.

One annoying side-effect of Flutter being a lot more popular for building mobile apps is that when you try to Google for information regarding the apple setup needed you’ll almost exclusively find questions and problems for iOS. They then recommend stuff like the export-options-command or other obscure settings you are supposed to change via xcode but that doesn’t actually do anything in the desktop version or doesn’t even exist. Google really doesn’t help you when you get stuck with your Flutter MacOS build.

2. Switching from github environment secrets to git-crypt for signatures and profiles

One thing we wished we had done earlier was switching from storing signatures and provisioning profiles in Github secret environment variables to using git-crypt`. Many tutorials and setups out there recommend using the Github secrets to store, well, secret information like the provisioning profiles and the secrets from the keychain and then have some companion script that puts that into the local Github Action build. That is all good and dandy if you only do that setup once and rarely change it. But I always found it kinda annoying that despite no hint in the Git history a build might fail or pass. Once you go beyond just managing a single profile the scripts are then often falling apart and the increasing number of environment variables becomes very confusing and it is super easy to mess up in converting them into the right base64 because it was soo long ago you did it last.

Rather than storing profiles and the keystore and similar file-based secrets in the secret environment variables we switched to using git-crypt a git extension you can configure that transparently encrypts a subset of files before committing them to the repo. That makes it super easy and simple to update them and still keep the files available. Rather than extracting each secret from the environment into a file we just install git-crypt and have the main password as the action secret that we then use to decrypt the files:

- name: Unlock git-crypt
  if: matrix.with_apple_cert
  run: |
    brew install git-crypt
    echo "$" | base64 --decode > .github/assets/git-crypt-key
    git-crypt unlock .github/assets/git-crypt-key
    echo "Files found:"
    git-crypt status -e

Once we have the files decrypted, we use the commonly used script to import the keychain from the now decrypted file. Technically we wouldn’t even need the extra password for that file, but it also doesn’t hurt:

# Install the Apple certificate and provisioning profile
- name: Install the Apple certificates
  if: matrix.with_apple_cert
  env:
    P12_PASSWORD: ${{ secrets.BUILD_CERTS_P12_PASSWORD }}
    KEYCHAIN_PASSWORD: ${{ secrets.KEYCHAIN_PASSWORD }}
  run: |
    echo "starting in $RUNNER_TEMP"
    # create variables
    CERTIFICATE_PATH=".github/assets/build_certificates.p12"
    KEYCHAIN_PATH="$RUNNER_TEMP/app-signing.keychain-db"
    echo "vars set"
    # import certificate and provisioning profile from secrets
    # create temporary keychain
    echo "creating keychain"
    security create-keychain -p "$KEYCHAIN_PASSWORD" "$KEYCHAIN_PATH"
    echo "setting keychain"
    security set-keychain-settings -lut 21600 "$KEYCHAIN_PATH"
    echo "unlocking keychain"
    security unlock-keychain -p "$KEYCHAIN_PASSWORD" "$KEYCHAIN_PATH"
    # import certificate to keychain
    echo "importing certificate"
    security import "$CERTIFICATE_PATH" -P "$P12_PASSWORD" -A -t cert -f pkcs12 -k "$KEYCHAIN_PATH"
    echo "listing keychains"
    security list-keychain -d user -s "$KEYCHAIN_PATH"

And finally we just take all the now decrypted provisioning_profiles files and copy them where they need to be. All files for all builds in the git repo. Sweet.

# Install the Apple certificate and provisioning profile
- name: Install the Apple certificates
  if: matrix.with_apple_cert
  env:
    P12_PASSWORD: ${{ secrets.BUILD_CERTS_P12_PASSWORD }}
    KEYCHAIN_PASSWORD: ${{ secrets.KEYCHAIN_PASSWORD }}
  run: |
    echo "starting in $RUNNER_TEMP"
    # create variables
    CERTIFICATE_PATH=".github/assets/build_certificates.p12"
    KEYCHAIN_PATH="$RUNNER_TEMP/app-signing.keychain-db"
    echo "vars set"
    # import certificate and provisioning profile from secrets
    # create temporary keychain
    echo "creating keychain"
    security create-keychain -p "$KEYCHAIN_PASSWORD" "$KEYCHAIN_PATH"
    echo "setting keychain"
    security set-keychain-settings -lut 21600 "$KEYCHAIN_PATH"
    echo "unlocking keychain"
    security unlock-keychain -p "$KEYCHAIN_PASSWORD" "$KEYCHAIN_PATH"
    # import certificate to keychain
    echo "importing certificate"
    security import "$CERTIFICATE_PATH" -P "$P12_PASSWORD" -A -t cert -f pkcs12 -k "$KEYCHAIN_PATH"
    echo "listing keychains"
    security list-keychain -d user -s "$KEYCHAIN_PATH"

Finally don’t forget to clean all that up, regardless of whether the build failed or succeeded!

- name: Clean up keychain and provisioning profile
  if: ${{ always() }}
  run: |
    security delete-keychain $RUNNER_TEMP/app-signing.keychain-db
    rm ~/Library/MobileDevice/Provisioning\ Profiles/*
    rm .github/assets/git-crypt-key

This makes it super easy to update all that data. Got a new provisioning profile? Just put it into that folder. Update to the keystore? Just export the p12-file with the same password again. No base64 conversion, no copying into the Github Secrets - just git commit && push. *chefskiss*.

3. Github Search is the hidden champion

One of Githubs most underrated features is its search. It being the biggest crowd source code knowledge base in the world, including the largest source for all their own configuration files (which the workflow-yamls are one of) their search can be truly amazing. Not everyone who found the hack to make something happen will blog about it or write a stack overflow—this post almost didn’t make it either. But it if works there is a high chance they commit it and it ends up in the Github repo, discoverable via the search.

Similar as Google, Github’s search has many advanced options. For us looking for alternative ways of doing the Flutter build within the Actions, adding the path:.github/workflow flutter macos was the key to unlocking a treasure of knowledge. Mind you that even though code is committed doesn’t necessarily mean it runs, though. But it is how we first found out about the git-crypt idea! And that’s also how we found out about the final upload pattern we ended up using.

Seriously, if you are ever stuck on some Github Action configuration that others probably already attempted try the Github search. Google doesn’t even know about a fraction of it and with the advanced search you can make the queries very specific to your problem.

4. MacOS apps need all their binaries signed

One particularly nasty difference between the iOS and MacOS flutter build is that the latter doesn’t really manage the signing properly for you. Singing the Mac App is different than the iOS one, too: While on iOS you create an ipa-file (effectively a Zip-File) which is then signed as a whole (oversimplified), the “Mac App” is actually a directory with the extension .app. You can’t effectively “sign” directories. Instead the people at Apple decided that what you must do is sign each binary within that app directory and provide these signatures in the directory. This is hidden in the docs somewhere but if you tried to Google for this information, you will only find iOS fixes (see No 1). So I am telling you know.

For most cases that is fairly irrelevant but as we had a bunch of binaries, our own included. We found a script that iterates through the final app and signs each binary with the provided credentials, which we then added to the regular Xcode shell-script build process for release builds. That means that at the end of flutter build macos, we now have an Acter.app directory with all the proper signatures included. Yay.

5. Build code ages quickly

One problem you’ll be facing with the Github Search as well as the Google search answers regardless is that the infrastructure you are building with and against constantly changes. For us, there were several tutorials out there recommending ways of packaging or uploading the app that were outdated to simply not supported anymore for the latest version (this was even worse for building the Windows App). Trying to figure out which is the latest recommended and thus hopefully the longest-lasting code you could write is a tedious and annoying process. Very often you don’t know this isn’t supported anymore until you installed and tried the command. But there is a few tricks to keep in mind, when you find a novel approach you might want to try out: you can check the official docs and see if it is still supported, if it is on Github you can see when it was last run, for StackOverflow and many blogs you can quickly gather whether this is a new or rather old idea. Unfortunately in this space, old often means less likely too still work…

For us the latest—at the time of writing—and recommended way to package and submit the Flutter MacOS app to the Apple Mac Store is:

build the release version of the app with flutter build macos; make sure all binaries are signed (see above)
use productbuild to create a modern .pkg and have it signed: productbuild --component Acter.app /Applications --sign "$APPLE_SIGN_CERTNAME" Acter.pkg
then use altool to upload the .pkg to the Apple Mac AppStore using a private_key credential (which we stored with git-crypt, of course):

      - name: Upload to App Store
     env:
       APPLE_API_KEY_BASE64: ${{ secrets.APPLE_API_KEY_BASE64 }}
       APPLE_API_KEY_ID: ${{ secrets.APPLE_API_KEY_ID }}
       APPLE_ISSUER_ID: ${{ secrets.APPLE_ISSUER_ID }}
     run: |
       mkdir private_keys
       echo -n "$APPLE_API_KEY_BASE64" | base64 --decode --output "private_keys/AuthKey_$APPLE_API_KEY_ID.p8"
       ls -ltas private_keys
       xcrun altool --upload-app --type macos --file acter-macosx-${{ needs.tags.outputs.tag }}.pkg \
           --bundle-id global.acter.a3 \
           --apiKey "$APPLE_API_KEY_ID" \
           --apiIssuer "$APPLE_ISSUER_ID"
     shell: bash

6. Github artifacts are not a proper package mechanism: measure twice

With that we are all set and everything should work. Yet Apple kept rejecting our app. But only after the upload in the post-processing on the server side, a few hours later we’d receive an email saying something along the lines of:

      - name: Upload to App Store
     env:
       APPLE_API_KEY_BASE64: ${{ secrets.APPLE_API_KEY_BASE64 }}
       APPLE_API_KEY_ID: ${{ secrets.APPLE_API_KEY_ID }}
       APPLE_ISSUER_ID: ${{ secrets.APPLE_ISSUER_ID }}
     run: |
       mkdir private_keys
       echo -n "$APPLE_API_KEY_BASE64" | base64 --decode --output "private_keys/AuthKey_$APPLE_API_KEY_ID.p8"
       ls -ltas private_keys
       xcrun altool --upload-app --type macos --file acter-macosx-${{ needs.tags.outputs.tag }}.pkg \
           --bundle-id global.acter.a3 \
           --apiKey "$APPLE_API_KEY_ID" \
           --apiIssuer "$APPLE_ISSUER_ID"
     shell: bash

The attentive reader might have already noticed the actual problem already. As we had gotten several similar looking emails (especially the top part) from before when the signatures were not properly set up for each binary, we assumed it was something wrong with that part again. Weirdly enough, when doing the entire process manually (rather than via Github Action) it all worked fine and Apple didn’t reject our submission. Weird. So we downloaded the latest Acter.app from the build artifacts to try to see if we could sign and submit that. The download was larger than usual (220mb rather than the usual 140mb we saw for most builds before) but we didn’t really think much about it. Indeed, trying to package and upload this version Apple rejected it again.

So, we look into the insides of the Acter.app build by the Github Action: it is just a folder after all (even though MacOS finder hides it under the right click -> Open Contents). Right away we noticed something odd: all binaries for the frameworks appeared to be in there twice: once under $framework/Versions/Current and once as $framework/Versions/A. That sure explained why it would be about twice the size. Interestingly our nightly builds didn’t show this behavior: there Current was a symlink to A for each as—we’d expect it to be. So although the nightly build system was the baseline we started with, we must have altered something along the way.

Then it hit us: the main difference is that in the nightly job packages the .app-Folder as a tar.bz directly and submits it to the Github release from the build job, while in the publishing action we store the folder as a Github Artifact that a second job after downloads and submits to the store.

Why does that matter? The Github Artefact is stored as a ZIP, too (to save disk space), after all. Yes, but for zipping by default is that symbolic links are resolved. As we are zipping the entire folder the symlinks that is usually Versions/Current -> Versions/A is resolved, meaning the files are stored twice. Yet the signature is only stored once and only for Versions/A (not for Versions/Current). So when we download that zipped version, we have an .app-folder with each framework version stored twice yet only a signature for one (and the file having about twice the size). Looking at the error messages sent by Apple, the last batch of errors even gives a hint to that problem.

Finding that issue, one and off, took us a month. Yet the fix was small and trivial: we moved the productbuild to create a .pkg-file from the publishing job into the build-job and store that .pkg-file as the artefact. Problem solved.

These are just a few things we wished we had known before. Do you have any additional tips for that—apparently niche—Flutter MacOS build systems you wished someone had told you before? Let us know below!

Hunting down a non-determinism-bug in our Rust Wasm build

Benjamin Kampmann — Fri, 10 Jul 2020 16:12:38 +0000

Note: Together with a few colleagues, I will be hosting an AMA on the Rust subreddit Wednesday, July 15th (today!). Come join us, if you have questions on this or any other part of our code base or how we handle things at Parity Technologies.

We recently learned that the WebAssembly build in our system isn't deterministic any longer. This is a short summary of what we did to chase down the bug in the hope that this helps others facing similar issues, give some help and guidance on what to try or how this kind of thing works.

A bit of background

Substrate / our stack

At Parity we are building software to run the next generation of the Web: a trust-less secure Web 3.0. Most notably we are building the Polkadot Network based on Substrate. Substrate is natively compatible with Polkadot, thus making it simple to secure your blockchain and communicate with Polkadot’s network. We have built everything using Rust which means no legacy codebase and it's open source.

Wasm Runtimes

A key architecture feature of Substrate is that the chain-specific state transition function (STF) is separated from the rest of the node. The binary WebAssembly (wasm) blob is stored on chain (at the key:code). The separation allows for network-wide upgrades of the state transition function independently from the rest of the client. These events happen through on-chain governance mechanisms. The client utilizes a wasm runtime, executing updated wasm blobs as the community decides to implement an upgrade. These mechanisms allow Substrate-based blockchains to evolve without the complicated aspects of Hard Forks. We call this forkless-upgrades, as participants can stay in sync with the network without relying on upgrading their client.

The way we achieve this is through building our the Rust-runtime-code in a separate crate with the wasm32-unknown-unknown target into a Wasm blob and store it on chain.

Deterministic builds

Wasm is overall a great invention providing a thin multi-plattform abstraction over the machine language target. Thus the wasm output from a compiler can easily be translated into the actual machine code needed for execution. However, WebAssemblz is not human readable, which makes it hard to audit for the people who should vote upon the chain upgrade. Upgrading a blockchain state transition function can't be taken back, so voting on an opaque block is not particularly instilling confidence in its users.

The way we approach this problem is through "deterministic builds". The rust compiler itself does not, as of now, guarantee that builds are deterministic – meaning that compiling the same code twice will yield the same resulting binary. However, Parity has managed to solve this problem for our code. So at least within the same environment (OS, Compiler, libs installed) it is reasonably deterministic for a set of targets to be consistent and wasm32-unknown-unknown is among them. This allows us to produce a docker-image (and its build description) confirming that the Rust source files indeed result in the binary blob proposed as the next chain runtime. Using the Docker image, auditors can look at the source code directly and do not have to wade through the wasm32 bytecode.

Whilein the past they did, we recently discovered that two consecutive builds of the runtime code did not yield the same wasm blobs anymore. This was the starting point when we realized that our build process had been broken.

Unfortunately we didn't have yet tooling in place to alert us about the problem, so we didn't know what introduced the bug. However we know when it last worked for sure: 2020-03-21T16:55:27Z . Here is what I did with that information to track down the problem:

0. The test

The first step towards the fix was devising a test that reproducibly displays the problem. In our case this was rather simple: build a specific package in the project (node-runtime) twice and compare the resulting wasm. We used the SHA256 hash of the compiler output to do that.
The specific step then are:

cargo build --release -p node-runtime   # build the first time
sha2sum target/release/wbuild/target/wasm32-unknown-unknown/release/*.wasm > checksum.sha256      # store the hash
cargo clean     # clean up the artifacts
cargo build --release -p node-runtime   # build again
sha2sum -c checksum.sha256    # are the build identical?

1. Nightly builds

Within our Wasm build we are using a few features that are not yet a fully supported by the Rust Compiler Team (aka Tier 1), so we need the nightly version to use it. As nightly is moving fast, features are added left and right and often times have unexpected side effects affecting determinism. It is not unlikely that upgrading nightly broke our build.

Luckily, all old rust nightly builds are available. With rustup and cargo, the amazing tooling Rust provides, it is easy to use and compile with any compiler version. So we first installed the old version via:

rustup install nightly-2020-03-19 # install nightly
rustup toolchain add nightly-2020-03-19 wasm32-unknown-unknown # the wasm target toolchain for that compiler version

This will install the last nightly version and the target toolchain we know to produce deterministic builds (Note: despite the name, it isn't released every night, often the compiler or some of the components fail to build and the version is skipped).

Now when building the crate we just add +nightly-2020-03-19 to the cargo command to tell it which version to use:

cargo +nightly-2020-03-19 build --release -p node-runtime   # build the first time
sha2sum target/release/wbuild/target/wasm32-unknown-unknown/release/*.wasm > checksum.sha256      # store the checksum
cargo clean     # clean up the build
cargo +nightly-2020-03-19 build --release -p node-runtime   # build again
sha2sum -c checksum.sha256    # are the build identical?

Unfortunately, that wasn't it: The nightly from back then doesn't produce the same wasm on the current version of our code either. But what about on the older version?

Nightly builds on old version

Checking out the old version of the code and building it with the old compiler was indeed deterministic. So what changed? The compiler.

Building the old code with the latest compiler also yields a deterministic build.

So we know it isn't a change in the compiler that was causing the determinism to break. This doesn't mean it isn't a compiler bug, but only that whatever it was, it wasn't introduced on their side but by changes from us.

2. `git bisect`

One of the great things about using popular (among developers) tools is that others add tooling on top that makes your lives easier. A lesser known but super useful of these tools that made it into mainline git already a few years ago, is git bisect. It helps you identify which changeset introduced a bug by applying a binary search on the commit history.

Essentially you tell git bisect which checkout you know to be git bisect good and git bisect bad, it then checks out the changeset in the middle of the two. You then perform your test and indicate the status via the same git bisect good or git bisect bad command. It then jumps in the middle between the latest known good and bad one and checks that out. And so you go until git bisect tells you this is the first change with the bug.

git bisect run even allows you to specify a command it should run that either succeeds or fails and lets git perform all the steps automatically. (Unfortunately I didn't have that script ready at the time and was actually building through a more complicated rsync-remote-build system – but that it can run that by itself is pretty awesome.).

Git bisect identified a pretty large PR to be the culprit . "Pretty large" not only because it adds a significant amount of code itself, it is also the first that activated a few features in the default runtime we are testing against, namely session_historical, which we already suspected to be related to this issue.

Unfortunately, this also didn't yield that one line that was the cause on our side. It could still be any number of aspects that cause it. One way forward could be to activate one feature after another to move closer and closer to the actual source. But that isn't as easy as it sounds, so we opted for wasm-introspection first.

Git bisect is a powerful tool and it often is crucial to help narrow down the scope of the search for a bug. Like this episode illustrates, it seldom pinpoints a specific line of code by itself.

3. Introspecting the Wasm

The wasm output from the rust compiler is a binary blob, but as any modern standard, it has a few introspection features built in. Most importantly, there is a 1-to-1 text-representation – called WAT – that it can the converted back and forth to without problem. And the default wasm toolchain already includes the handy wasm2wat tool.

Running wasm2wat on the wasm output of the first build and then again on the second build give us a human-parsable representation of the binary. Then we can diff the two wat version to identify what changed between them (omitted some lines marked as ... for legibility):

--- node_runtime_1_1.wat    2020-07-06 09:43:09.122043953 +0200
+++ node_runtime_1_2.wat    2020-07-06 09:43:14.178717225 +0200
@@ -791052,10 +791052,10 @@
                                             i32.add
                                             call $_ZN86_$LT$sp_trie..node_header..NodeHeader$u20$as$u20$parity_scale_codec..codec..Encode$GT$9encode_to17h7b42619bd7dc163dE
                                             local.get 15
-                                            br_if 11 (;@9;)
+                                            br_if 12 (;@8;)
                                             i32.const 0
                                             local.set 1
-                                            br 14 (;@6;)
+                                            br 13 (;@7;)
                                           end
                                           local.get 0
                                           i32.const 1
@@ -791092,10 +791092,10 @@
                                           i32.add
                                           call $_ZN86_$LT$sp_trie..node_header..NodeHeader$u20$as$u20$parity_scale_codec..codec..Encode$GT$9encode_to17h7b42619bd7dc163dE
                                           local.get 15
-                                          br_if 11 (;@8;)
+                                          br_if 10 (;@9;)
                                           i32.const 0
                                           local.set 1
-                                          br 12 (;@7;)
+                                          br 13 (;@6;)
                                         end
                                         i32.const 1
                                         local.set 17
@@ -966366,6 +966366,6 @@
   (export "__data_end" (global 1))
   (export "__heap_base" (global 2))
   ...
-  (data (;0;) (i32.const 1048576) "\04\80\e9\1b\80\14\10\00\80\14\10\00")
+  (data (;0;) (i32.const 1048576) "R\8a\11v\80\14\10\00\80\14\10\00")
   (data (;1;) (i32.const 1048592) " \00\10\00\17\00\00\00\ee\02\00\00\05\00\00\00src/liballoc/raw_vec.rs\00\c7\00\10\00F\00\00\00b\01\00\00\13\00\00\00J\00\00\00\04\00\00\00\04\00\00\00K\00\00\00L\00\00\00M\00\00\00a formatting trait implementation returned an error\00J\00\00\00\00\00\00\00\01\00\00\00N\00\00\00\b4\00\10\00\13\00\00\00J\02\00\00\05\00\00\00src/liballoc/fmt.rs/rustc/15812785344d913d779d9738fe3cca8de56f71d5/src/libcore/fmt/mod.

The diff is rather short. With just a bit of scrolling through the great Mozilla Wasm Explainer and the extensive and great wasm documentation by the original working group, we quickly learn that the first four changes are just labels that might just be having a different numbering because of compiler internals caused by the last change.

That last one is odd, though: It is a global memory address (at location 1048576), that is filled with differently prefixed values. What makes this particuarly odd is that if we searched for the address-number in the original wat file, we find it is marked as mutable.

  (table (;0;) 343 343 funcref)
  (global (;0;) (mut i32) (i32.const 1048576))
  (global (;1;) i32 (i32.const 1284452))
  (global (;2;) i32 (i32.const 1284452))

That is pretty weird, considering the context in which we are running this blob. Remember that the blob is stored on-chain, transparent to everyone. For the execution of each block, the wasm memory is reset and a new instance is created. In general, having mutable globals is pointless for the wasm we are producing, because it would only be live for the duration of the execution of a single block. If you want to mutate state from the runtime to be persisted between blocks, you'd have to call into the external database-storage functions. Because of this we generally don't have any mutable lazy_statics or alike in our code.

That doesn't mean that having globals is pointless for our wasm. It can be used for compiler optimisation. For example, every time we create a new Vec, it is reading the default values from a global address. This is quicker and needs less storage than pasting the values everywhere.

But, what is causing this memory address to be allocated here? Why would it be mutuable and why with a different value for every build?

Digging deeper
Well, we had to track down where it is being used. The compiler wouldn't mark it as mutable if it wasn't changed at least once. When searching we find it is being read from 8 times, but then once, we also see it being written to:


(func $_ZN14pallet_session10historical20ProvingTrie$LT$T$GT$12generate_for17hb9e80633994986a6E (type 2) (param i32 i32)
    (local i32 i32 i64 i64 i32 i32 i32 i32 i32 i32 i64 i64 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32 i32)
    global.get 0
    i32.const 928
    i32.sub
    local.tee 2
    global.set 0
    block  ;; label = @1
      block  ;; label = @2
        block  ;; label = @3
          block  ;; label = @4
            block  ;; label = @5
              block  ;; label = @6
                block  ;; label = @7
                  block  ;; label = @8
                    block  ;; label = @9
                      i32.const 1
                      call $__rust_alloc
                      local.tee 3
                      i32.eqz
                      br_if 0 (;@9;)
                      local.get 3
                      i32.const 0
                      i32.store8
                      i32.const 0
                      i32.const 0
                      i64.load32_u offset=1048576
                      i64.const 6364136223846793005
                      i64.mul
                      local.get 2
                      i32.const 640
                      i32.add
                      i64.extend_i32_u
                      i64.add
                      i64.const 31
                      i64.rotl
                      local.tee 4
                      i64.store32 offset=1048576
                      local.get 2
                      i32.const 8

Even without knowing too much WebAssembly ourselves, we have a few interesting hints in here:

the function name is _ZN14pallet_session10historical20ProvingTrie$LT$T$GT$12generate_for17hb9e80633994986a6E, which translates to ProvingTrie::generate_for in the session::historical module of our code base.
the indentation and many labels indicate that this is within some loop of loops.

Looking at the code we can identify three objects that are mutable – but only at that time, none of them is global. Or at least, as far as we can see, because in Wasm it clearly is.

Finding the source
Now that we have a precise point of focus, we can begin troubleshooting. Unfortunately, git won't help us here. We could trace back changes to that code base, but as it was only activated in the specific change set we've already identified, there is little that will help identify the source of the error.

impl<T: Trait> ProvingTrie<T> {
    fn generate_for<I>(validators: I) -> Result<Self, &'static str>
        where I: IntoIterator<Item=(T::ValidatorId, T::FullIdentification)>
    {
        let mut db = MemoryDB::default();
        let mut root = Default::default();

        {
            let mut trie = TrieDBMut::new(&mut db, &mut root);
            for (i, (validator, full_id)) in validators.into_iter().enumerate() {
                let i = i as u32;
                let keys = match <SessionModule<T>>::load_keys(&validator) {
                    None => continue,
                    Some(k) => k,
                };

                let full_id = (validator, full_id);

                // map each key to the owner index.
                for key_id in T::Keys::key_ids() {
                    let key = keys.get_raw(*key_id);
                    let res = (key_id, key).using_encoded(|k|
                        i.using_encoded(|v| trie.insert(k, v))
                    );

                    let _ = res.map_err(|_| "failed to insert into trie")?;
                }

                // map each owner index to the full identification.
                let _ = i.using_encoded(|k| full_id.using_encoded(|v| trie.insert(k, v)))
                    .map_err(|_| "failed to insert into trie")?;
            }
        }

        Ok(ProvingTrie {
            db,
            root,
        })
    }

When looking at the code, there are three main objects involved. It is also helpful to have a minimal understanding of the code base. We see two objects, both the root and the MemoryDB are passed to the trie. This is likely calculating a new trie root when the trie.insert (let _ = i.using_encoded(|k| full_id.using_encoded(|v| trie.insert(k, v))) is being called – the only thing we can actually see mutatating state here – and then passes the element through to MemoryDB.

So then, how is memory DB implemented?

pub struct MemoryDB<H, KF, T>
    where
    H: KeyHasher,
    KF: KeyFunction<H>,
{
    data: HashMap<KF::Key, (T, i32)>,
    hashed_null_node: H::Out,
    null_node_data: T,
    _kf: PhantomData<KF>,
}

It uses a HashMap.

HashMaps are tricky in a fixed-memory environment like wasm. I will not go into the details here, but most HashMaps use simplistic fast hashing functions that can cause collisions. This can degrade performance of a HashMap to the point of resulting in a DoS of the whole process. Any decent modern HashMap therefore adds some randomness when relying on hashing keys. Rusts std-implementation does this for example. However, a source of randomness doesn't exist within a wasm32-unknown-unknown environment, making generic (and in particular the std) HashMaps unsafe for user-controlled input.

Well, this isn't input users could easily control and use to bomb our hashmap, so that is fine. But the fact that modern implementations require a source of randomness is something to investigate. For a no_std like the wasm environment, the MemoryDB implementation takes the great implementation provided by the hashbrown crate – at version 0.6.3. with default features disabled as the Cargo.toml reveals.

It is important to note that default-features are disabled because otherwise hashbrown would activate the compile-time-rng feature in ahash. This is the hasher it utilizes internally. If the default-features is activated, the hasher would include const-random to generate a random seed for the hasher at compile time for some randomness.

This is similar to the problem we are debugging: a global constant, updated when we add a new key, that is slightly different on every compile.

Feature leaking
With the default features deactivated, how could it have snuck into our build still?

Well, looking just one line lower in the Cargo.toml reveals the answer. In order to fix a different compatibilty bug the MemoryDB attempts to pin the ahash crate to a non-broken version. In doing so, it activates the default features. And cargo features are additive, meaning that if one activates a features, all instances of the crate within the build have that feature activated. Thus leaking into our build.

Boom.

4. Fixing it

As you might have noticed, I was linking to specific older commits of these crates. On one side to give long-term correct links, secondly because those are the specific versions in use, but also because the problem is already partially address in newer version.
The latest ahash doesn't have the feature as part of the defaults anymore, it needs to be activated explictly. And by just removing the dependency pin in MemoryDB (which isn't needed anymore) and releasing a new version, the problem is gone here, too.

The test from step 0 is there to prove it. That very same test is now added as a proper CI-check that every PR must pass, so we notice early on if we broke it again.

5. Down the label-rabbit-hole

But it doesn't pass. The PR fixes the issue, yet the CI-check complains. Running the script directly and diffing the .wat's tells us why:

--- node_runtime_1_1.wat    2020-07-06 09:43:09.122043953 +0200
+++ node_runtime_1_2.wat    2020-07-06 09:43:14.178717225 +0200
@@ -791052,10 +791052,10 @@
                                             i32.add
                                             call $_ZN86_$LT$sp_trie..node_header..NodeHeader$u20$as$u20$parity_scale_codec..codec..Encode$GT$9encode_to17h7b42619bd7dc163dE
                                             local.get 15
-                                            br_if 11 (;@9;)
+                                            br_if 12 (;@8;)
                                             i32.const 0
                                             local.set 1
-                                            br 14 (;@6;)
+                                            br 13 (;@7;)
                                           end
                                           local.get 0
                                           i32.const 1
@@ -791092,10 +791092,10 @@
                                           i32.add
                                           call $_ZN86_$LT$sp_trie..node_header..NodeHeader$u20$as$u20$parity_scale_codec..codec..Encode$GT$9encode_to17h7b42619bd7dc163dE
                                           local.get 15
-                                          br_if 11 (;@8;)
+                                          br_if 10 (;@9;)
                                           i32.const 0
                                           local.set 1
-                                          br 12 (;@7;)
+                                          br 13 (;@6;)
                                         end
                                         i32.const 1
                                         local.set 17

Although our bug is fixed, the label issues are not and are persistent after. Other than we assumed, they are not caused by our fixed bug, they are their own bug.

Darn.

br and br_if are control flow conditions. This means they are marking the respective blocks stopping point, in addition to where the execution should continue after. Considering that there are no other diffs, the code jump seems to not differ, it just caused by the ordering of these labels by the compiler. Most likely this marking occurs by the method in which the labels are sorted within the compiler's final processing – specifcially, storing items by a non-determinstic collection internally (e.g. hashmap etc).

The most common place were this happens is in the optimization steps. If we build the wasm/wat in debug mode (without the --release flag) the diff doesn't show any changes. Thus strongly indicating that this was introduced somewhere in the optimization phase.

6. How the sausage is made

Rust, and the rust compiler in particular, is not a full re-implementation of compilers, but is built on a compiler toolchain called LLVM. This allows Rust to focus on implementing its own syntax and features, while leaving most of the heavy lifting to the impressive suite of LLVM compiler tooling.

rustc -vV even tells you as much:

$ rustc +nightly -vV
rustc 1.46.0-nightly (8ac1525e0 2020-07-07)
binary: rustc
commit-hash: 8ac1525e091d3db28e67adcbbd6db1e1deaa37fb
commit-date: 2020-07-07
host: x86_64-unknown-linux-gnu
release: 1.46.0-nightly
LLVM version: 10.0

LLVM is a modern and very flexible compiler framework with a huge range of supported platforms and compile targets. The way this is achieved, is by compiling your own language into an abstract in-between representation called llvm-ir that you then feed to the llvm compiler. This can then be compiled to machine code for the requested target. As a result, Rust is one of the first languages to directly support compiling to wasm.

In addition, most release-level optimizations don't actually happen within the rust compiler but in the llvm framework. Though llvm is mostly hidden from sight, for cases such as ours, rust allows us to pass through various arguments to get more data to inspect. Swapping build with the specific rustc command, we can append compiler flags to the compiler after--. For our case we were interested in learning about the different steps taken after each optimization run so -- -C llvm-args=-print-after-all is added before piping the entire output into a file.

We quickly noticed that the output _is too big to work with, and running it in parallel on multiple threads resulted in a unparsable output. Adding -Z no-parallel-llvm fixes this but our example is still unwieldy to deal with. Fortunately, the random relabeling happens in the same funtion call everytime. Thus isolating the exact call results in a very thin test case for the compiler bug, too.

7. Digging into the llvm output

Looking again at the .wat and tracing back from the differing output we find it located in

(func $_ZN7trie_db9triedbmut18TrieDBMut$LT$L$GT$12commit_child17h1a851bf4aa72b1bdE (type 4) (param i32 i32 i32 i32)

In order to create a reproducible test, we need a version that tells us what the actual inputs use. Here, the compiler internals can help; by passing -Zsymbol-mangling-version=v0. As a result, we get a more comprehensive compiler symbol in our .wat

(func $_RINvNtCs2KrsVm9iLGa_4core3ptr13drop_in_placeINtNtCsfzX9CsLwTkO_7trie_db9triedbmut9TrieDBMutINtCs7x3GksGMAjA_7sp_trie6LayoutNtNtCs42nTExHBz75_10sp_runtime6traits11BlakeTwo256EEECsdbcsBhSPY2w_12node_runtime (type 3) (param i32)

which we can then pass to rustfilt (cargo install rustfilt) to make it human readable again:

$ rustfilt _RINvNtCs2KrsVm9iLGa_4core3ptr13drop_in_placeINtNtCsfzX9CsLwTkO_7trie_db9triedbmut9TrieDBMutINtCs7x3GksGMAjA_7sp_trie6LayoutNtNtCs42nTExHBz75_10sp_runtime6traits11BlakeTwo256EEECsdbcsBhSPY2w_12node_runtime
core::ptr::drop_in_place::<trie_db::triedbmut::TrieDBMut<sp_trie::Layout<sp_runtime::traits::BlakeTwo256>>>

Alrighty! This is specific enough for us to create a build, and have something we can analyze. Replacing our main lib.rs with a static reference and adding the relevant dependencies in theCargo.toml:

#![cfg_attr(not(feature = "std"), no_std)]

#[no_mangle] pub static FOO: unsafe fn(
    *mut trie_db::triedbmut::TrieDBMut<'static, 
        sp_trie::Layout<sp_runtime::traits::BlakeTwo256>,
    >,
) = core::ptr::drop_in_place;

We now have a short crate that triggers the bug in our code path.

Now, to analyzing the llvm output, we compile this with:

cargo rustc -p tiny-package --release --target=wasm32-unknown-unknown -- -C llvm-args=-print-after-all -Z no-parallel-llvm 2> llvm-log-1

With a clean example, we can now look at the llvm output and the diffs between two runs again, revealing the first change to be:

-  successors: %bb.55(0x80000000); %bb.55(100.00%)
+  successors: %bb.58(0x80000000); %bb.58(100.00%

As assumed the internal order of processing changes between runs. This happens in the step # *** IR Dump After WebAssembly Fix Irreducible Control Flow ***:. We find in the llvm code here. Generally speaking, this has to be a compiler bug, because from the name of it, this step is supposed to prevent exactly that problem we are experincing.

Once you've found a bug in an external repo, the first thing to do is see if the issue is already reported or patched. And indeed, we can find a commit to master, not yet released.

As expected, llvm also stores some of its own internal state in non-order-persistent ways (e.g. HashMaps with randomized keys). To ensure the order in which they are processed and yielded is deterministic, they are sorted before processing. Before this patch, under certain conditions, namely "fixing up a set of mutual loop entries", this wasn't reliably done. It appears that with our code we triggered this bug within the llvm-ir representation.

After patching a local llvm in rustc and doing multiple runs, we can confirm: this is the bug and this commit fixes it. Although the bug was probably present in older versions of the compiler, only a new code base did actually triggered the path that would lead to it.

8. Backporting the compiler fix

Though the fix was merged into llvm back in February, it wasn't yet part of llvm10 nor any of the 10.0.1 release candidates, but will probably be part of the upcoming llvm 11 release. Unfortunately, rust is rather slow in picking up and porting to the latest version of llvm. Regardless, the Rust Team is very open for backports to the llvm and these migrate rather quickly into the nightly version of rust, which we are most interested in. As a result, we will can get a fixed wasm32 nightlt compiler pretty soon.

As of the time of writing the backport patch has been accepted and merged and we are just waiting for rustc to update its submodule. 🤞

Credits: Gratitude to eddyb for their tremendous help, especially on the compiler part of things, knowing off and fiddling around the llvm args and pin down the bug in llvm ❤️!. Also a thanks to the Museums of Victoria for sharing their Arctic Expedition Photos for free for reuse on unsplash, which I used as the header picture.