Planet Scheme

Monday, December 16, 2024

Peter Bex

Let's CRUNCH!

NOTE: This is another guest post by Felix Winkelmann, the founder and one of the current maintainers of CHICKEN Scheme.

Introduction

Hi! This post is about a new project of mine, called "CRUNCH", a compiler for a statically typed subset of the programming language Scheme, specifically, the R7RS (small) standard.

The compiler runs on top of the CHICKEN Scheme system and produces portable C99 that can then be compiled and executed on any platform that has a decent C compiler.

So, why another Scheme implementation, considering that there already exists such a large number of interpreters and compilers for this language? What motivated me was the emergence of the PreScheme restoration project, a modernisation of "PreScheme", a statically typed compiler for Scheme that is used in the Scheme48 implementation. The original PreScheme was embedded into S48 and was used to generate the virtual machine that is targeted by the latter system. Andrew Whatson couragously started a project to port PreScheme to modern R7RS Scheme systems (PreScheme is written in Scheme, of course) with the intention of extending it and keep the quite sophisticated and interesting compiler alive.

The announcement of the project and some of the reactions that it spawned made me realize that there seems to be a genuine demand for a statically typed high-performance compiler for Scheme (even if just for a subset) that would close a gap in the spectrum of Scheme systems currently available.

There are compilers and interpreters for all sorts of platforms, ranging from tiny, minimal interpreters to state-of-the-art compilers, targeting about every imaginable computer system. But most Schemes need relatively complex runtime systems, have numerous dependencies, or have slow performance, which is simply due to the powerful semantics of the language: dynamic typing, automatic memory management (garbage collection), first class continuations, etc. which all have a cost in terms of overhead.

What is needed is a small, portable compiler that generates more or less "natural" C code with minimal dependencies and runtime system that supports at least the basic constructs of the language and that puts an emphasis on producing efficient code, even if some of the more powerful features of Scheme are not available. Such a system would be perfect for writing games, virtual machines, or performance-sensitive libraries for other programs where you still want to use a high-level language to master the task of implementing complex algorithms, while keeping as close to C/C++ as possible. Another use is as a tool to write bare-metal code for embedded systems, device drivers and kernels for operating systems.

There are some high-performance compilers like Bigloo or Stalin. But the former still needs a non-trivial runtime-system and the latter is brittle and not actively maintained. Also, one doesn't necessarily need support for the full Scheme language and if one is willing to drop the requirement of dynamic typing, a lot of performance can be gained while still having a relatively simple compiler implementation. Even without continuations, dynamic typing, the full numeric tower and general tail call optimization, the powerful metaprogramming facilities of Scheme and the clear and simple syntax make it a useful notation for many uses that require a high level of abstraction. Using type inference mostly avoids having to annotate a source program with type information and thus allows creating code which still is to a large part standard Scheme code that can (with a little care) be tested on a normal Scheme system before compiling it to more efficient native code.

History

There was a previous extension for CHICKEN, also called "crunch", that compiled to C++, used a somewhat improvised type-inferencing algorithm and was severely restricted. It was used to allow embedding statically typed code into normal CHICKEN Scheme programs. The new CRUNCH picks up this specific way of use, but is a complete reimplementation that targets C99, has a more sophisticated type system, offers some powerful optimizations and has the option to create standalone programs or separately compilable C modules.

Installation

CRUNCH is only available for the new major release of CHICKEN (version 6). You will need to build and install a development snapshot containing the sources of this release, which is still unofficial and under development:

 $ wget https://code.call-cc.org/dev-snapshots/2024/12/09/chicken-6.0.0pre1.tar.gz
 $ tar xfz chicken-6.0.0pre1.tar.gz
 $ cd chicken-6.0.0pre1
 $ ./configure --prefix <install location>
 $ make
 $ make install
 $ <install location>/bin/chicken-install -test crunch

CHICKEN has minimal dependencies (a C compiler, sh(1) and GNU make(1)), so don't be put off to give it a try.

Basic Operation and Usage

CRUNCH can be used as a batch compiler, translating Scheme to standalone C programs or can be used at compile time for embedded fragments of Scheme code, automatically creating the necessary glue to use the compiled code from CHICKEN Scheme. The compiler itself is also exposed as a library function, making various scenarios possible where you want to programmatically convert Scheme into native code.

There are four modes of using CRUNCH:

1. Embedding:

;; embed compiled code into Scheme (called using the foreign function interface):
(import crunch)
(crunch
  (define (stuff arg) ...) )
(stuff 123)

2. Standalone:

 $ cat hello.scm
 (define (main) (display "Hello world\n"))
 $ chicken-crunch hello.scm -o hello.c
 $ cc hello.c $(chicken-crunch -cflags -libs)
 $ ./a.out

3. Wrap compiled code in Scheme stubs to use it from CHICKEN:

 $ cat fast-stuff.scm
 (module fast-stuff (do-something)
   (import (scheme base))
   (define (do-something) ...))

 $ cat use-fast-stuff.scm
 (import fast-stuff)
 (fast-wait)

 $ chicken-crunch -emit-wrappers wrap.scm -J fast-stuff.scm -o fast-stuff.c
 $ csc -s wrap.scm fast-stuff.c -o wrap.so
 $ csc use-fast-stuff.scm -o a.out

4. Using CRUNCH as a library:

#;1> (import (crunch compiler))
#;2> (crunch
       '(begin (define (main) (display "Hello world\n"))
       '(output-file "out.c") )

Module system and integration into CHICKEN

CRUNCH uses the module system and syntactic metaprogramming facilities of CHICKEN. Syntax defined in CHICKEN modules can be used in CRUNCH code and vice versa. CRUNCHed code can produce "import libraries", like in CHICKEN to provide separate compilation of modules.

Modules compiled by CRUNCH may only export procedures and a standalone program is expected to export a procedure called main. This simplifies interfacing to C and makes callbacks from C into Scheme straightforward.

As in PreScheme, toplevel code is evaluated at compile time. Most assigned values can be accessed in compiled code.

;; build a table of sine values at compile time
(define sines
  (list->f64vector
    (list-tabulate 360
      (lambda (n) (sin (/ (* n π) 180))) ) ) )

Restrictions

A number of significant restrictions apply to Scheme code compiled with CRUNCH:

  • No support for multiple values
  • No support for first class continuations
  • Tail calls can only be optimized into loops for local procedure calls or calls that can be inlined
  • Closures (procedures capturing free variables) are not supported
  • Procedures can have no "rest" argument
  • Imported global variables can not be modified
  • Currently only 2-argument arithmetic and comparison operators are supported
  • It must be possible to eliminate all free variables via inlining and lambda-lifting

This list looks quite severe but it should be noted that a large amount of idiomatic Scheme code can still be compiled that way. Also, CRUNCH does not attempt to be a perfect replacement for a traditional Scheme system, it merely tries to provide an efficient programming system for domains where performance and interoperability with native code are of high importance.

Datums are restricted to the following types:

  • basic types: integer, float, complex, boolean, char, pointer
  • procedure types
  • strings
  • vectors of any of the basic types, and vectors for specific numeric types
  • structs and unions

Note the absence of pairs, lists and symbols. Structures and unions are representations of the equivalent C object and can be passed by value or by pointer.

The Runtime System

The runtime system required to run compiled code is minimal and contained in a single C header file. CRUNCH supports UNICODE and the code for UNICODE-aware case conversions and some other non-trivial operations is provided in a separate C file. UNICODE support is optional and can be disabled.

No garbage collector is needed. Non-atomic data like strings and vectors are managed using reference counting without any precautions taken to avoid circular data, which is something that is unlikely to happen by accident with the data types currently supported.

Optimizations

CRUNCH provides a small number of powerful optimizations to ensure decent performance and to allow more or less idiomatic Scheme code to be compiled. The type system is not fully polymorphic, but allows overloading of many standard procedures to handle generic operations that accept a number of different argument types. Additionally, a "monomorphization" optimization is provided that clones user procedures that are called with different argument types. Standard procedures that accept procedures are often expanded inline which further increases the opportunities for inlining of procedure calls - this reduces the chance of having "free" variables, which the compiler must be able to eliminate as it doesn't support closures. Aggressively moving lexically bound variables to toplevel (making them globals) can further reduce the amount of free variables.

Procedures that are called only once are inlined at the call site ("integrated"). Fully general inlining is not supported, we leave that to the C compiler. Integrated procedures that call themselves recursively in tail position are turned into loops.

A crucial transformation to eliminate free variables is "lambda lifting", which passes free variables as extra arguments to procedures that do not escape and whose argument list can be modified by the compiler without interfering with user code:

(let ((x 123))
  ; ... more code ...
  (define (foo y) (+ x y))
  ; ... more code ...
  (foo 99) )

  ~>

(let ((x 123))
  ; ... more code ...
  (define (foo y x) (+ x y))
  ; ... more code ...
  (foo 99 x) )

Monomorphization duplicates procedures called with arguments of (potentially) different types:

(define (inc x) (+ x 1))
(foo (inc 123) (inc 99.0))

~>

;; a "variant" represents several instantiations of the original procedure
(define inc
  (%variant
    (lambda (x'int) (+ x'int 1)) 	; "+" will be specialized to integer
    (lambda (x'float) (+ x'float 1)))))	; ... and here to float
(foo (inc'int 123) (inc'float 99.0))

Certain higher-order primitives are expanded inline:

(vector-for-each
  v
  (lambda (x) ...) )

~>   ; (roughly)

(let loop ((i 0))
  (unless (>= i (vector-length v))
    (let ((x (vector-ref v i))) ... (loop (+ i 1))) ) )

A final pass removes unused variables and procedure arguments and code that has no side effects and has unused results.

Together these transformations can get you far enough to write relatively complex Scheme programs while ensuring the generated C code is tight, and with a little effort, easy to understand (in case you need to verify the translation) and (hopefully) does what it is intended to do.

Performance

Code compiled with CRUNCH should be equivalent to a straightforward translation of the Scheme code to C. Scalar values are not tagged nor boxed and are represented with the most fitting underlying C type. There is no extra overhead introduced by the translation, with the following exceptions:

  • Vector- and string accesses perform bound checks (these can be disabled)
  • Using vectors and strings will add some reference counting overhead

