I did a seminar talk on JTAG and how to use it to check a PCB for errors. For this i designed a little board in order to simulate manufacturing errors. In this post I want to give you a short introduction to JTAG and how to use it.

What is Boundary-scan

Boundary-scan was developed to simplify testing of integrated circuits. To do this the Joint Test Action Group introduced the Boundary Scan architecture as a standard and today it has replaced the old testing methods because of its cost efficiency and speed up of test development and execution.

So how does this work?

I will be just covering the basics here. If you want a more detailed introduction, you can read the articles referenced at the end of this post.

Boundary-scan is a technology which places cells at the circuits boundary that can sample the circuit inputs and also drive its outputs. This can be done while the circuit is operating and it is controlled via the JTAG interface. With these cells in place we wan test the internal logic of the circuit as well as the interconnects between the devices on a board.

In the picture above you can see an overview of the boundary-scan architecture. This picture only shows one JTAG device, but on more complex PCB there are many such devices that are connected in a JTAG chain. This means that the data out of one chip is connected to the input of the next.

In order for us use this architecture, we need to connect to the four JTAG pins:

• TDI Test Data In
• TDO Test Data Out
• TCK Test Clock
• TMS Test Mode Select

Once connected we can control all of the devices in the JTAG chain. In general we can perform two different types of actions. We can either write/read data or we can write instructions. Testing a circuit involves both of theses actions. By writing instructions we can set the connected circuits into different modes. And by writing data we can set the pins to the desired levels as well as read the results.

There are three different instructions we are interested in when testing interconnects:

• SAMPLE/PRELOAD
• EXTEST
• BYPASS

With the SAMPLE/PRELOAD instruction the boundary-scan cells will sample the inputs of the circuit, and when shifting in data we can read values received at the pins. We can also use this command to load data into the boundary-scan cells. The EXTEST instruction will set the output of the pins to the values provided in the boundary-scan cells and the BYPASS instruction lets us skip devices in the chain that are not of interest to the test currently performed.

With these instructions we can set pins of a device to a logic level and test at the receiving circuit if the correct logic level was received.

The Hardware

We need to connect to the JTAG pins of a devices. If they are exposed there probably is a connector on the board. If not it may be possible to solder wires directly to the pins. In any case we will need a JTAG adapter in order to connect them to a normal computer via USB. I am using a JLink adapter which features a 20 pin JTAG connector.

The PCB I am using for testing is a small circuit I designed myself, it also has a 20 pin connector which exposes the JTAG pins. Here is the layout:

It features two MAX V Altera CPLDs that implement the boundary-scan architecture and are connected in a JTAG chain. To test some connections between them I connected eight of their pins at the top and added a dip switch to simulate shorts between the wires as well as pull ups and pull downs.

Tooling

Okay so we got a PCB and connected it to a computer with a JTAG adapter now what? How do get the tests running?

Well this is where it gets hard, because there is no nice open source software that does it all for us. We need to write the test ourselves and for that we need to know the details of the interconnects on our PCB and the details of how the boundary-scan architecture is implemented in the devices in our JTAG chain.

BSDL Files

The Boundary-scan standard does not tell manufacturers what bit codes to use to encode the instructions, but it does require them to publish the so called BSDL (Boundary Scan Description Language) files free of charge for their devices. These files use a dialect derived from VHDL a hardware description language and describe all information needed to use a devices boundary-scan architecture. For example:

• Instruction register description
• Boundary-scan cell description
• Pin mappings
• and more

Basically all information we might want to know about a specific device is in that file.

SVF Files

Most JTAG adapter tool chains support a file format called SVF (Serial Vector Format). These are plain text files that describe what data or instructions to write to the JTAG connection. It has no knowledge about the JTAG chain of devices or any of there properties. We can just specify what data/instructions to shift in and what results we expect to be shifted out.

Designing a simple test

Okay so putting it all together. Lets say we want to test two neighboring interconnects for a bridging fault.

On my example PCB two neighboring interconnects are connected as follows:

1. CHIP 1 IO56 - CHIP 2 IO49
2. CHIP 1 IO55 - CHIP 2 IO50

So if we set IO56 of the first chip to a logic 1 and IO55 to logic 0, we would expect to receive a logic 1 on IO49 and a logic 0 at IO50 on the second chip. If we receive a logic 1 at IO50 that means that there is a bridging fault between the interconnects.

To write a test for this we need to write an SVF file that we can run with the JTAG adapter tool chain. It needs to complete the following steps:

1. Set first chip into SAMPLE/PRELOAD mode. (Shift in Instructions)
2. Load Test pattern into first chip (Shift in Data)
3. Set first chip to EXTEST and second chip to SAMPLE/PRELOAD mode (Shift in Instructions)
4. Shift in dummy data to receive the data sampled from chip 2 and compare against the expected result (Shift in Data)

The following SVF files does exactly this:

TRST OFF;
ENDIR IDLE;
ENDDR IDLE;
STATE RESET;
STATE IDLE;
FREQUENCY 10000000 HZ;
SIR 20 TDI (01405);
SDR 480 TDI (000000000000000000000000000000000000000000800000000000000
	000000000000000000000000000000000000000000000000000000000000000);
SIR 20 TDI (03c05);
SDR 480 TDI (0) TDO (000000000000000000000000000000000000000000000000
	00000000000000000000000000000000000000000000000100000000000000000
	0000000) MASK (00000000000000000000000000000000000000000000000000
	00000000000000000000000000000000000000000000012000000000000000000
	00000);

Up until the first line starting with SIR all we are doing is making sure the boundary-scan circuit is in a known state and setting the speed at which we want to operate.

SIR means we want to write instruction data. We need to specify the length and since we have to chips with both 10 bit instruction registers we are writing 20 bits of data. The data we want to write is specified behind the TDI statement as a hex string surrounded by parenthesis.

SDR works the same as SIR but instead of instruction data we are just writing data. In this case we are writing 480 bits, since both chips have a boundary-scan register length of 240 bits. If we want to compare the shifted out data against the expected data we have to write the expected result as a hex string behind the TDO statement and we can even mask the result so that we only look at the bits we are interested in.

How do we know what data to write and what data to expect? Well for that we have to look at the BSDL files of the devices in our JTAG chain and figure out which pin is mapped to which bit in the data. Of course writing a SVF by hand is very tedious, so instead I created some python scripts to help me with the task. Feel free to use them for your own projects.

Conclusion

Using Boundary-scan for PCB testing is very nice when trying to automatically test PCBs. Sadly there is little to no open source software which makes it easy to design tests for your own layouts. Which means that you still have to do a lot of information gathering if you want to use this technology. But once the tests are implemented testing a PCB becomes a very easy and fast.

I hope this blog post gave you an idea of what you need to do, to get up and running with boundary-scan testing. If you have any feedback feel free to contact me.

Further Reading Material

• Texas Instruments Testabilty Primer
• Paper on Interconnect Testing

It is time to revisit of the simple wifi setup as much has changed since. This time, however, we will not only cover wifi, but also wired connections as well as DNS.

Wired networking

This wired setup is based on systemd-networkd, which typically comes with systemd. If you use a systemd-based Linux, you should be ready to go right away. It further assumes that acquiring an IP address via DHCP once a cable is plugged in the typical usecase.¹

Create the file /etc/systemd/network/cable.network²:

[Match]
Name=<name of the wired network device> <second one if applicable> [<more ...>]

[Network]
DHCP=yes
IPv6PrivacyExtensions=true

[DHCP]
Anonymize=true

Then systemctl enable --now systemd-networkd and plug in a cable, wired networking with DHCP is up and running.

Wireless networking

The wireless setup is based on iwd, the currently vastly superior tool for wireless networking on Linux compared to existing alternatives such as wpa_supplicant (the effectively only other contender in this game) and software using it such as NetworkManager and netctl. It requires iwd as well as Linux >= 4.20 for full operation.

Create the file /etc/iwd/main.conf:

[General]
# uncomment for setting the wifi interface name yourself
# see https://iwd.wiki.kernel.org/interface_lifecycle
#UseDefaultInterface=true

# enable builtin DHCP-client within iwd for wifi
EnableNetworkConfiguration=true

# randomizes mac-address every time iwd starts or the hardware is initially detected
AddressRandomization=once

Then systemctl enable --now iwd, wireless networking with DHCP is up and running, blazingly fast and stable.

You might want to take a look at the previous post to deal with race conditions that might be introduced due to iwd being significantly faster than other wifi-solutions on Linux.

Frontends

iwd stores its known networks in /var/lib/iwd. To add, modify or delete them, several options are available:

iwctl

You can now connect to simple PSK wifi networks in the iwctl shell:

[iwctl] station <devicename> get-networks
…
[iwctl] station <devicename> connect <network-name>

iwctl will ask you for the password, iwd will memorize it for later connections and autoconnect the next time the network appears. Currently, iwctl only supports creating simple password-only network connections, for more complex network setups, instead of iwctl asking you all the nifty details of an enterprise connection, use the file-based config instead. For everything else, just type help within iwctl.

file-based config

If you have more complex wifi-setups, you can simply drop a network configuration file in /var/lib/iwd. The files must be named as networkname.protocol. You can find the protocol listed in the output of get-networks in the iwctl-shell. To fill the file, take a look to the network configuration settings in the iwd documentation or the iwd.network manpage.

For example, to use the University Heidelberg’s eduroam network, create the file /var/lib/iwd/eduroam.8021x containing

[Security]
EAP-Method=TTLS
EAP-Identity=<anonymous-identity>
EAP-TTLS-CACert=/etc/ssl/certs/T-TeleSec_GlobalRoot_Class_2.pem
EAP-TTLS-Phase2-Method=MSCHAPV2
EAP-TTLS-Phase2-Identity=<uni-id>@uni-heidelberg.de
EAP-TTLS-Phase2-Password=<your University account password>

For other institutions, the details in the method might vary, of course. See man iwd.network for details. It also includes several examples for almost all possible configurations.

Network Manager

You can also use Network Manager for a more graphical experience, you just have to enable the iwd-backend for NetworkManager to use it. In addition to that, double check if you have the right NetworkManager version for your iwd version, just as a precaution.

DNS

For modern domain name resolution, you can use systemd-resolved, which provides statistics, automated caching of DNS requests, DNSSEC validation and much more. To use it, ensure systemd-resolved is installed³ and systemctl enable --now systemd-resolved. Ensure that /etc/resolv.conf is symlinked to /run/systemd/resolve/stub-resolv.conf, if not

ln -sf /run/systemd/resolve/stub-resolv.conf /etc/resolv.conf

takes care of it. Afterwards, you can change the default fallback DNS servers and other things in /etc/systemd/resolved.conf, if desired and otherwise enjoy resolvectl and resolvectl statistics.

Miscellaneous optimizations

Binding iwd to the wifi-device

To disable iwd when the wifi is not present (and iwd therefore not needed) create the file /etc/udev/rules.d/wifi.rules containing

# bind iwd to wifi
SUBSYSTEM=="rfkill", ENV{RFKILL_NAME}=="phy0", ENV{RFKILL_TYPE}=="wlan", ACTION=="change", ENV{RFKILL_STATE}=="1", RUN+="/usr/bin/systemctl --no-block start iwd.service"
SUBSYSTEM=="rfkill", ENV{RFKILL_NAME}=="phy0", ENV{RFKILL_TYPE}=="wlan", ACTION=="change", ENV{RFKILL_STATE}=="0", RUN+="/usr/bin/systemctl --no-block stop iwd.service"

If AddressRamdomization=once is set in the configuration, this udev rule has the nice side-effect that, as iwd starts nanew when the wifi is un-rfkilled, the MAC address of the interface is randomized again.

Persistent device naming

If you want to have persistent device names, for example for devices showing up in a status bar or something similar, this ist easiest achieved by creating a link-file⁴ /etc/systemd/network. To persistently name the wireless device wifi, create /etc/systemd/network/00-wifi.link containing

[Match]
MACAddress=ab:cd:ef:12:34:56  # wifi's original MAC address

[Link]
Name=wifi  # can be used for matching in the according *.network-file

If you do this for any device operated by iwd, ensure you have UseDefaultInterface=true set in section [General] in /etc/iwd/main.conf.

Setting specific MAC addresses for specific wifi networks and randomizing on every connect

