DEV Community: Sven Kanoldt

What is a CIDR trie and how can it help you?

Sven Kanoldt — Tue, 28 May 2024 00:00:00 +0000

In this post, we will explore the CIDR trie data structure and how it can help you manage IP addresses and subnets in your Rust project.

As usual in this series, we will take a tiny piece of Rust out of a real project and explain it in a very practical way.

Problem

Imagine that your Rust service should only be available from specific IP addresses. This may be desirable for limiting access to certain geographical regions (similar to geo-fencing) or other services you control.

This service should not be slowed down by the need to check every incoming request's IP address against a list of allowed IP addresses.

Let's have a look at the size of the geo-whois-asn-country-ipv4.csv file that only contains ipv4 addresses: it contains 243K entries and is about 7.13 MB in size. Simply checking every incoming request against this list with Vec::contains is obviously too inefficient.

Furthermore, the problem is that we don't have the list of all single IP addresses that we can search, but we have a list of IP ranges, for example:

from 1.10.10.0 to 1.10.10.255 belongs to IN/India
from 1.5.0.0 to 1.5.255.255 belongs to JP/Japan

and so on.

Now when a client connects to our service we have to check a single IP to those given ranges and decide if the client is allowed to connect or not.

Solution

Let's first introduce a slightly different format for those IP ranges, the CIDR notation. CIDR stands for Classless Inter-Domain Routing, and it is a compact way to represent an IP address range. For example:

1.10.10.0 to 1.10.10.255 will be represented as 1.10.10.0/24
1.5.0.0 to 1.5.255.255 will be represented as 1.5.0.0/16

So the suffix /24 or /16 tells us how many leading bits of the IP address are fixed. Keep in mind that a full ipv4 address has 32 bits. That means if 24 bits are fixed, the remaining 8 bits are variable, and as we will see later, not important to us.

For the post we will assume we already have an efficient way of converting the range format above to the CIDR notation. We now want to find a data structure that is well-suited to searching for the country of a given IP address.

We ultimately want to use the data structure in our service like this:

// usage example
let mut country_ip_list = CidrCountryMap::new();
country_ip_list.insert("1.10.10.0/24", "IN");
country_ip_list.insert("1.5.0.0/16", "JP");

// search for the country of the given IP address
assert_eq!(country_ip_list.search("1.10.10.1"), Some("IN"));
assert_eq!(country_ip_list.search("1.10.10.22"), Some("IN"));
assert_eq!(country_ip_list.search("1.5.0.1"), Some("JP"));

// not in the list
assert_eq!(country_ip_list.search("10.1.1.1"), None);

Note: this code is pseudo code. In production we would likely not use strings for the IP addresses, but the std::net::Ipv4Addr type of the std lib.

The `CidrCountryMap`

One data structure we could base the CidrCountryMap on is a specialized trie. In it's most generic form, it can be used to search based on the prefix of an element (e.g. the first few letters of a string).

But let's first look at what a trie is and it's use case. According to wikipedia, a trie is also called digital tree or prefix tree. To quote:

Unlike a binary search tree, nodes in the trie do not store their associated key. Instead, a node's position in the trie defines the key with which it is associated. This distributes the value of each key across the data structure, and means that not every node necessarily has an associated value.

So the gist is, we would not store full values on nodes, but the data (that we want to store) will distribute on several nodes in the tree on a path. A path starting at the root (usally visualized on the top) leading down to a leaf (last not in the tree) or a terminal node.

This data distribution on paths comes with some very neat properties: the time it takes to search for an item, depends only on the key length, not on the amount of stored items. The same is true for inserting items.

The CIDR trie specifics

In the CIDR trie we represent a bit of the IP address as a node on the path. The complete path from the root to a (terminal) leaf node therefore represents the fixed bits of the IP address (without the trailing masked bits). The leaf node furthermore stores the country code associated with the IP address range.

For example let's look at the IP range 1.10.10.0/24 and their single bytes:

1  -> 00000001
10 -> 00001010
10 -> 00001010
0  -> 00000000

and the /24 suffix tells us that the first 24 bits are the ones we are taking into account. That means we don't store the last 8 bits of the IP range.

So we can build a trie just as we would read those binary numbers, that looks like this (showing only the first 2 bytes):

In the illustration we can see path that the first 16 bit of the IP address would span. The nodes of the 3rd byte are not shown, to keep the illustration simple. But just imagine a continued path down to the leaf node. The leaf node would contain the country code and also would be marked as a terminal node.

That means when we want to search for the country of the IP address, we must just process the bits of the given IP address and follow the path in the trie. If we reach a terminal node, we have found the country code.

That is the basic idea of the CIDR trie. Let's implement this trie in Rust now.

Implementation

Let's introduce the CidrCountryMap struct that holds the trie and the methods to insert and search for a given IP address.

#[derive(Default)]
pub struct CidrCountryMap {
    root: Node,
}

The Node struct represents a single node in the trie. It holds the country code, the child nodes and it keeps the information if it's a terminal node in the whole trie or not.

#[derive(Default)]
struct Node {
    is_terminal: bool,
    children: [Option<Box<Node>>; 2],
    value: Option<String>,
}

Note: we're using a fixed size array of for 2 Nodes (children: [Option<Box<Node>>;2]) to represent the child nodes. This is a common pattern in Rust to represent a tree structure. This avoids further allocations when inserting nodes. Just in case, could also use a Vec instead of an array. Also this is specific to a binary trie, e.g. for storing arbitrary ASCII characters we would have to (pre-)allocate 256 children (one per character). In that case it would be better to use a HashMap insteaf of a fixed size array.

We have to use Box because Rust does not allow recursive types that are not on the heap.

