30 Sep 2018

feedPlanet Lisp

Vsevolod Dyomkin: ANN: flight-recorder - a robust REPL logging facility

Interactivity is a principal requirement for a usable programming environment. Interactivity means that there should be a shell/console/REPL or other similar text-based command environment. And a principal requirement for such an environment is keeping history. And not just keeping it, but doing it robustly:

  • recording history from concurrently running sessions
  • keeping unlimited history
  • identifying the time of the record and its context

This allows to freely experiment and reproduce the results of successful experiments, as well as go back to an arbitrary point in time and take another direction of your work, as well as keeping DRY while performing common repetitive tasks in the REPL (e.g. initialization of an environment or context).

flight-recorder or frlog (when you need a distinct name) is a small tool that intends to support all these requirements. It grew out of a frustration with how history is kept in SLIME, so it was primarily built to support this environment, but it can be easily utilized for other shells that don't have good enough history facility. It is possible due to its reliance on the most common and accessible data-interchange facility: text-based HTTP.

frlog is a backend service that supports any client that is able to send an HTTP request.

The backend is a Common Lisp script that can be run in the following manner (probably, the best way to do it is inside screen):


sbcl --noprint --load hunch.lisp -- -port 7654 -script flight-recorder.lisp

If will print a bunch of messages that should end with the following line (modulo timestamp):


[2018-09-29 16:00:53 [INFO]] Started hunch acceptor at port: 7654.

The service appends each incoming request to the text file in markdown format: ~/.frlog.md.

The API is just a single endpoint - /frlog that accepts GET and POST requests. The parameters are:

  • text is the content (url-encoded, for sure) of the record that can, alternatively, be sent in the POST request's body (more robust)

Optional query parameters are:

  • title - used to specify that this is a new record: for console-based interactions, usually, there's a command and zero or more results - a command starts the record (and thus should be accompanied with the title: for SLIME interactions it's the current Lisp package and a serial number). An entitled record is added in the following manner:

    ### cl-user (10) 2018-09-29_15:49:17

    (uiop:pathname-directory-pathname )
    If there's no title, the text is added like this:

    ;;; 2018-09-29_15:49:29

    #<program-error @ #x100074bfd72>
  • tag - if provided it signals that the record should be made not to a standard .frlog.md file, but to .frlog-<tag>.md. This allows to easily log a specific group of interactions separately If the response code is 200 everything's fine.

Currently, 2 clients are available:

  • a SLIME client flight-recorder.el that monkey-patches a couple of basic SLIME functions (just load it from Emacs if you have SLIME initialized)
  • and a tiny Lisp client frlog.lisp

P.S. To sum up, more and more I've grown to appreciate simple (sometimes even primitive - the primitive the better :) tools. flight-recorder seems to me to be just like that: it was very easy to hack together, but it solves an important problem for me and, I guess, for many. And it's the modern "Unix way": small independent daemons, text-based formats and HTTP instead of pipes...

P.P.S. frlog uses another tiny tool of mine - hunch that I've already utilized in a number of projects but haven't described yet - it's a topic for another post. In short, it is a script to streamline running hunchentoot that does all the basic setup and reduces the developer's work to just defining the HTTP endpoints.

P.P.P.S. I know, the name is, probably, taken and it's a rather obvious one. But I think it just doesn't matter in this case... :)

30 Sep 2018 5:15pm GMT

31 Aug 2018

feedPlanet Lisp

Quicklisp news: August 2018 Quicklisp dist update now available

New projects:

Updated projects: 3d-matrices, 3d-vectors, a-cl-logger, acclimation, ahungry-fleece, alexa, algebraic-data-library, april, arc-compat, array-utils, bodge-sndfile, caveman, cepl, cepl.drm-gbm, chirp, cl+ssl, cl-ana, cl-bnf, cl-bootstrap, cl-colors2, cl-conllu, cl-csv, cl-dbi, cl-feedparser, cl-flac, cl-flow, cl-fond, cl-gamepad, cl-gendoc, cl-generator, cl-gpio, cl-grace, cl-i18n, cl-k8055, cl-kanren, cl-libuv, cl-mixed, cl-monitors, cl-mpg123, cl-oclapi, cl-opengl, cl-out123, cl-patterns, cl-ppcre, cl-progress-bar, cl-project, cl-pslib, cl-pslib-barcode, cl-sdl2-ttf, cl-soil, cl-soloud, cl-spidev, cl-str, cl-virtualbox, cl-wayland, cl-yesql, clack, claw, clip, clml, closer-mop, clss, clunit2, colleen, configuration.options, conium, croatoan, crypto-shortcuts, curry-compose-reader-macros, dartsclhashtree, deeds, deferred, definitions, delta-debug, deploy, dexador, dissect, dml, documentation-utils, dufy, eazy-gnuplot, eazy-project, eclector, fare-scripts, fast-http, flare, flow, flute, for, form-fiddle, fxml, glsl-spec, glsl-toolkit, golden-utils, gsll, halftone, harmony, humbler, ironclad, jsonrpc, kenzo, lack, lambda-fiddle, lass, legit, lichat-protocol, lichat-serverlib, lichat-tcp-client, lichat-tcp-server, lichat-ws-server, lionchat, lisp-executable, lispbuilder, listopia, lquery, maiden, mcclim, mito, modularize, modularize-hooks, modularize-interfaces, more-conditions, multiposter, neo4cl, nibbles, nineveh, north, oclcl, opticl, overlord, oxenfurt, parachute, pathname-utils, perlre, piping, plump, plump-bundle, plump-sexp, plump-tex, postmodern, qlot, qt-libs, qtools, qtools-ui, racer, random-state, ratify, redirect-stream, rfc2388, rutils, sanitized-params, sel, serapeum, shadow, simple-inferiors, simple-tasks, slime, snooze, softdrink, south, spinneret, staple, stumpwm, sxql, terminfo, thnappy, tooter, trace-db, trivial-arguments, trivial-battery, trivial-benchmark, trivial-clipboard, trivial-gray-streams, trivial-indent, trivial-main-thread, trivial-mimes, trivial-thumbnail, umbra, usocket, uuid, varjo, verbose, vgplot, whofields, with-c-syntax, woo, wookie, xml.location.

Removed projects: cl-clblas, cl-proj.

There are no direct problems with cl-clblas and cl-proj. They are victims of a hard drive crash on my end, and an incomplete recovery. I have not been able to set up the foreign libraries required to build those projects in time for this month's release.

If you want to continue using cl-clblas and cl-proj, there are a few options:

Sorry for any inconvenience this may cause. I hope to have it fully resolved in the September 2018 update.

To get this update, use (ql:update-dist "quicklisp").

Enjoy!

31 Aug 2018 8:02pm GMT

27 Aug 2018

feedPlanet Lisp

Zach Beane: A Road to Common Lisp - Steve Losh

A Road to Common Lisp - Steve Losh

27 Aug 2018 4:47pm GMT

26 Aug 2018

feedPlanet Lisp

Paul Khuong: Restartable Sequences With the Polysemic Null Segment Selector

