WEBVTT NOTE This file was generated by switchtitle 1 00:00:13.375 --> 00:00:15.375 This is Self-Directed Research! Our 2 00:00:15.375 --> 00:00:16.625 hosts, James and Amos, 3 00:00:16.791 --> 00:00:17.708 entertain each other with 4 00:00:17.708 --> 00:00:19.458 weekly hyper-focused technical deep 5 00:00:19.458 --> 00:00:21.750 dives. James closes out Season 2 with 6 00:00:21.750 --> 00:00:23.208 "Intrusive lists for fun 7 00:00:23.208 --> 00:00:24.916 and profit." We'll take a bit of a break 8 00:00:24.916 --> 00:00:26.083 before starting Season 3, 9 00:00:26.083 --> 00:00:27.166 but make sure to like, follow, 10 00:00:27.166 --> 00:00:28.625 and subscribe wherever you find us to 11 00:00:28.625 --> 00:00:29.750 stay up to date and visit 12 00:00:29.750 --> 00:00:31.833 sdr-podcast.com/episodes 13 00:00:31.833 --> 00:00:33.583 for all the presentations, videos, show 14 00:00:33.583 --> 00:00:35.375 notes, and transcripts. For your 15 00:00:35.375 --> 00:00:36.708 calendars, Self-Directed 16 00:00:36.708 --> 00:00:38.333 Research will be recording live October 17 00:00:38.333 --> 00:00:40.291 9th and 10th, 2025 at 18 00:00:40.291 --> 00:00:42.291 EuroRust. Hope to see you in Paris 19 00:00:42.500 --> 00:00:45.333 or online. Finally, thank you so much to 20 00:00:45.333 --> 00:00:47.333 Depot, the sponsor of this entire season. 21 00:00:47.666 --> 00:00:48.416 Hear more about them at 22 00:00:48.416 --> 00:00:49.333 the end of the episode. 23 00:00:53.666 --> 00:00:55.500 You have good taste, James. 24 00:00:55.791 --> 00:00:56.208 I'm surprised. 25 00:00:56.208 --> 00:00:57.083 Okay, we're gonna have to 26 00:00:57.083 --> 00:00:57.958 do it again because I... 27 00:00:58.833 --> 00:00:59.541 I'm surprised? 28 00:00:59.791 --> 00:01:00.750 Of course I'm surprised. 29 00:01:01.291 --> 00:01:02.791 Damn, that was a compliment until the 30 00:01:02.791 --> 00:01:04.750 last second stab in the back. 31 00:01:05.333 --> 00:01:06.208 Negging is a sport. 32 00:01:06.583 --> 00:01:08.708 Just don't do it to the people you're 33 00:01:08.708 --> 00:01:10.125 pursuing romantically. 34 00:01:10.750 --> 00:01:11.541 Just do it to your friends. 35 00:01:11.958 --> 00:01:13.000 Unless they're into it. 36 00:01:13.041 --> 00:01:13.625 We're not. 37 00:01:13.666 --> 00:01:13.875 Bye. 38 00:01:14.208 --> 00:01:15.833 Should we just cancel the recording? 39 00:01:15.875 --> 00:01:16.291 Bye, Amanda. 40 00:01:16.916 --> 00:01:18.083 No, we gotta get this one done. 41 00:01:18.125 --> 00:01:20.041 I know, but how do you get our collective 42 00:01:20.041 --> 00:01:20.958 minds out of the gutter? 43 00:01:21.458 --> 00:01:22.666 Um, um, linked lists. 44 00:01:23.500 --> 00:01:23.666 Surprise. 45 00:01:24.000 --> 00:01:25.833 So James, what do you have for us today? 46 00:01:26.125 --> 00:01:27.916 Okay, starting with a different word. 47 00:01:28.208 --> 00:01:29.000 We're gonna go over 48 00:01:29.000 --> 00:01:30.583 intrusive lists for fun and profit. 49 00:01:31.083 --> 00:01:32.041 Mostly on embedded, 50 00:01:32.041 --> 00:01:33.500 not entirely on embedded. 51 00:01:33.500 --> 00:01:35.000 All of this kind of works everywhere, but 52 00:01:35.000 --> 00:01:36.333 some of the things where I say it works 53 00:01:36.333 --> 00:01:38.750 really well are specifically on embedded. 54 00:01:38.750 --> 00:01:40.041 But, uh, Amos, do you remember what 55 00:01:40.041 --> 00:01:41.250 intrusive linked lists are? 56 00:01:41.250 --> 00:01:41.583 I do. 57 00:01:41.916 --> 00:01:43.666 It's when the data... 58 00:01:44.000 --> 00:01:45.875 No, the list, it's when the 59 00:01:45.875 --> 00:01:47.583 data is next to the point... 60 00:01:47.583 --> 00:01:48.875 No, it's no pointer. 61 00:01:49.333 --> 00:01:50.083 It's when the pointer is 62 00:01:50.083 --> 00:01:51.416 part of the data, the elements? 63 00:01:51.833 --> 00:01:52.583 Something like that. 64 00:01:52.583 --> 00:01:54.541 It's good for cache locality, okay? 65 00:01:54.541 --> 00:01:55.333 That's what I know. 66 00:01:55.375 --> 00:01:56.000 That is true. 67 00:01:56.000 --> 00:01:57.333 So we touched on this a little bit in 68 00:01:57.333 --> 00:01:58.416 "What are you syncing about?" 69 00:01:58.416 --> 00:02:00.166 Cause we talked about intrusive linked 70 00:02:00.166 --> 00:02:01.791 lists being used in 71 00:02:01.791 --> 00:02:03.291 async await executors. 72 00:02:03.541 --> 00:02:05.708 We talked about it being used in things 73 00:02:05.708 --> 00:02:07.708 like wakers, where you want to have a 74 00:02:07.708 --> 00:02:10.000 bunch of things waiting on one task. 75 00:02:10.541 --> 00:02:12.708 But we'll do the quick concept reminder. 76 00:02:13.166 --> 00:02:15.416 So classic linked lists, kind of the 77 00:02:15.416 --> 00:02:16.500 opposite of what you said. 78 00:02:16.708 --> 00:02:17.583 They have separate 79 00:02:17.583 --> 00:02:19.250 allocations for the node. 80 00:02:19.250 --> 00:02:20.666 So the thing that actually gets chained 81 00:02:20.666 --> 00:02:21.791 into the linked list. 82 00:02:22.208 --> 00:02:23.333 So we're talking about 83 00:02:23.333 --> 00:02:24.833 doubly linked lists right now. 84 00:02:25.000 --> 00:02:27.208 So each node points to someone in front 85 00:02:27.208 --> 00:02:29.041 of them and someone behind them or left 86 00:02:29.041 --> 00:02:30.666 or right or however you want to call it. 87 00:02:30.958 --> 00:02:31.625 But then each node 88 00:02:31.625 --> 00:02:32.958 also points to its data. 89 00:02:33.333 --> 00:02:35.625 So you've got this unbroken chain of 90 00:02:35.625 --> 00:02:37.083 nodes and each of them 91 00:02:37.083 --> 00:02:39.041 point to one piece of data. 92 00:02:39.291 --> 00:02:41.041 Right, and if you're a visual person, you 93 00:02:41.041 --> 00:02:41.958 can look at the slides 94 00:02:41.958 --> 00:02:43.125 that we have for this episode. 95 00:02:43.125 --> 00:02:44.291 Cause this podcast has slides. 96 00:02:44.500 --> 00:02:46.791 You can find them on sdr-podcast.com/ 97 00:02:46.791 --> 00:02:51.375 episodes or on YouTube or on Spotify. 98 00:02:51.875 --> 00:02:52.625 Yeah, I got to figure out. 99 00:02:53.000 --> 00:02:55.041 I don't think Apple has video podcasts. 100 00:02:55.041 --> 00:02:56.666 I think they might have like some fancy 101 00:02:56.666 --> 00:02:58.833 M4A format where we can embed stuff, but 102 00:02:58.833 --> 00:02:59.833 I haven't looked at that and I'm probably 103 00:02:59.833 --> 00:03:00.958 not going to this season. 104 00:03:00.958 --> 00:03:01.583 Maybe that's a season 105 00:03:01.583 --> 00:03:03.083 three thing, probably not. 106 00:03:03.083 --> 00:03:04.625 Maybe it's only for premium podcasts. 107 00:03:05.083 --> 00:03:05.708 Ooh, that's true. 108 00:03:06.000 --> 00:03:07.041 I'm on it, don't worry. 109 00:03:07.750 --> 00:03:08.916 For in between 110 00:03:08.916 --> 00:03:10.250 seasons, I will look into it. 111 00:03:10.791 --> 00:03:13.333 Right, whereas intrusive linked lists do 112 00:03:13.333 --> 00:03:14.583 something slightly different. 113 00:03:14.958 --> 00:03:17.916 They put a header inside of the data. 114 00:03:17.916 --> 00:03:20.166 So they kind of co-locate the linked list 115 00:03:20.166 --> 00:03:21.875 header and the data together. 116 00:03:22.125 --> 00:03:23.250 And so you don't have 117 00:03:23.250 --> 00:03:24.625 two allocations per thing. 118 00:03:24.916 --> 00:03:26.708 You just have one allocation of two 119 00:03:26.708 --> 00:03:28.916 things instead of two allocations of one 120 00:03:28.916 --> 00:03:30.250 thing, if that makes sense. 121 00:03:30.625 --> 00:03:32.958 The downside for the classic mode, like 122 00:03:32.958 --> 00:03:34.500 you said, for cache locality, you got to 123 00:03:34.500 --> 00:03:36.000 follow twice as many pointers. 124 00:03:36.000 --> 00:03:37.250 That means more cache misses. 125 00:03:37.250 --> 00:03:38.416 You've got to do two allocations. 126 00:03:39.125 --> 00:03:40.625 Allocators take some time to do things. 127 00:03:41.041 --> 00:03:42.958 So the downside with the classic flavor 128 00:03:43.333 --> 00:03:44.791 is that you have to do two allocations 129 00:03:44.791 --> 00:03:47.250 for every node and follow twice as many 130 00:03:47.250 --> 00:03:48.583 pointers for every node, 131 00:03:48.583 --> 00:03:50.000 which is kind of a bummer. 132 00:03:50.500 --> 00:03:52.166 But the classic upside is that items can 133 00:03:52.166 --> 00:03:53.583 exist in multiple lists. 134 00:03:53.583 --> 00:03:55.166 So if you do have those separate, 135 00:03:55.541 --> 00:03:57.375 especially if you're doing something 136 00:03:57.375 --> 00:03:59.375 Java-y, where you might want to have like 137 00:03:59.375 --> 00:04:02.000 a, you know, not duplicated list of 138 00:04:02.000 --> 00:04:03.666 strings, and you can have multiple things 139 00:04:03.666 --> 00:04:05.125 pointed to them and they're ref counted or 140 00:04:05.125 --> 00:04:06.958 something, you can maybe do this. 141 00:04:07.333 --> 00:04:09.125 But in intrusive linked lists, you 142 00:04:09.125 --> 00:04:10.125 totally can't do that. 143 00:04:10.583 --> 00:04:12.333 But for a lot of cases, that's not 144 00:04:12.333 --> 00:04:13.833 actually a problem, especially if you 145 00:04:13.833 --> 00:04:16.041 care about things like tasks waiting in a 146 00:04:16.041 --> 00:04:17.625 list instead of, hey, I want to 147 00:04:17.625 --> 00:04:19.666 deduplicate all of the JSON that I've 148 00:04:19.666 --> 00:04:21.875 received in individual strings or 149 00:04:21.875 --> 00:04:22.833 something like that. 150 00:04:22.875 --> 00:04:23.291 Right, right. 151 00:04:23.291 --> 00:04:26.541 So with multiple nodes pointing the same 152 00:04:26.541 --> 00:04:28.208 data, in Java that's easy 153 00:04:28.208 --> 00:04:29.041 because it's garbage collected. 154 00:04:29.500 --> 00:04:31.083 So it's just references, right? 155 00:04:31.083 --> 00:04:32.666 And the GC takes care of it. 156 00:04:32.875 --> 00:04:34.708 And Rust would be arcs or 157 00:04:34.708 --> 00:04:36.666 Weaks or RCs or it depends, 158 00:04:36.916 --> 00:04:37.791 Something like that. 159 00:04:38.208 --> 00:04:40.666 Yeah, you'd want arc or ref count or some 160 00:04:40.666 --> 00:04:42.333 people are trying to make GC types, but 161 00:04:42.333 --> 00:04:43.666 you need something to make sure that that 162 00:04:43.666 --> 00:04:45.166 data eventually goes away 163 00:04:45.166 --> 00:04:46.583 when nothing's pointing to it. 164 00:04:46.833 --> 00:04:48.083 And similarly, it doesn't 165 00:04:48.083 --> 00:04:50.333 go away until that point. 166 00:04:50.375 --> 00:04:51.916 I just think they should make a Rust 2 167 00:04:51.916 --> 00:04:53.916 and bring back the GC because Rust used 168 00:04:53.916 --> 00:04:55.000 to have garbage collection. 169 00:04:56.000 --> 00:04:57.750 I love this fact so much. 170 00:04:58.125 --> 00:04:59.458 Yeah, it had GC, it 171 00:04:59.458 --> 00:05:01.208 had actor model-y stuff. 172 00:05:01.458 --> 00:05:02.791 It was a squishy 173 00:05:02.791 --> 00:05:04.208 language for a very long time. 174 00:05:04.458 --> 00:05:05.791 But I've been told 175 00:05:05.791 --> 00:05:07.125 linked lists are bad, right? 176 00:05:07.125 --> 00:05:10.333 There's a whole bunch of writings in Rust 177 00:05:10.333 --> 00:05:11.708 that say linked lists are bad. 178 00:05:11.708 --> 00:05:13.583 You should use something with more direct 179 00:05:13.583 --> 00:05:15.291 locality, something like a vec because 180 00:05:15.291 --> 00:05:17.583 you go, hey, my processor has a cache and 181 00:05:17.583 --> 00:05:18.333 it loves running 182 00:05:18.333 --> 00:05:19.708 through linear address space. 183 00:05:20.000 --> 00:05:21.666 So running down a vec, even though it 184 00:05:21.666 --> 00:05:23.250 feels like it should be slower, a lot of 185 00:05:23.250 --> 00:05:25.750 times isn't actually much slower and it 186 00:05:25.750 --> 00:05:27.333 makes a lot of things much, much easier. 187 00:05:27.541 --> 00:05:29.583 But ha ha, we're doing embedded systems 188 00:05:29.916 --> 00:05:32.083 and it turns out that these factors sort 189 00:05:32.083 --> 00:05:33.708 of get flipped on their head for embedded 190 00:05:33.708 --> 00:05:34.875 systems because we care 191 00:05:34.875 --> 00:05:36.375 about slightly different things. 192 00:05:36.708 --> 00:05:37.416 Oh, right, right, right. 193 00:05:37.458 --> 00:05:39.000 Yeah, you can't have a cache miss if you 194 00:05:39.000 --> 00:05:39.916 don't have any cache. 195 00:05:39.916 --> 00:05:42.333 If all of your RAM in your processor is 196 00:05:42.333 --> 00:05:44.250 basically L1 cache, which is how most 197 00:05:44.250 --> 00:05:46.000 microcontrollers work, they have SRAM 198 00:05:46.000 --> 00:05:47.833 instead of DRAM, which means there's 199 00:05:47.833 --> 00:05:49.750 never far to go for your memory from the 200 00:05:49.750 --> 00:05:52.000 processor, which means that following a 201 00:05:52.000 --> 00:05:53.875 linked list is actually just as fast as a 202 00:05:53.875 --> 00:05:55.541 linear for loop because it's just 203 00:05:55.541 --> 00:05:57.416 changing the pointer and dereferencing 204 00:05:57.416 --> 00:05:58.750 it, which takes the same number of 205 00:05:58.750 --> 00:06:00.291 cycles, whether you're going from here to 206 00:06:00.291 --> 00:06:02.041 here: okay, I'm pointing for the 207 00:06:02.041 --> 00:06:03.416 audience, from here to here means very 208 00:06:03.416 --> 00:06:04.500 close, and from here to 209 00:06:04.500 --> 00:06:05.833 there means very far away. 210 00:06:05.833 --> 00:06:07.000 Doesn't really matter, it's still a 211 00:06:07.000 --> 00:06:08.458 pointer load and so it doesn't matter. 212 00:06:08.500 --> 00:06:10.958 So when's the last time like desktop CPUs 213 00:06:11.625 --> 00:06:13.916 cared more about instruction counts than 214 00:06:13.916 --> 00:06:15.208 they did about cache locality? 215 00:06:15.958 --> 00:06:18.541 It's at least 10 years, right? 216 00:06:18.916 --> 00:06:21.000 A long, oh, more than 10 years, 20 years? 217 00:06:21.375 --> 00:06:23.000 I mean, you'd have to go back to like-- 218 00:06:23.041 --> 00:06:23.791 Are we that old? 219 00:06:23.833 --> 00:06:25.416 Yeah, you'd have to go back to like early 220 00:06:25.416 --> 00:06:27.000 90s, late 80s maybe, 221 00:06:27.333 --> 00:06:28.916 like it's a long time. 222 00:06:28.916 --> 00:06:29.875 This is one of those things that 223 00:06:29.875 --> 00:06:31.791 microcontrollers are running into today. 224 00:06:32.125 --> 00:06:33.000 So there's two main 225 00:06:33.000 --> 00:06:33.958 kinds of memory that we use. 226 00:06:33.958 --> 00:06:35.250 This is an aside that we don't need to go 227 00:06:35.250 --> 00:06:36.375 into, but I'll be quick. 228 00:06:36.625 --> 00:06:37.625 There's two main kinds of memory. 229 00:06:37.625 --> 00:06:38.791 There's SRAM or static 230 00:06:38.791 --> 00:06:40.833 RAM and DRAM or dynamic RAM. 231 00:06:41.333 --> 00:06:44.208 Static RAM uses way less power, but is 232 00:06:44.208 --> 00:06:46.041 physically larger on silicon. 233 00:06:46.541 --> 00:06:48.791 And so microcontrollers use just SRAM 234 00:06:49.208 --> 00:06:52.208 because it's lower power and when we have 235 00:06:52.208 --> 00:06:52.833 little low power 236 00:06:52.833 --> 00:06:54.625 devices, we want it to be there. 237 00:06:54.625 --> 00:06:56.166 The problem is it's physically large. 238 00:06:56.166 --> 00:06:57.791 So at some point, getting more SRAM 239 00:06:57.791 --> 00:06:59.250 closer to your processor is just 240 00:06:59.250 --> 00:07:01.416 physically difficult and also 241 00:07:01.416 --> 00:07:02.458 just takes up a lot of space. 242 00:07:02.458 --> 00:07:03.458 So your microcontrollers, 243 00:07:03.458 --> 00:07:04.750 your processors get much bigger. 244 00:07:05.250 --> 00:07:08.083 So most things for bulk memory tend to 245 00:07:08.083 --> 00:07:09.458 use DRAM, which is what 246 00:07:09.458 --> 00:07:11.291 you're like DDR memory is using. 247 00:07:11.541 --> 00:07:13.625 The problem is that uses a ton more 248 00:07:13.625 --> 00:07:15.166 power, but you can fit way 249 00:07:15.166 --> 00:07:16.416 more in a smaller package. 250 00:07:16.833 --> 00:07:19.083 So most desktop processors these days 251 00:07:19.500 --> 00:07:21.958 have a little puddle of SRAM close to the 252 00:07:21.958 --> 00:07:22.833 processor and we call 253 00:07:22.833 --> 00:07:24.500 that L1, L2, L3 cache. 254 00:07:24.833 --> 00:07:26.125 And then we have a big 255 00:07:26.125 --> 00:07:28.333 bulk DRAM further away. 256 00:07:28.333 --> 00:07:29.958 And this is your main memory or your 257 00:07:29.958 --> 00:07:34.041 DDR3, four or five LPDDR, whatever, that 258 00:07:34.041 --> 00:07:35.583 holds a lot of storage, 259 00:07:35.583 --> 00:07:37.000 but is kind of further away. 260 00:07:37.000 --> 00:07:38.541 It's the storage unit at the end of the 261 00:07:38.541 --> 00:07:40.750 block rather than right in your pocket. 262 00:07:41.083 --> 00:07:42.708 But this is why we avoid linked lists a 263 00:07:42.708 --> 00:07:44.416 lot of times because if you're jumping 264 00:07:44.416 --> 00:07:47.000 through hoops in linked lists and you end 265 00:07:47.000 --> 00:07:49.000 up having to go to that storage facility 266 00:07:49.000 --> 00:07:50.500 at the end of the street instead of what 267 00:07:50.500 --> 00:07:51.208 happens to be in your 268 00:07:51.208 --> 00:07:53.250 pocket, it slows you way down. 269 00:07:53.250 --> 00:07:55.291 Whereas if you were smart with linear 270 00:07:55.291 --> 00:07:57.791 operation in a vec your processor is 271 00:07:57.791 --> 00:07:59.041 gonna be smart and go, "Hey, you're 272 00:07:59.041 --> 00:08:00.958 running this direction in memory. 273 00:08:01.333 --> 00:08:03.083 Let me just go pull the whole pallet out 274 00:08:03.083 --> 00:08:04.708 of storage and pull the 275 00:08:04.708 --> 00:08:05.708 whole thing in at once." 276 00:08:05.958 --> 00:08:07.958 And that way, if you keep going in a 277 00:08:07.958 --> 00:08:09.750 linear order, we're already gonna have 278 00:08:09.750 --> 00:08:10.833 the thing that you need. 279 00:08:10.833 --> 00:08:11.875 So linear iteration is 280 00:08:11.875 --> 00:08:13.416 great on desktop processors. 281 00:08:13.416 --> 00:08:15.333 But like I said, when you're made up of 282 00:08:15.333 --> 00:08:17.166 nothing but pockets on microcontrollers, 283 00:08:17.416 --> 00:08:18.208 then it doesn't cost 284 00:08:18.208 --> 00:08:19.250 anything to jump around. 285 00:08:19.541 --> 00:08:20.583 And so we get to do this 286 00:08:20.583 --> 00:08:21.875 for basically for free. 287 00:08:21.875 --> 00:08:22.875 Mhm,mhm. 288 00:08:22.875 --> 00:08:24.458 I like this because coding 289 00:08:24.458 --> 00:08:28.500 like it's 1987 or something, 290 00:08:30.458 --> 00:08:33.000 is nice because you can beat compilers. 291 00:08:33.000 --> 00:08:34.750 It makes a lot of sense to write 292 00:08:34.750 --> 00:08:37.416 assembly, not just to take advantage of 293 00:08:37.416 --> 00:08:38.500 newer instruction sets and 294 00:08:38.500 --> 00:08:39.708 do SIMD and stuff like that. 295 00:08:39.791 --> 00:08:40.833 You have to be clever. 296 00:08:41.166 --> 00:08:42.791 Like there's a whole lot of stuff that we 297 00:08:42.791 --> 00:08:44.500 lost, a lot of art because 298 00:08:44.500 --> 00:08:45.750 computers got fast enough. 299 00:08:46.166 --> 00:08:47.708 So I guess if you miss those days, you 300 00:08:47.708 --> 00:08:48.625 can just go work in embedded. 301 00:08:49.000 --> 00:08:50.375 For a while, but it's starting to get to 302 00:08:50.375 --> 00:08:51.750 the point where we have external memory 303 00:08:51.750 --> 00:08:53.583 because at some point, this is one of 304 00:08:53.583 --> 00:08:55.041 those funny things about microcontrollers 305 00:08:55.041 --> 00:08:58.291 today versus like 1990s desktops. 306 00:08:58.500 --> 00:09:00.166 The processors are about the same. 307 00:09:00.166 --> 00:09:01.875 If anything, microcontrollers have way 308 00:09:01.875 --> 00:09:04.166 faster processors these days, but 309 00:09:04.166 --> 00:09:06.250 microcontrollers don't have as much 310 00:09:06.250 --> 00:09:09.041 memory as desktop systems in the 90s had. 311 00:09:09.541 --> 00:09:12.083 A desktop system like an Apple in 1990, 312 00:09:12.416 --> 00:09:13.875 would have probably had like a 16 313 00:09:13.875 --> 00:09:15.333 megahertz processor, but it probably 314 00:09:15.333 --> 00:09:17.166 would have had a couple megabytes of RAM. 315 00:09:17.708 --> 00:09:19.208 Whereas today's microcontrollers are like 316 00:09:19.291 --> 00:09:22.708 single or dual core, 100 megahertz, 32 bit 317 00:09:22.708 --> 00:09:25.416 processors, but they still only have 500K 318 00:09:25.416 --> 00:09:27.750 of RAM because they don't have DRAM 319 00:09:27.750 --> 00:09:28.708 sitting next to them. 320 00:09:28.708 --> 00:09:30.291 But now we start to want it. 321 00:09:30.458 --> 00:09:32.541 So now ESP32s and some other ones are 322 00:09:32.541 --> 00:09:34.250 starting to add DRAM next to it because 323 00:09:34.250 --> 00:09:36.666 you wanna have an eight or a 16 megabyte 324 00:09:36.666 --> 00:09:38.416 buffer for audio samples or 325 00:09:38.416 --> 00:09:39.500 video and things like that. 326 00:09:39.750 --> 00:09:41.583 So in 10 years, some of this will also be 327 00:09:41.583 --> 00:09:43.083 a little out of date because most of the 328 00:09:43.083 --> 00:09:44.208 like, at least the high end 329 00:09:44.208 --> 00:09:45.625 microcontrollers that you'd wanna run 330 00:09:45.625 --> 00:09:47.250 displays or audio on will 331 00:09:47.250 --> 00:09:48.875 have DRAM and things like that. 332 00:09:48.875 --> 00:09:49.875 So you start having to care about 333 00:09:49.875 --> 00:09:51.916 locality again, but we'll get there. 334 00:09:52.250 --> 00:09:52.458 Right. 335 00:09:52.583 --> 00:09:54.666 And so this is what, like this is just 336 00:09:54.666 --> 00:09:56.166 different set of constraints and this is 337 00:09:56.166 --> 00:09:58.333 what -os like optimized 338 00:09:58.333 --> 00:10:00.500 for size is for, or -oz even. 339 00:10:00.750 --> 00:10:02.333 So that kind of scenario you think? 340 00:10:02.666 --> 00:10:03.583 It depends. 341 00:10:04.250 --> 00:10:07.750 So optimization settings changes how your 342 00:10:07.750 --> 00:10:10.333 actual executable code is compiled. 343 00:10:10.791 --> 00:10:12.958 So sometimes having smaller code makes it 344 00:10:12.958 --> 00:10:14.708 go faster than higher optimizations 345 00:10:15.000 --> 00:10:15.958 because just having less 346 00:10:15.958 --> 00:10:18.708 load means that it runs faster. 347 00:10:18.708 --> 00:10:19.750 But we're mostly 348 00:10:19.750 --> 00:10:21.291 talking about memory now. 349 00:10:21.291 --> 00:10:22.291 So for the linked lists, we're talking 350 00:10:22.291 --> 00:10:24.250 about things in memory and compiler 351 00:10:24.250 --> 00:10:26.916 optimizations mostly apply to the code 352 00:10:26.916 --> 00:10:28.375 size and things like that. 353 00:10:28.416 --> 00:10:28.708 Wait, because -- 354 00:10:28.708 --> 00:10:30.083 The compiler doesn't really know about 355 00:10:30.083 --> 00:10:31.208 cache most of the time. 356 00:10:31.250 --> 00:10:33.083 The code would be in a ROM, which is 357 00:10:33.083 --> 00:10:34.083 different from SRAM? 358 00:10:34.458 --> 00:10:36.083 Like SRAM is just working memory? 359 00:10:36.416 --> 00:10:37.041 Yes. 360 00:10:37.625 --> 00:10:37.958 Yes. 361 00:10:38.250 --> 00:10:40.125 But also on a microcontroller's code can 362 00:10:40.125 --> 00:10:42.625 sometimes be-- okay, I'll try and keep 363 00:10:42.625 --> 00:10:44.083 this self-contained because maybe we'll 364 00:10:44.083 --> 00:10:45.500 cut this, because it's a whole aside. 365 00:10:46.500 --> 00:10:48.500 So code is stored on microcontrollers. 366 00:10:49.000 --> 00:10:51.875 Often it's on the chip itself in flash. 367 00:10:51.875 --> 00:10:52.958 So this is one of the other cool things 368 00:10:52.958 --> 00:10:54.625 about microcontrollers is they have all 369 00:10:54.625 --> 00:10:56.791 of their hard drive, CPU and RAM in one 370 00:10:56.791 --> 00:10:58.208 chip, but this is also physically 371 00:10:58.208 --> 00:11:00.708 limiting because on-chip flash is also 372 00:11:00.708 --> 00:11:03.041 large, which means that fitting more into 373 00:11:03.041 --> 00:11:04.166 the same package means the 374 00:11:04.166 --> 00:11:05.125 package has to be bigger. 375 00:11:05.500 --> 00:11:07.291 And the problem is if you make it in the 376 00:11:07.291 --> 00:11:08.708 chip, then you have to sell all the 377 00:11:08.708 --> 00:11:10.083 different varieties because people want a 378 00:11:10.083 --> 00:11:11.333 cheaper one because they go, "I don't 379 00:11:11.333 --> 00:11:12.208 need that much flash. 380 00:11:12.583 --> 00:11:13.875 So I want to save some money. 381 00:11:13.875 --> 00:11:15.333 So I want a smaller one," but then you 382 00:11:15.333 --> 00:11:17.416 have to ship 10 kinds of processors with 383 00:11:17.416 --> 00:11:19.000 different hard drive sizes because it's 384 00:11:19.000 --> 00:11:20.208 kind of like a MacBook. 385 00:11:20.500 --> 00:11:22.541 It's all soldered onto the same chip. 386 00:11:23.291 --> 00:11:24.583 But these days, a lot of 387 00:11:24.583 --> 00:11:25.916 microcontrollers, it's getting more 388 00:11:25.916 --> 00:11:27.458 popular to have external flash. 389 00:11:28.041 --> 00:11:29.416 And this has the same kind of things as 390 00:11:29.416 --> 00:11:31.541 like external hard drives where internal 391 00:11:31.541 --> 00:11:33.625 flash might only have like a slight 392 00:11:33.625 --> 00:11:35.458 penalty for access and you might have 393 00:11:35.458 --> 00:11:36.833 cache as long as you're accessing 394 00:11:36.833 --> 00:11:38.750 linearly, it goes fairly well. 395 00:11:39.083 --> 00:11:40.791 Versus when you have external memory, 396 00:11:40.791 --> 00:11:42.500 there's higher latency on that. 397 00:11:42.500 --> 00:11:44.500 So you can have bigger bulk storage, but 398 00:11:44.500 --> 00:11:45.541 it might have higher latency. 399 00:11:46.208 --> 00:11:48.583 So again, this is like, not only do we 400 00:11:48.583 --> 00:11:51.208 have cache access penalties for RAM, we 401 00:11:51.208 --> 00:11:51.875 also have cache 402 00:11:51.875 --> 00:11:53.333 access penalties for flash. 403 00:11:53.583 --> 00:11:54.916 And if you're doing something hard real 404 00:11:54.916 --> 00:11:56.708 time, a lot of times you'll just load 405 00:11:56.708 --> 00:11:57.958 your whole program into RAM. 406 00:11:58.416 --> 00:12:00.625 So you never have to pay for flash access 407 00:12:00.625 --> 00:12:01.833 penalties if you care about like 408 00:12:01.833 --> 00:12:03.291 deterministic CPU 409 00:12:03.291 --> 00:12:04.500 counts and things like that. 410 00:12:04.500 --> 00:12:05.000 Yeah, that's what I 411 00:12:05.000 --> 00:12:05.833 was thinking of, yeah. 412 00:12:06.291 --> 00:12:08.500 Yeah, but yeah, it all matters like this. 413 00:12:08.500 --> 00:12:09.958 But specifically for linked lists we're 414 00:12:09.958 --> 00:12:10.791 talking about just 415 00:12:10.791 --> 00:12:11.916 the RAM side of things. 416 00:12:11.916 --> 00:12:13.833 So less about processor optimizations. 417 00:12:14.375 --> 00:12:16.291 So in the world of embedded, because the 418 00:12:16.291 --> 00:12:18.000 physical size of the chip matters, you 419 00:12:18.000 --> 00:12:19.916 can't do what they do in the desktop 420 00:12:19.916 --> 00:12:22.000 world, which is manufacture the same 421 00:12:22.000 --> 00:12:24.625 chip, but disable some of it for cheaper 422 00:12:24.625 --> 00:12:26.791 models or like do binning and like, those 423 00:12:26.791 --> 00:12:27.875 are a little bit damaged. 424 00:12:27.916 --> 00:12:28.958 Like you just disabled that. 425 00:12:29.000 --> 00:12:29.666 They do it too. 426 00:12:30.000 --> 00:12:30.500 Yeah, no, no, micro 427 00:12:30.500 --> 00:12:31.458 controllers do that too. 428 00:12:31.666 --> 00:12:33.250 But I mean, there's just some limit of 429 00:12:33.250 --> 00:12:35.791 even in the best bin, like the physical 430 00:12:35.791 --> 00:12:37.666 size or the amount of power that you need 431 00:12:37.666 --> 00:12:39.416 to use to keep your hard drive or keep 432 00:12:39.416 --> 00:12:41.916 your memory online, because it costs 433 00:12:41.916 --> 00:12:43.500 things, just gets too high. 434 00:12:43.750 --> 00:12:45.500 So even the biggest model, the best bin 435 00:12:45.500 --> 00:12:47.250 where everything worked, it just becomes 436 00:12:47.250 --> 00:12:49.833 too physically large or too, it increases 437 00:12:49.833 --> 00:12:51.791 your baseline power usage too high. 438 00:12:52.083 --> 00:12:53.750 And that becomes problematic either for 439 00:12:53.750 --> 00:12:54.916 heat or for battery life 440 00:12:54.916 --> 00:12:55.791 or something like that. 441 00:12:56.125 --> 00:12:57.708 So embedded is hard to generalize because 442 00:12:57.708 --> 00:12:59.000 different people care about stuff. 443 00:12:59.000 --> 00:13:00.333 Some embedded systems are plugged into a 444 00:13:00.333 --> 00:13:01.333 wall and don't care. 445 00:13:01.583 --> 00:13:03.000 Some embedded systems run on a tiny 446 00:13:03.000 --> 00:13:04.833 battery that need to run for five years. 447 00:13:05.333 --> 00:13:06.041 And so they have different 448 00:13:06.041 --> 00:13:07.083 optimization constraints. 449 00:13:07.083 --> 00:13:09.291 So it's hard to ever totally generalize 450 00:13:09.291 --> 00:13:10.041 for micro controllers. 451 00:13:10.500 --> 00:13:12.333 If you think shipping for desktop Linux 452 00:13:12.333 --> 00:13:15.500 is hard, just wait until you do embedded. 453 00:13:15.625 --> 00:13:17.000 Embedded systems is fun because your 454 00:13:17.000 --> 00:13:18.541 application is the operating system, 455 00:13:18.541 --> 00:13:19.833 which means you need to know everything 456 00:13:19.833 --> 00:13:20.750 about your system like 457 00:13:20.750 --> 00:13:21.833 an operating system does. 458 00:13:23.125 --> 00:13:23.791 Hello, Sherlock. 459 00:13:24.250 --> 00:13:25.208 (Laughing) 460 00:13:26.083 --> 00:13:27.208 This is a co-co-co host. 461 00:13:27.666 --> 00:13:29.208 And this is the trade-off is people were 462 00:13:29.208 --> 00:13:30.708 like, "Oh, you use vec because it has 463 00:13:30.708 --> 00:13:31.708 linear access order. 464 00:13:31.708 --> 00:13:33.875 That's great, but vec requires alloc 465 00:13:34.041 --> 00:13:36.083 because you have to allocate that space. 466 00:13:36.083 --> 00:13:38.166 Or if it changes over time, you have to 467 00:13:38.166 --> 00:13:39.458 reallocate those space. 468 00:13:39.750 --> 00:13:41.583 And because we don't have a lot of memory 469 00:13:41.583 --> 00:13:43.583 to deal with, we actually usually don't 470 00:13:43.583 --> 00:13:45.791 have alloc at all in embedded systems. 471 00:13:45.791 --> 00:13:47.500 We just say, you should figure out what 472 00:13:47.500 --> 00:13:49.791 kind of memory you need ahead of time and 473 00:13:49.791 --> 00:13:53.000 don't do dynamic memory access because it 474 00:13:53.000 --> 00:13:55.625 can cause a lot of variability in time. 475 00:13:55.625 --> 00:13:58.000 Like if you have to go hunting for memory 476 00:13:58.000 --> 00:14:01.416 to alloc, or you tend to need more memory 477 00:14:01.416 --> 00:14:03.500 with dynamic memory access because you 478 00:14:03.500 --> 00:14:04.083 can have fragmentation 479 00:14:04.083 --> 00:14:05.208 and things like that. 480 00:14:05.208 --> 00:14:07.208 So if you need typically on average, like 481 00:14:07.208 --> 00:14:09.750 let's say 64K of memory allocated 482 00:14:09.750 --> 00:14:11.708 anytime, you probably need an allocator 483 00:14:11.708 --> 00:14:15.250 with a pool of 128 or 192 or something 484 00:14:15.250 --> 00:14:16.416 like that because if it ever gets 485 00:14:16.416 --> 00:14:18.750 fragmented, you don't wanna go, "Well, I 486 00:14:18.750 --> 00:14:21.291 have space, but not in one linear shot." 487 00:14:21.291 --> 00:14:22.458 Right,right. 488 00:14:22.458 --> 00:14:22.666 Sorry. 489 00:14:23.083 --> 00:14:25.333 So it adds a lot of variability and 490 00:14:25.333 --> 00:14:27.500 inconsistency and non-determinism, which 491 00:14:27.500 --> 00:14:28.875 we don't love so much 492 00:14:28.875 --> 00:14:29.833 for embedded systems. 493 00:14:30.333 --> 00:14:31.833 A lot of times we just don't use alloc, 494 00:14:31.833 --> 00:14:34.208 which means having a vec is not really an 495 00:14:34.208 --> 00:14:36.166 option in embedded sys-- You can do it, 496 00:14:36.166 --> 00:14:37.458 but a lot of times you don't. 497 00:14:37.458 --> 00:14:39.458 Practically you can, pragmatically you 498 00:14:39.458 --> 00:14:40.750 don't, if that makes sense. 499 00:14:41.291 --> 00:14:44.208 Yeah, cause it's-- Jesus fucking Christ. 500 00:14:44.625 --> 00:14:44.958 Sherlock! 501 00:14:47.375 --> 00:14:47.750 (Speaking In Foreign Language) 502 00:14:51.500 --> 00:14:52.750 But don't you have the same problem with 503 00:14:52.750 --> 00:14:54.166 allocations for linked lists? 504 00:14:54.625 --> 00:14:56.125 Ooh, I'm excited to get there. 505 00:14:56.500 --> 00:14:57.333 And before we get there, 506 00:14:57.541 --> 00:14:59.250 one more fun fact is the... 507 00:14:59.250 --> 00:14:59.625 Rust-- 508 00:14:59.875 --> 00:15:01.916 I was gonna talk about this article! 509 00:15:02.500 --> 00:15:05.000 Yeah, so there's an excellent book called 510 00:15:05.000 --> 00:15:05.708 "Learning Rust with 511 00:15:05.708 --> 00:15:06.500 Too Many Linked Lists" 512 00:15:06.791 --> 00:15:07.500 Sorry, what I call 513 00:15:07.500 --> 00:15:08.916 articles, other people call books. 514 00:15:09.375 --> 00:15:09.791 Yeah, sorry. 515 00:15:11.083 --> 00:15:13.041 (Laughing) Your articles kind of are books. 516 00:15:13.791 --> 00:15:15.291 But they talk about all the places where 517 00:15:15.291 --> 00:15:17.166 they go, "You probably should never use 518 00:15:17.166 --> 00:15:18.708 linked lists in Rust because there's a 519 00:15:18.708 --> 00:15:19.458 lot of reasons you should 520 00:15:19.458 --> 00:15:20.791 use vec, you should use this. 521 00:15:20.791 --> 00:15:23.208 If you're coming from another language, 522 00:15:23.208 --> 00:15:24.125 you might reach for them." 523 00:15:24.125 --> 00:15:25.916 But in Rust, they happen to just not be 524 00:15:25.916 --> 00:15:27.166 as great as you might think because 525 00:15:27.166 --> 00:15:28.250 they're not abstracted away. 526 00:15:28.458 --> 00:15:30.416 But there's a couple caveats of like, 527 00:15:30.416 --> 00:15:32.250 "Hey, what are some cases where you still 528 00:15:32.250 --> 00:15:33.958 might want linked lists in Rust?" 529 00:15:34.166 --> 00:15:37.000 And one of them is mumble mumble, kernel 530 00:15:37.000 --> 00:15:38.666 embedded something, something intrusive. 531 00:15:39.041 --> 00:15:40.750 And they say, "It's niche, you're talking 532 00:15:40.750 --> 00:15:42.208 about a situation where you're not even 533 00:15:42.208 --> 00:15:43.458 using your language's runtime. 534 00:15:43.916 --> 00:15:45.125 Is that not a red flag that 535 00:15:45.125 --> 00:15:46.208 you're doing something strange? 536 00:15:46.583 --> 00:15:47.916 It's also wildly unsafe. 537 00:15:48.500 --> 00:15:50.125 But sure, build your awesome zero 538 00:15:50.125 --> 00:15:51.500 allocation lists on the stack." 539 00:15:51.750 --> 00:15:53.375 And that's what we're gonna do. 540 00:15:54.250 --> 00:15:55.250 This is the best slide. 541 00:15:55.625 --> 00:15:56.041 Yeah, yeah. 542 00:15:56.041 --> 00:15:56.583 I think this is 543 00:15:56.583 --> 00:15:58.458 Gankra's writing or Aria, yeah. 544 00:15:58.500 --> 00:16:01.541 In the show notes, we better have a link 545 00:16:01.541 --> 00:16:02.875 to that because yeah, I 546 00:16:02.875 --> 00:16:04.000 believe that it's real. 547 00:16:04.416 --> 00:16:06.875 I recognize the frustration of maybe 548 00:16:06.875 --> 00:16:09.791 people trying to do that kind of stuff 549 00:16:09.791 --> 00:16:11.666 too early in Rust's lifetime. 550 00:16:12.500 --> 00:16:14.458 And being like, "It's a systems language, 551 00:16:14.500 --> 00:16:16.500 therefore it should be able to do that." 552 00:16:16.791 --> 00:16:18.208 And it just wasn't quite there yet. 553 00:16:18.833 --> 00:16:20.583 And after the hundredth person asking 554 00:16:20.583 --> 00:16:21.416 about it, you're like, 555 00:16:21.416 --> 00:16:23.083 "Okay, you're on your own." 556 00:16:23.166 --> 00:16:24.750 It's like writing any other collection is 557 00:16:24.750 --> 00:16:26.791 that you can totally do it with Rust. 558 00:16:26.791 --> 00:16:28.666 And Rust has gotten better at making some 559 00:16:28.666 --> 00:16:30.083 of this unsafe stuff easier. 560 00:16:30.500 --> 00:16:31.291 It's just hard. 561 00:16:31.291 --> 00:16:32.875 It's not the first project you wanna do. 562 00:16:32.875 --> 00:16:33.500 Even if you go, "Ha 563 00:16:33.500 --> 00:16:34.416 ha, I am a gray beard. 564 00:16:34.666 --> 00:16:35.500 I should know." 565 00:16:35.750 --> 00:16:37.166 You gotta learn Rust and you gotta learn 566 00:16:37.166 --> 00:16:38.625 how to write unsafe code good. 567 00:16:39.041 --> 00:16:39.750 And we'll get into that. 568 00:16:39.750 --> 00:16:41.000 Because what I'm about to show you is 569 00:16:41.000 --> 00:16:44.625 wildly, wildly unsafe, but it requires 570 00:16:44.625 --> 00:16:47.541 unsafe code but is safe because of some 571 00:16:47.541 --> 00:16:48.750 of the guarantees we'll get into. 572 00:16:49.000 --> 00:16:51.958 So it can be done with unsafe code, but 573 00:16:51.958 --> 00:16:54.916 in a safe API sort of a setup. 574 00:16:55.666 --> 00:16:57.333 I just also wanted to mention that when 575 00:16:57.333 --> 00:16:58.833 this was written, Miri 576 00:16:58.833 --> 00:17:00.708 probably wasn't as good as it is now. 577 00:17:01.541 --> 00:17:02.083 Miri may not have 578 00:17:02.083 --> 00:17:03.500 existed when this was written. 579 00:17:03.541 --> 00:17:04.375 Yeah, I have no idea 580 00:17:04.375 --> 00:17:05.291 what the timeline is there. 581 00:17:05.833 --> 00:17:07.833 This might've been before the days of 582 00:17:07.833 --> 00:17:08.750 const because Miri didn't 583 00:17:08.750 --> 00:17:10.000 exist until we had const. 584 00:17:10.833 --> 00:17:11.791 And const didn't exist 585 00:17:11.791 --> 00:17:14.000 till 1.30 or something. 586 00:17:14.458 --> 00:17:15.500 And this might predate that. 587 00:17:15.500 --> 00:17:16.250 It'd be good to look up. 588 00:17:16.333 --> 00:17:17.458 The show notes will definitely tell you 589 00:17:17.458 --> 00:17:18.375 whether it does or not. 590 00:17:19.916 --> 00:17:20.750 Because Amanda's the best. 591 00:17:21.000 --> 00:17:21.208 Yeah. 592 00:17:21.916 --> 00:17:24.208 So if we don't have vec, how do we do a 593 00:17:24.208 --> 00:17:25.750 variable quantity of things? 594 00:17:25.750 --> 00:17:27.208 Like in embedded systems, if you say we 595 00:17:27.208 --> 00:17:28.875 might have one, two, three, four, five of 596 00:17:28.875 --> 00:17:30.583 something at any given time and this 597 00:17:30.583 --> 00:17:32.875 might change over time, how do we deal 598 00:17:32.875 --> 00:17:35.166 with that fact in embedded systems if we 599 00:17:35.166 --> 00:17:36.125 don't have something like 600 00:17:36.125 --> 00:17:37.375 vec where we can push and pop? 601 00:17:37.750 --> 00:17:39.250 Well, we usually use 602 00:17:39.250 --> 00:17:40.458 upper bound collections. 603 00:17:40.916 --> 00:17:42.500 So if you've used something like a stack 604 00:17:42.500 --> 00:17:45.625 vec before or heapless is a very popular 605 00:17:45.625 --> 00:17:48.375 crate, what you do is you go, here's a 606 00:17:48.375 --> 00:17:50.625 chunk with room for up to 16 items. 607 00:17:51.208 --> 00:17:53.958 And we track what our current len is 608 00:17:53.958 --> 00:17:56.833 separately from our capacity and you can 609 00:17:56.833 --> 00:17:57.708 push and pop things. 610 00:17:57.708 --> 00:17:58.875 But if you have 16 items 611 00:17:58.875 --> 00:18:00.500 and you go to push, it fails. 612 00:18:01.291 --> 00:18:03.916 And this is generally how vec itself 613 00:18:03.916 --> 00:18:06.041 works, but instead of failing on that 614 00:18:06.041 --> 00:18:08.708 17th item, it goes, reallocates, copies 615 00:18:08.708 --> 00:18:09.958 over, and then goes, 616 00:18:10.458 --> 00:18:12.000 surprise, I had room the whole time. 617 00:18:12.000 --> 00:18:13.375 But actually it's doing reallocation. 618 00:18:13.583 --> 00:18:14.416 That's what I was thinking. 619 00:18:14.416 --> 00:18:15.958 These are just special flavors of that 620 00:18:16.000 --> 00:18:17.250 that just never do that step. 621 00:18:17.250 --> 00:18:19.500 When a vec grows, you need 622 00:18:19.500 --> 00:18:21.250 extra space for that to happen. 623 00:18:22.000 --> 00:18:22.500 Just like-- 624 00:18:22.541 --> 00:18:24.000 Yeah, and usually it'll grow some 625 00:18:24.000 --> 00:18:25.500 reasonable amount, like double or 626 00:18:25.500 --> 00:18:26.375 something like that. 627 00:18:26.375 --> 00:18:28.250 So if you have 16, it goes, okay, I'm 628 00:18:28.250 --> 00:18:29.958 gonna get you 32, just so I don't have to 629 00:18:29.958 --> 00:18:31.541 go and reallocate too 630 00:18:31.541 --> 00:18:32.916 often and things like that. 631 00:18:32.916 --> 00:18:35.458 But again, no allocator, not an option. 632 00:18:35.458 --> 00:18:36.750 This reminds me of two things. 633 00:18:36.750 --> 00:18:38.083 When I was working on the itch desktop 634 00:18:38.083 --> 00:18:40.416 app and we started having larger games, 635 00:18:40.666 --> 00:18:42.458 like multi-gigabyte games, we had the 636 00:18:42.458 --> 00:18:45.416 problem where people had, for example, 15 637 00:18:45.416 --> 00:18:46.750 gigabytes free, and they wanted to 638 00:18:46.750 --> 00:18:47.916 install a 12 gigabyte game. 639 00:18:48.250 --> 00:18:49.708 And if you just download the archive and 640 00:18:49.708 --> 00:18:50.458 then try to extract 641 00:18:50.458 --> 00:18:51.250 it, that doesn't work. 642 00:18:51.500 --> 00:18:54.208 But I did the streaming extraction thingy 643 00:18:54.208 --> 00:18:55.625 where the archive is actually never 644 00:18:55.625 --> 00:18:56.958 stored on disk, and now that worked. 645 00:18:57.250 --> 00:18:57.458 Nice. 646 00:18:57.791 --> 00:18:59.166 I think that's what Steam is doing too. 647 00:18:59.541 --> 00:19:00.541 And the other thing I was thinking about 648 00:19:00.541 --> 00:19:03.541 was when you catch an out of memory 649 00:19:03.541 --> 00:19:04.916 error, you might not have 650 00:19:04.916 --> 00:19:06.083 enough memory to deal with it. 651 00:19:06.958 --> 00:19:08.500 Yeah, the nice thing in embedded is we 652 00:19:08.500 --> 00:19:10.000 usually, for all these upper bound 653 00:19:10.000 --> 00:19:12.083 collections, usually they're gonna live 654 00:19:12.083 --> 00:19:12.958 in one of two places. 655 00:19:13.291 --> 00:19:15.041 They're either gonna live in static. 656 00:19:15.333 --> 00:19:16.500 So a lot of times we'll just say, look, 657 00:19:16.708 --> 00:19:18.500 we're never gonna handle more than 16 658 00:19:18.500 --> 00:19:20.916 connections ever in this firmware. 659 00:19:21.291 --> 00:19:22.291 That's just a hard upper limit. 660 00:19:22.666 --> 00:19:24.250 And so we store that as a static, which 661 00:19:24.250 --> 00:19:25.958 means the linker actually has an option 662 00:19:25.958 --> 00:19:26.750 to say, do you have 663 00:19:26.750 --> 00:19:27.958 enough room for this or not? 664 00:19:27.958 --> 00:19:29.666 You can basically do your memory 665 00:19:29.666 --> 00:19:32.375 allocation at compile time by filling up 666 00:19:32.375 --> 00:19:33.958 your statics, and you tell the compiler 667 00:19:33.958 --> 00:19:35.583 how much total storage you have. 668 00:19:35.916 --> 00:19:37.208 And if you run out of storage, then it 669 00:19:37.208 --> 00:19:38.750 just says, nope, does not 670 00:19:38.750 --> 00:19:39.708 compile, you're out of space. 671 00:19:40.041 --> 00:19:40.666 That's great. 672 00:19:40.958 --> 00:19:42.375 But then sometimes we also put things on 673 00:19:42.375 --> 00:19:45.291 the stack and in embedded stack overflows 674 00:19:45.291 --> 00:19:46.666 are one of the most painful things to 675 00:19:46.666 --> 00:19:48.500 debug for exactly like what you're 676 00:19:48.500 --> 00:19:50.375 saying, because if I put these on the 677 00:19:50.375 --> 00:19:52.208 stack, especially if I try and return it 678 00:19:52.208 --> 00:19:53.791 or pass it up and down the stack and it 679 00:19:53.791 --> 00:19:55.791 makes duplicate copies, and it's very 680 00:19:55.791 --> 00:19:57.250 large, that's problematic. 681 00:19:57.625 --> 00:19:59.458 But pragmatically, most embedded systems 682 00:19:59.458 --> 00:20:02.083 for big, chunky things, like if they're 683 00:20:02.083 --> 00:20:04.416 bigger than a couple bytes or if you have 684 00:20:04.416 --> 00:20:05.458 a bunch of them, we're 685 00:20:05.458 --> 00:20:06.250 gonna put them in a static. 686 00:20:06.583 --> 00:20:08.125 And that way there's just 687 00:20:08.125 --> 00:20:09.833 always space guaranteed for it. 688 00:20:09.833 --> 00:20:10.833 And the compiler can say, 689 00:20:10.833 --> 00:20:12.166 it's allocated right here. 690 00:20:12.625 --> 00:20:14.791 About stack overflows, isn't there a way, 691 00:20:15.000 --> 00:20:16.791 like you have a red zone? 692 00:20:16.791 --> 00:20:17.958 I don't know if that's what red zones are 693 00:20:17.958 --> 00:20:19.125 for or something, but like-- 694 00:20:19.666 --> 00:20:21.041 So what a red zone is-- 695 00:20:21.458 --> 00:20:22.958 -- detect when it's about to blow. 696 00:20:23.583 --> 00:20:23.875 Yeah. Yeah. 697 00:20:24.375 --> 00:20:25.708 So another fun aside-- 698 00:20:26.000 --> 00:20:28.041 This whole podcast is asides in case you 699 00:20:28.041 --> 00:20:28.875 hadn't noticed, James. 700 00:20:28.875 --> 00:20:29.541 This is kind of, this 701 00:20:29.541 --> 00:20:30.541 is our second season. 702 00:20:30.916 --> 00:20:31.541 That's what we do. 703 00:20:31.541 --> 00:20:32.291 Yeah, that's what we do. 704 00:20:32.958 --> 00:20:34.541 So most stacks grow downwards. 705 00:20:34.916 --> 00:20:36.833 So when you put more stuff on there, they 706 00:20:36.833 --> 00:20:38.125 start at some top address 707 00:20:38.125 --> 00:20:39.166 and they grow downwards. 708 00:20:39.708 --> 00:20:41.250 Growing downwards is sort of a choice, 709 00:20:41.416 --> 00:20:41.875 but it's kind of like 710 00:20:41.875 --> 00:20:43.333 big endian little endian. 711 00:20:43.333 --> 00:20:45.375 Most processors have decided that growing 712 00:20:45.375 --> 00:20:47.375 downward is the direction that stacks go. 713 00:20:47.375 --> 00:20:50.583 The way that you detect stack overflows 714 00:20:50.583 --> 00:20:52.750 on a desktop system is that your 715 00:20:52.750 --> 00:20:53.958 operating system will put 716 00:20:53.958 --> 00:20:55.291 what's called a red zone there. 717 00:20:55.291 --> 00:20:57.333 And what it'll do is it'll say, if anyone 718 00:20:57.333 --> 00:20:59.583 touches this, it throws a fault and we 719 00:20:59.583 --> 00:21:01.125 halt the program and that's a problem. 720 00:21:01.416 --> 00:21:03.541 So it kind of puts like a no man's land 721 00:21:03.833 --> 00:21:05.500 at some limit on your stack. 722 00:21:05.750 --> 00:21:07.458 So that if you increment the stack 723 00:21:07.458 --> 00:21:09.375 pointer and start writing into that dead 724 00:21:09.375 --> 00:21:12.416 zone, then it throws an error and the 725 00:21:12.416 --> 00:21:13.833 operating system can either choose to do 726 00:21:13.833 --> 00:21:15.583 something like allocate more memory or 727 00:21:15.583 --> 00:21:17.541 kill the program or something like that. 728 00:21:17.541 --> 00:21:20.083 That requires the operating system to do 729 00:21:20.083 --> 00:21:21.958 so and the CPU to have 730 00:21:21.958 --> 00:21:24.416 something that can catch that access. 731 00:21:24.416 --> 00:21:24.958 Yeah, I was gonna say-- 732 00:21:25.041 --> 00:21:26.625 Usually that's an MMUs job. 733 00:21:26.625 --> 00:21:28.041 That's the right barrier. 734 00:21:28.333 --> 00:21:30.125 Yeah, that's the MMU who would catch 735 00:21:30.125 --> 00:21:31.166 that, like that you're 736 00:21:31.166 --> 00:21:31.875 actually writing there. 737 00:21:31.875 --> 00:21:33.208 Cause you're not, it's not like you have 738 00:21:33.208 --> 00:21:34.541 an interpreter or something, you can 739 00:21:34.541 --> 00:21:35.708 check every memory access. 740 00:21:36.041 --> 00:21:36.583 Well, yeah. 741 00:21:37.125 --> 00:21:37.750 Yeah, exactly. 742 00:21:38.041 --> 00:21:39.458 So your operating system will just say, 743 00:21:39.500 --> 00:21:40.666 hey, this region of memory, if anyone 744 00:21:40.666 --> 00:21:42.750 ever writes into it, throw an error, the 745 00:21:42.750 --> 00:21:44.541 operating system catches that and then 746 00:21:44.541 --> 00:21:45.750 does something with it. 747 00:21:46.125 --> 00:21:47.791 So fun fact about microcontrollers, no 748 00:21:47.791 --> 00:21:51.041 operating systems, no MMUs, they usually 749 00:21:51.041 --> 00:21:53.708 sometimes have something called an MPU 750 00:21:54.166 --> 00:21:55.875 which can do that protection job that we 751 00:21:55.875 --> 00:21:57.916 talked about, but can't do the memory, 752 00:21:57.916 --> 00:21:58.416 virtual memory 753 00:21:58.416 --> 00:22:00.458 remapping that desktops do. 754 00:22:00.583 --> 00:22:01.791 I imagine MPU for a 755 00:22:01.791 --> 00:22:03.041 memory protection unit? 756 00:22:03.541 --> 00:22:03.833 Yep, exactly. 757 00:22:04.166 --> 00:22:06.375 But not every system has that and not 758 00:22:06.375 --> 00:22:07.583 everyone likes setting that up. 759 00:22:07.958 --> 00:22:10.500 So on embedded systems, it's very classic 760 00:22:10.500 --> 00:22:12.125 that when your linker comes along and is 761 00:22:12.125 --> 00:22:13.541 deciding where to put things in memory, 762 00:22:13.791 --> 00:22:15.500 it starts at the bottom of memory and 763 00:22:15.500 --> 00:22:16.583 starts putting all of your global 764 00:22:16.583 --> 00:22:17.458 variables and your 765 00:22:17.458 --> 00:22:18.625 statics and stuff like that. 766 00:22:18.916 --> 00:22:20.083 And it places those upwards. 767 00:22:20.500 --> 00:22:21.291 And then your stack 768 00:22:21.291 --> 00:22:22.625 starts at the top of memory. 769 00:22:22.625 --> 00:22:24.625 So you have the largest variable possible 770 00:22:24.625 --> 00:22:26.541 amount and the amount of stack memory, 771 00:22:26.875 --> 00:22:29.125 your max stack usage, is just the space 772 00:22:29.125 --> 00:22:31.083 from the top of your memory to when you 773 00:22:31.083 --> 00:22:32.125 hit the first variable. 774 00:22:32.541 --> 00:22:35.041 But the linker does nothing to set up any 775 00:22:35.041 --> 00:22:36.541 guard in between that, which means if you 776 00:22:36.541 --> 00:22:38.625 stack overflow, you just start scribbling 777 00:22:38.625 --> 00:22:40.166 over all your globals and statics. 778 00:22:40.541 --> 00:22:41.083 And when you don't have 779 00:22:41.083 --> 00:22:42.791 multiple threads, you only have one. 780 00:22:43.000 --> 00:22:44.500 So it just grows from the top downwards. 781 00:22:45.083 --> 00:22:46.958 That's one of those horrific programming 782 00:22:46.958 --> 00:22:48.375 things that everyone just accepted 783 00:22:48.375 --> 00:22:49.666 because that was the best you could do 784 00:22:49.666 --> 00:22:50.750 for a very long time and 785 00:22:50.750 --> 00:22:52.000 now it's just become standard. 786 00:22:52.416 --> 00:22:54.625 Newer, like new, like coming out right 787 00:22:54.625 --> 00:22:56.541 now processors for microcontrollers will 788 00:22:56.541 --> 00:22:58.833 have a CPU level stack limit where you 789 00:22:58.833 --> 00:23:01.250 could basically not use an MMU or an MPU 790 00:23:01.250 --> 00:23:03.083 and just say, if the stack ever hits this 791 00:23:03.083 --> 00:23:04.875 number, it throws a processor fault. 792 00:23:05.125 --> 00:23:06.583 Because if you like increment the stack 793 00:23:06.583 --> 00:23:08.000 pointer above some limit. 794 00:23:08.458 --> 00:23:09.416 Right, you could watch the register. 795 00:23:09.833 --> 00:23:10.291 Yeah, yeah, yeah. 796 00:23:10.291 --> 00:23:12.208 So thumb V8, which is like the new 797 00:23:12.208 --> 00:23:14.750 Cortex-M33, 23 processors, like the new 798 00:23:14.750 --> 00:23:17.833 Raspberry Pi Pico 2 have an instruction 799 00:23:17.833 --> 00:23:19.333 for stack limit setting. 800 00:23:19.625 --> 00:23:20.625 Older processors don't. 801 00:23:20.625 --> 00:23:21.583 And so there's a really 802 00:23:21.583 --> 00:23:22.708 cool tool in embedded. 803 00:23:23.125 --> 00:23:25.333 And the problem is with linkers, a lot of 804 00:23:25.333 --> 00:23:27.166 this numbers you don't really know until 805 00:23:27.166 --> 00:23:27.750 you're like done 806 00:23:27.750 --> 00:23:29.500 compiling and it's placing things. 807 00:23:29.500 --> 00:23:31.750 There's a cool tool from Ferrous called 808 00:23:31.750 --> 00:23:34.208 Fliplink which does a cool trick where it 809 00:23:34.208 --> 00:23:36.333 compiles once, figures out what the size 810 00:23:36.333 --> 00:23:37.583 of the global variables are. 811 00:23:37.916 --> 00:23:39.166 And instead of putting them at the bottom 812 00:23:39.375 --> 00:23:41.041 where the stack will grow into them, it 813 00:23:41.041 --> 00:23:42.916 moves them to the top and puts the stack 814 00:23:42.916 --> 00:23:45.041 pointer just below them so that it grows 815 00:23:45.041 --> 00:23:46.375 downwards because on most of these 816 00:23:46.375 --> 00:23:47.916 processors, when you hit the bottom of 817 00:23:47.916 --> 00:23:49.791 RAM and start writing into the next 818 00:23:49.791 --> 00:23:51.291 addresses that are not valid 819 00:23:51.291 --> 00:23:53.041 RAM, you do get a hard fault. 820 00:23:53.333 --> 00:23:55.083 Like you just get a processor fault that 821 00:23:55.083 --> 00:23:56.958 says like, "You tried to write to memory 822 00:23:56.958 --> 00:23:58.375 that doesn't exist, sorry!" 823 00:23:59.000 --> 00:24:00.416 And so that's a much more predictable way 824 00:24:00.416 --> 00:24:01.958 of making sure that your stack overflows 825 00:24:02.083 --> 00:24:05.291 become like hard program stops versus 826 00:24:05.291 --> 00:24:07.208 just, "Hey, it happens to keep going 827 00:24:07.208 --> 00:24:09.125 except for you just zeroed all of your 828 00:24:09.125 --> 00:24:11.958 executor state tracking variables, oops." 829 00:24:12.583 --> 00:24:14.291 And so like anytime anyone comes in and 830 00:24:14.291 --> 00:24:15.666 they're like, "Hey, this is weird, it 831 00:24:15.666 --> 00:24:17.500 only crashes sometimes," or, "It does 832 00:24:17.500 --> 00:24:19.333 crash in debug mode, but it 833 00:24:19.333 --> 00:24:20.541 doesn't crash in release mode." 834 00:24:20.541 --> 00:24:22.625 We go, "You should try Fliplink because 835 00:24:22.625 --> 00:24:24.083 you probably have a stack overflow!" 836 00:24:24.375 --> 00:24:25.750 Like anytime anyone just goes spooky 837 00:24:25.750 --> 00:24:27.375 things are happening because that's 838 00:24:27.375 --> 00:24:28.541 really weird in Rust. 839 00:24:28.541 --> 00:24:30.333 We don't run into that almost always. 840 00:24:31.041 --> 00:24:32.250 You had a stack overflow and you 841 00:24:32.250 --> 00:24:35.125 accidentally did undefined behavior to 842 00:24:35.125 --> 00:24:36.333 all of your global variables. 843 00:24:36.833 --> 00:24:38.000 So you're saying Rust is unsafe... 844 00:24:39.125 --> 00:24:40.291 Environments are not safe. 845 00:24:41.916 --> 00:24:43.458 Okay, no, no, we're moving on. 846 00:24:43.458 --> 00:24:45.416 "If you file open dev 847 00:24:45.416 --> 00:24:47.708 mem and you write to it..." 848 00:24:48.083 --> 00:24:48.708 Yeah, exactly. 849 00:24:49.166 --> 00:24:50.416 These are one of those things that the 850 00:24:50.416 --> 00:24:52.333 programming language has certain rules 851 00:24:52.666 --> 00:24:55.541 that your environment has to upkeep and 852 00:24:55.541 --> 00:24:58.000 that at some point the language just has 853 00:24:58.000 --> 00:24:59.541 to say, I have to assume 854 00:24:59.541 --> 00:25:01.250 these facts are always true. 855 00:25:02.000 --> 00:25:03.500 And if you violate those as the 856 00:25:03.500 --> 00:25:05.000 implementer, usually that's like a 857 00:25:05.000 --> 00:25:06.208 problem with your operating system 858 00:25:06.208 --> 00:25:08.041 integration, but embedded systems, 859 00:25:08.375 --> 00:25:09.166 everyone is writing their 860 00:25:09.166 --> 00:25:10.458 own operating system basically. 861 00:25:10.875 --> 00:25:13.166 So if you violate systemic rules, then 862 00:25:13.166 --> 00:25:14.875 you have systemic problems. 863 00:25:15.125 --> 00:25:17.208 But yeah, to avoid this, we usually put 864 00:25:17.208 --> 00:25:18.916 these things in static so we can see that 865 00:25:18.916 --> 00:25:20.416 they are there and then track them and 866 00:25:20.416 --> 00:25:21.458 go, hey, it's really clear. 867 00:25:21.958 --> 00:25:22.791 We have a baseline 868 00:25:22.791 --> 00:25:24.541 memory usage of this much. 869 00:25:25.208 --> 00:25:27.125 The downside is, is you have to sort of 870 00:25:27.125 --> 00:25:29.458 guess and if you guess too 871 00:25:29.458 --> 00:25:31.041 high, you have potential waste. 872 00:25:31.291 --> 00:25:32.750 If you say, hey, I'm just gonna say I 873 00:25:32.750 --> 00:25:35.291 have room for 16 connections, but in 874 00:25:35.291 --> 00:25:37.458 practice you only ever have three, you're 875 00:25:37.458 --> 00:25:41.375 just wasting whatever 13/16ths of that 876 00:25:41.375 --> 00:25:42.416 chunk of collection is 877 00:25:42.500 --> 00:25:43.958 because you just never use it. 878 00:25:44.291 --> 00:25:46.583 And so that memory could be used for 879 00:25:46.583 --> 00:25:48.416 something else or more stack. 880 00:25:48.416 --> 00:25:49.083 So you don't run into 881 00:25:49.083 --> 00:25:50.458 stack overflows as much. 882 00:25:50.458 --> 00:25:51.083 You kind of have to 883 00:25:51.083 --> 00:25:52.500 manually size these things. 884 00:25:52.500 --> 00:25:53.125 Too small? 885 00:25:53.541 --> 00:25:54.791 And you run into errors where it says, 886 00:25:54.791 --> 00:25:56.375 no, we couldn't allocate another socket 887 00:25:56.375 --> 00:25:57.416 or something like that. 888 00:25:57.458 --> 00:25:59.625 Too high and you just are burning memory, 889 00:25:59.625 --> 00:26:01.166 which we've talked about is like one of 890 00:26:01.166 --> 00:26:04.291 your most valuable and not abundant 891 00:26:04.291 --> 00:26:06.250 resources on embedded systems. 892 00:26:06.541 --> 00:26:08.166 And the other side is when you're writing 893 00:26:08.166 --> 00:26:10.416 a library and every user wants to use a 894 00:26:10.416 --> 00:26:12.208 different number of sockets or 895 00:26:12.208 --> 00:26:13.250 connections, we put a 896 00:26:13.250 --> 00:26:14.541 const generic on it. 897 00:26:14.541 --> 00:26:16.916 So you say this is a pool of sockets that 898 00:26:16.916 --> 00:26:20.041 is generic over some number that lets you 899 00:26:20.041 --> 00:26:22.625 say it could be four, it could be 16, it 900 00:26:22.625 --> 00:26:25.500 could be 32 and generics are infectious. 901 00:26:26.208 --> 00:26:27.416 When you have to deal with generics on 902 00:26:27.416 --> 00:26:29.416 multiple things or you are making like a 903 00:26:29.416 --> 00:26:31.416 bigger data structure that contains a 904 00:26:31.416 --> 00:26:33.333 bunch of variably sized things, you can 905 00:26:33.333 --> 00:26:35.666 end up with like five or 10 generics on 906 00:26:35.666 --> 00:26:37.166 one structure that are just like the 907 00:26:37.166 --> 00:26:38.625 dials for what are the 908 00:26:38.625 --> 00:26:40.166 maximum sizes for these. 909 00:26:40.166 --> 00:26:41.166 And it's tremendously 910 00:26:41.166 --> 00:26:42.500 tedious to write that. 911 00:26:42.500 --> 00:26:44.708 And it looks super ugly everywhere you 912 00:26:44.708 --> 00:26:46.958 use it and name that type and aliases can 913 00:26:46.958 --> 00:26:48.625 help, but it does not bring joy. 914 00:26:49.375 --> 00:26:50.875 Yeah, I think the one of the most 915 00:26:50.875 --> 00:26:52.625 generics heavy code base that I 916 00:26:52.625 --> 00:26:56.125 encountered early on was Tower and Hyper 917 00:26:56.791 --> 00:26:57.916 with all the service abstraction... 918 00:26:57.916 --> 00:26:59.166 I wrote about it 919 00:26:59.166 --> 00:27:00.583 actually back in the days. 920 00:27:01.166 --> 00:27:03.541 And the nice thing on desktop is that you 921 00:27:03.541 --> 00:27:06.000 can eventually just do what Axum does and 922 00:27:06.000 --> 00:27:08.333 just box it if it becomes out of control. 923 00:27:09.000 --> 00:27:10.291 Like box dyn or whatever? 924 00:27:10.333 --> 00:27:11.500 Yeah, which I assume is not 925 00:27:11.500 --> 00:27:12.750 an option here on embedded. 926 00:27:13.208 --> 00:27:14.375 It is, it's a pain. 927 00:27:14.875 --> 00:27:16.250 I mean, boxing is not an option. 928 00:27:16.250 --> 00:27:17.458 We still have like dyn 929 00:27:17.458 --> 00:27:19.375 trait, you can still do dyn trait. 930 00:27:19.375 --> 00:27:20.000 The downsides is 931 00:27:20.000 --> 00:27:20.916 like, where do you put it? 932 00:27:21.541 --> 00:27:22.333 Because if you can't 933 00:27:22.333 --> 00:27:23.333 box it, where does it go? 934 00:27:23.333 --> 00:27:24.833 And you can have these kind of like stack 935 00:27:24.833 --> 00:27:26.166 collections or like static 936 00:27:26.166 --> 00:27:28.000 boxes, like one use boxes. 937 00:27:28.500 --> 00:27:29.333 And we use those for a 938 00:27:29.333 --> 00:27:30.416 bunch of things on embedded too. 939 00:27:30.750 --> 00:27:32.041 It's not impossible, it's just a pain in 940 00:27:32.041 --> 00:27:33.250 the butt is the answer. 941 00:27:33.291 --> 00:27:33.666 I see. 942 00:27:34.041 --> 00:27:35.666 After all that, maybe linked lists aren't 943 00:27:35.666 --> 00:27:37.500 so bad, at least for embedded systems. 944 00:27:37.791 --> 00:27:40.375 So cool, maybe we wanna try intrusive 945 00:27:40.375 --> 00:27:41.791 linked lists, but how? 946 00:27:42.041 --> 00:27:44.375 And how do we get like these linked lists 947 00:27:44.375 --> 00:27:45.583 where we talked about like where do we 948 00:27:45.583 --> 00:27:47.333 put stuff and how does it work and how do 949 00:27:47.333 --> 00:27:48.875 we make it safe and things like that? 950 00:27:48.875 --> 00:27:49.958 Like we talked about in 951 00:27:49.958 --> 00:27:51.000 "What are you synching about?" 952 00:27:51.333 --> 00:27:53.958 We already do this in maitake-sync 953 00:27:54.125 --> 00:27:56.041 because we have intrusive linked lists 954 00:27:56.041 --> 00:27:57.833 for wakers and things like that. 955 00:27:58.125 --> 00:28:00.375 So we talked about WaitCell which is just 956 00:28:00.375 --> 00:28:01.041 like, it's like an 957 00:28:01.041 --> 00:28:02.500 option waker basically. 958 00:28:02.958 --> 00:28:04.291 So you have room for exactly one thing, 959 00:28:04.291 --> 00:28:05.833 which works really great if only one 960 00:28:05.833 --> 00:28:07.041 person's ever gonna wait on that. 961 00:28:07.375 --> 00:28:09.000 But if you have five tasks that might 962 00:28:09.000 --> 00:28:11.125 wanna wait on that, or in some cases 963 00:28:11.125 --> 00:28:14.250 three and in some cases five, how do we 964 00:28:14.250 --> 00:28:15.625 deal with that without having a const 965 00:28:15.625 --> 00:28:17.041 generic for the upper bound? 966 00:28:17.041 --> 00:28:18.791 And the answer is intrusive linked lists. 967 00:28:19.208 --> 00:28:22.250 We put wakers inside of tasks and they 968 00:28:22.250 --> 00:28:24.291 are pinned inside of their tasks. 969 00:28:24.541 --> 00:28:26.833 So they cannot be forgotten without 970 00:28:26.833 --> 00:28:27.916 running their destructor. 971 00:28:28.208 --> 00:28:29.916 And what we end up doing is we make a 972 00:28:29.916 --> 00:28:32.583 little linked list of all of these wakers 973 00:28:32.583 --> 00:28:34.500 inside of the individual tasks. 974 00:28:34.750 --> 00:28:36.166 So if you have five tasks that are 975 00:28:36.166 --> 00:28:38.083 waiting on something, each of the wakers 976 00:28:38.083 --> 00:28:40.916 lives inside of that task's memory and is 977 00:28:40.916 --> 00:28:42.500 chained into a single list. 978 00:28:42.750 --> 00:28:44.125 So that for example, when the thing 979 00:28:44.125 --> 00:28:46.416 happens that all five are waiting on, you 980 00:28:46.416 --> 00:28:47.791 can go through and either wake the next 981 00:28:47.791 --> 00:28:49.916 one or you can wake all of them because 982 00:28:49.916 --> 00:28:51.125 they are all waiting on 983 00:28:51.125 --> 00:28:52.583 the thing that has happened. 984 00:28:52.666 --> 00:28:53.583 What is inside a waker? 985 00:28:54.041 --> 00:28:55.000 It's a pointer. 986 00:28:55.666 --> 00:28:56.125 What is it? 987 00:28:56.541 --> 00:28:57.250 It's a vtable? 988 00:28:57.250 --> 00:28:58.125 Is it a vtable? 989 00:28:58.416 --> 00:28:59.208 I think it's a vtable 990 00:28:59.208 --> 00:29:01.291 and a pointer to the thing. 991 00:29:01.291 --> 00:29:02.291 So basically it's something-- 992 00:29:02.333 --> 00:29:02.791 So you're talking about 993 00:29:02.791 --> 00:29:04.416 the standard type from Rust. 994 00:29:05.208 --> 00:29:07.166 Well, the container is standard. 995 00:29:07.375 --> 00:29:09.666 The executor is responsible for providing 996 00:29:09.666 --> 00:29:11.208 what the contents of a waker is. 997 00:29:11.708 --> 00:29:13.708 So the raw waker is something that has a 998 00:29:13.708 --> 00:29:14.750 bunch of vtable functions 999 00:29:14.750 --> 00:29:16.208 and a base pointer in it. 1000 00:29:16.625 --> 00:29:18.791 The contract in Rust is basically in that 1001 00:29:18.791 --> 00:29:21.041 context struct that gets passed to 1002 00:29:21.041 --> 00:29:22.166 futures when they're polled. 1003 00:29:22.583 --> 00:29:25.083 The executor has a way of getting a waker 1004 00:29:25.083 --> 00:29:27.125 that is relevant for the executor you're 1005 00:29:27.125 --> 00:29:28.125 running on, but it's 1006 00:29:28.125 --> 00:29:29.333 kind of a blind interface. 1007 00:29:29.958 --> 00:29:31.750 So every executor defines its own waker. 1008 00:29:32.000 --> 00:29:34.291 So an embassy waker and a Tokio waker are 1009 00:29:34.291 --> 00:29:36.416 not the same, but they have the same like 1010 00:29:36.416 --> 00:29:39.041 opaque contract, if that makes sense. 1011 00:29:40.416 --> 00:29:41.458 Yeah, and the waker is basically like a 1012 00:29:41.458 --> 00:29:44.041 callback that takes a task and moves it 1013 00:29:44.041 --> 00:29:46.208 into the ready state for the executor. 1014 00:29:46.208 --> 00:29:47.375 So it tells the executor, 1015 00:29:47.791 --> 00:29:49.583 hey, this task of yours is ready. 1016 00:29:49.833 --> 00:29:50.458 Whenever you get a 1017 00:29:50.458 --> 00:29:51.541 chance, go check on them. 1018 00:29:51.833 --> 00:29:53.250 You mentioned that it can't be dropped 1019 00:29:53.250 --> 00:29:55.708 without its destructor being run, but 1020 00:29:55.708 --> 00:29:57.333 what about mem forget? 1021 00:29:57.875 --> 00:29:59.416 That's the whole existence. 1022 00:29:59.416 --> 00:30:00.500 You wrote "Pin and Suffering." 1023 00:30:01.000 --> 00:30:03.375 So the whole point of pin is that it is 1024 00:30:03.375 --> 00:30:05.833 impossible to forget something without 1025 00:30:05.833 --> 00:30:07.291 running the destructor of it. 1026 00:30:07.291 --> 00:30:08.791 So pin makes sure that something is 1027 00:30:08.791 --> 00:30:10.041 stable and in place. 1028 00:30:10.708 --> 00:30:13.625 And it means that you can't forget it 1029 00:30:13.875 --> 00:30:15.333 because you never have 1030 00:30:15.333 --> 00:30:16.625 ownership of it again. 1031 00:30:16.625 --> 00:30:19.083 So in most cases, you either box pin it, 1032 00:30:19.083 --> 00:30:20.625 which only gives you a mute ref, which 1033 00:30:20.625 --> 00:30:22.250 means you can't run forget 1034 00:30:22.250 --> 00:30:23.958 on it, or it'll be leaked. 1035 00:30:24.250 --> 00:30:25.750 So it will exist forever without 1036 00:30:25.750 --> 00:30:27.291 destructor running, and that's fine. 1037 00:30:27.708 --> 00:30:29.208 But for stack full pinning, like when you 1038 00:30:29.208 --> 00:30:32.250 call the pin macro, it hides, it rebinds 1039 00:30:32.250 --> 00:30:33.333 the same name and 1040 00:30:33.333 --> 00:30:35.041 basically hides the item from you. 1041 00:30:35.333 --> 00:30:36.875 So you can't call mem forget because you 1042 00:30:36.875 --> 00:30:37.708 need to have the own 1043 00:30:37.708 --> 00:30:39.416 thing to call mem forget. 1044 00:30:39.416 --> 00:30:41.041 So you can mem forget the reference to 1045 00:30:41.041 --> 00:30:43.833 it, but that still allows the original 1046 00:30:43.833 --> 00:30:45.916 item, which is now like has a nameless 1047 00:30:45.916 --> 00:30:48.000 existence to still run the 1048 00:30:48.000 --> 00:30:49.166 destructor at the end of scope. 1049 00:30:49.541 --> 00:30:50.958 Sure, I know I wrote about it James. 1050 00:30:51.916 --> 00:30:52.666 It was a while ago. 1051 00:30:52.958 --> 00:30:54.916 So you're right to remind me, but there's 1052 00:30:54.916 --> 00:30:57.250 no mention of forget in either my piece 1053 00:30:57.416 --> 00:30:59.125 or the official documentation for pin. 1054 00:30:59.125 --> 00:31:00.625 This is why like the whole point of pin 1055 00:31:00.625 --> 00:31:01.958 is that is something 1056 00:31:01.958 --> 00:31:03.500 I hadn't heard before. 1057 00:31:03.791 --> 00:31:04.916 So that's why I'm surprised. 1058 00:31:04.916 --> 00:31:05.166 Interesting. 1059 00:31:05.541 --> 00:31:05.750 Yeah. 1060 00:31:06.208 --> 00:31:06.416 Yeah. 1061 00:31:06.666 --> 00:31:07.875 I mean, it's not the whole point. 1062 00:31:07.875 --> 00:31:09.500 It is one of the major points of pin. 1063 00:31:10.250 --> 00:31:11.833 Pin does two things. 1064 00:31:11.833 --> 00:31:13.041 It makes sure that the item can't be 1065 00:31:13.041 --> 00:31:14.000 moved and it makes sure 1066 00:31:14.000 --> 00:31:15.375 the item can't be forgotten. 1067 00:31:15.625 --> 00:31:17.250 As I understand it, the two main things. 1068 00:31:17.625 --> 00:31:19.375 I think the docs for pin even talk about 1069 00:31:19.375 --> 00:31:20.958 intrusive stack full linked list. 1070 00:31:21.250 --> 00:31:22.541 I should have put a screenshot in here 1071 00:31:22.541 --> 00:31:24.208 too, but I think the docs for pin 1072 00:31:24.208 --> 00:31:25.208 actually has like, 1073 00:31:25.208 --> 00:31:26.416 "What can you do with pin? 1074 00:31:26.708 --> 00:31:28.083 You can use intrusive linked lists 1075 00:31:28.208 --> 00:31:30.041 because it lets you do this!" 1076 00:31:30.041 --> 00:31:32.458 And yes, it's very spooky, but these are 1077 00:31:32.458 --> 00:31:33.250 the kind of guarantees 1078 00:31:33.250 --> 00:31:34.500 that you can expect with pin. 1079 00:31:34.750 --> 00:31:36.583 So when we have our list of wakers-- 1080 00:31:36.625 --> 00:31:38.458 Fact check, they do not talk about 1081 00:31:38.458 --> 00:31:39.250 intrusive linked list. 1082 00:31:39.666 --> 00:31:41.166 They talk about no std context where you 1083 00:31:41.166 --> 00:31:42.416 don't have access to the standard library 1084 00:31:42.416 --> 00:31:43.541 or allocation in general. 1085 00:31:43.833 --> 00:31:45.000 I'd have to look, it might be at the pin 1086 00:31:45.000 --> 00:31:46.166 module level instead 1087 00:31:46.166 --> 00:31:48.625 of the pin type level. 1088 00:31:49.125 --> 00:31:50.333 I think someone wrote that. 1089 00:31:50.333 --> 00:31:51.000 I'd have to go find it. 1090 00:31:51.041 --> 00:31:51.833 You are correct. 1091 00:31:52.250 --> 00:31:53.208 I was wrong. 1092 00:31:53.791 --> 00:31:55.791 In std::pin, the module itself, it's 1093 00:31:55.791 --> 00:31:57.333 talking about self-referential types and 1094 00:31:57.333 --> 00:31:58.208 intrusive data structures. 1095 00:31:58.625 --> 00:31:58.875 Yeah. 1096 00:31:58.875 --> 00:32:00.708 I talked to boats about it, because yeah, 1097 00:32:01.041 --> 00:32:02.166 as boats was interesting, because it's 1098 00:32:02.166 --> 00:32:02.916 exactly the kind of 1099 00:32:02.916 --> 00:32:04.000 thing you can do with pin. 1100 00:32:04.666 --> 00:32:04.875 Yeah. 1101 00:32:05.083 --> 00:32:06.958 So we have all of these tasks and we go 1102 00:32:06.958 --> 00:32:08.666 where do these wakers live? 1103 00:32:08.708 --> 00:32:10.791 They live in the tasks wherever they 1104 00:32:10.791 --> 00:32:13.791 exist, because we know that the future 1105 00:32:14.208 --> 00:32:15.500 that the task is running is pinned. 1106 00:32:15.875 --> 00:32:18.041 And so we can pin items inside of that 1107 00:32:18.041 --> 00:32:20.375 task and they exist until they don't. 1108 00:32:20.375 --> 00:32:22.541 And then if we cancel the task and the 1109 00:32:22.541 --> 00:32:23.458 future falls out of 1110 00:32:23.458 --> 00:32:24.958 scope, we run the destructor. 1111 00:32:25.541 --> 00:32:27.708 And when we run the destructor, we remove 1112 00:32:27.708 --> 00:32:28.708 the item from the list. 1113 00:32:29.208 --> 00:32:30.875 So even though we have this list, we know 1114 00:32:30.875 --> 00:32:32.541 that anything that on the list is valid, 1115 00:32:33.000 --> 00:32:33.750 because if it wasn't 1116 00:32:33.750 --> 00:32:35.000 valid, we would have removed it. 1117 00:32:35.375 --> 00:32:38.250 And anyone who is on the list must exist 1118 00:32:38.458 --> 00:32:40.416 because to create something to attach it 1119 00:32:40.416 --> 00:32:41.166 to the list, it had 1120 00:32:41.166 --> 00:32:42.375 to exist at that point. 1121 00:32:42.375 --> 00:32:43.791 And we know that if it still exists 1122 00:32:43.791 --> 00:32:44.750 there, then it hasn't 1123 00:32:44.750 --> 00:32:46.291 become invalid at any point. 1124 00:32:46.291 --> 00:32:48.458 So we're safe to assume that no matter 1125 00:32:48.458 --> 00:32:50.125 how spooky following all these pointers 1126 00:32:50.125 --> 00:32:52.750 is, it must be valid because we can rely 1127 00:32:52.750 --> 00:32:54.208 on pin as long as no one's 1128 00:32:54.208 --> 00:32:55.750 done any unsafe incorrectly. 1129 00:32:56.375 --> 00:32:57.500 In safe Rust, it's safe 1130 00:32:57.500 --> 00:32:58.458 to assume these things. 1131 00:32:58.875 --> 00:33:00.458 And similarly, if we drop the whole 1132 00:33:00.458 --> 00:33:02.458 WaitQueue the job of dropping the 1133 00:33:02.458 --> 00:33:04.375 WaitQueue means running down the list and 1134 00:33:04.375 --> 00:33:06.083 removing everyone from the list. 1135 00:33:06.166 --> 00:33:07.916 And this is why it has to be a doubly 1136 00:33:07.916 --> 00:33:09.708 linked list and not a singly linked list, 1137 00:33:10.041 --> 00:33:11.083 because every node has to 1138 00:33:11.083 --> 00:33:12.291 be able to remove itself. 1139 00:33:12.875 --> 00:33:14.333 So it has to be able to like, if it 1140 00:33:14.333 --> 00:33:16.083 decides I'm gonna drop myself, I have to 1141 00:33:16.083 --> 00:33:17.666 grab my two buddies to the left and right 1142 00:33:17.666 --> 00:33:18.958 of me, tie them back 1143 00:33:18.958 --> 00:33:20.958 together, and then drop myself out. 1144 00:33:21.375 --> 00:33:22.791 Otherwise, we could do some really cool 1145 00:33:22.791 --> 00:33:23.791 lock free programming. 1146 00:33:24.000 --> 00:33:25.916 But since the nodes have to be able to 1147 00:33:25.916 --> 00:33:28.458 remove themselves from the list, and we 1148 00:33:28.458 --> 00:33:30.333 don't wanna change their order, it has to 1149 00:33:30.333 --> 00:33:31.291 be a doubly linked list. 1150 00:33:31.583 --> 00:33:33.666 Well, do you need to maintain the 1151 00:33:33.666 --> 00:33:34.708 structure of the list? 1152 00:33:35.166 --> 00:33:36.000 Could you just not care 1153 00:33:36.000 --> 00:33:36.833 about all the pointer? 1154 00:33:36.833 --> 00:33:38.541 You'd just navigate it in one direction 1155 00:33:39.083 --> 00:33:39.916 and then free everything? 1156 00:33:40.875 --> 00:33:41.791 Hard maybe, you'd have to 1157 00:33:41.791 --> 00:33:43.125 go ask Vyukov about that. 1158 00:33:43.416 --> 00:33:43.625 Okay. 1159 00:33:44.416 --> 00:33:45.833 So Vyukov is the person who writes a lot 1160 00:33:45.833 --> 00:33:47.250 of those lock free data structures. 1161 00:33:47.250 --> 00:33:47.833 The answer is maybe. 1162 00:33:48.083 --> 00:33:49.583 There are cases where you can use it. 1163 00:33:49.625 --> 00:33:51.000 It wouldn't be unwind safe anymore. 1164 00:33:51.250 --> 00:33:52.666 If you panic in the middle of that, 1165 00:33:52.666 --> 00:33:53.791 you're in a very bad place. 1166 00:33:54.250 --> 00:33:55.708 So maybe that's the reason. 1167 00:33:55.708 --> 00:33:57.000 Yeah, yeah, yeah. 1168 00:33:57.000 --> 00:33:58.708 Unwind safe and panic safety as a whole. 1169 00:33:58.958 --> 00:34:01.041 Yeah, that's a topic for another chat. 1170 00:34:01.375 --> 00:34:02.708 Another podcast, really. 1171 00:34:02.833 --> 00:34:04.083 (Laughs) 1172 00:34:04.291 --> 00:34:05.708 Pin guarantees we can't skip the drop. 1173 00:34:06.000 --> 00:34:08.166 If we drop, we remove ourselves, or we 1174 00:34:08.166 --> 00:34:09.541 remove the whole list, great. 1175 00:34:09.750 --> 00:34:11.583 Then it doesn't really matter that these 1176 00:34:11.583 --> 00:34:13.458 things, they don't have lifetimes that we 1177 00:34:13.458 --> 00:34:16.416 can super explain to the borrow checker, 1178 00:34:16.416 --> 00:34:18.541 but as unsafe programmers, we say it 1179 00:34:18.541 --> 00:34:20.583 exists as long as it exists. 1180 00:34:21.208 --> 00:34:23.875 And then that's the fulfilling of the 1181 00:34:23.875 --> 00:34:25.291 unsafe guarantees there. 1182 00:34:25.291 --> 00:34:26.916 That's our safety comment 1183 00:34:26.916 --> 00:34:28.583 is we know it's load bearing. 1184 00:34:29.041 --> 00:34:31.000 But I made a crate for this called 1185 00:34:31.000 --> 00:34:33.791 Pinlist Very unimaginatively named 1186 00:34:33.791 --> 00:34:36.375 because it takes pinned items and puts 1187 00:34:36.375 --> 00:34:37.125 them in a linked list. 1188 00:34:37.333 --> 00:34:39.125 The way it works is you usually have your 1189 00:34:39.125 --> 00:34:40.666 list in some kind of static. 1190 00:34:41.125 --> 00:34:42.666 This becomes your anchor point. 1191 00:34:42.666 --> 00:34:44.833 You have a global static in your project 1192 00:34:44.833 --> 00:34:46.750 that says, this is the list where a 1193 00:34:46.750 --> 00:34:48.375 variable list of items will go. 1194 00:34:48.833 --> 00:34:50.000 You go, it lives right here. 1195 00:34:50.000 --> 00:34:51.125 It's a big flag in the sand 1196 00:34:51.125 --> 00:34:52.750 for everyone to go find it. 1197 00:34:52.958 --> 00:34:54.791 And then every time you have something 1198 00:34:54.791 --> 00:34:57.291 you wanna add to that list, that can live 1199 00:34:57.291 --> 00:34:59.166 inside of a task, or even it could live 1200 00:34:59.166 --> 00:35:00.708 inside of the stack. 1201 00:35:01.250 --> 00:35:02.166 And you say, I'm gonna 1202 00:35:02.166 --> 00:35:03.166 make a node right here. 1203 00:35:03.416 --> 00:35:05.041 And it has a header with my linked list 1204 00:35:05.041 --> 00:35:07.208 pointers and whatever data that I want. 1205 00:35:07.458 --> 00:35:08.291 And all the data is the 1206 00:35:08.291 --> 00:35:09.750 same kind across the array. 1207 00:35:09.958 --> 00:35:12.583 And we're gonna chain it onto this list. 1208 00:35:12.583 --> 00:35:14.291 So when I wanna push something onto this 1209 00:35:14.291 --> 00:35:17.916 list, I go to the list, I chain it onto 1210 00:35:17.916 --> 00:35:20.791 this, and I create my node item. 1211 00:35:21.000 --> 00:35:22.083 So actually what I do is 1212 00:35:22.083 --> 00:35:23.791 I pin it in place first. 1213 00:35:24.208 --> 00:35:25.875 Then after it's pinned, you can attach 1214 00:35:25.875 --> 00:35:27.500 the pinned item onto the list. 1215 00:35:27.666 --> 00:35:29.500 And then it exists on that list until 1216 00:35:29.500 --> 00:35:31.416 either someone removes it or it removes 1217 00:35:31.416 --> 00:35:33.500 itself by dropping the item. 1218 00:35:33.958 --> 00:35:36.000 This is really, really neat because it 1219 00:35:36.000 --> 00:35:37.416 means that tasks can lend 1220 00:35:37.625 --> 00:35:39.791 their ephemeral data to the list. 1221 00:35:40.333 --> 00:35:41.875 So if you say, this is a socket that 1222 00:35:41.875 --> 00:35:44.958 holds whatever, and I need one here, 1223 00:35:45.458 --> 00:35:47.416 depending on how many tasks you have, you 1224 00:35:47.416 --> 00:35:48.958 don't need to go and fudge this number of 1225 00:35:48.958 --> 00:35:49.958 what's the perfect min 1226 00:35:49.958 --> 00:35:51.708 max number or whatever. 1227 00:35:51.708 --> 00:35:53.708 Anywhere you create one, it exists. 1228 00:35:54.125 --> 00:35:56.333 And you don't necessarily need to worry 1229 00:35:56.333 --> 00:35:57.916 about them because if they exist at 1230 00:35:57.916 --> 00:35:59.916 different stages of the tasks and things 1231 00:35:59.916 --> 00:36:01.666 like that, you always know there's enough 1232 00:36:01.666 --> 00:36:04.000 room because if it exists in the task, 1233 00:36:04.416 --> 00:36:05.750 there must be storage for it. 1234 00:36:06.125 --> 00:36:07.041 Therefore, if it exists in 1235 00:36:07.041 --> 00:36:08.500 the list, it's good to use. 1236 00:36:09.000 --> 00:36:10.708 But wait, I just said I'm gonna put 1237 00:36:10.708 --> 00:36:12.333 something in a static and then I'm gonna 1238 00:36:12.333 --> 00:36:13.708 point to non-static 1239 00:36:13.708 --> 00:36:15.583 data from that static. 1240 00:36:15.833 --> 00:36:18.000 And that's like Rust's whole thing that 1241 00:36:18.000 --> 00:36:19.875 you're really not supposed to be able to 1242 00:36:19.875 --> 00:36:22.541 do that because you're taking items that 1243 00:36:22.541 --> 00:36:24.208 have a lifetime that does not live as 1244 00:36:24.208 --> 00:36:26.208 long as static and you're storing them in 1245 00:36:26.208 --> 00:36:27.166 a static and then 1246 00:36:27.166 --> 00:36:28.875 calling that static lifetime. 1247 00:36:29.291 --> 00:36:30.875 How do we do that? 1248 00:36:31.291 --> 00:36:32.416 And the answer is it's unsafe. 1249 00:36:32.625 --> 00:36:34.458 Like we use unsafe code to do that, but 1250 00:36:34.458 --> 00:36:38.458 we can put a safe exterior on interiorly 1251 00:36:38.458 --> 00:36:40.333 unsafe code because that's how all 1252 00:36:40.333 --> 00:36:42.791 abstractions in Rust work is you limit 1253 00:36:42.791 --> 00:36:44.333 the blast radius and then you 1254 00:36:44.333 --> 00:36:45.625 put a safe outer shell on it. 1255 00:36:45.625 --> 00:36:47.333 And then you say, anyone who uses this in 1256 00:36:47.333 --> 00:36:49.250 safe code never has to worry about 1257 00:36:49.250 --> 00:36:50.333 unsafey because I've done 1258 00:36:50.333 --> 00:36:52.041 all the spooky stuff inside. 1259 00:36:52.583 --> 00:36:54.000 The trick here that I didn't really 1260 00:36:54.000 --> 00:36:56.375 mention is that you can only access the 1261 00:36:56.375 --> 00:36:58.833 items on the list while you're holding a 1262 00:36:58.833 --> 00:37:00.666 blocking mutex, not an 1263 00:37:00.666 --> 00:37:02.541 async mutex, a blocking mutex. 1264 00:37:02.916 --> 00:37:04.791 And what this means is that when you add 1265 00:37:04.791 --> 00:37:07.000 stuff or remove stuff, you have to hold 1266 00:37:07.000 --> 00:37:09.333 the mutex so you can access the list and 1267 00:37:09.333 --> 00:37:11.208 add or remove something from it. 1268 00:37:11.208 --> 00:37:13.125 Or if you wanna run down all the items, 1269 00:37:13.125 --> 00:37:15.625 like I wanna iterate over all my sockets, 1270 00:37:16.166 --> 00:37:18.000 you need to be holding a mutex for the 1271 00:37:18.000 --> 00:37:20.333 whole time that you are running across 1272 00:37:20.333 --> 00:37:23.833 that list because the mutex acts not only 1273 00:37:23.833 --> 00:37:26.750 as mediating exclusive access, so like 1274 00:37:26.750 --> 00:37:28.291 being able to do mutable things to each 1275 00:37:28.291 --> 00:37:30.666 item on the list, it's also preventing 1276 00:37:30.666 --> 00:37:32.125 you from adding or 1277 00:37:32.125 --> 00:37:33.833 dropping anything to that list. 1278 00:37:34.208 --> 00:37:36.458 So an item can't drop itself off the list 1279 00:37:36.750 --> 00:37:38.708 if the mutex is already being held. 1280 00:37:39.000 --> 00:37:40.375 Yeah, I was gonna ask, well, what's 1281 00:37:40.375 --> 00:37:41.541 preventing you from doing that? 1282 00:37:41.750 --> 00:37:44.166 Does it just throw, not throw, but panic? 1283 00:37:44.666 --> 00:37:45.250 How does it check, does 1284 00:37:45.250 --> 00:37:46.208 it block indefinitely? 1285 00:37:46.583 --> 00:37:48.125 Well, it's just a blocking mutex. 1286 00:37:48.125 --> 00:37:50.000 So if you try and get the mutex in your 1287 00:37:50.000 --> 00:37:52.541 destructor, it's just gonna block until 1288 00:37:52.541 --> 00:37:54.000 it's able to get that mutex. 1289 00:37:54.500 --> 00:37:56.291 So if someone's iterating over it, you 1290 00:37:56.291 --> 00:37:57.041 have to wait until they're done 1291 00:37:57.041 --> 00:37:58.708 iterating, they release the mutex, then 1292 00:37:58.708 --> 00:37:59.833 the destructor can grab the 1293 00:37:59.833 --> 00:38:02.250 mutex, remove itself, and go on. 1294 00:38:02.250 --> 00:38:03.208 But the code just blocks 1295 00:38:03.208 --> 00:38:04.666 if you try and do this. 1296 00:38:04.708 --> 00:38:05.458 Yeah, is there any 1297 00:38:05.458 --> 00:38:06.458 provision against deadlocks? 1298 00:38:06.916 --> 00:38:07.250 Yep. 1299 00:38:07.250 --> 00:38:09.041 So the way you access mutex, like I'm 1300 00:38:09.041 --> 00:38:10.291 looking at the API right now, and there's 1301 00:38:10.291 --> 00:38:13.958 a with lock method on a node handle, and 1302 00:38:13.958 --> 00:38:15.875 it takes closure and an FnOnce. 1303 00:38:16.333 --> 00:38:18.750 What if you drop another node handle in 1304 00:38:18.750 --> 00:38:20.750 there, then you have a deadlock, right? 1305 00:38:21.708 --> 00:38:24.833 You would, if you're accessing it from 1306 00:38:24.833 --> 00:38:26.000 the node itself, let me 1307 00:38:26.000 --> 00:38:26.750 go back to the picture. 1308 00:38:27.166 --> 00:38:28.458 If you're accessing it from the node 1309 00:38:28.458 --> 00:38:30.625 itself, you typically in your local scope 1310 00:38:30.625 --> 00:38:32.291 only have access to your own node because 1311 00:38:32.291 --> 00:38:33.083 you've declared it there. 1312 00:38:33.458 --> 00:38:35.000 The only thing you have in other scopes 1313 00:38:35.000 --> 00:38:36.750 or your only way of seeing other nodes is 1314 00:38:36.750 --> 00:38:39.958 through the Pinlist method that gives you 1315 00:38:39.958 --> 00:38:41.000 access to the other items. 1316 00:38:41.333 --> 00:38:42.750 I think, yes, you probably could make it 1317 00:38:42.750 --> 00:38:44.833 deadlock in some way if you like, I will 1318 00:38:44.833 --> 00:38:46.416 make two nodes here that I have local 1319 00:38:46.416 --> 00:38:48.375 context to, and while I'm holding the 1320 00:38:48.375 --> 00:38:50.833 mutex, I will try and drop the node. 1321 00:38:51.041 --> 00:38:52.583 But actually with pinning, it's very 1322 00:38:52.583 --> 00:38:54.333 difficult to manually drop something 1323 00:38:54.958 --> 00:38:56.458 because you don't have 1324 00:38:56.458 --> 00:38:57.708 access to the original item. 1325 00:38:57.708 --> 00:38:59.541 So the only way to really make things 1326 00:38:59.541 --> 00:39:01.291 trigger drop is to make 1327 00:39:01.291 --> 00:39:02.250 them fall out of scope. 1328 00:39:02.708 --> 00:39:04.041 And to make them fall out of scope, you 1329 00:39:04.041 --> 00:39:05.375 have to return, and if you're inside a 1330 00:39:05.375 --> 00:39:07.083 scope where you're doing this stuff, you 1331 00:39:07.083 --> 00:39:08.833 can't really return from the scope while 1332 00:39:08.833 --> 00:39:09.500 you're doing something 1333 00:39:09.500 --> 00:39:10.708 else, if that makes sense. 1334 00:39:11.291 --> 00:39:14.000 You probably could, in a very convoluted 1335 00:39:14.000 --> 00:39:15.666 way, shoot yourself in the 1336 00:39:15.666 --> 00:39:16.791 foot and cause it to deadlock. 1337 00:39:17.083 --> 00:39:19.500 It's not particularly easy to do with the 1338 00:39:19.500 --> 00:39:21.000 interfaces I've given you here. 1339 00:39:21.083 --> 00:39:22.833 Well, I guess the easy case is just two 1340 00:39:22.833 --> 00:39:25.333 nested calls of with lock, but then it's 1341 00:39:25.333 --> 00:39:26.791 pretty visible, like the 1342 00:39:26.791 --> 00:39:27.541 wouldn't pass code review. 1343 00:39:27.541 --> 00:39:28.291 Yeah, yeah. 1344 00:39:28.291 --> 00:39:30.041 You'd be in a blocking context and 1345 00:39:30.041 --> 00:39:31.916 calling, you'd be calling lock to get 1346 00:39:31.916 --> 00:39:32.875 access to the thing you 1347 00:39:32.875 --> 00:39:34.250 already have access to. 1348 00:39:34.833 --> 00:39:36.083 So it would, yeah, you probably could 1349 00:39:36.083 --> 00:39:37.541 deadlock, and at that point, like a std 1350 00:39:37.541 --> 00:39:39.166 mutex, if you try and lock it while it's 1351 00:39:39.166 --> 00:39:40.833 locked, it'll deadlock if 1352 00:39:40.833 --> 00:39:41.791 you're in the same thread. 1353 00:39:41.791 --> 00:39:42.291 If you're at a different 1354 00:39:42.291 --> 00:39:43.291 thread, it will just block. 1355 00:39:43.666 --> 00:39:45.083 If you're in the same thread, it will 1356 00:39:45.083 --> 00:39:47.208 just deadlock because it'll detect that. 1357 00:39:47.541 --> 00:39:48.791 On embedded systems, we don't have the 1358 00:39:48.791 --> 00:39:49.666 operating system locks. 1359 00:39:50.083 --> 00:39:50.583 So when are you 1360 00:39:50.583 --> 00:39:51.583 adding a deadlock detector? 1361 00:39:52.250 --> 00:39:53.583 Just like, what's 1362 00:39:53.583 --> 00:39:53.791 the, 1363 00:39:55.000 --> 00:39:56.541 the answer is I kind of actually do. 1364 00:39:56.750 --> 00:39:58.000 Cause on desktop, if you're in the same 1365 00:39:58.000 --> 00:39:59.333 thread and you lock it again and it would 1366 00:39:59.333 --> 00:40:02.166 deadlock, std mutex will already panic. 1367 00:40:02.166 --> 00:40:03.458 On embedded systems, we don't have std 1368 00:40:03.458 --> 00:40:05.791 mutex, but I have a crate called mutex 1369 00:40:05.791 --> 00:40:06.875 and it uses what's called 1370 00:40:06.875 --> 00:40:08.625 a scoped blocking mutex. 1371 00:40:08.875 --> 00:40:10.541 On embedded systems to handle this, we're 1372 00:40:10.541 --> 00:40:11.750 gonna take like a 1373 00:40:11.750 --> 00:40:12.875 critical section or whatever. 1374 00:40:13.125 --> 00:40:14.583 And if you go to lock it again, we will 1375 00:40:14.583 --> 00:40:15.791 see that it's already locked. 1376 00:40:15.791 --> 00:40:17.250 And so we can do the same deadlock 1377 00:40:17.250 --> 00:40:18.500 detection where it'll just panic. 1378 00:40:18.875 --> 00:40:20.375 So if you deadlock, it will panic, but 1379 00:40:20.375 --> 00:40:22.333 the answer is it's exceedingly hard to 1380 00:40:22.333 --> 00:40:23.000 deadlock unless 1381 00:40:23.000 --> 00:40:24.208 you're trying, I would say. 1382 00:40:24.458 --> 00:40:24.833 All right. 1383 00:40:25.208 --> 00:40:26.625 Well, good thing deadlock detection is 1384 00:40:26.625 --> 00:40:28.416 super easy with a single thread. 1385 00:40:30.166 --> 00:40:30.666 Yeah, yeah. 1386 00:40:30.666 --> 00:40:32.333 And running drop means holding the mutex. 1387 00:40:32.625 --> 00:40:34.583 So actually running the destructor here 1388 00:40:34.583 --> 00:40:35.791 means that if you're not holding the 1389 00:40:35.791 --> 00:40:36.750 mutex, you have to wait. 1390 00:40:37.333 --> 00:40:39.375 And if you're holding the mutex so you 1391 00:40:39.375 --> 00:40:40.708 can drop, you know that there are no 1392 00:40:40.708 --> 00:40:43.333 other live views of the list, which means 1393 00:40:43.333 --> 00:40:44.875 there's no problem because no one can 1394 00:40:44.875 --> 00:40:46.041 have like an item 1395 00:40:46.125 --> 00:40:47.458 spookily pulled from under them. 1396 00:40:48.000 --> 00:40:49.958 And the interface for gaining access to 1397 00:40:49.958 --> 00:40:52.208 this doesn't let you return a reference 1398 00:40:52.208 --> 00:40:54.583 to an item on the list outside of the 1399 00:40:54.583 --> 00:40:56.541 closure of holding the lock, which means 1400 00:40:56.541 --> 00:40:58.500 you can never like return an item beyond 1401 00:40:58.500 --> 00:41:00.250 the actual call, which means all your 1402 00:41:00.250 --> 00:41:01.333 access of the items has to 1403 00:41:01.333 --> 00:41:02.666 be done with the mutex locked. 1404 00:41:03.125 --> 00:41:04.583 You can't just hold on to a reference 1405 00:41:04.583 --> 00:41:06.083 that could get stale because someone 1406 00:41:06.083 --> 00:41:07.916 could decide to drop it, which means you 1407 00:41:07.916 --> 00:41:09.791 do all of your actions immediately 1408 00:41:10.833 --> 00:41:12.500 rather than holding on to 1409 00:41:12.500 --> 00:41:13.541 something and doing it later. 1410 00:41:13.791 --> 00:41:16.500 This feels weird because there's pins so 1411 00:41:16.500 --> 00:41:17.291 I would expect async, 1412 00:41:17.625 --> 00:41:18.958 but no, it's all blocking. 1413 00:41:18.958 --> 00:41:19.416 It's all sickness. 1414 00:41:20.500 --> 00:41:22.000 Yeah, it's correct. 1415 00:41:22.375 --> 00:41:24.500 Yeah, pin is not exclusive to async and 1416 00:41:24.500 --> 00:41:25.875 we do need to do it blocking because 1417 00:41:25.875 --> 00:41:27.500 there's no async drop right now. 1418 00:41:28.291 --> 00:41:30.458 So once we get async drop, I could 1419 00:41:30.458 --> 00:41:32.333 probably loosen this restriction and be 1420 00:41:32.333 --> 00:41:34.333 able to do async drop here where 1421 00:41:34.333 --> 00:41:36.375 something can yield until it's able to 1422 00:41:36.375 --> 00:41:37.416 remove the item from the list. 1423 00:41:37.666 --> 00:41:38.375 You'd still only be 1424 00:41:38.375 --> 00:41:39.458 able to do it with it held. 1425 00:41:39.708 --> 00:41:40.458 I do actually have 1426 00:41:40.458 --> 00:41:41.625 another variant of this. 1427 00:41:41.875 --> 00:41:42.708 Well, I'll mention at the end. 1428 00:41:42.958 --> 00:41:44.625 If you make all of your items static 1429 00:41:44.625 --> 00:41:47.125 instead of pinned, so that they can never 1430 00:41:47.125 --> 00:41:49.291 be dropped, you actually can use an async 1431 00:41:49.291 --> 00:41:50.916 mutex to this and not worry about it 1432 00:41:50.916 --> 00:41:53.291 because then, items are always live 1433 00:41:53.291 --> 00:41:54.958 because they are static items and they 1434 00:41:54.958 --> 00:41:55.666 can never be dropped. 1435 00:41:56.000 --> 00:41:57.166 And I actually use that in one of the 1436 00:41:57.166 --> 00:41:58.750 libraries I'm gonna mention because we do 1437 00:41:58.750 --> 00:42:00.333 want async for some things 1438 00:42:00.333 --> 00:42:02.000 like this, but you actually can-- 1439 00:42:02.041 --> 00:42:03.833 But then why do you need a linked list if 1440 00:42:03.833 --> 00:42:04.875 it's only static items? 1441 00:42:05.083 --> 00:42:06.500 Like it's just to maintain an order? 1442 00:42:06.625 --> 00:42:08.333 I'll get to it in a second. 1443 00:42:08.958 --> 00:42:11.375 Back to talking about holding non-static 1444 00:42:11.375 --> 00:42:13.875 things in a static item, it's good enough 1445 00:42:13.875 --> 00:42:15.333 because we know that if as long as it's 1446 00:42:15.333 --> 00:42:17.333 on the list, it lives long enough. 1447 00:42:17.541 --> 00:42:18.000 And really static 1448 00:42:18.000 --> 00:42:19.166 doesn't mean lives forever. 1449 00:42:19.625 --> 00:42:21.791 It means how old are you, old enough to 1450 00:42:21.791 --> 00:42:23.625 drink kind of thing, like it's like, 1451 00:42:23.625 --> 00:42:24.583 that's probably a joke about a four 1452 00:42:24.583 --> 00:42:25.583 that's not gonna make a lot of sense. 1453 00:42:25.875 --> 00:42:28.000 So the answer is it just needs to exist 1454 00:42:28.291 --> 00:42:30.375 as long as anyone could possibly want it. 1455 00:42:31.000 --> 00:42:32.083 Sometimes that means forever. 1456 00:42:32.291 --> 00:42:34.041 Sometimes that just means long enough. 1457 00:42:34.833 --> 00:42:36.000 And so that's what we're doing here. 1458 00:42:36.000 --> 00:42:38.083 Everything lives long enough because it 1459 00:42:38.083 --> 00:42:39.541 lives as long as it's on the list. 1460 00:42:39.541 --> 00:42:40.625 And if it's not alive, 1461 00:42:40.625 --> 00:42:41.583 then it's not on the list. 1462 00:42:42.250 --> 00:42:44.208 Static is sometimes code for just owned. 1463 00:42:44.666 --> 00:42:46.291 Like I think if it is owned or 1464 00:42:46.291 --> 00:42:48.500 self-contained or something, it's not 1465 00:42:48.500 --> 00:42:49.500 borrowed from somewhere else. 1466 00:42:49.708 --> 00:42:51.208 So we control this lifetime. 1467 00:42:51.458 --> 00:42:53.333 I really think of it as lives long enough 1468 00:42:53.666 --> 00:42:56.083 because if it's owned, it always lives 1469 00:42:56.083 --> 00:42:56.875 long enough because it 1470 00:42:56.875 --> 00:42:58.500 lives as long as you hold it. 1471 00:42:58.500 --> 00:43:00.208 And if it's in a static and lives 1472 00:43:00.208 --> 00:43:02.166 forever, obviously it lives enough 1473 00:43:02.166 --> 00:43:03.916 because it lives forever and 1474 00:43:03.916 --> 00:43:05.083 forever is always long enough. 1475 00:43:05.500 --> 00:43:06.791 You're right, there's like in between 1476 00:43:06.791 --> 00:43:09.375 cases between owned and like a static 1477 00:43:09.375 --> 00:43:11.250 forever reference where it really does 1478 00:43:11.250 --> 00:43:13.041 mean it lives as long 1479 00:43:13.041 --> 00:43:14.416 as it could ever need to. 1480 00:43:14.666 --> 00:43:15.958 So that's usually how I think of tick 1481 00:43:15.958 --> 00:43:18.458 static is just it lives as long as it 1482 00:43:18.458 --> 00:43:20.000 could possibly ever need to. 1483 00:43:20.625 --> 00:43:21.708 And that means for as long as someone 1484 00:43:21.708 --> 00:43:23.041 knows about it, it exists. 1485 00:43:23.500 --> 00:43:25.541 And for owned things, only one person can 1486 00:43:25.541 --> 00:43:27.541 know about it or as long as the borrow 1487 00:43:27.541 --> 00:43:28.625 lasts and things like that. 1488 00:43:28.625 --> 00:43:30.250 So yeah, I think a good way to think of 1489 00:43:30.250 --> 00:43:32.541 static is it lives as long enough as 1490 00:43:32.541 --> 00:43:34.375 someone could possibly want it to. 1491 00:43:34.375 --> 00:43:35.458 So the reason why you might want 1492 00:43:35.458 --> 00:43:37.416 something like this, both in the pin case 1493 00:43:37.416 --> 00:43:39.458 and in the everything's a static case 1494 00:43:39.458 --> 00:43:41.291 where it's a variable item, it lets you 1495 00:43:41.291 --> 00:43:43.125 do a very cool thing of separating 1496 00:43:43.125 --> 00:43:45.875 ownership of resources from 1497 00:43:45.875 --> 00:43:47.958 a worker of those resources. 1498 00:43:48.666 --> 00:43:50.333 So what I mean by that is because you 1499 00:43:50.333 --> 00:43:52.291 have this flag in the sand where everyone 1500 00:43:52.291 --> 00:43:54.208 can meet, either to add items to the list 1501 00:43:54.208 --> 00:43:56.833 or to access the list, you can have your 1502 00:43:56.833 --> 00:43:59.583 IO worker task independent from all the 1503 00:43:59.583 --> 00:44:01.583 items that are storing things, which 1504 00:44:01.583 --> 00:44:03.166 means you can do cool things with 1505 00:44:03.166 --> 00:44:03.833 different libraries. 1506 00:44:04.125 --> 00:44:05.583 So one library that I've written is 1507 00:44:05.583 --> 00:44:07.291 called cfg-noodle It was 1508 00:44:07.291 --> 00:44:08.333 a silly placeholder name. 1509 00:44:08.625 --> 00:44:08.916 Love that. 1510 00:44:08.958 --> 00:44:10.000 This is one of those things I have a 1511 00:44:10.000 --> 00:44:12.000 habit of adding placeholder names. 1512 00:44:12.208 --> 00:44:13.375 This was originally written because I was 1513 00:44:13.375 --> 00:44:14.375 just noodling around. 1514 00:44:14.375 --> 00:44:14.791 I was trying to figure 1515 00:44:14.791 --> 00:44:16.083 out what to do before it. 1516 00:44:16.083 --> 00:44:17.541 So like on a guitar, when you're noodling 1517 00:44:17.541 --> 00:44:19.958 around, it's just like improv and not 1518 00:44:19.958 --> 00:44:21.125 really doing anything meaningful. 1519 00:44:21.500 --> 00:44:23.583 So I named the repo cfg-noodle because I 1520 00:44:23.583 --> 00:44:24.833 was just noodling around to figure out 1521 00:44:24.833 --> 00:44:25.625 what I wanted to do. 1522 00:44:25.875 --> 00:44:26.875 And then the customer never 1523 00:44:26.875 --> 00:44:28.000 came up with a better name. 1524 00:44:28.000 --> 00:44:29.458 And so now the library is just released 1525 00:44:29.458 --> 00:44:31.541 as cfg-noodle But it does 1526 00:44:31.541 --> 00:44:33.416 things where it holds storage. 1527 00:44:33.791 --> 00:44:35.208 Like you can have a config item that 1528 00:44:35.208 --> 00:44:36.500 exists in all the tasks. 1529 00:44:37.041 --> 00:44:38.958 And then because that storage in the 1530 00:44:38.958 --> 00:44:41.500 config exists on external storage, you 1531 00:44:41.500 --> 00:44:43.708 have one IO worker task that just 1532 00:44:43.708 --> 00:44:45.958 whenever any of the config nodes says, "I 1533 00:44:45.958 --> 00:44:46.958 would like to store data." 1534 00:44:47.041 --> 00:44:48.791 Or at the beginning at boot up, they go, 1535 00:44:48.791 --> 00:44:50.708 "I need to be hydrated with my data." 1536 00:44:50.708 --> 00:44:52.375 They can just raise a flag and the IO 1537 00:44:52.375 --> 00:44:54.208 worker, which is totally separate, can 1538 00:44:54.208 --> 00:44:56.791 just access the external memory, populate 1539 00:44:56.791 --> 00:44:59.083 all the items on the list, or grab the 1540 00:44:59.083 --> 00:45:00.458 items on the list and flush 1541 00:45:00.458 --> 00:45:01.833 them back to external memory. 1542 00:45:02.041 --> 00:45:03.416 So instead of everyone having to hold 1543 00:45:03.416 --> 00:45:05.416 like a reference to things where the 1544 00:45:05.416 --> 00:45:07.125 generics have to be consistent because 1545 00:45:07.125 --> 00:45:08.958 all the items have to be of the same type 1546 00:45:08.958 --> 00:45:10.791 or whatever, you can just say, "Okay, IO 1547 00:45:10.791 --> 00:45:11.958 worker lives over here. 1548 00:45:12.250 --> 00:45:13.833 And then all the nodes live over here. 1549 00:45:13.833 --> 00:45:15.625 And they just exist in the linked list." 1550 00:45:15.625 --> 00:45:17.750 And by having a node that exists in the 1551 00:45:17.750 --> 00:45:19.125 linked list, you get the benefit of 1552 00:45:19.125 --> 00:45:21.541 someone running the IO task for you. 1553 00:45:21.541 --> 00:45:23.291 And your IO task is totally independent 1554 00:45:23.291 --> 00:45:24.625 where it doesn't have to have references 1555 00:45:24.916 --> 00:45:26.791 to however many tasks you have. 1556 00:45:27.083 --> 00:45:29.083 It just says, "I just run down the list 1557 00:45:29.083 --> 00:45:30.875 whenever someone asked me to, and I 1558 00:45:30.875 --> 00:45:32.541 either flush data to the disc or I load 1559 00:45:32.541 --> 00:45:33.541 data from the disc." 1560 00:45:33.541 --> 00:45:34.416 And it works really well. 1561 00:45:34.625 --> 00:45:35.791 And this way you can basically have 1562 00:45:35.791 --> 00:45:37.083 storage for keeping all the 1563 00:45:37.083 --> 00:45:39.125 items cached wherever they are. 1564 00:45:39.500 --> 00:45:41.166 So anywhere where you have the item and 1565 00:45:41.166 --> 00:45:42.708 you would like to have access to it, 1566 00:45:43.166 --> 00:45:44.458 that's where your cache exists. 1567 00:45:44.458 --> 00:45:46.041 So you don't need to figure out exactly 1568 00:45:46.041 --> 00:45:47.250 how much cache I need. 1569 00:45:47.541 --> 00:45:49.666 You just have the right size of cache 1570 00:45:49.833 --> 00:45:51.500 everywhere where you have an item and it 1571 00:45:51.500 --> 00:45:53.208 just exists inside of the task. 1572 00:45:53.208 --> 00:45:54.458 So it's always right sized. 1573 00:45:54.833 --> 00:45:56.708 You don't have to like tune any values to 1574 00:45:56.708 --> 00:45:57.708 figure out how much you need. 1575 00:45:57.833 --> 00:45:58.500 That is really cool. 1576 00:45:58.958 --> 00:45:59.916 Yeah, yeah, yeah. 1577 00:45:59.916 --> 00:46:01.500 This is like a very classic way of doing 1578 00:46:01.500 --> 00:46:02.833 things on embedded systems or kernels. 1579 00:46:03.166 --> 00:46:04.916 Like it's just not usual that you have a 1580 00:46:04.916 --> 00:46:07.000 safe interface to it because the language 1581 00:46:07.000 --> 00:46:09.083 is expressive enough to like not totally 1582 00:46:09.083 --> 00:46:09.875 make the guarantees. 1583 00:46:10.250 --> 00:46:11.625 You still have to write the unsafe under 1584 00:46:11.625 --> 00:46:13.250 the hood, but it can at least express 1585 00:46:13.250 --> 00:46:15.750 that on the exterior so you can use it 1586 00:46:15.750 --> 00:46:17.458 safely, if that makes sense. 1587 00:46:17.666 --> 00:46:19.000 Yeah, you don't have to write any unsafe 1588 00:46:19.000 --> 00:46:20.208 codes to use Pinlist, right? 1589 00:46:20.291 --> 00:46:20.875 Correct, correct. 1590 00:46:21.250 --> 00:46:22.041 Yeah, I've written 1591 00:46:22.041 --> 00:46:23.083 all the unsafe for you. 1592 00:46:23.083 --> 00:46:24.625 So as long as you just use it with its 1593 00:46:24.625 --> 00:46:26.583 public API, it'll always work and you 1594 00:46:26.583 --> 00:46:27.291 won't have to write any 1595 00:46:27.291 --> 00:46:28.500 of your own unsafe code. 1596 00:46:28.541 --> 00:46:31.375 Yeah, that reminds me of the Rust and 1597 00:46:31.375 --> 00:46:34.041 Linux work where they made safe 1598 00:46:34.041 --> 00:46:35.250 interfaces for a bunch of stuff. 1599 00:46:35.541 --> 00:46:36.166 And a bunch of people were 1600 00:46:36.166 --> 00:46:37.291 like, oh, this looks complicated. 1601 00:46:37.750 --> 00:46:38.375 I'll do that one again. 1602 00:46:39.791 --> 00:46:39.833 (Laughing) 1603 00:46:39.833 --> 00:46:41.333 Turns out this was all everything that 1604 00:46:41.333 --> 00:46:42.083 you had to do anyway 1605 00:46:42.083 --> 00:46:42.916 and was just implicit. 1606 00:46:43.500 --> 00:46:44.500 Yeah, yeah, exactly. 1607 00:46:44.958 --> 00:46:46.916 And it's like now we're just annotating 1608 00:46:46.916 --> 00:46:48.666 that and this can never 1609 00:46:48.666 --> 00:46:50.041 go wrong because of that. 1610 00:46:50.291 --> 00:46:51.958 Yeah, we can describe the contract in the 1611 00:46:51.958 --> 00:46:53.333 way that the compiler can enforce. 1612 00:46:53.583 --> 00:46:55.375 Even though we can't describe what's 1613 00:46:55.375 --> 00:46:57.166 going on under the hood in a way that the 1614 00:46:57.166 --> 00:46:58.458 compiler can understand because there's 1615 00:46:58.458 --> 00:47:00.000 pointers and whatever, we can at least 1616 00:47:00.000 --> 00:47:02.083 explain the contract in a way that the 1617 00:47:02.083 --> 00:47:04.000 compiler can enforce, which is super 1618 00:47:04.000 --> 00:47:05.208 useful because the person who knows the 1619 00:47:05.208 --> 00:47:06.583 most about this is the implementer. 1620 00:47:06.833 --> 00:47:07.916 And most of the time the people who know 1621 00:47:07.916 --> 00:47:09.875 the least about it are the users of it. 1622 00:47:09.875 --> 00:47:11.375 And so you wanna protect all of your 1623 00:47:11.375 --> 00:47:13.208 users as long as one maintainer 1624 00:47:13.208 --> 00:47:15.208 understands it and can rely on the 1625 00:47:15.208 --> 00:47:17.000 compiler enforcing that rule. 1626 00:47:17.000 --> 00:47:18.166 That's one of my favorite things to 1627 00:47:18.166 --> 00:47:19.625 explain about Rust, especially when 1628 00:47:19.625 --> 00:47:20.875 people are frustrated about it. 1629 00:47:20.875 --> 00:47:23.666 It's that the number of programs that the 1630 00:47:23.666 --> 00:47:26.541 Rust compiler will accept is very small 1631 00:47:26.916 --> 00:47:28.125 compared to the number of 1632 00:47:28.125 --> 00:47:29.500 programs that are memory safe. 1633 00:47:30.000 --> 00:47:31.791 But that's the compromise we make because 1634 00:47:31.791 --> 00:47:32.833 all the programs that 1635 00:47:32.833 --> 00:47:34.416 are accepted are safe. 1636 00:47:34.916 --> 00:47:36.333 So you don't have to worry about it. 1637 00:47:36.625 --> 00:47:36.833 Exactly. 1638 00:47:37.166 --> 00:47:38.250 And the other place that I'm using this 1639 00:47:38.250 --> 00:47:40.625 is in Ergot, which is my networking or 1640 00:47:40.625 --> 00:47:42.708 message communication library for 1641 00:47:42.708 --> 00:47:44.958 embedded systems, where all of my sockets 1642 00:47:44.958 --> 00:47:46.708 work basically the same way. 1643 00:47:46.708 --> 00:47:48.833 The sockets are things that you hold in 1644 00:47:48.833 --> 00:47:50.750 the tasks that you're using them from. 1645 00:47:51.291 --> 00:47:54.791 And there's IO worker tasks where if you 1646 00:47:54.791 --> 00:47:56.291 have an external interface and a packet 1647 00:47:56.291 --> 00:47:58.708 comes in, it can run through that list, 1648 00:47:58.708 --> 00:48:00.375 find the destination for that packet and 1649 00:48:00.375 --> 00:48:02.541 drop it in the correct socket. 1650 00:48:02.541 --> 00:48:03.708 Or it can run to the end and say, I 1651 00:48:03.708 --> 00:48:05.791 didn't find anyone, send a negative 1652 00:48:05.791 --> 00:48:07.041 acknowledgement back or like 1653 00:48:07.041 --> 00:48:09.166 a NAK and things like that. 1654 00:48:09.166 --> 00:48:10.375 And that way it doesn't 1655 00:48:10.375 --> 00:48:11.750 matter how many sockets you have. 1656 00:48:11.750 --> 00:48:13.541 Or if you go, oh, I only have this socket 1657 00:48:13.541 --> 00:48:16.500 open in this mode, or I only wanna open a 1658 00:48:16.500 --> 00:48:18.500 socket just long enough to send a 1659 00:48:18.500 --> 00:48:20.291 request, get my response, and then 1660 00:48:20.291 --> 00:48:22.708 immediately drop my response because I'm 1661 00:48:22.708 --> 00:48:24.291 only waiting on one response here. 1662 00:48:24.291 --> 00:48:26.166 So you can have ephemeral sockets or 1663 00:48:26.166 --> 00:48:27.833 sockets that live forever or as many as 1664 00:48:27.833 --> 00:48:29.083 you want and things like that. 1665 00:48:29.083 --> 00:48:31.000 And the IO worker task that's taking 1666 00:48:31.000 --> 00:48:33.500 these incoming packets just goes, hey, 1667 00:48:33.500 --> 00:48:34.625 look at the header, figure out the 1668 00:48:34.625 --> 00:48:35.791 destination, is that here? 1669 00:48:35.791 --> 00:48:36.875 Do we have a socket like this? 1670 00:48:36.875 --> 00:48:37.375 Yes, we do. 1671 00:48:37.666 --> 00:48:39.250 Drop it in and then move on. 1672 00:48:39.500 --> 00:48:41.750 And because any socket can then just send 1673 00:48:41.750 --> 00:48:44.000 directly in the outgoing queue, it means 1674 00:48:44.000 --> 00:48:46.333 that now you don't have to tightly 1675 00:48:46.333 --> 00:48:47.583 coordinate in all of these things. 1676 00:48:47.583 --> 00:48:49.291 And you get the same kind of feeling 1677 00:48:49.291 --> 00:48:51.250 interface that an operating system socket 1678 00:48:51.250 --> 00:48:52.666 library gives you, but 1679 00:48:52.666 --> 00:48:54.416 it's all in user space. 1680 00:48:54.750 --> 00:48:56.458 Like it's all just linked together in a 1681 00:48:56.458 --> 00:48:57.583 way that keeps this reasonable. 1682 00:48:58.000 --> 00:48:59.000 And then you get that as like a firmware 1683 00:48:59.000 --> 00:49:00.541 developer, you get something that feels 1684 00:49:00.541 --> 00:49:02.625 like something an operating system would 1685 00:49:02.625 --> 00:49:04.541 give you, but is actually 1686 00:49:04.541 --> 00:49:06.208 totally done in firmware. 1687 00:49:06.208 --> 00:49:07.625 There's a little bit of code behind the 1688 00:49:07.625 --> 00:49:09.375 library, but there's no magic behind the 1689 00:49:09.375 --> 00:49:10.166 operating system because 1690 00:49:10.166 --> 00:49:11.291 there is no operating system. 1691 00:49:12.166 --> 00:49:13.750 Like I said, it's a pretty handy pattern 1692 00:49:13.750 --> 00:49:14.583 and it's how I've been 1693 00:49:14.583 --> 00:49:15.875 building a bunch of libraries. 1694 00:49:15.875 --> 00:49:17.291 This is like a streak that I've been on 1695 00:49:17.291 --> 00:49:19.500 is I kind of went back and looked at a 1696 00:49:19.500 --> 00:49:21.083 WaitQueue and went, "I wish we had that 1697 00:49:21.083 --> 00:49:22.708 for more general stuff because I could 1698 00:49:22.708 --> 00:49:24.000 use that for a bunch of stuff." 1699 00:49:24.000 --> 00:49:25.916 And then I started using it in ergot, 1700 00:49:25.916 --> 00:49:27.916 then I started using it in cfg-noodle and 1701 00:49:27.916 --> 00:49:29.208 then eventually someone was talking to me 1702 00:49:29.208 --> 00:49:30.375 about it and was like, 1703 00:49:30.375 --> 00:49:31.708 "Hey, how would I do this?" 1704 00:49:31.708 --> 00:49:33.000 And I go, "You should use this pattern. 1705 00:49:33.208 --> 00:49:34.458 Here's a linked to like 1706 00:49:34.458 --> 00:49:36.041 500 lines of unsafe code. 1707 00:49:36.041 --> 00:49:37.375 Just do what I do and 1708 00:49:37.375 --> 00:49:38.291 also hold it right." 1709 00:49:38.291 --> 00:49:40.291 And I went, "Well, that's not great." 1710 00:49:40.291 --> 00:49:41.916 So I eventually extracted Pinlist. 1711 00:49:42.166 --> 00:49:42.958 There's actually, Pinlist 1712 00:49:42.958 --> 00:49:44.500 only does one of the two tricks. 1713 00:49:44.875 --> 00:49:47.500 So both cfg-noodle and ergot take this 1714 00:49:47.500 --> 00:49:49.916 one step further where Pinlist requires 1715 00:49:49.916 --> 00:49:51.333 that all the items in the 1716 00:49:51.333 --> 00:49:52.833 linked list are of the same type. 1717 00:49:53.458 --> 00:49:54.916 So when you iterate over them, you get 1718 00:49:54.916 --> 00:49:56.625 the same type on the same place. 1719 00:49:57.000 --> 00:49:59.291 But actually ergot and cfg-noodle and also 1720 00:49:59.291 --> 00:50:00.541 async executors that do 1721 00:50:00.541 --> 00:50:02.416 this kind of stuff don't. 1722 00:50:02.416 --> 00:50:05.333 Every item has a common header, but then 1723 00:50:05.333 --> 00:50:07.125 you have basically like a 1724 00:50:07.125 --> 00:50:09.416 dyn object below that pointer. 1725 00:50:10.208 --> 00:50:12.000 So all those sockets that I talked about, 1726 00:50:12.000 --> 00:50:13.416 they all have differently type 1727 00:50:13.416 --> 00:50:15.375 deserializers because they're given the 1728 00:50:15.375 --> 00:50:17.833 message, but one socket might be of this 1729 00:50:17.833 --> 00:50:18.708 type and one socket 1730 00:50:18.708 --> 00:50:19.666 might be of this type. 1731 00:50:20.000 --> 00:50:20.833 And same with configuration. 1732 00:50:21.041 --> 00:50:22.791 One configuration element might be of 1733 00:50:22.791 --> 00:50:24.916 this type and one configuration element 1734 00:50:24.916 --> 00:50:25.916 might be of this type. 1735 00:50:25.916 --> 00:50:27.416 And what you do is you actually have a 1736 00:50:27.416 --> 00:50:29.000 vtable in all of the nodes. 1737 00:50:29.625 --> 00:50:31.916 And so the IO worker that's coming along 1738 00:50:31.916 --> 00:50:33.541 can go, "Is this for you?" 1739 00:50:33.916 --> 00:50:34.750 "Yes, it is for you." 1740 00:50:35.000 --> 00:50:36.458 "Cool, I'm gonna call your vtable method 1741 00:50:36.458 --> 00:50:39.125 with like a raw pointer and just do it." 1742 00:50:39.125 --> 00:50:40.666 So the second stage of this is actually 1743 00:50:40.666 --> 00:50:43.458 like really spooky type erasure, which is 1744 00:50:43.458 --> 00:50:45.041 I think someone actually sort of figured 1745 00:50:45.041 --> 00:50:47.916 out how to get dyn trait working in 1746 00:50:47.916 --> 00:50:49.625 Pinlist I'd have to check and see if that 1747 00:50:49.625 --> 00:50:50.500 PR is still working 1748 00:50:50.833 --> 00:50:51.833 and if it's still sound. 1749 00:50:52.083 --> 00:50:54.583 But the vibe of what cfg-noodle and ergot 1750 00:50:54.708 --> 00:50:57.291 are actually doing is basically having a 1751 00:50:57.291 --> 00:50:59.500 linked list of dyn trait items so that 1752 00:50:59.500 --> 00:51:00.541 you can hand them a packet 1753 00:51:00.541 --> 00:51:02.250 and go, "Did you like that?" 1754 00:51:02.250 --> 00:51:04.125 And then they have at least a consistent 1755 00:51:04.125 --> 00:51:05.291 interface to say, "Yes, I 1756 00:51:05.291 --> 00:51:06.541 did and I took that message." 1757 00:51:06.916 --> 00:51:08.583 Or, "No, I didn't, I don't want this." 1758 00:51:08.916 --> 00:51:10.291 And that way the IO worker, that's all 1759 00:51:10.291 --> 00:51:11.541 the IO worker needs to know. 1760 00:51:11.541 --> 00:51:11.958 They don't need to 1761 00:51:11.958 --> 00:51:13.041 know what it did with it. 1762 00:51:13.291 --> 00:51:14.125 They just wanted to know, 1763 00:51:14.125 --> 00:51:15.791 "Did I deliver it to you or not?" 1764 00:51:16.416 --> 00:51:17.750 So that's the spooky second half. 1765 00:51:17.750 --> 00:51:19.791 It's a whole nother episode, but just 1766 00:51:19.791 --> 00:51:22.291 storing items is a pretty neat technique. 1767 00:51:22.666 --> 00:51:24.000 And then you can take that neat technique 1768 00:51:24.000 --> 00:51:25.250 a little further at 1769 00:51:25.250 --> 00:51:26.166 some point if you want. 1770 00:51:26.541 --> 00:51:28.625 So with items of different sizes, you 1771 00:51:28.625 --> 00:51:30.000 still need some sort of 1772 00:51:30.000 --> 00:51:31.208 dynamic memory allocation. 1773 00:51:32.041 --> 00:51:32.666 You do not. 1774 00:51:32.708 --> 00:51:33.166 You don't. 1775 00:51:33.291 --> 00:51:33.791 Because they are 1776 00:51:33.791 --> 00:51:35.291 stored inside of the task. 1777 00:51:35.541 --> 00:51:37.250 And the task knows what type they, that's 1778 00:51:37.250 --> 00:51:38.750 the trade off is the list doesn't know 1779 00:51:38.750 --> 00:51:40.041 what type they are, but the 1780 00:51:40.041 --> 00:51:41.583 nodes know what type they are. 1781 00:51:41.833 --> 00:51:43.708 So when you create the item inside the 1782 00:51:43.708 --> 00:51:46.083 task, it knows it's the specific item 1783 00:51:46.083 --> 00:51:48.250 that it is, but then it just has the 1784 00:51:48.250 --> 00:51:50.458 common header that's at the top of the 1785 00:51:50.458 --> 00:51:52.958 item and that exists in the list, but 1786 00:51:52.958 --> 00:51:54.000 they can be of different 1787 00:51:54.000 --> 00:51:56.125 sizes in every single task. 1788 00:51:56.708 --> 00:51:59.416 Right, this can all happen on the stack 1789 00:51:59.416 --> 00:51:59.916 is what you're 1790 00:51:59.916 --> 00:52:01.500 saying, or yeah, or static. 1791 00:52:01.958 --> 00:52:03.958 Yep, in embedded for tasks, we actually 1792 00:52:03.958 --> 00:52:06.083 statically allocate our tasks usually. 1793 00:52:06.375 --> 00:52:08.291 So they exist as basically like reusable 1794 00:52:08.291 --> 00:52:12.750 boxes for specific tasks because in Rust 1795 00:52:12.750 --> 00:52:13.875 now we can figure out 1796 00:52:13.875 --> 00:52:15.166 the size of a future. 1797 00:52:15.458 --> 00:52:16.916 And if we can figure out the size of a 1798 00:52:16.916 --> 00:52:19.083 future when we're creating the task, we 1799 00:52:19.083 --> 00:52:21.166 can make a perfectly sized static that is 1800 00:52:21.166 --> 00:52:23.250 the size of this specific task. 1801 00:52:23.583 --> 00:52:24.791 And then we just say we can have one of 1802 00:52:24.791 --> 00:52:25.875 those or five of those or 1803 00:52:25.875 --> 00:52:26.875 10 of those or whatever. 1804 00:52:27.208 --> 00:52:30.666 So it's kind of magic in: it is stored in 1805 00:52:30.666 --> 00:52:32.000 a static, but it's the compiler figuring 1806 00:52:32.000 --> 00:52:33.833 out how large that static needs to be. 1807 00:52:34.166 --> 00:52:34.750 And then you don't 1808 00:52:34.750 --> 00:52:35.541 have to think about it. 1809 00:52:35.541 --> 00:52:37.000 And you just know that it's bounded like, 1810 00:52:37.291 --> 00:52:38.958 okay, I can have up to four of these 1811 00:52:38.958 --> 00:52:39.958 exist at the same time. 1812 00:52:39.958 --> 00:52:41.541 So we are kind of doing that like fixed 1813 00:52:41.541 --> 00:52:43.375 upper bound kind of thing, but most of 1814 00:52:43.375 --> 00:52:46.000 it's hidden in the executor's plumbing 1815 00:52:46.000 --> 00:52:48.541 where you don't have to care, but you are 1816 00:52:48.541 --> 00:52:51.166 still at compile time deciding how much 1817 00:52:51.166 --> 00:52:53.166 memory you need for all of your tasks. 1818 00:52:53.666 --> 00:52:55.125 But the thing is these sockets or 1819 00:52:55.125 --> 00:52:57.875 whatever could just be one leaf future 1820 00:52:57.875 --> 00:52:59.541 state inside of that whole task. 1821 00:53:00.125 --> 00:53:01.916 So if you have like part of the time I 1822 00:53:01.916 --> 00:53:03.458 have this socket open and another part of 1823 00:53:03.458 --> 00:53:05.208 the time I have this socket open, you 1824 00:53:05.208 --> 00:53:06.500 don't need to reserve space for two 1825 00:53:06.500 --> 00:53:07.958 sockets because the compiler is smart 1826 00:53:07.958 --> 00:53:10.250 enough to tell these two states of the 1827 00:53:10.250 --> 00:53:12.125 future are never live at the same time. 1828 00:53:12.666 --> 00:53:13.458 So I just need like, 1829 00:53:13.750 --> 00:53:14.791 kind of like an enum. 1830 00:53:15.000 --> 00:53:17.583 I only need the superset max size, but 1831 00:53:17.583 --> 00:53:20.000 not the sum of all size, just the max of 1832 00:53:20.000 --> 00:53:21.708 all leaf states of a future. 1833 00:53:22.333 --> 00:53:25.083 That reminds me of an episode where we 1834 00:53:25.083 --> 00:53:27.833 argued a little bit about how easy it is 1835 00:53:27.833 --> 00:53:28.833 to write async code. 1836 00:53:28.833 --> 00:53:30.375 And I think in the comments someone said, 1837 00:53:30.625 --> 00:53:31.625 "Amos, actually you're wrong. 1838 00:53:32.000 --> 00:53:33.875 Like the tooling is good now, it's fine." 1839 00:53:34.333 --> 00:53:34.583 So. 1840 00:53:34.583 --> 00:53:35.458 It got better. 1841 00:53:35.458 --> 00:53:36.125 There's still some stuff 1842 00:53:36.125 --> 00:53:37.250 where there's rough edges. 1843 00:53:37.250 --> 00:53:38.416 And I think both of us are on the same 1844 00:53:38.416 --> 00:53:40.000 page of like, we know 1845 00:53:40.000 --> 00:53:41.208 the places where it sucks. 1846 00:53:42.083 --> 00:53:43.458 And we know the places where it's 1847 00:53:43.458 --> 00:53:44.208 actually pretty good. 1848 00:53:44.208 --> 00:53:45.958 And we know that the set of places where 1849 00:53:45.958 --> 00:53:47.541 it's pretty good is getting bigger over 1850 00:53:47.541 --> 00:53:49.416 time, but there's still like a non-zero 1851 00:53:49.416 --> 00:53:51.833 set of items that kind of sucks to debug, 1852 00:53:52.083 --> 00:53:53.541 but yeah, it is getting better. 1853 00:53:53.958 --> 00:53:55.666 So how many of those libraries, well, 1854 00:53:55.666 --> 00:53:57.708 those crates are you maintaining now? 1855 00:53:58.000 --> 00:54:00.583 How big is the dependency tree that is 1856 00:54:00.583 --> 00:54:03.958 your own under your network stack? 1857 00:54:04.750 --> 00:54:05.458 The network stack... 1858 00:54:05.875 --> 00:54:07.041 I'd have to look at the dependencies. 1859 00:54:07.041 --> 00:54:08.333 So there's three libraries, basically 1860 00:54:08.333 --> 00:54:09.083 where I'm using this trick. 1861 00:54:09.333 --> 00:54:10.458 I listed all of them. 1862 00:54:10.458 --> 00:54:13.083 There's ergot, cfg-noodle and Pinlist. 1863 00:54:13.250 --> 00:54:15.333 Yeah, but it's not the only pattern, the 1864 00:54:15.333 --> 00:54:16.458 only like idea you've 1865 00:54:16.458 --> 00:54:17.458 turned into a crate, right? 1866 00:54:17.458 --> 00:54:19.041 You've been publishing a bunch of those. 1867 00:54:19.125 --> 00:54:20.666 Of this one so far, yes. 1868 00:54:21.000 --> 00:54:22.333 Cause I really only started doing this a 1869 00:54:22.333 --> 00:54:24.166 couple months ago, but I'm sure I will 1870 00:54:24.166 --> 00:54:26.041 have more by the time that probably 1871 00:54:26.041 --> 00:54:28.125 anyone's listening to this, but the main 1872 00:54:28.125 --> 00:54:31.541 two dependencies to make this happen are 1873 00:54:31.541 --> 00:54:34.666 Cordyceps, which we talked about in "What 1874 00:54:34.666 --> 00:54:35.458 are you syncing about?" 1875 00:54:35.458 --> 00:54:36.958 It's the intrusive linked list library 1876 00:54:36.958 --> 00:54:39.000 with the best name ever, cause it's named 1877 00:54:39.000 --> 00:54:41.500 after a fungus that invades your brain 1878 00:54:41.500 --> 00:54:42.500 and makes you do stuff. 1879 00:54:42.500 --> 00:54:43.833 So the intrusive linked list 1880 00:54:43.833 --> 00:54:45.166 library is called Cordyceps. 1881 00:54:45.375 --> 00:54:46.708 That's from Eliza and I guess 1882 00:54:46.708 --> 00:54:48.000 I help out with that library. 1883 00:54:48.250 --> 00:54:49.791 So it's Eliza's library, but I 1884 00:54:49.791 --> 00:54:51.416 have made a lot of PRs to it. 1885 00:54:51.458 --> 00:54:51.625 Right. 1886 00:54:51.875 --> 00:54:53.958 And that's used also by maitake-sync. 1887 00:54:54.250 --> 00:54:55.833 So like WaitQueue and WaitCell are using 1888 00:54:55.833 --> 00:54:57.125 Cordyceps under the hood as well. 1889 00:54:57.416 --> 00:54:58.666 And then all three crates that I named 1890 00:54:58.666 --> 00:54:59.791 are using this for the 1891 00:54:59.791 --> 00:55:00.541 intrusive linked list. 1892 00:55:01.000 --> 00:55:03.083 Then for that blocking mutex, there's a 1893 00:55:03.083 --> 00:55:06.583 crate called mutex, which I also own with 1894 00:55:06.583 --> 00:55:08.375 Eliza and that's used in 1895 00:55:08.375 --> 00:55:09.166 all three of those crates. 1896 00:55:09.875 --> 00:55:10.916 Actually, no, I don't think it's used in 1897 00:55:10.916 --> 00:55:12.791 cfg-noodle because like I 1898 00:55:12.791 --> 00:55:13.750 said, we made them static. 1899 00:55:13.750 --> 00:55:15.208 So we don't need a blocking mutex. 1900 00:55:15.208 --> 00:55:16.083 We just say that 1901 00:55:16.083 --> 00:55:17.208 every node lives forever. 1902 00:55:17.833 --> 00:55:19.958 So it's not using that, but those are the 1903 00:55:19.958 --> 00:55:21.541 only two main building blocks. 1904 00:55:22.000 --> 00:55:24.000 And I think Cordyceps has no direct 1905 00:55:24.000 --> 00:55:25.500 dependencies or maybe just one or two 1906 00:55:25.500 --> 00:55:28.041 small helpers and the mutex library also, 1907 00:55:28.458 --> 00:55:29.333 I think it depends on 1908 00:55:29.333 --> 00:55:30.291 what feature you use. 1909 00:55:30.291 --> 00:55:31.500 Like on embedded systems, you want the 1910 00:55:31.500 --> 00:55:32.541 critical section crate. 1911 00:55:32.833 --> 00:55:34.458 And then on desktop, it's just using std 1912 00:55:34.458 --> 00:55:35.875 mutex if I remember correctly. 1913 00:55:36.125 --> 00:55:38.208 So it's not a deep dependency list. 1914 00:55:38.416 --> 00:55:40.625 In fact, Cordyceps has no dependencies. 1915 00:55:40.958 --> 00:55:43.250 It has like three dev dependencies and a 1916 00:55:43.250 --> 00:55:44.833 loom feature that enables loom and 1917 00:55:44.833 --> 00:55:46.791 tracing for testing I'm assuming. 1918 00:55:46.875 --> 00:55:47.291 That makes sense. 1919 00:55:47.541 --> 00:55:49.083 And then the mutex crate probably is just 1920 00:55:49.083 --> 00:55:51.458 based on like, it's generic over, you 1921 00:55:51.458 --> 00:55:53.125 tell me how we can make a mutex because 1922 00:55:53.125 --> 00:55:55.500 that way on desktop, you can do one thing 1923 00:55:55.500 --> 00:55:56.291 and on embedded, you 1924 00:55:56.291 --> 00:55:57.041 can do another thing. 1925 00:55:57.875 --> 00:55:59.166 So it probably has a couple of 1926 00:55:59.166 --> 00:56:00.458 dependencies depending on which feature 1927 00:56:00.458 --> 00:56:02.375 you enable, but in practice, you probably 1928 00:56:02.375 --> 00:56:04.625 are only ever enabling one of them. 1929 00:56:04.833 --> 00:56:06.666 So it'll be like either the Cortex M 1930 00:56:06.666 --> 00:56:10.083 crate or critical section or std, maybe 1931 00:56:10.083 --> 00:56:11.416 actually just critical section with the 1932 00:56:11.416 --> 00:56:12.250 std feature enabled. 1933 00:56:12.833 --> 00:56:14.416 So you don't really need a lot of deps to 1934 00:56:14.416 --> 00:56:16.458 do this because like the depth of the 1935 00:56:16.458 --> 00:56:18.125 unsafe code that you need here is pretty 1936 00:56:18.125 --> 00:56:19.958 shallow just for the data structures. 1937 00:56:20.583 --> 00:56:22.166 And then what you do with it on top of 1938 00:56:22.166 --> 00:56:23.333 that is sort of the question. 1939 00:56:23.333 --> 00:56:25.375 So like cfg-noodle then relies on the 1940 00:56:25.375 --> 00:56:27.291 CBOR library, which is a serialization 1941 00:56:27.291 --> 00:56:29.166 and deserialization library, which is how 1942 00:56:29.166 --> 00:56:30.916 you implement those V table methods for 1943 00:56:30.916 --> 00:56:32.625 like loading and storing and then some 1944 00:56:32.625 --> 00:56:34.375 other like storage libraries for how you 1945 00:56:34.375 --> 00:56:35.333 store stuff externally. 1946 00:56:35.750 --> 00:56:38.541 Ergot at that point, ergot-base is where 1947 00:56:38.541 --> 00:56:40.333 I do all of this stuff and then ergot's 1948 00:56:40.333 --> 00:56:41.208 like the nicer higher 1949 00:56:41.208 --> 00:56:42.500 level interface over this. 1950 00:56:42.916 --> 00:56:44.666 I'd have to look, ergot's like 10,000 1951 00:56:44.666 --> 00:56:45.750 lines of code at this point 1952 00:56:45.958 --> 00:56:47.958 and then the deps I don't know. 1953 00:56:48.250 --> 00:56:49.625 I'd have to look at, I don't know exactly 1954 00:56:49.625 --> 00:56:51.500 what my load bearing deps are there, but 1955 00:56:51.500 --> 00:56:52.958 there's more there because I'm doing 1956 00:56:52.958 --> 00:56:55.291 stuff like postcard and serde and I'm 1957 00:56:55.291 --> 00:56:56.125 using a bunch of crates from 1958 00:56:56.125 --> 00:56:57.666 the postcard ecosystem in there. 1959 00:56:57.666 --> 00:56:59.166 So those probably have a bunch of 1960 00:56:59.166 --> 00:57:00.375 recursive deps as well. 1961 00:57:00.791 --> 00:57:01.791 Yeah, for the actual just like this 1962 00:57:01.791 --> 00:57:03.458 pattern, you need like two libraries. 1963 00:57:03.750 --> 00:57:05.208 You could totally do it yourself if you 1964 00:57:05.208 --> 00:57:06.916 wanted, but Cordyceps is a really good 1965 00:57:06.916 --> 00:57:08.625 library and the mutex library is exactly 1966 00:57:08.625 --> 00:57:09.583 what you want for this. 1967 00:57:09.625 --> 00:57:12.041 So probably two in most cases, unless 1968 00:57:12.041 --> 00:57:14.250 you're doing additional spooky things, 1969 00:57:14.250 --> 00:57:15.208 but then it's just whatever. 1970 00:57:15.791 --> 00:57:17.708 Just looking forward to see the James 1971 00:57:17.708 --> 00:57:19.666 cinematic universe... grow! 1972 00:57:21.875 --> 00:57:24.583 Yeah, yeah, yeah. 1973 00:57:24.583 --> 00:57:26.208 We'll get to ergot probably next season. 1974 00:57:26.208 --> 00:57:27.500 I was thinking about doing ergot for this 1975 00:57:27.500 --> 00:57:29.416 last episode, but I could 1976 00:57:29.416 --> 00:57:31.333 do a season on ergot so. 1977 00:57:31.416 --> 00:57:33.125 We both decided it was too much. 1978 00:57:33.125 --> 00:57:33.500 Yeah, yeah. 1979 00:57:33.958 --> 00:57:35.458 Yeah, so maybe season three is just gonna 1980 00:57:35.458 --> 00:57:37.166 be the ergot season at this point. 1981 00:57:37.583 --> 00:57:37.833 Exactly. 1982 00:57:38.541 --> 00:57:39.166 I think that's a good end. 1983 00:57:39.541 --> 00:57:42.541 (Upbeat Music) 1984 00:57:49.125 --> 00:57:50.625 This episode is sponsored by Depot: 1985 00:57:50.625 --> 00:57:51.916 the build acceleration platform 1986 00:57:51.916 --> 00:57:52.791 that's on a mission to 1987 00:57:52.791 --> 00:57:54.375 make all builds near instant. 1988 00:57:54.625 --> 00:57:55.833 If you're tired of watching your builds 1989 00:57:55.833 --> 00:57:56.750 and GitHub actions crawl 1990 00:57:56.750 --> 00:57:57.458 like the modern day 1991 00:57:57.458 --> 00:57:58.625 equivalent of paint drying, 1992 00:57:58.958 --> 00:57:59.833 give Depot's GitHub 1993 00:57:59.833 --> 00:58:01.000 Actions runners a try. 1994 00:58:01.375 --> 00:58:02.541 They're up to 10X faster 1995 00:58:02.541 --> 00:58:03.875 with unlimited concurrency, 1996 00:58:03.875 --> 00:58:05.291 faster caching, support for 1997 00:58:05.291 --> 00:58:06.666 Linux, macOS, and Windows, 1998 00:58:06.666 --> 00:58:07.541 and they plug right into 1999 00:58:07.541 --> 00:58:08.458 other Depot optimizations 2000 00:58:08.750 --> 00:58:10.333 like accelerated container image builds 2001 00:58:10.333 --> 00:58:11.750 and remote caching for Bazel, 2002 00:58:12.041 --> 00:58:13.833 Turborepo, Gradle, and more. 2003 00:58:14.208 --> 00:58:15.166 Depot was built by developers 2004 00:58:15.166 --> 00:58:16.333 who were tired of wasting time 2005 00:58:16.333 --> 00:58:17.625 waiting on builds instead of shipping. 2006 00:58:17.916 --> 00:58:18.750 It's made for teams 2007 00:58:18.750 --> 00:58:19.666 that wanna move faster 2008 00:58:19.666 --> 00:58:20.666 and stay focused on 2009 00:58:20.666 --> 00:58:21.708 what actually matters. 2010 00:58:22.000 --> 00:58:23.333 That's why companies like PostHog 2011 00:58:23.333 --> 00:58:24.333 use Depot to cut build 2012 00:58:24.333 --> 00:58:25.666 times from over three hours 2013 00:58:25.666 --> 00:58:26.875 to just three minutes, 2014 00:58:26.875 --> 00:58:27.833 saving tens of thousands 2015 00:58:27.833 --> 00:58:29.083 of build hours every week. 2016 00:58:29.375 --> 00:58:30.333 Start your free 7 2017 00:58:30.333 --> 00:58:31.458 day trial at depot.dev 2018 00:58:31.458 --> 00:58:32.541 and let them know we sent you.