Let's implement the CidrCountryMap insert method.

impl CidrCountryMap {
    pub fn insert(&mut self, cidr: &str, data: impl Into<String>) -> Result<()> {
        let (cidr, take_bits) = cidr
            .split_once('/')
            .ok_or(CidrCountryMapError::SplitError)?;
        let mut take_bits = take_bits
            .parse::<usize>()
            .map_err(|err| CidrCountryMapError::ParseIntError(err))?;

        let mut current_node = &mut self.root;
        for byte in cidr.split('.').flat_map(|octet| octet.parse::<u8>()) {
            for bi in (0..8).rev() {
                if take_bits == 0 {
                    break;
                }
                let index = (byte >> bi) & 1;
                current_node = current_node.children[index as usize].get_or_insert(Box::default());
                take_bits -= 1;
            }
        }

        current_node.is_terminal = true;
        current_node.value = Some(data.into());

        Ok(())
    }}

it splits the CIDR notation into the IP address and the number of bits
it iterates over the bytes of the IP address and the bits of the CIDR notation
it processes the bits from left to right by using bit shifting and masking (byte >> bi) & 1 (bi is the amount of bits we shift to the right)
- first we shift by 7 bits, then by 6 bits, then by 5 bits and so on
- after shifting the bits to the right we select the right-most bit with the mask 1
- by doing so we iterate through the bits of the byte from left to right
- this gives either true or false (1 or 0) and we use this as an index to access the child array
we take or insert a new node in the trie for each bit
after all current_node is the leaf node and we set the country code and mark it as terminal

Note: You might wonder about the the use of Result<()> and CidrCountryMapError. I kept it out on purpose to keep the code simple and not use .unwrap(). You can find the full code in playground link on the References section.

The search method is quite similar to the insert method. We just have to iterate over the bits of the IP address and follow the path in the trie.

impl CidrCountryMap {
    pub fn search(&self, cidr: &str) -> Option<&str> {
        let mut current_node = &self.root;
        for byte in cidr.split('.').flat_map(|octet| octet.parse::<u8>()) {
            for bi in (0..8).rev() {
                let index = byte >> bi & 0b1;

                if let Some(node) = &current_node.children[index as usize] {
                    current_node = node;
                } else if current_node.is_terminal {
                    break;
                } else {
                    return None;
                }
            }
        }
        current_node.value.as_deref()
    }
}

we break the loop if we reach a terminal node
we return None if we reach a node that has no children
we return the country code of the end node, the leaf node, if we reach the end of the IP address

Conclusion

Searching an IP Address in the CIDR trie is done in O(k) time complexity. Where k is the number of bits in the IP Adress to look up, so O(32). It may also take less than O(k) time when the IP is not present in the trie.

The CIDR trie is a very efficient data structure to search for IP addresses in a given range.

Note: For other more complex use cases it might be better to roll the trie_rs crate, which provides a more generic trie implementation. However, I want to encourage you to mind a clean and small dependency list in your projects. Be aware that every external dependency comes with the cost of maintenance and less control over security and stability.

Improvement ideas:

we could store the whole trie Nodes in a single Vec to avoid multiple allocations and to improve cache locality
we could compress the trie by combining nodes that have only one child, this approach is then called to be a Radix Trie
we could store the country code in a separate vector and use the index as a reference in the trie nodes, to save memory and to avoid storing the country code multiple times

Special thanks to Jonas and David for providing feedback and improvement suggestions to this post 🙏 🦀 🚀

References

What is the matter with `AsRef`?

Sven Kanoldt — Tue, 09 Aug 2022 15:33:11 +0000

the AsRef trait is everywhere in the std lib and very handy. However, the benefit using it is maybe not too obvious. But read on, and you will see some useful examples and where to apply it.

This is the 2nd post on the series "practical rust bites" that shows very tiny pieces of rust taken out of practical real projects. It aims to illustrate only one rust idiom or concept at a time with very practical examples.

Background

AsRef can be found in the std::convert module and is used
for cheap reference-to-reference conversion.

It's a very essential trait widely used in the std library and helps with seamless reference conversions from one type to another.
Often it is at play, and you do not even realize it is there.

Example: `String` or `&str`

Did you ever have had a function where you wanted to accept a string as a parameter?
You might then also have asked yourself should you accept a string reference (as in &str) or an owned string (as in String)?

So you would have something like this in mind:

fn take_a_str(some: &str) {}

and the other one:

fn take_a_string(some: String) {}

So why not have both?!

At this very point AsRef<str> comes in very handy,
because both types str and String implement this trait.

fn take_a_str(some: impl AsRef<str>) {
    let some = some.as_ref();
    println!("{some}");
}

fn main() {
    take_a_str("str");
    take_a_str("String".to_string());

    // also `&String` is supported:
    let string_ref = "StringRef".to_string();
    take_a_str(&string_ref);
}

check out the code on the playground

As you can see this version of take_a_str accepts a type that just implements AsRef<str>.

By doing so some: impl AsRef<str> does not make any concrete assumptions on the type that is provided.
Instead, it just insists that any given type only implements this trait.

Example: wrapper type

In this example we want to focus on how can you implement AsRef yourself for any arbitrary struct.

Let's look at this tiny program:

pub struct Envelope {
    letter: String
}

fn main() {
    let a_letter = Envelope { 
        letter: "a poem".to_string() 
    };

    println!("this is a letter: {}", &a_letter);
}

But of course you'd say now, well, it does not implement Display and so does the rust compiler agree with you:

error[E0277]: `Envelope` doesn't implement `std::fmt::Display`
  --> src/main.rs:10:38
   |
