Category Archives: _Lab Notes 🧪

Rough notes, typically technical, usually bullet points about some topic.

osdev journal: bootloaders and booting (grub, multiboot, limine, BIOS, EFI)

Leave a reply
: _Lab Notes 🧪, Operating Systems

Here’s my rough lab notes from what I learned during weeks 69-73 of streaming where I did my “boot tour” and ported JOS to a variety of boot methods.

JOS originally used a custom i386 BIOS bootloader. This is a classic approach for osdev: up to 512 bytes of hand written 16 bit real mode assembly packed into the first sector of a disk.

I wanted to move away from this though — I had the sense that using a real third party bootloader was the more professional way to go about this.

Grub

First I ported to Grub, which is a widely used, standard bootloader on Linux systems.

This requires integrating the OS with the Multiboot standard. Grub is actually designed to simply be a reference implementation of a generic boot protocol, called Multiboot. The goal is to allow different implementations of bootloaders and operating systems to all transparently interoperate with each other, as opposed to the specific bootloaders made for each OS which was common at the time of its development.

(Turns out Multiboot never really took off. Linux and BSDs already had bootloaders and boot protocols and never ported to use Multiboot. Grub supports them via implementing their specific boot protocols in addition to Multiboot. I’m not sure any mainstream OS is natively using Multiboot. Probably mostly hobby os projects.)

This integration looks like:

  • Adding a Multiboot header
  • Optionally making use of an info struct pointer in EBX

The Multiboot header is interesting. Multiboot was designed to be binary format agnostic. While there is native ELF support, OS’s need to advertise that they are Multiboot compatible by including magic bytes in the first few KB of their binary, along with some other metadata (e.g. about architecture). The multiboot conforming boot loader will scan for this header. Exotic binary formats can add basic metadata about what load address they need and have a basic form of loading be done (probably just memcpying the entire OS binary into place. The OS might need to load itself further from there if it has non-contiguous segments.)

Then, for Multiboot v1, the OS receives a pointer to an info struct in EBX. This contains useful information provided from the bootloader (cli args, memory maps, etc), which is the second major reason to use a third party bootloader.

There are two versions of the Multiboot standard. V1 is largely considered obsolete and deprecated because this method of passing a struct wasn’t extensible in a backward compatible way. An OS coded against a newer version of the struct (which might have grown) would possibly crash if loaded against an older bootloader that only provided a smaller struct (because it might dereference struct offsets that go out of bounds of the given struct).

So the Multiboot V2 standard was developed to fix this. Instead of passing a struct, it uses a TLV format where the OS receives an array of tagged values, and can interpret only those whose tags it’s aware of.

The build process is a bit nicer for Grub also compared with a custom bootloader. Instead of creating a “disk image” by concatenating a 512 byte assembly block, and my kernel, with Grub you can use an actual filesystem.

You simply create a directory with a specific directory structure, then you can use grub-mkrescue to convert that into an .iso file with some type of CD-ROM based filesystem format. (Internally it uses xorriso). You can then pass the .iso to QEMU with -cdrom instead of -drive as I was doing previously.

Limine

Limine is a newer, modern bootloader aimed at hobby OS developers. I tried it out because it’s very popular, which I now think is well deserved. In addition to implementing essentially every boot protocol, it includes its own native boot protocol with some advanced features like automatic SMP setup, which is otherwise fairly involved.

It uses a similar build process to grub-mkrescue with creating a special directory structure and running xorriso to produce an iso.

I integrated against Limine, but kept my OS as Multiboot2 since Limine’s native protocol only supported 64 bit.

BIOS vs UEFI

Everything I’ve mentioned so far has been in the context of legacy BIOS booting.

Even though I ported away from a custom bootloader to these fancy third party ones, I’m still using them in BIOS mode. I don’t know exactly what’s in these .iso files, but that means they must populate the first 512 bytes of the media with their own version of the 16 bit real mode assembly, and bootstrap from there.

But BIOS is basically obsolete — the modern way to boot a PC is UEFI.

The nice thing about integrating against a mature third party bootloader, is it abstracts the low level boot interface for you. So all you need to do is target Grub or Limine, and then you can (nearly) seamlessly boot from either BIOS or UEFI.

