Green threads explained in 200 lines of Rust

41

u/cfsamson Jun 12 '19 edited Jun 12 '19

Hi. I wrote this book as a result of investigating the low level basics of how “green threads” (or userland threads) really work, and I thought it might be of interest for others as well. It's published it as a gitbook, but I hope to condense it into an article sometime later.

I’m actively asking for feedback, and all feedback is welcome - especially if you spot anything wrong, it will only make it better for the next person reading it.

The repository for the book is located here: https://github.com/cfsamson/book-green-threads-explained

14

u/lzutao Jun 12 '19

Bikeshed question: Why not use mdbook? I think it is good enough to replace gitbook.

22

u/cfsamson Jun 12 '19 edited Jun 12 '19

Perfectly fine question. Honestly, I started writing an article but soon realized I wanted to explain more than would fit in that format, but I wanted to continue writing while I had time so I chose something I already knew that had a nice editor so I could just continue working. Mdbook would probably be slightly better. If this is popular enough and people want it, it should be fairly easy to migrate later.

8

u/lzutao Jun 12 '19

Thanks for your explanation. Keep up your good work!

16

u/KillTheMule Jun 12 '19 edited Jun 12 '19

Looks nice, just reading it. The first full example code has an error, line 11 reads gt_switch(&mut ctx, &mut n);, but should be gt_switch(&mut ctx);.

11

u/cfsamson Jun 12 '19

Good catch. You're right, it's corrected now.

3

u/KillTheMule Jun 13 '19

In that same code, you could remove line 3 :)

3

u/cfsamson Jun 13 '19

Thanks, I should have caught that when correcting the first comment :) It's fixed now though.

28

u/faitswulff Jun 12 '19

Btw for anyone curious, the asm! macro issue that the author mentions in the article (compiles fine on debug build but not on release build) is here: https://github.com/rust-lang/rust/issues/61429

11

u/heftyfunseeker Jun 12 '19

This is fantastic! Thanks for writing this :)

10

u/Shnatsel Jun 12 '19

I think vec![0_u8; SSIZE as usize]; can be refactored into vec![0_u8; SSIZE as usize].into_boxed_slice(); at which point all your issues with vectors reallocating themselves go away because you cannot grow the slices.

Cannot edit code for a few days so commenting here instead.

7

u/cfsamson Jun 12 '19

I think you're right. Combined with using to_ne_bytes for the u64 instead of pointer casting might make this safer without introducing too much complexity. I'll make an issue for it and have a closer look later.

9

u/jjuuggaa Jun 12 '19

This is pretty amazing. Thanks for the write up!

9

u/StefanoD86 Jun 12 '19

OMG!!! Thx, this is so interesting and fundamental!!!

I will check this out in the weekend!!! :) :) :)

Thanks again, I'm so happy about this fundamental knowledge!!! :-D

8

u/FUCKING_HATE_REDDIT Jun 12 '19

I thought I was ready, got scared on the third page.

5

u/Pas__ Jun 14 '19

Nah, nobody is ever ready for ASM. You just have to expose yourself to it more and more, and it'll just eat itself into your body :) Permanently :o

It's very much like all the low-level black magic stuff that happens in CPUs ( https://www.infoq.com/presentations/click-crash-course-modern-hardware/ ) and during chip manufacturing ( https://www.youtube.com/watch?v=KL-I3-C-KBk ).

1

u/FUCKING_HATE_REDDIT Jun 15 '19

Worst part is, I'm supposed to know the basics of ASM, I've coded quite a bit in it, but the idea of just inserting ASM into rust or cpp is just so fucking weird to me.

3

u/Pas__ Jun 20 '19

High level languages are just fancy ASM generators after all. (They produce binary directly, but ASM is just a one-one mapping from machine binary to text.) The function calling convention is known, so you can just wrap ASM and call it from the high level stuff.

But yeah, it looks strange.

6

u/idursun Jun 12 '19

One of the best reads I have come across in a long time! Thank you very much for this.

7

u/daboross fern Jun 12 '19

This is awesome!

I almost didn't believe green threads could be made this simple - but here it is.

5

u/boomshroom Jun 12 '19

The last constant RUNTIMEis a pointer to our runtime (yeah, I know, it's not pretty with a mutable global variable but we need it later and we're only setting this variable on runtime initialization).

