A previous post introduced the SPURV Android compatibility layer for Wayland based Linux environment.
In this post we're going to dig into how you can run an Android application on the very common i.MX6 based Nitrogen6_MAX board from Boundary Devices.

Build SPURV for Nitrogen6_MAX

Build Android

mkdir android; cd android
repo init -u https://android.googlesource.com/platform/manifest -b android-9.0.0_r10
git clone https://gitlab.collabora.com/zodiac/android_manifest.git .repo/local_manifests/
repo sync -j15
. build/envsetup.sh
lunch spurv-eng
make -j12
cd ..

Build Linux Kernel

git clone https://gitlab.collabora.com/zodiac/linux.git -b android-container
cd linux
sh ../android/device/freedesktop/spurv/build-kernel.sh
cd ..

Create root filesystem

Just a kernel does not make an OS, so we're using Debian …

15 Apr 2019 1:44pm GMT

After upgrading my main workstation to F30 a while ago (soon after it branched) dbus-broker failed to start, making my machine pretty-much unusable. I tried putting selinux in permissive mode and that fixed it, so I made a note to revisit this later.

Fast-forward to today, I applied all updates, did a full-relabel for good measure and things were still broken. Spinning up a fresh F30 vm does not exhibit this problem, so the problem had to be something specific to my machine. After lots of debugging I found bug 1663040 which is about the same thing happen on the live media and only on the live media, the problem turns out to be the selinux attributes on the mount-points (/dev, /proc, /sys) in / which cannot be updated by a relabel because at that time they already have a filesystem mounted on them.

I created the problem of the wrong labels myself when I moved from a hdd to a ssd and did a cp -pr of the non mount dirs and a straight forward mkdir to create the mount-points on the ssd. Zbigniew gives a need trick to detect this problem from a running system in bug 1663040:

mkdir /tmp/foo
sudo mount --bind / /tmp/foo
ls -lZd /tmp/foo/* | grep unlabeled

If the output of the last command show any files/dirs with unlabeled_t as type then your system has the same issue as mine had. To fix this boot from a livecd, mount your / on /mnt, cd into /mnt and then run:

chcon -t device_t dev
chcon -t home_root_t home
chcon -t root_t proc sys
chcon -t var_run_t run

Then umount /mnt and reboot. After this your system should be able to run in enforcing mode again without problems.

10 Apr 2019 1:08pm GMT

While browsing for some internationalisation/localisation features, I found an interesting piece of functionality in Android's developer documentation. I'll quote it here:

A pseudolocale is a locale that is designed to simulate characteristics of languages that cause UI, layout, and other translation-related problems when an app is translated.

I've now implemented this for applications and libraries that use gettext, as an LD_PRELOAD library, available from this repository.


The current implementation can highlight a number of potential problems (paraphrasing the Android documentation again):

- String concatenation, which displays as one message split across 2 or more brackets.
- Hard-coded strings, which cannot be sent to translation, display as unaccented text in the pseudolocale to make them easy to notice.
- Right-to-left (RTL) problems such as elements not being mirrored.

06 Apr 2019 10:41am GMT

I just installed the Fedora Workstation 30 Beta yesterday and so far things are looking great. As many others have reported to, with the GNOME 3.32 update things definitely feels faster and smoother. So I thought it was a good time to talk about what is coming in Fedora Workstation 30 and what we are currently working on.

Fractional Scaling: One of the big features that landed, although still considered experimental was the fractional scaling feature that has been a collaboration between Jonas Ådahl here at Red hat and Marco Trevisan at Canonical. It has taken quite some time since the initial hackfest as it is a complex task, but we are getting close. Fractional scaling is a critical feature for many HiDPI screen laptops to get a desktop size that perfectly fits their screen, not being to small or to large.

Screen sharing support for Chrome and Firefox under Wayland. The Wayland security model doesn't allow any application to freely grab images or streams of the whole desktop like you could under X. This is of course a huge improvement in security, but it did cause some disruption for valid usecases like screen sharing with things like BlueJeans and Google Hangouts. We been working on resolving that with the help of PipeWire. We been at it for some time and things are now coming together. Chrome 73 ships with everything needed to make this work with Chrome, although you have to turn it on manually (got to this URL to turn it on: chrome://flags/#enable-webrtc-pipewire-capturer). The reason it needs to be manually enabled is not that it is unreliable, it is because the UI is still a little fugly due to a combination of feature overlap between the browser and the desktop and also how the security feature of the desktop is done. We are trying to come up with ways for the UI to be smoother without sacrificing your privacy/security. For Firefox we will keep shipping with our downstream patch until we manage to get it landed upstream.

Firefox for Wayland: Martin Stransky has been hard at work making Firefox be able to run Wayland-native. That work is tantalizingly near, but we decided to postpone it for Fedora Workstation 31 in the end to make sure it is really well polished before releasing it upon the world. The advantage of Wayland native Firefox is that in addition to bring us one step closer to not needing to run an X server (XWayland) all the time it also enables things like fractional scaling mentioned above to work for Firefox.

OpenH264 improved: As many of you know Firefox relies on a library called OpenH264, provided by Cisco, for its H264 video codec support for WebRTC. This library is also provided to Fedora users from Cisco free of charge (you can install it through GNOME Software). However its usefulness have been somewhat limited due to only supporting the baseline profile used for video calling, but not the Main and High profiles used by most online video content. Well what I can tell you is that Red Hat, Endless and Cisco partnered with Centricular some time ago to add support for decoding those profiles to OpenH264 and that work is now almost complete. The basic code enabling them is already merged, but Jan Schmidt at Centricular is working on fixing a few files that are still giving us problems. As soon as that is generally shipping we hope to get Firefox to be able to use OpenH264 also for things like Youtube playback and of course also use OpenH264 to playback any H264 using GStreamer applications like Totem. So a big thank you to Endless, Cisco and Centricular for working with us on this and thus enabling us to have a legal way to offer H264 support to our users.

NVidia binary driver support under Wayland: We been putting it quite a bit of effort trying to tie off the lose ends for using the NVidia binary driver with Wayland. We did manage to fix a long list of bugs like dealing with various colorspace issues, multimonitor setups and so on. For Intel and AMD graphics users things should actually be pretty good to go at this point. The last major item holding us back on the NVidia side is full support for using the binary driver with XWayland applications (native Wayland applications should work fine already). Adam Jackson worked diligently to get all the pieces in place and we do think we have a model now that will allow NVidia to provide an updated driver that should enable XWayland. As it stands though that driver update is likely to only come out towards the fall, so we will keep defaulting to X for NVidia binary driver users for some time more.

Gaming under Wayland. Olivier Fourdan and Jonas Ådahl has trying to crush any major Wayland bug reported for quite some time now and one area where we seem to have rounded the corner is for games. Valve has been kind enough to give us the ability to install and run any steam game for testing purposes, so whenever we found a game giving us trouble we have been able to let Olivier and Jonas reproduce it easily. So on my own gaming box I am now able to run all the Steam games I have under Wayland, including those using Proton, without a hitch. We haven't tested with the full Steam catalog of course, there are thousands, so if your favourite game is giving you trouble under Wayland still, please let us know. Talking about gaming one area we will try to free up some cycles going forward to look deeper at is Flatpaks and gaming. We already done quite a bit of work in this area, with things like the NVidia binary driver extension and the Steam package on Flathub. But we know from leading linux game devs that there are still some challenges to be resolved, like making host device access for gamepads simpler from within the Flatpak sandbox.

Flatpak Creation in Fedora. Owen Taylor has been in charge of getting Flatpaks building in Fedora, ensuring we can produce Flatpaks from Fedora packages. Owen set up a system to track the Fedora Flatpak status, we got about 10 applications so far, but hope to greatly grow that number of time as we polish up the system. This enables us to start planning for shipping some applications in Fedora Workstation as Flatpaks by default in a future release. This respository will be available by default in Fedora workstation 30 and you can choose the flatpak version of the package through the new drop down box in the top right corner of GNOME Software. For now the RPM version of the package is still the default, but we expect to change that in later releases of Fedora Workstation.

Gedit in GNOME Software with Source drop down box

Fedora Toolbox - Debarshi Ray is leading the effort we call Fedora Toolbox, which is our starting point for our goal to revitalise and revolutionize development on Linux. Fedora Toolbox is trying to take the model of a pet container for development and make it seamless and natural. Our goal is to make it dead simple to create pet containers for your projects, so you can for instance have a Fedora pet container where you develop against the leading edge libraries and tools in Fedora, and you can have a RHEL based container where you develop against the library versions and tools shipping in RHEL (makes updating and fixing in production applications a lot easier) and maybe a SteamOS container to work on your little game project. Currently the model is that you have one pet container per OS your targeting, but we are pondering if maybe having one pet container per project would be even better if we can find good ways to avoid it being a lot of extra overhead (by for example having to re-install all your favourite command line tools in the container) or just outright confusing (which container got what tools and libraries again). Our goal here though is to ensure Fedora becomes the premier container native OS out there and thus a natural home for developers doing container development.
We are also working with the team inside Red Hat focusing on AI/ML and trying to ensure that we have a super smooth way for you to get a pet container with things like TensorFlow and CUDA up and running quickly.

Being an excellent platform for Openshift and Kubernetes development: We are putting effort into together with the Red Hat developer tools organization to bringing the OpenShift and CodeReady Studio and CodeReady Workspaces tools to Fedora. These tools have so far been very focused on RHEL support, but thanks to Flatpak for CodeReady Studio and web integration for CodeReady Workspaces we now have a path for making them easily available in Fedora too. In the world of Kubernetes OpenShift is where you want to be, and we want Fedora Workstation to be the ultimate portal for OpenShift development.

Fleet Commander with Active Directory support - So we are about to hit a very major milestone with Fleet Commander our large scale desktop management tool for Fedora and RHEL. Oliver Gutierrez has been hard at work making it work with Active Directory in addition to the existing FreeIPA support. We know that a majority of people interested in Fleet Commander are only using Active Directory currently, so being able to use Active Directory with Fleet Commander should make this great tool available to a huge number of new users. So if you are managing a University computer lab or a large number of Fedora or RHEL clients in your company we should soon have a Fleet Commander release out that you can use. And if you are not using Fedora or RHEL today well Fleet Commander is a very big reason for switching over!
We will do a proper announcement with further details once the release with Active Directory support is out.

PipeWire - I don't have a major development to report, just a lot of steady work being done to stabilize and improve PipeWire. As mentioned earlier we now have Wayland screen sharing and recording working smoothly in the major browsers which is the user facing feature I think most of you will notice. Wim is still working on pushing the audio side it forward, but that is also a huge task. We have started talking about organizing a new hackfest soon to see if we can accelerate the effort further again. Likely scenario at this point in time is that we start enabling the JACK side of PipeWire first, maybe as early as Fedora Workstation 31, and then come back and do the PulseAudio replacement as a last stage.

Improved Input handling Another area we keep focusing on is improving input in Fedora. Peter Hutterer and Benjamin Tissoires are working hard on improving the stack. Peter just sent an extensive RFC out for how to deal with high resolution mice under Linux and Benjamin has been trying to get support for the Dell Totem landed. Neither will be there unfortunately for Fedora Workstation 30,but we expect to land this before Fedora Workstation 31.

Flicker-free boot
Hans de Goede has continued working on his effort to create a flicker-free boot experience with Fedora. The results of this work is on display in Fedora Workstation 30 and will for most of you now provide a seamless bootup experience . This effort is not so much about functionality as it is about ensuring you have an end-to-end polished experience with your Linux desktop. Things like the constant mode changes we seen in the past contribute to giving Linux an image of being unpolished and we want Fedora to be the vehicle that breaks down that image.

Ramping up Silverblue

For those of you following Fedora you are probably aware of Silverblue, which is our effort to re-think the Linux desktop distribution from the ground up and help us take the Linux desktop to a new level. The distribution model hasn't really changed much over the last 20 years and we probably polished up the offering as far as we can within the scope of that model. For instance I upgraded my system to Fedora 30 beta yesterday and it was a long and tedious process of looking at about 6000 individual packages get updated from the Fedora 29 version to the Fedora 30 version one by one. I didn't hit a lot of major snags despite this being a beta, but it is screamingly obvious that updating your operating system in this way is both slow and inherently fragile as anyone of those 6000 packages might hit a problem during upgrade and leave the system in a unknown state, especially since its common for packages to run scripts and similar as part of their upgrade.

Silverblue provides a revolutionary replacement for that process. First of all since it ships as a unified image we make life a lot easier for our QE team who can then test and verify against a single image which is in a known state. This in turn ensures that you as a user can feel confident that the new OS version will not break something on your system. And since the new version is just an image stored on your system next to the old one, upgrading is just about rebooting your system. There is no waiting for individual packages to get upgraded, as everything is already there and ready. Compare it to booting into a different kernel version on Fedora, it is quick and trivial.
And this also means that in the unlikely case that there is a problem with the new OS version you can just as easily go back to the previous version, by rebooting again and choosing to boot into that version. So you basically have instant upgrades with instant rollback if needed.
We believe this will radically change the way you look at OS upgrades forever, in fact you might almost forget they are happening.

And since Silverblue will basically be a Flatpak (and other containers) only OS you will have a clean delimitation between OS and applications. This means that even if we do major updates to the host, your applications should remain unaffected by the host OS update.
In fact we have some very interesting developments underway for Flatpak, with some major new efforts underway, efforts that I would love to talk about, but they are tied to some major Red Hat announcements that will happen at this years Red Hat Summit which will happen on May 7th - May 9th, so I will leave it as a teaser and then let you all know once the Summit is underway and Red Hats related major announcements are done.

There is a lot of work happening around Silverblue and as it happens Matthias Clasen wrote a long blog entry about it today. That blog goes into a lot more details on some of the Silverblue work items we been doing.

Anyway, I feel really excited about Silverblue and as we continue to refine the experience and figure out how everything will look in this brave new world I am sure everyone else will get excited too. Silverblue represents the single biggest evolution of the Linux desktop since the original GNOME and KDE releases back in the late nineties. It is not just about trying to tweak the existing experience, but an attempt at taking a big leap forward and provide an operating system that embodies all that we learned over these last 20 years and provide a natural home for developers and creators of all kind in our container centric computing future. Be sure to grab the Silverblue image of Fedora 30 beta and give it a test run. I recommend activating flathub.org repo to get started in order to get a decent range of applications available. As we move forward we are working hard to ensure that you have the world of applications available out of the box, so no need to go an enable any 3rd party repositories, but there are some more work that needs to happen before we can do that.

Summary
So Fedora Workstation 30 is going to be another exiting release of both of traditional RPM based Workstation version and of Silverblue, and I hope they will encourage even more people to join our rapidly growing Fedora community. Be sure to join us in #fedora-workstation on freenode IRC to talk!

03 Apr 2019 7:13pm GMT

Portable Services Walkthrough (Go Edition)

A few months ago I posted a blog story with a walkthrough of systemd Portable Services. The example service given was written in C, and the image was built with mkosi. In this blog story I'd like to revisit the exercise, but this time focus on a different aspect: modern programming languages like Go and Rust push users a lot more towards static linking of libraries than the usual dynamic linking preferred by C (at least in the way C is used by traditional Linux distributions).

Static linking means we can greatly simplify image building: if we don't have to link against shared libraries during runtime we don't have to include them in the portable service image. And that means pretty much all need for building an image from a Linux distribution of some kind goes away as we'll have next to no dependencies that would require us to rely on a distribution package manager or distribution packages. In fact, as it turns out, we only need as few as three files in the portable service image to be fully functional.

So, let's have a closer look how such an image can be put together. All of the following is available in this git repository.

A Simple Go Service

Let's start with a simple Go service, an HTTP service that simply counts how often a page from it is requested. Here are the sources: main.go - note that I am not a seasoned Go programmer, hence please be gracious.

The service implements systemd's socket activation protocol, and thus can receive bound TCP listener sockets from systemd, using the $LISTEN_PID and $LISTEN_FDS environment variables.

The service will store the counter data in the directory indicated in the $STATE_DIRECTORY environment variable, which happens to be an environment variable current systemd versions set based on the StateDirectory= setting in service files.

Two Simple Unit Files

When a service shall be managed by systemd a unit file is required. Since the service we are putting together shall be socket activatable, we even have two: portable-walkthrough-go.service (the description of the service binary itself) and portable-walkthrough-go.socket (the description of the sockets to listen on for the service).

These units are not particularly remarkable: the .service file primarily contains the command line to invoke and a StateDirectory= setting to make sure the service when invoked gets its own private state directory under /var/lib/ (and the $STATE_DIRECTORY environment variable is set to the resulting path). The .socket file simply lists 8080 as TCP/IP port to listen on.

An OS Description File

OS images (and that includes portable service images) generally should include an os-release file. Usually, that is provided by the distribution. Since we are building an image without any distribution let's write our own version of such a file. Later on we can use the portablectl inspect command to have a look at this metadata of our image.

Putting it All Together

The four files described above are already every file we need to build our image. Let's now put the portable service image together. For that I've written a Makefile. It contains two relevant rules: the first one builds the static binary from the Go program sources. The second one then puts together a squashfs file system combining the following:

1. The compiled, statically linked service binary
2. The two systemd unit files
3. The os-release file
4. A couple of empty directories such as /proc/, /sys/, /dev/ and so on that need to be over-mounted with the respective kernel API file system. We need to create them as empty directories here since Linux insists on directories to exist in order to over-mount them, and since the image we are building is going to be an immutable read-only image (squashfs) these directories cannot be created dynamically when the portable image is mounted.
5. Two empty files /etc/resolv.conf and /etc/machine-id that can be over-mounted with the same files from the host.

And that's already it. After a quick make we'll have our portable service image portable-walkthrough-go.raw and are ready to go.

Trying it out

Let's now attach the portable service image to our host system:

# portablectl attach ./portable-walkthrough-go.raw
(Matching unit files with prefix 'portable-walkthrough-go'.)
Created directory /etc/systemd/system.attached.
Created directory /etc/systemd/system.attached/portable-walkthrough-go.socket.d.
Written /etc/systemd/system.attached/portable-walkthrough-go.socket.d/20-portable.conf.
Copied /etc/systemd/system.attached/portable-walkthrough-go.socket.
Created directory /etc/systemd/system.attached/portable-walkthrough-go.service.d.
Written /etc/systemd/system.attached/portable-walkthrough-go.service.d/20-portable.conf.
Created symlink /etc/systemd/system.attached/portable-walkthrough-go.service.d/10-profile.conf → /usr/lib/systemd/portable/profile/default/service.conf.
Copied /etc/systemd/system.attached/portable-walkthrough-go.service.
Created symlink /etc/portables/portable-walkthrough-go.raw → /home/lennart/projects/portable-walkthrough-go/portable-walkthrough-go.raw.

The portable service image is now attached to the host, which means we can now go and start it (or even enable it):

# systemctl start portable-walkthrough-go.socket

Let's see if our little web service works, by doing an HTTP request on port 8080:

# curl localhost:8080
Hello! You are visitor #1!

Let's try this again, to check if it counts correctly:

# curl localhost:8080
Hello! You are visitor #2!

Nice! It worked. Let's now stop the service again, and detach the image again:

# systemctl stop portable-walkthrough-go.service portable-walkthrough-go.socket
# portablectl detach portable-walkthrough-go
Removed /etc/systemd/system.attached/portable-walkthrough-go.service.
Removed /etc/systemd/system.attached/portable-walkthrough-go.service.d/10-profile.conf.
Removed /etc/systemd/system.attached/portable-walkthrough-go.service.d/20-portable.conf.
Removed /etc/systemd/system.attached/portable-walkthrough-go.service.d.
Removed /etc/systemd/system.attached/portable-walkthrough-go.socket.
Removed /etc/systemd/system.attached/portable-walkthrough-go.socket.d/20-portable.conf.
Removed /etc/systemd/system.attached/portable-walkthrough-go.socket.d.
Removed /etc/portables/portable-walkthrough-go.raw.
Removed /etc/systemd/system.attached.

And there we go, the portable image file is detached from the host again.

A Couple of Notes

1. Of course, this is a simplistic example: in real life services will be more than one compiled file, even when statically linked. But you get the idea, and it's very easy to extend the example above to include any additional, auxiliary files in the portable service image.

2. The service is very nicely sandboxed during runtime: while it runs as regular service on the host (and you thus can watch its logs or do resource management on it like you would do for all other systemd services), it runs in a very restricted environment under a dynamically assigned UID that ceases to exist when the service is stopped again.

3. Originally I wanted to make the service not only socket activatable but also implement exit-on-idle, i.e. add a logic so that the service terminates on its own when there's no ongoing HTTP connection for a while. I couldn't figure out how to do this race-freely in Go though, but I am sure an interested reader might want to add that? By combining socket activation with exit-on-idle we can turn this project into an excercise of putting together an extremely resource-friendly and robust service architecture: the service is started only when needed and terminates when no longer needed. This would allow to pack services at a much higher density even on systems with few resources.

4. While the basic concepts of portable services have been around since systemd 239, it's best to try the above with systemd 241 or newer since the portable service logic received a number of fixes since then.

Further Reading

A low-level document introducing Portable Services is shipped along with systemd.

Please have a look at the blog story from a few months ago that did something very similar with a service written in C.

There are also relevant manual pages: portablectl(1) and systemd-portabled(8).

02 Apr 2019 10:00pm GMT

Running Android has some advantages compared to native Linux applications, for example with regard to the availability of applications and application developers.

For current non-Android systems, this work enables a path forward to running Android applications in the same graphical environment as traditional non-Android applications are run.

What is SPURV?

SPURV is our experimental containerized Android environment, and this is a quick overview of what it is.

It's aptly named after the first robotic fish since a common Android naming scheme is fish-themed names. Much like its spiritual ancestor Goldfish, the Android emulator.

Other Android Compatibility Layers

This means that Anbox which is LXC based, is different from SPURV in terms of how hardware is accessed. The hardware access that Anbox provides in indirect, and …

01 Apr 2019 4:07pm GMT

The process of reverse engineering Arm GPUs has been going on for a long time, starting with Luc Verhaegens work on the low-end Mali 2/3/400 series of GPUs based on the Arm Utgard family of GPUs.
This driver has recently seen a lot new attention and is itself progressing quickly, which means it will likely be accepted into the kernel soon.
A piece of trivia is that this GPU architecture was what Arm received when they purchased the Norwegian GPU IP vendor Falanx Microsystems.

The Mali T and G-series of GPUs are based on the Midgard and Bifrost architectures respectively, both of which are quite different from the 2/3/400 series. However the T and G-series are somewhat similar at least when …

01 Apr 2019 4:01pm GMT

Back in October, Panfrost ran some simple benchmarks, like glmark. Five months later, Panfrost has grown from running benchmarks to real-world apps, like Kodi, and 3D games like SuperTuxKart and Neverball.

Since the previous post, there have been major improvements across every part of the aspect culminating in this milestone. On the kernel side, my co-contributors Tomeu Vizoso and Rob Herring have created a modern kernel driver, suitable for mainline inclusion. Panfrost now uses this upstream-friendly driver, rather than relying on a modified legacy kernel as in the past. The new kernel module is currently under review for mainline inclusion. You can read more about this progress on Tomeu's blog.

Outside the kernel, however, the changes have been no less significant. Early development was constrained to our own project repositories, as the code was not yet ready to general users. In early February, thanks in part to the progress on the kernel-space, we flew out of our nest, and Panfrost was merged into upstream Mesa, the central repository for free software graphics drivers. Development now occurs in-tree in Mesa.

We have continued decoding new aspects of the hardware and implementing support in the driver. A few miscellaneous additions include cube maps, gl_PointSize and gl_PointCoord, linear depth rendering, performance counters, and new shader instructions.

One area of particular improvement has been our understanding of the hardware formats (like "4-element vector of 32-bit floats" or "single 16-bit unsigned normalized integer"). In Panfrost's early days, we knew magic numbers to distinguish a few of the most common formats, but the underlying meanings of the voodoo patterns were elusive. Further, the format bits for textures and attributes were not unified, further hindering the diversity of supported formats available. However, Connor Abbott and I have since identified the underlying meaning of the format codes for textures, attributes, and framebuffers. This new understanding allows for the magic numbers to be replaced by a streamlined format selection routine, mapping Gallium's formats to the hardware's and supporting the full spectrum of formats required for a conformant driver. Panfrost is now passing texture format tests for OpenGL ES 2.0.

From a performance standpoint, various optimizations have been added. In particular, a fast path likely relating to the "tiler" in the hardware was discovered. When this fast path is used, performance on geometry heavy scenes skyrockets. In one extreme demo (shading the Stanford bunny), performance more than tripled, and these gains trickle down to real-world games.

Features aside, one of the key issues with an early driver is the brittleness and instability. Accordingly, to guarantee robustness, I now test with the drawElements Quality Program (dEQP), which includes comprehensive code correctness tests. Although we're still a while away from conformance, I now systematically step through identified issues and resolved the bugs, translating to fixes across every aspect of the driver.

One real-world benefactor of these fixes is the Kodi media center, which today works well using Panfrost to achieve a fluid interface on Midgard devices. For standalone installations of Kodi, today there are experimental images featuring Kodi and Panfrost. To further improve fluidity, Kodi and Panfrost can even interoperate with the video decoding acceleration, contingent on cooperative kernel drivers.

For users more inclined to gaming, some 3D games are beginning to show signs of life with Panfrost. For instance, the classic (OpenGL ES 2.0) backend of the ever-popular kart racing game, SuperTuxKart, now renders with some minor glitches with Panfrost. Performance is playable on simple tracks, though we have many opportunities for optimization. To bring up this racing game, I added support for complex control flow in the compiler. Traditionally, control flow is discouraged in graphics, due to the architecture of desktop GPUs (thread "warps"). However, Midgard does not feature these traditional optimizations, negating the performance penalty for branching from control flow. The implementation required new bookkeeping in the compiler, as well as an investigation into long jumps due to the size of the game's "uber-shader". In total, this compiler improvement - paired with assorted bug fixes - allows SuperTuxKart to run.

Likewise, Neverball is playable (and fun!) with Panfrost, although there are rendering anomalies relating to the currently unimplemented legacy feature "point sprites". In contrast to Kodi and SuperTuxKart, which make liberal use of custom shaders, Neverball is implemented with purely fixed-function desktop OpenGL. This poses an interesting challenge, as Midgard is designed specifically for embedded graphics; the blob does not support this desktop superset. But that's no reason we can't!

Like most modern free software OpenGL drivers, Panfrost is built atop the modular "Gallium" architecture. This architecture abstracts away interface details, like desktop versus embedded OpenGL, normalizing differences to allow drivers to focus on the hardware itself. This abstraction means that by implementing Panfrost as an embedded driver atop Gallium, we get a partial desktop OpenGL implementation "free".

Of course, there is functionality in the desktop superset that does not exist in the embedded profile. While Gallium tries to paper over these differences, the driver is required to implement features like point sprites and alpha testing to expose the corresponding desktop functions. So, the bring-up of desktop OpenGL applications like Neverball has led me to implement some of this additional functionality. Translating the "alpha test" to a conditional discard instruction in the fragment shader works. Similarly, translating "point sprites" to the modern equivalent, gl_PointCoord, is planned.

Interestingly, the hardware does support some functionality only available through the full desktop profile. It is unknown how many "hidden features" of this type are supported; as the blob does not appear to use them, these features were discovered purely by accident on our part. For instance, in addition to the familiar set of "points, lines, and triangles", Midgard can natively render quadrilaterals and polygons. The existence of this feature will suggested by the corresponding performance counters, and the driver-side mechanics were determined by manual bruteforce of the primitive selection bits. Nevertheless, now that these bonus features are understood, quads can be drawn from desktop applications without first translating to indexed triangles in software. Similarly, it appears in addition to the embedded standard of boolean occlusion queries, setting a chicken bit enable the hardware's hidden support for precise occlusion counters, a useful desktop feature.

Going forward, although the implementation of OpenGL ES 2.0 is approaching feature-completeness, we will continue to polish the driver, guided by dEQP. Orthogonal to conformance, further optimization to improve performance and lower memory usage is on the roadmap.

It's incredible to reflect back and realise just one year ago, work had not even begun on writing a real OpenGL driver. Yet here we are today with an increasingly usable, exclusive free software, hardware-accelerated desktop with Mali Midgard graphics.

Frost on.

01 Apr 2019 7:00am GMT

Aside from the regular board elections we also have some bylaw changes to vote on. As usual with bylaw changes, we need a supermajority of all members to agree - if you don't vote you essentially reject it, but the board has no way of knowing.

Please see the detailed changes of the bylaws, make up your mind, and go voting on the shiny new members page.

29 Mar 2019 12:00am GMT

Today the announcement went out that the Linux Vendor Firmware Service has become and official Linux Foundation service. For those that don't know it yet LVFS is a service that provides firmware for your linux running hardware and it was one off our initial efforts as part of the Fedora Workstation effort to drain the swamp in terms of making Linux a first class desktop operating system.

The effort came about due to Peter Jones, who is Red Hats representative to the UEFI standards body, approaching me to talk about how Microsoft was trying to push for a standardized way to ship UEFI firmware for Windows and how UEFI being a standard openeded a path for us to actually get full support for this without each vendor having to ship and maintain their own proprietary firmware tools. So we did a meeting with Peter Jones and also brought in Richard Hughes who had already been looking at the problem of firmware updates in Linux, partly due to his ColorHug hardware, and the effort got started with Peter working on the low level OS tooling and Richard taking on building the service to drive distribution and the work to integrate it all into GNOME Software. One concern we had of course was if we could reach critical mass for this and get vendors interested, but luckily Dell was just as keen on improving firmware handling under Linux as us and signed on from the start. Having Dell onboard helped give the effort a lot of credibility and as the service matured we ended up having more and more vendors sign up. We also reached out through Red Hats partnerships to push vendors to adopt supporting it. As Richard also mentions in his interview about it, we had made the solution as similar to Microsofts as possible to decrease the threshold for hardware vendors to join, the goal being that if they did the basic work to support Windows they could more or less just ship the same firmware file to LVFS.

One issue that we had gone back on forth about inside Red Hat was the formal setup of the service. While we all agreed the service was hugely beneficial it felt like something that should be a shared service for all of Linux and we felt that if the service was Red Hat provided it might dissuade other vendors to join. So we started looking around for a neutral place to land the service while in the meantime LVFS had a sort of autonomous status being run as a community effort by Richard Hughes. We ended up talking to Chris Wright, the Red Hat CTO, about the project and he offered to facilitate contact with the Linux Foundation. The initial meetings was very positive and the Linux Foundation seemed interested in running the service right from the start, it did end up taking us quite some time to clear all formal and technical hurdles to get there, but I for one is very happy to see the LVFS now being a vendor neutral service provided by the Linux Foundation.

So a big thank you to Richard Hughes, Peter Jones, Chris Wright, Mario Limonciello and Dell and the Linux Foundation for their help in getting us here. And also a big thank you to Fedora and the Fedora community for their help with providing us a place to develop and polish up this service to the benefit of all. To me this is one of many examples of how Fedora keeps innovating and leading the way on Desktop linux.

28 Mar 2019 2:50pm GMT

I had to work on an image yesterday where I couldn't install anything and the amount of pre-installed tools was quite limited. And I needed to debug an input device, usually done with libinput record. So eventually I found that hexdump supports formatting of the input bytes but it took me a while to figure out the right combination. The various resources online only got me partway there. So here's an explanation which should get you to your results quickly.

By default, hexdump prints identical input lines as a single line with an asterisk ('*'). To avoid this, use the -v flag as in the examples below.

hexdump's format string is single-quote-enclosed string that contains the count, element size and double-quote-enclosed printf-like format string. So a simple example is this:

$ hexdump -v -e '1/2 "%d\n"' 
-11643
23698
0
0
-5013
6
0
0

This prints 1 element ('iteration') of 2 bytes as integer, followed by a linebreak. Or in other words: it takes two bytes, converts it to int and prints it. If you want to print the same input value in multiple formats, use multiple -e invocations.

$ hexdump -v -e '1/2 "%d "' -e '1/2 "%x\n"' 
-11568 d2d0
23698 5c92
0 0
0 0
6355 18d3
1 1
0 0

This prints the same 2-byte input value, once as decimal signed integer, once as lowercase hex. If we have multiple identical things to print, we can do this:

$ hexdump -v -e '2/2 "%6d "' -e '" hex:"' -e '4/1 " %x"' -e '"\n"'
-10922  23698 hex: 56 d5 92 5c
     0      0 hex: 0 0 0 0
 14879      1 hex: 1f 3a 1 0
     0      0 hex: 0 0 0 0
     0      0 hex: 0 0 0 0
     0      0 hex: 0 0 0 0

Which prints two elements, each size 2 as integers, then the same elements as four 1-byte hex values, followed by a linebreak. %6d is a standard printf instruction and documented in the manual.

Let's go and print our protocol. The struct representing the protocol is this one:

struct input_event {
#if (__BITS_PER_LONG != 32 || !defined(__USE_TIME_BITS64)) && !defined(__KERNEL__)
        struct timeval time;
#define input_event_sec time.tv_sec
#define input_event_usec time.tv_usec
#else
        __kernel_ulong_t __sec;
#if defined(__sparc__) && defined(__arch64__)
        unsigned int __usec;
#else
        __kernel_ulong_t __usec;
#endif
#define input_event_sec  __sec
#define input_event_usec __usec
#endif
        __u16 type;
        __u16 code;
        __s32 value;
};

So we have two longs for sec and usec, two shorts for type and code and one signed 32-bit int. Let's print it:

$ hexdump -v -e '"E: " 1/8 "%u." 1/8 "%06u" 2/2 " %04x" 1/4 "%5d\n"' /dev/input/event22 
E: 1553127085.097503 0002 0000    1
E: 1553127085.097503 0002 0001   -1
E: 1553127085.097503 0000 0000    0
E: 1553127085.097542 0002 0001   -2
E: 1553127085.097542 0000 0000    0
E: 1553127085.108741 0002 0001   -4
E: 1553127085.108741 0000 0000    0
E: 1553127085.118211 0002 0000    2
E: 1553127085.118211 0002 0001  -10
E: 1553127085.118211 0000 0000    0
E: 1553127085.128245 0002 0000    1

And voila, we have our structs printed in the same format evemu-record prints out. So with nothing but hexdump, I can generate output I can then parse with my existing scripts on another box.

21 Mar 2019 12:30am GMT

Ho ho ho, let's write libinput. No, of course I'm not serious, because no-one in their right mind would utter "ho ho ho" without a sufficient backdrop of reindeers to keep them sane. So what this post is instead is me writing a nonworking fake libinput in Python, for the sole purpose of explaining roughly how libinput's architecture looks like. It'll be to the libinput what a Duplo car is to a Maserati. Four wheels and something to entertain the kids with but the queue outside the nightclub won't be impressed.

The target audience are those that need to hack on libinput and where the balance of understanding vs total confusion is still shifted towards the latter. So in order to make it easier to associate various bits, here's a description of the main building blocks.

libinput uses something resembling OOP except that in C you can't have nice things unless what you want is a buffer overflow\n\80xb1001af81a2b1101. Instead, we use opaque structs, each with accessor methods and an unhealthy amount of verbosity. Because Python does have classes, those structs are represented as classes below. This all won't be actual working Python code, I'm just using the syntax.

Let's get started. First of all, let's create our library interface.

class Libinput:
   @classmethod
   def path_create_context(cls):
        return _LibinputPathContext()

   @classmethod
   def udev_create_context(cls):
       return _LibinputUdevContext()

   # dispatch() means: read from all our internal fds and
   # call the dispatch method on anything that has changed
   def dispatch(self):
        for fd in self.epoll_fd.get_changed_fds():
           self.handlers[fd].dispatch()

   # return whatever the next event is
   def get_event(self):
        return self._events.pop(0)

   # the various _notify functions are internal API
   # to pass things up to the context
   def _notify_device_added(self, device):
        self._events.append(LibinputEventDevice(device))
        self._devices.append(device)

   def _notify_device_removed(self, device):
        self._events.append(LibinputEventDevice(device))
        self._devices.remove(device)

   def _notify_pointer_motion(self, x, y):
        self._events.append(LibinputEventPointer(x, y))



class _LibinputPathContext(Libinput):
   def add_device(self, device_node):
       device = LibinputDevice(device_node)
       self._notify_device_added(device)

   def remove_device(self, device_node):
       self._notify_device_removed(device)


class _LibinputUdevContext(Libinput):
   def __init__(self):
       self.udev = udev.context()

   def udev_assign_seat(self, seat_id):
       self.seat_id = seat.id

       for udev_device in self.udev.devices():
          device = LibinputDevice(udev_device.device_node)
          self._notify_device_added(device)

We have two different modes of initialisation, udev and path. The udev interface is used by Wayland compositors and adds all devices on the given udev seat. The path interface is used by the X.Org driver and adds only one specific device at a time. Both interfaces have the dispatch() and get_events() methods which is how every caller gets events out of libinput.

In both cases we create a libinput device from the data and create an event about the new device that bubbles up into the event queue.

But what really are events? Are they real or just a fidget spinner of our imagination? Well, they're just another object in libinput.

class LibinputEvent:
     @property
     def type(self):
        return self._type

     @property
     def context(self):
         return self._libinput
       
     @property
     def device(self):
        return self._device

     def get_pointer_event(self):
        if instanceof(self, LibinputEventPointer):
            return self  # This makes more sense in C where it's a typecast
        return None

     def get_keyboard_event(self):
        if instanceof(self, LibinputEventKeyboard):
            return self  # This makes more sense in C where it's a typecast
        return None


class LibinputEventPointer(LibinputEvent):
     @property
     def time(self)
        return self._time/1000

     @property
     def time_usec(self)
        return self._time

     @property
     def dx(self)
        return self._dx

     @property
     def absolute_x(self):
        return self._x * self._x_units_per_mm

     @property
     def absolute_x_transformed(self, width):
        return self._x *  width/ self._x_max_value

You get the gist. Each event is actually an event of a subtype with a few common shared fields and a bunch of type-specific ones. The events often contain some internal value that is calculated on request. For example, the API for the absolute x/y values returns mm, but we store the value in device units instead and convert to mm on request.

So, what's a device then? Well, just another I-cant-believe-this-is-not-a-class with relatively few surprises:

class LibinputDevice:
   class Capability(Enum):
       CAP_KEYBOARD = 0
       CAP_POINTER  = 1
       CAP_TOUCH    = 2
       ...

   def __init__(self, device_node):
      pass  # no-one instantiates this directly

   @property
   def name(self):
      return self._name

   @property
   def context(self):
      return self._libinput_context

   @property
   def udev_device(self):
      return self._udev_device

   @property
   def has_capability(self, cap):
      return cap in self._capabilities

   ...

Now we have most of the frontend API in place and you start to see a pattern. This is how all of libinput's API works, you get some opaque read-only objects with a few getters and accessor functions.

Now let's figure out how to work on the backend. For that, we need something that handles events:

class EvdevDevice(LibinputDevice):
    def __init__(self, device_node):
       fd = open(device_node)
       super().context.add_fd_to_epoll(fd, self.dispatch)
       self.initialize_quirks()

    def has_quirk(self, quirk):
        return quirk in self.quirks

    def dispatch(self):
       while True:
          data = fd.read(input_event_byte_count)
          if not data:
             break

          self.interface.dispatch_one_event(data)

    def _configure(self):
       # some devices are adjusted for quirks before we 
       # do anything with them
       if self.has_quirk(SOME_QUIRK_NAME):
           self.libevdev.disable(libevdev.EV_KEY.BTN_TOUCH)


       if 'ID_INPUT_TOUCHPAD' in self.udev_device.properties:
          self.interface = EvdevTouchpad()
       elif 'ID_INPUT_SWITCH' in self.udev_device.properties:
          self.interface = EvdevSwitch()
       ...
       else:
          self.interface = EvdevFalback()


class EvdevInterface:
    def dispatch_one_event(self, event):
        pass

class EvdevTouchpad(EvdevInterface):
    def dispatch_one_event(self, event):
        ...

class EvdevTablet(EvdevInterface):
    def dispatch_one_event(self, event):
        ...


class EvdevSwitch(EvdevInterface):
    def dispatch_one_event(self, event):
        ...

class EvdevFallback(EvdevInterface):
    def dispatch_one_event(self, event):
        ...

Our evdev device is actually a subclass (well, C, *handwave*) of the public device and its main function is "read things off the device node". And it passes that on to a magical interface. Other than that, it's a collection of generic functions that apply to all devices. The interfaces is where most of the real work is done.

The interface is decided on by the udev type and is where the device-specifics happen. The touchpad interface deals with touchpads, the tablet and switch interface with those devices and the fallback interface is that for mice, keyboards and touch devices (i.e. the simple devices).

Each interface has very device-specific event processing and can be compared to the Xorg synaptics vs wacom vs evdev drivers. If you are fixing a touchpad bug, chances are you only need to care about the touchpad interface.

The device quirks used above are another simple block:

class Quirks:
   def __init__(self):
       self.read_all_ini_files_from_directory('$PREFIX/share/libinput')

   def has_quirk(device, quirk):
       for file in self.quirks:
          if quirk.has_match(device.name) or
             quirk.has_match(device.usbid) or
             quirk.has_match(device.dmi):
             return True
       return False

   def get_quirk_value(device, quirk):
       if not self.has_quirk(device, quirk):
           return None

       quirk = self.lookup_quirk(device, quirk)
       if quirk.type == "boolean":
           return bool(quirk.value)
       if quirk.type == "string":
           return str(quirk.value)
       ...

A system that reads a bunch of .ini files, caches them and returns their value on demand. Those quirks are then used to adjust device behaviour at runtime.

The next building block is the "filter" code, which is the word we use for pointer acceleration. Here too we have a two-layer abstraction with an interface.

class Filter:
   def dispatch(self, x, y):
      # converts device-unit x/y into normalized units
      return self.interface.dispatch(x, y)

   # the 'accel speed' configuration value
   def set_speed(self, speed):
       return self.interface.set_speed(speed)

   # the 'accel speed' configuration value
   def get_speed(self):
       return self.speed

   ...


class FilterInterface:
   def dispatch(self, x, y):
       pass

class FilterInterfaceTouchpad:
   def dispatch(self, x, y):
       ...
       
class FilterInterfaceTrackpoint:
   def dispatch(self, x, y):
       ...

class FilterInterfaceMouse:
   def dispatch(self, x, y):
      self.history.push((x, y))
      v = self.calculate_velocity()
      f = self.calculate_factor(v)
      return (x * f, y * f)

   def calculate_velocity(self)
      for delta in self.history:
          total += delta
      velocity = total/timestamp  # as illustration only

   def calculate_factor(self, v):
      # this is where the interesting bit happens,
      # let's assume we have some magic function
      f = v * 1234/5678
      return f

So libinput calls filter_dispatch on whatever filter is configured and passes the result on to the caller. The setup of those filters is handled in the respective evdev interface, similar to this:

class EvdevFallback:
    ...
    def init_accel(self):
         if self.udev_type == 'ID_INPUT_TRACKPOINT':
             self.filter = FilterInterfaceTrackpoint()
         elif self.udev_type == 'ID_INPUT_TOUCHPAD':
             self.filter = FilterInterfaceTouchpad()
         ...

The advantage of this system is twofold. First, the main libinput code only needs one place where we really care about which acceleration method we have. And second, the acceleration code can be compiled separately for analysis and to generate pretty graphs. See the pointer acceleration docs. Oh, and it also allows us to easily have per-device pointer acceleration methods.

Finally, we have one more building block - configuration options. They're a bit different in that they're all similar-ish but only to make switching from one to the next a bit easier.

class DeviceConfigTap:
    def set_enabled(self, enabled):
       self._enabled = enabled

    def get_enabled(self):
        return self._enabled

    def get_default(self):
        return False

class DeviceConfigCalibration:
    def set_matrix(self, matrix):
       self._matrix = matrix

    def get_matrix(self):
        return self._matrix

    def get_default(self):
        return [1, 0, 0, 0, 1, 0, 0, 0, 1]

And then the devices that need one of those slot them into the right pointer in their structs:

class  EvdevFallback:
   ...
   def init_calibration(self):
      self.config_calibration = DeviceConfigCalibration()
      ...

   def handle_touch(self, x, y):
       if self.config_calibration is not None:
           matrix = self.config_calibration.get_matrix

       x, y = matrix.multiply(x, y)
       self.context._notify_pointer_abs(x, y)

And that's basically it, those are the building blocks libinput has. The rest is detail. Lots of it, but if you understand the architecture outline above, you're most of the way there in diving into the details.

15 Mar 2019 6:15am GMT

One of the features in the soon-to-be-released libinput 1.13 is location-based touch arbitration. Touch arbitration is the process of discarding touch input on a tablet device while a pen is in proximity. Historically, this was provided by the kernel wacom driver but libinput has had userspace touch arbitration for quite a while now, allowing for touch arbitration where the tablet and the touchscreen part are handled by different kernel drivers.

Basic touch arbitratin is relatively simple: when a pen goes into proximity, all touches are ignored. When the pen goes out of proximity, new touches are handled again. There are some extra details (esp. where the kernel handles arbitration too) but let's ignore those for now.

With libinput 1.13 and in preparation for the Dell Canvas Dial Totem, the touch arbitration can now be limited to a portion of the screen only. On the totem (future patches, not yet merged) that portion is a square slightly larger than the tool itself. On normal tablets, that portion is a rectangle, sized so that it should encompass the users's hand and area around the pen, but not much more. This enables users to use both the pen and touch input at the same time, providing for bimanual interaction (where the GUI itself supports it of course). We use the tilt information of the pen (where available) to guess where the user's hand will be to adjust the rectangle position.

There are some heuristics involved and I'm not sure we got all of them right so I encourage you to give it a try and file an issue where it doesn't behave as expected.

15 Mar 2019 5:58am GMT

The process of reverse engineering Arm GPUs has been going on for a long time, starting with Luc Verhaegens work on the low-end Mali 2/3/400 series of GPUs based on the Arm Utgard family of GPUs.
This driver has recently seen a lot new attention and is itself progressing quickly, which means it will likely be accepted into the kernel soon.
A piece of trivia is that this GPU architecture was what Arm received when they purchased the Norwegian GPU IP vendor Falanx Microsystems.

The Mali T and G-series of GPUs are based on the Midgard and Bifrost architectures respectively, both of which are quite different from the 2/3/400 series. However the T and G-series are somewhat similar at least when …

13 Mar 2019 3:25pm GMT

The process of reverse engineering Arm GPUs has been going on for a long time, starting with Luc Verhaegens work on the low-end Mali 2/3/400 series of GPUs based on the Arm Utgard family of GPUs.
This driver has recently seen a lot new attention and is itself progressing quickly, which means it will likely be accepted into the kernel soon.
A piece of trivia is that this GPU architecture was what Arm received when they purchased the Norwegian GPU IP vendor Falanx Microsystems.

The Mali T and G-series of GPUs are based on the Midgard and Bifrost architectures respectively, both of which are quite different from the 2/3/400 series. However the T and G-series are somewhat similar at least when …

13 Mar 2019 3:25pm GMT

Imagine a finite resource that you want to distribute amongst peers in a fair manner. If you know the number of peers to be n, the problem becomes trivial and you can assign every peer 1/n-th of the total. This way every peer gets the same amount, while no part of the resource stays unused. But what if the number of peers is only known retrospectively? That is, how many resources do you grant a peer if you do not know whether there are more peers or not? How do you define "fairness"? And how do you make sure as little of the resource as possible stays unused?

The fairdist algorithm provides one possible solution to this problem. It defines how many resources a new peer is assigned, considering the following propertis:

1. The total amount of resources already distributed to other peers. This is also referred to by the term consumption.
2. The number of peers that already got resources assigned.
3. The amount of resources remaining. That is, the resources that are remaining to be distributed. This is also referred to by the term reserve.

The following is a mathematical proof of the properties of the fairdist algorithm. For the reference implementation of the algorithm and information on the different applications of it, see the r-fairdist project.

Prerequisites

We define a set of symbols up front, to keep the proofs shorter. Whenever these symbols are mentioned, the following definition applies:

• Let be a total amount of consumed resources.
• Let be a total amount of reserved resources.
• Let be a number of peers that consumed resources.
• Let be a function that computes the proportion of a peer can consume, based on the number of peers that currently have resources consumed.
• Let be a function that computes the proportion of a peer is guaranteed, based on the number of peers that currently have resources consumed.

The algorithm considers a total amount of resources, but splits it into two separate parts, the remaining reserve and the consumed part . Their sum represents the total amount that was initially available. It then declares a function , which is the resource allocator. It will later on be used to calculate how many resources of the reserve a peer can allocate: . That is, defines the proportion of the reserve a new peer gets access to. The smaller it is, the more a peer gets.

Similarly, the guarantee is used to declare a lower bound of the total resources the allocator grants a new peer. That is, while is a function applied to allocations, is a property the allocator will guarantee you. Unlike an allocation, will later on be calculated based on the total amount of resources: . Again, the function defines the proportion that is guaranteed. So the smaller is, the stronger the guarantee becomes.

Definition

The allocator is said to guarantee the limit , if there exists a function so that for all , , and :

implies both:

The idea here is to define a function which calculates how many resources a new peer can allocate. That is, considering a new peer requests resources, it will get of the reserve. The first property of this implication guarantees that this allocation is bigger than, or equal to, the guaranteed total for each peer. The guaranteed total is calculated through based on the total amount of resources (which is the consumption plus the reserve).

If you now pick an allocator and a guarantee that fulfil this definition, the idea is that this ensures you that the allocator can be used to serve resource requests from new peers, and it ensures that regardless of how many peers will request resources, each one will be guaranteed an amount equal to, or bigger than, the guarantee .

This definition requires the existance of a reserve watermark . It uses this watermark as a selector for an inductive step. That is, if the requirements of this reserve selector are true, the second implication guarantees that they are true for an infinite number of following allocations. That is, the right hand side of the second implication matches exactly the requirement of the implication, once a single allocation was performed (i.e., a resource chunk was subtracted from the reserve and added to the total consumption, while the number of peers increased by one).

Note that if is , then the requirement of the implication is true for all and . This guarantees that there is always a situation where allocator can actually be applied.

Lemma 1

To prove an allocator guarantees , it is sufficient to show that fulfils:

and

This lemma is used to make it easier to prove a specific allocator guarantees a specific limit. Without it, each proof of the different allocators would have to replicate it.

However, this lemma also gives a better feeling of what the different functions actually mean. For instance, it clearly shows must always be smaller than , and that by a considerable amount. If , then no would ever fulfil this requirement (remember: ). At the same time, you can see the closer and are together, the smaller gets, and as such the requirements on the reserve get harder to fulfil.

The second requirement gives you a recursive equation to find an for any allocator you pick. Hence, in combination both these requirements show you an iterative process to find and , for any guarantee you pick. However, the closer and get, the harder it becomes to solve the recursive equation.

Proof

To show this lemma is true, we must show both implications of the definition are true. As first step, we show the first implication is true, which is:

We show this b starting with the left-hand side and showing it implies the right hand side, using the requisite of this lemma.

As second step, we need to show the second implication of the definition is true, which is:

To prove this, we start with the second requisite of this lemma and then show it implies the right-hand side of the implication, using the requisite of the implication.

Hint: The following introduction of is correct, since is per definition greater than , so neither side can be 0.

Theorem

The following allocators each guarantee the specified limit:

This theorem defines three different allocators for different guarantees. The last one provides the strongest guarantee. Both the allocation and the guarantee are quasilinear. It is thus a good fit for fair allocation schemes, while still being reasonably fast to compute.

The other two provide quadratic and exponential guarantees and are mostly listed for documentational purposes. With the quasilinear guarantees at hand, there is little reason to use the other two.

As you might notice, this theorem does not provide a solution where and become infinitesimally close. It remains open whether what this solution would look like. However, the listed quasilinear solution is good enough, that it is unlikely that better options exist, which can still be calculated in reasonable amounts of time.

Proof

We provide a function for each pair. We then substitute them in Lemma 1 and show through equivalence transformations that the assertions are true.

Proof 1: Exponential Guarantee

• Allocator:
• Guarantee:

Let .

Part 1:

Part 2:

Proof 2: Polynomial Guarantee

• Allocator:
• Guarantee:

Let .

Part 1:

Part 2:

Proof 3: Quasilinear Guarantee

• Allocator:
• Guarantee:

Let .

Part 1:

Part 2:

For this part, we rely on the following property:

This is true for all logarithms for all .

We now show the second requirement of the Lemma is true. However, we cannot use equivalence transformations as in the other proofs. Hence, we show it by implication.

13 Mar 2019 12:00am GMT