In case you need to set a specific address for a specific wireless network, iwd>=1.6 allows using AddressOverride= inside a network configuration file. For this to take effect, however, AddressRandomization=once must be dropped from /etc/iwd/main.conf. This makes iwd generate persistent MAC addresses per network (generated from its SSID and real hardware address) by default and allows AddressOverride to take effect. Additionally, a network file can contain AlwaysRandomizeAddress=true, which randomizes the MAC address on each connect for this network (also only takes effect when AddressRandomization is not set or set do its default value in main.conf. However, due to kernel limitations, each change of a MAC address requires powercyling the card. This leads to (for iwd standards) singificantly prolonged connection times (by ≈300-400ms). Given that, as long as you do not require AddressOverride, AddressRandomization=once gives you fast connection times while still randomizing your card’s MAC address regularly enough.

_{Thanks to rixx for helpful suggestions.}

This blog has had an RSS-feed from the very start. But from today on, this blog also officially has feeds on Mastodon and Twitter you can subscribe to if you do not like RSS or prefer these over RSS.

Let’s see where this goes, I’m curious if that’s something people will find useful. Retoots or -tweets encouraged!

ACHTUNG: Aufgrund der aktuellen Lage und Vorgaben der Stadt Mannheim (siehe auch) bleibt das RaumZeitLabor bis auf weiteres geschlossen. Alle öffentlichen Veranstaltungen sind abgesagt.

Passt auf euch auf.

When we are storing data, we typically assume that our storage system of choice returns that data later just as we put it in. However what guarantees do we have that this is actually the case? The case made here is the case of bitrot, the silent degradation of the physical charges that physically make up today’s storage devices.

To counter this type of problem, one can employ data checksumming, as it is done by both btrfs and ZFS. However, while in the long run btrfs might be the tool of choice for this, it is fairly complex and not yet too mature, whereas ZFS, the most prominent candidate for this type of features, is not without hassle and it must be recompiled for every kernel update (although automation exists).

In this blogpost, we’ll therefore take a look into a storage design that actually checks whether the returned data is actually valid and not silently corrupted inside our storage system and is completely designed with components available in Linux itself without the need to recompile and test your storage layer on every kernel upgrade. We find that this storage design, while fulfilling the same purpose as ZFS, does not only yield comparable performance, but actually in some cases even able to significantly outperform it, as the benchmarks at the end indicate.

The setup

The system we will test in the following will be constructed from four components (including the filesystem):

• dm-integrity provides blocklevel checksumming for all incoming data and will check said checksum for all data read through it (and return a read error if it doesn’t match).
• mdraid provides redundancy if a disk misbehaves, avoiding data loss. If the dm-integrity-layer detects invalid data from the disk, mdraid will see a read-error and can immediately correct this error by reading it from somewhere else in the redundancy pool.
• dm-crypt on top of the RAID, right below the filesystem will encrypt the data¹
• ext4 as a filesystem to actually store files on it

The order matters, dm-integrity must be placed between the harddisks and the mdraid, to ensure that data corruption errors can be corrected by mdraid after they have been detected by dm-integrity. Similarly, dm-crypt has nothing to do with redundancy, therefore it should be placed on top of of mdraid, to only having to be passed once, and not multiple times as it would be the case for placing it alongside dm-integrity.²

This yields the following storage design:

Storage system architecture

This script will assemble the above depicted system and mount it to /mnt.

Resulting performance

Now that we have an assembled system, we’d like to quantify the performance impact of the different layers. The test setup for this is a Kobol Helios4 (primarily because it’s the intended target platform for this storage system) with four disks³ running Debian 10 “Buster”. The Helios4 is powered by an energy efficient dual-core ARM SoC optimized for storage systems. The setup was not built based on the entire disks, but on partitions of a size of 10GiB each, allowing multiple parallel designs and therefore easing the benchmarking procedure, as well as speeding up the experiments⁴.

Layer analysis of performance impact

Throughput

To benchmark throughput, the following commands were used:

# write:
echo 3 > /proc/sys/vm/drop_cache  # drop all caches
dd if=/dev/zero of=/path/to/testfile bs=1M count=8000 conv=fdatasync

# read
echo 3 > /proc/sys/vm/drop_cache  # drop all caches
dd if=/path/to/testfile of=/dev/zero conv=fdatasync

This procedure was repeated ten times for proper statistics for the different cases for both read (r) and write (w):

• ext4 filesystem only (f, one disk only)
• encryption, topped by ext4 (cf, one disk only)
• mdraid (RAID6/double parity), topped by the former (rcf, 4 disks)
• the final setup, including integrity (ircf, 4 disks)

We see different interesting results in the data: First of all, the encryption engine on the helios4 is not completely impact free, although the resulting performance is still more than sufficient for the designated uses for a Helios4.

Secondly, we see that adding integrity layer does have a noticable impact on writing, but a negligible impact on reading, indicating that especially for systems primarily intended to read data from adding the integrity layer is a matter of negligible cost.

For write-heavy systems, the performance impact is more considerable, but for certain workloads, such as the home-NAS-case the Helios is designed for, the performance can still be considered fully sufficient, especially as normally the system would cache those writes to a certain extend, which was explicitly disabled for benchmarking purposes (see conv=fdatasync in the benchmark procedure).

The reason for the degradation in write (but not in read) is likely due to the fact that the integrity layer and the mdraid layer are decoupled from one another, the raid-layer is not aware that for a double parity setup it effectively has to write the same information three times, and the integrity layer has to account for all three writes before the data is considered synced as required by conv=fdatasync.

Latency

We have found that the throguhput of such a storage design is yielding useful throughput-rates. The next question is about the latency of the system, which we will, for simplicity, only estimate for random 4K-reads. Again, just as above, we will investigate the impact of the different layers of the system. To do so, we read 100.000 sectors randomly from an 18GB sized testfile filling the storage mountpoint for each configuration after dropping all caches.

Latency comparison of system layers

The figure above yields several interesting insights: First of all, we do see cache hits close to zero milliseconds, furthermore, we see that the latency distribution is fairly evenly distributed over the available range and finally and most interestingly, we see that the impact of the several layers onto the latency is measurable, but rather irrellevant for typical practical purposes.

Performance comparison with ZFS

So far we have tested the setup on its intended target platform, the Helios4. To compare the resulting system against the elephant in the room, ZFS, we will use a different test platform, based on an Intel i7-2600K as CPU and 4x1TB disks, as the zfs-dkms was not reliably buildable on Debian Buster on ARM, and when it actually built, it explicitly stated that 32bit-processors (as the Helios’ CPU) are not supported by upstream, although technically the system would run.

To allow for a cleaner comparison, the testbed was accordinly changed to accomodate for ZFS’s preferences. As ZFS did not adhere to conv=fdatasync⁵, the main memory was restricted to 1GB, swap was turned off and the size of the testfile was chosen to be 18GB. This way, any caching happening would be at least significantly reduced as there was little space next to the OS inside of the main memory for caching.

All tests were run on a Debian 10 “Buster” with Linux 4.19, ZFS was used in form of the package zfs-dkms in version 0.8.2 from backports. The storage layer for both setups was layouted with double parity (RAID6/raidz2) and, as the zfs-dkms package in Debian was not able to do encryption, the mdraid-based setup was also setup without the encryption layer.

Throughput

The commands used for benchmarking throughput were conceptually the same as above:

# write:
echo 3 > /proc/sys/vm/drop_cache  # drop all caches
dd if=/dev/zero of=/path/to/testfile bs=1M count=18000 conv=fdatasync

# read
echo 3 > /proc/sys/vm/drop_cache  # drop all caches
dd if=/path/to/testfile of=/dev/zero conv=fdatasync

Although ZFS seemingly does not adhere to any cache dropping or syncing instructions, they were still performed and adhered to by the mdraid-based setup.

Throughput comparison, zfs & md

The results are very interesting: While the md-based setup performs less consistent in and of itself, it still consistently outperforms ZFS in read performance. When it comes to write, though, ZFS performs noticably better.⁶

To investigate the cause of this unexpected balance, we note that while ZFS combines raid, integrity and filesystem in one component, for the md-based setup these are separate components. Of these components, not only the filesystem, but also the dm-integrity implements journalling to avoid inconsistencies in case of a power outage. This leads to increased work until the transaction has been fully flushed to disk, which can be seen in the next figure, where the md-based system (without the encryption layer) is tested with both journalling enabled and disabled in the integrity layer:

Throughput effect of integrity journaling

We find that write-performance increases significantly (and taking into account the factor of increase it actually surpasses the write performance of ZFS). We can therefore conclude that the Linux components are very capable of matching ZFS performance-wise, at least for low memory environements, and especially outperform ZFS in read-performance. In a purely throughput-optimized configuration (such as when an uninterruptible power supply is installed, so that the guarantees of journalling are not necessarily crucial) it even outperforms a standard ZFS-configuration in both read and write⁷. Before you disable integrity-journalling in production, however, take into account the implications⁸.

Disabling journalling on the filesystem layer of the md-based setup did not have any measurable impact onto the throughput performance of the setup.

Latency

Analoguous to the latency measurements on the Helios4 we can measure the latency profile for both the md-based storage as well as ZFS, reading 1 million random 4K-samples from an 18GB sized testfile.

Latency comparison, zfs & md

Besides the expected cache hits close to zero millisecond-mark we find some very interesting results with regards to latency: While the md-based system is very consistent with its latency profile, both with the distribution as well as the average and median being almost identical, ZFS exhibits a slightly lower median latency, but contrasts that with an up to five-fold larger latency tail, which lifts the average latency noticably above that of the md-based setup, indicating that ZFS seems far less predictable with regard to read-latcency.

Remark on RAID checks

One thing to note is that checks and resyncs of the proposed setup are significantly prolonged (by a factor of 3 to 4) compared to an mdraid without the integrity-layer underneath. The investigation so far has so far not revealed the underlying cause. It is not CPU-bound, indicating that the read-performance is not held back by checksumming, the latency figures above do not imply an increase in latency significant enough to cause a factor 3-4 prolonged check-time, disabling the journal did not change this either (as one would expect, as the journal is unrelated to read, which should be the only relevant mode for a raid-check).

ZFS was roughly on par with mdraid without the integrity-layer underneath with regard to raid-check time.

If anyone has an idea of the root cause of this behavior, feel encouraged to contact me, I’d be intrigued to know.

Conclusion

First of all, the conclusion when pondering if ZFS is required for guaranteeing data integrity in a storage layer can clearly be answered with a no. Not only does the combination of mdraid and dm-integrity yield more than sufficient data rates for a typical home-storage-setup, the data also indicates that at least in low-memory environements this kind of setup can actually outperform ZFS for read-heavy operations, both in throughput as well as being at least comparable if not more reliable with regard to latency. Especially for long-term-storage solutions primarily intended for just having tons of storage space, such as home-NAS-systems, this is typically the more relevant mode of operation as long as the write-performance is sufficient (which the data confirms).

Therefore data integrity on the storage layer is very possible without going through the hassle of having to build ZFS additionally with each kernel upgrade and preserving the option for easy restore with any modern linux, even if ZFS is not available, should the primary storage system fail.

The prolonged check- and resync-times still lack a reasonable explanation, which is unsatisfying. However, from a purely practical point of view, rebuilds and resyncs are typically a rather rare occurance, therefore the prolongation of check- and resync-time is a comparatively small (and rarely paid) price for the guarantee of data integrity.

Additional thoughts and outlook

In addition to the conclusions we can draw from the data we gathered, the md-based setup has another advantage ZFS does not (yet) provide: for ZFS all disks for the storage pool must be available upfront at first assembly⁹ (or the redundancy will not be “any 2 disks may fail and the storage pool is still operational” for a system ultimately intended to have double parity) whereas this is not the case with mdraid, which can extend or grow a pool¹⁰, resyncing it to, for all (changing) configurations, at any point in time (except disk failure and rebuild) fulfill “any two disks may fail” (for an intended double parity/RAID6-setup with over time increasing disk count).

Of course, ZFS is not only blocklevel checksumming. ZFS provides additional tooling for different purposes which might make its use still worthwhile. If one was to extend the md-raid-based system by some of these features, it might be of interest to use XFS as the filesystem on top, as with a sufficiently recent Kernel XFS also supports features like filesystem-snapshots and many more. Alternatively, one could introduce an LVM-layer into the system (or, if desired, even replace md with LVM).

As usual, feedback is always appreciated.

_{Thanks to Hauro for proofreading and helpful comments.}

Liebe RaumZeitSaunierende,

am 1. März 2020 wollen wir zuSamen den “Kalevalan päivä” und somit den Tag der finnischen Kultur (28. Februar) bei einem Spätstück nachfeiern. Zieht euer Eläkeläiset-Fanshirt aus dem Schrank und kommt um 11.30 Uhr auf eurem Nokia 3310 ins RZL vibriert. Lasst euch dieses finntastische Ereignis nicht entgehen! Damit wir wissen, wie viel Munavoi wir anrühren müssen, bitten wir um Anmeldung per Mail bis zum 25. Februar 2020. Wir freuen uns über einen Beitrag von 8 Euro für unser Finnkasso-Unternehmen.

Hyvää ruokahalua!
Eure Muumirattie

When spawning a child program, for example in an integration test, it is often helpful to know when the child program is ready to receive requests.

Delaying

A brittle strategy is to just add a delay (say, time.Sleep(2 * time.Second)) and hope the child program finishes initialization in that time. This is brittle because it depends on timing, so when the computer running the test is slow for whichever reason, your test starts failing. Many CI/CD systems have less capacity (and/or are more heavily utilized) than developer machines, so timeouts frequently need to be adjusted.

Also, relying on timing is a race to the bottom: your delay needs to work on the slowest machine that runs your code. Ergo, tests waste valuable developer time on your high-end workstation, just so that they pass on some under-powered machine.

Polling

A slightly better strategy is polling, i.e. repeatedly checking whether the child program is ready. As an example, in the dnsmasq_exporter test, I need to poll to find out when dnsmasq(8) is ready.

This approach is better because it automatically works well on both high-end and under-powered machines, without wasting time on either.

Finding a good frequency with which to poll is a bit of an art, though: the more often you poll, the less time you waste, but also the more resources you spend on polling instead of letting your program initialize. The overhead may be barely noticeable, but when starting lots of programs (e.g. in a microservice architecture) or when individual polls are costly, the overhead can add up.

Readiness notifications

The most elegant approach is to use readiness notifications: you don’t waste any time or resources.

It only takes a few lines of code to integrate this approach into your application. The specifics might vary depending on your environment, e.g. whether an environment variable is preferable to a command-line flag; my goal with this article is to explain the approach in general, and you can take care of the details.

The key idea is: the child program inherits a pipe file descriptor from the parent and closes it once ready. The parent program knows the child program is ready because an otherwise blocking read from the pipe returns once the pipe is closed.

This is similar to using a chan struct{} in Go and closing it. It doesn’t have to remain this simple, though: you can also send arbitrary data over the pipe, ranging from a simple string being sent in one direction and culminating in speaking a framed protocol in a client/server fashion. In Debian Code Search, I’m writing the chosen network address before closing the pipe, so that the parent program knows where to connect to.

Parent Program

So, how do we go about readiness notifications in Go? We create a new pipe and specify the write end in the ExtraFiles field of (os/exec).Cmd:

r, w, err := os.Pipe()
if err != nil {
  return err
}

child := exec.Command("child")
child.Stderr = os.Stderr
child.ExtraFiles = []*os.File{w}

It is good practice to explicitly specify the file descriptor number that we passed via some sort of signaling, so that the child program does not need to be modified when we add new file descriptors in the parent, and also because this behavior is usually opt-in.

In this case, we’ll do that via an environment variable and start the child program:

// Go dup2()’s ExtraFiles to file descriptor 3 and counting.
// File descriptors 0, 1, 2 are stdin, stdout and stderr.
child.Env = append(os.Environ(), "CHILD_READY_FD=3")

// Note child.Start(), not child.Run():
if err := child.Start(); err != nil {
  return fmt.Errorf("%v: %v", child.Args, err)
}

At this point, both the parent and the child process have a file descriptor referencing the write end of the pipe. Since the pipe will only be closed once all processes have closed the write end, we need to close the write end in the parent program:

// Close the write end of the pipe in the parent:
w.Close()

Now, we can blockingly read from the pipe, and know that once the read call returns, the child program is ready to receive requests:

// Avoid hanging forever in case the child program never becomes ready;
// this is easier to diagnose than an unspecified CI/CD test timeout.
// This timeout should be much much longer than initialization takes.
r.SetReadDeadline(time.Now().Add(1 * time.Minute))
if _, err := ioutil.ReadAll(r); err != nil {
  return fmt.Errorf("awaiting readiness: %v", err)
}

// …send requests…

// …tear down child program…

Child Program

In the child program, we need to recognize that the parent program requests a readiness notification, and ensure our signaling doesn’t leak to child programs of the child program:

var readyFile *os.File

func init() {
  if fd, err := strconv.Atoi(os.Getenv("CHILD_READY_FD")); err == nil {
    readyFile = os.NewFile(uintptr(fd), "readyfd")
    os.Unsetenv("CHILD_READY_FD")
  }
}

func main() {
  // …initialize…

  if readyFile != nil {
    readyFile.Close() // signal readiness
    readyFile = nil   // just to be prudent
  }
}

Conclusion

Depending on what you’re communicating from the child to the parent, and how your system is architected, it might be a good idea to use systemd socket activation (socket activation in Go). It works similarly in concept, but passes a listening socket and readiness is determined by the child process answering requests. We introduced this technique in the i3 testsuite and reduced the total wallclock time from >100 seconds to a mere 16 seconds back then (even faster today).

The technique described in this blog post is a bit more generic than systemd’s socket activation. In general, passing file descriptors between processes is a powerful idea. For example, in debiman, we’re passing individual pipe file descriptors to a persistent mandocd(8) process to quickly convert lots of man pages without encurring process creation overhead.

Earlier this month the first annual meeting of the French working group NBODY (GDR NBODY) took place in Lille. Since the GDR NBODY is an association of interdisciplinary scientists working on N-body problems in chemistry an physics, the about 80 participants came from a broad background ranging from quantum chemistry, materials science, mathematics or nuclear physics. The overall atmosphere of the conference was extremely relaxed, such that during the talks vivid discussions frequently arose. I particularly enjoyed the presentations about N-body effects in nuclear physics and the first-principle simulations of the structure of nuclei, since that topic was completely new to me. Fortunately there was one introductory talk for each of the four mayor topics of the working group bringing everyone up to speed in each others' subject.

As part of the program I presented about DFTK and our recent advances with the code. I first gave a brief rationalisation why we started DFTK as a new code for working on electronic-structure problems from the mathematical perspective, then I briefly presented two applications, where we hope our code could be useful towards developing new approaches for practical calculations. One is an investigation of increased precision and more generally estimates for the floating-point error in density-functional theory calculations. The other was a discussion of our ongoing work on SCF preconditioning techniques. In this I showed our first steps towards developing a mathematically justified SCF preconditioner suitable for tackling systems containing both a conducting and an insulating part. Our first results indicate that our approach could be more suitable than established methods, which usually rely on interpolating empirically between the established preconditioning strategies for metals and insulators. Our hope would be that our preconditioner could allow to apply DFTK in the context of simulating the electronic structure of catalytic metal surfaces in the future. In this application a challenge for SCF schemes is that employed catalysts are usually coated with an insulating oxide layer or are interfacing with more insulating organic compounds or air.

Link	Licence
Using the density-functional toolkit (DFTK) to investigate floating-point error and SCF convergence (Slides)

In case you are not yet familiar with why an initramfs (or initrd, or initial ramdisk) is typically used when starting Linux, let me quote the wikipedia definition:

“[…] initrd is a scheme for loading a temporary root file system into memory, which may be used as part of the Linux startup process […] to make preparations before the real root file system can be mounted.”

Many Linux distributions do not compile all file system drivers into the kernel, but instead load them on-demand from an initramfs, which saves memory.

Another common scenario, in which an initramfs is required, is full-disk encryption: the disk must be unlocked from userspace, but since userspace is encrypted, an initramfs is used.

Motivation

Thus far, building a distri disk image was quite slow:

This is on an AMD Ryzen 3900X 12-core processor (2019):

distri % time make cryptimage serial=1
80.29s user 13.56s system 186% cpu 50.419 total # 19s image, 31s initrd

Of these 50 seconds, dracut’s initramfs generation accounts for 31 seconds (62%)!

Initramfs generation time drops to 8.7 seconds once dracut no longer needs to use the single-threaded gzip(1) , but the multi-threaded replacement pigz(1) :

This brings the total time to build a distri disk image down to:

distri % time make cryptimage serial=1
76.85s user 13.23s system 327% cpu 27.509 total # 19s image, 8.7s initrd

Clearly, when you use dracut on any modern computer, you should make pigz available. dracut should fail to compile unless one explicitly opts into the known-slower gzip. For more thoughts on optional dependencies, see “Optional dependencies don’t work”.

But why does it take 8.7 seconds still? Can we go faster?

The answer is Yes! I recently built a distri-specific initramfs I’m calling minitrd. I wrote both big parts from scratch:

1. the initramfs generator program (distri initrd)
2. a custom Go userland (cmd/minitrd), running as /init in the initramfs.

minitrd generates the initramfs image in ≈400ms, bringing the total time down to:

distri % time make cryptimage serial=1
50.09s user 8.80s system 314% cpu 18.739 total # 18s image, 400ms initrd

(The remaining time is spent in preparing the file system, then installing and configuring the distri system, i.e. preparing a disk image you can run on real hardware.)

How can minitrd be 20 times faster than dracut?

dracut is mainly written in shell, with a C helper program. It drives the generation process by spawning lots of external dependencies (e.g. ldd or the dracut-install helper program). I assume that the combination of using an interpreted language (shell) that spawns lots of processes and precludes a concurrent architecture is to blame for the poor performance.

minitrd is written in Go, with speed as a goal. It leverages concurrency and uses no external dependencies; everything happens within a single process (but with enough threads to saturate modern hardware).

Measuring early boot time using qemu, I measured the dracut-generated initramfs taking 588ms to display the full disk encryption passphrase prompt, whereas minitrd took only 195ms.

The rest of this article dives deeper into how minitrd works.

What does an initramfs do?

Ultimately, the job of an initramfs is to make the root file system available and continue booting the system from there. Depending on the system setup, this involves the following 5 steps:

1. Load kernel modules to access the block devices with the root file system

Depending on the system, the block devices with the root file system might already be present when the initramfs runs, or some kernel modules might need to be loaded first. On my Dell XPS 9360 laptop, the NVMe system disk is already present when the initramfs starts, whereas in qemu, we need to load the virtio_pci module, followed by the virtio_scsi module.

How will our userland program know which kernel modules to load? Linux kernel modules declare patterns for their supported hardware as an alias, e.g.:

initrd# grep virtio_pci lib/modules/5.4.6/modules.alias
alias pci:v00001AF4d*sv*sd*bc*sc*i* virtio_pci

Devices in sysfs have a modalias file whose content can be matched against these declarations to identify the module to load:

initrd# cat /sys/devices/pci0000:00/*/modalias
pci:v00001AF4d00001005sv00001AF4sd00000004bc00scFFi00
pci:v00001AF4d00001004sv00001AF4sd00000008bc01sc00i00
[…]

Hence, for the initial round of module loading, it is sufficient to locate all modalias files within sysfs and load the responsible modules.

Loading a kernel module can result in new devices appearing. When that happens, the kernel sends a uevent, which the uevent consumer in userspace receives via a netlink socket. Typically, this consumer is udev(7) , but in our case, it’s minitrd.

For each uevent messages that comes with a MODALIAS variable, minitrd will load the relevant kernel module(s).

When loading a kernel module, its dependencies need to be loaded first. Dependency information is stored in the modules.dep file in a Makefile-like syntax:

initrd# grep virtio_pci lib/modules/5.4.6/modules.dep
kernel/drivers/virtio/virtio_pci.ko: kernel/drivers/virtio/virtio_ring.ko kernel/drivers/virtio/virtio.ko

To load a module, we can open its file and then call the Linux-specific finit_module(2) system call. Some modules are expected to return an error code, e.g. ENODEV or ENOENT when some hardware device is not actually present.

Side note: next to the textual versions, there are also binary versions of the modules.alias and modules.dep files. Presumably, those can be queried more quickly, but for simplicitly, I have not (yet?) implemented support in minitrd.

2. Console settings: font, keyboard layout

Setting a legible font is necessary for hi-dpi displays. On my Dell XPS 9360 (3200 x 1800 QHD+ display), the following works well:

initrd# setfont latarcyrheb-sun32

Setting the user’s keyboard layout is necessary for entering the LUKS full-disk encryption passphrase in their preferred keyboard layout. I use the NEO layout:

initrd# loadkeys neo

3. Block device identification

In the Linux kernel, block device enumeration order is not necessarily the same on each boot. Even if it was deterministic, device order could still be changed when users modify their computer’s device topology (e.g. connect a new disk to a formerly unused port).

Hence, it is good style to refer to disks and their partitions with stable identifiers. This also applies to boot loader configuration, and so most distributions will set a kernel parameter such as root=UUID=1fa04de7-30a9-4183-93e9-1b0061567121.

Identifying the block device or partition with the specified UUID is the initramfs’s job.

Depending on what the device contains, the UUID comes from a different place. For example, ext4 file systems have a UUID field in their file system superblock, whereas LUKS volumes have a UUID in their LUKS header.

Canonically, probing a device to extract the UUID is done by libblkid from the util-linux package, but the logic can easily be re-implemented in other languages and changes rarely. minitrd comes with its own implementation to avoid cgo or running the blkid(8) program.

4. LUKS full-disk encryption unlocking (only on encrypted systems)

Unlocking a LUKS-encrypted volume is done in userspace. The kernel handles the crypto, but reading the metadata, obtaining the passphrase (or e.g. key material from a file) and setting up the device mapper table entries are done in user space.

initrd# modprobe algif_skcipher
initrd# cryptsetup luksOpen /dev/sda4 cryptroot1

After the user entered their passphrase, the root file system can be mounted:

initrd# mount /dev/dm-0 /mnt

5. Continuing the boot process (switch_root)

Now that everything is set up, we need to pass execution to the init program on the root file system with a careful sequence of chdir(2) , mount(2) , chroot(2) , chdir(2) and execve(2) system calls that is explained in this busybox switch_root comment.

initrd# mount -t devtmpfs dev /mnt/dev
initrd# exec switch_root -c /dev/console /mnt /init

To conserve RAM, the files in the temporary file system to which the initramfs archive is extracted are typically deleted.

How is an initramfs generated?

An initramfs “image” (more accurately: archive) is a compressed cpio archive. Typically, gzip compression is used, but the kernel supports a bunch of different algorithms and distributions such as Ubuntu are switching to lz4.

Generators typically prepare a temporary directory and feed it to the cpio(1) program. In minitrd, we read the files into memory and generate the cpio archive using the go-cpio package. We use the pgzip package for parallel gzip compression.

The following files need to go into the cpio archive:

minitrd Go userland

The minitrd binary is copied into the cpio archive as /init and will be run by the kernel after extracting the archive.

Like the rest of distri, minitrd is built statically without cgo, which means it can be copied as-is into the cpio archive.

Linux kernel modules

Aside from the modules.alias and modules.dep metadata files, the kernel modules themselves reside in e.g. /lib/modules/5.4.6/kernel and need to be copied into the cpio archive.

Copying all modules results in a ≈80 MiB archive, so it is common to only copy modules that are relevant to the initramfs’s features. This reduces archive size to ≈24 MiB.

The filtering relies on hard-coded patterns and module names. For example, disk encryption related modules are all kernel modules underneath kernel/crypto, plus kernel/drivers/md/dm-crypt.ko.

When generating a host-only initramfs (works on precisely the computer that generated it), some initramfs generators look at the currently loaded modules and just copy those.

Console Fonts and Keymaps

The kbd package’s setfont(8) and loadkeys(1) programs load console fonts and keymaps from /usr/share/consolefonts and /usr/share/keymaps, respectively.

Hence, these directories need to be copied into the cpio archive. Depending on whether the initramfs should be generic (work on many computers) or host-only (works on precisely the computer/settings that generated it), the entire directories are copied, or only the required font/keymap.

cryptsetup, setfont, loadkeys

These programs are (currently) required because minitrd does not implement their functionality.

As they are dynamically linked, not only the programs themselves need to be copied, but also the ELF dynamic linking loader (path stored in the .interp ELF section) and any ELF library dependencies.

For example, cryptsetup in distri declares the ELF interpreter /ro/glibc-amd64-2.27-3/out/lib/ld-linux-x86-64.so.2 and declares dependencies on shared libraries libcryptsetup.so.12, libblkid.so.1 and others. Luckily, in distri, packages contain a lib subdirectory containing symbolic links to the resolved shared library paths (hermetic packaging), so it is sufficient to mirror the lib directory into the cpio archive, recursing into shared library dependencies of shared libraries.

cryptsetup also requires the GCC runtime library libgcc_s.so.1 to be present at runtime, and will abort with an error message about not being able to call pthread_cancel(3) if it is unavailable.

time zone data

To print log messages in the correct time zone, we copy /etc/localtime from the host into the cpio archive.

minitrd outside of distri?

I currently have no desire to make minitrd available outside of distri. While the technical challenges (such as extending the generator to not rely on distri’s hermetic packages) are surmountable, I don’t want to support people’s initramfs remotely.

Also, I think that people’s efforts should in general be spent on rallying behind dracut and making it work faster, thereby benefiting all Linux distributions that use dracut (increasingly more). With minitrd, I have demonstrated that significant speed-ups are achievable.

Conclusion

It was interesting to dive into how an initramfs really works. I had been working with the concept for many years, from small tasks such as “debug why the encrypted root file system is not unlocked” to more complicated tasks such as “set up a root file system on DRBD for a high-availability setup”. But even with that sort of experience, I didn’t know all the details, until I was forced to implement every little thing.

As I suspected going into this exercise, dracut is much slower than it needs to be. Re-implementing its generation stage in a modern language instead of shell helps a lot.

Of course, my minitrd does a bit less than dracut, but not drastically so. The overall architecture is the same.

I hope my effort helps with two things:

1. As a teaching implementation: instead of wading through the various components that make up a modern initramfs (udev, systemd, various shell scripts, …), people can learn about how an initramfs works in a single place.

2. I hope the significant time difference motivates people to improve dracut.

Appendix: qemu development environment

Before writing any Go code, I did some manual prototyping. Learning how other people prototype is often immensely useful to me, so I’m sharing my notes here.

First, I copied all kernel modules and a statically built busybox binary:

% mkdir -p lib/modules/5.4.6
% cp -Lr /ro/lib/modules/5.4.6/* lib/modules/5.4.6/
% cp ~/busybox-1.22.0-amd64/busybox sh

To generate an initramfs from the current directory, I used:

% find . | cpio -o -H newc | pigz > /tmp/initrd

In distri’s Makefile, I append these flags to the QEMU invocation:

-kernel /tmp/kernel \
-initrd /tmp/initrd \
-append "root=/dev/mapper/cryptroot1 rdinit=/sh ro console=ttyS0,115200 rd.luks=1 rd.luks.uuid=63051f8a-54b9-4996-b94f-3cf105af2900 rd.luks.name=63051f8a-54b9-4996-b94f-3cf105af2900=cryptroot1 rd.vconsole.keymap=neo rd.vconsole.font=latarcyrheb-sun32 init=/init systemd.setenv=PATH=/bin rw vga=836"

The vga= mode parameter is required for loading font latarcyrheb-sun32.

Once in the busybox shell, I manually prepared the required mount points and kernel modules:

ln -s sh mount
ln -s sh lsmod
mkdir /proc /sys /run /mnt
mount -t proc proc /proc
mount -t sysfs sys /sys
mount -t devtmpfs dev /dev
modprobe virtio_pci
modprobe virtio_scsi

As a next step, I copied cryptsetup and dependencies into the initramfs directory:

% for f in /ro/cryptsetup-amd64-2.0.4-6/lib/*; do full=$(readlink -f $f); rel=$(echo $full | sed 's,^/,,g'); mkdir -p $(dirname $rel); install $full $rel; done
% ln -s ld-2.27.so ro/glibc-amd64-2.27-3/out/lib/ld-linux-x86-64.so.2
% cp /ro/glibc-amd64-2.27-3/out/lib/ld-2.27.so ro/glibc-amd64-2.27-3/out/lib/ld-2.27.so
% cp -r /ro/cryptsetup-amd64-2.0.4-6/lib ro/cryptsetup-amd64-2.0.4-6/
% mkdir -p ro/gcc-libs-amd64-8.2.0-3/out/lib64/
% cp /ro/gcc-libs-amd64-8.2.0-3/out/lib64/libgcc_s.so.1 ro/gcc-libs-amd64-8.2.0-3/out/lib64/libgcc_s.so.1
% ln -s /ro/gcc-libs-amd64-8.2.0-3/out/lib64/libgcc_s.so.1 ro/cryptsetup-amd64-2.0.4-6/lib
% cp -r /ro/lvm2-amd64-2.03.00-6/lib ro/lvm2-amd64-2.03.00-6/

In busybox, I used the following commands to unlock the root file system:

modprobe algif_skcipher
./cryptsetup luksOpen /dev/sda4 cryptroot1
mount /dev/dm-0 /mnt

Werte Tageslichtablehnende und Stahlbetonfans,

die nächste Tour ist ein Highlight für uns Kellerkinder!

Am Samstag, den 8. Februar 2020, werden wir uns den Atomschutzbunker unter dem Stadthaus in N1 anschauen. Falls ihr etwas über die Geschichte des Tiefbunkers erfahren möchtet, oder wissen wollt, welche Auswirkungen der Kalte Krieg auf Mannheim hatte, solltet ihr diesen Ausflug in den Untergrund nicht verpassen. Für RaumZeitLaborierende sind 10 Plätze bei MannheimTours für die Führung ab 15.30 Uhr reserviert. Bitte meldet euch bis zum 1. Februar 2020 per Mail an, wenn ihr dabei sein wollt.

Let’s have a blast
Falloutrattie

“Another One Bites the Crust” – Queen

Dear fellow RaumZeitLaboroyals!

Anlässlich des möglicherweise (oder auch doch noch nicht) bevorstehenden EU-Austritts des Vereinigten Königreichs, wollen wir uns am Freitag, den 31. Januar zum gemeinsamen BrexEat im RZL treffen.

Steckt eure schönste Tudor-Rosenkohl-Brosche ans Jäckchen und sattelt die Corgis, denn ab 18.30 Uhr stoßen wir auf das/die Wo/ahl unserer britischen Nachbarn an.

Chicken und Vegetable Tikka Masala mit Reis, sowie Indian Treacle Tart – für Veggie- und Beefeater wird es gleichermaßen Britisch-Indische Klassiker zum Dinieren geben.

Falls ihr zum Union Snack kommen wollt, meldet euch bitte bis zum 29.01. per Mail an und schreibt uns, ob ihr Fleisch esst oder nicht. Damit es auch in Zukunft noch “Keep calm and culinary on” heißt und wir weiter lustige Motto-Essfeste machen können, bitten wir um einen Unkostenbeitrag von mindestens 8 Euro pro Person.

Drool, Britannia!
Eure Chai Spice Girls

Zwar liegen hier seit Monaten mehrere fertige Artikel technischer Natur auf der Platte, nur kann ich davon noch nichts veröffentlichen, daher zu Abwechslung mal etwas aus dem Unterhaltungssektor.

Vor einigen Tagen habe ich mir X4: Foundations gekauft, da der Einstieg im ersten Szenario etwas anstrengend ist stelle ich nun als Backup meiner Notizen die - subjektiv betrachtet - wichtigsten in den Blog. Wahrscheinlich ist es wie mit den Vorgängern, in ein paar Wochen ist die Luft mit einem millionenschweren Selbstläuferunternehmen raus und Ende des Jahres wird dann von Grund auf neu angefangen. Nur muss ich mit diesem Post nach der nächsten längeren Pause nicht ewig in meinen Notizbüchern/Dateien suchen.

Hinweis: Alle Informationen meinerseits beziehen sich auf Version 2.60 HOTFIX 2 (GOG) und können mit vorherigen oder folgenden Versionen völlig nutzlos sein.

• Der wichtigste Hinweis zu Beginn des Spiels: Über die Taste H erreicht man die Hilfstutorials die man zu Beginn braucht und die man auch spielen sollte. In den Patch Notes für die kommende Version 3.00 an wird an mehreren Stellen eine Verbesserung der Einführung und der Tutorials aufgeführt.
• Zu Beginn sind Missionen der Argonen wichtig um schnell ein Ansehen von 10 zu erreichen und günstiger effektive Mining Schiffe kaufen zu können.
• Einstieg ins Mining: Es lohnt sich kleine Schürfer der Klasse M zum sammeln von Methan Gas zu nutzen und diese über die Gebiete der verschiedenen großen Fraktionen zu verteilen. Dadurch steigt langsam mit jeder dieser Fraktionen das Ansehen und eine Marktsättigung tritt nicht zu schnell ein. Manche Schiffe können auch nur im selben Sektor Ressourcen abbauen und verkaufen, andere Nachbarsektoren mitversorgen und im Bestfall global operieren, wegen des ersten Falles wäre ein Schiff der Klasse L zu Beginn gefährlich, da es schnell zu einer Marktsättigung führt. Warum man mal auch zu Beginn des Spiels einen absoluten Experten, dann aber etliche Male einen Neueinsteiger bekommt scheint ein generell offenes Fragezeichen zu sein.
• Fortgeschrittenes Mining: Wenn Schiffe später in der Lage sind in multiplen Sektoren Bergbau und Handel zu betreiben lohnen sich Schiffe der Kategorie L zum sammeln von Nvidium und Silizium. Erz bringt nur wenig Gewinn, dafür ist die Menge der möglichen Abnehmer größer. Damit eine Fraktion eine stabile Flottenstärke hat kann man dies mit Erz unterstützen, ansonsten lohnt es sich nur für eigene Stationen im späteren Spiel.
• Wer zu Beginn fix ein paar Millionen möchte für den kann ich den Beitrag Die ersten Millionen empfehlen. Eine kurze Anleitung wie man im Xenon Sektor Fehlerhafte Logik VII (zu erreichen durch die Verbindung von Gesegnete Vision zu Fehlerhafte Logik I und dort einem Highway im Süden), im "westlichen" Teil, ein größeres Schlachtschiff findet und es kapert. (Achtung: Es kann auch links "außerhalb" der initialen Karte liegen). Ich rate jedoch davon ab, das Schiff umgehend zu verkaufen. Es ist besser es zur Schiffswerft in Argon Prime zu schicken, dort die Marine Einheit wieder an Bord zu nehmen und die Ausstattung(Antrieb/Software) und die Verbrauchsgüter zuerst zu verkaufen. Der Wert solcher Dinge, wurde zumindest bei mir nicht bei jedem Schiff dem Verkaufspreis angerechnet, bei diesem Schiff geht einem dann doch ein siebenstelliger Betrag durch die Finger. Damit das Schiff das Ziel erreicht am Besten speichern und nicht auf die Karte schauen, so nutzt man die Spielmechanik aus, dass unbeachtete Schiffe sich nicht "normal" Verhalten sondern ungebremst durch Sprungtore/Verbindugen rasen.

Sektoren für das Mining

• In Profitabler Handel (TEL kontrolliert) gibt es viele Xenon und Kha'ak Angriffe, allerdings hatte ich hier mit einem Mangel an Abnehmern für Methan und Silizium noch keine Probleme.
• Dreieinigkeit VII ist ein PAR kontrollierter Sektor in dem ein Klasse M Mineralienschürfer in Ruhe mit Silizium für eine Verbesserung der Beziehung zur Fraktion arbeiten kann.
• Gesegnete Vision ist ein HOP kontrollierter Sektor, welcher mit Fehlerhafte Logik verbunden und stark umkämpft ist. Hier lohnt es sich sowohl mit Mineralien als auch Methan zu arbeiten.
• Zweiter Kontakt II Unruheherd ist mit mehreren Fraktionen versorgt, ein kleiner Händler mit Energiezellen ist hier recht zu Beginn zwecks Gewinn von Ansehen praktisch.
• Ianamus Zura IV ist der Teladi Hauptsektor direkt in dem eigentlich durchgehend mit Xenon gekämpft wird. Es lohnt sich hier ein billiges Schiff in die Handelsstation zu stellen, schlicht um mit der später zur Verfügung stehenden Teleportation die Fraktionsvertretetung unkompliziert zu erreichen.

Nach den ersten zehn Millionen: Konstruktionsaufträge

Wenn man mindestens zehn Millionen Credits auf dem Konto hat kommt man mit Bauaufträgen schnell voran.

• Es lohnt sich sehr die Hauptquest mit dem freundlichen Boronen Boso Ta früh abzuschließen, die Belohnungen führen hier zu einer gewissen Kostenreduktion bzgl. Pläne für künftige Stationen und generell entspannterem Vorgehen im Spiel.
• Regelmäßig auf dem Superhighway zwei Runden drehen und jeden Auftrag annehmen auch wenn man die Teile noch nicht alle bauen kann. Anschließen nach Möglichkeit direkt die notwendigen Bauplätze in der Nähe von Toren kaufen, schlicht damit dort später nicht eine andere Station den Platz blockiert. Achtung: Man mag die Karte von oben sehen und glauben, das richtige Gebiet eingegrenzt zu haben, aber das Spiel spielt in einem dreidimensionalen Raum insofern die Y-Achse nicht vergessen und die Karte drehen.
• Bei den Ressourcen nicht sparen und das globale Limit für den Einkaufspreis bei 100% lassen und lieber 10k Credits nehr hinterlegen als vorgeschlagen wird. Bei mir sind schon mehrere Male Bauaufträge hängen geblieben weil für die letzte Energiezelle ein Credit gefehlt hat (95% Limit und passgenau Credits hinterlegt). Bemerkt man dies nicht darf man dann wieder 50k für das Mieten des Bauschiffs zahlen.
• Der Abschluss der Konstruktionen dauert natürlich seine Zeit, aber wenn man 5,5 Millionen Gewinn machen kann ohne viel aktiven Aufwand ist es eine wertvolle Angelegenheit. Die Höhe der Belohnungen nimmt auch zu, ich habe gerade mehrere Aufträge für Verteidigungsstationen, die mich je 2 Millionen Credits gekostet haben, für die ich jedoch mehr als 15 Millionen ausgezahlt bekommen werde.
• Meiner Meinung nach lohnt sich ein eigenes Konstruktionsschiff zu Beginn nicht. Verteilt man über die Sektoren hinweg an jeder kritischen speziellen Station Satelliten findet man immer eines, welches man für 50K Credits anheuern kann. Mehrere Millionen für ein eigenes auszugeben, das auch nur an einer Stelle gleichzeitig arbeiten kann ist vielleicht im späten Spiel sinnvoll, wenn regelmäßig eine Station erweitert werden muss.
• Vorsicht: Wenn die Stationen fertig sind sie Eigentum des Auftraggebers, eine Station zur Produktion von Waren muss man also nicht mit umfangreichen Verteidigungsmaßnahmen versorgen, sofern dies nicht gewünscht ist.
• Eigene Stationen: Eine kleine Werft in umkämpften Gebieten anzubieten lohnt sich, vor allem wenn man mit den sich bekämpfenden Fraktionen befreundet ist. *hüstel* Es dauert zwar eine Weile bis man die Credits wieder hat, aber solange sich mindestens zwei Streiten kommt kontinuierlich Geld, meist aber auch zusätzlich von unbeteiligten Fraktionen. Hierzu muss man neben den Blaupausen der Schiffe auch die der Ausrüstungsteile besitzen, je größer die Auswahl, desto mehr wird ausgegeben. Da die Einkäufe, Reparaturen und Bauaufträge komplett von der KI Situation abhängen lässt sich hier natürlich keine regelmäßiger Gewinn-/Umsatz berechnen.
• Bei einer Werft sollte man zur Gewinnmaximierung auch zeitnah nach und nach die Ressourcen selbst bereitstellen können und die Module an der selben Station oder in deren Nähe anbringen. Ohne diese Eigenproduktion geht doch viel Geld verloren. Man kann natürlich den Spieß auch umdrehen und mit den Modulen zur Ressourcenverarbeitung anfangen.

At this year's 36th Chaos Communication Congress in Leipzig, I signed up to give a short introductory workshop for Julia. To my surprise the room was completely packed yesterday, even though the meeting was scheduled for 11am on day 4 ... Everyone at the session was extremely engaged and packaged with plenty of supporting and challenging questions about Julia. Luckily a bunch of masters from the Julia community were in the audience to help out with providing the in-depth details where I failed (tip of the hat to Keno Fischer and Valentin Churavy). Thanks for everyone in the room! I really enjoyed my time and as usual with these things I learned a lot.

As I mentioned during the session, the Jupyter notebooks I used are all available on github. They were originally made for a one-day introductory Julia course, which I presented in Paris a few weeks ago (details here). The material, however, should be self-explanatory and accessible to people completely new to Julia, but which already have some familiarity with programming of some kind. Main point is to get an idea of what Julia is like, seed a little curiosity about the language and provide links to plenty of further info (see also these links). Feel free to spread the word about the repo if you like the material.

With that said, I am happy to receive any feedback you might have about the session, the notebooks and the other material. I plan to keep doing such courses in the future and I'm always looking for ways how to improve ;).

Link	Licence
https://github.com/mfherbst/course_julia_day

Lately I have been doing programming for embedded systems such as the esp32 and esp8266, and additionally I did a course on embedded systems for my masters degree. This introduced me to the wonderful world of programming close to the hardware level, and inspired me to write this post about hardware peripherals.

What are Hardware Peripherals?

Hardware Peripherals are specialized pieces of silicon that are built into a processor. They are used to perform a diverse set of task. This includes controlling the processors clock speed, power management and communication with other devices. They are responsible for configuring the device operation and during operation are used to perform tasks in parallel with the main cores.

So what can these peripherals do?

Anyone who has ever looked into the data sheet of a microprocessor will know that these data sheets are long. The data sheet for the ARM cortex m7 CPU for example is about 2000 pages long. Which is to say that there are a lot of peripherals that can do a variety of things, for example:

• Analog Digital Converters (ADC) used for measuring analog signals
• Direct Memory Access Controllers (DMA) used for copying data from sensor to memory or the other way
• GPIO Interfaces used for pin management
• I2C and SPI Interfaces used for communicating with sensor devices
• PMC the power management controller
• Other Memory interfaces such as PCI or EBI

Using Peripherals

In order for us to use a peripheral, we have to complete a few steps:

1. Setup peripheral mode

2. Start peripheral task

3. Wait for peripheral to finish

All of this is done via memory mapped registers, which is to say that within the memory range of the processor there are dedicated areas of memory that do not map to a memory controller like an SDRAM, but are mapped to registers belonging to the peripherals. The peripherals use these registers as configuration values that change how the peripheral is working or if it is running, and some of the registers are not meant to be written to but instead are used to communicate the status of the peripheral back to the CPU.

All of this is described in the data sheet of the processor you are using. Every peripheral has a section describing what it can do, and what parameters can be changed via the memory mapped registers, as well as how the peripheral can be started, stopped and how to know when it is finished.

Since all of this is highly dependent on the platform you are using, it is hard to give you a clear cut way to use any peripheral. You will always have to refer back to the data sheet and look how to use the peripheral for your platform. But in order for you to get an idea on how to do this, let us look at an example.

Example

Every example is specific to the specific device we are using. For these examples we are going to look at the simple case of toggling a GPIO pin. The chip we are using is an embedded cortex m7 cpu, from atmel. It belongs to the atsame70 family of cpu’s. Datasheet

So all we want to do is let a led blink. To do this we will have to toggle the status of a pin, and all pins are managed by the GPIO peripheral. In the data sheet of this particular chip this peripheral is just called PIO. To be able to do this we first have to tell the PIO peripheral that it should take control of the pin and then tell it to configure the pin to be used as an output. After that we can change the pin state.

If you already looked into the data sheet you might have noticed so that there are multiple PIO peripherals and how the pins are mapped depends on the rest of the system. For the system that i am programming a led is connected to pin 19 on PIO C. So this is the pin I will be using in this example.

To achive an accurate timeout between turning the led on and off, we are going to use the real time timer peripheral on our device. It is in essence a configurable counter attached to a clock signal.

Let us do this in C

This example uses the C library provided by atmel which provides the correct memory addresses of the peripherals and exposes them to us as definitions and structures. By just using these we are automatically writing to the correct addresses.

	#include "atsame70.h" 
	
	void timeout_ms(int ms) {
		// restart timer and set prescaler to count every 32 clock cycles 
		// this corresponds to a 1ms clock cycle since the clock frequency is 32 kHz 
		RTT->RTT_MR = RTT_MR_RTPRES(0x20) | RTT_MR_RTTRST; 
		
		while ( (RTT->RTT_VR | RTT_VR_CRTV_Msk) < ms) {
			//wait for counter to have counted to desired timeout
		}
	}

	void blink_led() {
		//give control of the pin to the pio -> basically the running code
		ATSAME70_BASE_PIOC->PIO_PER = PIO_PC19; 
		ATSAME70_BASE_PIOC->PIO_OER = PIO_PC19;

		while(true) {
			//turn led on 
			ATSAME70_BASE_PIOC->PIO_SODR = PIO_PC19;
			
			timeout_ms(500); 
			
			//turn led off 
			ATSAME70_BASE_PIOC->PIO_CODR = PIO_PC19; 
			
			timeout_ms(500);
		}
}

Timeouts

Since the device can vary it’s clock speed it is not desirable to implement a delay with just waiting a specified amount of clock cycles. Instead we are going to use the atsame70 Real Time Timer (RTT).

How to configure the RTT correctly can be read in the functional description in the data sheet. In short we have to configure the clock source since there are two at different speeds. Scale how many clock cycles trigger the counter and reset the peripheral for the new setting to take affect.

To do this we have to write to a memory mapped register:

In the figure we can see all the registers that are connected to the RTT. All the values we need to configure are in the RTT_MR register. It is basically just a 32 bit value. But every bit has a meaning. The first 16 bits represent the 16 bit prescaler value, and there is also a bit to enable the peripheral and one to the reset it. Selecting the clock source is also done with one bit.

So what do we need to wait for a certain amount of ms:

1. Select the 32kHz clock src by setting the RTC1HZ bit in RTT_MR to 0

2. Setting the RTPRES 16 bit value to 32 in order for the counter to increase ever 32 clock cycles which corresponds to increase the counter value evey 1ms

3. Set the RTTDIS bit to 0 to not disable the rtt

4. Trigger the RTT reset by setting RTTRST bit to 1

All of these 4 steps can be done with one write to the RTT_MR register.

Afterwards the timer is running and we can read the value in RTT_VR to see how much time has passed.

Controlling the LED

The PIO peripheral that manages the pins of the device is a lot more complex than the RTT peripheral. Which means it has many more registers. Using these we can do fancy things like giving other peripherals such as the SPI peripheral control over the pins it needs to communicate.

But we are just interested in simply controlling a pin ourselfs. For this we need 4 different registers:

1. PIO_PER peripheral enable register

2. PIO_OER peripheral output enable register

3. PIO_SODR set output data register

4. PIO_CODR clear output data register

They all have the same structure so i am just going to show you one of them:

Basically for every pin controlled by the PIO there is a bit. So one PIO gives us control over 32 pins. To control a pin we have to do the following steps:

1. set PIO_PER pin bit to 1 to enable control of the PIO over the pin

2. set PIO_OER pin bit to 1 to set the pin into output mode

Now setting the PIO_SODR pin bit to 1 to pull the pin high and setting the PIO_CODR pin bit to 1 pulls the pin low again.

How does all of this look in Rust

For rust there is no official library from atmel, but there is a project called svd2rust that allows us to auto-generate a library that we can use to address the correct peripheral registers. All we need is the svd file of the processor we are using, this is an xml file describing all the peripherals and their register values.

	use atsame70q21::{Peripherals}
	
	fn timeout_ms(peripherals : & Peripherals, u32 ms) {
		let rtt = &peripherals.RTT;
		
		// restart timer and set prescaler to count every 32 clock cycles 
		// this corresponds to a 1ms clock cycle since the clock frequency is 32 kHz 
		rtt.rtt_mr.write( |w| {
			unsafe {w.rtpres().bits(0x20);}
			w.rttdis().clearbit();
			w.rttrst().set_bit()
		});
		while rtt.rtt_vr.read().crtv().bits() < ms {
			// wait for counter to have counted to desired timeout
		}
	}

	fn blink_led() {
		let peripherals = Peripherals::take().unwrap();
		
		let pioc = &peripherals.PIOC;
		
		//give control of the pin to the pio -> basically the running code
		pioc.pio_per.write( |w| w.p19().set_bit() );
		pioc.pio_oer.write( |w| w.p19().set_bit() );
		
		loop() {
			//turn led on 
			pioc.pio_sodr.write( |w| w.p19().set_bit() );
			
			timeout_ms(&peripherals, 500); 
			
			//turn led off 
			pioc.pio_codr.write( |w| w.p19().set_bit() );
			
			timeout_ms(&peripherals, 500);
		}
	}

The logic of the rust code is exactly the same as the C example, and since all of the actual functionality we are using is provided by the hardware and not by the language specifics the code looks mostly the same.

I hope you liked this little excursion into bare metal programming, i am sure i will return with more blog post regarding similar topics while i keep experimenting more with rust on bare metal systems.

If you missed the Julia day at Jussieu in Paris last week, but still want to get to know the programming language Julia a little, have no fear: I'll be doing an introductory Julia session at the 36th Chaos Communication Congress in Leipzig this year (on day 4, 11am, so be prepared to get up early ;) ). Find all the infos here.

The plan is to do something similar to the Julia day, just a little more condensed with more focus on showing things rather than explaining things. Overall the workshop will not be so much centred on really teaching Julia, much rather to show you the potential of the language and get you all set to start exploring Julia on your own.

Update: Details here

Congress Everywhere

Auch dieses Mal laden wir alle, die nicht persönlich auf dem 36C3 sein können, wieder herzlich ein, etwas Congress-Atmosphäre bei uns im RaumZeitLabor zu geniessen.

Zusammen schauen wir uns ausgewählte Talks live auf dem Beamer an. Und Essen gibt’s auch. Aller Voraussicht nach gibt es morgens einen Frühstücks-Bausatz bestehend aus Nutella und frischem Brot, abends einen Essens-Bausatz bestehend aus Dürüm, Gemüse und Vleisch. Bembel, Bier und diverse anti-alkoholische Getränke (u.a. 3 Sorten Mate!) werden im Kühlschrank bereitgestellt.

So einfach ist es: Auf https://status.raumzeitlabor.de/ schauen ob die Ampel grün ist, ggf. 0621 76231370 anrufen um ganz sicher zu sein, und ab ins RZL!!!

This Blogpost will investigate the impact of different power management policies for SATA devices in Linux with regard to their power consumption as well as their performance impact. Because after all, everyone likes to get more battery life for free, right?

We will briefly discuss the test setup, then take a look at several measurement results for both power and performance to at the end take a look how to leverage the found results in practice.

Overall, we will find that for SSDs the power management policies for SATA devices can make a significant difference in power consumption while having a negligible impact on performance at the same time.

Background

On a modern linux machine, several modes for power management of a SATA drive are available. These are

• max_performance: A disk is typically kept awake and running to get the best performance out of it. This is most indicative when thinking about spinning disks, as a spindown leads to inevitable significant latencies for the next access of the drive
• min_power: This mode prefers power saving over maximum performance. For spinning disks this for example implies spindowns to save power
• medium_power: A compromise between the aforementioned two.
• med_power_with_dipm: This mode configures the drive like medium_power does, but with additional Device Initiated Power Management. It uses the same configuration the Intel IRST Windows driver uses to for drives.

Setup and Test Procedure

Setup

The measurement was performed on laptops and their internal SSDs. Due to availability to the author, the measurements were done with a Crucial M550 and a Crucial MX500, both 1TB in size. Measurements were taken with

• Linux 5.3
• no applications opened (except for the terminal with the benchmarking process)
• screen turned off (only really relevant for power)
• standard system daemons still running

Power consumption

The power consumption measurements were done using this code, to further reduce noise, wifi was disabled as well. After the link power management policy was set, the system was let idling for 10 minutes to reduce any influences from other policies or activities from before. Afterwards, power consumpiton was measured over 15 minutes via the /sys-API of the machine’s battery controller. It was read every three seconds.

Three scenarios were tested for all available link power management policies:

• idle: no induced activity
• synchronous: activity right before reading the current power consumption
• asynchronous: activity in the middle of two power measurements

The entire procedure was repeated for all combinations of available link power management policies and scenarios (so in total 12 times).

Performance

After setting the link power management policy and let the system idle to ensure measurements would not be influenced by past activity. Idle time was chosen to be 15 minutes (slightly longer as for power, an additional precaution as the performance measurements were significantly shorter time-wise that the power measurements). Performance was then measured using fio 3.16 with this preset adapted from here using this script. As benchmarking is hard, the performance measurements are not intended to be an absolute statement of the drive’s performance, but rather intended as a ballpark measurement to get a feel for the performance impact of different link power management policies.

Results

Power consumption

MX500

M550

Performance

The measurements for the MX500 were very consistent when repeatedly measured. The measurements for the M550 were a bit flakey, so the fio-measurement on the M550 was performed three times and the performance characteristics shown are the respective medians over all three measurements for both throughput and latency.

Throughput

Latency

Latency information was gathered as part of the fio-measurements for the different link power management policies. The results (specifically lat in fio’s output) are denoted as average +/- standard deviation in microseconds to, again, get a ballpark estimate.

Conclusion

As the results clearly indicate, the power link management policy has a noticable impact on a computer’s power consumption, up to a third of its total under light load when we exclude the screen. The newest mode med_power_with_dipm proves to be both among the lowest consuming ones for all modes for the tested SSD models and also very consistent in this, whereas other modes are either equal, systematically higher or highly dependent of the scenario at play (for example the min_power mode on the MX500).

The performance impact, both in latency and in throughput, was, however, somewhere between measurable and completely negligible, the highest impact could be seen in the throughput of the M550 where the data still implies med_power_with_dipm to be the preferred choice.

Beware that the results in this post are only applicable to SSDs. HDDs might have significantly different performance and power characteristics due to spin-down and spin-up times and other factors. Furthermore, the aforementioned results will likely apply for SSDs in general, but were obviously only tested on certain models. Different models, especially from differend vendors, could have different characteristics.

Practical usage

If you want to check which policy is in place, you can take a look at the content of the files /sys/class/scsi_host/host[0-9]/link_power_management_policy, which indicate the applied policy or simply use

cat /sys/class/scsi_host/host*/link_power_management_policy

to see the policies. After all, if you didn’t configure anything, they should all be the same, so you’ll see what’s configured no matter which disk it is. To automatically set the desired policy, you can create a file /etc/udev/rules.d/disk-power.rules containing:

SUBSYSTEM=="scsi_host", KERNEL=="host*", ATTR{link_power_management_policy}="med_power_with_dipm"

that will set med_power_with_dipm for all SATA disks that will show up. Alternatively, if you use tlp, you don’t have to do anything, because (at least in the default configuration) tlp does already take care of setting this policy, at least for the primary SATA disk.

Appendix

Liteonit LCS-256, 256GB

One additional dataset was donated from an additional SSD, specifically a Liteonit LCS-256, sized at 256GB. Below you find the power measurements for this disk, the measurement procedure is roughly equal to the one outlined for Crucial’s MX500 and M550 above. We see that, while the exact numbers vary, the power profiles behave very similar, specifically to the ones of the MX500, and our conclusions apply for this disk as well.

If someone has a disk or SSD manufacturer not covered so far, feel invited to still send data to broaden the survey started here.

A few weeks ago on 21st and 22nd November of this year Pierre-Francois Loos invited me for two days to the Laboratoire de Chimie et Physique Quantiques of the Université Paul Sabatier Toulouse. On Thursday the 21st I had the chance to present our current status in DFTK and adcc at the lab's seminar. My talk ended up being an updated version of my talk at the Domcke group in Munich, which I held just in the previous month. After the talk and on Friday I had plenty of time to discuss with Titou, Anthony Scemama and Michel Caffarel about adcc, DFTK and their respective projects. The discussions were interesting from my end and ended up being a rather fruitful exchange of ideas. During the two days I certainly learned a lot.

As usual my slides and examples are attached below:

Link	Licence
Interdisciplinary software for electronic structure theory: adcc and DFTK (Slides seminar LCPQ)
DFTK and Julia examples (Tarball)
adcc examples (Notebook)

As part of my research stay at the Matherials team of ENPC Paris Tech and Inria I have been developing the density-functional toolkit, DFTK.jl, together with Antoine Levitt and Eric Cancès. Finally after about six months of joint effort on this Julia code, we just released a first preview in the form of version 0.0.1.

As I mentioned already in previous articles and talks the aim of DFTK is to bridge between mathematicians, computer scientists and materials scientists and to simplify mathematically-motivated research in this interdisciplinary subject. Currently we exclusively focus on a plane-wave discretisation of density-functional theory (PWDFT) as implemented in plenty of mature packages in the community (Abinit, Quantum Espresso, VASP, ...).

DFTK is mainly born from two realisations: Firstly, existing PWDFT progams have huge code bases, where reducing or altering the physical model to a case, which can be treated with rigorous mathematics is very challenging. As a result mathematical research is done in custom codes developed mostly for the purpose of a single project or research questions and findings hardly make it into a setting useful for practitioners. Secondly, such single-purpose custom codes are usually are not fast enough to treat the setting of real-world applications. This prevents verification of obtained results in the context actually relevant in practice. With DFTK we want to overcome this issue by allowing in one code to both implement toy problems and upscale them to the high-performance level needed in practice.

As of now, we're certainly not fully there, but given the short time, we're still proud of our feature list:

• Plane-wave basis sets
• All LDA and GGA functionals from libxc
• Modelling of Insulators and metals (Fermi-Dirac or Methfessel-Paxton smearing)
• GTH or HGH Pseudopotentials
• Exploitation of Brillouin zone symmetry for k-Point sampling
• Band structure computation
• Full access to intermediate quantities (density, Bloch wave)
• Three SCF algorithms (DIIS, NLsolve, damping)
• Close agreement with Abinit for a few thoroughly tested cases (silicon, graphite, manganese).
• Support for both single and double precision throughout the library for a small set of functionals. Support for arbitrary floating point types is on the way.

Recently we moved the code to JuliaMolSim a github organisation, where we want to collect Julia codes for performing molecular simulations in quantum chemistry and materials science. Along with this we registered the release with the MolSim Julia registry, which means that you can install DFTK by two simple steps:

1. Add the MolSim registry to your Julia installation. Type from a Julia REPL:

] registry add https://github.com/JuliaMolSim/MolSim.git