10 |     println!("this is a letter: {}", &a_letter);
   |                                      ^^^^^^^^^ `Envelope` cannot be formatted with the default formatter
   |
   = help: the trait `std::fmt::Display` is not implemented for `Envelope`
   = note: in format strings you may be able to use `{:?}` (or {:#?} for pretty-print) instead
   = note: this error originates in the macro `$crate::format_args_nl` (in Nightly builds, run with -Z macro-backtrace for more info)

For more information about this error, try `rustc --explain E0277`.

But we ignore Display for now and focus on another use case. That is we want to access the inner value of Envelope.

Solving this problem with implementing AsRef<str> we would do the following:

impl AsRef<str> for Envelope {
    fn as_ref(&self) -> &str {
        // here we up-call to the `AsRef<str>` implementation for String
        self.letter.as_ref()
    }
}

and with this we need just one little adjustment:

fn main() {
    let a_letter = Envelope {
        letter: "a poem".to_string()
    };

    println!("this is a letter: {}", a_letter.as_ref());
}

Now the rust compiler does not complain anymore.

Again, of course it would be appropriate to implement Display for this very println! case, but the point is here that we would want to access the inner data as reference.

check out the full example on the playground

Example: a composed type

I have to admit, take this example with a grain of salt. It's very likely that this kind of usage
would lead to problems with bigger structs. So as a rule of thumb if a struct has more than 2 fields, better not go down this path.

let's look at a simple struct that represents a weight:

struct Weight {
    weight: f32,
    unit: String
}

impl Weight {
    /// Weight in Tons that is 157.47 stones 
    pub fn from_tons(weight: f32) -> Self {
        Self { weight, unit: "t".to_string() }
    }

    /// Weight in Stones
    pub fn from_stones(weight: f32) -> Self {
        Self { weight, unit: "st".to_string() }
    }
}

As you can see we have not given pub fields and also no getter accessor functions.

So how we can actually get our hand on the data inside?

You've guessed it, AsRef is our friend here as well.

impl AsRef<str> for Weight {
    fn as_ref(&self) -> &str {
        &self.unit
    }
}

impl AsRef<f32> for Weight {
    fn as_ref(&self) -> &f32 {
        &self.weight
    }
}

So here we use the AsRef trait for the types f32 and str to get access to the weight and unit inside the struct.

fn main() {
    let a_ton = Weight::from_tons(1.3);

    let tons: &f32 = a_ton.as_ref();
    let unit: &str = a_ton.as_ref();

    println!("a weight of {tons} {unit}");
}

you could also skip the variable bindings and make it less verbose:

fn main() {
    let a_ton = Weight::from_tons(1.3);

    println!(
        "a weight of {} {}",
        a_ton.as_ref() as &f32,
        a_ton.as_ref() as &str
    );
}

checkout the full example on the playground

Wrap up

AsRef is a very handy tool and if you go through the standard library, you will find it implemented for a lot of types.
By this a lot of reference types become interchangeable and this increases the overall ergonomics a lot.

As you also have seen how AsRef can be useful to get access to inner data of structs without having to provide accessory methods or public fields.

A very related function to get the inner value of a struct, but as value (not as reference) is the .into_inner().
As you can see it is used a lot in the std lib, but it is not bound to a trait. So this is more of a convention: Whenever you need to consume a struct and unfold the inner wrapped type, then .into_inner() is the common schema to go for.

Versions used for this post:

$ cargo --version && rustc --version
cargo 1.61.0 (a028ae42f 2022-04-29)
rustc 1.61.0 (fe5b13d68 2022-05-18)

To receive updates about new blog post and other rust related news you can follow me on twitter.

🎉 🚀 🍺 New release of Terminal Recorder - t-rec

Sven Kanoldt — Mon, 12 Oct 2020 16:00:15 +0000

Blazingly fast terminal recorder that generates animated gif images for the web written in rust for MacOS.

Demo

Features

Screenshotting your terminal with 4 frames per second (every 250ms)
Generates high quality small sized animated gif images
Build-In idle frames detection and optimization (for super fluid presentations)
Runs (only) on MacOS
Uses native efficient APIs
Runs without any cloud service and entirely offline
No issues with terminal sizes larger than 80x24
No issues with fonts or colors
No issues with curses based programs
No issues with escape sequences
No record and replay - just one simple command to rule them all
Hidden feature: Record every window you want
Written in Rust 🦀

Install

NOTE for now t-rec depends on imagemagick, but this is going to change soon.

❯ brew install imagemagick
❯ cargo install -f t-rec

Hidden Gems

You can record not only the terminal but also every other window. There 2 ways to do so:

1) abuse the env var TERM_PROGRAM like this:

for example lets record a window 'Google Chrome'
make sure chrome is running and visible on screen

❯ TERM_PROGRAM="google chrome" t-rec
Frame cache dir: "/var/folders/m8/084p1v0x4770rpwpkrgl5b6h0000gn/T/trec-74728.rUxBx3ohGiQ2"
Press Ctrl+D to end recording
Recording Window: "Google Chrome 2"

this is how it looks then:

2) use the env var WINDOWID like this:

for example let's record a VSCode window
figure out the window id program, and make it
make sure the window is visible on screen
set the variable and run t-rec

❯ t-rec --ls-win | grep -i code
Code | 27600

# set the WINDOWID variable and run t-rec
❯ WINDOWID=27600 t-rec

Frame cache dir: "/var/folders/m8/084p1v0x4770rpwpkrgl5b6h0000gn/T/trec-77862.BMYiHNRWqv9Y"
Press Ctrl+D to end recording

this is how it looks then:

Contribute

Testers on different Apple hardware needed. Also, exotic shell setups are very interesting for testing.

To contribute to t-rec you can either checkout existing issues labeled with good first issue or open a new issue and describe your problem.
Also every PR is welcome. Support for Linux and Windows needs to be done.

