Introduction

What is CSD?

CSD contains C++23 implementations of several well-known data structures from the BSD family of operating systems. 1

It provides the following:

• STL-like implementation of BSD’s queue(3) intrusive linked list library (link)

• STL-like implementation of BSD’s intrusive, chained hash tables, similar to hashinit(9)

• std::pmr::memory_resource-compatible implementation of the vmem(9) general purpose memory allocator

• std::allocator-compatible implementation of the uma(9) “zone” pool allocator

• STL-like ring buffers based on FreeBSD’s buf_ring(9) and DPDK’s librte_ring

• A ring based shared memory allocator based on DPDK’s librte_mempool

• A read/writer mutex that keeps track of all readers for debugging and robust deadlock detection, based on FreeBSD’s rmlock and conforming to the C++17 threading library concepts.

CSD is an acronym for “Cyril Software Data Structures”; it is used in other open source releases from the Cyril Software Group (CSG). Because it provides core functionality to other CSG projects, its classes are defined directly in namespace csg so they can be referenced via unqualified names in other CSG code.

When C++20 modules support improves in both gcc and clang, the name CSD will go away and it will be distributed as the module csg.core.

Warning

This is an alpha release of CSD, made so that other early-stage projects could source it from github. Some of the libraries described above are not included in this alpha release, and the libraries that are included do not have stable APIs or complete documentation.

Warning

This alpha release of CSD uses C++20 concepts. For this reason, the reference documentation is often incorrect or missing, since the concept declarations cannot be parsed by doxygen.

Why should I care about this library?

Consider this sad-but-true observation from The Architecture of Open Source Applications:

Architects look at thousands of buildings during their training, and study critiques of those buildings written by masters. In contrast, most software developers only ever get to know a handful of large programs well – usually programs they wrote themselves – and never study the great programs of history. As a result, they repeat one another’s mistakes rather than building on one another’s successes.

Most programmers are terrible software architects because they have never studied a truly great program designed by engineers who have mastered the art. If you have not done this, you should do it! One “great program of history” you might want to study is the FreeBSD kernel, because it has such excellent documentation.

Why BSD and and why UNIX?

The Design and Implementation of the FreeBSD Operating System – one of the great works in computer science literature – walks through designs for all major subsystems needed for a modern OS. You will finish this book not just understanding a single great program, but understanding the brilliance of the original UNIX architecture.

This architecture is peerless in computer science – where there were once a million and one competitors, over time UNIX vanquished them all. This happened in large part because the clean, well-documented design made it possible to teach the architecture to the next generation of engineers. Every decade or so, a hefty tome would be published describing an updated UNIX design to the next class of operating system acolytes. This was true since the very beginning, through the critical years of its adoption, during the years it made the Internet possible and when it replaced everything in commercial computing, right up until modern times where it is essentially one of only two designs left in the world – and its only remaining competitor is slowly embracing its programming interface.

What CSD offers you

In my experience, the effect of studying any great program is two-fold. First, your skills are vastly increased, elevating you from a mere programmer to a true “software engineer.” Once you have seen what a great program looks like, you can stand on the shoulders of giants and credibly try to emulate it.

A second, more subtle effect is that the “patterns” and “structure” of the code begin to rub off on you. Just like artists are able to cite their “artistic influences,” your own programming style becomes influenced by the great programs you study.

When this happens, there is a typically a problem.

All “large” programs (> 100,000 lines of code) are full of smaller helper libraries and attendant design patterns that help organize their code. Because the “great programs of history” are, by definition, very cleanly designed, you find yourself reaching for their libraries and design patterns in your own projects.

Although such code is typically useful outside of the original project, it often isn’t easy to repackage into a free-standing library. Sometimes it’s full of dependencies on unwanted interfaces (e.g., header files). Other times, you want to reuse the core ideas but in a different programming language.

CSD contains high quality, free-standing re-implementations of several such libraries from BSD-licensed code bases. The original libraries were mostly written in C, whereas CSD rewrites them using C++20 idioms.

If you haven’t studied any of the programs that this code is derived from, you might not see the appeal. However, if you have witnessed the engineering excellence of these programs, you just might find yourself reaching for these powerful abstractions in your C++ projects.

And finally, here they are!

How do I install CSD?

CSD is a header-only library, so there is little to do. However, you should read the installation page if you want to:

• Enable CSD assertions (to catch undefined behavior if you break the API contract)

• Install the GDB debug pretty printers

• Build the test suite or the documentation

1

CSD was originally called “BDS” – for “BSD Data Structures” – but the similarity between BSD and BDS made the documentation difficult to read. The old name was also slightly misleading, because a few of the designs come from OpenSolaris and DPDK.