1. Install DFTK as usual, again from a REPL:

] add DFTK

For the time being, DFTK will probably stay in the pre-release stage, as we are not yet completely happy with the internal code structure and the API and we think some more restructuring should follow. Still, we consider the code now sufficiently advanced to suggest you to have a look and try it out :). With this naturally comes a small plea: If you discover something, which bothers you or something, which does not work, please open an issue on github and pose it for discussion. Also we are very happy if you want to contribute something, please just get going!

For further details and the DFTK source code, see the DFTK project page on github. Citations to the DFTK source code are possible using DOI 10.5281/zenodo.3541724.

Liebe RaumZeitLaborierende!

Bei unserem nächsten Ausflug geht die Post ab! Auch wenn der Leiter des Museums für Kommunikation in Frankfurt “Gold” mit Nachnamen heißt, dreht sich dort das meiste um die Farbe Gelb.

Am Sonntag, den 1. Dezember 2019, haben wir ab 13 Uhr die Möglichkeit durch die Dauerausstellung des ehemaligen Post-Museums geführt zu werden und zu schauen, welche Erfindungen und technischen Entwicklungen unsere heutige Kommunikation möglich machen. Falls euch interessiert, was ein Reiseruf ist, ihr alte Telefonzellen bewundern, einen Kraftpostbus und eine Briefsortieranlage von Nahem sehen wollt, dann solltet ihr bei dieser Adventstour dabei sein. Im Anschluss werden wir nach aktuellem Planungsstand auch die Funkstation auf dem Museumsdach besuchen können.