It was fairly easy to get this working with Limine, because Limine provides prebuilt UEFI binaries (BOOTIA32.EFI) and has good documentation.

The one tricky thing is that QEMU doesn’t come with UEFI firmware by default, unlike with BIOS (where SeaBIOS is included). So you need to get a copy of OVMF to pass to QEMU to do UEFI boot. (Conveniently there are pre-built OVMF binaries available by the Limine author).

I failed at getting UEFI booting with Grub to work on my macOS based dev setup, because I couldn’t easily find a prebuilt Grub BOOTIA32.EFI. There is a package on apt, but I didn’t have a Linux machine quickly available to investigate if I could extract the file out of that.

Even though UEFI is the more modern standard, I’m proceeding with just using BIOS simply to avoid dealing with the whole OVMF thing.

Comparison table

ProsCons
Custom– No external dependency– More finicky custom code to support, more surface area for bugs
– Doable to get basics working but nontrivial effort required to reimplement more advanced features in Grub/Limine (a boot protocol, cli args, memory map, etc)
– No UEFI support
Grub– Well tested, industrial strength
– Available prebuilt from Homebrew
– Simple build process, just use single i386-grub-mkrescue to create iso		– Difficult to get working in UEFI mode on Mac (difficult to find a prebuilt BOOTIA32.EFI)
Limine– Good documentation
– Easy to get working for both BIOS and UEFI
– Supports Multiboot/Multiboot2. Near drop in replacement for grub
– Can opt into custom boot protocol with advanced features (SMP bringup)		– Not used industrially, mostly for hobby osdev
– Not packaged in Homebrew, requires building driver tool from source (but this is trivial)

osdev journal: Gotchas with cc-runtime/libgcc

Leave a reply
: _Lab Notes 🧪, C, Operating Systems

libclang_rt/libgcc are compiler runtime support library implementations, which the compiler occasionally emits calls into instead of directly inlining the codegen. Usually this is for software implementations of math operations (division/mod). Generally you’ll need a runtime support library for all but the most trivial projects.

cc-runtime is a utility library for hobby OS developers. It is a standalone version of libclang_rt, which can be included vendored into an OS build.

The main advantage for me is that it lets me use a prebuilt clang from Homebrew. The problem with prebuilt clang from Homebrew, is it doesn’t come with a libclang_rt compiled for i386 (which makes sense, why would it — I’m on an ARM64 Mac).

(This is unlike the prebuilt i386-elf-gcc in Homebrew, which does come with a prebuilt libgcc for i386).

Since it doesn’t come with libclang_rt for i386, my options are:

Option
Keep using libgcc from i386-elf-gcc in HomebrewUndesirable — the goal is to only depend on one toolchain, and here I’d depend on both clang and gcc.
Build clang and libclang_rt from sourceUndesirable — it’s convenient to avoid building the toolchain from source if possible.
Vendor in a libgcc.a binary from https://codeberg.org/osdev/libgcc-binariesUndesirable — vendoring binaries should be a last resort
Use cc-runtimeBest — No vendored binaries, no gcc dependency, no building toolchain from source

However, cc-runtime does have a gotcha. If you’re not careful, you’ll balloon your binary size.

This is because the packed branch of cc-runtime (which is the default and easiest to integrate) packs all the libclang_rt source files into a single C file, which produces a single .o file. So the final .a library has a single object file in it.

This is in contrast to libgcc.a (or a typical compilation of libclang_rt) where the .a library probably contains multiple .o files — one for each .c file.

By default, linkers will optimize and only use any .o files in the .a library that are needed. But since cc-runtime is a single .o file, the whole thing will get included! This means, the binary will potentially include many libclang_rt functions that are unused.

In my case, the size of one of my binaries went from 36k (libgcc) to 56k (cc-runtime, naive).

To work around this, you either need to use the trunk branch of cc-runtime (which doesn’t pack them all into one .c file). This is ~30 .c files and slightly more annoying to integrate into the build system.

Or, you can use some compiler/linker flags to make the linker optimization more granular and work at the function level, instead of the object file level.

Those are:

Compiler flag:

-ffunction-sections -fdata-sections