License

GNU GPL v3 license
Copyright 2020 © Sven Assmann.

🎉 🚀 🍺 The new release v0.4.1 of stegano-rs is out

Sven Kanoldt — Tue, 22 Sep 2020 23:46:51 +0000

The new major release contains the following:

✨ Features

WAV Audio media file support - by sassman, pull/6

stegano has now support for input and output wav audio files (.wav). This means that hiding secret messages and files are now **not* only possible for png image media files but also wav audio files in the same way. For example like this:

❯ stegano hide \
  -i resources/plain/carrier-audio.wav \
  -d resources/secrets/Blah.txt \          
     resources/secrets/Blah-2.txt \
  -o secret.wav

Arch Linux packages - by orhun, pull/10

stegano can now be installed from available AUR packages using an AUR helper. For example like this:

❯ yay -S stegano

🛠️ Maintenance

Update stegano-core to latest dependencies - by sassman, pull/2

check it out on crates.io

reference tweet

Rust Munich Meetup #3

Sven Kanoldt — Wed, 26 Aug 2020 21:13:38 +0000

Yesterday was the third online meetup of the rust munich group, just in case you missed it, no worries it's available on youtube. I recommend giving it a watch.

Things you can learn / expect

tons of details about binary formats
how steganography (hiding data) in binaries works
history of the image crate
tons of design details in the image crate to coop with all the different formats and platform differences

There are also some side topics to learn about

importance of code formatting, especially in OSS and to get it right as early as possible
the super powers of fuzzing

Thanks to our host Bernhard and all the speakers for their amazing talks.

You can now also follow us on twitter to not miss the next one.

container less cloud computing - wascc

Sven Kanoldt — Tue, 09 Jun 2020 08:11:47 +0000

If you are curious about a container less secure server side future you need to watch this talk.

At time index 19min it's getting real. Kevin Hoffman demonstrates how hot swap of modules is possible, means deployment with zero downtime, not only of code but also of attached resources like key value stores etc.

This is super exciting! What do you think about this possible future?

Read more about waSCC.

steganography cli in rust - architecture

Sven Kanoldt — Sat, 30 May 2020 16:21:56 +0000

Little preview of my talk about steganography in rust, a little hobby project of mine, at the #rust #meetup #munich on 3rd of June. Fully remote.

You can also join on meetup.com

UPDATE 2020-06-02:
The Livestream will be hosted on youtube

stegano-cli on crates.io

rust macro rules in practice

Sven Kanoldt — Fri, 22 May 2020 22:55:34 +0000

This is the first post on my new series "practical rust bites" that shows very tiny pieces of rust, taken out of practical real projects. So this article will be super short, easy to follow and hopefully helpful to find your way into the rust eco system.

TL;DR

macro rules are very nice to keep your code DRY wherever you can't or don't want to use functions.
e.g. having several println! statements in your code that repeat with a lot of similarity, or when you want to wrap or intercept your code with some action before and after your code.

In this post we explore a profiling macro, called prof that is used like this:

let mut total_time = Duration::new(0, 0);
total_time += prof! {
    file.write_all(buffer)?;
};

The code examples are based on a little program that I wrote recently that does a write to disk benchmark.

Of course you can also checkout the amazing rust macro rules documentation to learn more about rust macro rules.

Background

You can checkout the tool I mentioned above, super simple disk benchmark on GitHub or on crates.io. It's nothing fancy and only solves my very own issue of benchmarking the writing speed of a hard disk.

I started with no macros at all, then I found myself repeating on 2 things.

The first was printing out metrics like:

Total time                                29598 ms
Min write time                             2516 ms
[...]

where the width between the unit and the label is fixed, so that they align nicely on the console.

The second was profiling how long an operation takes, for instance writing a buffer to file on disk or writing data into a buffer. Data are written in chunks in a loop, so I wanted to avoid to profile the time of the whole loop, but rather profile only the write operation itself, to be more accurate on the numbers (some sort of).

So the code doing the profiling looks essentially like this:

let mut total_time = Duration::new(0, 0);
let start = Instant::now();

// doing the thing

total_time += start.elapsed();

I did not want to have the overhead of a function call, so I took it as an opportunity to explore the macro rule system of rust. Both cases are suited to explore macro rules further, but we want to focus on the second one here.

Macro in rust

A macro in rust is safe, the compiler is pretty strict about the syntax and all type and ownership check uphold there as well and there is no way of messing this up as you can in c/c++. To give an example of messing things up in c/c++:

#define MAX(a,b) ((a) > (b) ? a : b)

then calling c = MAX(a++, b); causes some unpleasant side effects of double incrementing. Since the preprocessor just does a search and replace job, and a++ is pasted 2 times as it is executed 2 times. Bad luck!

In rust this would not have happened.

The most popular macro that you might already know and probably did use is println! it just simplifies the usage of formatting output that ends with a newline and is send to stdout.
Macros can also call functions and other macros inside.

So a macro rule has the following anatomy:

macro_rules! name_of_the_macro {
    ($param1:expr, $param2:expr) => {
        // here you go with your function call or macro call here or whatever logic
    };
}

this macro above takes 2 arguments, both can be an expression on they own. Isn't it simple?

An Example

Let's first imagine how our future code should look like, starting from here:

let mut total_time = Duration::new(0, 0);
let start = Instant::now();

// file and buffer is declared somewhere above..
file.write_all(buffer)?;

total_time += start.elapsed();

we want something like:

let mut total_time = Duration::new(0, 0);
total_time += prof! {
    file.write_all(buffer)?;
};

so we want the macro called prof!, like profiling and it should have no arguments but a block where things can be done inside. Last it will return the Duration it took for executing the block.