Für RaumZeitLaborierende ist diese Führung kostenlos, Nicht-Mitglieder bitten wir um 5 Euro für die RZL-Tourenkasse. Da diese Führung auf 15 Plätze beschränkt ist, bitte ich bis zum 24. November 2019 um Rückmeldung per elektronischem Briefchen.

Goldgelbe Grüße
FlederrattY

Over the part year or so a side project I have been working off and on has been the adcc code. This python module allows to perform excited states calculation for simulating molecular spectra based on algebraic-diagrammatic construction (ADC) methods. The speciality of the adcc code is that (a) multiple host programs are supported for supplying a Hartree-Fock reference, right now pyscf, Psi4, molsturm and veloxchem, and (b) that its hybrid C++/python design allows to implement a large part of the ADC procedure including iterative solver schemes in python and still achieve the speed required for larger ADC calculations. The code development has been a collaboration with multiple members from the old group of my PhD times, the Dreuw group from Heidelberg. Finally, today, we are publicly releasing the code following the submission of our paper on adcc last week (download link).

I have already talked about adcc and ADC methods before (see also my research interests), so I'll be brief with my summary about these. The ADC scheme builds upon the fact that the poles of the polarisation propagator, i.e. the two-particle Green's function, contains the physical information for describing excited electronic states and their properties. Using a Møller-Plesset partitioning of the Schrödinger Hamiltonian one may construct a perturbative expansion for said polarisation propagator. In the ADC approach this is done using a particular representation basis for the many-body states of the Schrödinger Hamiltonian, the so-called intermediate state basis. The outcome are a perturbative series of matrices, the so-called ADC matrices corresponding to the ADC(n) series of methods. The ADC matrices contain exactly the spectral information of the polarisation propagator consistent to order n of a Møller-Plesset expansion of the correlated ground state. Diagonalising this matrix, thus allows to obtain excitation energies and excited-state properties. For more details, see for example the theory section in the adcc documentation.

