EdSchouten

Yeah, that Sudoku puzzle has multiple valid solutions, whereas the page only seems to accept a single one.

It looks like the code of the course was 2WC16. Unfortunately the course material no longer seems to be available online.

I still remember following Andries’s “Linux kernel hacker’s hut” course he taught at the Eindhoven University of Technology (TU/e) back in 2010. Every week we’d get an assignment where we had to write exploits for commonly occurring security vulnerabilities (e.g., buffer overflows, bad printf format). It was one of the most enjoyable courses I ever followed. Thanks for that, Andries!

If sizes are unsigned, like in C, C++, Rust and Zig – then it follows that anything involving indexing into data will need to either be all unsigned or require casts.

I don’t really get this claim. Indexing should just look up the element corresponding to the value provided. It’s easy to come up with semantics that are intuitive and sound, even if signed integers or ones smaller than size_t are used.

You can always use a divide and conquer strategy to compute the chunks. Chunk both halves of the file independently. Once that’s done, you redo the chunking around the midpoint of the file forward, until it starts to match the chunks obtained previously.

It depends on the architecture. On ARM64, SHA-256 tends to be faster than BLAKE3. The reasons being that most modern ARM64 CPUs have native SHA-256 instructions, and lack an equivalent of AVX-512.

Furthermore, if your input files are large enough that parallelizing across multiple cores makes sense, then it's generally better to change your data model to eliminate the existence of the large inputs altogether.

For example, Git is somewhat primitive in that every file is a single object. In retrospect it would have been smarter to decompose large files into chunks using a Content Defined Chunking (CDC) algorithm, and model large files as a manifest of chunks. That way you get better deduplication. The resulting chunks can then be hashed in parallel, using a single-threaded algorithm.

That’s great! People who do that are often inconsiderate of how it affect others. First of all, it generates unnecessary noise, which is annoying for neighbors who are still trying to sleep. Pedestrians/cyclists also need to breathe those exhaust gases.

I don’t understand why I would need to care about this. Can’t my operating system and/or pthread library sort this out by itself?

Yeah, that's true. Having some kind of chunking algorithm that's content/file format aware could make it work even better. For example, it makes a lot of sense to chunk source files at function/scope boundaries.

In my case I need to ensure that all producers of data use exactly the same algorithm, as I need to look up build cache results based on Merkle tree hashes. That's why I'm intentionally focusing on having algorithms that are not only easy to implement, but also easy to implement consistently. I think that MaxCDC implementation that I shared strikes a good balance in that regard.

In my case I observed a ~2% reduction in data storage when attempting to store and deduplicate various versions of the Linux kernel source tree (see link above). But that also includes the space needed to store the original version.

If we take that out of the equation and only measure the size of the additional chunks being transferred, it's a reduction of about 3.4%. So it's not an order of magnitude difference, but not bad for a relatively small change.

Yeah, GEAR hashing is simple enough that I haven't considered using anything else.

Regarding the RNG used to seed the GEAR table: I don't think it actually makes that much of a difference. You only use it once to generate 2 KB of data (256 64-bit constants). My suspicion is that using some nothing-up-my-sleeve numbers (e.g., the first 2048 binary digits of π) would work as well.

I’ve also been doing lots of experimenting with Content Defined Chunking since last year (for https://bonanza.build/). One of the things I discovered is that the most commonly used algorithm FastCDC (also used by this project) can be improved significantly by looking ahead. An implementation of that can be found here:

https://github.com/buildbarn/go-cdc

So 19494 is the largest? That's far lower than I expected. There's nobody out there that has put a date in a version number (e.g., 20250915)?

Soon available for people in the Vatican as well?

Exactly! At the same time you also don't want to call into the kernel's internal malloc() whenever a thread ends up blocking on a lock to allocate the data structures that are needed to keep track of queues of blocked threads for a given lock.

To prevent that, many operating systems allocate these 'queue objects' whenever threads are created and will attach a pointer to it from the thread object. Whenever a thread then stumbles upon a contended lock, it will effectively 'donate' this queue object to that lock, meaning that every lock having one or more waiters will have a linked list of 'queue objects' attached to it. When threads are woken up, they will each take one of those objects with them on the way out. But there's no guarantee that they will get their own queue object back; they may get shuffled! So by the time a thread terminates, it will free one of those objects, but that may not necessarily be the one it created.

I think the first operating system to use this method was Solaris. There they called these 'queue objects' turnstiles. The BSDs adopted the same approach, and kept the same name.

https://www.oreilly.com/library/view/solaristm-internals-cor...

https://www.bsdcan.org/2012/schedule/attachments/195_locking...

Calls to bind(), connect(), listen(), and accept() can be used to initiate and accept connections in much the same way as with TCP, but then things diverge a bit. [...] The sendmsg() and recvmsg() system calls are used to carry out that setup

I wish the article explained why this approach was chosen, as opposed to adding a dedicated system call API that matches the semantics of QUIC.

That's not entirely true: with CBOR you can add custom data types through custom tags. A central registry of them is here:

https://www.iana.org/assignments/cbor-tags/cbor-tags.xhtml

This is, for example, used by IPLD (https://ipld.io) to express references between objects through native types (https://github.com/ipld/cid-cbor/).

Those plants likely have a higher efficiency than a gas powered stove, so may be worth it regardless?

If only there was a variant of execve() / posix_spawn() that simply took a literal array of which file descriptors would need to be present in the new process. So that you can say:

    int subprocess_stdin = open("/dev/null", O_RDONLY);
    int subprocess_stdout = open("some_output", O_WRONLY);
    int subprocess_stderr = STDERR_FILENO; // Let the subprocess use the same stderr as me.
    int subprocess_fds[] = {subprocess_stdin, subprocess_stdout, subprocess_stderr};
    posix_spawn_with_fds("my process", [...], subprocess_fds, 3);

It looks like @HoussemNasri forked @CookiePLMonster's website repo:

https://github.com/HoussemNasri/HoussemNasri.github.io

Maybe that person simply wanted to have a nice template to work with, but forgot to scrub all the old content?

Same in Dutch. “Oproepen” means “to summon”. We would use “aanroepen”.

zettELkasten

Just like “this entire meeting could have been an email”, all this effort writing this gist could have been spent creating a PR.

The Dutch have a very lackadaisical attitude to law

What do you mean by this specifically?

Relatedly, what's the advantage of that secretbox package over calling https://pkg.go.dev/crypto/cipher#NewGCM ?

Indeed. A screenshot of the resulting output would have been more useful.

An interesting aspect of waitid is that it allows you to access the full exit code of the process (i.e., the entire int instead of just the bottom 8 bits).

Unfortunately, many operating systems implement waitid() on top of one of the older APIs, meaning the top bits get lost regardless…

strlcpy()!

Note that it doesn’t remove support for 32 bit apps. It only removes the ability to boot 32 bit operating systems.

Exactly. This is also highly problematic if you try to perform atomic operations against bare 64 bit integers on those systems, because the atomic instructions do require them to be 8 byte aligned. In C11 and later it’s not an issue, because _Atomic(int64_t)’s alignment may be stricter than int64_t.

This was also an issue in Go, because it tries to use the same alignment rules as C to make cgo work. There they also solved it by adding dedicated atomic types.

https://github.com/golang/go/discussions/47141