WEBVTT NOTE This file was generated by Descript 00:00:13.941 --> 00:00:15.751 This is Self-Directed Research. 00:00:15.891 --> 00:00:18.661 James and Amos, our hosts, get really excited about different 00:00:18.661 --> 00:00:22.038 things, and each week they take turns presenting their ideas to each other. 00:00:22.338 --> 00:00:25.550 We have another announcement: this week we are adding a video version of 00:00:25.560 --> 00:00:27.300 the episode that follows the slides. 00:00:27.570 --> 00:00:31.500 Check out the website, YouTube, or Spotify to see the presentation in action. 00:00:32.170 --> 00:00:37.090 Visit sdr-podcast.com/episodes for previous episodes, more presentations, 00:00:37.100 --> 00:00:38.560 show notes, and transcripts. 00:00:38.780 --> 00:00:40.700 New episodes are published every Wednesday. 00:00:41.550 --> 00:00:44.730 Today's episode is sponsored by the Postcard crate, which is looking 00:00:44.730 --> 00:00:46.540 for sponsors for the 2.0 release. 00:00:46.830 --> 00:00:50.180 More info on that at the end of the episode or in our show notes. 00:00:50.510 --> 00:00:54.020 This week, James presents "What Are You Syncing About?" 00:00:59.546 --> 00:01:01.226 So for this presentation, I've done the funniest 00:01:01.226 --> 00:01:05.409 thing possible for uh, an audio podcast and added a visual gag. 00:01:05.568 --> 00:01:07.588 We'll see how many people end up coming and looking at the 00:01:07.588 --> 00:01:08.778 video version of this one. 00:01:09.258 --> 00:01:11.001 But this is uh, what are you syncing about? 00:01:11.251 --> 00:01:15.791 So I generally just want to talk about one of my favorite async libraries, 00:01:15.831 --> 00:01:19.831 and I am biased because I've worked on it and done some contributions to 00:01:19.831 --> 00:01:25.401 it, but it's one of the few libraries that every single time I have to use 00:01:25.401 --> 00:01:28.331 it or modify it, I've just come away... 00:01:28.761 --> 00:01:30.511 like, I don't have a better word than chuffed. 00:01:30.551 --> 00:01:33.241 Like, it's just, it works the way that I want it to work. 00:01:33.292 --> 00:01:35.822 It's designed in the way that I would want it to be designed. 00:01:35.822 --> 00:01:39.922 So I wanted to just share my excitement about it. 00:01:40.782 --> 00:01:43.122 And that library is called maitake-sync. 00:01:43.702 --> 00:01:47.022 So it comes from the mycelium project. 00:01:47.032 --> 00:01:51.232 And this is from Eliza from tokio and tracing fame. 00:01:51.452 --> 00:01:55.402 She was working on an operating system project for a while called mycelium. 00:01:55.692 --> 00:01:59.282 It has sort of a mushroom theme to all the names and things like that. 00:01:59.592 --> 00:02:04.642 We then kind of joined forces on another operating system project, but this comes 00:02:04.642 --> 00:02:07.722 from her original work in this area. 00:02:08.772 --> 00:02:12.682 So, maitake is actually the executor of that project. 00:02:12.772 --> 00:02:15.822 Like tokio or embassy, it is an executor. 00:02:16.062 --> 00:02:19.302 It is aimed, interestingly, sort of between those two. 00:02:19.312 --> 00:02:23.652 It's very influenced by tokio, but it's written in a way that works on 00:02:23.662 --> 00:02:28.152 bare metal or inside of a kernel kind of operation, where you may or may 00:02:28.152 --> 00:02:32.732 not have heap allocation, or it may not be the standard library's heap 00:02:32.732 --> 00:02:36.102 allocation interface if you're running the allocator in the operating system. 00:02:36.868 --> 00:02:42.078 But it had such useful pieces that eventually she broke maitake-sync 00:02:42.098 --> 00:02:47.598 out to just have the sync primitives exposed for anyone to use. 00:02:47.608 --> 00:02:49.598 So this is published on crates.io. 00:02:49.978 --> 00:02:55.278 But this is sort of the synchronization primitives piece of maitake. 00:02:55.608 --> 00:02:59.668 So if you use tokio, it has a module called `tokio::sync`. 00:03:00.168 --> 00:03:04.308 And those are all of the synchronization primitives that tokio brings off the 00:03:04.308 --> 00:03:08.478 shelf, or embassy- the executor also has broken out a crate called embassy-sync. 00:03:08.498 --> 00:03:12.858 This is just: hey, these are sort of like the first party synchronization 00:03:12.878 --> 00:03:16.548 primitives, or things that you can use in async as building blocks. 00:03:16.768 --> 00:03:20.128 They may not be tied to that executor, it's just where they came from. 00:03:20.739 --> 00:03:25.934 And when we're working in async code, I describe async code is all about waiting. 00:03:26.354 --> 00:03:28.214 You are waiting for a packet to come in. 00:03:28.214 --> 00:03:29.874 You are waiting for an event to happen. 00:03:29.884 --> 00:03:34.584 Your task is pending because it's waiting for some kind of event to happen. 00:03:34.584 --> 00:03:41.104 So the concept of waiting is huge, but that connection of how a task 00:03:41.104 --> 00:03:45.849 goes from waiting to ready to run is all about being notified. 00:03:46.031 --> 00:03:50.511 So I like to think of sync primitives as being all about notifications. 00:03:50.771 --> 00:03:55.771 They're the thing that when an event happens, wakes up your task and says, 00:03:55.771 --> 00:03:57.361 "Hey, that thing you were waiting on? 00:03:57.531 --> 00:03:58.361 It's time to go." 00:03:59.518 --> 00:04:02.648 These are useful for building essentially anything async. 00:04:02.988 --> 00:04:05.898 It could be tied to hardware like an ethernet packet. 00:04:05.898 --> 00:04:09.378 So your reactor, whatever, might want to wake up a task when an 00:04:09.388 --> 00:04:14.343 ethernet frame is received, but it could also just be totally async data 00:04:14.343 --> 00:04:16.773 structures, like a mutex, for example. 00:04:17.013 --> 00:04:21.143 If you're holding a locked async mutex, and another task comes 00:04:21.143 --> 00:04:22.423 along and wants to lock it... 00:04:22.651 --> 00:04:23.281 it can't. 00:04:23.381 --> 00:04:25.761 It needs to wait until the other task is done. 00:04:26.041 --> 00:04:30.131 So it needs some way of saying: first, I would like to be notified, and to give 00:04:30.131 --> 00:04:34.634 that to the mutex and say, "Next time you got a spot available, wake me up." 00:04:35.224 --> 00:04:38.524 And then when that spot becomes available, it wakes up that task, 00:04:38.534 --> 00:04:43.114 so that task has a chance to come back and get access to that mutex. 00:04:43.700 --> 00:04:48.435 Now, with how Rust async works, it's not actually passing anything 00:04:48.435 --> 00:04:49.945 along in that notification. 00:04:50.175 --> 00:04:52.685 There's not usually some, like, associated data. 00:04:52.715 --> 00:04:56.145 It's just kind of like, when you say I want to wait for something... 00:04:56.355 --> 00:04:58.315 Have you ever been to a restaurant and they have those beepers? 00:04:58.315 --> 00:05:01.775 Like, when you order food or your table's not ready yet, and they hand you a beeper, 00:05:01.775 --> 00:05:06.355 and then you go sit in the waiting room, and then once your table is ready or your 00:05:06.355 --> 00:05:08.285 food is ready, the little beeper buzzes. 00:05:08.889 --> 00:05:11.139 And they haven't given you your food through the buzzer. 00:05:11.339 --> 00:05:15.454 You just know that it's time to go up to the desk or the counter and check. 00:05:15.844 --> 00:05:19.134 So you've got no information other than, "It's time to check again." 00:05:19.754 --> 00:05:22.754 That's how I usually model or think about Wakers, or when I'm teaching 00:05:22.754 --> 00:05:26.314 them, that's the model I like to use, because it's just a notification. 00:05:26.504 --> 00:05:28.374 Just 'time to come check again.' 00:05:28.958 --> 00:05:34.058 So in particular, maitake-sync has three synchronization primitives that I love. 00:05:34.708 --> 00:05:39.243 The three of them are called WaitCell, WaitQueue and WaitMap. 00:05:39.573 --> 00:05:42.633 They're all 'wait' because they're about waiting or being notified for 00:05:42.633 --> 00:05:47.393 something, and then the back half sort of explains what makes them special. 00:05:48.653 --> 00:05:50.423 So WaitCell's the most basic one. 00:05:50.843 --> 00:05:54.843 It's a synchronization primitive that holds 0 or 1 Wakers. 00:05:54.843 --> 00:05:58.353 If you've used like the future crate or tokio, if you've ever heard of something 00:05:58.353 --> 00:06:02.763 like an atomic-waker before, WaitCell is very much like an atomic-waker. 00:06:03.948 --> 00:06:07.618 Internally we can kind of think of it like a `Mutex>` 00:06:07.958 --> 00:06:11.348 When a task comes along and wants to be, it knows that it needs to wait. 00:06:11.408 --> 00:06:14.228 The mutex isn't available, it needs to wait. 00:06:14.258 --> 00:06:19.228 So it goes, "Hey, WaitCell: here is a Waker to me, my async 00:06:19.258 --> 00:06:21.888 task, and here's my Waker. 00:06:21.888 --> 00:06:22.878 You hold onto this. 00:06:22.878 --> 00:06:26.688 Whenever that mutex is ready, wake me through that handle." 00:06:27.018 --> 00:06:29.738 It's sort of like that receiving of the beeper, of like, you kind of 00:06:29.738 --> 00:06:34.938 check in, you go, "Here's my waker, beep me whenever the thing is ready." 00:06:35.472 --> 00:06:37.332 What's in the Waker specifically? 00:06:37.332 --> 00:06:41.822 Because I, I have whiplash from reading tokio internals and Rust 00:06:41.832 --> 00:06:43.622 async machinery in general, and... 00:06:43.632 --> 00:06:46.332 is it just a vtable with a bunch of raw pointers again? 00:06:47.026 --> 00:06:49.536 So the way it typically works is it has a pointer 00:06:49.536 --> 00:06:51.616 to the task that is waiting. 00:06:52.046 --> 00:06:56.896 And by waking, what you're doing is you're taking that handle of that task 00:06:56.926 --> 00:06:59.356 and adding it to the executor's run queue. 00:06:59.686 --> 00:07:02.846 So you're actually taking this task that's floating out in the ether 00:07:02.856 --> 00:07:05.166 somewhere, just waiting and sleeping. 00:07:05.581 --> 00:07:09.131 And you take that pointer and give it to the executor and say, 00:07:09.321 --> 00:07:10.801 "Hey, this task is ready to run." 00:07:11.181 --> 00:07:15.091 So I'm sure there's some complication of how different executors do this, but more 00:07:15.091 --> 00:07:21.461 or less, the Waker is primarily a pointer to the task itself, or a handle of the 00:07:21.461 --> 00:07:26.311 task, which is then given to the executor to say, "This one's ready," or it adds 00:07:26.311 --> 00:07:28.361 it to the list of things that are ready. 00:07:28.941 --> 00:07:31.666 Right, so, while you were explaining, I did a bit of research 00:07:31.666 --> 00:07:35.296 and actually the Waker type is from the standard library and it does, it's like 00:07:35.296 --> 00:07:39.996 a wrapper over `RawWaker` and it is pretty much data plus virtual table. 00:07:41.754 --> 00:07:43.174 This is very simple to think about. 00:07:43.204 --> 00:07:46.044 We have storage for zero or one items. 00:07:46.164 --> 00:07:47.434 It's an option. 00:07:47.704 --> 00:07:49.574 We store the data in the Waker. 00:07:49.574 --> 00:07:53.171 So like the mutex will just have an option, or a mutex option 00:07:53.591 --> 00:07:55.281 inside of the mutex itself. 00:07:55.281 --> 00:07:58.941 So wherever the mutex is allocated, the space for that Waker is. 00:07:59.201 --> 00:08:01.171 And so when you want to wait on it, you give it the thing. 00:08:01.171 --> 00:08:02.611 It kind of puts it in its pocket. 00:08:02.651 --> 00:08:04.741 And then when the data is available again. 00:08:05.111 --> 00:08:06.111 It reaches in it pocket. 00:08:06.141 --> 00:08:09.561 If it has something there, it presses the wake button and then throws it away. 00:08:09.591 --> 00:08:10.921 Cause it says, "I have done my job. 00:08:10.921 --> 00:08:13.321 I have notified, we can move on." 00:08:13.981 --> 00:08:15.401 And it's very simple to think about. 00:08:16.021 --> 00:08:17.701 It's used in a lot of places. 00:08:18.081 --> 00:08:21.661 But it has a problem that it doesn't work with more than one task. 00:08:22.091 --> 00:08:26.171 So let's say we have that mutex and one of them has it locked. 00:08:26.571 --> 00:08:29.888 A second one comes along and says, "I would like access to that mutex!" 00:08:30.188 --> 00:08:33.043 We put it inside the WaitCell, and it goes off. 00:08:33.153 --> 00:08:33.603 Great! 00:08:33.853 --> 00:08:36.303 And then a third task comes along and says, "I would 00:08:36.303 --> 00:08:37.723 like to wait for that mutex!" 00:08:38.153 --> 00:08:39.973 And so now what does the mutex do? 00:08:40.423 --> 00:08:45.153 The only reasonable thing it can generally do is reach into its pocket, if it has 00:08:45.153 --> 00:08:48.713 something there, it just presses the wake button and then throws it away. 00:08:49.073 --> 00:08:51.354 And then grabs the new Waker and puts it in the pocket. 00:08:51.874 --> 00:08:56.634 Because when that second task comes up to the front desk and says, "Hey, 00:08:56.634 --> 00:08:58.500 is access to that mutex ready now?" 00:08:58.700 --> 00:08:59.650 It'll go, "No..." 00:09:00.160 --> 00:09:04.390 But that's kind of the only thing that it can do without losing one of the two. 00:09:04.390 --> 00:09:07.870 It just says, "I sent them a notification, but they're not going 00:09:07.870 --> 00:09:09.400 to be happy when they show up." 00:09:10.480 --> 00:09:13.590 The real problem with this is you get something that's called Waker churn. 00:09:13.920 --> 00:09:18.725 Where these two tasks will basically endlessly fight each other until that 00:09:18.925 --> 00:09:23.285 mutex becomes available, because the second one gets kicked out and then 00:09:23.285 --> 00:09:25.915 it shows back up at the front desk and says, "Hey, can I have my mutex now?" 00:09:25.915 --> 00:09:26.945 And it goes, "No." 00:09:27.155 --> 00:09:29.085 "Okay, here's my waker, wake me when you're done!" 00:09:29.305 --> 00:09:32.315 Reaches in the pocket, throws away the other one, and these two just take 00:09:32.315 --> 00:09:38.055 turns burning CPU until eventually that first task is done with the mutex. 00:09:38.515 --> 00:09:39.685 And one of them will win. 00:09:40.030 --> 00:09:43.177 And this is sort of the other problem: it's a random throw of the dice 00:09:43.177 --> 00:09:45.987 of which one of them wins, because they're just both sitting there 00:09:45.987 --> 00:09:48.777 essentially polling the mutex in async. 00:09:48.817 --> 00:09:54.263 They will check whether the mutex is available, not, yield, and then come back. 00:09:54.263 --> 00:09:57.383 So they're essentially taking turns running, yielding, running, yielding, 00:09:57.393 --> 00:10:01.413 running, yielding, which means at least the runtime can make forward 00:10:01.413 --> 00:10:04.823 progress because these are all yielding, but if the executor is not 00:10:04.823 --> 00:10:08.073 doing anything else, these two will just sit there and burn CPU cycles 00:10:08.093 --> 00:10:10.437 until that mutex is available again. 00:10:10.677 --> 00:10:10.867 Yeah. 00:10:10.867 --> 00:10:14.367 It's a busy loop, because they're, you know, they're not sleeping for anything. 00:10:14.367 --> 00:10:18.217 They're not, there's no actual event system notification stuff going on. 00:10:18.227 --> 00:10:19.757 They're just trying as best as they can. 00:10:19.977 --> 00:10:21.987 They- they, do yield at least. 00:10:21.987 --> 00:10:24.297 So it's not all the way busy, but it's essentially like... 00:10:25.017 --> 00:10:28.147 yeah, like, an endless loop of yield now, basically. 00:10:28.181 --> 00:10:28.851 Almost busy loop. 00:10:29.227 --> 00:10:29.607 I see. 00:10:29.687 --> 00:10:31.777 Which is the second worst thing you can do. 00:10:31.787 --> 00:10:33.087 It is not the worst thing you can do- 00:10:33.107 --> 00:10:33.797 True true, true. 00:10:34.362 --> 00:10:36.922 Which would be like a blocking busy loop, but it is pretty 00:10:36.922 --> 00:10:38.742 much the second worst thing you can do. 00:10:39.173 --> 00:10:41.522 So, it's really useful for something if you have like a 00:10:41.522 --> 00:10:44.332 multi-producer single-consumer channel where there's only going to 00:10:44.362 --> 00:10:46.382 ever be one thing waiting on that. 00:10:46.512 --> 00:10:49.902 So on the single-consumer side, you're only going to ever have one 00:10:49.902 --> 00:10:52.852 task waiting for that data because it has exclusive ownership for it. 00:10:53.152 --> 00:10:57.002 So it works really great for that, but you can't really use it in any 00:10:57.002 --> 00:10:59.592 case- like you couldn't even use it on the multiple-producer side 00:10:59.882 --> 00:11:01.642 because it will just cause problems. 00:11:01.822 --> 00:11:06.082 So, it's great because it's simple, but it's simple, which means it's limited. 00:11:06.803 --> 00:11:09.643 Now, WaitQueue is sort of the next step up. 00:11:09.663 --> 00:11:11.523 It's what the name sounds like. 00:11:11.533 --> 00:11:13.203 It is a queue of waiters. 00:11:13.563 --> 00:11:17.593 It's capable of holding 0 to infinity Wakers, basically. 00:11:17.993 --> 00:11:21.973 If you were doing the multiple-producer single-consumer thing or a mutex, you'd be 00:11:21.973 --> 00:11:24.113 able to just keep tacking on new Wakers. 00:11:24.333 --> 00:11:27.313 You'd be able to access them in a first in first out basis. 00:11:27.493 --> 00:11:31.473 So when someone frees up the mutex, you can go: okay, next in line, I notify 00:11:31.473 --> 00:11:33.323 them, then throw away their waker. 00:11:33.353 --> 00:11:35.803 And then when they're done, I can notify the next in line. 00:11:35.803 --> 00:11:38.933 It's totally fair because it's first in first out... 00:11:39.103 --> 00:11:41.353 All those kinds of good properties that you want. 00:11:42.193 --> 00:11:45.413 But before I said that we stored the Waker inside the mutex. 00:11:45.453 --> 00:11:47.895 It was a single element option. 00:11:47.935 --> 00:11:49.295 So it either was there or it wasn't. 00:11:50.025 --> 00:11:54.775 When you have potentially infinite Wakers, where do you store these? 00:11:55.325 --> 00:11:58.675 If you're on the standard library or on the desktop or something, like 00:11:58.675 --> 00:12:01.945 you could have a mutex VecDeque of Wakers or you could do something 00:12:01.945 --> 00:12:04.375 else clever with heap allocations. 00:12:04.880 --> 00:12:07.900 But I said that maitake and maitake-sync work on bare metal 00:12:07.900 --> 00:12:09.610 systems with no allocator. 00:12:10.060 --> 00:12:14.510 So how could we possibly store an unbounded number of Wakers? 00:12:14.807 --> 00:12:17.357 And the answer is doubly linked lists. 00:12:17.407 --> 00:12:20.647 And because this comes from Eliza, you know it's got doubly linked lists in it. 00:12:21.227 --> 00:12:27.457 And more specifically and more spookily, it is intrusive doubly linked lists. 00:12:28.027 --> 00:12:29.577 And this is the next mushroom name. 00:12:29.577 --> 00:12:34.614 So the intrusive list library from mycelium is called cordyceps. 00:12:35.044 --> 00:12:37.984 If you aren't familiar with cordyceps: this is the fungus that invades 00:12:38.156 --> 00:12:42.646 ants' brains and takes over them and makes them crawl up and so they 00:12:42.646 --> 00:12:44.746 can be eaten and spread the disease. 00:12:44.756 --> 00:12:47.883 But it is an intrusive data structures list. 00:12:48.573 --> 00:12:52.433 And what I mean by intrusive data structures is: when you have that doubly 00:12:52.433 --> 00:12:57.293 linked list, all the nodes, a regular doubly linked list would have sort 00:12:57.293 --> 00:13:01.367 of nodes for each of them, and each of the nodes would point to the data. 00:13:01.377 --> 00:13:04.757 So you would have your string or whatever in the doubly linked list. 00:13:04.757 --> 00:13:09.227 So you would have node, node, node, node, and each node would point to its data. 00:13:09.787 --> 00:13:16.217 Intrusive kind of smashes that together and says that each of these nodes contains 00:13:16.257 --> 00:13:19.087 the pointers and the actual string itself. 00:13:19.107 --> 00:13:23.365 You reduce the number of pointer indirections by one, which is 00:13:23.815 --> 00:13:25.525 fairly convenient for some reasons. 00:13:26.388 --> 00:13:32.608 And this is particularly interesting to us because when you poll a Future- 00:13:33.048 --> 00:13:37.138 and we're talking in async here- so when you poll a Future, you actually 00:13:37.138 --> 00:13:39.398 get two things that are relevant here. 00:13:40.118 --> 00:13:45.274 You get a pinned mutable reference to Self and you get the Context. 00:13:45.594 --> 00:13:47.774 The Context is where we're going to get the Waker from. 00:13:47.814 --> 00:13:49.304 This comes from the executor. 00:13:49.524 --> 00:13:53.199 It says, "Here is where you get your Waker from when you want to be woken," 00:13:53.209 --> 00:13:56.769 like that's where you get the specific pointer and vtable that you'll need 00:13:57.339 --> 00:13:59.179 for the executor to do that waking. 00:13:59.569 --> 00:14:04.689 But that pinned pointer to Self is particularly interesting because 00:14:04.959 --> 00:14:09.749 we know that when the Future has been pinned, as long as it is Not 00:14:09.799 --> 00:14:14.279 unpin, then it cannot move for the existence of the rest of that Future. 00:14:14.579 --> 00:14:18.249 We know that that Future is going to be at this pointer location 00:14:18.599 --> 00:14:20.593 for the remainder of time. 00:14:21.169 --> 00:14:25.499 Which means we could stick something inside of the task or the Future 00:14:25.499 --> 00:14:30.299 itself that has these two pointers- like point backwards point forwards- 00:14:30.609 --> 00:14:33.099 and the actual data and wire it up. 00:14:33.899 --> 00:14:40.379 So somewhat cleverly, every task brings its own storage to the list, which 00:14:40.379 --> 00:14:45.672 means as long as you were able to create the Future or create the task, then 00:14:45.672 --> 00:14:51.212 the room for that node in the linked list lives inside of the task itself. 00:14:52.382 --> 00:14:54.817 Now, the reason that this needs to be a doubly linked list 00:14:54.847 --> 00:14:59.157 instead of a singly linked list is because Futures can be dropped. 00:14:59.797 --> 00:15:04.597 And if a Future is cancelled, it needs to be dropped, then you need to remove 00:15:04.597 --> 00:15:08.187 yourself from that doubly linked list, which means you have to grab the next 00:15:08.187 --> 00:15:12.527 one and the previous one, remove yourself from the equation and wire them up. 00:15:13.897 --> 00:15:14.697 And this is great. 00:15:14.697 --> 00:15:17.207 We can abuse this stable pointer. 00:15:17.237 --> 00:15:20.177 And if we do some fancy things with like `#[repr(C)]` and things like that, 00:15:20.417 --> 00:15:23.997 we can make sure that the pointer that we have is always reasonable to be 00:15:23.997 --> 00:15:25.557 including in this doubly linked list. 00:15:26.177 --> 00:15:30.837 Which is wonderful, because on embedded, we don't have to like, have a const 00:15:30.877 --> 00:15:34.207 generic argument of like, "Okay, how many Waker spaces do we have?" 00:15:34.437 --> 00:15:38.597 Where if you don't give enough, then you get into that Waker churn 00:15:38.597 --> 00:15:42.272 problem, just it's- instead of zero or one, it's like: if you have spaces 00:15:42.272 --> 00:15:45.732 for four and a fifth one shows up, then you just Waker churn the whole 00:15:45.742 --> 00:15:48.442 chain, which is somehow even worse. 00:15:48.732 --> 00:15:52.012 Or if you over allocate it, you're wasting a bunch of static memory 00:15:52.012 --> 00:15:53.842 space that you could otherwise use. 00:15:54.262 --> 00:15:58.752 And you have to carry around this annoying `const N:usize` 00:15:58.772 --> 00:16:01.142 bound on everything that uses it. 00:16:02.441 --> 00:16:04.371 But the downside is it's a doubly linked list. 00:16:04.631 --> 00:16:08.421 So you get kind of all the downside of linked lists of: less pointer 00:16:08.421 --> 00:16:13.071 locality, access is a little bit more expensive, the code is more 00:16:13.111 --> 00:16:15.231 unsafe and challenging to use. 00:16:15.541 --> 00:16:19.681 But at least as a mitigation for here on embedded, we don't have like three 00:16:19.681 --> 00:16:24.011 levels of caches where a pointer lookup might be incredibly expensive because 00:16:24.011 --> 00:16:26.811 it's a cache miss, it's just part of RAM. 00:16:27.191 --> 00:16:31.851 It's just kind of the same as any other access on embedded, which is great. 00:16:32.571 --> 00:16:36.344 And we typically only access this linearly. 00:16:36.394 --> 00:16:39.254 For like a WaitQueue, you're always waking the first one, pulling the 00:16:39.254 --> 00:16:42.244 chain forward, grabbing the next one, pulling the chain forward. 00:16:42.254 --> 00:16:45.604 Or if you're removing yourself, you already have the two pointers, so 00:16:45.604 --> 00:16:47.274 you grab them and put them together. 00:16:47.274 --> 00:16:50.834 You're not really like trying to random access the link list, 00:16:50.834 --> 00:16:54.464 which is like the worst access pattern you can do on a link list. 00:16:54.821 --> 00:16:55.681 So that's WaitQueue. 00:16:56.011 --> 00:16:59.671 It's very neat and very flexible, especially on embedded. 00:17:00.936 --> 00:17:04.516 I'm reading code comments from `WaitQueue` as we're discussing this. 00:17:04.906 --> 00:17:09.796 And there's a very interesting comment saying, "This is kind of a bummer-" 00:17:10.111 --> 00:17:10.801 Oh, what part? 00:17:10.996 --> 00:17:13.246 "That we have to use a doubly-linked list." 00:17:14.136 --> 00:17:17.906 Because there's apparently very interesting singly-linked list domains. 00:17:17.926 --> 00:17:20.515 And there are lock-free doubly-linked lists, so you wouldn't have 00:17:20.515 --> 00:17:21.905 to have the mutex around it. 00:17:22.215 --> 00:17:27.255 But they rely on, "deferred reclamation schemes, such as hazard pointers or QSBR," 00:17:27.585 --> 00:17:30.055 both of which I'm hearing about for the first time, so I'm going to shut up. 00:17:30.065 --> 00:17:31.255 But it's an interesting comment. 00:17:32.010 --> 00:17:33.500 Have you ever heard of Vyukov? 00:17:33.690 --> 00:17:36.410 V Y U K O V? 00:17:36.855 --> 00:17:39.795 I, I, yes, because I just read the comment, but otherwise, no. 00:17:39.820 --> 00:17:44.070 Okay, he's a, he's a guy who's been doing high performance 00:17:44.070 --> 00:17:47.960 data structures and linked lists and particularly lockfree algorithms. 00:17:48.180 --> 00:17:52.847 So, for a very long time, maybe still, but a ton of high performance crates 00:17:52.847 --> 00:17:56.237 you've seen that use pointers and things like that or use linked lists: a lot 00:17:56.237 --> 00:18:00.187 of them are just using, you'll see mentions of like Vyukov's algorithm and 00:18:00.187 --> 00:18:02.927 he has a bunch of different ones, but he's had this blog, I think it's like 00:18:03.167 --> 00:18:08.587 1024cores.something he's written sort of the standard of so many of these. 00:18:08.587 --> 00:18:13.217 And actually mycelium uses one of those for its run queue. 00:18:13.487 --> 00:18:18.117 So when you have a singly linked list, and you want it to be lockfree, you 00:18:18.117 --> 00:18:22.777 can use this singly linked list, which means that you don't need a lock to 00:18:22.777 --> 00:18:25.077 append a task to the back of a queue. 00:18:25.357 --> 00:18:28.457 Because if you're always appending something to the back and always pulling 00:18:28.457 --> 00:18:33.537 from the front, you can actually get away with no mutex on that just using atomics. 00:18:33.737 --> 00:18:37.087 It's a little tricky and you have to be very careful, but there is like a 00:18:37.197 --> 00:18:42.117 well-defined and tested atomic algorithm that is likely to work with that. 00:18:42.527 --> 00:18:46.075 But the problem is when you need random access to the middle, you 00:18:46.075 --> 00:18:49.335 break that property, unfortunately, because if you had two threads... 00:18:49.777 --> 00:18:53.567 let's say, removing themselves at the exact same time or two tasks running 00:18:53.567 --> 00:18:57.157 on two different threads, removing themselves, they could race and 00:18:57.157 --> 00:19:01.626 essentially you have half the chain just floats off into space because they've done 00:19:01.626 --> 00:19:03.946 it incorrectly and detached the chain. 00:19:03.961 --> 00:19:04.871 Yeah, I see. 00:19:05.021 --> 00:19:05.611 I see what you mean. 00:19:05.856 --> 00:19:07.646 And I think the hazard pointer stuff is more like... 00:19:07.741 --> 00:19:12.661 kind of ref counted garbage collecty thing where you use heap allocations to do it 00:19:12.661 --> 00:19:14.321 in a way- I don't- I'm not entirely sure. 00:19:14.582 --> 00:19:19.069 But I think they're not generally applicable to a non-allocated environment. 00:19:19.839 --> 00:19:23.955 So then there's the third one: again, I'm a little biased because I wrote this one. 00:19:24.315 --> 00:19:27.640 But it's just the oddball weird one of the whole group. 00:19:27.640 --> 00:19:30.290 So like WaitCell and WaitQueue are essentially the building kit 00:19:30.300 --> 00:19:32.090 for building any async thing. 00:19:32.390 --> 00:19:38.200 If you are building a channel or a mutex or anything basically, even all the 00:19:38.200 --> 00:19:42.520 way down to hardware drivers, WaitCell and WaitQueue are essentially the two 00:19:42.800 --> 00:19:47.920 primitives that you need that you can turn anything into an async version of itself. 00:19:47.970 --> 00:19:53.570 Because once you have the thing that can do something, and some way to notify and 00:19:53.570 --> 00:19:59.070 wait for things, all of a sudden you now have an async version of that driver or 00:19:59.070 --> 00:20:01.010 library structure or anything like that. 00:20:01.750 --> 00:20:03.960 WaitMap is my fun oddball one. 00:20:04.240 --> 00:20:09.980 It's not really as fundamental as the other two, but it works quite a bit like 00:20:10.100 --> 00:20:15.960 WaitQueue in that it uses an intrusive doubly linked list, but instead of just 00:20:15.960 --> 00:20:18.860 storing the Waker in the task itself. 00:20:19.590 --> 00:20:22.725 It also stores a Key and a Value. 00:20:23.285 --> 00:20:27.525 So we have some Key of something that we're waiting for, and the 00:20:27.525 --> 00:20:32.315 Value is actually space to store the Value when that Value becomes ready. 00:20:32.815 --> 00:20:37.065 So before I described it as: the Waker doesn't really send any data. 00:20:37.185 --> 00:20:42.185 You just get a notification to go check the desk that your item might be ready. 00:20:42.805 --> 00:20:46.005 But that requires you to be woken up and then go check and 00:20:46.005 --> 00:20:47.025 see if your thing is there. 00:20:47.275 --> 00:20:51.095 Maybe say, like, "I'm waiting for message number whatever," and the 00:20:51.095 --> 00:20:53.355 data structure will say, "Yes, I have this message for you." 00:20:53.365 --> 00:20:55.475 It's- it's kind of extra work. 00:20:55.945 --> 00:20:59.345 WaitMap says: what if we did that all in one step? 00:21:00.425 --> 00:21:03.245 So let's say we had something like an async mailbox. 00:21:03.535 --> 00:21:06.841 We're sending requests out, that maybe have some specific 00:21:06.841 --> 00:21:08.051 sequence number with them. 00:21:08.791 --> 00:21:11.261 And we're waiting for responses to come back. 00:21:11.481 --> 00:21:15.491 So you say like: sequence number four goes out, sequence number five goes out, six, 00:21:15.491 --> 00:21:19.981 seven, eight, but they're not necessarily going to come back in the same order. 00:21:20.221 --> 00:21:24.142 They could come back out of order, but you always know the response will have 00:21:24.142 --> 00:21:26.582 the same sequence number as the request. 00:21:27.662 --> 00:21:32.792 So kind of like the WaitQueue, you tack yourself onto this doubly linked list. 00:21:33.182 --> 00:21:39.032 But we also know that next to the Waker, there is a Value that is the Key that 00:21:39.032 --> 00:21:40.932 is essentially what you are waiting for. 00:21:41.462 --> 00:21:43.532 And then there's space for the Value. 00:21:43.652 --> 00:21:47.652 So when you start, the Value is not there because you're waiting for it. 00:21:48.732 --> 00:21:52.912 And then what happens is when that item actually arrives- so the other side, like 00:21:52.912 --> 00:21:57.162 the mailbox is processing responses and it goes, "Ah, I got response number four. 00:21:57.372 --> 00:21:58.892 Let me look through my list. 00:21:59.082 --> 00:22:01.812 Ooh, here's someone who is waiting with the key of four. 00:22:02.242 --> 00:22:03.422 I have this response. 00:22:03.512 --> 00:22:06.232 I just shove the answer in their pocket. 00:22:06.632 --> 00:22:10.237 Then poke the waker and then throw them out of the list." 00:22:10.447 --> 00:22:12.607 So essentially it's kind of like a- have you ever heard the 00:22:12.607 --> 00:22:14.347 phrase 'putpocketing' before? 00:22:15.062 --> 00:22:15.772 I have not. 00:22:16.137 --> 00:22:17.817 It's the opposite of pickpocketing. 00:22:17.817 --> 00:22:19.917 So pickpocketing, you sneak up behind someone, you take 00:22:19.917 --> 00:22:21.477 something out of their pocket. 00:22:21.747 --> 00:22:25.107 Putpocketing is you sneak up to someone and put something into their pocket. 00:22:25.427 --> 00:22:30.767 So essentially, while the task is sitting there sleeping and waiting, the mailbox 00:22:30.767 --> 00:22:32.757 can go, "Ooh, you were looking for this." 00:22:33.047 --> 00:22:36.927 It puts the item in your pocket, boops you on the head so that you know that you're 00:22:36.927 --> 00:22:41.017 ready to wake up, and then removes you from the list of things that are waiting. 00:22:41.407 --> 00:22:48.467 It is perfectly designed for a bare metal async mailbox, which when I'm writing 00:22:48.467 --> 00:22:52.137 something like Postcard-RPC- where I have exactly this request response 00:22:52.167 --> 00:22:54.612 RPC pattern- it's exactly what I need. 00:22:54.662 --> 00:22:55.722 And this is why I wrote it. 00:22:56.422 --> 00:22:59.222 And it allows us to be very, very flexible because instead of having 00:22:59.222 --> 00:23:03.442 to have all of this storage where we have to like, because let's say 00:23:03.442 --> 00:23:05.012 we receive a couple of packets in. 00:23:05.542 --> 00:23:08.952 And then we've woken these tasks to tell them to come pick up their messages... 00:23:09.367 --> 00:23:12.304 but what if they get delayed and they don't come and pick it up 00:23:12.304 --> 00:23:14.254 quickly and I run out of space? 00:23:14.594 --> 00:23:17.344 If I don't have a heap, I'm bounded in the amount of space that I have. 00:23:17.544 --> 00:23:19.114 So what am I supposed to do with these messages? 00:23:19.114 --> 00:23:20.154 Do I just throw them away? 00:23:20.154 --> 00:23:23.004 And when they show up, then I say, "Sorry, I threw away your response. 00:23:23.004 --> 00:23:25.334 It got here, but I threw it away because you took too long..." 00:23:26.091 --> 00:23:31.561 So this allows us to basically say: as long as you can make a request, you have 00:23:31.561 --> 00:23:34.941 space for the response because everyone's bringing their own storage for it. 00:23:35.171 --> 00:23:38.001 Which works really well on embedded because we don't have to worry 00:23:38.001 --> 00:23:39.901 about perfectly sizing the bounds. 00:23:40.121 --> 00:23:43.301 We don't have to worry about what happens if someone takes too long, and 00:23:43.311 --> 00:23:48.321 even you can essentially cancel caring about the response because if the 00:23:48.351 --> 00:23:53.051 Future removes itself, then all of a sudden when that response comes in we'll 00:23:53.051 --> 00:23:54.561 go, "Is anyone waiting for this one? 00:23:54.661 --> 00:23:54.971 Nope." 00:23:55.041 --> 00:23:59.491 Okay, we just throw away the packet or we NAK the packet or whatever we need to. 00:23:59.901 --> 00:24:03.627 Essentially, this allows us to pretend like we have a bunch of oneshot 00:24:03.647 --> 00:24:07.467 channels, but without having to allocate space for those oneshot channels. 00:24:08.667 --> 00:24:14.047 It's interesting that this property that you like in `no_std` land 00:24:14.047 --> 00:24:21.247 that like essentially all the state gets folded down into this state machine 00:24:21.257 --> 00:24:24.857 that you carry on the stack, unless you explicitly put it on the heap, which you 00:24:24.857 --> 00:24:26.557 don't have one of in `no_std` land... 00:24:26.877 --> 00:24:28.037 is the bane a negative thing? 00:24:28.047 --> 00:24:28.357 Yes. 00:24:28.367 --> 00:24:30.457 It's the bane of web developers. 00:24:30.777 --> 00:24:34.267 Because they end up having enormous Futures and they're like, "Oops, 00:24:34.267 --> 00:24:37.277 we put like six megabytes on the stack just by calling this thing 00:24:37.277 --> 00:24:38.877 that just does one HTTP request." 00:24:39.147 --> 00:24:42.377 And then you have to box things on purpose just so the stack doesn't blow up. 00:24:42.398 --> 00:24:46.578 And there's no good tooling to determine like this async block, like how big, 00:24:46.588 --> 00:24:48.308 how big is it going to be once compiled? 00:24:48.308 --> 00:24:50.978 And of course it depends between debug and release. 00:24:51.148 --> 00:24:54.168 So it's interesting that this very, very annoying property, which is 00:24:54.328 --> 00:24:56.028 fundamental to how Rust async works. 00:24:56.038 --> 00:25:00.243 This time, this one is, is, you know, both annoying for high-level 00:25:00.263 --> 00:25:03.603 web code and really essential for low-level bare metal code. 00:25:04.413 --> 00:25:04.763 Yeah. 00:25:05.033 --> 00:25:08.133 And it's like you said, it's one of those things of scale that when 00:25:08.133 --> 00:25:10.373 you're waiting on one kind of thing... 00:25:10.838 --> 00:25:14.678 in moderation, it's fine, and it's reasonable and on embedded, you probably 00:25:14.678 --> 00:25:18.748 have moderation because you don't have much to go around anyway, so you're 00:25:18.748 --> 00:25:23.688 not gonna be boxing hundred kilobyte chunks of data or megabytes of data. 00:25:23.688 --> 00:25:27.445 You're like, "Well, I have my one space of 128 bytes that I'm gonna put my 00:25:27.445 --> 00:25:29.170 response in, and I'm excited about it!" 00:25:29.170 --> 00:25:32.690 Like, yeah, on embedded a lot of times we either statically allocate our tasks, 00:25:32.700 --> 00:25:37.606 so we go: look, there's only gonna ever be these five tasks existing, and 00:25:37.606 --> 00:25:39.866 we have them in statics, basically. 00:25:39.876 --> 00:25:41.496 So they are statically allocated. 00:25:41.816 --> 00:25:46.686 Or, like in MnemOS, my operating system, we do have an allocator, but we'll sort of 00:25:46.686 --> 00:25:50.866 just allocate all the tasks up front most of the time when we're creating drivers. 00:25:51.271 --> 00:25:54.551 And then they just live unbounded more or less. 00:25:54.571 --> 00:25:58.771 It's less dynamic usually than you would have on your desktop. 00:25:59.601 --> 00:26:02.771 But yeah, it's very flexible and we don't need a bunch of oneshot channels. 00:26:02.791 --> 00:26:06.261 But now the downside is again that it's a doubly linked list, but 00:26:06.261 --> 00:26:11.221 actually sometimes a little bit worse because this isn't a real hash map. 00:26:11.391 --> 00:26:16.501 We are linearly searching the doubly linked list for which waiter is ready. 00:26:16.591 --> 00:26:17.541 Right. 00:26:17.771 --> 00:26:22.521 Which for small Ns, which you probably will have on embedded is fine. 00:26:22.893 --> 00:26:26.731 Especially when the cost of following pointers isn't too expensive. 00:26:27.311 --> 00:26:33.461 On the desktop, you might want to not use a linked list for all the 00:26:33.461 --> 00:26:35.681 reasons that you might not want to use a linked list on desktop. 00:26:35.691 --> 00:26:38.871 But on desktop, you probably have a heap, and you probably could just 00:26:38.871 --> 00:26:44.011 use a real hash map of all of these items rather than a linear search. 00:26:44.011 --> 00:26:47.986 You could use the same intrusive trick for storage, But also on 00:26:47.986 --> 00:26:49.226 a desktop, you maybe just don't. 00:26:49.236 --> 00:26:52.446 You could just use a oneshot channel, and it wouldn't be a problem. 00:26:52.456 --> 00:26:56.326 So, this totally can work on desktop, but if you get to the point where you 00:26:56.326 --> 00:27:00.286 have, like, 2,000 in flight requests at the same time, you're going to have 00:27:00.286 --> 00:27:04.726 horrific performance, because you might have to search the entire 2,000 waiting 00:27:04.726 --> 00:27:08.836 tasks to figure out: Oh, no one was waiting for this response, and I just 00:27:08.836 --> 00:27:13.286 wasted a whole lot of time and cache busting walking this doubly linked list. 00:27:13.451 --> 00:27:16.961 Well, what if you have more tasks than is practical for a linear 00:27:16.961 --> 00:27:18.681 search, but still don't have a heap? 00:27:18.681 --> 00:27:21.851 Clearly the solution is to move from a doubly-linked list to some 00:27:21.851 --> 00:27:25.491 sort of tree data structure that is self-balancing, don't you think? 00:27:25.576 --> 00:27:29.106 I think cordyceps either has or is working on 00:27:29.106 --> 00:27:31.816 an intrusive tree as well. 00:27:32.076 --> 00:27:34.526 And I've thought about it, but it makes my brain hurt. 00:27:35.386 --> 00:27:39.276 I'm very lucky that Eliza wrote most of this code, especially cordyceps. 00:27:39.716 --> 00:27:42.686 And she is proficient in both Miri and loom. 00:27:42.886 --> 00:27:47.036 So Miri is sort of a runtime sanitizer that checks if you've 00:27:47.036 --> 00:27:48.975 done undefined behavior, basically. 00:27:48.996 --> 00:27:51.502 It is- it is worth noting that I wasn't serious. 00:27:51.542 --> 00:27:53.142 I was just trying to be annoying. 00:27:53.142 --> 00:27:54.242 Like, "Can you imagine?" 00:27:54.272 --> 00:27:56.522 And then the response being like, "Actually, Eliza's 00:27:56.562 --> 00:27:57.552 probably working on it." 00:27:57.572 --> 00:27:58.872 Is, is par for the course. 00:27:58.902 --> 00:27:59.762 It's what I would expect. 00:28:00.232 --> 00:28:03.747 We should have Eliza on as a guest just to explain 00:28:03.797 --> 00:28:07.697 cordyceps or intrusive linked list because they are tremendously 00:28:07.827 --> 00:28:10.407 useful and scary at the same time. 00:28:10.917 --> 00:28:11.117 Sure! 00:28:11.517 --> 00:28:13.377 But yeah, this is one of those things that, like 00:28:13.377 --> 00:28:15.047 I said, in moderation it's good. 00:28:15.237 --> 00:28:19.557 It gives you the kind of flexibility that feels unreasonable, but with a little 00:28:19.557 --> 00:28:24.087 knowledge of the Dark Arcane and how `Pin` works and how Futures work, you realize 00:28:24.107 --> 00:28:28.637 that all of a sudden, with a little bit of a stable pointer and `#[repr(C)]`, you can 00:28:28.637 --> 00:28:32.237 start doing the very spooky things that you'd like to be doing and get the kind 00:28:32.237 --> 00:28:34.107 of safe flexibility you'd like out of it. 00:28:34.852 --> 00:28:37.602 Speaking of `Pin`, I know this is, this is your outro 00:28:37.602 --> 00:28:40.872 and I'm ruining it, but Boats has a great article about it. 00:28:41.057 --> 00:28:43.407 It's really good and there's going to be a second part 00:28:43.407 --> 00:28:45.027 that I am also very excited about. 00:28:45.337 --> 00:28:45.767 Yes. 00:28:45.837 --> 00:28:47.347 And I'm going to link to it. 00:28:47.576 --> 00:28:48.266 Yes, please do. 00:28:48.266 --> 00:28:50.756 And this is actually, I caught myself because I was going to say, 00:28:50.786 --> 00:28:52.336 if something's pinned, it can't move. 00:28:52.376 --> 00:28:56.116 But that blog post explains exactly the point where that's not exactly 00:28:56.116 --> 00:29:01.333 true of `Pin` only has that property if the item is not unpinned. 00:29:01.623 --> 00:29:06.463 So if it cannot be unpinned before the end of the life cycle, but yes, 00:29:06.563 --> 00:29:08.383 that is a very, very good post. 00:29:08.383 --> 00:29:13.243 And `Pin` is one of those things that is very load bearing in the async world and 00:29:13.253 --> 00:29:18.683 also tremendously not well understood particularly by its critics and uh... 00:29:18.813 --> 00:29:24.453 it's a very neat thing but it is a weird sort of programming language theory brain 00:29:24.522 --> 00:29:27.054 topic which is unusual for a lot of Rust. 00:29:27.833 --> 00:29:32.333 Yeah, I, I have tried to explain `Pin`, in 2021. 00:29:32.333 --> 00:29:33.363 And... 00:29:33.793 --> 00:29:40.029 I wonder what will happen first, whether the majority of Rust users or consumers 00:29:40.059 --> 00:29:44.289 will understand `Pin` or whether we find a way to boot it out of the language. 00:29:44.369 --> 00:29:48.525 I'm, I'm genuinely curious because Boats announced an idea. 00:29:48.725 --> 00:29:51.135 So I'm excited about the idea as always. 00:29:56.648 --> 00:29:59.028 This episode is sponsored by the postcard crate. 00:29:59.388 --> 00:30:02.608 Postcard is gearing up for version 2.0 of the library and is looking 00:30:02.608 --> 00:30:03.938 for sponsors for this release. 00:30:04.508 --> 00:30:07.638 If your company uses postcard, you can help fund a portion of these efforts. 00:30:08.188 --> 00:30:12.108 Postcard is a compact binary wire format that is compatible with serde and 00:30:12.108 --> 00:30:15.508 allows devices big and small to quickly and efficiently serialize their data. 00:30:16.078 --> 00:30:19.278 Postcard is used widely in embedded Rust projects, as well as for projects 00:30:19.278 --> 00:30:21.898 like ICU4x, Bevy, and wasmtime. 00:30:22.079 --> 00:30:25.689 The 2.0 release is aimed at simplifying the library API while not changing 00:30:25.689 --> 00:30:27.799 the wire format, meaning postcard 1. 00:30:27.799 --> 00:30:31.629 0 and 2.0 are fully compatible when it comes to messages you send and receive. 00:30:31.969 --> 00:30:35.339 This version will also stabilize the Schema and MaxSize attributes, 00:30:35.539 --> 00:30:38.539 which are used by other crates in the postcard ecosystem like postcard-rpc. 00:30:38.948 --> 00:30:42.468 For more information about sponsoring Postcard Version 2.0, see the link in 00:30:42.468 --> 00:30:46.808 the show notes, or send an email to contact@onevariable.com to get in touch.