This is how it looks:

macro_rules! prof {
    ($something:expr;) => {
        {
            let start = Instant::now();
            $something;
            start.elapsed()
        }
    };
}

Alright, let's walk that through line by line:

prof is the name of the macro
$something describes one parameter called something, :expr declares the parameter to be a rust expression, followed by a literal ;
opens a block { - the first { belongs to the macro, the second { actually starts a block
we store the start time - regular rust code
$something; means the expression we give into the macro will be placed here
start.elapsed() regular rust code, without the ; means we will return this from the block, that's like the return value of the macro.
} closing the block of the generated rust code

We can verify the result and inspect what the compiler will generate out of it. Unfortunately it requires rust unstable to be installed.

rustup run nightly cargo rustc -- -Z unstable-options --pretty=expanded | less

This will produce a lot of code, very interesting to dig through that. But what we are actually looking for is the following:

let mut total_time = Duration::new(0, 0);
total_time += {
    let start = Instant::now();
    file.write_all(buffer)?;
    start.elapsed()
};

so as you can see the macro expands to a block, that contains the code from the macro with the stuff we have given to the macro in between. Eventually it returns the duration start.elapsed().

Bonus Track

So far so good, but let's have a look at yet another use case of the macro

for _ in 0..TOTAL_SIZE_MB / BUF_SIZE_MB {
    write_time += prof! {
        file.write_all(buffer)?;
        std::io::stdout().flush()?;
    };
    print!(".");
}

So here we have 2 expressions in side the macro body. Unfortunately the compiler will yell at us with this:

error: no rules expected the token `std`
   --> src/main.rs:179:17
    |
44  | macro_rules! prof {
    | ----------------- when calling this macro
...
179 |                 std::io::stdout().flush()?;
    |                 ^^^ no rules expected this token in macro call

Clearly the second expression gives us this troubles. The good thing is that we can have quantifier in the left hand side of the matching tree in the macro:

-    ($($something:expr)) => {
+    ($something:expr; $($otherthings:expr;)*) => {

Here we extend the macro by $($otherthings:expr;)* that is basically the same as the first argument, just with the difference * modifies, similar to a RegEx, the the expression to be present 0 or n times. Now we can hand more expressions over to the macro, but yet we don't use them. For this we need to change the content of the macro:

             $something;
+            $(
+                $otherthings;
+            )*

At $otherthings; will be the expression placed, and $()* will expand the expression as often as expressions given to the macro.

As a whole the macro looks now like:

macro_rules! prof {
    ($something:expr; $($otherthings:expr;)*) => {
        {
            let start = Instant::now();
            $something;
            $(
                $otherthings;
            )*
            start.elapsed()
        }
    };
}

Let's verify again how this macro would expand:

    write_time +=
        {
            let start = Instant::now();
            file.write_all(buffer)?;
            std::io::stdout().flush()?;
            start.elapsed()
        };

Simplification

Alright, now let's have a final look if we can simplify that macro further because the first parameter and the second are basically identically. So let's just get rid of the second one, and apply the repeat modifier to the first one.

macro_rules! prof {
    ($($something:expr;)+) => {
        {
            let start = Instant::now();
            $(
                $something;
            )*
            start.elapsed()
        }
    };
}

$($something:expr;)+ has now the modifier + that says once or multiple times the whole expression terminated by a ;.
In the macro body we now only expand the one and only parameter $($something;)*.

The only drawback is that expressions that are not terminated by a ; like a for loop for instance, now must be terminated by a ;

let buffer_time = prof! {
    for i in 0..BUF_SIZE {
        buffer[i] = rng.gen();
    }
}

let buffer_time = prof! {
    for i in 0..BUF_SIZE {
        buffer[i] = rng.gen();
    };
}

Versions used for this post

$ cargo --version && rustc --version
cargo 1.43.0 (2cbe9048e 2020-05-03)
rustc 1.43.1 (8d69840ab 2020-05-04)

Please don't forget to share your feedback, give a 👍, follow me on twitter and most importantly share your learnings and your struggles while learning rust.

Time spend on writing CI configurations

Sven Kanoldt — Sun, 17 May 2020 14:25:34 +0000

How much time, at the beginning and summed up overall did you spend on writing your ci configuration? Be it for github actions or Travis CI or even Jenkins?

Super Simple Disk Benchmark written in rust

Sven Kanoldt — Thu, 07 May 2020 21:52:28 +0000

Today I discovered simple disk benchmark that is written in C and I wanted to give a very minimal version of it a try in rust. So here I'am reporting of my new crate and command line tool ssd-benchmark. It is so super simple you cannot do anything wrong. Give it a try.

Purpose of life

This tool has just one single purpose, it measures the writing performance of your hard disk on macOS and Linux. More precisely spoken of the disk under your CWD.

It used random data from rand crate and writes first sequentially chunks of 8MB until a total 1GB is written. It measures writing time and throughput.

After that it writes this random data 8 times again on disk and measures the average writing times and throughput for this.

Quick Start

Install

To install the ssd-benchmark tool, you just need to run

cargo install --force ssd-benchmark

(--force just makes it update to the latest version if it's already installed)

to verify if the installation went through, you can run ssd-benchmark that should output similar to

$HOME/.cargo/bin/ssd-benchmark

Usage

$ ssd-benchmark

###             Super Simple Disk Benchmark              ###
## Star me on https://github.com/sassman/ssd-benchmark-rs ##

Filling buffer with 8 MB random data...
Initilisation of buffer done               4890 ms

Starting benchmark...

Perform sequential writing of total 1024 MB in 8 MB chunks
................................................................................................................................

Total time                                 2522 ms
Throughput                               512.00 MB/s

Perform 8 write cycles of 1024 MB
................................................................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................

Total time                                29598 ms
Min write time                             2516 ms
Max write time                             4934 ms
Range write time                           2418 ms
Average write time μ                       3699 ms
Standard deviation σ                        801 ms

Min throughput                           207.54 MB/s
Max throughput                           407.00 MB/s
Average throughput Ø                     276.83 MB/s
Standard deviation σ                      64.76 MB/s

The great thing is, there are no parameters or options.

Missing something?

If you miss a feature file an issue on github and don't forget to star the repo.

Thanks for reading and don't miss out to give feedback :)

Used versions:

$ rustc --version
rustc 1.43.0 (4fb7144ed 2020-04-20)
$ cargo --version
cargo 1.43.0 (3532cf738 2020-03-17)

Originally published on my blog

little rust starter hint series: lifetimes made easy

Sven Kanoldt — Sun, 03 May 2020 15:07:32 +0000

As usual, I want to share with you an awesome online-book to learn rust in a very problem centric way. This book focuses on the problem of implementing a linked list, which is a very essential data structure, and a fundamental lesson in computer science and programming. It's for instance also a very popular exam exercise at universities in c++ programming.

While the problem of a linked list is basic, it does not mean it is trivial to implement especially in a language that is new and, in this case, that is memory safe. So why is that? Well, read the book than you'll know 😁.

All right, to keep that post very focused to the topic of lifetimes, I'll pick one example from the problem of a linked list - very specifically the iteration of items. What I mean with iteration of items is, that we want to be able to loop over the list and get every item until there are no more items. But more importantly, we want the list to remain intact as it was before we started to iterate. So we don't want to consume the list. Pretty much like:

#[test]
fn loop_over_vec() {
    // creating a Vec<i32>
    let v = vec![1, 2, 3, 4, 5];

    // looping over all items
    for i in v.iter() {
        // print the item to stdout
        println!("{}", i);
    }

    // printing the length of the Vector (should be 5)
    println!("{}", v.len());
}

just with our list implementation instead of Vec.

Ok, how is this connected with lifetimes?

Glad, you asked. Let me introduce few little data structures first, that would help to make the connection: a Node, a Link, and the List itself.

Note: for the sake of simplicity I'll not use a generic list but a simple list of integers (i32).

pub struct Node {
    next: Link, // the link to the next item or to None
    data: i32,  // the actual data item
}

// Option is used because the Link might be 'empty', means there is no item.
pub type Link = Option<Box<Node>>;

pub struct List {
    head: Link,
}

The structs should be easy to read. Just in case you wonder about type Link = Option<Box<Node>>, it is called a type alias and just renames the rust Option type to our use case. You might have seen it in c/c++ as a typedef statement. And in case you wonder about the mysterious Box: imagine it as a very literally box that surrounds a Node (the details doesn't matter for lifetimes).

Let's see if the compiler agrees with that:

#[cfg(test)]
mod test {
    use super::*;

    #[test]
    fn list() {
        let last_item = Node {
            next: Link::None,
            data: 2,
        };
        let first_item = Node {
            next: Some(Box::new(last_item)),
            data: 1,
        };

        let mut list = List {
            head: Some(Box::new(first_item)),
        };
    }
}

It compiles, nice. Well, it's not very handy to use that list, but as said, we focus on lifetimes. So let's move on and implement the Iterator trait for this list. Well not directly for the List, but a helper Iter that allows us to operate on the list items.

pub struct Iter {
    next: Option<&Node>,  // has a reference to the Node, not Node by value
}

// implementing the Iterator trait for the helper Iter
impl Iterator for Iter {
    type Item = &i32;     // has a reference to the data of the Node
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node); // What?
            &node.data  //
        })
    }
}

// obtain the helper Iter from our list
impl List {
    pub fn iter(&self) -> Iter {
        Iter {
            next: self.head.as_ref().map(|node| &**node), // again?
        }
    }
}

So, we got the Iter that has the next node or None in case we are done or empty. We obtain the Iter from the List by calling iter - ok that was simple. When we call next on Iter an item is returned and the next node of the list is set to it's next property. By that we are moving from a to z until we encounter None.

Ok, but what is that |node| &**node? So 2 things here: The |node| states that this is a closure. If you know a bit of ruby, then that feels like home. And the other &**node just means we dereference (*) the node (because node is a reference to a Box that holds the actual Node), then we dereference again (this time we unbox), and then we take the reference to that node and return it.

Ok, let's move on and compile: 🧨

error[E0106]: missing lifetime specifier
  --> src/list_for_article.rs:22:18
   |
22 |     next: Option<&Node>,
   |                  ^ expected named lifetime parameter
   |
help: consider introducing a named lifetime parameter
   |
21 | pub struct Iter<'a> {
22 |     next: Option<&'a Node>,
   |

error[E0106]: missing lifetime specifier
  --> src/list_for_article.rs:40:17
   |
40 |     type Item = &i32;
   |                 ^ expected named lifetime parameter
   |
help: consider introducing a named lifetime parameter
   |
40 |     type Item<'a> = &'a i32;
   |              ^^^^   ^^^

So we encounter 2 issues:

in line 22, where we want to store a reference to the Node as the next node in Iter
in line 40, where we want to return a reference to the data of the node, not a copy of it!

The compiler wants us here to specify the lifetime of the Node reference and the node's data reference.

When are lifetimes required?

There are 3 types of variables in rust:

a value like: let a = 1;
a reference to a value like: &a
a mutable reference to a value like: &mut a

Let's put that into the context of structures: our struct Iter contains an Option to a reference of Node. So that reference lives in Iter, but the actual value of that reference lives in List. You can think of a lifetime as a hidden information that exists in every block, and when you want to use references to a value, you need to explicitly pass that information from the block where the value lives to the place where the reference will live. For Iter that looks like:

pub struct Iter<'a> {
    next: Option<&'a Node>,
}

First we mark the struct itself using the generics notation <>, however, this time a lifetime ' called a is provided instead of a type. Together that looks like <'a>. You can call it whatever you like, only 'static is reserved for the lifetime of the whole program.

Second, we mark the field next to be of type Option<&'a Node>. So to say, the lifetime is passed into the reference from the block where it is created in:

impl List {
    pub fn iter(&self) -> Iter {
        // here the lifetime of the list itself is passed over too the Iter
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }
}

That implies, that the Iter from above cannot live longer than the list where it came from. Essentially, that is very logical - of course you cannot hold an iterator to a node of a list that is gone. The lifetime notation just makes it more explicit that there is a connection between the two structs.

The Invisible

There is this helpful feature of lifetime elision that allows the programmer to hide that lifetimes basically everywhere. Otherwise every variable or function would need to have it written out. That would be very painful. So in fact the List::iter method looks like the following:

impl List {
    pub fn iter<'a>(&'a self) -> Iter<'a> {
        Iter {
            next: self.head.as_ref().map(|node| &**node),
        }
    }
}