If you study the generated code you will encounter many useless variable assignments and some unused values in statement position, these will be removed by the C compiler, also unexported procedures are declared static and so can also very often be inlined by the C compiler leading to little or no overhead.

The Debugger

For analyzing type errors, a static debugger is included, that presents a graphical user interface. When the -debug option is given, a Tcl/Tk script is invoked in a subprocess that shows the internal node tree and can be used to examine the transformed code and the types of sub-expressions, together with the corresponding source code line (if available). Should the compilation abort with an error, the shown node-tree is the state of the program at the point where the error occurred.

Differences to PreScheme

CRUNCH is inspired by and very similar to PreScheme, but has a number of noteworthy differences. CRUNCH tries to be as conformant to R7RS (small) as possible and handles UNICODE characters and strings. It also is tightly integrated into CHICKEN, allowing nearly seamless embedding of high-performance code sections. Macros and top-level code can take full advantage of the full CHICKEN Scheme language and its ecosystem of extension libraries.

PreScheme supports multiple values, while CRUNCH currently does not.

PreScheme uses explicit allocation and deallocation for compound data objects, while CRUNCH utilizes reference counting, removing the need to manually clean up resources.

I'm not too familiar with the PreScheme compiler itself, but I assume it provides more sophisticated optimizations, as it does convert to Static Single Assignment form (SSA), so it is to be expected that the effort to optimise the code is quite high. On the other hand, modern C compilers already provide a multitude of powerful optimizations, so it is not clear how many advantages lower-level optimizations will bring.

Future Plans

There is a lot of room for improvements. Support of multiple vales would be nice, and not too hard to implement, but will need to follow a convention that should not be too awkward to use on the C side. Also, the support for optional arguments is currently quite weak; the ability to specify default values is something that needs to be added.

Primitives for many POSIX libc system calls and library functions should be straightforward to use in CRUNCH code, at least the operations provided by the (chicken file posix) module.

What would be particularly nice would be if the compiler detects state machines - mutually recursive procedures that call each other in tail position.

Other targets are possible, like GPUs. I don't know anything about that, so if you are interested and think you can contribute, please don't hesitate to contact me.

Disclaimer

CRUNCH is currently alpha-software. It certainly contains numerous bugs and shortcomings that will hopefully be found and corrected as the compiler is used. If you are interested, I invite you to give it a try. Contact me directly or join the #chicken IRC channel on Libera.chat, if you have questions, want to report bugs, if you would like to suggest improvements or if you just want to know more about it.

All feedback is very welcome!

The CRUNCH manual can be found at the CHICKEN wiki, the source code repository is here.

by Peter Bex at Monday, December 16, 2024

Thursday, December 12, 2024

GNU Guix

The Shepherd 1.0.0 released!

Finally, twenty-one years after its inception (twenty-one!), the Shepherd leaves ZeroVer territory to enter a glorious 1.0 era. This 1.0.0 release is published today because we think Shepherd has become a solid tool, meeting user experience standards one has come to expect since systemd changed the game of free init systems and service managers alike. It’s also a major milestone for Guix, which has been relying on the Shepherd from a time when doing so counted as dogfooding.

To celebrate this release, the amazing Luis Felipe López Acevedo designed a new logo, available under CC-BY-SA, and the project got a proper web site!

Logo of the Shepherd.

Let’s first look at what the Shepherd actually is and what it can do for you.

At a glance

The Shepherd is a minimalist but featureful service manager and as such, it herds services: it keeps track of services, their state and their dependencies, and it can start, stop, and restart them when needed. It’s a simple job; doing it right and providing users with insight and control over services is a different story.

The Shepherd consists of two commands: shepherd is the daemon that manages services, and herd is the command that lets you interact with it to inspect and control the status of services. The shepherd command can run as the first process (PID 1) and serve as the “init system”, as is the case on Guix System; or it can manage services for unprivileged users, as is the case with Guix Home. For example, running herd status ntpd as root allows me to know what the Network Time Protocol (NTP) daemon is up to:

$ sudo herd status ntpd
● Status of ntpd:
  It is running since Fri 06 Dec 2024 02:08:08 PM CET (2 days ago).
  Main PID: 11359
  Command: /gnu/store/s4ra0g0ym1q1wh5jrqs60092x1nrb8h9-ntp-4.2.8p18/bin/ntpd -n -c /gnu/store/7ac2i2c6dp2f9006llg3m5vkrna7pjbf-ntpd.conf -u ntpd -g
  It is enabled.
  Provides: ntpd
  Requires: user-processes networking
  Custom action: configuration
  Will be respawned.
  Log file: /var/log/ntpd.log

Recent messages (use '-n' to view more or less):
  2024-12-08 18:35:54  8 Dec 18:35:54 ntpd[11359]: Listen normally on 25 tun0 128.93.179.24:123
  2024-12-08 18:35:54  8 Dec 18:35:54 ntpd[11359]: Listen normally on 26 tun0 [fe80::e6b7:4575:77ef:eaf4%12]:123
  2024-12-08 18:35:54  8 Dec 18:35:54 ntpd[11359]: new interface(s) found: waking up resolver
  2024-12-08 18:46:38  8 Dec 18:46:38 ntpd[11359]: Deleting 25 tun0, [128.93.179.24]:123, stats: received=0, sent=0, dropped=0, active_time=644 secs
  2024-12-08 18:46:38  8 Dec 18:46:38 ntpd[11359]: Deleting 26 tun0, [fe80::e6b7:4575:77ef:eaf4%12]:123, stats: received=0, sent=0, dropped=0, active_time=644 secs

It’s running, and it’s logging messages: the latest ones are shown here and I can open /var/log/ntpd.log to view more. Running herd stop ntpd would terminate the ntpd process, and there’s also a start and a restart action.

Services can also have custom actions; in the example above, we see there’s a configuration action. As it turns out, that action is a handy way to get the file name of the ntpd configuration file:

$ head -2 $(sudo herd configuration ntpd)
driftfile /var/run/ntpd/ntp.drift
pool 2.guix.pool.ntp.org iburst

Of course a typical system runs quite a few services, many of which depend on one another. The herd graph command returns a representation of that service dependency graph that can be piped to dot or xdot to visualize it; here’s what I get on my laptop:

Example of a service dependency graph.

It’s quite a big graph (you can zoom in for details!) but we can learn a few things from it. Each node in the graph is a service; rectangles are for “regular” services (typically daemons like ntpd), round nodes correspond to one-shot services (services that perform one action and immediately stop), and diamonds are for timed services (services that execute code periodically).

Blurring the user/developer line

A unique feature of the Shepherd is that you configure and extend it in its own implementation language: in Guile Scheme. That does not mean you need to be an expert in that programming language to get started. Instead, we try to make sure anyone can start simple for their configuration file and gradually get to learn more if and when they feel the need for it. With this approach, we keep the user in the loop, as Andy Wingo put it.

A Shepherd configuration file is a Scheme snippet that goes like this:

(register-services
  (list (service '(ntpd) …)
        …))

(start-in-the-background '(ntpd …))

Here we define ntpd and get it started as soon as shepherd has read the configuration file. The ellipses can be filled in with more services.

As an example, our ntpd service is defined like this:

(service
  '(ntpd)
  #:documentation "Run the Network Time Protocol (NTP) daemon."
  #:requirement '(user-processes networking)
  #:start (make-forkexec-constructor
           (list "…/bin/ntpd"
                 "-n" "-c" "/…/…-ntpd.conf" "-u" "ntpd" "-g")
           #:log-file "/var/log/ntpd.log")
  #:stop (make-kill-destructor)
  #:respawn? #t)

The important parts here are #:start bit, which says how to start the service, and #:stop, which says how to stop it. In this case we’re just spawning the ntpd program but other startup mechanisms are supported by default: inetd, socket activation à la systemd, and timers. Check out the manual for examples and a reference.

There’s no limit to what #:start and #:stop can do. In Guix System you’ll find services that run daemons in containers, that mount/unmount file systems (as can be guessed from the graph above), that set up/tear down a static networking configuration, and a variety of other things. The Swineherd project goes as far as extending the Shepherd to turn it into a tool to manage system containers—similar to what the Docker daemon does.

Note that when writing service definitions for Guix System and Guix Home, you’re targeting a thin layer above the Shepherd programming interface. As is customary in Guix, this is multi-stage programming: G-expressions specified in the start and stop fields are staged and make it into the resulting Shepherd configuration file.

New since 0.10.x

For those of you who were already using the Shepherd, here are the highlights compared to the 0.10.x series:

  • Support for timed services has been added: these services spawn a command or run Scheme code periodically according to a predefined calendar.
  • herd status SERVICE now shows high-level information about services (main PID, command, addresses it is listening to, etc.) instead of its mere “running value”. It also shows recently-logged messages.
  • To make it easier to discover functionality, that command also displays custom actions applicable to the service, if any. It also lets you know if a replacement is pending, in which case you can restart the service to upgrade it.
  • herd status root is no longer synonymous with herd status; instead it shows information about the shepherd process itself.
  • On Linux, reboot --kexec lets you reboot straight into a new Linux kernel previously loaded with kexec --load.

The service collection has grown:

  • The new log rotation service is responsible for periodically rotating log files, compressing them, and eventually deleting them. It’s very much like similar log rotation tools from the 80’s since shepherd logs to plain text files like in the good ol’ days.

    There’s a couple of be benefits that come from its integration into the Shepherd. First, it already knows all the files that services log to, so no additional configuration is needed to teach it about these files. Second, log rotation is race free: no single line of log can be lost in the process.

  • The new system log service what’s traditionally devoted to a separate syslogd program. The advantage of having it in shepherd is that it can start logging earlier and integrates nicely with the rest of the system.

  • The timer service provides functionality similar to the venerable at command, allowing you to run a command at a particular time:

herd schedule timer at 07:00 -- mpg123 alarm.mp3
  • The transient service maker lets you run a command in the background as a transient service (it is similar in spirit to the systemd-run command):
herd spawn transient -d $PWD -- make -j4
  • The GOOPS interface that was deprecated in 0.10.x is now gone.

As always, the NEWS file has additional details.

In the coming weeks, we will most likely gradually move service definitions in Guix from mcron to timed services and similarly replace Rottlog and syslogd. This should be an improvement for Guix users and system administrators!

Cute code

I did mention that the Shepherd is minimalist, and it really is: 7.4K lines of Scheme, excluding tests, according to SLOCCount. This is in large part thanks to the use of a high-level memory-safe language and due to the fact that it’s extensible—peripheral features can live outside the Shepherd.

Significant benefits also come from the concurrency framework: the concurrent sequential processes (CSP) model and Fibers. Internally, the state of each service is encapsulated in a fiber. Accessing a service’s state amounts to sending a message to its fiber. This way to structure code is itself very much inspired by the actor model. This results in simpler code (no dreaded event loop, no callback hell) and better separation of concern.

Using a high-level framework like Fibers does come with its challenges. For example, we had the case of a memory leak in Fibers under certain conditions, and we certainly don’t want that in PID 1. But the challenge really lies in squashing those low-level bugs so that the foundation is solid. The Shepherd itself is free from such low-level issues; its logic is easy to reason about and that alone is immensely helpful, it allows us to extend the code without fear, and it avoids concurrency bugs that plague programs written in the more common event-loop-with-callbacks style.

In fact, thanks to all this, the Shepherd is probably the coolest init system to hack on. It even comes with a REPL for live hacking!

What’s next

There’s a number of down-to-earth improvements that can be made in the Shepherd, such as adding support for dynamically-reconfigurable services (being able to restart a service but with different options), integration with control groups (“cgroups”) on Linux, proper integration for software suspend, etc.

In the longer run, we envision an exciting journey towards a distributed and capability-style Shepherd. Spritely Goblins provides the foundation for this; using it looks like a natural continuation of the design work of the Shepherd: Goblins is an actor model framework! Juliana Sims has been working on adapting the Shepherd to Goblins and we’re eager to see what comes out of it in the coming year. Stay tuned!

Enjoy!

In the meantime, we hope you enjoy the Shepherd 1.0 as much as we enjoyed making it. Four people contributed code that led to this release, but there are other ways to help: through graphics and web design, translation, documentation, and more. Join us!

Originally published on the Shepherd web site.

by Ludovic Courtès at Thursday, December 12, 2024

Wednesday, December 4, 2024

spritely.institute

Spritely launches Supporter Drive

Here at Spritely, we're building the future of decentralized networking technology for social networks and other applications!

As you can tell by the banner of this website, we just launched a supporter campaign and could really use your help.

Spritely Institute is a 501(c)(3) nonprofit and donations within the US are tax-deductible! We have a few donation levels with different perks for each one. Some of them even let you get your name in video game credits! More on that later...

History and Inspiration

Spritely is built by people who know and understand decentralized networks and their strengths and weaknesses today very well. Jessica Tallon and Christine Lemmer-Webber, two co-founders (and the first two working on Spritely's engineering) are both co-authors of the ActivityPub spec powering the fediverse!

Unfortunately, it's not feasible or easy to do everything we'd like in decentralized social networks today. Not on the fediverse nor anywhere.

The vision of Spritely is "secure collaboration". Finding out how to do it was a four-year research project before the Spritely Institute was even launched!

It turns out there's a whole group of people who figured out how to do "secure collaboration" right: the object capability security folks! Spritely builds on their history.

Here's an image of Electric Communities Habitat: a P2P, secure, 3D virtual world with player-run economies and safe, untrusted execution of code, all the way back in 1997!

Image of Electric Communities Habitat

Goblins: Secure and Decentralized, by default

Ultimately, Spritely is working towards user-facing software with secure-UI ideas applied to them. Here's a little mock-up!

Basic chat app implementation with secure collaboration and petnames

Right now it is way too hard to build this kind of software correctly. P2P tech shouldn't be the domain of only super-experts. When using Spritely's technology as a starting point, a secure P2P application is the default thing that you get.

Spritely Goblins sprite

That's what our first piece of technology, Spritely Goblins, is for! Goblins is a capability-security-by-default, distributed programming environment with a few key features:

Goblins takes care of the hard parts of distributed programming by abstracting them out so you can focus on the application you want to build. This is a game-changer, and it's the essential foundation for everything else we're doing.

Goblins is fully transactional. Remember when we said it supports "time travel" debugging? Here's a terminal-based space shooter built on Goblins. As you can see, we can roll backwards and forwards in time.

Terminal Phase time-traveldemo

The important thing here is that not a single line of gameplay code was added to support time travel, because that comes built in to any application built with Goblins!

OCapN Protocol

Goblins is deeply integrated with the Object Capability Network, or OCapN, protocol. OCapN supports wild things like:

  • distributed, efficient capability security
  • sending messages to objects before they even exist (called promise pipelining)
  • distributed garbage collection
  • and much more!

OCapN is based on CapTP from the E language (from which EC Habitat was built), and is a new open standard we're collaborating with other organizations to use. To learn more about it, visit ocapn.org.

Goblins abstracts the network away, though. You usually never even need to think about whether an actor is remotely or locally available.

Hoot: Goblins in the Browser

The other big piece of Spritely's tech stack is Hoot, our Scheme-to-WebAssembly compiler. This helps us get our tech to everyone!

The most important thing to us is that Spritely's distributed programs are coming to the browser, but Hoot is much more than that, it's an all-around Wasm toolkit!

Hey, remember when I mentioned you can get your name in Spritely's video game credits by donating?

You can go play a Goblins-based video game right now in your browser, thanks to Hoot!

Play Cirkoban on itch.io

Cirkoban is a hell of a lot of fun and you should definitely give it a shot. If you manage to get all the gems, let us know!

Why all this? Why the video games? Why the weird low-level tech? Why not just focus on writing some new higher-level software?

Lots of people are writing great high-level software right now! That's good, but right now we need new foundations. We need to change the game.

Our Mission

We need to make it simple and easy to run decentralized apps that don't just scale up, but scale down. That means more independent nodes running with fewer resources rather than fewer, higher capacity nodes which exert outsized control over a network.

We need decentralized technology that's easy to build and reason about!

We need tech that's safe and secure.

And we need tech that's cooperative, where everyone can have a stake.

I don't know about you, but there's a lot about the world today that worries me. I don't think building decentralized versions of existing social networks alone is going to get us where we need to be. Trying to replicate Web 2.0 user experiences is simply not enough to meet the challenges ahead.

I worry about activism on such platforms today. We need platforms which serve individuals, communities, and activists and empower each of them to take on a larger role in supporting a network.

You might be thinking: we've started to get into some serious topics like "activism" and "human rights" but also she's showing us video game screenshots? What on earth is going on?

Well, aside from being great demos, I think we need fun and whimsy. It's gotten us this far, at the very least.

It's easy to forget that social networks have owed their success more than anything to people enjoying being on them. I think sometimes people say, "we need to focus on serious things", and it's easy to accidentally make the story sterile. We aren't going to make it if we don't have fun along the way.

So, please come participate in our supporter drive. Try out our tech, ask questions, we are all eager to respond. We're only going to succeed if we all move forward together.

Visit our donation page!

by Christine Lemmer-Webber, Amy Grinn (contact@spritely.institute) at Wednesday, December 4, 2024

Sunday, November 24, 2024

GNU Guix

Guix/Hurd on a Thinkpad X60

A lot has happened with respect to the Hurd since our Childhurds and GNU/Hurd Substitutes post. As long as two years ago some of you have been asking for a progress update and although there have been rumours on a new blog post for over a year, we were kind of waiting for the rumoured x86_64 support.

With all the exciting progress on the Hurd coming available after the recent (last?) merger of core-updates we thought it better not to wait any longer. So here is a short overview of our Hurd work over the past years:

NetDDE and Rumpdisk support

Back in 2020, Ricardo Wurmus added the NetDDE package that provides Linux 2.6 network drivers. At the time we didn't get to integrate and use it though and meanwhile it bitrotted.

After we resurrected the NetDDE build, and with kind help of the Hurd developers we finally managed to support NetDDE for the Hurd.. This allows the usage of the Intel 82573L Gigabit Ethernet Controller of the Thinkpad X60 (and many other network cards, possibly even WIFI). Instead of using the builtin kernel driver in GNU Mach, it would be running as a userland driver.

What sparked this development was upstream's NetBSD rumpdisk support that would allow using modern hard disks such as SSDs, again running as a userland driver. Hard disk support builtin in GNU Mach was once considered to be a nice hack but it only supported disks up to 128 GiB…

First, we needed to fix the cross build on Guix.

After the initial attempt at rumpdisk support for the Hurd it took (v2) some (v3) work (v4) to finally arrive at rumpdisk support for the Hurd, really, *really* (v5)

Sadly when actually using them, booting hangs:

start: pci.arbiter:

What did not really help is that upstream's rumpkernel archive was ridiculously large. We managed to work with upstream to remove unused bits from the archive. Upstream created a new archive that instead of 1.8 GiB (!) now “only” weighs 670 MiB.

Anyway, after a lot of building, rebuilding, and debugging and some more with kind help from upstream we finally got Rumpdisk and NetDDE to run in a Childhurd.

NetDDE and Rumpdisk userland processes in a Childhurd

Initial Guix/Hurd on the Thinkpad X60

Now that the last (!) core-updates merge has finally happened (thanks everyone!), the recipe of installing Guix/Hurd has been much simpfilied. It goes something along these lines.

  1. Install Guix/Linux on your X60,

  2. Reserve a partition and format it for the Hurd:

    mke2fs -o hurd -L hurd /dev/sdaX
  3. In your config.scm, add some code to add GRUB menuentries for booting the Hurd, and mount the Hurd partition under /hurd:

    (use-modules (srfi srfi-26)
                 (ice-9 match)
                 (ice-9 rdelim)
                 (ice-9 regex)
                 (gnu build file-systems))
    
    (define %hurd-menuentry-regex
      "menuentry \"(GNU with the Hurd[^{\"]*)\".*multiboot ([^ \n]*) +([^\n]*)")
    (define (text->hurd-menuentry text)
      (let* ((m (string-match %hurd-menuentry-regex text))
             (label (match:substring m 1))
             (kernel (match:substring m 2))
             (arguments (match:substring m 3))
             (arguments (string-split arguments #\space))
             (root (find (cute string-prefix? "root=" <>) arguments))
             (device-spec (match (string-split root #\=)
                            (("root" device) device)))
             (device (hurd-device-name->device-name device-spec))
             (modules (list-matches "module ([^\n]*)" text))
             (modules (map (cute match:substring <> 1) modules))
             (modules (map (cute string-split <> #\space) modules)))
        (menu-entry
         (label label)
         (device device)
         (multiboot-kernel kernel)
         (multiboot-arguments arguments)
         (multiboot-modules modules))))
    
    (define %hurd-menuentries-regex
      "menuentry \"(GNU with the Hurd[^{\"]*)\" \\{([^}]|[^\n]\\})*\n\\}")
    (define (grub.cfg->hurd-menuentries grub.cfg)
      (let* ((entries (list-matches %hurd-menuentries-regex grub.cfg))
             (entries (map (cute match:substring <> 0) entries)))
        (map text->hurd-menuentry entries)))
    
    (define (hurd-menuentries)
      (let ((grub.cfg (with-input-from-file "/hurd/boot/grub/grub.cfg"
                        read-string)))
        (grub.cfg->hurd-menuentries grub.cfg)))
    
    ...
    (operating-system
       ...
      (bootloader (bootloader-configuration
                   (bootloader grub-bootloader)
                   (targets '("/dev/sda"))
                   (menu-entries (hurd-menuentries))))
      (file-systems (cons* (file-system
                             (device (file-system-label "guix"))
                             (mount-point "/")
                             (type "ext4"))
                           (file-system
                             (device (file-system-label "hurd"))
                             (mount-point "/hurd")
                             (type "ext2"))
                           %base-file-systems))
      ...)
  4. Create a config.scm for your Hurd system. You can get inspiration from bare-hurd.tmpl and inherit from %hurd-default-operating-system. Use grub-minimal-bootloader and add a static-networking-service-type. Something like:

    (use-modules (srfi srfi-1) (ice-9 match))
    (use-modules (gnu) (gnu system hurd))
    
    (operating-system
      (inherit %hurd-default-operating-system)
      (bootloader (bootloader-configuration
                   (bootloader grub-minimal-bootloader)
                   (targets '("/dev/sda"))))
      (kernel-arguments '("noide"))
    ...
      (services
        (cons*
          (service static-networking-service-type
                   (list %loopback-static-networking
                         (static-networking
                          (addresses
                           (list
                            (network-address
                             (device "eth0")
                             (value "192.168.178.37/24"))))
                          (routes
                           (list (network-route
                                  (destination "default")
                                  (gateway "192.168.178.1"))))
                          (requirement '())
                          (provision '(networking))
                          (name-servers '("192.168.178.1")))))
        ...)))
  5. Install the Hurd. Assuming you have an ext2 filesystem mounted on /hurd, do something like:

    guix system build --target=i586-pc-gnu vuurvlieg.hurd --verbosity=1
    sudo -E guix system init --target=i586-pc-gnu --skip-checks \
        vuurvlieg.hurd /hurd
    sudo -E guix system reconfigure vuurvlieg.scm
  6. Reboot and...

Hurray!

We now have Guix/Hurd running on Thinkpad.

Guix/Hurd GRUB menu on ThinkpadX60

Guix/Hurd running on ThinkpadX60

Guix/Hurd on Real Iron

While the initial manual install on the X60 was an inspiring milestone, we can do better. As mentioned above, just recently the installer learnt about the Hurd, right after some smaller problems were addressed, like guix system init creating essential devices for the Hurd, not attempting to run a cross-built grub-install to install Grub, soft-coding the hard-coded part:1:device:wd0 root file-system, adding support for booting Guix/Hurd more than once.

To install Guix/Hurd, first, build a 32bit installation image and copy it to a USB stick:

guix system image --image-type=iso9660 --system=i686-linux gnu/system/install.scm
dd if=/gnu/store/cabba9e-image.iso of=/dev/sdX status=progress
sync

then boot it on a not-too-new machine that has wired internet (although installation over WIFI is possible, there is currently no WIFI support for the installed Hurd to use it). On the new Kernel page:

Installer Kernel page

choose Hurd. Do not choose a desktop environment, that's not available yet. On the Network management page:

Installer Network management page

choose the new Static networking service. In the final Configuration file step, don't forget to edit:

Installer Configuration file page

and fill-in your IP and GATEWAY:

Installer Edit static networking

You may want to add some additional packages such as git-minimal from (gnu packages version-control) and sqlite from (gnu packages sqlite).

If you also intend to do Guix development on the Hurd—e.g., debugging and fixing native package builds—then you might want to include all dependencies to build the guix package, see the devel-hurd.tmpl for inspiration on how to do that. Note that any package you add must already have support for cross-building.

Good luck, and let us know if it works for you and on what kind of machine, or why it didn't!

What's next?

In an earlier post we tried to answer the question “Why bother with the Hurd anyway?” An obvious question because it is all too easy to get discouraged, to downplay or underestimate the potential social impact of GNU and the Hurd.

The most pressing problem currently is that the guix-daemon fails when invoking guix authenticate on the Hurd, which means that we cannot easily keep our substitutes up to date. guix pull is known to work but only by pulling from a local branch doing something like:

mkdir -p ~/src/guix
cd src/guix
git clone https://git.savannah.gnu.org/git/guix.git master
guix pull --url=~/src/guix/master

kinda like we did it in the old days. Sometimes it seems that guix does not grok the sqlite store database. This is needs to be resolved but as sqlite does read it this can be easily worked around by doing something like:

mv /var/guix/db/db.sqlite /var/guix/db/db.sqlite.orig
sqlite3 /var/guix/db/db.sqlite.orig .dump > /var/guix/db/db.sqlite.dump
sqlite3 -init /var/guix/db/db.sqlite.dump /var/guix/db/db.sqlite .quit

Also, the boot process still fails to handle an unclean root file system. Whenever the Hurd has suffered an unclean shutdown, cleaning it must currently be done manually, e.g., by booting from the installer USB stick.

Upstream now has decent support for 64bit (x86_64) albeit with more bugs and fewer packages. As mentioned in the overview we are now working to have that in Guix and have made some progress:

Hello Guix 64bit Hurd

more on that in another post. Other interesting task for Guix include:

  • Have guix system reconfigure work on the Hurd,
  • Figure out WiFi support with NetDDE (and add it to installer!),
  • An isolated build environment (or better wait for, err, contribute to the Guile guix-daemon?),
  • An installer running the Hurd, and,
  • Packages, packages, packages!

We tried to make Hurd development as easy and as pleasant as we could. As you have seen, things start to work pretty nicely and there is still plenty of work to do in Guix. In a way this is “merely packaging” the amazing work of others. Some of the real work that needs to be done and which is being discussed and is in progress right now includes:

All these tasks look daunting, and indeed that’s a lot of work ahead. But the development environment is certainly an advantage. Take an example: surely anyone who’s hacked on device drivers or file systems before would have loved to be able to GDB into the code, restart it, add breakpoints and so on—that’s exactly the experience that the Hurd offers. As for Guix, it will make it easy to test changes to the micro-kernel and to the Hurd servers, and that too has the potential to speed up development and make it a very nice experience.

Join #guix and #hurd on libera.chat or the mailing lists and get involved!

Addendum

It has been brought to our attention that people haven't heard that Debian GNU/Hurd has been a reality for some years now. While Guix GNU/Hurd has an exciting future, please be aware that it lacks many packages and services, including Xorg. If you would simply like to install the Hurd on bare metal running your favorite window manager (eg: i3, icewm, etc.) or lightweight desktop environment (Xfce) right now, then installing Debian GNU/Hurd is a good choice. Though we hope to catch up to them soon!

by Janneke Nieuwenhuizen at Sunday, November 24, 2024

Wednesday, November 20, 2024

Scheme Requests for Implementation

SRFI 256: Minimal extension to SRFI 9/R7RS small record type definitions for inheritance

SRFI 256 is now in draft status.

A SRFI 9-style define-record-type is specified which allows subtyping while preserving encapsulation, in that the field structure of supertypes remains an implementation detail with which subtypes need not concern themselves.

by Daphne Preston-Kendal at Wednesday, November 20, 2024

Monday, November 18, 2024

Peter Bex

What to expect from CHICKEN 6

NOTE: This is a guest post by Felix Winkelmann, the founder and one of the current maintainers of CHICKEN Scheme.

Introduction

This article is about the changes in the next major version of CHICKEN Scheme.

The current version is 5.4.0. The next major version, 6.0.0, is mostly implemented. Currently we are adding final touches before preparing the next release. If you are already familiar with CHICKEN, this article will help you get a more detailed view of what has been done. If you are not into CHICKEN or even Scheme, this article may still give you an insight into what's involved in the development and maintenance of a programming language project. You may also find it interesting to know how we address issues like portability and backwards-compatibility. There are also some juicy details on implementation techniques.

No previous knowledge of CHICKEN Scheme is required, but it will help if you are familiar with common terms used in programming language design and Lisp-y languages.

Versions

CHICKEN uses the usual major.minor.patch versioning scheme, where we bump major versions only for significant changes that break compatibility with older versions. CHICKEN has a relatively large community for a non-mainstream language and has lots of contributed extension libraries called "eggs". Breaking backwards compatibility in non-major versions adds implementation effort for users that just want keep their CHICKEN up to date and any eggs they're using should also keep working.

The process of avoiding breakage can sometimes become challenging. We may, for example, provide two different implementations for one and the same thing, to allow adoption of the new feature while keeping old code working. Typically this happens when the new feature is safer, easier to use, faster or more standards compliant than the old. We also remove features in stages. First we mark it as deprecated, and delete it later. This allows users to upgrade their code gradually.

On major version changes, we create a new mirror of the egg "repository", where most of the extensions are stored. Externally contributed eggs can choose when and how to publish an extension for specific versions. This is described in a previous post on this blog.

Major version changes also usually bump the "binary version". This is a suffix to the shared runtime library name to avoid intermixing tools and programs written for one version with the libraries for another.

We started CHICKEN major version 6 to introduce new features that were dearly required but were impossible to add without changing external interfaces, in particular what modules exist and what they export. Specifically, we needed full support for UNICODE strings and compliance with the R7RS (small) language standard.

Both features were already available in a rudimentary manner as external libraries. They were not fully integrated, a fact that showed in various places and could lead to subtle bugs as core and extension code assumed differences in string representation and the behaviour of standard procedures. The same approach was used for integrating the "full numeric tower" (the full set of numeric types, including rationals, big integers and complex numbers), which was formerly a library and was moved into the core system with the 5.0.0 release.

We'll now describe the most noteworthy changes made during this major version transition.

UNICODE

A major shortcoming of CHICKEN up to now was that it didn't support full UNICODE strings. All string data was assumed to consist of 8-bit characters in the ASCII or Latin-1 range. Internationalisation of source code and applications is unavoidable and libraries and operating systems have moved towards UTF-8 as a standard character encoding. So we saw no choice but to find a reasonably efficient way of using the full range of possible characters in all parts of the system.

There is an open-ended space of design choices regarding how to efficiently implement UNICODE strings. The Damocles Sword of unanticipated performance degradation constantly looms over the head of the language implementer, so finding the ideal solution in terms of memory use, speed and simplicity is not easy. Some implementations go to great lengths by providing complex storage schemes or multiple representations depending on a strings' content. In the end, we think a simple representation serves everybody better by being easier to understand and maintain.

Also it is not entirely sure that (say) a dynamic multi-representation approach pays off sufficiently. Too many factors come into play, like string usage patterns in applications, memory management and implementation overhead. Data exchange at the boundaries of operating system and foreign code also have to be taken into account. You want to avoid unnecessary conversions and copying, especially because CHICKEN is geared towards easy interfacing to external libraries and OS functionality.

We decided to use an UTF-8 representation internally. Many operating systems and applications already support UTF-8, which removes the need for costly conversions. UTF-8 is also backwards compatible to ASCII and keeps storage requirements at a minimum.

Since UTF-8 is a multi-byte encoding, character lookup in a string is of linear complexity. Characters have to be scanned when addressing a specific index in a string. To avoid repeatedly scanning the same section of a string when iterating over it, we use a simple cache slot in the string that maps byte-offsets to code point indices and holds the offset/index pair of the last access.

String representation

A quick recap regarding how strings are currently stored in CHICKEN is in order. If you are interested, there's also an older post on this blog with a more detailed explanation of the data representation used by CHICKEN.

Characters are stored as immediates with the special bit pattern 1110 (type code 111):

This gives us enough bits (even on 32-bit platforms) to hold all code points in the Basic Multilingual Plane (code points in the range 32 - 0x1fffff). CHICKEN 5 already supported characters in that range, but strings were still restricted to having 8-bit elements.

Up to CHICKEN 5 a string was represented by a single byteblock:

In CHICKEN 6 we add an indirection:

As you can see, the string itself is a normal block containing a pointer to a byteblock holding the UTF-8 byte sequence and a trailing zero byte. The "Count" slot is a fixnum with the number of code points in the string (the length). "Offset" and "Index" act as a cache for the byte-offset and code point-index of the last access. They are reset to zero if the string changes its length due to a character's width changing at an offset before the cached point.

An indirection is necessary regardless of the other details of the representation: as UTF-8 is a multi-byte encoding, destructively modifying characters in a string may grow or shrink the total byte-sequence. The string must still keep its identity and be indistinguishable from the original string (in terms of the primitive eq? procedure).

One obvious optimisation we can do here is that character accesses for strings where the length ("Count") and the length of the character data (encoded in the header of the byteblock) minus one is equal: then we can simply index by byte offset.

Alternative representations are possible. I believe the following is used in Chibi Scheme: keep a list of "chunks", i.e. multiple byte-offset/code point-index pairs per string. You can traverse this list to obtain the first chunk of string data containing the index you want to access.

In CHICKEN this would probably be represented thus:

This way we can find the offset for the index right at or before the location addressed. This reduces the amount of scanning to the part inside a chunk pointed to by the offset/index pair.

Such an approach of maintaining the offset/index list is more complex and keeping it up to date is more effort than the simple offset/index cache. Should the performance impact of the simpler representation turn out to be too large, the alternative approach may still be an option to try.

This leads me to the subject of benchmarks. We do have a benchmark suite holding a number of micro-benchmarks and CHICKEN 6 has been compared to previous versions using this suite. Nevertheless, the results of micro-benchmarking have to be taken with a grain of salt.

The behaviour of real-world applications may differ considerably depending on the memory consumption, memory address patterns and the type and amount of data processed. Reasoning about performance is especially difficult due to the complex caching mechanisms of contemporary hardware and operating systems. Therefore we will try to use the simplest approach that has a good chance of providing sufficient performance while keeping the implementation effort and complexity at a minimum.

Dealing with the outside world

There's another point we have to address when considering strings that are received from external sources like OS APIs, from files and from the foreign function interface. What to do when encountering invalid UTF-8 byte sequences, for example when reading file or directory names? Signal an error? Convert to some other representation or mark the location in the byte sequence using some special pattern?

We decided to basically ignore the problem. Strings are accepted whether valid or not. Only when decoding a string we distinguish between valid and invalid sequences. When indexing and scanning a string's byte sequence, we return the invalid byte as a "surrogate pair end" code point that has the value 0xDCxx. This approach allows us to store the byte in the lower 8 bits of the code point. When inserting a character in a string that has such a value, we simply copy the byte. As I understand it, this is the approach used by the "surrogateescape" error handler in PEP 383. However, we do this masking every time we decode an unexpected byte (and do the inverse when encoding).

Say we received a string from an external source containing the following byte sequence:

This is invalid UTF-8. Extracting character by character with the described method would yield the following code point values:

Inserting such a surrogate pair end code point will inject the value of the lower byte. For example, calling (string-set! str #\xdcfe), where str is the above invalid utf-8 encoded string would yield the following byte sequence:

The advantage is that we can simply accept and pass strings containing invalid sequences as if nothing happened. We don't need to do any conversions and checks. We can also access items in the character sequence and store them back without having to worry about the validity of the sequence with respect to the UTF-8 encoding. The process is "lossless".

The disadvantage is that we have to perform an additional check when encoding or decoding UTF-8 sequences. Again we decided to reduce copying and transcoding overhead and rather have complete transparency regardless of the source of the string. Furthermore no validation is performed for incoming strings. The R7RS standard procedure utf8->string which converts bytevectors into strings does validation, though to at least ensure that strings created from binary data are always correctly encoded.

A final issue is UNICODE handling on Windows platforms. There, the OS API entry-points that are UNICODE aware use UTF-16 for strings like filenames or the values of environment variables. On Windows there is no choice but to encode and decode from UTF-8 to UTF-16 and back when interfacing with the OS.

Port encodings

When accessing files, we still want to be able to read and write data in an 8-bit encoding or in binary. We may also want to support additional encodings, even though these are currently not provided by default so we'll need to associate an "encoding" property to "ports". Ports are the Scheme objects that provide access to files and other streams of data, like traffic received from a network. The encoding is selected when opening a port using additional arguments to standard procedures that create ports for textual input and output like open-input-port/open-output-port.

Ports internally hold a table of "port methods", roughly similar to how object-oriented programming systems attach behaviour to data objects of a particular class. The port methods in former versions of CHICKEN included the low-level counterpart of the standard operations peek-char, read-char and read-string for input ports and write-char/write-string (among others) for output ports. The major change here is to replace the string I/O methods with methods that act upon bytevectors.

An internal mechanism delegates the operations for encoding and decoding or scanning for the next character in a stream to an internal hook procedure. Additional encodings can be registered by using a built-in procedure to extend the hook. Currently supported are binary, UTF-8 and Latin-1 encodings. Support for a larger set of encodings can be done through extensions and thus can be developed separately from the core system. Port encodings can be accessed using port-encoding. They can also be changed using the SRFI-17 setter for port-encoding, because encodings need sometimes to be changed while the port is still open.

R7RS does not define whether binary I/O standard procedures are allowed to operate on textual ports and vice versa. In CHICKEN we do not restrict the set of operations depending on the port type, so you can read and write bytevectors to and from a textual port and the other way round. We think this is more practical and intuitive - it makes more sense to read and write binary data as bytevectors and have dedicated operations for this.

R7RS support

The second big change for CHICKEN 6 is proper R7RS (small) compliance. Like with the UTF-8 support this was previously provided by an extension library, but using it needed some minor extra steps to set up. Now, all syntactic definitions of the (scheme base) module are available by default (most notably define-library) without requiring any further action.

Deciding what is available by default in a compilation unit or interpretation environment is a bit of a problem: to make it easy to get going when experimenting or scripting, we defaulted to having all standard R5RS procedures and macros available in the base environment of the interpreter (csi), together with the imports from the (chicken base) module. Compiled code was slightly more restricted but defaulted also to R5RS.

In CHICKEN 5 the scheme module referred to the R5RS standard procedures. To avoid breaking too much existing code this is still the case. So now, scheme is an alias for the R7RS (scheme r5rs) library module that exports all bindings of the former language standard. But to avoid duplicating the set of exported identifiers over several core modules, certain functionality has been moved from (chicken base) to (scheme base) and is thus not available in the default toplevel environment.

To make a long story short, the switch makes it necessary to access certain standard bindings like open-input-string by importing additional modules like (scheme base). This is not necessarily a bad thing, as it incentivises the user to write code in a more standard compliant way. But it all feels a bit clunky and may have been a suboptimal choice. Note that just adding an (import (scheme base)) is usually enough to make existing code run. We will see how that works out.

All required (scheme ...) modules are implemented and can be imported using their full functionality. Two notable changes that influence backwards compatibility are generative record types and hexadecimal escape sequences in string literals.

Formerly record types defined with define-record-type were non-generative: re-defining a record type with the same name, even if the type definition is completely different, would not create a new type. Instances of the former definition would also be of the newly defined type, provided the type name is the same. Now every definition of a record type creates a completely new type, regardless of the name. This is of course more correct and much safer as it doesn't invalidate previously defined instances.

A second (and much more annoying) change is that R7RS requires hex escape sequences in string literals to be terminated by a semicolon. Unfortunately the change is incompatible to the convention used in most programming languages, including existing many Lisp and Scheme implementations.

What in CHICKEN 5 would looked like this:

   "the color \x1b[31mRED\x1b[0m"

in CHICKEN 6 (and R7RS) must now be (note the semicolon):

   "the color \x1b;[31mRED\x1b;[0m"

The motivation here was probably to avoid having dedicated escape sequences for values that require more than 2 hex digits (e.g. \uNNNN). The change is particularly bad from a compatibility point of view. All string literals that contain the old style of escape sequences must be changed. To keep code working in both CHICKEN 5 and 6 you can use the 4-digit \uNNNN escape sequence which is still valid in all versions.

Foreign Function Interface changes

CHICKEN has a very easy to use foreign function interface, which mostly derives from the fact that the compiler generates C. The alternative approach are binary FFIs that use native code to interface with C code, like libffi, which must reproduce a lot of ABI details to safely interface with C libraries, things like struct alignment and padding, how arguments of various lengths are passed on the stack, etc.

The most notable FFI-related change for CHICKEN 6 is that it allows passing and returning C structs and unions to and from foreign code by value. The contents are copied in and out of bytevectors and wrapped in a block. The components of the struct or union can not be directly manipulated in Scheme but can be passed on to other foreign functions. Additionally, for completeness, you can now also directly pass C99 complex numbers. Note that complex numbers in the FFI are always passed as inexact (i.e., floating-point), as opposed to Scheme complex numbers that may have exact (integer or even rational) real and imaginary components.

Platform support and build system

Here two major changes have been introduced. First, we now have a proper configuration ("configure") script. Formerly, all build parameters were passed as extra arguments to make(1), like this:

   make PREFIX=$HOME/.local ...

This required that for every make(1) invocation, the same set of parameters had to be given to avoid inconsistencies. A configuration script written in portable POSIX sh(1) notation is now provided to perform the configuration step once before building. It also follows the de facto convention used in many GNU programs, where the usual incantation is:

   ./configure; make; make install

Note that we don't use the dreaded "autotools" (autoconf, automake and libtool), which have arcane syntax, are very brittle and produce more problems that they are trying to solve. They were originally designed to port code to now dead or obscure UNIX derivatives, yet fail to provide a straightforward and easy to use configuration tool for modern systems (Linux/BSD, Mac, Windows, mostly). Our configure script is hand written instead of auto-generated, and only checks for the platform differences that are relevant to those platforms that CHICKEN actually supports.

The old style of passing variables to make(1) should still work, but is deprecated.

The second change in the build system is that we cleaned up the confusion about toolchains on Windows systems. There is a bunch of half-maintained flavors of GNU-based C development environments for Windows systems ("MingGW", "MingGW-w64", "MSYS2", etc.) and it is a constant source of pain to support and test all these variants.

There is now one official "blessed" toolchain that we support. Specifically, we recommend Chris Wellon's excellent w64devkit. It contains compilers, build tools and enough of a POSIX environment for building CHICKEN on Windows. We also require a POSIX sh(1) (contained in w64devkit) and have dropped all support for building on a non-POSIX shell, i.e. cmd.exe. This simplifies the build and package management tools considerably. It also ensures we have less environments to test.

Building for Windows Subsystem for Linux (WSL) and Cygwin is of course still supported, but those use the UNIX build setup and need no or very little specific platform support.

Minor changes

Quite a number of minor changes have taken place that either increase the robustness or standards compliance of the system.

syntax-error is now a macro, as required by R7RS. Previously there was a syntax-error procedure in (chicken syntax) with the same argument signature. So where the error was previously raised at runtime, it is now done at expansion time. This is something to take note of when porting code to CHICKEN 6. The invocation is still the same, so the difference can at least be identified easily and corrected, and (scheme base) needs to be imported, of course.

The csc compiler driver passes arguments now properly to subprocesses via execve(2) and not system(3) which reduces shell quoting headaches.

The chicken-install package ("egg") manager locks the build cache directory to avoid conflicts when running multiple installations in parallel. Also, a custom-config feature has been added to places in the package description (.egg) file that specify compile and link options provided by external tools like pkg-config for more portable configuration of native libraries that packages use. The configuration script is expected to be Scheme code. Other eggs can extend the set of possible customisation facilities by providing library code to access them.

The feathers debugger has been removed from the core system and re-packaged as an egg, allowing separate development or replacement. It always was a bit of a proof-of-concept thing that lacks the robustness and flexibility of a real debugger. Some users found it helpful, so we keep it for the time being.

Future directions

Every major release is a chance of fixing long-standing problems with the codebase and address bad design decisions. CHICKEN is now nearly 25 years old and we had many major overhauls of the system. Sometimes these caused a lot of pain, but still we always try to improve things and hopefully make it more enjoyable and practical for our users. There are places in the code that are messy, too complex, or that require cleanup or rewrite, always sitting there waiting to be addressed. On the other hand CHICKEN has been relatively stable compared to many other language implementations and has a priceless community of users that help us improving it. Our users never stop reminding us of what could be better, where the shortcomings are, where things are hard to use or inefficient.

So the final goal is and will always be to make it more robust and easier to use. Performance improvements are always good but are secondary. Strong standards compliance is a requirement, unless it interferes with practicality. We also try to avoid dependencies in the core system at all costs. This eases porting and avoids friction that is very often introduced by inadequate tools or overdesigned development environments.

Some moody ramblings about Scheme standards

The switch to seamless support for R7RS (small) was due for quite a while. R7RS is by now the generally accepted Scheme standard that implementations try to follow. How the further development of R7RS (large) will turn out remains to be seen, but I'm not very confident that it will result in anything more that just a shapeless agglomeration of features. The current direction seems to be oriented towards creating something that includes everything but the "kitchen-sink" - too ambitious and too much driven by the urge to produce something big and comprehensive.

What always distinguished Scheme from other languages and Lisp dialects was its elegance and minimalism. This resulted in a large number of experimental implementations, the investigation of various directions of programming language semantics and in highly interesting advanced implementation techniques that are still in use today. The expressiveness and the small number of core concepts made it also perfect for teaching computing. It still is great for teaching, even if the tendency to address perceived requirements of the "market" replaces the academic use of Scheme with languages that belong more to the "mainstream". This strikes me as strange, as if learning multiple languages and studying different programming paradigms couldn't help in obtaining a broader view of software development; or as if one is somehow wasting time by exploring the world of programming in a non-mainstream language.

Repeatedly the small size and limited scope of Scheme has driven a number of enthusiasts dedicated to favouring a broader use in the industry to demand "bigness". They dream of a comprehensive standard that will support everything and please everyone and makes it easy to write portable and non-trivial applications in Scheme and have them run on large number of implementations. With this comes the tacit expectation that implementers will just follow such a large standard and implement it faithfully.

But what made Scheme successful (and beautiful) was the small size, the small number of powerful concepts, the minimalism, the joy in experimentation. Trying to create the Comprehensive Mother of all Schemes is in my opinion a waste of time. In fact, it makes Scheme less relevant. Large languages inevitably die - the warts and inconsistencies that crop up when you try to design too much up front will just get more blatant as the language ages and will annoy users, constrain implementers and make people search for alternatives.

You can already write serious programs and use a large number of libraries in Scheme: just install CHICKEN, Guile or (even) Racket and get going. The code will to a certain part not be portable across implementations, that's unavoidable, but to use dynamic languages effectively and successfully, some experience with and a certain understanding of the design of the underlying compiler or interpreter is necessary anyway.

Acknowledgements

I would like to thank my employer, bevuta IT GmbH which sponsored part of the effort of preparing a new major release of CHICKEN.

by Peter Bex at Monday, November 18, 2024

Friday, November 15, 2024

Scheme Requests for Implementation

SRFI 253: Data (Type-)Checking

SRFI 253 is now in final status.

Data validation and type checking (supposedly) make for more correct code. And faster code too, sometimes. And, in rare cases, code that's easier to follow than un-checked code. Unfortunately, Scheme does not have many (type-)checking primitives out of the box. This SRFI provides some, with the aim of allowing more performant and correct code with minimum effort on the user side. Both (manual) argument checking/validation (check-arg) and return value(s) (values-checked) checking/coercion are provided. Syntax sugar like define-checked and define-record-type-checked is added on top.

by Artyom Bologov at Friday, November 15, 2024

Sunday, November 10, 2024

GNU Guix

Take the Guix User and Contributor Survey

To understand the views of the Guix community we're running a survey that we'd love you to take part in! The Guix User and Contributor Survey is live now, and should take about 10 minutes to fill out. Perfect for doing with a cup of tea and a biscuit!

The Guix project continues to grow and change, with new contributors and users joining our community. We decided to run this survey as it's the best way to gather good quality feedback across the widest cross-section of the community. Of course, there's lots of interesting topics a survey could ask about! We decided to focus on how Guix is used, and how contributors take part in the project.

The survey is being run on LimeSurvey which is a Free Software project and has been used by many other projects for similar surveys. The survey's hosted on the LimeSurvey SaaS so that we don't have the additional task of operating the software. No personal data is asked for (e.g. email addresses), no tracking data is being collected (e.g. IP addresses) and the entries are anonymised.

We'll be making the results and the anonymised data available under the Creative Commons CCO: that way anyone can analyse the data for further insights.

We hope the results of the survey will be used to understand both the Guix project's strengths and areas we can improve. Which is why your input is so important. If you can, please take the survey!

Take the survey now!

by Steve George at Sunday, November 10, 2024

Tuesday, November 5, 2024

The Racket Blog

Racket v8.15

posted by Stephen De Gabrielle


We are pleased to announce Racket v8.15 is now available from https://download.racket-lang.org/.

As of this release:

  • Documentation search results are ordered, with visual cues indicating what their source is (core, main-distribution, etc.). These results are also grouped by language family (Racket, Rhombus, etc.). Search e.g. second to see an example.

  • DrRacket offers to restore previously open files when starting, which can be made the default.

DrRacket restore open files dialog

  • In DrRacket, Images in editing panels can be saved by right-clicking, including those generated by the functional picture libraries pict and 2htdp/image.

DrRacket save image in context menu

Thank you

The following people contributed to this release:

Alec Mills, Alex Knauth, Alexander Shopov, Ashlynn Anderson, Ashton Wiersdorf, Ben Greenman, Benjamin Yeung, Bob Burger, Bogdan Popa, Breck Yunits, Carl Gay, Claes Wallin (韋嘉誠), CooperCorad, Crystal Jacobs, D. Ben Knoble, Dexter Santucci, Eduardo Cavazos, Emil Szpakowski, evelynmitchell, Greg Hendershott, Gunnar Ahlberg, Gwen Weinholt, Idiomdrottning, Ikko Eltociear Ashimine, Jacqueline Firth, Jarhmander, Jay McCarthy, Jens Axel Søgaard, Jimmy McNutt, jinser, Jinser Kafka, John Clements, lukejianu, Marc Nieper-Wißkirchen, Matej Fandl, Matthew Flatt, Matthias Felleisen, Michael Ballantyne, Mike Sperber, olopierpa, Paul Morris, Phil Nguyen, Philip McGrath, Robby Findler, Ronald Garcia, Ryan Culpepper, Sam Phillips, Sam Tobin-Hochstadt, Siddhartha Kasivajhula, Sorawee Porncharoenwase, Stephen De Gabrielle, Syntacticlosure, Taylor Allred, Tomas Fabrizio Orsi, Wing Hei Chan, and Yafei Yang.

Racket is a community developed open source project and we welcome new contributors. See racket/README.md to learn how you can be a part of this amazing project.

Feedback Welcome

Questions and discussion welcome at the Racket community Discourse announcement(join) or on the Racket Discord.

Please share

If you can - please help get the word out to users and platform specific repo packagers

Racket - the Language-Oriented Programming Language - version 8.15 is now available from https://download.racket-lang.org

See https://blog.racket-lang.org/2024/08/racket-v8-15.html for the release announcement and highlights.

by John Clements, Stephen De Gabrielle at Tuesday, November 5, 2024

Monday, October 28, 2024

Idiomdrottning

Watching Jellyfin videos with VLC

Okay so if you wanna watch a Jellyfin video with VLC, go to your Jellyfin instance’s web view where you can copy a stream URL and it’ll look like this:

https://jellyfinserver.tld/Items/TheIdForTheVideoGoesHere/Download?api_key=YourKeyIdGoesHere

And you can paste that URL into your VLC.

If you want to grab a whole season’s worth of video IDs that you can mangle into a .pls, you can with Jellyfin’s API! Here’s an example using httpie and jq.

https jellyfinserver.tld/Shows/ShowIdThatYouAlsoCanFindFromTheWebView/Episodes X-Emby-Token:YourKeyIdGoesHere season==1 |jq -r '.Items[].Id'

With VLC, watching stream URLs from .pls files is way better than watching individually pasted streams since it can remember how far into the video you were.

Pretty sure this works with other stream players too, like mpd.

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Monday, October 28, 2024

Tuesday, October 22, 2024

spritely.institute

Make a game with Hoot for the Autumn Lisp Game Jam!

Hi everyone, it's that time of year again: the Autumn Lisp Game Jam is upon us!

In case you're unfamiliar, the Lisp Game Jam is a twice yearly ten day game jam co-hosted by our very own Dave Thompson, in which participants make games using their favorite Lisp dialects. It's a much more relaxed schedule than your average game jam to foster a more inclusive turnout.

Although there are no prizes, there is time reserved at the end to play everyone's games and give feedback! ✨ Of course, the real game jam is the Lisps you used along the way ☺�

This fall's game jam starts on Friday, October 25th. Head on over to the official game jam page on itch.io for helpful tips and information on how to join!

Spritely is here to help

Do you wish you could use Scheme in the browser? Well thanks to Hoot, our Scheme to WebAssembly compiler, you can! In fact, we've prepared a game jam template repository to get you up and running on making a 2D game with Hoot and HTML5 canvas. It even comes with a game demo of its own!

If you run into any issues with Hoot or have ideas on how to make it even better, we'd love to hear about them.

For help with Hoot or the game template during the jam, you can post questions on our community forum or in this itch.io forum thread.

And if you'd like to show off your game in progress, we'd love to hear about it on our community forum!

Further reading

If you'd like to learn more about past game jams and what we've built, here are some of our previous posts to get you started.

Thanks for reading, and see you at the itch arcade! 👾🕹�

by tessa (contact@spritely.institute) at Tuesday, October 22, 2024

Monday, October 21, 2024

GNU Guix

Build User Takeover Vulnerability (CVE-2024-52867)

A security issue, known as CVE-2024-52867, has been identified in guix-daemon which allows for a local user to gain the privileges of any of the build users and subsequently use this to manipulate the output of any build. You are strongly advised to upgrade your daemon now (see instructions below), especially on multi-user systems.

This exploit requires the ability to start a derivation build and the ability to run arbitrary code with access to the store in the root PID namespace on the machine the build occurs on. As such, this represents an increased risk primarily to multi-user systems and systems using dedicated privilege-separation users for various daemons: without special sandboxing measures, any process of theirs can take advantage of this vulnerability.

Vulnerability

For a very long time, guix-daemon has helpfully made the outputs of failed derivation builds available at the same location they were at in the build container. This has aided greatly especially in situations where test suites require the package to already be installed in order to run, as it allows one to re-run the test suite interactively outside of the container when built with --keep-failed. This transferral of store items from inside the chroot to the real store was implemented with a simple rename, and no modification of the store item or any files it may contain.

If an attacker starts a build of a derivation that creates a binary with the setuid and/or setgid bit in an output directory, then, and the build fails, that binary will be accessible unaltered for anybody on the system. The attacker or a cooperating user can then execute the binary, gain the privileges, and from there use a combination of signals and procfs to freeze a builder, open any file it has open via /proc/$PID/fd, and overwrite it with whatever it wants. This manipulation of builds can happen regardless of which user started the build, so it can work not only for producing compromised outputs for commonly-used programs before anybody else uses them, but also for compromising any builds another user happens to start.

A related vulnerability was also discovered concerning the outputs of successful builds. These were moved - also via rename() - outside of the container prior to having their permissions, ownership, and timestamps canonicalized. This means that there also exists a window of time for a successful build's outputs during which a setuid/setgid binary can be executed.

In general, any time that a build user running a build for some submitter can get a setuid/setgid binary to a place the submitter can execute it, it is possible for the submitter to use it to take over the build user. This situation always occurs when --disable-chroot is passed to guix-daemon. This holds even in the case where there are no dedicated build users, and builds happen under the same user the daemon runs as, as happens during make check in the guix repository. Consequently, if a permissive umask that allows execute permission for untrusted users on directories all the way to a user's guix checkout is used, an attacker can use that user's test-environment daemon to gain control over their user while make check is running.

Mitigation

This security issue has been fixed by two commits. Users should make sure they have updated to the second commit to be protected from this vulnerability. Upgrade instructions are in the following section. If there is a possibility that a failed build has left a setuid/setgid binary lying around in the store by accident, run guix gc to remove all failed build outputs.

The fix was accomplished by sanitizing the permissions of all files in a failed build output prior to moving it to the store, and also by waiting to move successful build outputs to the store until after their permissions had been canonicalized. The sanitizing was done in such a way as to preserve as many non-security-critical properties of failed build outputs as possible to aid in debugging. After applying these two commits, the guix package in Guix was updated so that guix-daemon deployed using it would use the fixed version.

If you are using --disable-chroot, whether with dedicated build users or not, make sure that access to your daemon's socket is restricted to trusted users. This particularly affects anyone running make check and anyone running on GNU/Hurd. The former should either manually remove execute permission for untrusted users on their guix checkout or apply this patch, which restricts access to the test-environment daemon to the user running the tests. The latter should adjust the ownership and permissions of /var/guix/daemon-socket, which can be done for Guix System users using the new socket-directory-{perms,group,user} fields in this patch.

A proof of concept is available at the end of this post. One can run this code with:

guix repl -- setuid-exposure-vuln-check.scm

This will output whether the current guix-daemon being used is vulnerable or not. If it is not vulnerable, the last line will contain your system is not vulnerable, otherwise the last line will contain YOUR SYSTEM IS VULNERABLE.

Upgrading

Due to the severity of this security advisory, we strongly recommend all users to upgrade their guix-daemon immediately.

For Guix System, the procedure is to reconfigure the system after a guix pull, either restarting guix-daemon or rebooting. For example:

guix pull
sudo guix system reconfigure /run/current-system/configuration.scm
sudo herd restart guix-daemon

where /run/current-system/configuration.scm is the current system configuration but could, of course, be replaced by a system configuration file of a user's choice.

For Guix running as a package manager on other distributions, one needs to guix pull with sudo, as the guix-daemon runs as root, and restart the guix-daemon service, as documented. For example, on a system using systemd to manage services, run:

sudo --login guix pull
sudo systemctl restart guix-daemon.service

Note that for users with their distro's package of Guix (as opposed to having used the install script) you may need to take other steps or upgrade the Guix package as per other packages on your distro. Please consult the relevant documentation from your distro or contact the package maintainer for additional information or questions.

Conclusion

Even with the sandboxing features of modern kernels, it can be quite challenging to synthesize a situation in which two users on the same system who are determined to cooperate nevertheless cannot. Guix has an especially difficult job because it needs to not only realize such a situation, but also maintain the ability to interact with both users itself, while not allowing them to cooperate through itself in unintended ways. Keeping failed build outputs around for debugging introduced a vulnerability, but finding that vulnerability because of it enabled the discovery of an additional vulnerability that would have existed anyway, and prompted the use of mechanisms for securing access to the guix daemon.

I would like to thank Ludovic Courtès for giving feedback on these vulnerabilities and their fixes — discussion of which led to discovering the vulnerable time window with successful build outputs — and also for helping me to discover that my email server was broken.

Proof of Concept

Below is code to check if your guix-daemon is vulnerable to this exploit. Save this file as setuid-exposure-vuln-check.scm and run following the instructions above, in "Mitigation."

(use-modules (guix)
             (srfi srfi-34))

(define maybe-setuid-file
  ;; Attempt to create a setuid file in the store, with one of the build
  ;; users as its owner.
  (computed-file "maybe-setuid-file"
                 #~(begin
                     (call-with-output-file #$output (const #t))
                     (chmod #$output #o6000)

                     ;; Failing causes guix-daemon to copy the output from
                     ;; its temporary location back to the store.
                     (exit 1))))

(with-store store
  (let* ((drv (run-with-store store
                (lower-object maybe-setuid-file)))
         (out (derivation->output-path drv)))
    (guard (c (#t
               (if (zero? (logand #o6000 (stat:perms (stat out))))
                   (format #t "~a is not setuid: your system is not \
vulnerable.~%"
                           out)
                   (format #t "~a is setuid: YOUR SYSTEM IS VULNERABLE.

Run 'guix gc' to remove that file and upgrade.~%"
                           out))))
      (build-things store (list (derivation-file-name drv))))))

by Caleb Ristvedt at Monday, October 21, 2024

Thursday, October 17, 2024

spritely.institute

Our first office hours: A recap (and how to join the next one)

In mid-September, the Spritely Institute held our first open office hours event. 🎉

The team was surprised and delighted that ten members of our community came to ask questions and learn more about our work!

A dive into Spritely

After opening with introductions, we asked attendees what brought them here and if they had any questions for the team. Reasons included:

  • Curiosity
  • Wanting to try Spritely technologies for game development and more
  • Tangential interest through Scheme
  • Concerns about social network design
  • Desire to learn more about cryptography
  • Enthusiasm to hear about the institute's roadmap

As for questions, the discussion this time around centered on broad overviews of the Institute and broader community's various initiatives, such as:

Thank you to everyone who joined us for a rousing conversation in September!

What the future holds

Going forward, we're looking to establish a cadence of meeting on the last Wednesday of the month at 2:00 PM Eastern Time (UTC-4/5 depending on Daylight Saving Time), with exceptions in the schedule to account for holidays and so forth.

As previously, reservations are available for the closest new office hours meeting, and drop ins are also welcome!

For our next meeting, we're interested in hosting a discussion on community-driven topics, as well as demoing how to get started with Hoot for the Autumn Lisp Game Jam starting up next Friday, October 25th.

We'll be addressing pre-scheduled project and other technical questions first, so if that describes your needs, you can read more about how to reserve time with us below.

To submit topics for the open discussion, we'd love to hear your thoughts on our community form thread here. We'll add some suggestions first to help get the party started. 🥳

Reserving an office hours slot

If, after filing an issue and/or posting on our forums, you still require further discussion, you can schedule a meeting with a member of the team here.

Dropping in

Alternatively, if you just want to say hello, listen in, or think of a burning question on the day of, you can join us impromptu in the meeting room. Our next meeting as of this post is on Wednesday, October 30th at 2:00 PM EDT (UTC-4)!

In the meantime, we look forward to seeing you around on our community forum. Thanks for reading, and see you soon! 👋

by tessa (contact@spritely.institute) at Thursday, October 17, 2024

Wednesday, October 16, 2024

Idiomdrottning

md, mvd and cpd

I have gotten so much mileage out of these three zsh functions for making directories for over a decade, I should’ve posted them a long time ago but I just didn’t think to.

md () {
	mkdir -p $1
	cd $1
}

mvd () {
	mkdir -p "${@[$#]}"
	mv "$@"
	cd "${@[$#]}"
}

cpd () {
	mkdir -p "${@[$#]}"
	cp -r "$@"
	cd "${@[$#]}"
}

by Idiomdrottning (sandra.snan@idiomdrottning.org) at Wednesday, October 16, 2024

Thursday, October 3, 2024

Andy Wingo

preliminary notes on a nofl field-logging barrier

When you have a generational collector, you aim to trace only the part of the object graph that has been allocated recently. To do so, you need to keep a remembered set: a set of old-to-new edges, used as roots when performing a minor collection. A language run-time maintains this set by adding write barriers: little bits of collector code that run when a mutator writes to a field.

Whippet’s nofl space is a block-structured space that is appropriate for use as an old generation or as part of a sticky-mark-bit generational collector. It used to have a card-marking write barrier; see my article diving into V8’s new write barrier, for more background.

Unfortunately, when running whiffle benchmarks, I was seeing no improvement for generational configurations relative to whole-heap collection. Generational collection was doing fine in my tiny microbenchmarks that are part of Whippet itself, but when translated to larger programs (that aren’t yet proper macrobenchmarks), it was a lose.

I had planned on doing some serious tracing and instrumentation to figure out what was happening, and thereby correct the problem. I still plan on doing this, but instead for this issue I used the old noggin technique instead: just, you know, thinking about the thing, eventually concluding that unconditional card-marking barriers are inappropriate for sticky-mark-bit collectors. As I mentioned in the earlier article:

An unconditional card-marking barrier applies to stores to slots in all objects, not just those in oldspace; a store to a new object will mark a card, but that card may contain old objects which would then be re-scanned. Or consider a store to an old object in a more dense part of oldspace; scanning the card may incur more work than needed. It could also be that Whippet is being too aggressive at re-using blocks for new allocations, where it should be limiting itself to blocks that are very sparsely populated with old objects.

That’s three problems. The second is well-known. But the first and last are specific to sticky-mark-bit collectors, where pages mix old and new objects.

a precise field-logging write barrier

Back in 2019, Steve Blackburn’s paper Design and Analysis of Field-Logging Write Barriers took a look at the state of the art in precise barriers that record not regions of memory that have been updated, but the precise edges (fields) that were written to. He ends up re-using this work later in the 2022 LXR paper (see §3.4), where the write barrier is used for deferred reference counting and a snapshot-at-the-beginning (SATB) barrier for concurrent marking. All in all field-logging seems like an interesting strategy. Relative to card-marking, work during the pause is much less: you have a precise buffer of all fields that were written to, and you just iterate that, instead of iterating objects. Field-logging does impose some mutator cost, but perhaps the payoff is worth it.

To log each old-to-new edge precisely once, you need a bit per field indicating whether the field is logged already. Blackburn’s 2019 write barrier paper used bits in the object header, if the object was small enough, and otherwise bits before the object start. This requires some cooperation between the collector, the compiler, and the run-time that I wasn’t ready to pay for. The 2022 LXR paper was a bit vague on this topic, saying just that it used “a side table”.

In Whippet’s nofl space, we have a side table already, used for a number of purposes:

  1. Mark bits.

  2. Iterability / interior pointers: is there an object at a given address? If so, it will have a recognizable bit pattern.

  3. End of object, to be able to sweep without inspecting the object itself

  4. Pinning, allowing a mutator to prevent an object from being evacuated, for example because a hash code was computed from its address

  5. A hack to allow fully-conservative tracing to identify ephemerons at trace-time; this re-uses the pinning bit, since in practice such configurations never evacuate

  6. Bump-pointer allocation into holes: the mark byte table serves the purpose of Immix’s line mark byte table, but at finer granularity. Because of this though, it is swept lazily rather than eagerly.

  7. Generations. Young objects have a bit set that is cleared when they are promoted.

Well. Why not add another thing? The nofl space’s granule size is two words, so we can use two bits of the byte for field logging bits. If there is a write to a field, a barrier would first check that the object being written to is old, and then check the log bit for the field being written. The old check will be to a byte that is nearby or possibly the same as the one to check the field logging bit. If the bit is unsert, we call out to a slow path to actually record the field.

preliminary results

I disassembled the fast path as compiled by GCC and got something like this on x86-64, in AT&T syntax, for the young-generation test:

mov    %rax,%rdx
and    $0xffffffffffc00000,%rdx
shr    $0x4,%rax
and    $0x3ffff,%eax
or     %rdx,%rax
testb  $0xe,(%rax)

The first five instructions compute the location of the mark byte, from the address of the object (which is known to be in the nofl space). If it has any of the bits in 0xe set, then it’s in the old generation.

Then to test a field logging bit it’s a similar set of instructions. In one of my tests the data type looks like this:

struct Node {
  uintptr_t tag;
  struct Node *left;
  struct Node *right;
  int i, j;
};

Writing the left field will be in the same granule as the object itself, so we can just test the byte we fetched for the logging bit directly with testb against $0x80. For right, we should be able to know it’s in the same slab (aligned 4 MB region) and just add to the previously computed byte address, but the C compiler doesn’t know that right now and so recomputes. This would work better in a JIT. Anyway I think these bit-swizzling operations are just lost in the flow of memory accesses.

For the general case where you don’t statically know the offset of the field in the object, you have to compute which bit in the byte to test:

mov    %r13,%rcx
mov    $0x40,%eax
shr    $0x3,%rcx
and    $0x1,%ecx
shl    %cl,%eax
test   %al,%dil

Is it good? Well, it improves things for my whiffle benchmarks, relative to the card-marking barrier, seeing a 1.05×-1.5× speedup across a range of benchmarks. I suspect the main advantage is in avoiding the “unconditional” part of card marking, where a write to a new object could cause old objects to be added to the remembered set. There are still quite a few whiffle configurations in which the whole-heap collector outperforms the sticky-mark-bit generational collector, though; I hope to understand this a bit more by building a more classic semi-space nursery, and comparing performance to that.

Implementation links: the barrier fast-path, the slow path, and the sequential store buffers. (At some point I need to make it so that allocating edge buffers in the field set causes the nofl space to page out a corresponding amount of memory, so as to be honest when comparing GC performance at a fixed heap size.)

Until next time, onwards and upwards!

by Andy Wingo at Thursday, October 3, 2024