Implementing non-blocking algorithms is one of the few things that are easier to code in a kernel than in userspace (the only other one I can think of is physically wrecking a machine). In the kernel, we only have to worry about designing a protocol that achieves forward progress even if some threads stop participating. We must guarantee the absence of conceptual locks (we can't have operations that must be paired, or barriers that everyone must reach), but are free to implement the protocol by naïvely spinlocking around individual steps: kernel code can temporarily disable preemption and interrupts to bound a critical section's execution time.

Getting these non-blocking protocols right is still challenging, but the challenge is one fundamental for reliable systems. The same problems, solutions, and space/functionality trade-offs appear in all distributed systems. Some would even argue that the kind of interfaces that guarantee lock- or wait- freedom are closer to the object oriented ideals.

Of course, there is still a place for clever instruction sequences that avoid internal locks, for code that may be paused anywhere without freezing the whole system: interrupts can't always be disabled, read operations should avoid writing to shared memory if they can, and a single atomic read-modify-write operation may be faster than locking. The key point for me is that this complexity is opt-in: we can choose to tackle it incrementally, as a performance problem rather than as a prerequisite for correctness.

We don't have the same luxury in userspace. We can't start by focusing on the fundamentals of a non-blocking algorithm, and only implement interruptable sequences where it makes sense. Userspace can't disable preemption, so we must think about the minutiae of interruptable code sequences from the start; non-blocking algorithms in userspace are always in hard mode, where every step of the protocol might be paused at any instruction.

Specifically, the problem with non-blocking code in user space isn't that threads or processes can be preempted at any point, but rather that the preemption can be observed. It's a PCLSRing issue! Even Unices guarantee programmers won't observe a thread in the middle of a syscall: when a thread (process) must be interrupted, any pending syscall either runs to completion, or returns with an error1. What we need is a similar guarantee for steps of our own non-blocking protocols2.

Hardware transactional memory kind of solves the problem (preemption aborts any pending transaction) but is a bit slow3, and needs a fallback mechanism. Other emulation schemes for PCLSRing userspace code divide the problem in two:

  1. Determining that another thread was preempted in the middle of a critical section.
  2. Guaranteeing that that other thread will not blindly resume executing its critical section (i.e., knowing that the thread knows that we know it's been interrupted4).

The first part is relatively easy. For per-CPU data, it suffices to observe that we are running on a given CPU (e.g., core #4), and that another thread claims to own the same CPU's (core #4's) data. For global locks, we can instead spin for a while before entering a slow path that determines whether the holder has been preempted, by reading scheduling information in /proc.

The second part is harder. I have played with schemes that relied on signals, but was never satisfied: I found Linux perf will rarely, but not never, drop interrupts when I used it to "profile" context switches, and signaling when we determine that the holder has been pre-empted has memory visibility issues for per-CPU data5.

Until earlier this month, the best known solution on mainline Linux involved cross-modifying code! When a CPU executes a memory write instruction, that write is affected by the registers, virtual memory mappings, and the instruction's bytes. Contemporary operating systems rarely let us halt and tweak another thread's general purpose registers (Linux won't let us self-ptrace, nor pause an individual thread). Virtual memory mappings are per-process, and can't be modified from the outside. The only remaining angle is modifying the premptee's machine code.

That's what Facebook's experimental library Rseq (restartable sequences) actually does.

I'm not happy with that solution either: while it "works," it requires per-thread clones of each critical section, and makes us deal with cross-modifying code. I'm not comfortable with leaving code pages writable, and we also have to guarantee the pre-emptee's writes are visible. For me, the only defensible implementation is to modify the code by mmap-ing pages in place, which incurs an IPI per modification. The total system overhead thus scales superlinearly with the number of CPUs.

With Mathieu Desnoyers's, Paul Turner's, and Andrew Hunter's patch to add an rseq syscall to Linux 4.18, we finally have a decent answer. Rather than triggering special code when a thread detects that another thread has been pre-empted in the middle of a critical section, userspace can associate recovery code with the address range for each restartable critical section's instructions. Whenever the kernel preempts a thread, it detects whether the interruptee is in such a restartable sequence, and, if so, redirects the instruction pointer to the associated recovery code. This essentially means that critical sections must be read-only except for the last instruction in the section, but that's not too hard to satisfy. It also means that we incur recovery even when no one would have noticed, but the overhead should be marginal (there's at most one recovery per timeslice), and we get a simpler programming model in return.

Earlier this year, I found another way to prevent critical sections from resuming normal execution after being preempted. It's a total hack that exercises a state saving defect in Linux/x86-64, but I'm comfortable sharing it now that Rseq is in mainline: if anyone needs the functionality, they can update to 4.18, or backport the feature.

Here's a riddle!

riddle.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static const char values[] = { 'X', 'Y' };

static char
read_value(void)
{
        /*
         * New feature in GCC 6; inline asm would also works.
         * https://gcc.gnu.org/onlinedocs/gcc-6.1.0/gcc/Named-Address-Spaces.html#Named-Address-Spaces
         */
        return *(const __seg_gs char *)(uintptr_t)values;
}

int
main(int argc, char **argv)
{
        /* ... */
        char before_switch = read_value();  /* Returns 'X'. */
        usleep(1000 * 1000);  /* Or any other wait for preemption. */
        char after_switch = read_value();  /* Returns 'Y'. */
        /* ... */
}

With an appropriate setup, the read_value function above will return a different value once the executing thread is switched out. No, the kernel isn't overwriting read-only data while we're switched out. When I listed the set of inputs that affect a memory store or load instruction (general purpose registers, virtual memory mappings, and the instruction bytes), I left out one last x86 thing: segment registers.

Effective addresses on x86oids are about as feature rich as it gets: they sum a base address, a shifted index, a constant offset, and, optionally, a segment base. Today, we simply use segment bases to implement thread-local storage (each thread's FS or GS offset points to its thread-local block), but that usage repurposes memory segmentation, an old 8086 feature... and x86-64 still maintains some backward compatibility with its 16-bit ancestor. There's a lot of unused complexity there, so it's plausible that we'll find information leaks or otherwise flawed architectural state switching by poking around segment registers.

How to set that up

After learning about this trick to observe interrupts from userland, I decided to do a close reading of Linux's task switching code on x86-64 and eventually found this interesting comment6.

Observing a value of 0 in the FS or GS registers can mean two things:

  1. Userspace explicitly wrote the null segment selector in there, and reset the segment base to 0.
  2. The kernel wrote a 0 in there before setting up the segment base directly, with WR{FS,GS}BASE or by writing to a model-specific register (MSR).

Hardware has to efficiently keep track of which is actually in effect. If userspace wrote a 0 in FS or GS, prefixing an instruction with that segment has no impact; if the MSR write is still active (and is non-zero), using that segment must impact effective address computation.

There's no easy way to do the same in software. Even in ring 0, the only sure-fire way to distinguish between the two cases is to actually read the current segment base value, and that's slow. Linux instead fast-paths the common case, where the segment register is 0 because the kernel is handling segment bases. It prioritises that use case so much that the code knowingly sacrifices correctness when userspace writes 0 in a segment register after asking the kernel to setup its segment base directly.

This incorrectness is acceptable because it only affects the thread that overwrites its segment register, and no one should go through that sequence of operations. Legacy code can still manipulate segment descriptor tables and address them in segment registers. However, being legacy code, it won't use the modern syscall that directly manipulates the segment base. Modern code can let the kernel set the segment base without playing with descriptor tables, and has no reason to look at segment registers.

The only way to observe the buggy state saving is to go looking for it, with something like the code below (which uses GS because FS is already taken by glibc to implement thread-local storage).

h4x.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#define RUN_ME /*
gcc-6 -std=gnu99 $0 -o h4x && ./h4x; exit $?;

Should output
Reads: XXYX
Re-reads: XYX
*/
#define _GNU_SOURCE
#include <asm/prctl.h>
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <sys/prctl.h>
#include <sys/syscall.h>
#include <unistd.h>

static const char values[] = { 'X', 'Y' };

/* Directly set GS's base with a syscall. */
static void
set_gs_base(unsigned long base)
{
        int ret = syscall(__NR_arch_prctl, ARCH_SET_GS, base);
        assert(ret == 0);
}

/* Write a 0 in GS. */
static void
set_gs(unsigned short value)
{
        asm volatile("movw %0, %%gs" :: "r"(value) : "memory");
}

/* Read gs:values[0]. */
static char
read_value(void)
{
        /*
         * New feature in GCC 6; inline asm would also works.
         * https://gcc.gnu.org/onlinedocs/gcc-6.1.0/gcc/Named-Address-Spaces.html#Named-Address-Spaces
         */
        return *(const __seg_gs char *)(uintptr_t)values;
}

int
main(int argc, char **argv)
{
        char reads[4];
        char re_reads[3];

        reads[0] = read_value();
        reads[1] = (set_gs(0), read_value());
        reads[2] = (set_gs_base(1), read_value());
        reads[3] = (set_gs(0), read_value());

        printf("Reads: %.4s\n", reads);
        fflush(NULL);

        re_reads[0] = read_value();
        re_reads[1] = (usleep(1000 * 1000), read_value());
        re_reads[2] = (set_gs(0), read_value());

        printf("Re-reads: %.3s\n", re_reads);
        return 0;
}

Running the above on my Linux 4.14/x86-64 machine yields

$ gcc-6 -std=gnu99 h4x.c && ./a.out
Reads: XXYX
Re-reads: XYX

The first set of reads shows that:

  1. our program starts with no offset in GS (reads[0] == values[0])
  2. explicitly setting GS to 0 does not change that (reads[1] == values[0])
  3. changing the GS base to 1 with arch_prctl does work (reads[2] == values[1])
  4. resetting the GS selector to 0 resets the base (reads[3] == values[0]).

The second set of reads shows that:

  1. the reset base survives short syscalls (re_reads[0] == values[0])
  2. an actual context switch reverts the GS base to the arch_prctl value (re_reads[1] == values[1])
  3. writing a 0 in GS resets the base again (re_reads[2] == values[0]).

Cute hack, why is it useful?

The property demonstrated in the hack above is that, after our call to arch_prctl, we can write a 0 in GS with a regular instruction to temporarily reset the GS base to 0, and know it will revert to the arch_prctl offset again when the thread resumes execution, after being suspended.

We now have to ensure our restartable sequences are no-ops when the GS base is reset to the arch_prctl offset, and that the no-op is detected as such. For example, we could set the arch_prctl offset to something small, like 4 or 8 bytes, and make sure that any address we wish to mutate in a critical section is followed by 4 or 8 bytes of padding that can be detected as such. If a thread is switched out in the middle of a critical section, its GS base will be reset to 4 or 8 when the thread resumes execution; we must guarantee that this offset will make the critical section's writes fail.

If a write is a compare-and-swap, we only have to make sure the padding's value is unambiguously different from real data: reading the padding instead of the data will make compare-and-swap fail, and the old value will tell us that it failed because we read padding, which should only happen after the section is pre-empted. We can play similar tricks with fetch-and-add (e.g., real data is always even, while the padding is odd), or atomic bitwise operations (steal the sign bit).

If we're willing to eat a signal after a context switch, we can set the arch_prctl offset to something very large, and take a segmentation fault after being re-scheduled. Another option is to set the arch_prctl offset to 1, and use a double-wide compare-and-swap (CMPXCHG16B), or turn on the AC (alignment check) bit in EFLAGS. After a context switch, our destination address will be misaligned, which will trigger a SIGBUS that we can handle.

The last two options aren't great, but, if we make sure to regularly write a 0 in GS, signals should be triggered rarely, only when pre-emption happens between the last write to GS and a critical section. They also have the advantages of avoiding the need for padding, and making it trivial to detect when a restartable section was interrupted. Detection is crucial because it often isn't safe to assume an operation failed when it succeeded (e.g., unwittingly succeeding at popping from a memory allocator's freelist would leak memory). When a GS-prefixed instruction fails, we must be able to tell from the instruction's result, and nothing else. We can't just check if the segment base is still what we expect, after the fact: our thread could have been preempted right after the special GS-prefixed instruction, before our check.

Once we have restartable sections, we can use them to implement per-CPU data structures (instead of per-thread), or to let thread acquire locks and hold them until they are preempted: with restartable sections that only write if there was no preemption between the lock acquisition and the final store instruction, we can create a revocable lock abstraction and implement wait-free coöperation or flat-combining.

Unfortunately, our restartable sections will always be hard to debug: observing a thread's state in a regular debugger like GDB will reset the GS base and abort the section. That's not unique to the segment hack approach. Hardware transactional memory will abort critical sections when debugged, and there's similar behaviour with the official rseq syscall. It's hard enough to PCLSR userspace code; it would be even harder to PCLSR-except-when-the-interruption-is-for-debugging.

Who's to blame?

The null GS hack sounds like it only works because of a pile of questionable design decisions. However, if we look at the historical context, I'd say everything made sense.

Intel came up with segmentation back when 16 bit pointers were big, but 64KB of RAM not quite capacious enough. They didn't have 32 bit (never mind 64 bit) addresses in mind, nor threads; they only wanted to address 1 MB of RAM with their puny registers. When thread libraries abused segments to implement thread-local storage, the only other options were to over-align the stack and hide information there, or to steal a register. Neither sounds great, especially with x86's six-and-a-half general purpose registers. Finally, when AMD decided to rip out segmentation, but keep FS and GS, they needed to make porting x86 code as easy as possible, since that was the whole value proposition for AMD64 over Itanium.

I guess that's what systems programming is about. We take our tools, get comfortable with their imperfections, and use that knowledge to build new tools by breaking the ones we already have (#Mickens).

Thank you Andrew for a fun conversation that showed the segment hack might be of interest to someone else, and to Gabe for snarkily reminding us Rseq is another Linux/Silicon Valley re-invention.


  1. That's not as nice as rewinding the PC to just before the syscall, with a fixed up state that will resume the operation, but is simpler to implement, and usually good enough. Classic worst is better (Unix semantics are also safer with concurrency, but that could have been opt-in...).

  2. That's not a new observation, and SUN heads like to point to prior art like Dice's and Garthwaite's Mostly Lock-Free Malloc, Garthwaite's, Dice's, and White's work on Preemption notification for per-CPU buffers, or Harris's and Fraser's Revocable locks. Linux sometimes has to reinvent everything with its special flavour.

  3. For instance, SuperMalloc optimistically uses TSX to access per-CPU caches, but TSX is slow enough that SuperMalloc first tries to use a per-thread cache. Dice and Harris explored the use of hardware transactional lock elision solely to abort on context switches; they maintained high system throughput under contention by trying the transaction once before falling back to a regular lock.

  4. I did not expect systems programming to get near multi-agent epistemic logic ;)

  5. Which is fixable with LOCKed instructions, but that defeats the purpose of per-CPU data.

  6. I actually found the logic bug before the Spectre/Meltdown fire drill and was worried the hole would be plugged. This one survived the purge. fingers crossed

26 Aug 2018 1:57am GMT

25 Aug 2018

feedPlanet Lisp

Nicolas Hafner: Geometry Clipmaps Revisited - Gamedev

header
A while back I wrote a bit about my adventures with a game engine technique called Geometry Clipmaps and my difficulties in implementing them. After spending what was supposed to be a week wherein I create a game fixing and completing an implementation of the Clipmaps instead, I think I'm now ready to talk about it. I'll also try to answer the questions I posed in the previous entry.

Base Geometry

The clipmaps have a base resolution that defines the number of vertices used along an axis per level. We then construct a uniform grid of 1/4th of the vertices along each side. For instance, let's use a base resolution of 1024, so we construct a 256x256 grid. This grid is then used to form a 1024x1024 ring.

base ring

The level-0 ring uses four more instances of this grid to fill out the middle, but every other ring uses the exact same geometry, just scaled up by a power of two.

nested rings

This means we only need a single 256x256 vertex array to render everything. We can even reduce the number of draw calls to one by creating an additional vertex buffer that contains all the per-level grid offsets and level indices, and using instanced rendering. This additional buffer only requires ((12*l)+4)*3 elements, so with a typical 5 levels that would be a negligible 192 floats. This could be further reduced, but as it is it should be good enough for now.

Map Representation

Since each level is represented by 1024x1024 vertices, we need l number of 1024x1024 textures to represent the map data. We can make use of 2D array textures for this. You'll likely want multiple textures to represent all of your data (one for elevation, one for material blends, etc).

texture arrays

In the vertex shader of the clipmap we then look up the value of the height texture corresponding to the current vertex position.

layout (location = 0) in vec3 position;
layout (location = 1) in float level;
layout (location = 2) in vec2 offset;

uniform mat4 view_matrix;
uniform mat4 projection_matrix;
uniform sampler2DArray height_map;

void main(){
  float level_scale = pow(2.0, level);
  float n = textureSize(height_map, 0).x;
  vec2 map_pos = (position.xz + offset)/4;
  
  vec2 tex_off = (map_pos+0.5-1/(n+1))*n;
  float y = texelFetch(height_map, ivec3(tex_off, level), 0).r;
  
  vec2 world_2d = map_pos * level_scale;
  vec4 world = vec4(world_2d.x, y, world_2d.y, 1);
  gl_Position =  projection_matrix * view_matrix * world;
}

Here, position is the position of the vertex in the grid, level is the current level index, and offset is the offset of the grid from the ring's centre. For simplicity's sake we assume the grid vertexes span between -0.5 and +0.5 and thus the offsets between -1.5 and +1.5.

Since the lookup of the texture is precise, we can use the pixel-aligned texelFetch function. You're also going to want a scaling factor in there somewhere in order to make sure you get the height you want, since it has been normalised into unit floats.

You can use the same fetch procedure for any additional maps you might have to retrieve their values and pass them on to the fragment shader, or whatever you like.

Preparation Step

Once you export the full map data from your scene creator, you need to preprocess it into appropriate chunks before it can be used by the clipmaps. You need a directory of chunk files for each level of the clipmaps, with each chunk being of the clipmap resolution. So you start out with level 0, dice the map up and save the chunks to file. Then you subsequently scale the map down linearly by a factor of two and chunk it for the next level.

I recommend using a raw data format for the chunks that only contains the uncompressed pixel data without any header, so that loading it is efficient. Without compression or header you can simply mmap the file and pass the pointer to OpenGL to upload to textures.

Update Step

Finally you need to implement an update step that takes care of uploading new map data to the texture arrays. This is the most complicated part of the whole technique and it has gone through several iterations as I've worked on it. The current version is almost perfect. There's a further optimisation that could be done, but I haven't felt the need to implement it yet.

In any case, since the clipmap chunks and the clipmap region coincide in size, any particular clipmap region can be covered by at most four chunks. So, in order to display a particular region, we upload the sub-regions of the four chunks that make up the region to each level of the clipmap array texture. We can do this thanks to gl:pixel-store's unpack-row-length, which makes it possible to upload sub-regions of a source image.

Calculating the proper offsets isn't terribly exciting, but I've laid out the basic idea in the following image just for completeness' sake.

update regions

And with this finally implemented, the clipmaps are complete!

Or so one would think. Unfortunately the devil is in the details, and there's a lot of those.

Inter-Level Blending

Since each level above loses precision, the height values at the border between the levels is not going to match up exactly. In order to accommodate this, you have to blend smoothly between the two levels, gradually picking values from the higher level as you get closer to the edge.

At this point an attentive reader might notice that, since the vertex resolution is also not matching between two levels, the border is going to have a single edge of an outer level represented by two edges with a vertex in the middle of the inner level. Fortunately for us this is not an issue as long as we ensure that our clipmap textures use linear magnification interpolation. In that case, since the lines between vertices are linearly interpolated themselves, the lookup between two texels of the higher level is going to be interpolated in the same way, giving us a value that lands exactly on the middle point of the edge, just as we need it to be.

The blending factor itself can be calculated from the map_pos using some basic scaling and arithmetic.

vec2 alpha = (abs(map_pos)*2-0.5)*2;
alpha = clamp((alpha+BORDER_OFFSET-(1-BORDER_WIDTH))/BORDER_WIDTH, 0, 1);
float a = max(alpha.x, alpha.y);

The constants BORDER_OFFSET and BORDER_WIDTH allow you to easily designate how far from the border the blend should begin and how much you want to blend. I found 0.1 and 0.25 to be good values, though you might need to experiment depending on the resolution.

blending regions

At this point we simply perform another texture lookup in the outer level and mix the two together.

vec2 tex_off_o = (map_pos/2+0.5)-0.5/n;
float y_o = texture(height_map, vec3(tex_off_o, level+1)).r;
y = mix(y, y_o, a);

In this case we need to make use of the standard texture lookup, since we do want interpolation between texels. This also requires a slightly different texture coordinate calculation of course. You have to repeat this mixing procedure for every other map in order to smoothly transition between levels.

There's one more gotcha here, which is what happens at the outermost level. Since there's no higher level to blend with, we need to catch this. For this purpose we need a uniform that instructs us of the number of levels, and a check to see if we should blend or not.

layout (location = 0) in vec3 position;
layout (location = 1) in float level;
layout (location = 2) in vec2 offset;

uniform mat4 view_matrix;
uniform mat4 projection_matrix;
uniform sampler2DArray height_map;
uniform int levels;

void main(){
  float level_scale = pow(2.0, level);
  float n = textureSize(height_map, 0).x;
  vec2 map_pos = (position.xz + offset)/4;
  
  vec2 tex_off = (map_pos+0.5-1/(n+1))*n;
  float y = texelFetch(height_map, ivec3(tex_off, level), 0).r;
  
  if(level+1 < levels){
    vec2 tex_off_o = (map_pos/2+0.5)-0.5/n;
    float y_o = texture(height_map, vec3(tex_off_o, level+1)).r;
    y = mix(y, y_o, a);
  }
  
  vec2 world_2d = map_pos * level_scale;
  vec4 world = vec4(world_2d.x, y, world_2d.y, 1);
  gl_Position =  projection_matrix * view_matrix * world;
}

With this in place we should now have a smooth display of the entire clipmap.

As long as we don't move, that is.

Moving Updates

When the camera or player moves, the clipmaps need to be updated. We already have the update of the actual underlying elevation maps covered, but that's not good enough. Since the elevation maps are pixel-aligned, they are going to pop into place once the threshold has been crossed to load the next row of pixels in. Naturally this popping effect is very jarring and not acceptable.

Interestingly enough I don't recall any of the papers talking about this problem. I haven't re-read them to check, but I'm quite sure about it since I think I would have remembered.

In order to deal with this popping problem we have to physically move vertices by the remainder of the grid motion. As in, if our current level clipmap grid is unit-sized, then we need to shift the vertices in xz direction by mod(pos, 1.0) to compensate for the movement.

vec2 mov_off = mod(world_pos.xz, level_scale)/n;
vec2 world_2d = (map_pos * level_scale) - mov_off;

Naturally, we need to blend this between regions as well.

vec2 mov_off_o = mod(world_pos.xz, level_scale*2)/n;
mov_off = mix(mov_off, mov_off_o, a);

This will make the height transitions look buttery smooth, even in the face of continuous movement. It's almost perfect.

Adjusting Inter-Level Map Lookup for Moving Updates

Since we shift the physical vertices for the elevation, we don't need to change how the values are looked up in the texture. This is not the same for any other map, which might be used for material lookup or other purposes in the fragment shader. The texture coordinates for those maps needs to be adjusted.

vec3 tex_i = vec3(tex_off/n, level);
vec3 tex_o = vec3(tex_off_o-a/(2*n), level+1);

This is almost perfect, but unfortunately there's still a small bit of popping going on, namely when two adjacent levels are off-by-one in their displayed maps. This effect is only really visible on low-resolution clipmaps, but I'd still like to figure out how to fix it at some point. At the time of writing this I had played around trying to fix it for around an hour and then put it off for later.

Surface Normals

If you're going to use any kind of lighting engine, you're likely going to need surface normals for the clipmap. You could add another array texture that has this information baked in beforehand, but that would increase the amount of data that's being streamed quite a bit. It's easier and probably more efficient to just calculate the normals in the vertex shader.

float yu = texelFetch(height_map, ivec3(min(n-1, tex_off.x+1), tex_off.y, level), 0).r;
float yv = texelFetch(height_map, ivec3(tex_off.x, min(n-1, tex_off.y+1), level), 0).r;
vec3 normal = normalize(vec3(y-yu, 0.5, y-yv));

And of course we need to blend this as well.

float yu_o = texture(height_map, vec3(tex_off_o+vec2(1/n,0), level+1)).r;
float yv_o = texture(height_map, vec3(tex_off_o+vec2(0,1/n), level+1)).r;
yu = mix(yu, yu_o, a);
yv = mix(yv, yv_o, a);

Not too bad!

Concave Geometry

Since elevation maps can only represent convex geometry, concave geometry like caves, houses, and so forth need to be handled separately. In order to allow this, I attempted to use a simple geometry shader that punches holes into the terrain where the height value is zero.

layout(triangles) in;
layout(triangle_strip, max_vertices = 3) out;
in vec3 world[];

void main(){
  if(world[0].y*world[1].y*world[2].y != 0){
    int i;
    for(i = 0;i < gl_in.length();i++){
      gl_Position = gl_in[i].gl_Position;
      EmitVertex();
    }
    EndPrimitive();
  }
}

With the holes punched this would allow rendering in parts of the map that would be concave in place of the hole. Unfortunately it turns out that geometry shaders are super slow and this tears my frame rate in half. There's the other option of using discard; in the fragment shader, but that has its issues too. At this point I'm not sure yet how I'll handle this case.

Besides, I don't have a system for general mesh streaming yet, so I'll probably think about this once I get to it. If you have ideas though, please do let me know.

Putting it All Together

Implementing this technique has been a long, arduous process. It has cost me multiple attempts and many hours of fiddling around and trying things out. Still, I'm quite happy to be able to say that I've got a technique implemented and working in Trial that is typically employed in big, commercial, triple-A titles.

You can find the current implementation of the clipmaps in the Trial repository. It's still making some shortcuts for me to test things, but I'm sure I'll get it to a usable, modular point soon enough. I hope that this entry has been helpful for people trying to understand this technique, and if not that, then I at least hope it has given people a bit of an appreciation for the work that has gone into it.

For now, here's a short in-engine rendering of a basic terrain region I generated using WorldCreator. It's rendered live using five levels of clipmaps with a base resolution of 1024x1024. Rendering is done using a very, very primitive phong renderer with solid colour mixing. No textures or anything fancy is applied, so it looks rather basic. The map is also not scaled quite right, so things look a bit squashed. My apologies for that.

Finally I'd like to apologise for the lack of Lisp in this entry! After all, all the code snippets are GLSL code. I hope that you'll at least trust me when I say that everything except for the shaders was indeed implemented in Lisp.

25 Aug 2018 7:47pm GMT

19 Aug 2018

feedPlanet Lisp

Hans Hübner: Using the VMS PATCH utility to fix a VAX LISP issue

In my previous post about VAX LISP, I complained about a misfeature of the editor that prevented binding editor functions to the Ctrl-S and Ctrl-Q keys. In the manual, it is stated that these keys cannot be bound due to "system restrictions". It appears, though, that it is a measure to prevent users from footing themselves in the foot because Ctrl-S and Ctrl-Q could be sent by terminals to implement software flow control. Software flow control is optional, though; it can be switched on and off for each terminal line and it is not needed for virtual terminal connections (Telnet, DECNET) as flow control is implemented by the network layer and networked terminal sessions usually have enough buffer space. Thus, reserving Ctrl-S and Ctrl-Q really only makes sense for asynchronous terminal lines that require software flow control, and there is no reason to reserve these characters for all terminal sessions, regardless of technology.
I am used to having Ctrl-S and Ctrl-Q be bound to certain functions from GNU Emacs, and I want to use the same bindings with VAX LISP as they've become part of my muscle memory. Thus, I wanted to remove the explicit checks for these keys in the EDITOR::BIND-COMMAND and BIND-KEYBOARD-FUNCTION functions. Lacking the source code to VAX LISP, I could not just remove the checks and recompile, so I needed a different way.
This is where the VMS PATCH utility comes into play. It is a standard tool that is used to modify program executables, usually to remove bugs without requiring a full reinstallation of the software package that needs to be fixed.

Finding what to patch

In order to remove the checks for Ctrl-S/Q in EDITOR::BIND-COMMAND and BIND-KEYBOARD-FUNCTION, I disassembled the two function using the standard VAX LISP function DISASSEMBLE. VAX assembler code is easy to read, so it was rather straightforward to find out how the checks work. Here is the relevant extract of the disassembly output from the VAX LISP BIND-KEYBOARD-FUNCTION function:

000FC  MOVQ   BIND, -(STACK)
000FF  MOVL   -10(FRAME), -(STACK)
00103  MOVZBL #89, -(STACK)
00107  MOVZBL #99, -(STACK)
0010B  MOVAB  18(STACK), FRAME
0010F  MOVL   'CHAR/=, LEX
00113  MOVL   4(LEX), FUNC
00117  JMP    @4(FUNC)
0011A  CMPL   RES, SV
0011D  BEQL   121
0011F  BRB    145
00121  MOVL   FRAME, -(STACK)
00124  MOVL   #A28, -(STACK)
0012B  MOVQ   BIND, -(STACK)
0012E  MOVL   '"The character argument must be a control character (other than~%~
            CTRL/S or CTRL/Q): ~S", -(STACK)

Apparently, #89 and #99 refer to Ctrl-S and Ctrl-Q, and the CHAR/= function is called to check whether the argument is one of those characters.
The easiest way to get rid of the check seemed to me to replace the BEQL 121 instruction, which jumps to printing the error message and returning from the function, to BRB 145, which is the jump to the rest of the function, which performs the actual binding.

Locating the code

To make the actual modification using the PATCH utility, I now needed to know where in the executable file these instructions can be found - the addresses in the DISASSEMBLE output are only relative to the start of the function, and the LISP.EXE executable file does not include any symbols. I thus picked out a few instructions that seemed characteristic and assembled them to machine code using the VMS macroassembler. Then, I searched for this instruction sequence in LISP.EXE using a trivial perl program, which gave me the offset of the function that I needed to update.
Knowing the offsets of the locations in the binary file that I needed to change, I could now go about and use the PATCH utility in interactive mode to devise the actual patch. The PATCH manual suggests that the VMS standard debugger would be used for patch development, but as I did not have the symbol table for LISP.EXE, using PATCH itself for development was more appropriate as it can work in /ABSOLUTE mode which uses file offsets for loctions.
First, I needed to find and disassemble the code using the locations I had devised. As I only had the offset of the MOVZBL #89, -(STACK) instruction and VAX instructions have variable lengths, I needed to probe a bunch of addresses before I could come up with this:

PATCH>e/i 00403E68:00403E9A
00403E68:  MOVQ    R10,-(R7)
00403E6B:  MOVL    B^0F0(R8),-(R7)
00403E6F:  MOVZBL  #089,-(R7)
00403E73:  MOVZBL  #099,-(R7)
00403E77:  MOVAB   B^18(R7),R8
00403E7B:  MOVL    B^30(R11),R9
00403E7F:  MOVL    B^04(R9),R11
00403E83:  JMP     @B^04(R11)
00403E86:  CMPL    R6,AP
00403E89:  BEQL    00403E8D
00403E8B:  BRB     00403EB1
00403E8D:  MOVL    R8,-(R7)
00403E90:  MOVL    #00000A28,-(R7)
00403E97:  MOVQ    R10,-(R7)
00403E9A:  MOVL    B^38(R11),-(R7)

This is exactly the same instruction sequence that I disassembled using VAX LISP above. As you can see, it is significantly harder to read the disassembly produced by PATCH as it does not show symbolic register names, and it also does not translate data pointers like in the last instruction - VAX LISP showed the error message where PATCH prints B^38(R11). The addresses in the disassembly, however, are absolute offsets into the LISP.EXE file, and that was what I needed.

Creating the actual patch

Equipped with this information, I could create the actual patch to change VAX LISP so that it no longer disallows binding of Ctrl-S and Ctrl-Q, which I reproduce below:
$ PATCH/ABSOLUTE LISP$SYSTEM:LISP.EXE/OUTPUT=LISP$SYSTEM:
REPLACE /INSTRUCTION
^X00403E5A
'BLEQ ^X00403E5E'
EXIT
'BLEQ ^X00403EB1'
EXIT
REPLACE /INSTRUCTION
^X002F3246
'BEQL ^X002F324A'
EXIT
'BRB ^X002F3265'
EXIT
UPDATE
EXIT
I used the REPLACE/INSTRUCTION command which requires the specification of an address, the current instruction(s) at the location and the new instruction(s) to put at the location. PATCH would only perform the replacement if the instructions currently in the file match what is specified, otherwise it would abort with an error. This is useful to prevent the patch from patching the wrong file or the wrong version of a file.

Better patches

As I did not have the source code or the symbol table for LISP.EXE when I developed this patch, I needed to resort to patching in absolute mode which is kind of brittle. PATCH can also work in symbolic mode if a symbol table is available for the executable file, which allows patches to work even if the executable has been linked differently than the executable used to develop the patch (i.e. you could write a patch for a library function that'd work for executables that were linked statically against the library). Also, PATCH allows patches to insert more instructions than were originally present in the executable. It does this by adding additional disk space to the executable to hold the new, longer code, and then patch the required jump instructions to the patch area into the original location.

Closing thoughts

It is quite nice to be able to fix a bug in or remove a feature from a commercial program without having the source code, just by working with a bit of disassembly and on-board utilities. Back in the day, it was also useful to be able to distribute fixes to customers in the form of tiny patches. These could even be sent as a printed letter and typed in by the customer on a terminal, with reasonable effort and good chances of success.

19 Aug 2018 7:35am GMT

15 Aug 2018

feedPlanet Lisp

Hans Hübner: Evaluating VAX LISP 3.1

The back story

Back in the day, when there still existed a number of different computer architectures and operating systems, I was a huge fan of the VAX/VMS operating system. VMS was designed together with the VAX architecture, and it used specific mechanisms offered by the processor to implement its I/O, security and other services. As it was still common at the end of the 1970ies, portability was not a design objective, and computer companies often had both hardware and software teams working together to implement computing solutions, from hardware to operating systems, development environments and applications.
I became a VMS fan mostly for three reasons: VMS machines were popular in the early packet switched networks that I could access, their default installation often left accounts with default passwords open, and VMS has an excellent online help system which helped me to learn and program VMS without having access to printed manuals.

I also liked the VAX for its orthogonal architecture, which made it somewhat similar to my favorite 8 bit microprocessor at the time, the Zilog Z80. Back then, being able to program a machine in assembly language was still somewhat desirable, and an orthogonal instruction set with many general purpose registers and fancy addressing modes allowing complex programs to be written in assembly language appealed to me, too.
Frankly, though, I never wrote a lot of assembly language code. Instead, C quickly became my language of choice even on VMS, and when g++ 1.42 became available on VMS, I mostly became a full time C++ programmer. This was when object oriented programming just became the fad, with magazines like the C/C++ Users Journal and the Journal of Object Oriented Programming being the prime sources of inspiration. Around that time, I read Grady Booch's excellent book Object-Oriented Analysis and Design with Applications, which explained OO programming using examples in a variety of then-popular OO languages like Smalltalk, C++ and Object Pascal. It also had a chapter on using CLOS as the example language. To me, CLOS was completely out of reach and locked in the ivory tower, requiring utterly expensive machines and software licenses that I'd never hope to have access to, so I read the chapter more as science fiction than as something of practical relevance.
Thus, I stuck with C++ and later Perl on VMS, which was amusing enough, also for being a rather exotic blend.

Around 2001, I was introduced to Lisp by the way of VMS. At the time, my programming gigs were all on Unix or Windows and my affection to VMS became part of my hobby as a collector of vintage computers.

At some point, I brought a MicroVAX with me to a vintage computer convention, and a friend had his MacIvory Symbolics Lisp Machine on display. As the two systems were from the same era, we thought that we should try to bring up some network between them. My VAX ran a fairly recent version of VMS, though, and when we tried to establish a DECNET connection, the Lisp machine would signal an error and put us into a debugger. What got me hooked on Lisp was that my friend could display the source code of the failing DECNET device driver, figure out that the problem was the too-new DECNET version number that the VAX had reported in the connection setup packet, fix the Lisp code in the DECNET driver of the Lisp Machine and then continue the file transfer operation that had signaled the problem. I certainly understood that this would theoretically be possible back then, but I had never seen a system that would have that level of integration of operating system and programming language. I was intrigued.
Fortunately, machines had become much cheaper and faster in the decade since I had first read about CLOS, and the open source movement had made Unix and Common Lisp affordable. I went for CMUCL and eventually became a full time Common Lisp developer for several years.

The holy combination

I had been looking for VAX LISP for some time, as LISP and VMS sounded like a blend of very likeable technologies, so I was very happy when someone found the installation tapes and made them available through the comp.os.vms news group in 2017. I played around with it a little, but unfortunately the manuals that were publicly available at the time were only for VAX LISP V2.1, and V3.1 was supposedly different enough to make me want the updated manual set. It took a bit of research and emailing until I got in touch with the former architect of VAX LISP at digital equipment, and he was kind enough to borrow me the complete manual set for version 3.0, which I scanned and OCRed so that it is now available on bitsavers. Thus, i felt equipped to give VAX LISP a test drive as a vacation project.

About VAX LISP

VAX LISP is an implementation of Common Lisp, but it implements it as described in the first version of "Common Lisp the Language" (CLtL1). This means that it feels like Common Lisp as it was standardized nine years later, but with several important features missing. Among these missing features are:
  • LOOP, the general purpose, well-hated macro for iteration. You get simple LOOP, DOLIST, DOTIMES and of course the dreadful DO and DO* couple.
  • The Common Lisp Object System (CLOS), although there is a version of PCL coming with VAX LISP in the examples directory. There also is a version of the Flavors object system included.
  • The condition system. VAX LISP allows you to bind the *UNIVERSAL-ERROR-HANDLER* special variable to a function that'd be called when ERROR, CERROR or WARN would be called and that could take a non-local jump using THROW.
  • DESTRUCTURING-BIND and lambda lists with &KEY, &REST etc. Lambda lists like we know them today are only available in DEFUN
Furthermore, the package system is not yet where it is today, there are no generalized sequences and there are probably a several other bits and pieces that are missing.

Notable features of VAX LISP are:
  • Integrated, user-extensible editor with both EDT (VMS's standard editor) and Emacs emulation modes, both with a terminal and a DECwindows backend. There is extensive documentation on programming the editor in LISP and I've added several features myself, which was a joy.
  • Interface to the standard DECwindows widget set. This required the implementation of a multithreading system so that DECwindows code, written in C, could be called from LISP and DECwindows handlers could be written in LISP and called from C.
  • A foreign function interface implementing the VMS procedure calling standard, making it possible to call VMS system services and library routines as well as code written in other VMS languages.
Additionally, it comes with a good bunch of example code that is quite helpful when trying to figure out how to use the language, although the quality of the samples vary.

A Project to Try It Out

I wanted to get a feel of how programming in VAX LISP works, so I decided to write a simple http server in it. This would give me the opportunity to try out the system interface as I would have to call into the TCP/IP subsystem. As I wanted to evaluate VAX LISP during a vacation trip, I used SIMH on my MacBook instead of a real VAX, running VMS V5.5-2.

The Development Experience

Initially, I had hoped that I could use the graphical version of VAX LISP for development, but I did not manage to set up a fully functional DECwindows workstation environment and fell back to the terminal version. The downside of this is that I had to alternate between working in the editor and in the REPL, as the editor does not have a convenient way to evaluate expressions and display the results built-in. It would probably not be very hard to add that, but I wanted to spend most of my time working on the web server.

The REPL

The terminal REPL of VAX LISP does not have a lot of convenience features. LISP expressions are entered using the standard VMS line editor, which means that no completion is available and all you get is a way to recall the previously entered line. Annoyingly, if a line is longer than whatever your current terminal width is, there is no way to edit text before the line break. Obviously, no work has been put into making the terminal REPL nice.

The only notable convenience is that one can bind keys (ASCII codes, really) to call LISP functions, and one use case suggested in the manual is to bind, say, Ctrl-E to call the 'ED function. That way, switching to the editor from the REPL is very quick and I use that feature all the time. Beyond that, the REPL experience is rather bare-bones and only slightly better than, say, a bare SBCL or Clozure CL REPL because of VMS's standard line-editing facility, which gives you a one-line recall buffer.

The Editor

VAX LISP comes with an editor that is written in LISP itself and that is extensively documented so that users can extend and adapt it as desired. By default, it tries to emulate EDT, which is the original VMS editor, but EDT is rather quirky and pretty much unusable without a DEC keyboard as it relies on certain function keys that are not present on modern keyboard layouts. The VAX LISP editor also supports an Emacs compatibility mode, because even back in the late 1980ies, most LISP programmers would be used to Emacs and not be willing to use another editor. In Emacs emulation mode, I found it rather easy to write and edit code and I even did some substantial refactorings of my http server code base with it without too much grief. I spent a bit of time of adding a few features that I am used to from GNU Emacs. Writing editor extensions in the same language and environment as the actual project was rather joyful.
The documentation to the editor is extensive, but it leaves a number of questions unanswered. I also find its organization a bit odd, with a whole chapter on editor concepts that comes after all the nitty gritty details of editor customization explanations as separate "Part II" of the manual. I'd expect the description of editor concepts to be coming first, before applying the concepts would be explained. Also, the explanation how editor major and minor modes work is rather fuzzy.
One annoying misfeature of the editor is that it explicitly disallows binding Ctrl-S and Ctrl-Q, and the manual claims that this is due to "system restrictions". While it is true that Ctrl-S and Ctrl-Q were used to implement software flow control on terminal connections that lacked hardware flow control, software flow control is an optional feature of the VMS terminal driver and can easily be switched off if out-of-band flow control is available for a given terminal connection. This would be easy to fix if one hard the VAX LISP source code, but that seems to be lost, unfortunately.
Maybe not so unexpectedly for an editor written in the 1980ies, the VAX LISP editor does not have an "undo" facility. This dampened my enthusiasm when I started writing code, but in practice, it has not hurt me too much. When I made larger changes, I saved my buffers beforehand, and as the VMS file system automatically keeps old versions of files until they're purged, I could go back to the previous state if I wanted to roll back.

VMS and the Internet Protocols

My romanticized memories of VMS date back from a time when there was no Internet, and the Internet Protocols (IP) were just one set of protocols that were used in global networking. DEC had its own protocol suite, DECNET, and was committed to making DECNET OSI compatible, as they believed that OSI would become the dominant wide-area networking protocol suite of the future. DECNET was integrated into VMS quite nicely, and it was easy to implement peer to peer connections from any language, even from command line scripts (which enabled the creation of early networked malware like WANK). Implementations of other networking protocols like RSCS (for BITNET/EARN) and IP (for Arpanet) were available for VMS, but DEC just treated them as secondary networking systems that did not deserve a lot of attention.
To implement my http server in VAX LISP, I needed an implementation of IP, so I installed "DEC TCP/IP Services for VMS" (traditionally referred to as UCX, "VMS/Ultrix Connection") as an add-on product to my base VMS installation. UCX implements a standard set of IP clients and servers like FTP, Telnet, NFS etc. and supports two programming interfaces, one similar to the BSD socket calls meant to be used from programs written in C, and another one based on VMS system services, meant for programs written in other languages. Boldly, I decided that I wanted to use the System Services interface, also in the hope that it would be as nice and convenient as the DECNET programming interface. I was quite wrong.
Apparently, the System Services interface to UCX is a layer on top of the socket interface, so you get the "best" of both worlds: BSD sockets with its quirky sequence of required calls to socket(), listen() and accept(), asking you to specify the length of the "listen queue" and to set the "reuse address" option in your server code because, well, because that is how it wants its chicken to be waved to work well. And then the beautiful VMS $QIO interface with its opaque "function code" and the parameters named P1 to P6 which would be used differently based on the function code supplied.
DEC, in its lack of enthusiasm for supporting IP on VMS, really made sure that the combination of $QIO and sockets would be as ugly as possible.

So, the required sequence to listen to incoming TCP connections and then accept them requires the program to:
  • Assign a channel to the UCX network device
  • Set the channel to be a TCP/IP socket
  • Enable the REUSEADDR option, which is already inconvenient in C with the setsockopt interface, but with $QIO you have to create an additional descriptor to point to the socket option
  • Set the local address of the socket, again using an additional descriptor to point to the local address
  • Set the socket to listen, using another $QIO invocation, now passing the maximum queue length
These steps directly correspond to what you'd have to do when using the BSD socket interface, only that with the System Services interface, you need to call $QIO all the time. What is actually done underneath is then determined by which of the P1 to P6 parameters you set and how, so if you call $QIO with the IO$_SETMODE function code and specify a non-zero P5 parameter, you are calling setsockopt() and if you specify a non-zero P3 parameter, you're calling listen() and so on.
Of course, there are few things that can't be syntactically improved with a bunch of LISP macros and in my http server, the whole sequence does not look so bad, but seriously: This is one of the worst APIs that I have seen in my life and the experience put quite a damper on my romanticized view on VMS and DEC in general.

Serving Files

A http server commonly serves content from files, so I wanted mine to do so as well so that it could deliver a HTML page and some additional resources to the client. On VMS, files are not the simple byte streams that we think about when talking about files nowadays. Rather, the Record Managment System (RMS) maintains the file structure for applications and supports various file organizations like line-sequential and indexed with fixed and varying record lengths etc. It is still possible to read the raw data stored in a file, but that will include the bookkeeping information of RMS. This means that the http server also needs to know something about the structure of the file being served and possibly perform some conversion instead of just forwarding the file data to the client directly.

Binary Files

Serving binary files like images requires the http server to just read the files in a block-wise fashion, but as VAX LISP does not support block-wise reading, this needs to be done with direct calls to RMS. This gave me an opportunity to learn working with RMS, as its API is quite different from, say, the POSIX file API with its simple open()/read()/write()/close() interface.
As RMS supports different file organizations, there are many parameters that an application program needs to specify when it wants to operate on a file. Instead of putting all these different parameters into many functions, RMS uses in-memory structures (blocks) that describe the operations and parameters. These blocks could be defined using the facilities of the application programming language (i.e. struct definitions and numeric constant macros in C), or they could be described using the File Definition Language (FDL). FDL is a domain specific language that describes file and record structures. Applications could invoke the FDL interpreter to turn textual file structure descriptions into binary RMS blocks that it could then use for accessing files.
As a result, the RMS API entry points only require specifying pointers to the blocks that describe the operation, which makes the call sites look rather clean. As, the entry points themselves clearly describe the operation, this makes the LISP code to serve a binary file using RMS calls rather clean-looking.

Text Files

Serving text files like HTML or CSS files is rather more challenging in VAX LISP, considering that the on-disk data of RMS text files cannot simply be copied to the HTTP client. This is because, depending on the file's RMS record format, text files are stored with the length of each line stored in the file in binary form before the actual characters in the line. For that reason, I chose to use the text file I/O mechanism of VAX LISP to read and provide for some explicit buffering to avoid writing each line to the client in a separate $QIO call. I am not sure whether that strategy really provides performance benefits or whether UCX's own buffering would be as good. The resulting code does not really look terribly complex, though.

Roundup

In the end, I've now implemented a basic http server in VAX LISP, called rasselbock. The development experience was quite good, and I found it to be fun to write some code in a Lisp that felt like the Common Lisp I've been using professionally for several years, but that lacks several of the features that I took for granted. I think that in the end, VAX LISP provides enough tooling for serious programming work. It was also an interesting experience to write some code in a language for which the Internet offers no support at all. All I had was the manuals, some sample code and DESCRIBE, and that was sufficient to create something which (kind of) works.

My vacation comes to an end so I'm going to stop at this point for now. In the future, I'm going to put rasselbock onto a real VAX, and I also want to spend some time working with the DECwindows version of VAX LISP as that will probably be a much nicer development experience. Furthermore, I would like to try converting rasselbock to run asynchronously, as that one of the cool things in VMS is that all its system services can be used asynchronously.

I need to thank Walter van Roggen who was kind enough to borrow me the VAX LISP V3.0 manual set for scanning, and Michael Kukat who parted with his remaining VAX hardware so that I have a real machine to run VAX LISP and rasselbock on. I'd also like to thank Richard Wells who pointed me at the vectorized version of the digital logo which led me to become a producer of t-shirts.


If you made it this far, you might also be interested in my follow-on post, in which I describe how I patched the editor so that I could bind Ctrl-S and Ctrl-Q.


15 Aug 2018 12:02pm GMT

13 Aug 2018

feedPlanet Lisp

Christophe Rhodes: a trace of riscv success

(Don't get too excited by the "success" in the title of this post.)

A brief SBCL RISC-V update this time, as there have been no train journeys since the last blog post. Most of what has been achieved is trivial definitions and rearrangements. We've defined some more of the MOVE Virtual Operations that the compiler needs to be able to move quantities between different storage classes (from immediate to descriptor-reg, or between tagged fixnums in descriptor-reg to untagged fixnums in signed-reg, for example).

We've defined a debugging printer function, which wouldn't be needed at this stage except that we're asking the compiler to print out substantial parts of its internal data structures. We've reorganized, and not in a desperately good way, the definitions of the registers and their storage bases and classes; this area of code is "smelly", in that various arguments aren't evaluate when maybe they should be, which means that some other structures need to be defined at compile-time so that variables can be defined at compile-time so that values (in the next form) can be evaluated at read-time; it's all a bit horrible, and as Paul said, not friendly to interactive development. And then a few more fairly trivial definitions later, we are at the point where we have a first trace file from compiling our very simple scratch.lisp file. Hooray! Here's the assembly code of our foo function:

L10:

VOP XEP-ALLOCATE-FRAME {#<SB!ASSEM:LABEL 1>} 
L1:

VOP EMIT-LABEL {#<SB!ASSEM:LABEL 2>} 
L2:

VOP EMIT-LABEL {#<SB!ASSEM:LABEL 3>} 
L3:

VOP NOTE-ENVIRONMENT-START {#<SB!ASSEM:LABEL 4>} 
L4:

L11:
L5:

VOP TYPE-CHECK-ERROR/C #:G0!4[A0] :DEBUG-ENVIRONMENT
    {SB!KERNEL:OBJECT-NOT-SIMPLE-ARRAY-FIXNUM-ERROR X}

L12:
    byte    50
    byte    40
    .align  2

L6:

VOP EMIT-LABEL {#<SB!ASSEM:LABEL 7>} 
L7:

VOP EMIT-LABEL {#<SB!ASSEM:LABEL 8>} 
L8:

VOP NOTE-ENVIRONMENT-START {#<SB!ASSEM:LABEL 9>} 
L9:

L13:
L14:
L15:

I hope that everyone can agree that this is a flawless gem of a function.

The next step is probably to start actually defining and using RISC-V instructions, so... stay tuned!

13 Aug 2018 4:57pm GMT

07 Aug 2018

feedPlanet Lisp

Christophe Rhodes: first riscy steps

In our first post, I summarized the work of a few evenings of heat and a few hours on a train, being basically the boilerplate (parenthesis-infested boilerplate, but boilerplate nonetheless) necessary to get an SBCL cross-compiler built. At that point, it was possible to start running make-host-2.sh, attempting to use the cross-compiler to build the Lisp sources to go into the initial Lisp image for the new, target SBCL. Of course, given that all I had done was create boilerplate, running the cross-compiler was unlikely to end well: and in fact it barely started well, giving an immediate error of functions not being defined.

Well, functions not being defined is a fairly normal state of affairs (fans of static type systems look away now!), and easily fixed: we simply define them until they're not undefined any more, ideally with sensible rather than nonsensical contents. That additional constraint, though, gives us our first opportunity to indulge in some actual thought about our target platform.

The routines we have to define include things like functions to return Temporary Names (registers or stack locations) for such things as the lisp return address, the old frame pointer, and the number of arguments to a function: these are things that will be a part of the lisp calling convention, which may or may not bear much relation to the "native" C calling convention. On most SBCL platforms, it doesn't have much in common, with Lisp execution effectively being one large complicated subroutine when viewed from the prism of the C world; the Lisp execution uses a separate stack, which allows us to be sure about what on the stack is a Lisp object and what might not be (making garbage collectors precise on those platforms).

In the nascent RISC-V port, in common with other 32-register ports, these values of interest will be stored in registers, so we need to think about mapping these concepts to the platform registers, documentation of which can be found at the RISC-V site. In particular, let's have a look at logical page 109 (physical page 121) of the user-level RISC-V ISA specification v2.2:

Register ABI Name Description Saver
x0 zero Hard-wired zero -
x1 ra Return address Caller
x2 sp Stack pointer Callee
x3 gp Global pointer -
x4 tp Thread pointer -
x5 t0 Temporary/Alternate link register Caller
x6-7 t1-2 Temporaries Caller
x8 s0/fp Saved register/Frame pointer Callee
x9 s1 Saved register Callee
x10-11 a0-1 Function arguments/return values Caller
x12-17 a2-7 Function arguments Caller
x18-27 s2-11 Saved registers Callee
x28-31 t3-6 Temporaries Caller

The table (and the rest of the document) tells us that x0 is a wired zero: no matter what is written to it, reading from it will always return 0. That's a useful thing to know; we can now define a storage class for zero specifically, and define the zero register at offset 0.

The platform ABI uses x1 for a link register (storing the return address for a subroutine). We may or may not want to use this for our own return address; I'm not yet sure if we will be able to. For now, though, we'll keep it reserved for the platform return address, defining it as register lr in SBCL nomenclature, and use x5 for our own lisp return address register. Why x5? The ISA definition for the jalr instruction (Jump And Link Register, logical page 16) informs us that return address prediction hardware should manipulate the prediction stack when either x1 or x5 is used as the link register with jalr, and not when any other register is used; that's what "Alternate link register" means in the above table. We'll see if this choice for our lra register, for Spectre or for worse, gives us any kind of speed boost - or even if it is tenable at all.

We can define the Number Stack Pointer and Number Frame Pointer registers, even though we don't need them yet: in SBCL parlance, the "number" stack is the C stack, and our register table says that those should be x2 and x8 respectively. Next, for our own purposes we will need: Lisp stack, frame and old-frame pointer registers; some function argument registers; and some non-descriptor temporaries. We'll put those semi-arbitrarily in the temporaries and function arguments region of the registers; the only bit of forethought here is to alternate our Lisp arguments and non-descriptor temporaries with one eye on the "C" RISC-V extension for compressed instructions: if an instruction uses registers x8-x15 and the "C" extension is implemented on a particular RISC-V board, the instruction might be encodable in two bytes instead of four, hopefully reducing instruction loading and decoding time and instruction cache pressure. (This might also be overthinking things at this stage). In the spirit of not overthinking, let's just put nargs on x31 for now.

With all these decisions implemented, we hit our first "real" error! Remembering that we are attempting to compile a very simple file, whose only actual Lisp code involves returning an element from a specialized array, it's great to hit this error because it seems to signify that we are almost ready. The cross-compiler is built knowing that some functions (usually as a result of code transformations) should never be compiled as calls, but should instead be /translated/ using one of our Virtual OPerations. data-vector-ref, which the aref in our scratch.lisp file translates to because of the type declarations, is one such function, so we need to define it: and also define it in such a way that it will be used no matter what the current compiler policy, hence the :policy :fast-safe addition to the reffer macro. (That, and many other such :policy declarations, are dotted around everywhere in the other backends; I may come to regret having taken them out in the initial boilerplate exercise.)

And then, finally, because there's always an excuse for a good cleanup: those float array VOPs, admittedly without :generator bodies, look too similar: let's have a define-float-vector-frobs macro to tidy things up. (They may not remain that tidy when we come to actually implement them). At this point, we have successfully compiled one Virtual OPeration! I know this, because the next error from running the build with all this is about call-named, not data-vector-set. Onward!

07 Aug 2018 5:36pm GMT

Didier Verna: Quickref open-sourced

8 months after the original announcement, we finally open-sourced Quickref. The complete source code is available here.

I gave a lightning talk at ELS 2018, in which I claimed I would release the code in "something like two weeks". That was 4 months ago :-). I apologize for the delay, especially to Zach who expressed interest in how we did the Docker thing at the time. I wanted to clean up the code before the first public release (I'm a maniac like that), which I did, but it took some time.

Compared to what I announced at ELS, Quickref also has a couple of new features, most importantly the ability to generate documentation for only what's already installed, rather than for the whole Quicklisp world. This can be very convenient if you just want some local documentation for the things you use daily. Finally, there is also a very rudimentary support for multithreading, which currently doesn't bring much. But the code has been prepared for going further in that direction; this will be the topic of another internship which will start next September.

Browse no less than 1588 reference manuals right now at https://quickref.common-lisp.net/, and recreate your own local version with this Docker 2-liner:

docker run --name quickref quickref/quickref
docker cp quickref:/home/quickref/quickref .

07 Aug 2018 12:00am GMT