There it is even more explicit, that so to say, the lifetime of the reference to self is the same as the one of Iter.

Does the compiler know, that the lifetime of self and Iter are the same if you don't explicitly write them?

Let's check out that little change:

impl List {
    pub fn iter<'y, 'z>(&'y self, other: &'z List) -> Iter {
        Iter {
            next: other.head.as_ref().map(|node| &**node),
        }
    }
}

We add a second parameter of the same type List but with a different lifetime 'z and still keep omitting the lifetime of Iter.

Let's compile and see if the compiler get's it right:

error[E0623]: lifetime mismatch
  --> src/list_for_article.rs:36:9
   |
32 |       pub fn iter<'y, 'z>(&'y self, other: &'z List) -> Iter {
   |                                            --------     ----
   |                                            |
   |                                            this parameter and the return type are declared with different lifetimes...
...
36 | /         Iter {
37 | |             next: other.head.as_ref().map(|node| &**node),
38 | |         }
   | |_________^ ...but data from `other` is returned here

Well in that case, the compiler doesn't know what is the right lifetime to use, so we have to be explicit about our intentions that we want the lifetime of other to be used for Iter:

pub fn iter<'z, 'y>(&'y self, other: &'z List) -> Iter<'z> {
    Iter {
        next: other.head.as_ref().map(|node| &**node),
    }
}