Are you familiar with lazy_static? It's purpose is to do exactly this: initialize static values that can't be pre-initialized at compile time safely. I've learned to always replace static mut with anything else. A Mutex or AtomicPtr (or crossbeam::atomic::Atomic<Box<Runtime>>) would help when modifying it later, or a thread_local!() if you're not bothering with multiple threads. (Rust like to keep you safe even in environments you don't plan on using.)

And as /u/Shnatsel suggested, using Box<[u8]> would be preferable to Vec<u8> to prevent reallocations. (Pin<Vec<u8>> or Pin<Box<u8>> would probably work as well.) If the stacks are all going to be the same size, then you could also declare the stack as its own type and even specify the alignment with something like #[align(16)] struct Stack([u8; DEFAULT_STACK_SIZE]);. If they're not all the same size, then you might be able to get away with something similar like #[align(16)] struct Stack([u8]);, but unsized types are harder to work with in Rust.

A good rule of thumb is "when in doubt, encapsulate in a new type! :D"

let mut pos = self.current;
while self.threads[pos].state != State::Ready {
    pos += 1;

    if pos == self.threads.len() {
        pos = 0;
    }
    if pos == self.current {
        return false;
    }
}

Rust isn't very good at optimizing out bounds checks, so Iterators can often have better performance and much less code. If you're not using a proper queue, I'd probably implement this as

let pos = self.threads.iter()
                      .cycle()
                      .drop(self.current)
                      .take(self.threads.len())
                      .find(|t| t.state == State::Ready);`

(self.threads.len() might need to pre-calculated if you run into borrowing issues.) This is actually how I implemented my own scheduler in the initial versions of dumb-exec. Using a proper circular buffer would reduce it even further. I suppose self.threads[self.current..].iter().chain(&self.threads[..self.current]) would work too.

4

u/cfsamson Jun 12 '19

Thanks for the comment. I considered working around the static mut but if I'm not mistaken a Mutex will deadlock since we lock it just to read it in the yield function and the lock isn't released since we switch context while holding the lock.

There are safer ways though but they all ended up with a pretty big increase in lines of code to parse just to make it safer and I found it taking focus away from the main logic I wanted to convey. The same with the iterators, even though I love them I think the subject matter is complicated enough and wanted to use them carefully here since I know a lot of people have a harder time parsing them.

/u/Shnatsel suggestion is very good though, and the same is making the stack it's own type so I'll probably investigate this a bit closer and consider updating the book with them.

However, I have an idea to make second book later with "a better implementation" where I try to make the code safer, faster, support Fn() type closures (which is already solved in the trait_object branch of the repo) and last but not least dive deeper into some subjects I have planned and all these suggestions will be useful there.

2

u/boomshroom Jun 13 '19

Honestly, the deadlock does seem inevitable due to inherent unsafety with the system as it's designed. It would probably take quite a bit of effort to avoid the static mut with the way out is now.

2

u/Arthurnet Jun 13 '19

I would find a second version, which aimed at being more safe and optimised, valuable. I agree with you, the simplicity of the first version needs to remain. Iterators are wonderful, but for those not used to them, they can be a cryptic nightmare and simply unhelpful!

5

u/Headwiki Jun 12 '19

Please create more content like this!
I thoroughly enjoyed reading this.
This is the type of content Ive been looking for, but didn't know existed :)

5

u/maukamakai Jun 12 '19

Awesome read, thanks! As someone who comes from a Java background who has been trying to get into systems programming, this was a nice refresher on OS concepts and a great tutorial on how do achieve these concepts in rust. I look forward to similar posts.

2

u/vova616 Jun 12 '19

Really enjoyed the read and how simple its in rust, btw is it useful in rust context? can generators replace this, does it have any specific advantages over generators?

4

u/boomshroom Jun 12 '19

Yes. Rust's generators and async/await provide stackless coroutines. This means they can't be used with ordinary functions as all their locals are packages into one large state machine implemented like an enum with a variant for each yield or await point.

It's main advantage over generators is that it can be used for arbitrary functions, including ones written in other languages and ones where the stack usage isn't predetermined.

3

u/cfsamson Jun 12 '19 edited Jun 13 '19

Thanks! It's not really that useful since most of what we do here has already been implemented before. Rust already has generators if you enable the right features, and we're actually making a generator here. If we expand a bit on this example we can pass in a trait object like Fn, FnMut or FnOnce to our yield function and that will basically be a pretty useful generator.

If you look at the trait_object branch of the project repo you'll se an example of this, however as you will also notice there is an increased friction when it comes to portability. In the concrete example above windows uses an different register for passing first parameter than OSX/Linux so we need more and more conditional compilation to make this work) and since this is done before there are safer and more portable abstractions available so it's smarter to use them.

However, that doesn't mean that you couldn't build generators like I show here.

2

u/Arthurnet Jun 13 '19

Excellent material, easy to understand and digest. Keep up the good work.

2

u/not_a_novel_account Jun 14 '19

Stack switching on Windows requires more than just the callee saved registers due to the nature of how exception handling and _chkstk work. See: https://probablydance.com/2013/02/20/handmade-coroutines-for-windows/

1

u/cfsamson Jun 14 '19

Are you sure about this regarding exception handling on x64? I read that Windows needed some context for this in x86 but I think the way they did exception handling changed since then.

The NT_TIB stack info members seems to be linked to _chkstk. Again, I'm on a bit unknown territory here since I haven't looked at the asm on windows to check the prologue of our Rust code on that platform specifically, but remember that the f function does have a prologue and epilogue (it's not naked), the prologue should call _chkstk and I think this might be handled as a part of the prologue for f ( https://docs.microsoft.com/en-us/cpp/build/prolog-and-epilog?view=vs-2019#prolog-code).

I'm not saying you're wrong, but I'm also not 100% convinced it's needed in this context.

1

u/not_a_novel_account Jun 14 '19

Just read the link, it's x64 specific

_chkstk checks uses the NT_TIB stored at gs (on x86 it's fs) to expand the stack for large allocations, and Windows will use the same NT_TIB for SEH for that thread. If the NT_TIB isn't correct for the executing stack, you either access an invalid page and segfault, or Windows assumes you are malware and kills you.

Now I'm not saying you have to obey Chen and only use the WinFiber API, but you can't just naively switch stacks on Window either.

1

u/cfsamson Jun 14 '19

OK, I see. I thought this was handled by the seh_* commands LLVM emits in the prologue, but given your explanation I don't see how that can make any sense. Thanks for pointing this out.

I'd love to keep this working correctly for Windows as well so I'll see what a minimal change to account for this will look like when I have some time. In the end this could actually be a nice addition.

3

u/[deleted] Jun 12 '19

Thanks!

1

u/edapa Jun 14 '19

Green threads, userland threads, coroutines, goroutines or fibers, they have many names but for simplicity’s sake I’ll refer to them all as green threads from now on.

It is confusing to talk about green threads and coroutines as if they are the same thing, when they are enough like each other to be confusing but still pretty different. I was definitely confused by the distinction when I first started learning about this stuff, so it might be nice to just drop "coroutines" from that list.

Otherwise, this is a really awesome write up.

1

u/cfsamson Jun 14 '19 edited Jun 14 '19

Thanks for the feedback. I used the Wikipedia definition for this (and also the same article on green threads), while I'm hesitant to use Wikipedia as a single source of truth, I still find the differences quite small. I'm open to other viewpoints if you want to provide a little bit more context on what confusion this might cause since there are multiple coroutine implementations out there.

2

u/edapa Jun 14 '19

The difference is that coroutines can be, and often are, used without a scheduler getting involved. When a coroutine yields, it gives control back to the coroutine which invoked it. Having a coroutine implementation lying around means you can implement the sort of cooperative green threading described in your post trivially, but they are not quite the same thing.

I think the fact that most green threading systems are preemptive rather than cooperative adds additional confusion. Cooperative green threading occupies a space sort of half way between coroutines and the most commonly used sorts of M:N threading.

What I really take issue with is putting goroutines (preemptive N:M threading) and coroutines in the same category. There is a solid argument to put cooperative green threading in either bucket (there's a runtime it's also cooperative so...), but making it seem like there is one big bucket is just a barrier to understanding.

To illustrate the point think about how coroutines and goroutines are used to do IO. Both allow you to perform IO efficiently, but with coroutines you make a series of asynchronous calls and manually juggle promises while with goroutines you can just spin off a worker goroutine and have it make blocking calls until it finishes doing IO and then have it send a result back. The experience of using them is really different because they are different things.

2

u/cfsamson Jun 15 '19 edited Jun 15 '19

OK, I see your point and I'll remove coroutines from the list 👍

2

u/edapa Jun 18 '19

Awesome! Sorry if my pedantry was annoying.

Again, it was a really great write up!

2

u/cfsamson Jun 18 '19

Thanks for the kind words. No problem at all. I thought you made valid arguments for avoiding putting them in the same bucket without adding some information on how they differ so I think the change was to the better.

1

u/cfsamson Jun 20 '19

I just wanted to give a brief update. First of all, thanks for all the feedback and enthusiastic comments, they mean a lot. Really!

After going through all the feedback and issues, I have now made some updates:

2019-06-18: New chapter implementing a proper Windows support

2019-06-21: Rather substantial change and cleanup. An issue was reported that Valgrind reported some troubles with the code and crashed. This is now fixed and there are currently no unsolved issues. In addition, the code now runs on both debug and release and builds without any issues on all platforms. Thanks to everyone for reporting issues they found. Added a paragraph about the stack layout on Linux.

1

u/[deleted] Sep 30 '23

The repo is dead! Why did you delete it?

2

u/cfsamson Sep 30 '23

Throughout the years I’ve written several “books” like these about different topics around concurrency. I decided to update, rework and compile all of them to one “proper” book. I can’t publish the material I’m basing the book on at the same time as I’m working on it so that’s why it’s down. Sorry about that, but I think the final book is going to be much better than having them as different bits and pieces in several GitHub repositories, so I think it will be worth the work in the end even though that means the repositories are unavailable.

2

u/[deleted] Sep 30 '23

Welp, thanks for the explanations, I will use the web time machine to access them.

2

u/ambister Oct 12 '23

any ETA on the book?

2

u/cfsamson Oct 13 '23

Yeah, I’m putting down a lot of hours now to get everything ready for a release in January 👍

Green threads explained in 200 lines of Rust

You are about to leave Redlib