Linker flag

--gc-sections

With this, my binary size reduced to 47k. So there is still a nontrivial size increase, but the situation is slightly improved.

Ultimately, my preferred solution is the first: to use the trunk branch. The build integration is really not that bad, and the advantage is you don’t need to remember to use the special linker flag, which you’d otherwise need to ensure is in any link command for any binary that links against cc-runtime.

That said, those compiler/linker flags are probably a good idea to use anyway, so the best solution might be to do both.

VIM tips + lab notes

Leave a reply
: _Lab Notes 🧪, _Living Doc 🌱

Underrated commands:

z commands

  • z<cr> – redraw with current line at the top
  • zz – redraw with current line at middle

L and H — great for quickly going to the top or bottom of editor and browsing slightly offscreen

Enable VSCode “Editor smooth scrolling”, or find a vim smooth scrolling plugin to make ctrl+d and ctrl+u actually functionality

[[ and ]] — for quickly browsing opening brackets

x86 kernel development lab notes

Leave a reply
: _Lab Notes 🧪, Computers, Operating Systems

Here’s what I know about x86 kernel development. The usual caveat applies for my lab notes: this is not considered a high quality document and there may be inaccuracies.

Main Processor Modes

  • Real Mode (16 bit)
    • CPU boots into this mode for backward compatibility
    • The IDT is instead the IVT here (Interrupt Vector Table)
    • Legacy BIOS booting begins here — the BIOS loads the first sector of disk into memory at a fixed address and begins executing it in Real Mode.
  • Protected Mode (32 bit)
    • Segmentation is mandatory — a minimal GDT is necessary.
    • Paging is not mandatory
  • Long Mode (64 bit)
    • Paging is mandatory

Segmentation

  • Originally solved the problem of CPUs having more physical memory than could be addressed with 16 bit registers. (Note, this is the opposite situation of what we have today where virtual address spaces are vastly greater than physical ones)
  • Introduces the concept of “segments”, which are variable length “windows” into a larger address space.

Data structures

GDT (Global Descriptor Table)

  • Contains “descriptors” to describe the memory segments (“windows”) available. Segment register contain effectively an index into this table.
  • There are “normal” descriptors which describe memory segments and “system” descriptors which point to more exotic things, like Task State Segments (TSS) or Local Descriptor Tables (LDT)
  • These days OSs use the GDT as little as possible, only as much as strictly necessary. On 32 bit, this looks like 4 entries that start at base 0x0, and cover the entire 32 bit space. 2 for kernel, 2 for user — 1 for code, 1 for data for each. (?)
  • On 64 bit GDT is totally unused (I believe?), as are nearly all segment registers(?), except FS and GS. (Why are they special? There is even a special MSR for GS?)

LDT (Local Descriptor Table)

  • My understanding is LDTs are really no longer used by nearly any OS. Some parts of segmentation are still required by OSs, like the GDT, but LDT is not required and almost completely unused in modern OSs.
  • These would contain segments only accessible to a single task, unlike the regions in the GDT (?)