and it compiles just fine.

Back to the Iterator

There was the other error about the lifetime of the Iterator's item that we did not yet fix:

impl<'a> Iterator for Iter<'a> {
    type Item = &'a i32;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.data
        })
    }
}

We make here as well explicit that lifetime of Iter is the same as the one of the item. Here, the name 'a is not the same 'a as we used before in List - the 2 are not connected with each other. However there is this, so to say, chain of passing the lifetime from the List to the Iter to the Item of the iterator. They all live together and happily ever after.

Final test

#[test]
fn list() {
    let last_item = Node {
        next: Link::None,
        data: 2,
    };
    let first_item = Node {
        next: Some(Box::new(last_item)),
        data: 1,
    };

    let mut list = List {
        head: Some(Box::new(first_item)),
    };

    for x in list.iter() {
        println!("{}", x);
    }

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&1));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), None);
}

Wrapping it up

Lifetimes are present in rust everytime and everywhere, we normally just don't see them and often don't need to see them. Mainly, when we deal with references that are owned by some other piece of code, then we have to be explicit about where they live.

You can find the full code example as a gist on github.

Thanks for reading and don't miss out to give feedback :)

Let me know, if that was helpful for you and if there are other concepts of rust that appear confusing or not easy to grasp.

Used versions:

$ rustc --version
rustc 1.43.0 (4fb7144ed 2020-04-20)
$ cargo --version
cargo 1.43.0 (3532cf738 2020-03-17)

Originally published on my blog

little rust starter hint series: Polymorphism and Traits

Sven Kanoldt — Thu, 05 Sep 2019 22:16:09 +0000

Today we going to explore Polymorphism and how that is actually doable in Rust.
For those that have not done any OOP language yet, Polymorphism is just a fancy term for behaving or being polymorph. For example a instance of something can also be or behave as something else. In Java, you would use interfaces to declare some behaviour that can be implemented by a class. So one class can implement one or many interfaces. In rust there are only structs no classes and traits that act as interfaces. As simple as that.

the problem statement

We want to implement a very basic hexdump tool that either accepts a file as argument or reads from stdin if that file is not provided.

for instance usable like this

hexdump README.md
0000000 23 20 48 65 78 64 75 6d 70 0a 0a 23 23 20 55 73
0000010 61 67 65 0a 0a 60 60 60 62 61 73 68 0a 68 65 78
0000020 64 75 6d 70 20 52 45 41 44 4d 45 2e 6d 64 0a 0a
0000030 60 60 60 0a

or without a file

hexdump
foo bar bak^D
0000000 66 6f 6f 20 62 61 72 20 62 61 6b 0a

the basics

Q: How to open a file
A: File::open(file)

Q: How to read from a file
A: BufReader::new(File::open(file))

Q: How to read from stdin
A: stdin().lock()

explanation

So it seems that stdin().lock() and BufReader::new() seems to have something in common that. The both allow to read bytes from them. Well, we come to this in a moment. Let's dump the full code for now:

use std::env;
use std::fs::File;
use std::io::prelude::*;
use std::io::stdin;
use std::io::BufReader;