As we discuss in our paper, in adcc the basic procedure of building and diagonalising the ADC matrix is implemented in a hybrid C++/python code. The aim was to keep everything, including intermediate results, accessible from the python layer, while implementing the computationally intensive parts in C++. As a result, the code is comparable to C++-only implementations in speed, such that it can be used to e.g. treat biomolecular systems. The iterative diagonalisation procedure and other aspects of the numerics are implemented completely in python, facilitating experimenting on the numerical level in the future. Multiple variants of ADC are available up to and including ADC(3), i.e. a treatment of the polarisation propagator consistent to third-order. Originally adcc grew out of my desire to use another ADC code, which is developed in the Dreuw group, namely the adcman code, interactively from python. In its current state, however, adcc has well grown beyond being a plain wrapper around adcman. The internal code structure and workflows of both packages have very little in common, albeit the general methodology to solve ADC of both packages is certainly related. The design of adcc aims to simplify working with ADC methods as a developer, but also facilitating the use and extension of existing workflows by everyday users. For more details and a couple of examples, see the paper, or the Performing calculations with adcc section of the adcc documentation. Installing adcc is simple. Given that a few requirements (such as openblas on Linux) are available, it boils down to using pip:

pip install pybind11
pip install adcc

The full abstract reads

ADC-connect (adcc) is a hybrid python/C++ module for performing excited state calculations based on the algebraic-diagrammatic construction scheme for the polarisation propagator (ADC). Key design goal is to restrict adcc to this single purpose and facilitate connection to external packages, e.g., for obtaining the Hartree-Fock references, plotting spectra, or modelling solvents. Interfaces to four self-consistent field codes have already been implemented, namely pyscf, psi4, molsturm, and veloxchem. The computational workflow, including the numerical solvers, are implemented in python, whereas the working equations and other expensive expressions are done in C++. This equips adcc with adequate speed, making it a flexible toolkit for both rapid development of ADC-based computational spectroscopy methods as well as unusual computational workflows. This is demonstrated by three examples. Presently, ADC methods up to third order in perturbation theory are available in adcc, including the respective core-valence separation and spin-flip variants. Both restricted or unrestricted Hartree-Fock references can be employed.