IDT (Interrupt Descriptor Table)

  • Interrupts: Generally externally triggered, i.e. from hardware devices
  • Exceptions: Internally generated, I.e. division by zero exception, or software breakpoint
  • When the processor receives an interrupt or exception, it handles that by executing code — interrupt handler routines.
  • These routines are registered via the IDT — an array of descriptors that describes how to handle a particular interrupt.
  • Interrupts/exceptions have numbers which directly map to entries in the IDT.
  • IDT descriptors are a polymorphic structure — there are several kinds of entities: interrupt, trap, and task gates (maybe others – call gates?).
  • Interrupt/trap gates are nearly identical and differ only in their handling of the interrupt flag. They contain a pointer to code to execute. This is expressed via a segment/offset.
  • Task gates make use of HW task switching and offer a more “turnkey” solution for running code in a separate context when an interrupt happens — but generally aren’t used for other reasons (?). Context switch is automatic?
  • Task gates in the IDT point to a TSS descriptor in the GDT, which points to a TSS (?)
  • Some interrupt/exceptions have an associated error code, some don’t.
  • Interrupt gates describe a minimal privilege level required to trigger then with an int instruction — this prevents userspace from triggering arbitrary interrupts with int. If userspace tries to trigger an int without permission, that is converted in to a General Protection fault (#GP)

Hardware task switching

  • Although long considered obsolete in favor of software task/context switching, x86 provides significant facilities for modeling OS “tasks” at the hardware level, and including functionality for automatic context switching between them.
  • Hardware task switching may require copying much more machine state than is necessary. Software context switches can be optimized to copy less and be faster, which is one reason why they’re preferred.
  • Hardware task switching puts a fixed limit on the number of tasks in the system (?)

TSS (Task State Segment)

  • This is a large structure modeling a “task” (thread of execution)
  • Contains space for registers & execution context
  • Even if HW task switching is not used, one TSS is still needed as the single HW Task running on the system, which internally implements all software context switching
  • TSS is minimally used for stack switches when handling interrupts across privilege levels — when switching from userspace to kernel during interrupt, kernel stack is taken from TSS
  • Linux task_struct is probably named with “task” due to being original created for i386
  • The Task Register (TR) contains a descriptor pointing to the current active HW task (?)

The JOS boot process

JOS is the OS used in MIT 6.828 (2018).

Bootloader

  • JOS includes a small BIOS bootloader in addition to the kernel
  • The bootloader begins with typical 16 bit Real Mode assembly to do the typical steps to initialize the CPU (Set A20 line, etc)
  • Transition to protected mode
  • Set the stack immediately at the start of the code, and transition to C
  • The kernel is loaded from disk using Port IO
  • Loaded into physical memory around the 1MB mark, which is generally considered a “safe” area to load into. (Below the 1MB mark has various regions where devices, BIOS data, or other “things” reside and it’s best to not clobber them.)
  • Call into the kernel entrypoint

Early kernel boot

  • Receive control from the bootloader in protected mode
  • Transition to paging
  • The kernel is linked to run in high memory, starting at 0xf000000 (KERNBASE)
  • The transition from segmentation to paging virtual memory happens in a few steps. There’s first an initial basic transition using set of minimal page tables.
  • After that transition is made, a basic memory allocator is set up, which is then used to allocate memory for the production page tables which implement the production virtual memory layout used for the rest of runtime.
  • The minimal page tables contain two mappings:
    • 1 – Identity map the first 4MB to itself
    • 2 – Map the 4MB region starting at KERNBASE also to the first 4MB
  • One page directory entry maps a 4MB region, so only two page directory entries are needed
  • These page tables are constructed statically at compile time
  • The first identity mapping is critical because without it the kernel would crash immediate after loading CR3, because the next instruction would be unmapped. The identity mapping allows the low mem addresses the kernel resides in to remain valid until the kernel can jump to high mem
  • The assembly there looks a bit strange because the jump appears redundant. But all the asm labels are linked using highmem addresses, so jumping to them transitions from executing in low mem, to executing in high mem, where the kernel will remain executing for the rest of its lifetime.
  • Set the stack pointer to a global data/BSS section of internal storage within the kernel and enter C code

Memory allocators

  • The goal is transition to a production virtual memory setup
  • This requires allocating memory for page tables
  • To build the dynamic page/frame allocator, we start with a basic bump allocator
  • It starts allocating simply from the end of the kernel in memory. We have access to a symbol for the end of the kernel via a linker script.
  • Kernel queries the physical memory size of the system and dynamically allocates data structures for the dynamic page/frame allocator. This is an array of structure that correspond to each available frame of physical memory. These structures have an embedded linked list pointer (intrusive linked list) and a refcount. They are linked together into a linked list, to implement a stack data structure where frames can be popped (when allocating) and pushed (when freeing).
  • Using this frame allocator, pages for the production page tables are allocated.

gardenOS Update 1

Leave a reply
: _Lab Notes 🧪, Streaming

(This is a random collection of thoughts around my new operating systems project, “gardenOS”.)

What’s up with the “gardening” terminology?

This is a phrase that I feel perfectly describes the ethos of this project. In the same way people have gardens as calm places to express themselves, learn things, and have fun doing work, I want to create an analogous place for exploring my interest in operating systems.

Some key tenants of the approach:

  • No stress
  • Have fun
  • Pursue whatever interests you

I don’t have particularly strong OSdev skills at the moment, so I’m especially focusing on doing small, easy tasks, such as cleaning up the build system. I do this in the same way you might spend an afternoon picking weeds in your little garden. It’s easy, well understood, not too complicated, no large decisions to be made — and it concretely improves the project. It’s a concrete win you can lock in, in a fixed amount of time, with fairly little work.

Disclaimer: I’m almost apprehensive to even give this project a name

I’m worried that even naming this project (“gardenOS”) will put too much pressure on me. I am deeply aware that OS’s take monumental amounts of time and energy to even get to basic states. And at my current rate (~2 hours a week), it’s unlikely we will get to even basic levels soon.

I wasn’t expecting things to get this philosophical this quickly. My focus above all, is to have fun, learn things, and make some small progress each week in the stream. Each week where I do a stream or do some work, any any of that happens, is a win.

I explicitly hold very few expectations around a future “goal” of the project or where I want it to end up. I just want to have fun and learn things about operating systems.

The loose vision I have is to create a minimal OS for play and experimentation. It should be a high quality codebase, and I should work on it as if I wanted to present my best self as an aspiring pro systems programmer.

The ethos of the project

Even though the project is in a maximally nascent stage, I already feel a certain ethos evolving. In the project, we emphasize:

  • Relaxed, casual, kind attitude
  • Learning mindset
  • Ambition to use programming best practices, and aspiring to become pro systems programmers
  • Portray an accurate “slice of life” of systems programming. Meaning: Show the day to day, which is not always thrilling tasks (like adding a syscall), but simply just working on the build system or refactoring some code.

My experience after doing four streams

I’ve done four streams so far (2 live, 2 recorded). My big worries are that I’ll run out of stuff to do and have to scramble to find something to do, live.

This has never happened — I’m always surprised at the adventures “we” find ourselves going on

The use of “we”

The project is just me at the moment, but there’s something about using “we” to describe it that makes me feel good.

It’s not just to make myself seem more impressive, or feel less alone. When I use it, I think of the handful of enthusiastic people that have joined me in the live streams, or left comments with questions or encouragement.

Even in these earliest of days, there is some tiny, microscopic community feel forming. So when I say “we”, I speak for this community.

WIP: What’s the deal with memory ordering? (seq_cst, acquire, release, etc)

Leave a reply
: _Lab Notes 🧪, C++, Concurrency

(This is a high level summary of my current knowledge, primarily to help me crystallize the knowledge. It comes entirely from from Jeff Preshing’s blog (see end of post) and youtube talk. This is not intended to be a comprehensive overview; for that, please see the aforementioned materials. I am very much a non-expert on this topic; please treat everything with skepticism.)

When programming with atomics, how are you suppose to know which of the ~four memory orderings to use? For example, the main ones (C++ terminology) are:

  • memory_order_seq_cst
  • memory_order_acquire
  • memory_order_release
  • memory_order_relaxed
  • (and a few other niche ones: acq_rel, consume)

First, as Jeff Preshing states, there is a distinction between “sequentially consistent” atomics and “low level” atomics. He describes it as two libraries for atomics masquerading as a single one within the C++ standard library.

The first, “sequentially consistent”, can be considered a higher level way of using atomics. You can safely use seq_cst everywhere. You get simpler semantics and higher likelihood of correctness, just at the expensive of performance. As an optimization, you can then port the code to the second form of “low level atomics”. This is where you must choose the explicit memory orderings.

But why do sequentially consistent atomics come with a performance hit?

The performance hit comes from cross core communication. The sequentially consistent memory model offers a very strong guarantee to the programmer; in addition to the ordering of atomic operations being consistent across cores (which is always the case), the ordering of non-atomic operations is also guaranteed to be consistent (i.e. no reordering) relative to the atomic ones.

This is relevant because programming with atomics often involves “guard” (atomic) variables who regulate access to “normal” (non-atomic) data that is transferred between threads. This guarantee requires extra effort from the memory subsystem of the CPU in the form of cross core communication as the cores need to effectively synchronize their caches.

When one moves to “low level” atomics, the strict constraints required of the memory subsystem are relaxed. Not all orderings of non-atomic accesses relative to atomic accesses must be maintained. The consequence is less cross-core coordination is required. This can be exploited for higher performance in specific scenarios where the strict ordering constraint is not required in both (or any) directions (i.e. non-atomic memory accesses are allowed to move before or after the atomic access).

Exercise: Would one expect to see a performance improvement from porting code from sequentially consistent atomics to low level atomics, if the code is run on a single core system?

The whole point of low level atomics is to optimize performance by relaxing constraints and reducing cross core communication, so no. There is no cross core communication in a single core system, so there is nothing substantial to optimize.

(I am not 100% sure of this answer. This is the current state of my knowledge and I would appreciate being corrected or affirmed either way!)

So how does one choose between all those memory orderings?

With my non-expert understanding, I believe there are some simple rules that make the decision much easier than it might seem.

First off: Decide whether you’re using sequentially consistent or low level atomics. If the former, you use seq_cst everywhere (this is even the default with C++ if you don’t specify anything).

If you want to optimize to use low level atomics, then for most cases, you then only have three choices: acquire, release, and relaxed. (seq_cst is no longer an option; acq_rel is more niche; consume is actively discouraged). Then:

  • If you’re deciding for a load operation, you then only choose between acquire and relaxed. Loads are never release.
  • And vice verse, If you’re deciding for a store operation, you then only choose between release and relaxed. Stores are never acquire.

This narrows it down to two choices. To determine whether it’s acquire/release or relaxed, determine whether the load/store has a synchronizes-with relation to a corresponding store/load. If there is one, you want acquire/release. Otherwise, choose relaxed.

Read these blog posts for a fuller answer to this:

Links:

https://www.youtube.com/watch?v=X1T3IQ4N-3g

Mutexes, atomics, lockfree programming

Leave a reply
: _Lab Notes 🧪, C, C++, Computer Architecture, Concurrency

Some rough lab notes on these topics to record the current state of my knowledge. I’m not an expert, so there may be inaccuracies.

Mutexes

  • On Linux, libpthread mutexes are implemented using the underlying futex syscall
  • They are basically a combination of a spinlock (in userspace), backed by the kernel for wait/signal operations only when absolutely necessary (i.e. when there’s contention). In the common case of an uncontended lock acquire, there is no context switch which improves performance
  • The userspace spinlock portion uses atomics as spinlocks usually do, specifically because the compare and set must be atomic
  • Jeff Preshing (see below) writes that each OS/platform has an analogous concept to this kind of “lightweight” mutex — Windows and macOS have them too
  • Before futex(2), other syscalls were used for blocking. One option might have been the semaphore API, but commit 56c910668cff9131a365b98e9a91e636aace337a in glibc is before futex, and it seems like they actually use signals. (pthread_mutex_lock -> __pthread_lock (still has spinlock elements, despite being before futex) -> suspend() -> __pthread_suspend -> __pthread_wait_for_restart_signal -> sigsuspend)
  • A primary advantage of futex over previous implementations is that futexes only require kernel resources when there’s contention
  • Like atomics, mutexes implementations include memory barriers (maybe even implicitly due to atomics) to prevent loads/stores from inappropriately crossing the lock/unlock boundary due to compiler and/or hardware instruction reordering optimizations
Continue reading →

Runtime polymorphism cheat sheet

Leave a reply
: _Lab Notes 🧪, C++, Software Development

While C++ is used here as an example, the concepts apply to any statically typed programming language that supports polymorphism.

For example, while Rust doesn’t have virtual functions and inheritance, it’s traits/dyn/Boxes are conceptually equivalent and. Rust enums are conceptually equivalent to std::variant as a closed set runtime polymorphism feature.

Virtual Functions/Inheritancestd::variant
Runtime PolymorphismYes – dynamic dispatch via vtableYes – dynamic dispatch via internal union tag (discriminant) and compile-time generated function pointer table
SemanticsReference – clients must operate using pointer or referenceValue – clients use value type
Open/Closed?Open – Can add new types without recompiling (even via DLL). Clients do not need to be adjusted.Closed – Must explicitly specify the types in the variant. Generally clients/dispatchers may need to be adjusted.
CodegenClient virtual call + virtual methodsClient function table dispatch based on union tag + copy of callable for each type in the dispatch. If doing generic dispatch (virtual function style), then also need the functions in each struct. Inlining possible.
Class definition boilerplateClass/pure virtual methods boilerplate.Almost none.
Client callsite boilerplateAlmost nonestd::visit() boilerplate can be onerous.
Must handle all cases in dispatch?No support — the best you can do is an error-prone chain of dynamic_cast<>. If you need this, virtual functions are not the best tool.Yes, can support this.

Overall, virtual functions and std::variant are similar, though not completely interchangeable features. Both allow runtime polymorphism, however each has different strengths.

Virtual functions excels when the interface/concept for the objects is highly uniform and the focus is around code/methods; this allows callsites to be generic and avoid manual type checking of objects. Adding a const data member to the public virtual interface is awkward and must go through a virtual call.

std::variant excels when the alternative types are highly heterogenous, containing different data members, and the focus is on data. The dispatch/matching allows one to safely and maintainably handle the different cases, and be forced to update when a new alternative type is added. Accessing data members is much more ergonomic than for virtual functions, but the opposite is true for generic function dispatch across all alternative types, because the std::visit() is not ergonomic.

Building on these low level primitives, one can build:

  • Component pattern (using virtual functions typically) (value semantics technique; moves away from static typing and towards runtime typing)
  • Type erase pattern (also virtual functions internally) (value semantics wrapper over virtual functions)

Fun facts:

  • Rust also has exactly these, but just with different names and syntax. The ergonomics and implementation are different, but the concepts are the same. Rust uses fat pointers instead of normal pointer pointing to a vtable. Rust’s match syntax is more ergonomic for the variant-equivalent. Rust uses fat pointers apparently because it allows “attaching a vtable to an object whose memory layout you cannot control” which is apparently required due to Rust Traits. (source)
  • Go uses type erasure internally, but offers this as a first class language feature.

Case study: Component pattern

The component pattern is a typical API layer alternative to classical virtual functions. With classical runtime polymorphism via virtual functions, the virtual functions and inheritance are directly exposed to the client — the client must use reference semantics and does direct invocation of virtual calls.

With the component pattern, virtual functions are removed from the API layer. Clients use value semantics and then “look up” a component for behavior that would have previously been inherited.

API classes, instead of inheriting, contain a container of Components, who are themselves runtime polymorphic objects of heterogenous types. The components can classically use virtual functions for this, inheriting from some parent class. Then the API class contains a container of pointers to the parent class. API clients look up the component they are interested in via its type, and the API class implements a lookup method that iterates the components and identifies the right one using dynamic_cast or similar.

However, variants offer another way to implement this. Rather than having all components inherit from the superclass, they can be separate classes that are included in a variant. The API class then has a container of this variant type. In the lookup method, instead of using dynamic_cast, it uses std::holds_alternative which is conceptually equal.

This is a somewhat unusual application of runtime polymorphism and neither implementation method stands out as strictly better. Since components do not share a common interface really (they would just inherit so they can be stored heterogenously in a container), virtual functions does not offer a strong benefit. But also since the component objects are never dispatched on (they are always explicitly looked up by type), the variant method also does not offer a strong benefit.

The main difference in this scenario is the core difference between virtual functions and variants: whether the set of “child” types is open or closed. With virtual functions being open, it offers the advantage that new components can be added by simply inheriting from the parent class and no existing code needs to be touched. Potentially new components could even be loaded dynamically and this would work.

With variants, when new components are added, the core definition of the component variant needs to be adjusted to include the new type. No dynamic loading is supported.

So it appears that virtual functions have slight advantage here.

See: https://gameprogrammingpatterns.com/component.html

Q: What about std::any?

std::any is loosely similar to virtual functions or std::variant in that it implements type erasure, allowing a set of heterogenous objects of different types, to be referenced using a single type. Virtual functions and std::variant aren’t typically called “type erasure” as far as I’ve heard, but this is effectively what they do.

However that’s where the similarities end. std::any represents type erasure, but not any kind of object polymorphism. With std::any, there is no notion of a common interface that can be exercised across a variety of types. In fact, there is basically nothing you can do with a std::any but store it and copy it. In order to extract the internally stored object, it must be queried using its type (via std::any_cast()) which tends to defeat the purpose of polymorphism.

std::any is exclusively designed to replace instances where you might have previously used a void * in C code, offering improved type safety and possibly efficiency. 1 The classic use case is implementing a library that allows clients to pass in some context object that will later be passed to callbacks supplied by the client.

For this use case, the library must be able to store and retrieve the user’s context object. It’s it. It literally never will interpret the object or access it in any other way. This is why std::any fits here.

Another use case for std::any might be the component pattern in C++, where objects store a list of components, which are then explicitly queried for by client code. In this case, the framework also never deals directly with the components, but simply stores and exposes the to clients on request.

More: https://devblogs.microsoft.com/cppblog/stdany-how-when-and-why

Task queues, Redis, Python, Celery, RQ

1 Reply
: _Lab Notes 🧪, Web Dev
  • There are many instances where your application has some expensive work to do, that would be not good to execute in the hot path. (e.g. responding to an HTTP request)
  • The typical solution is to enqueue a task in a queue and have a worker process it “offline”
  • In Python, Celery is a popular library for this. It uses backends for the actual queue. Popular backends are RabbitMQ and Redis.
  • RQ is another Python that supports Redis only.
  • RabbitMQ is designed to be a queue — it’s in the name.
  • Redis is a in memory key value store/database. (or “data structure” store). It includes a number of primitives that might be used to implement a queue. It’s basically a in memory hashmap. Keys are strings in a flat namespace. Value are a set of supported fundamental data types. Everything is serialized as it’s interacted with IPC.
    • List — (Implemented in RQ.) You can use opcodes like LPUSH and RPOP.
    • Pub/Sub — Unsure about this. (Possibly implemented in Celery?)
    • Stream — Advanced but apparently is not implemented in either Celery or RQ.
  • Celery has sleek Pythonic syntactic sugar for specifying a “Task” and then calling it from the client (web app). It completely abstracts the queue. It returns a future to the client (AsyncResult) — the interface is conceptually similar to std::async in C++.
  • RQ is less opinionated and any callable can be passed into this .enqueue() function, with arguments to call it with. This has the advantage that the expensive code does not need to have Celery as a dependency (to decorate it). However that is not a real downside, as you can always keep things separate by making Celery wrappers around otherwise dependency free Python code. But it is an addition level of layers.
  • Heroku offers support for this — you just need to add a new process to your Procfile for the celery/RQ worker process. Both celery/RQ generate a main.
  • Redis has other uses beyond being a queue: it can be a simple cache that you application accesses on the same server before accessing the real database server. It can also be used to implement a distributed lock (sounds fancy but is basically just a single entry in redis that clients can check to see if a “lock” is taken. Of course it’s more complicated than just that). Redis also supports transactions, in a similar way to transactional memory on CPUs. In general there are direct parallels from from local parallel programming to nearly everything in this distributed system world. That said there are unique elements — like the Redis distributed lock includes concepts like a timeout and a nonce in case the client that acquired the lock crashes or disappears forever. That is generally not something you’d see in a mutex implementation. Another difference is that even though accessing Redis is shared mutable state, clients probably don’t need some other out of band mutex because Redis implements atomicity likely. That’s different than local systems because even if the shared, mutable data type you’re writing to/reading from locally is atomic (like a int/word), you should still use a mutex/atomic locally due to instruction reordering (mutexes and atomics insert barriers).

How to enable colored compiler output with CMake + VSCode

Leave a reply
: _Lab Notes 🧪, C++, CMake

Assuming you’re using the “CMake Tools” VSCode extension, here’s what works for me.

1 – Set CMAKE_COLOR_DIAGNOSTICS to ON in your environment

This makes CMake pass -fcolor-diagnostics to clang. If you build on the command line, you’ll now have color. But the VSCode “output” pane will still be non-colored.

2 – Install the “Output Colorizer” extension from IBM.

This adds color to the Output pane.

It looks like this:

Links:

https://github.com/ninja-build/ninja/issues/174

https://github.com/microsoft/vscode-cmake-tools/issues/478