fn main() -> std::io::Result<()> {
    let args: Vec<String> = env::args().collect();

    match args.get(1) {
        Some(file) => read_and_dump(BufReader::new(File::open(file)?)),
        None => read_and_dump(stdin().lock()),
        //      ^--- this function will be implemented later on, don't worry
    }
    Ok(())
}

the trait `BufRead`

So the thing that both (stdin().lock() and BufReader::new()) have in common, the both implement the trait BufRead
at the declaration we can see pub trait BufRead: Read that means that the BufRead extends Read by some more methods.

the naive approach

Perfect so let's now implement the missing method from above and hand over the instance that implements the BufRead

fn read_and_dump(r: BufRead) {
    for (i, b) in r.bytes().enumerate() {
        print_line_no_once(i);    // <-- we'll come to that later
        print_byte(b.unwrap());   // <-- we'll come to that later
    }
    print!("\n");
}

Cool, let's ask the compiler how he likes it..

cargo build --release
   Compiling hexdump v0.1.0
warning: trait objects without an explicit `dyn` are deprecated
  --> src/main.rs:17:21
   |
17 | fn read_and_dump(r: BufRead) {
   |                     ^^^^^^^ help: use `dyn`: `dyn BufRead`
   |
   = note: #[warn(bare_trait_objects)] on by default

[...]

error[E0277]: the size for values of type `(dyn std::io::BufRead + 'static)` cannot be known at compilation time
  --> src/main.rs:17:18
   |
17 | fn read_and_dump(r: BufRead) {
   |                  ^ doesn't have a size known at compile-time
   |
   = help: the trait `std::marker::Sized` is not implemented for `(dyn std::io::BufRead + 'static)`
   = note: to learn more, visit <https://doc.rust-lang.org/book/ch19-04-advanced-types.html#dynamically-sized-types-and-the-sized-trait>
   = note: all local variables must have a statically known size
   = help: unsized locals are gated as an unstable feature

well, that would be too easy.
It took me actually a bit time to gasp the problem, I read the docs and not got much further until I realized that traits should not be used as direct types but rather as "marker".

To explain what I mean with "marker" let's checkout the next iteration

Version 1: the impl on anonymous type

fn read_and_dump(r: impl BufRead) {
    for (i, b) in r.bytes().enumerate() {
        print_line_no_once(i);
        print_byte(b.unwrap());
    }
    print!("\n");
}

So here we not name any type and just say that whatever type we provide it will implement the trait BufRead. And by doing so the compiler is perfectly fine with everything.

Version 2: generic short hand

I was curious if generics are not as well capable of solving this. Just with the difference that the compiler might be able to do further optimizations.

fn read_and_dump<T: BufRead>(r: T) {
    for (i, b) in r.bytes().enumerate() {
        print_line_no_once(i);
        print_byte(b.unwrap());
    }
    print!("\n");
}

so in <> we specify a type T that implements BufRead that is called a bound generic in rust.

Version 3: generic verbose

When you implement traits you will see that syntax quite often, so it is worth to mentioning the where syntax

fn read_and_dump<T>(r: T)
where
    T: BufRead
{
    for (i, b) in r.bytes().enumerate() {
        print_line_no_once(i);
        print_byte(b.unwrap());
    }
    print!("\n");
}

Here we name the bounds of the generic by the word where directly before the body {} braces. More than just one can be appended by ,.

wrap up

to not miss out the other functions, even thou they are not showing much here you go:

fn print_line_no_once(i: usize) {
    if i % 0x10 == 0 {
        if i > 0 {
            print!("\n");
        }
        print!("{:07x}", i);
    }
}

fn print_byte(b: u8) {
    print!(" {:02x}", b);
}

So we have now learned how we can use anonymous types or generics to make use of loosely couple our functions to traits instead of tightly couple them to the real structs that they are. That is also sometimes referred to as the Open Close Principle

references

Further reading about subtle differences can be found on reddit

the title image belongs to Blizzard Entertainment and is available under CC BY-NC-SA 3.0.

used versions:

$ rustc --version && cargo --version
rustc 1.37.0 (eae3437df 2019-08-13)
cargo 1.37.0 (9edd08916 2019-08-02)

Please don't forget to share your feedback, and let me know what was your learning if there was any. If you have more variants that I missed, please share them.

DEV Community: Sven Kanoldt

What is a CIDR trie and how can it help you?

Problem

Solution

The CidrCountryMap

The CIDR trie specifics

Implementation

Conclusion

References

What is the matter with `AsRef`?

Background

Example: String or &str

Example: wrapper type

Example: a composed type

Wrap up

🎉 🚀 🍺 New release of Terminal Recorder - t-rec

Demo

Features

Install

Hidden Gems

Contribute

License

🎉 🚀 🍺 The new release v0.4.1 of stegano-rs is out

✨ Features

🛠️ Maintenance

Rust Munich Meetup #3

container less cloud computing - wascc

steganography cli in rust - architecture

rust macro rules in practice

TL;DR

Background

Macro in rust

An Example

Bonus Track

Simplification

Time spend on writing CI configurations

Super Simple Disk Benchmark written in rust

Purpose of life

Quick Start

Install

Usage

Missing something?

little rust starter hint series: lifetimes made easy

Ok, how is this connected with lifetimes?

When are lifetimes required?

The Invisible

Back to the Iterator

Final test

Wrapping it up

little rust starter hint series: Polymorphism and Traits

the problem statement

the basics

explanation

the trait BufRead

the naive approach

Version 1: the impl on anonymous type

Version 2: generic short hand

Version 3: generic verbose

wrap up

references

The `CidrCountryMap`

Example: `String` or `&str`

the trait `BufRead`