One of my two NAS builds recently died, so I bought a new one until I find some time to debug the old one. Since a couple of people have been asking me what I would recommend nowadays based on my November 2016 article “Gigabit NAS (running CoreOS)”, I figured I would share the new hardware listing:

In November 2016 I paid only 225 CHF, i.e. 126 CHF less.

Why is this build so much more expensive? There are two major reasons:

The AM4 platform

The AM4 platform replaced the AM1 APU series as the cheapest broadly available AMD platform.

As you might have gathered from the links in the hardware listing above, I define “broadly available” as available at digitec, a large electronics shop in Zürich.

They offer same-day orders for pick-up in their Zürich location during Weekdays and on Saturdays, so it is kind of like being on a hardware support plan :-)

Unfortunately, the cheapest AM4 CPU is a lot more expensive (+ 23.31 CHF).

Also, there are (currently?) no AM4 mainboards with DC barrel power plugs, meaning more expensive ATX power supplies (+ 26.30 CHF) become necessary.

Additional components: fan and system disk

Definitely invest in the Noctua 120mm ULN (Ultra Low Noise) fan (+ 29.00 CHF). The fan that comes in the Silverstone case is pretty noisy, and that might be bothersome if you don’t have the luxury of stashing your NAS away in the basement.

In my last build, I had an SSD lying around that I used as system disk, this time I had to buy one (+ 27.50 CHF).

Note that I intentionally picked a SATA SSD over an M.2 SSD: the M.2 slot of the AB350 is on the back of the mainboard, so an M.2 SSD is harder to reach. The performance disadvantage of a SATA SSD compared to an M.2 SSD might be measurable, but irrelevant for my day-to-day usage. Quickly accessing the physical hardware is more important.

Yesterday we had the first instance of the Julia Paris Meetup. As the name suggests a couple of us Julia enthusiasts in the French capital got together for one evening of talks and chatting about everyone's favourite programming language. It was a great occasion to finally meet some people in person and gather around for some technical chit-chat till the late hours at one of the bars of the 11th arrondissement after the talks.

I myself was pretty excited about the evening and not quite sure what kind of people to expect. Unsurprisingly most people, who turned up had an academic background with focus on number crunching of some sort, mostly high-performance linear algebra or optimisation problems. To my big surprise, the number of people working in a industrial context was a lot larger than I expected, even though most did not use the language to a large extend in their everyday work. Still, after the evening I am yet again convinced that Julia is spreading beyond dusty desks in universities. Certainly, a great part in this plays the dedicated community of people, willing to invest a Sunday evening here and there to work on just the very thing required to advance the language and the Julia ecosystem step by step. Even though this has already been clear to me to some extent before Thursday, actually meeting the community and listening to stories and experiences from the Julia trenches, make the whole impression more vivid. I am already looking forward to the next meeting (details as always on https://julia-users-paris.github.io).

On that note, I was very happy, that I had the chance to play an active part in the evening by being one of the first to present some stories of my own. Naturally I talked about my endeavours with Julia while developing the DFTK code. Since I was not too sure about the audience, I tried to get across what makes Julia an ideal language for our efforts, what things we are currently working on and what will be our focus next and how we expect Julia to help. I'm not going to repeat the details about DFTK here, because these can be found in a previous article. See also the second half of this article. The slides of my talk can be downloaded here as usual:

Link	Licence
Electronic-structure simulations using Julia (Slides 1st Julia Paris Meetup)

Just sharing a quick convenience idea: merging Desktop and /tmp to use it as a quick drop directory. Sounds stupid? Bear with me.

XDG user directories

XDG user directories are a freedesktop.org de-facto standard for specifying typical directories within a user’s home, such as Documents, Downloads, Pictures, Music etc.. Filemanagers typically mark these xdg-user-dirs with special folder icons, so even if you haven’t explicitly bothered yet, you might have noticed.

Setting one of the XDG user directories allows your system (typically impersonated by your desktop environement) to ensure these folders are always existing, allows file managers to specifically mark them and to allow applications to save things there (for example applications can look up a user-specified download-folder to drop downloads there instead of reconfiguring each application separately). Also, many file managers and dialogs show you those XDG-user-dirs as quicklinks:

You can see that Desktop as well as the other xdg-dirs I use are accessible as quicklinks on the left.

Hijacking the desktop dir

I personally do not use files on my desktop, as I most of the time do not see my desktop anyways, therefore I have little use for the Desktop directory. However, as many file dialogs offer quicklinks to those directories, we can use the otherwise useless desktop dir for another purpose: putting a quick-drop directory there. In my case this is /tmp, for two reasons:

• easily accessible from the commandline to pull/push files from/to there, just two characters and a tab to type
• already set up as a tmpfs, so it lives in my computer’s memory and will be cleared and empty again upon next reboot

By specifying /tmp as the Desktop directory we now have it accessible as a quicklink in close to every file dialog and can quickly drop things from any terminal location there and then access them with two clicks from every filesystem dialog (and the other way round).

Setting xdg-user-dirs

To do so we now need to set that directory. This is done via the file ~/.config/user-dirs.dirs, which for our purpose should contain the line:

XDG_DESKTOP_DIR="/tmp"

You can set additional directories, the scheme will be always the same, XDG_<dirname>_DIR, you can query directories from the commandline via xdg-user-dir <dirname> to use them in your own scripts. <dirname> can be almost anything (although most software out there of course doesn’t consider any value for that).

drop-directory for display on your desktop

If you use a Desktop Environement that actually displays icons on your desktop, using /tmp is most likely unsatistfactory, as many applications use it for files and directories and therefore your desktop will be cluttered with those files.

Instead, we can create a directory specifically for that purpose, for example you could create a folder /drop in your filesystem root. This already retains the first property mentioned above, being accessible with few keystrokes (3 + tab: /dr<tab>, as /d<tab> collides with /dev). The second property we want is being in-memory, so we have simple regular clearance upon reboot and don’t collect clutter over time. We can achieve that by placing the line

tmpfs /drop tmpfs rw,nodev,noexec,nosuid,mode=1777 0 0

in /etc/fstab. This mounts a tmpfs to /drop in read-write mode.

nodev,noexec,nosuid are optional, but tightening permissions a little more rarely hurts. mode=1777 makes the directory readwriteeverythingable for every user on the system, but sets the sticky bit, so only the user placing things can delete them. Certainly not the most locked-down mode you could set, so potentially you want to tighten the screws here a little more.

Adapt the entry in ~/.config/user-dirs.dirs accordingly and you’re ready to go, now having an actual drop directory where you can simply drag and drop things onto your desktop.

Further reading

• ArchWiki on xdg-user-dirs
• /etc/fstab: common options

“I Want to Break Fast” - Queen

Dear fellow RaumZeitLaboroyals!

Anlässlich des möglicherweise (oder auch doch noch nicht) bevorstehenden EU-Austritts des Vereinigten Königreichs, wollen wir uns am Sonntag, den 27. Oktober zum gemeinsamen BrexEat im RZL treffen.

Steckt eure schönste Tudor-Rose-Spiegeleibrosche ans Jäckchen und sattelt die Corgis, denn ab 11.30 Uhr gibt es nicht nur einen Toast auf unsere britischen Nachbarn.

Würstchen, Hash Browns, Porridge, Bacon - für Veggie- und Beefeater wird es ein Full English Breakfast geben.

Falls ihr zum Union Snack kommen wollt, meldet euch bitte bis zum 23.10. per Mail an. Damit es auch in Zukunft noch “Keep calm and culinary on” heißt und wir weiter lustige Motto-Essfeste machen können, bitten wir um einen Unkostenbeitrag von mindestens 10 Euro pro Person.

God save our baked bean!
Eure Earls of Sandwich

A quick teaser for some Julia-related activities around Paris, I am involved with in the next months.

• 17 Oct 2019, 19:00, QuantStack (27 Rue du Chemin Vert 75011, Paris): The first Julia meet-up of Paris. We want to gather the people in and around Paris, who are interested in or working with Julia and stimulate exchanging experiences and ideas. I'll give a short talk about DFTK.jl and François Févotte will talk about AccurateArithmetic.jl. More details on https://julia-users-paris.github.io. Feel free to drop by if you are around!

• 13 Dec 2019, 09:00, Sorbonne Université, LJLL and LCT labs of Jussieu Campus. Julia Day (Journée Julia): I'll do an introductory session to Julia in the morning and talk a little bit about useful and helpful Julia packages (linear algebra, non-linear solvers, etc.) in the afternoon. followed by an introduction to DFTK.jl. For more details on the day see the website.

See the Conclusion for a summary if you’re impatient :-)

