EdSchouten

22 hari yang laludiscuss

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.

EdSchouten

bulan laludiscuss

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!

EdSchouten

2 bulan yang laludiscuss

> 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.

EdSchouten

6 bulan yang laludiscuss

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.

EdSchouten

6 bulan yang laludiscuss

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.

EdSchouten

6 bulan yang laludiscuss

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.

EdSchouten

7 bulan yang laludiscuss

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?

EdSchouten

10 bulan yang laludiscuss

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.

EdSchouten

10 bulan yang laludiscuss

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.

EdSchouten

10 bulan yang laludiscuss

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.

EdSchouten

10 bulan yang laludiscuss

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

EdSchouten

10 bulan yang laludiscuss

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)?

EdSchouten

11 bulan yang laludiscuss

Soon available for people in the Vatican as well?

EdSchouten

11 bulan yang laludiscuss

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...

EdSchouten

12 bulan yang laludiscuss

> 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.

EdSchouten

12 bulan yang laludiscuss

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/).

EdSchouten

12 bulan yang laludiscuss

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

EdSchouten

12 bulan yang laludiscuss

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);

Never understood why POSIX makes all of this so hard.

EdSchouten

12 bulan yang laludiscuss

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?

comments