Forem: Tim McNamara

Two trie implementations in Rust (one's super fast)

Tim McNamara — Fri, 31 Mar 2023 01:58:14 +0000

A trie is a data structure that enables very fast lookups, while taking up quite a small amount of space. Here's an implementation in Rust:

use std::collections::HashMap;

#[derive(Default, Debug)]
struct TrieNode {
    is_end_of_word: bool,
    children: HashMap<char, TrieNode>,
}

#[derive(Default, Debug)]
pub struct Trie {
    root: TrieNode,
}

impl Trie {
    pub fn new() -> Self {
        Trie {
            root: TrieNode::default(),
        }
    }

    pub fn insert(&mut self, word: &str) {
        let mut current_node = &mut self.root;

        for c in word.chars() {
            current_node = current_node.children.entry(c).or_default();
        }
        current_node.is_end_of_word = true;
    }

    pub fn contains(&self, word: &str) -> bool {
        let mut current_node = &self.root;

        for c in word.chars() {
            match current_node.children.get(&c) {
                Some(node) => current_node = node,
                None => return false,
            }
        }

        current_node.is_end_of_word
    }
}

fn main() {
    let mut trie = Trie::new();
    trie.insert("hello");
    trie.insert("hi");
    trie.insert("hey");
    trie.insert("world");

    println!("{trie:#?}");

    println!("hiiii? {}", trie.contains("hiiii"));
}

You can gain some extra speed by replacing the standard library's hash map implementation with fxhash. To do so, replace the first few lines with this:

use std::collections::HashMap;
use fxhash::FxBuildHasher;

type FxHashMap<K, V> = HashMap<K, V, FxBuildHasher>;

#[derive(Default)]
struct TrieNode {
    is_end_of_word: bool,
    children: FxHashMap<char, TrieNode>,
}

What's happening?

The standard library's std::collections::HashMap uses a hash function -- a function which takes an input and morphs it into an output of a fixed size -- that's designed to be cryptographically secure and general purpose at the expense of speed. Because we know that our keys will be the char type, which takes up 4 bytes, we can use a hash function that's more suited for short keys. (By the way, in case you were wondering, it probably still makes sense to use a hash function for char values, even though we could just use the bits' values directly as they're all a fixed sized. Because human language tends to use a very narrow spectrum of bit patterns within a char, and hash tables like keys to be well spread out, the hash function can spread the bits out for what is hopefully a net performance win.)

Create something beautiful this weekend! Write your first shader and put it on the web with WebGL

Tim McNamara — Sun, 19 Mar 2023 02:13:00 +0000

I've always wanted to create a "shader" -- a graphics program that works really fast (it runs on your GPU) -- but I've always been put off because they seemed really difficult.

Shaders come in two forms: fragment shaders and vertex shaders. Fragment shaders are what we care about here, because they're more useful for drawing. A fragment shader is a type of shader that processes individual fragments (pixels) on the screen. It is responsible for determining the color of each pixel in the final rendered image. GLSL is a C-like language used for writing shaders in OpenGL.

All of this complexity has kept me away for a long time. Today I managed to put that fear aside and create this - a fun dynamic gradient background:

Running the shader yourself..

.. in ShaderToy

ShaderToy is an interactive web playground for running shaders.



void mainImage(out vec4 fragColor, in vec2 fragCoord)
{
    // Normalized pixel coordinates (from 0 to 1)
    vec2 uv = fragCoord / iResolution.xy;

    // Time-based variables for smooth animation
    float t = iTime * 1.5;
    float t1 = sin(t) * 0.5 + 0.5;
    float t2 = cos(t) * 0.5 + 0.5;

    // Color components
    float r = sin(3.0 * uv.x + t1) * 0.5 + 0.5;
    float g = cos(3.0 * uv.y + t2) * 0.5 + 0.5;
    float b = sin(4.0 * (uv.x + uv.y) + t1 + t2) * 0.5 + 0.5;

    // Output the final color
    fragColor = vec4(r, g, b, 1.0);
}

To use this shader, follow these steps:

Go to https://www.shadertoy.com/new.
Replace the existing code in the "mainImage" function with the code provided above.
Click the "Play" button.

.. locally

If you want to learn how to use a shader in your own projects, you'll need to do a little more work to set things up.

The project has two files:

glsl.html - the main webpage
shader.frag - a fragment shader

glsl.html:



<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>GLSL/WebGL Shader Example</title>
    <meta name="author" content="Tim McNamara">
    <meta property=”og:url content=”https://github.com/timClicks/glsl-shader-intro” />
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <script type="text/javascript" src="https://rawgit.com/patriciogonzalezvivo/glslCanvas/master/dist/GlslCanvas.js"></script>
    <style>
        html, body {
          width:  100%;
          height: 100%;
          margin: 0;
        }
        canvas {
            display: block;
            width: 100%;
            height: 100%;
        }
    </style>
</head>
<body>
    <canvas class="glslCanvas" data-fragment-url="shader.frag"></canvas>
    <script>
        const canvas = document.querySelector('.glslCanvas');
        canvas.width = window.innerWidth;
        canvas.height = window.innerHeight;
        const sandbox = new GlslCanvas(canvas);
    </script>
</body>
</html>

shader.frag:



#ifdef GL_ES
precision mediump float;
#endif

uniform float u_time;
uniform vec2 u_resolution;

void mainImage(out vec4 fragColor, in vec2 fragCoord)
{
    // Normalized pixel coordinates (from 0 to 1)
    vec2 uv = fragCoord / u_resolution.xy;

    // Time-based variables for smooth animation
    float t = u_time * 1.5;
    float t1 = sin(t) * 0.5 + 0.5;
    float t2 = cos(t) * 0.5 + 0.5;

    // Color components
    float r = sin(2.0 * uv.x + t1) * 0.5 + 0.5;
    float g = cos(3.0 * uv.y + t2) * 0.5 + 0.5;
    float b = sin(4.0 * (uv.x + uv.y) + t1 + t2) * 0.5 + 0.5;

    // Output the final color
    fragColor = vec4(r, g, b, 1.0);
}

void main() {
    mainImage(gl_FragColor, gl_FragCoord.xy);
}

Note: the variables in WebGL are different than those available in ShaderToy. ShaderToy's iResolution becomes u_resolution and its iTime becomes u_time.

Explaining the code

The GLSL code in shader.frag is relatively short, but still fairly off-putting. Let's break it down.

Preprocessor

To start, we have a "Preprocessor directive". The compiler has stages, and one of the initial stages is called the "Preprocessor".



  #ifdef GL_ES
  precision mediump float;
  #endif

This part checks if the shader is running on OpenGL ES (Embedded Systems), a subset of OpenGL for mobile and embedded devices. If so, it sets the default floating-point precision to "medium." Precision indicates the accuracy and range of floating-point variables. "Medium" precision offers a balance between performance and accuracy.

Creating two "uniform" (global) variables



uniform float u_time;
uniform vec2 u_resolution;

Uniform variables are global variables that can be set from outside the shader, usually from the application code. In this case, u_time represents the elapsed time, and u_resolution represents the screen resolution as a 2D vector (width, height).

mainImage function



void mainImage(out vec4 fragColor, in vec2 fragCoord)

The mainImage function processes the fragment color (fragColor) based on the fragment coordinates (fragCoord). It takes an "output variable" fragColor of type vec4 rather than use a return value to set the color of the fragment (pixel) and an input variable fragCoord of type vec2 that describes the fragment's coordinates.

Normalize pixel coordinates



vec2 uv = fragCoord / u_resolution.xy;

This line translates the fragment's coordinates between absolute position and a relative position between 0 and 100%. I use the term normalized because the coordinates uv are independent from the device that is rendering the shader, whereas fragCoord is device-specific. The code calculates uv by dividing the fragment coordinates by the resolution. The uv coordinates will range from (0, 0) to (1, 1), representing the bottom-left and top-right corners of the screen, respectively.

Changing what's displayed over time



float t = u_time * 1.5;
float t1 = sin(t) * 0.5 + 0.5;
float t2 = cos(t) * 0.5 + 0.5;

These lines create time-based variables for smooth animation. The t variable scales the elapsed time (u_time), while t1 and t2 use sine and cosine functions to create smoothly changing values that oscillate between 0 and 1.

Changing the constant being multiplied with u_time changes how quickly the image changes. Adjusting how t1 and t2 behave will affect the cycle that produces the colors.

Calculate color components (red, green, blue)



float r = sin(2.0 * uv.x + t1) * 0.5 + 0.5;
float g = cos(3.0 * uv.y + t2) * 0.5 + 0.5;
float b = sin(4.0 * (uv.x + uv.y) + t1 + t2) * 0.5 + 0.5;

These lines calculate the red, green, and blue color components for each fragment using the time-based variables and the normalized pixel coordinates. The sine and cosine functions generate smoothly varying values, creating color gradients on the screen.

Set the pixel's color



fragColor = vec4(r, g, b, 1.0);

This line sets the output fragColor with the calculated color components (r, g, b) and an alpha (transparency) value of 1.0 (fully opaque).

Main function



void main() {
    mainImage(gl_FragColor, gl_FragCoord.xy);
}

The main function is the entry point of the shader. Its only job is to call the mainImage function that we've just chatted about. I've included mainImage to simplify refactoring and translating between your own HTML and ShaderToy's hosted environment.

Expanding the shader

You can further experiment with this shader by adjusting the parameters, such as the coefficients in the sine (sin) and cosine (cos) functions that produce color components, to create different effects.

Acknowledgments

This example makes use of the patriciogonzalezvivo/glslCanvas project, which makes it really easy to use a GLSL shader within the HTML tag.

patriciogonzalezvivo / glslCanvas

Simple tool to load GLSL shaders on HTML Canvas using WebGL

GlslCanvas is JavaScript Library that helps you easily load GLSL Fragment and Vertex Shaders into an HTML canvas. I have used this in my Book of Shaders and glslEditor.

How to use it?

There are different ways to do this. But first, make sure you are loading the latest version of GlslCanvas.js on your page by adding this line to your HTML:

<script type="text/javascript" src="https://rawgit.com/patriciogonzalezvivo/glslCanvas/master/dist/GlslCanvas.js"></script>

or if you are using npm package manager on your console do:

npm install glslCanvas

The easy way

Create a canvas element in your HTML.
Add the class name glslCanvas to the canvas.
Assign it a shader
- through a url using the attribute data-fragment-url
- or directly writing your code inside the data-fragment attribute

<canvas class="glslCanvas" data-fragment-url="shader.frag" width="500" height="500"></

…

View on GitHub

Creating a priority queue with a custom sort order using a binary heap in Rust

Tim McNamara — Fri, 28 Oct 2022 09:13:00 +0000

I want to create a personal web crawler. As I download each page, I collect a new list of URLs. To increase the likelihood that I am downloading the most important pages first, I want to keep the list of URLs to visit sorted by length (shorter URLs are more likely to be closer to the front page). That presents a problem though, because I'm also adding URLs.

A naïve list (Vec<T> in Rust), won't be very efficient. After every batch of inserts, I would need to re-sort the list. Wouldn't it be good if there were a data structure that could maintain the sort order itself? Yes! It's called a binary heap.

// Detect dark theme var iframe = document.getElementById('tweet-1585905108029960193-847'); if (document.body.className.includes('dark-theme')) { iframe.src = "https://platform.twitter.com/embed/Tweet.html?id=1585905108029960193&theme=dark" }

Rust's standard library provides a binary heap implementation, as std::collections::BinaryHeap. In my case, I want to sort a list of url::Url. By default, they are sorted in alphabetic order.

use url::Url;
use std::collections::BinaryHeap;

fn main() {
    let raw_urls = vec![
        "https://www.youtube.com/watch?v=ywskA8CoulM",
        "https://tim.mcnamara.nz/",
        "https://github.com/rust-lang/rust/issues?labels=E-easy&state=open",
    ];

    let mut urls = BinaryHeap::new();
    for url in raw_urls {
        urls.push(Url::parse(url).unwrap());
    }

    while let Some(url) = urls.pop() {
        println!("{:?}", url.as_str());
    }
}

This prints our URLs, but in alphabetic order:

"https://www.youtube.com/watch?v=ywskA8CoulM"
"https://tim.mcnamara.nz/"
"https://github.com/rust-lang/rust/issues?labels=E-easy&state=open"

Unfortunately, it's a little bit complicated to ask BinaryHeap to use a custom sort order. To change the default, I create a new type that wraps one as ShortestFirst(Url). Then, I implement Ord and PartialOrd traits.

use url::Url;
use std::collections::BinaryHeap;

#[derive(PartialEq, Eq, , Debug)]
struct ShortestFirst(Url);

impl PartialOrd for ShortestFirst {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for ShortestFirst {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let left = (other.0).as_str().len();
        let right = (self.0).as_str().len();

        left.cmp(&right)
    }
}

fn main() {
    let raw_urls = vec![
        "https://www.youtube.com/watch?v=ywskA8CoulM",
        "https://tim.mcnamara.nz/",
        "https://github.com/rust-lang/rust/issues?labels=E-easy&state=open",
    ];

    let mut urls = BinaryHeap::new();
    for url in raw_urls {
        urls.push(ShortestFirst(Url::parse(url).unwrap()));
    }

    while let Some(ShortestFirst(url)) = urls.pop() {
        println!("{:?}", url.as_str());
    }
}

This prints the URLs, in the order we wanted:

"https://tim.mcnamara.nz/"
"https://www.youtube.com/watch?v=ywskA8CoulM"
"https://github.com/rust-lang/rust/issues?labels=E-easy&state=open"

Principles of the 1x programmer

Tim McNamara — Tue, 09 Nov 2021 22:31:36 +0000

Software is a team sport

Even if you’re coding for yourself, you’re still coding for a team. Your future self will not have the same cognitive context that you do currently. Therefore, you should always code in a way that respects the people who are following you.

One of the best introductions to this type of socially minded programming is called Building Software Together (freely licensed under CC-BY-NC 4.0) by Greg Wilson and contributors.

Our aim is to teach you how to be a compassionate programmer: one who cares as much about the well-being of their colleagues and users as they do about their own. This focus is not entirely altruistic—everything you do to help others also helps your future self—but now that we all know how much harm software can do, we hope you’ll be interested in some practical idealism.

Learn through mimicry

Find the best software written in your programming language of choice. Usually, the language’s standard library is a good place to start. Look for patterns. Try to consider how you would implement things.

Small children learn by copying others. Why shouldn’t adults?

Being a computer scientist is less useful than you might think**

Synthesis is essence of software engineering, whereas abstraction is the essence of computer science. Your job as a software developer will be to synthesise something new from composable pieces. What you create should be simple to understand and extend.

You are unlikely to implement sophisticated data structures and algorithms.

I don’t agree with everything that pg writes, but this struck out.

99.5% of programming consists of gluing together calls to library functions.

The time to fix things is now

Your team isn’t going to have fewer priorities next week or next month. There will not be an opportunity to the wholesale rewrite that the code base deserves. The only way to improve a code base is incrementally.

I learned this through John Ousterhout’s book, A Philosophy of Software Design. The overall suggestion that I took away from the book is that if your team is struggling with a spaghetti code base, its members should be investing about 10-20% of their total development time cleaning it up.

You’re paid to build

If you think that you’re employed to write software, then you’ve not thought hard enough.

You’re employed to make money – or save money – for someone. And the way to do that is probably through programming.

The phrase is terrible, but it’s worth repeating anyway. Make sure that you “add value”.

This matters because sometimes – perhaps often – working on the boring thing that no one wants to work on is really the thing that you should be doing.

Simplicity really helps

We all want to write simple software, as hard as that is. Ideally, your code should be simple enough so that a junior programmer who doesn’t like you can understand it.

Ironically, simple code probably has a shorter lifespan than complex code. Complex and difficult code remains fixed because people are afraid to change it. Complex code is very hard to test. And without regression tests, we don’t know if we’ve broken behaviour. So it becomes brittle.

API beats algorithm

Syntax matters. One of the lessons from the success of Kenneth Reith’s requests package — which completely took over from the standard library’s own implementation of making web requests — is that the (public) API is more important than every millisecond that you save from implementing the perfect algorithm. Users care about convenience. Convenient code is easy to write, easy to read and easy to maintain.However, it’s also understand what comprises your “Porcelain API” and your “Plumbing API”

Other people make mistakes

The majority of us are better drivers than average. I’m sure the same is true for programming.Brains are imperfect.

It’s impossible for you to assess your own skill level.

If you want adoption, software is just the start

If you care about adoption, there’s lots of work to do once the code has been written. That is, unless you’re Fabrice Bellard, I guess.

This, to me, is the ultimate reason why being a 1x programmer (even in a professional setting) can be sufficient. You might be able to contribute to other areas that someone who is focused purely on the code is not able (or, more commonly, unwilling) to do. 10x programmers care about the code. Everything else is secondary.

Users care about themselves. To them, they need to be the primary priority. This rift causes a problem when open source maintainers decide that their users are indeed secondary. But that might be the theme of a future post.

Let me know what you agree with. Hopefully it isn't everything!

How type conversions work in Rust

Tim McNamara — Thu, 12 Aug 2021 10:23:33 +0000

Background

Rust is a strongly-typed programming language with static typing. It’s also quite pedantic. For example, it’s impossible to compare two integers with each other if they are of the different types. To avoid any extra work at runtime, such as reflection, Rust requires us to be precise with the types that our programs use.

This small program won't compile:

// https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4a0ad78e651e74bc52d986037eb21b0c
fn main() {
    let a: i32 = 10;
    let b: u32 = 10;
    println!("{}", a + b);
}

Instead creating a program that prints 20 to the console, we receive an error message with two error codes:

error[E0308]: mismatched types
 --> src/main.rs:4:22
  |
4 |   println!("{}", a + b); 
  |                      ^ expected `i32`, found `u32`

error[E0277]: cannot add `u32` to `i32`
 --> src/main.rs:4:20
  |
4 |   println!("{}", a + b); 
  |                    ^ no implementation for `i32 + u32`
  |
  = help: the trait `Add<u32>` is not implemented for `i32`

For the curious, here is some information about how to interpret those error codes. The first (E0308) is caused because the addition operator (+) expects the same type for both of its operands. The second error (E0277) is subtly different. It’s saying that the trait bounds (the interface) are not satisfied. Addition is provided by the std::ops::Add trait and has been implicitly parameterized to i32 type by its left operand.

Explicitly changing types with the as keyword

The most common method you’ll encounter to convert one type to another is via the as keyword. It’s particularly common when converting between usize (which may be 32 or 64 bits wide, depending on CPU architecture) and fixed-width integers, such as u32.

One option that's available to us for fixing the earlier example is to promote both values to the type i64, which can represent all possible values within the u32 and i32 types:

// https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=b55bd9b4447b9b01d4f98649ed54edf6
fn main() {
    let a: i32 = 10;
    let b: u32 = 10;
    println!("{}", a as i64 + b as i64);
}

If the value cannot fit within the bounds of the type being converted to — a negative number cannot be represented by an unsigned integer type, for example — then the program will exhibit very strange behaviour (see the "Rustnomicon" reference at the bottom of the article for details). We'll work through other options for handling cases where type conversions might fail later in the series.

The as keyword asks Rust to do the minimal amount of work possible to treat a value of one type as a value of another. Very often, such as converting between integer types of equal width, the internal representation does not change. This efficiency comes at a cost.

As is only available for primitive types. When you require conversions of types that you’ve designed yourself, you need to use the std::convert::{From,Into} traits.

The Rust reference provides a good overview of the details in the type cast expression page. The Rustnomicon also has a detailed section about casting between data types.

Posts to come in this series. Please follow me to get notified when they are posted!

Using the From and Into traits
Using the From and Into traits
Hidden type conversion via the Deref trait
Trait objects
Downcasting

Thanks to @vorfeedcanal for comments on a previous version of this post.

My book on Rust is available on Amazon!

Tim McNamara — Wed, 11 Aug 2021 03:57:38 +0000

It may seem like a small milestone, but I'm really happy to share that my book, Rust in Action, is being sent around the world from Amazon.

https://smile.amazon.com/Rust-Action-Tim-McNamara/dp/1617294551/

I also spent some time creating a website for the book last night:

https://www.rustinaction.com/

The source code for the book's examples is available here:

rust-in-action / code

Source code for the book Rust in Action

Welcome to Rust in Action source code

This source code repository is a companion to the Rust in Action book by Tim McNamara, published by Manning Publications.

Supporting the book

Most book sales are generated on the basis of trusted referrals and recommendations Please add your rating or review on Goodreads, Amazon or perhaps even your own blog.

If you haven't got it yet, here are some links so that you can buy Rust in Action for yourself:

direct from the publisher (recommended)
Amazon, or one of its subsidiaries like Book Depository
Books-a-Million
Barnes & Noble
perhaps even your local bookshop via indiebound!

Providing feedback

The issue tracker is open, and is useful for minor bug reports.

Please don't submit pull requests. They are not accepted due to copyright.

Please use https://livebook.manning.com/books/rust-in-action to submit issues for anything larger, especially if you want to discuss the book's text…

View on GitHub

9 advantages of programming in Rust

Tim McNamara — Tue, 27 Jul 2021 03:56:20 +0000

So, Edward Snowden has endorsed the Rust programming language. Google, Microsoft, AWS, Mozilla, Facebook and many other companies are funding its development. Why? I can’t say for sure, but here are a few of the reasons that I like the language so much that I wrote a book about it:

Safety for your users

Programming in Rust provides safety guarantees that are not available to programing languages that have safety features bolted on. And unlike languages that provide an equivalent level of safety, Rust is unique in that it does not impose runtime costs.

Cheaper running costs

Other things being equal, the application that uses less memory is cheaper to run. You can run more applications on fewer compute nodes, or you can run your application within a smaller compute instance. An application that can easily scale to serve the next 1,000 users means you’ll spend less money on development also.

Faster debugging

The Rust compiler is a coach, not simply a pedantic critic. Your experience with the helpfulness of Rust’s compiler output will make you frustrated with what you encounter from other error messages.

Speed that’s available to ordinary programmers

Most programmers are not 10x programmers. Because of its safety safeguards, Rust programmers who do not consider themselves expert are free more willing to experiment — free from the fear that they have introduced security holes or stability issues.

Multi-disciplinary community

Rust is almost no one’s first programming language. Nor are there many Rust programmers who code exclusively in Rust. Instead, its community is drawn from programmers from many fields. This means that the Rust ecosystem benefits from many ideas that have been incubated and refined, where-ever they first popped up.

Wide applicability

Rust is labelled as a “systems programming language”, but don’t allow that to cloud your thinking. Many domains are well suited for Rust development. To draw an analogy, Rust has high dynamic range.

Thoughtful abstractions

Rust’s design process is highly collaborative. It takes years for an idea to become a stable Rust feature, partially because there are often multiple iterations of thoughtful design.

Easy packaging and code-reuse

Incorporating third-party libraries into your project involves adding a single line to a metadata file. No fighting with multiple interpreter versions, incompatible dependencies, strange linker problems, or an arcane module system.

An empowerment mindset

The Rust community’s overarching goal is to empower. As you take the time to learn Rust and become productive with it, you’ll find yourself believing in yourself.

Tim McNamara is the author of Rust in Action. He is active on Twitter and hosts tutorials on YouTube.

Things I learned about creating a C API for my Rust crate by making every mistake about creating a C API

Tim McNamara — Tue, 06 Jul 2021 10:22:54 +0000

tl;dr

Here are my tips:

C programmers want to allocate and free their own memory. They don't want a string provided for them. They want you to write to an array that they control.
You need to "box" local variables if you want them to out-live the function.
Don't model your API after libc. In particular, you should avoid global state.

Background

A few weeks ago, I stumbled upon a way for creating unique identifiers that are still sortable: ULIDs. ULIDs are very similar to UUIDs are typically used: as random identifiers [footnote: you should ensure that you're using UUIDv4 if you're using them this way, otherwise your IDs are not random].

ULIDs have a neat trick trick though, newer IDs are higher than older IDs. IDs generated within the same millisecond are random, but if the interval between them is longer than that then you'll be able to compare them.

Naturally, I thought that I should try and implement them. And I did. In fact, some benchmarking indicates that I may have created the fastest Rust implementation: it takes my computer roughly 28 nanoseconds to generate an identifier. That's 35,000 ULIDs per millisecond.

Then I thought about exposing my Rust code as a C library. libulid. And then I discovered that I knew almost nothing about writing a C library.

Lessons

Here are a few things that I needed to fix before getting libulid ready.

Global state

One of the first things that I did was to take inspiration from the rand() function from libc. rand() requires a seed() function to be called that initializes a global random seed.

My initial API involved calling ulid_seed() and then ulid_new() later on. This created two issues. First it was horrible to work with. Secondly, it wasn't thread safe.

It turns out that the thread safety problem is well documented.

The function rand() is not reentrant, since it uses hidden state that is modified on each call. This might just be the seed to be used by the next call, or it might be something more elaborate. In order to get reproducible behavior in a threaded application, this state must be made explicit; this can be done using the reentrant function rand_r().

Why did I use functionality that is not thread safe? Well, I was working with the rust crate and didn't check the upstream libc documentation.

I was somewhat embarrassed, although very relieved, that a contributor to my code that raised the thread safety issue. Thanks Jonas!.

To avoid the issue, I ask users of the library to initialize a ulid_ctx object that stores the random seed and pass a pointer to it when creating a new ULID.

_t suffix is reserved

At one stage, I added a _t suffix to all of the types that I created. It turns out that this convention is reserved by POSIX for its types.

Let callers manage their own memory

One of the things that caused quite a few problems was attempting to create raw pointers in Rust, then hand them across the FFI boundary.

I did this to match the ULID spec, which specifies that the API to generate a ULID should look like this:

ulid()

In Rust, this is a fine thing to do. But in C, you have a decision to make: where will the memory be allocated and freed? Will it be the responsibility of the caller or the library?

I spent several days trying to figure out how to do something very simple: allocate an array in Rust on the heap, pass a pointer to that array to C, then free the memory later in Rust. I eventually gave up on getting all of the pieces work together, because it seemed like C programmers would like to do something else entirely. They want to manage their own memory.

Acknowledgements

Many thanks to the #include Discord server for offering lots of advice and encouragement during this process.

Thanks also to Jonas for providing lots of patches!

Calling a private Rust function from outside of its module

Tim McNamara — Sat, 06 Mar 2021 22:10:44 +0000

Private functions should be, well, private. Let's learn how to break that! Understanding what's happening will provide you insight into how programming languages are implemented.

This party trick is attributed to LordMZTE. When I was discussing raw pointer manipulation on a live stream a few days' ago, they sent me a Rust playground link to explore. What I discovered was code doing something that I didn’t think was possible: call a function that’s private from outside of a module.

When the code from the example below is executed, it prints an interesting message:

Private function called!

Take a look at the source and see if you can figure out what’s happening:

#![allow(dead_code)]

pub mod foo {
    pub fn public() {
        println!("Public function called");
        private();   
    }
    fn private() {
        println!("Private function called!");
    }
}

pub fn main() {
    // foo::public();

    unsafe {
        std::mem::transmute::<usize fn> ()>((foo::public as usize) + 64)();
    }
}

So, how does it work? And where does 64 come from?

Video Recording

If you prefer videos - you can watch a recording of the stream.

Explanation

The magic happens here:

std::mem::transmute::<usize fn> ()>((foo::public as usize) + 64)();

This line asks Rust to treat the memory address of the foo::public function as an unsigned integer, add 64 to that value, then treat that higher address as a function and call it.

Let’s break it apart to figure out how it works.

Functions are represented in memory as an array of bytes just like data. Unlike data, the CPU interprets them as code. To call the foo::private function from outside of the foo module, we need to find out where it is laid out in memory. The Rust compiler happens to lay functions right next to each other. So to find the start of foo::private, we can start with the location of foo::public and add its length.

Now to reveal a sleight of hand in the original example. I removed a call to the dbg!() macro, which I had executed in a previous execution:

// finding the length of foo::public()

#![allow(dead_code)]

pub mod foo {
    pub fn public() {
        println!("Public function called");
        private();   
    }
    pub fn private() { // temporarily mark foo::private as public
        println!("Private function called!");
    }
}

pub fn main() {
    dbg!((foo::private as usize) - (foo::public as usize));
}

If we run this new version in the playground, we’ll receive the length printed to the console:

[src/main.rs:16] (foo::private as usize) - (foo::public as usize) = 64

With the length handy, we now know what fn foo::private refers to. As an implementation detail, the fn keyword creates a function pointer. Function pointers are pointers that point to executable memory.

To treat a function pointer as an integer, the code uses <fn> as usize. To treat a usize as a memory address though, we need more powerful tools. The std::mem::transmute() function is that tool. It is probably the most unsafe constructs in the Rust language. It instructs Rust to re-interpret data types. In our case, std::mem::transmute::<usize fn> ()> asks Rust to interpret a usize as a function pointer that takes 0 arguments and returns the “unit type” (()).

Discussion

Is being able to call private functions a security hole?

No, not really. The program needs to be able to call private functions. We only knew which memory address to “call” because we had access to the source code. This enabled us to mark foo::private as public and deduce the length of foo::public.

That said, it is possible to scan a program’s address space looking for executable chunks. That’s exactly what viruses do. But that doesn’t mean that Rust programs can arbitrarily violate their own privacy guards.

What does “private” mean in the context of a programming language?

In some sense, privacy doesn’t exist. There is no guard watching modules to make sure that they’re not trespassing other modules. Privacy, at least within Rust as it’s currently implemented, is a compile-time construct. We can’t look inside the executable binary to find sections marked as private.

That said, programming language designers have the ability to define whatever compile-time they want. For example, the operating system has the ability to mark specific memory pages as illegal (look up “guard pages” for extra info). Attempts to access these specially marked sections of memory indicate a runtime fault and the process will be terminated. It would be possible to add one of these pages between private and public members of a module, but that would incur a memory overhead.

What’s in those 64 bytes?

If you’re interested in what is happening in those 64 bytes, then you can ask the playground to print out the assembly generated by rustc. Look for the playground::foo::public section:

playground::foo::public:
        subq        $56, %rsp
        leaq        .L__unnamed_2(%rip), %rax
        leaq        .L__unnamed_3(%rip), %rcx
        xorl        %edx, %edx
        movl        %edx, %r8d
        leaq        8(%rsp), %rdi
        movq        %rax, %rsi
        movl        $1, %edx
        callq        core::fmt::Arguments::new_v1
        leaq        8(%rsp), %rdi
        callq        *std::io::stdio::_print@GOTPCREL(%rip)
        callq        playground::foo::private
        addq        $56, %rsp
        retq

Here is foo::public again. Can you align the source code its assembly?

    pub fn public() {
        println!("Public function called");
        private();   
    }

Here are some hints for the curious. Many of the the opcodes are suffixed with q meaning quad, or l for long. Strings are passed to functions as memory addresses and the println! macro desugars to calls to functions within core::fmt.

Docker for the late majority

Tim McNamara — Fri, 26 Feb 2021 00:36:34 +0000

This is a guide for people who would like a brief introduction to Docker and are too afraid to ask for one. I get it. Everyone around you already seems to know what they’re talking about. Looking ignorant is no fun.

What is a container?

A container is a strengthened process. Processes each have their own memory address space, all processes share the file system and the network. Containers are processes that have also been delegated with their own isolated file system and network.

If you think of isolation of concurrent applications as a spectrum. As you move from left-to-right in this table, isolation increases:

Thread	Process	Container
CPU time	CPU time	CPU time
	Memory	Memory
		Network
		File system
		…

Each step rightwards includes steps to the left. Containers contain 1 or more processes. Each process contains 1 or more threads.

One thing to note is that these abstractions are not created equally. Processes and containers are abstractions provided by the operating system. Threads are abstractions that are provided by the CPU.

What is a “cgroup”? And what is a “namespace”?

In Linux, containers are implemented with a kernel feature called namespaces. Namespaces can have their access to resources such as the system’s memory restricted via _control _groups (“cgroups”). The docker run command provides --cpus, --memory, --ulimit and other parameters to enable you to define the cgroup restrictions.

In addition to cgroups, Linux also enables you to restrict which syscalls are permitted by any processes running inside a container through secure computing mode (“seccomp” and its “secomp-bpf” extension) . This could be used, for example, to prevent a container exposed to the Internet from ever writing to file. In Docker, this feature is exposed as --cap-drop and --security-opt parameters to docker run.

What is an “image”?

Applications running in containers managed by Docker have an added trick: they carry their data along with them. Docker images, or more precisely, container images, are .tar files that contain an application and anything the application needs to run.

What is a “Docker container"?

A Docker container is a fusion of the two concepts we’ve discussed: kernel namespaces and container image. Once that container image is created, it can be run by any docker command on any (relatively recent) Linux kernel. docker takes the image, creates a kernel namespace, applies the cgroup and seccomp-bpf policies, creates any required file system and networking resources, then the ENTRYPOINT defined in the Dockerfile.

Why did Docker take off?

Containers were moderately successful before Docker. But Docker solved something else apart from isolation. They were lightweight. The predominant alternative at the time Docker emerged was to run virtual machines to isolate development environment. So, every project required its own entire operating system, along with requisite disk space and memory.

Moreover, virtual machine images were too bulky to send from a laptop to a production server. While it’s possible to create container images weighing in at over 1GB, it’s uncommon. Virtual machines were the opposite. It was possible to create VM images that were less than 1GB, but it was uncommon.

Docker provided some things that set it apart:

an easy-to-use, developer-centric CLI that simplified namespaces, cgroups, seccomp and container images
creating Dockerfile, an easy-to-use, developer-centric format for specifying how to build container images
hosting Docker Hub, an easy-to-use, developer-centric image hosting service

This ease-of-use looked quite attractive when compared against virtual machines, which were slow to boot and resource intensive to run.

Appendix: is Docker dead?

If you’re in the late majority and are just coming to grips with the terminology, I have an admission to make: you’re probably going to need to learn some more language.

Despite the frequency of the word “Docker container”, very few containers are run directly by docker these days. Not even Docker manages containers anymore. Most containers will be managed by a different container runtime environment, such as containerd or CRI-O.

Depending on your audience, you may wish to change your language to use industry-neutral terminology:

replace the term “Docker container” with “container”
replace the term ”Docker image” with “container image”. Or even better, use the term “OCI image”
replace “docker” with the name of the actual container runtime, such as containerd or CRI-O

Spend your novelty budget on Rust

Tim McNamara — Tue, 16 Jun 2020 01:30:55 +0000

Starting a new project is exciting. You get to try the new database, the new framework, the new architecture, the new everything. But every new tool introduces a risk. And those risks compound. That’s why I believe that you should choose boring technology for most of your stack and only allow a meagre novelty budget.

Rust is a programming language that has now proven that it deserves your attention. Software heavyweights, including Microsoft, Google and AWS all use Rust. Hundreds of smaller companies are also taking advantage of it.

If you’re in the lucky position of being able to decide which tools to use, consider Rust.

Side projects make good candidates, especially if you are hitting memory constraints. Don’t rewrite your core application in a programming language that you haven’t used before. Using Rust for projects off the critical path provides time for learning, stumbling and revision. Even if the Rust prototype is not put into production, I believe that you will become a stronger software engineer. The compiler will teach you about object lifetime management and modelling concurrent applications.

There are many stories of applications that are now impossible to maintain because someone decided that the latest NoSQL database, framework, or language would be perfect for the new project. That person has now left and no one knows how to keep the application alive. Luckily, Rust is a programming language for the next 40 years.

Deadbeef? Just say no. Let's learn to build a small Rust app to find out what words can you spell with the letters A-F

Tim McNamara — Thu, 07 Nov 2019 18:39:08 +0000

I'm always really irritated when I see "babe" and "deadbeef" (the worst) in code examples that use hexadecimal numbers. It's actually not that funny.

You know you can do the dab in hex, right?

Photo: User:Gokudabbing / Wikipedia

What else is there? Here's a selection (the full list is at the bottom of the post).

Nouns

ace (perhaps that should be an adjective, it's time for a 90s linguistic revival)
bead
bee
cab
dad
fad

Adjectives

decaf
deaf
dead
deed
faded

Verbs

add
cede
fade
dab
feed

How do we find them?

Here's the full source code. If you're new to Rust, keep reading&mdashlI explain what's going on below.

use std::fs::File;
use std::io::{BufReader, BufRead};

fn main() -> std::io::Result<()> {
    let f = File::open("/usr/share/dict/words")?;
    let reader = BufReader::new(f);

    'lines: for line in reader.lines() {
        let word = line.unwrap();
        for byte in word.bytes() {
            match byte {
                b'A' | b'B' | b'C' | b'D' | b'E' | b'F' |
                b'a' | b'b' | b'c' | b'd' | b'e' | b'f' => continue,
                _ => continue 'lines,
            }
        }

        if word.len() > 2 {
            println!("{}", word);
        }
    };

    Ok(())
}

Let's break the example down. We start with imports.

use std::fs::File;
use std::io::{BufReader, BufRead};

We're bringing some of the standard library into local scope. That gives us the ability to open files. File can open them. A BufReader can read them efficiently. We also need to import BufReader's "traits" along with it to avoid name clashes. Traits define methods, and we can sort of pick and mix the methods that we want for any given type.

Hint: If you haven't encountered the term trait before, think of it as an Abstract Base Class or an interface. If you're new to programming and haven't heard of those two either, that's ok. It's not essential to know what a trait is for the rest of the post.

fn main() -> std::io::Result<()> {
    // ...
    Ok(())
}

The std::io::Result<()> type is a bit crazy, sorry about that. It's an indicator that something might fail under the hood—like the hard drive might break or we could trigger a permissions error—and Rust should be prepared for that.

Adding Ok(()) at the end is our main() function saying "everything went fine". We are returning Ok with a () type, which has the fun name "unit". It is a placeholder value.

let f = File::open("/usr/share/dict/words")?;

I run Ubuntu, which includes a list of valid-ish words as a plain text file. We open that up. If we do end up triggering a permissions error, or the file is deleted, the ? at the end will propagate the error and immediately exit the main() function.

let reader = BufReader::new(f);

We create a BufReader that knows how to read from File objects efficiently. It's called BufReader because it has contains an internal in-memory buffer that can and then ask it to inject anything it reads into the string we create next.

Now comes the best bits, or why I love Rust:

    'lines: for line in reader.lines() {
        let word = line.unwrap();
        for byte in word.bytes() {
            match byte {
                b'A' | b'B' | b'C' | b'D' | b'E' | b'F' |
                b'a' | b'b' | b'c' | b'd' | b'e' | b'f' => continue,
                _ => continue 'lines,
            }
        }

        if word.len() > 2 {
            println!("{}", word);
        }
    };

This chunk of code is a bit of a showoff. We define a named loop, 'lines that can be used later to immediately abort from a word that contains a character outside of our limited alphabet. And then it uses the match syntax to elegantly match bytes that we care about. (The b prefix on all of those literals indicates to Rust that they should be treated as 8-bit integers, not as characters or strings - for the details check a Rust book)

Compiling the code

Let's see the result!

First let's build a new project:

$ cargo new hexwords
     Created binary (application) `hexwords` package

$ tree hexwords
hexwords
├── Cargo.toml
└── src
    └── main.rs

Now copy the source code into the main.rs file. Once that's done, we can run it.

$ cd hexwords

$ cargo run -q
Abe
Ada
BBB
Bede
Beebe
Dacca
Dada
Dec
Decca
Dee
Edda
Feb
abed
accede
acceded
ace
aced
add
added
baa
baaed
babe
bad
bade
bead
beaded
bed
bedded
bee
beef
beefed
cab
cabbed
cad
cede
ceded
dab
dabbed
dad
dead
deaf
deb
decade
decaf
deed
deeded
deface
defaced
ebb
ebbed
efface
effaced
facade
face
faced
fad
fade
faded
fed
fee
feed

Voilà!

Full source code here:

https://github.com/timClicks/hexwords