Motivation

Over the last few months, I have been developing a new index format for Debian Code Search. This required a lot of careful refactoring, re-implementation, debug tool creation and debugging.

Multiple factors motivated my work on a new index format:

1. The existing index format has a 2G size limit, into which we have bumped a few times, requiring manual intervention to keep the system running.

2. Debugging the existing system required creating ad-hoc debugging tools, which made debugging sessions unnecessarily lengthy and painful.

3. I wanted to check whether switching to a different integer compression format would improve performance (it does not).

4. I wanted to check whether storing positions with the posting lists would improve performance of identifier queries (= queries which are not using any regular expression features), which make up 78.2% of all Debian Code Search queries (it does).

I figured building a new index from scratch was the easiest approach, compared to refactoring the existing index to increase the size limit (point ①).

I also figured it would be a good idea to develop the debugging tool in lock step with the index format so that I can be sure the tool works and is useful (point ②).

Integer compression: TurboPFor

As a quick refresher, search engines typically store document IDs (representing source code files, in our case) in an ordered list (“posting list”). It usually makes sense to apply at least a rudimentary level of compression: our existing system used variable integer encoding.

TurboPFor, the self-proclaimed “Fastest Integer Compression” library, combines an advanced on-disk format with a carefully tuned SIMD implementation to reach better speeds (in micro benchmarks) at less disk usage than Russ Cox’s varint implementation in github.com/google/codesearch.

If you are curious about its inner workings, check out my “TurboPFor: an analysis”.

Applied on the Debian Code Search index, TurboPFor indeed compresses integers better:

Disk space

Switching to TurboPFor (via cgo) for storing and reading the index results in a slight speed-up of a dcs replay benchmark, which is more pronounced the more i/o is required.

Query speed (regexp, cold page cache)

Query speed (regexp, warm page cache)

Overall, TurboPFor is an all-around improvement in efficiency, albeit with a high cost in implementation complexity.

Positional index: trade more disk for faster queries

This section builds on the previous section: all figures come from the TurboPFor index, which can optionally support positions.

Conceptually, we’re going from:

type docid uint32
type index map[trigram][]docid

…to:

type occurrence struct {
    doc docid
    pos uint32 // byte offset in doc
}
type index map[trigram][]occurrence

The resulting index consumes more disk space, but can be queried faster:

1. We can do fewer queries: instead of reading all the posting lists for all the trigrams, we can read the posting lists for the query’s first and last trigram only.
   This is one of the tricks described in the paper “AS-Index: A Structure For String Search Using n-grams and Algebraic Signatures” (PDF), and goes a long way without incurring the complexity, computational cost and additional disk usage of calculating algebraic signatures.

2. Verifying the delta between the last and first position matches the length of the query term significantly reduces the number of files to read (lower false positive rate).

3. The matching phase is quicker: instead of locating the query term in the file, we only need to compare a few bytes at a known offset for equality.

4. More data is read sequentially (from the index), which is faster.

Disk space

A positional index consumes significantly more disk space, but not so much as to pose a challenge: a Hetzner EX61-NVME dedicated server (≈ 64 €/month) provides 1 TB worth of fast NVMe flash storage.

The idea behind the positional index (posrel) is to not store a (doc,pos) tuple on disk, but to store positions, accompanied by a stream of doc/pos relationship bits: 1 means this position belongs to the next document, 0 means this position belongs to the current document.

This is an easy way of saving some space without modifying the TurboPFor on-disk format: the posrel technique reduces the index size to about ¾.

With the increase in size, the Linux page cache hit ratio will be lower for the positional index, i.e. more data will need to be fetched from disk for querying the index.

As long as the disk can deliver data as fast as you can decompress posting lists, this only translates into one disk seek’s worth of additional latency. This is the case with modern NVMe disks that deliver thousands of MB/s, e.g. the Samsung 960 Pro (used in Hetzner’s aforementioned EX61-NVME server).

The values were measured by running dcs du -h /srv/dcs/shard*/full without and with the -pos argument.

Bytes read

A positional index requires fewer queries: reading only the first and last trigram’s posting lists and positions is sufficient to achieve a lower (!) false positive rate than evaluating all trigram’s posting lists in a non-positional index.

As a consequence, fewer files need to be read, resulting in fewer bytes required to read from disk overall.

As an additional bonus, in a positional index, more data is read sequentially (index), which is faster than random i/o, regardless of the underlying disk.

The values were measured by running iostat -d 25 just before running bench.zsh on an otherwise idle system.

Query speed

Even though the positional index is larger and requires more data to be read at query time (see above), thanks to the C TurboPFor library, the 2 queries on a positional index are roughly as fast as the n queries on a non-positional index (≈4s instead of ≈3s).

This is more than made up for by the combined i/o matching stage, which shrinks from ≈18.5s (7.1s i/o + 11.4s matching) to ≈1.3s.

Note that identifier query i/o was sped up not just by needing to read fewer bytes, but also by only having to verify bytes at a known offset instead of needing to locate the identifier within the file.

Conclusion

The new index format is overall slightly more efficient. This disk space efficiency allows us to introduce a positional index section for the first time.

Most Debian Code Search queries are positional queries (78.2%) and will be answered much quicker by leveraging the positions.

Bottomline, it is beneficial to use a positional index on disk over a non-positional index in RAM.

Last week, from Wednesday to Friday, I paid the Technical University of Munich (TUM) a short visit for two great opportunities to present my work: Once in the theoretical chemistry group of Professor Wolfgang Domcke and once at the annual meeting of the modeling, analysis and simulation of molecular systems (MoAnSi) interest group, a crowd consisting mostly of mathematicians and fellow modelling scientists.

Talk at Domcke group

The first presentation I gave last Wednesday in the Domcke group, where I talked about challenges and approaches to interdisciplinary software projects. I also presented two projects of my own, namely DFTK and adcc. About these codes I already gave a few details in previous articles and thus be rather brief with respect to details about them.

In the part of the talk on the plane-wave density-functional theory code DFTK I mainly focused on the question why we decided to use Julia as a programming language. For this I summarised Julia's capabilities and performance and gave a short teaser of Julia code in a Jupyter notebook. This notebook shows a Julia implementation of a Jacobi-Davidson iterative eigensolver and discusses concrete instantiations of the code in various situations. This includes a mixed-precision algorithm, which transfers intermediate results obtained in a lower precision (e.g. single precision) to higher (i.e. double) precision and then continues the iterations at this level. Other examples were diagonalisations using sparse matrices or GPU computations. Most notably, for all these cases the actual Jacobi-Davidson code was only written once and not explictly adapted to fit the respective datastructures or computational backends. Last, but not least the notebook teasered a small automatic differentiation example as well.

The main focus of the talk, however, was the adcc code, which implements the algebraic-diagrammatic construction scheme for the polarisation propagator (ADC) and allows to drive this computation from any SCF code using a python-based interface. In the presentation I sketch content from our upcoming software paper on adcc and present three examples for calculations, which we are able to do with only few lines of python code. This includes an analysis of the core-valence separation (CVS) error for water, a sophisticated combination of freezing extra core and valence orbitals alongside the CVS and a case of an ADC(2) modelling of nile red (426 basis functions) in an explicit solvent model (polarisable embedding). The code for the second example, namely the combination of CVS with freezing other orbitals, was also shown in an example notebook. Especially this part of the talk was well-received, providing fruit for many ADC-related and adcc-related discussions afterwards.

MoAnSi workshop

Directly after the day at the Domcke group I attended the MoAnSi meeting, which took place last Thursday and Friday, bringing together a bunch of mathematicians interested in computational methods for molecular science. Similar to other interdisciplinary meetings overlapping chemistry and maths, like the one in Oberwolfach, the atmosphere was friendly and open. Plenty of discussions were stimulating for thought about fundamental aspects of quantum chemistry, one usually does not think about as a chemist.

For this reason my second talk was tailored a bit more to the mathematician crowd, which meant that I focused more on DFTK and how it could be used in the context of mathematically-driven research of density-functional theory. Apart from the slides and the Julia examples I also presented some actual DFTK code, emphasising how Julia leads to extremely concise and readable programs. During the Q&A, I mentioned a blog article about a Julia case study using the language for a petascale computation. The respective project is the Celeste code and a summary of the hurdles and difficulties can be found in a post by Keno Fischer on the Julia Computing Blog.

Slides and notebooks for both talks are linked in the main text above or can be downloaded here:

Link	Licence
Interdisciplinary software for electronic structure theory: adcc and DFTK (Slides seminar Domcke group)
Two Julia examples (Notebook)
adcc Demo: Combining CVS and frozen orbitals (Notebook)
DFTK: The density-functional toolkit (Slides MoAnSi talk)

Over the last year or so I have worked on a research linux distribution in my spare time. It’s not a distribution for researchers (like Scientific Linux), but my personal playground project to research linux distribution development, i.e. try out fresh ideas.

This article focuses on the package format and its advantages, but there is more to distri, which I will cover in upcoming blog posts.

Motivation

I was a Debian Developer for the 7 years from 2012 to 2019, but using the distribution often left me frustrated, ultimately resulting in me winding down my Debian work.

Frequently, I was noticing a large gap between the actual speed of an operation (e.g. doing an update) and the possible speed based on back of the envelope calculations. I wrote more about this in my blog post “Package managers are slow”.

To me, this observation means that either there is potential to optimize the package manager itself (e.g. apt), or what the system does is just too complex. While I remember seeing some low-hanging fruit¹, through my work on distri, I wanted to explore whether all the complexity we currently have in Linux distributions such as Debian or Fedora is inherent to the problem space.

I have completed enough of the experiment to conclude that the complexity is not inherent: I can build a Linux distribution for general-enough purposes which is much less complex than existing ones.

① Those were low-hanging fruit from a user perspective. I’m not saying that fixing them is easy in the technical sense; I know too little about apt’s code base to make such a statement.

Key idea: packages are images, not archives

One key idea is to switch from using archives to using images for package contents. Common package managers such as dpkg(1) use tar(1) archives with various compression algorithms.

distri uses SquashFS images, a comparatively simple file system image format that I happen to be familiar with from my work on the gokrazy Raspberry Pi 3 Go platform.

This idea is not novel: AppImage and snappy also use images, but only for individual, self-contained applications. distri however uses images for distribution packages with dependencies. In particular, there is no duplication of shared libraries in distri.

A nice side effect of using read-only image files is that applications are immutable and can hence not be broken by accidental (or malicious!) modification.

Key idea: separate hierarchies

Package contents are made available under a fully-qualified path. E.g., all files provided by package zsh-amd64-5.6.2-3 are available under /ro/zsh-amd64-5.6.2-3. The mountpoint /ro stands for read-only, which is short yet descriptive.

Perhaps surprisingly, building software with custom prefix values of e.g. /ro/zsh-amd64-5.6.2-3 is widely supported, thanks to:

1. Linux distributions, which build software with prefix set to /usr, whereas FreeBSD (and the autotools default), which build with prefix set to /usr/local.

2. Enthusiast users in corporate or research environments, who install software into their home directories.

Because using a custom prefix is a common scenario, upstream awareness for prefix-correctness is generally high, and the rarely required patch will be quickly accepted.

Key idea: exchange directories

Software packages often exchange data by placing or locating files in well-known directories. Here are just a few examples:

• gcc(1) locates the libusb(3) headers via /usr/include
• man(1) locates the nginx(1) manpage via /usr/share/man.
• zsh(1) locates executable programs via PATH components such as /bin

In distri, these locations are called exchange directories and are provided via FUSE in /ro.

Exchange directories come in two different flavors:

1. global. The exchange directory, e.g. /ro/share, provides the union of the share sub directory of all packages in the package store.
   Global exchange directories are largely used for compatibility, see below.

2. per-package. Useful for tight coupling: e.g. irssi(1) does not provide any ABI guarantees, so plugins such as irssi-robustirc can declare that they want e.g. /ro/irssi-amd64-1.1.1-1/out/lib/irssi/modules to be a per-package exchange directory and contain files from their lib/irssi/modules.

Search paths sometimes need to be fixed

Programs which use exchange directories sometimes use search paths to access multiple exchange directories. In fact, the examples above were taken from gcc(1) ’s INCLUDEPATH, man(1) ’s MANPATH and zsh(1) ’s PATH. These are prominent ones, but more examples are easy to find: zsh(1) loads completion functions from its FPATH.

Some search path values are derived from --datadir=/ro/share and require no further attention, but others might derive from e.g. --prefix=/ro/zsh-amd64-5.6.2-3/out and need to be pointed to an exchange directory via a specific command line flag.

FHS compatibility

Global exchange directories are used to make distri provide enough of the Filesystem Hierarchy Standard (FHS) that third-party software largely just works. This includes a C development environment.

I successfully ran a few programs from their binary packages such as Google Chrome, Spotify, or Microsoft’s Visual Studio Code.

Fast package manager

I previously wrote about how Linux distribution package managers are too slow.

distri’s package manager is extremely fast. Its main bottleneck is typically the network link, even at high speed links (I tested with a 100 Gbps link).

Its speed comes largely from an architecture which allows the package manager to do less work. Specifically:

1. Package images can be added atomically to the package store, so we can safely skip fsync(2) . Corruption will be cleaned up automatically, and durability is not important: if an interactive installation is interrupted, the user can just repeat it, as it will be fresh on their mind.

2. Because all packages are co-installable thanks to separate hierarchies, there are no conflicts at the package store level, and no dependency resolution (an optimization problem requiring SAT solving) is required at all.
   In exchange directories, we resolve conflicts by selecting the package with the highest monotonically increasing distri revision number.

3. distri proves that we can build a useful Linux distribution entirely without hooks and triggers. Not having to serialize hook execution allows us to download packages into the package store with maximum concurrency.

4. Because we are using images instead of archives, we do not need to unpack anything. This means installing a package is really just writing its package image and metadata to the package store. Sequential writes are typically the fastest kind of storage usage pattern.

Fast installation also make other use-cases more bearable, such as creating disk images, be it for testing them in qemu(1) , booting them on real hardware from a USB drive, or for cloud providers such as Google Cloud.

Fast package builder

Contrary to how distribution package builders are usually implemented, the distri package builder does not actually install any packages into the build environment.

Instead, distri makes available a filtered view of the package store (only declared dependencies are available) at /ro in the build environment.

This means that even for large dependency trees, setting up a build environment happens in a fraction of a second! Such a low latency really makes a difference in how comfortable it is to iterate on distribution packages.

Package stores

In distri, package images are installed from a remote package store into the local system package store /roimg, which backs the /ro mount.

A package store is implemented as a directory of package images and their associated metadata files.

You can easily make available a package store by using distri export.

To provide a mirror for your local network, you can periodically distri update from the package store you want to mirror, and then distri export your local copy. Special tooling (e.g. debmirror in Debian) is not required because distri install is atomic (and update uses install).

Producing derivatives is easy: just add your own packages to a copy of the package store.

The package store is intentionally kept simple to manage and distribute. Its files could be exchanged via peer-to-peer file systems, or synchronized from an offline medium.

distri’s first release

distri works well enough to demonstrate the ideas explained above. I have branched this state into branch jackherer, distri’s first release code name. This way, I can keep experimenting in the distri repository without breaking your installation.

From the branch contents, our autobuilder creates:

1. disk images, which…

   • can be tested on real hardware
   • can be tested in qemu
   • can be tested in virtualbox
   • can be tested in docker
   • can be tested on Google Cloud

2. a package repository. Installations can pick up new packages with distri update.

3. documentation for the release.

   • Definitely check out the “Cool things to try” README section.

The project website can be found at https://distr1.org. The website is just the README for now, but we can improve that later.

The repository can be found at https://github.com/distr1/distri

Project outlook

Right now, distri is mainly a vehicle for my spare-time Linux distribution research. I don’t recommend anyone use distri for anything but research, and there are no medium-term plans of that changing. At the very least, please contact me before basing anything serious on distri so that we can talk about limitations and expectations.

I expect the distri project to live for as long as I have blog posts to publish, and we’ll see what happens afterwards. Note that this is a hobby for me: I will continue to explore, at my own pace, parts that I find interesting.

My hope is that established distributions might get a useful idea or two from distri.

There’s more to come: subscribe to the distri feed

I don’t want to make this post too long, but there is much more!

Please subscribe to the following URL in your feed reader to get all posts about distri:

https://michael.stapelberg.ch/posts/tags/distri/feed.xml

Next in my queue are articles about hermetic packages and good package maintainer experience (including declarative packaging).

Feedback or questions?

I’d love to discuss these ideas in case you’re interested!

Please send feedback to the distri mailing list so that everyone can participate!

I measured how long the most popular Linux distribution’s package manager take to install small and large packages (the ack(1p) source code search Perl script and qemu, respectively).

Where required, my measurements include metadata updates such as transferring an up-to-date package list. For me, requiring a metadata update is the more common case, particularly on live systems or within Docker containers.

All measurements were taken on an Intel(R) Core(TM) i9-9900K CPU @ 3.60GHz running Docker 1.13.1 on Linux 4.19, backed by a Samsung 970 Pro NVMe drive boasting many hundreds of MB/s write performance.

See Appendix B for details on the measurement method and command outputs.

Measurements

Keep in mind that these are one-time measurements. They should be indicative of actual performance, but your experience may vary.

ack (small Perl program)

qemu (large C program)

The difference between the slowest and fastest package managers is 30x!

How can Alpine’s apk and Arch Linux’s pacman be an order of magnitude faster than the rest? They are doing a lot less than the others, and more efficiently, too.

Pain point: too much metadata

For example, Fedora transfers a lot more data than others because its main package list is 60 MB (compressed!) alone. Compare that with Alpine’s 734 KB APKINDEX.tar.gz.

Of course the extra metadata which Fedora provides helps some use case, otherwise they hopefully would have removed it altogether. The amount of metadata seems excessive for the use case of installing a single package, which I consider the main use-case of an interactive package manager.

I expect any modern Linux distribution to only transfer absolutely required data to complete my task.

Pain point: no concurrency

Because they need to sequence executing arbitrary package maintainer-provided code (hooks and triggers), all tested package managers need to install packages sequentially (one after the other) instead of concurrently (all at the same time).

In my blog post “Can we do without hooks and triggers?”, I outline that hooks and triggers are not strictly necessary to build a working Linux distribution.

Thought experiment: further speed-ups

Strictly speaking, the only required feature of a package manager is to make available the package contents so that the package can be used: a program can be started, a kernel module can be loaded, etc.

By only implementing what’s needed for this feature, and nothing more, a package manager could likely beat apk’s performance. It could, for example:

• skip archive extraction by mounting file system images (like AppImage or snappy)
• use compression which is light on CPU, as networks are fast (like apk)
• skip fsync when it is safe to do so, i.e.:
  • package installations don’t modify system state
  • atomic package installation (e.g. an append-only package store)
  • automatically clean up the package store after crashes

Current landscape

Here’s a table outlining how the various package managers listed on Wikipedia’s list of software package management systems fare:

Conclusion

As per the current landscape, there is no distribution-scoped package manager which uses images and leaves out hooks and triggers, not even in smaller Linux distributions.

I think that space is really interesting, as it uses a minimal design to achieve significant real-world speed-ups.

I have explored this idea in much more detail, and am happy to talk more about it in my post “Introducing the distri research linux distribution".

Appendix A: related work

There are a couple of recent developments going into the same direction:

• “Revisiting How We Put Together Linux Systems” describes mounting app bundles
• Android Q uses ext4 loopback images
• The Haiku Operating System’s package manager Haiku Depot uses images

Appendix B: measurement details

ack

You can expand each of these:

% docker run -t -i fedora /bin/bash
[root@722e6df10258 /]# time dnf install -y ack
Fedora Modular 30 - x86_64            4.4 MB/s | 2.7 MB     00:00
Fedora Modular 30 - x86_64 - Updates  3.7 MB/s | 2.4 MB     00:00
Fedora 30 - x86_64 - Updates           17 MB/s |  19 MB     00:01
Fedora 30 - x86_64                     31 MB/s |  70 MB     00:02
[…]
Install  44 Packages

Total download size: 13 M
Installed size: 42 M
[…]
real	0m29.498s
user	0m22.954s
sys	0m1.085s

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -i perl5.28.2-ack-2.28'
unpacking channels...
created 2 symlinks in user environment
installing 'perl5.28.2-ack-2.28'
these paths will be fetched (14.91 MiB download, 80.83 MiB unpacked):
  /nix/store/57iv2vch31v8plcjrk97lcw1zbwb2n9r-perl-5.28.2
  /nix/store/89gi8cbp8l5sf0m8pgynp2mh1c6pk1gk-attr-2.4.48
  /nix/store/gkrpl3k6s43fkg71n0269yq3p1f0al88-perl5.28.2-ack-2.28-man
  /nix/store/iykxb0bmfjmi7s53kfg6pjbfpd8jmza6-glibc-2.27
  /nix/store/k8lhqzpaaymshchz8ky3z4653h4kln9d-coreutils-8.31
  /nix/store/svgkibi7105pm151prywndsgvmc4qvzs-acl-2.2.53
  /nix/store/x4knf14z1p0ci72gl314i7vza93iy7yc-perl5.28.2-File-Next-1.16
  /nix/store/zfj7ria2kwqzqj9dh91kj9kwsynxdfk0-perl5.28.2-ack-2.28
copying path '/nix/store/gkrpl3k6s43fkg71n0269yq3p1f0al88-perl5.28.2-ack-2.28-man' from 'https://cache.nixos.org'...
copying path '/nix/store/iykxb0bmfjmi7s53kfg6pjbfpd8jmza6-glibc-2.27' from 'https://cache.nixos.org'...
copying path '/nix/store/x4knf14z1p0ci72gl314i7vza93iy7yc-perl5.28.2-File-Next-1.16' from 'https://cache.nixos.org'...
copying path '/nix/store/89gi8cbp8l5sf0m8pgynp2mh1c6pk1gk-attr-2.4.48' from 'https://cache.nixos.org'...
copying path '/nix/store/svgkibi7105pm151prywndsgvmc4qvzs-acl-2.2.53' from 'https://cache.nixos.org'...
copying path '/nix/store/k8lhqzpaaymshchz8ky3z4653h4kln9d-coreutils-8.31' from 'https://cache.nixos.org'...
copying path '/nix/store/57iv2vch31v8plcjrk97lcw1zbwb2n9r-perl-5.28.2' from 'https://cache.nixos.org'...
copying path '/nix/store/zfj7ria2kwqzqj9dh91kj9kwsynxdfk0-perl5.28.2-ack-2.28' from 'https://cache.nixos.org'...
building '/nix/store/q3243sjg91x1m8ipl0sj5gjzpnbgxrqw-user-environment.drv'...
created 56 symlinks in user environment
real	0m 14.02s
user	0m 8.83s
sys	0m 2.69s

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y ack-grep)
Get:1 http://cdn-fastly.deb.debian.org/debian sid InRelease [233 kB]
Get:2 http://cdn-fastly.deb.debian.org/debian sid/main amd64 Packages [8270 kB]
Fetched 8502 kB in 2s (4764 kB/s)
[…]
The following NEW packages will be installed:
  ack ack-grep libfile-next-perl libgdbm-compat4 libgdbm5 libperl5.26 netbase perl perl-modules-5.26
The following packages will be upgraded:
  perl-base
1 upgraded, 9 newly installed, 0 to remove and 60 not upgraded.
Need to get 8238 kB of archives.
After this operation, 42.3 MB of additional disk space will be used.
[…]
real	0m9.096s
user	0m2.616s
sys	0m0.441s

% docker run -t -i archlinux/base
[root@9604e4ae2367 /]# time (pacman -Sy && pacman -S --noconfirm ack)
:: Synchronizing package databases...
 core            132.2 KiB  1033K/s 00:00
 extra          1629.6 KiB  2.95M/s 00:01
 community         4.9 MiB  5.75M/s 00:01
[…]
Total Download Size:   0.07 MiB
Total Installed Size:  0.19 MiB
[…]
real	0m3.354s
user	0m0.224s
sys	0m0.049s

% docker run -t -i alpine
/ # time apk add ack
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
(1/4) Installing perl-file-next (1.16-r0)
(2/4) Installing libbz2 (1.0.6-r7)
(3/4) Installing perl (5.28.2-r1)
(4/4) Installing ack (3.0.0-r0)
Executing busybox-1.30.1-r2.trigger
OK: 44 MiB in 18 packages
real	0m 0.96s
user	0m 0.25s
sys	0m 0.07s

qemu

You can expand each of these:

% docker run -t -i fedora /bin/bash
[root@722e6df10258 /]# time dnf install -y qemu
Fedora Modular 30 - x86_64            3.1 MB/s | 2.7 MB     00:00
Fedora Modular 30 - x86_64 - Updates  2.7 MB/s | 2.4 MB     00:00
Fedora 30 - x86_64 - Updates           20 MB/s |  19 MB     00:00
Fedora 30 - x86_64                     31 MB/s |  70 MB     00:02
[…]
Install  262 Packages
Upgrade    4 Packages

Total download size: 172 M
[…]
real	1m7.877s
user	0m44.237s
sys	0m3.258s

% docker run -t -i nixos/nix
39e9186422ba:/# time sh -c 'nix-channel --update && nix-env -i qemu-4.0.0'
unpacking channels...
created 2 symlinks in user environment
installing 'qemu-4.0.0'
these paths will be fetched (262.18 MiB download, 1364.54 MiB unpacked):
[…]
real	0m 38.49s
user	0m 26.52s
sys	0m 4.43s

% docker run -t -i debian:sid
root@b7cc25a927ab:/# time (apt update && apt install -y qemu-system-x86)
Get:1 http://cdn-fastly.deb.debian.org/debian sid InRelease [149 kB]
Get:2 http://cdn-fastly.deb.debian.org/debian sid/main amd64 Packages [8426 kB]
Fetched 8574 kB in 1s (6716 kB/s)
[…]
Fetched 151 MB in 2s (64.6 MB/s)
[…]
real	0m51.583s
user	0m15.671s
sys	0m3.732s

% docker run -t -i archlinux/base
[root@9604e4ae2367 /]# time (pacman -Sy && pacman -S --noconfirm qemu)
:: Synchronizing package databases...
 core       132.2 KiB   751K/s 00:00
 extra     1629.6 KiB  3.04M/s 00:01
 community    4.9 MiB  6.16M/s 00:01
[…]
Total Download Size:   123.20 MiB
Total Installed Size:  587.84 MiB
[…]
real	1m2.475s
user	0m9.272s
sys	0m2.458s

% docker run -t -i alpine
/ # time apk add qemu-system-x86_64
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/main/x86_64/APKINDEX.tar.gz
fetch http://dl-cdn.alpinelinux.org/alpine/v3.10/community/x86_64/APKINDEX.tar.gz
[…]
OK: 78 MiB in 95 packages
real	0m 2.43s
user	0m 0.46s
sys	0m 0.09s