Let's get going. Good morning. Good morning. It's Friday, end of the week.   The actual standing, Jason, I'm looking at you.  How long will everybody have to wait for Jason to stand up? Hold up. Dachi, too. Oh, I don't know, man. Put me in a tough spot. Dachi? Your leg hurts. See, try that excuse next time. That's more effective. All right, everybody sit down. Should have class standing one day, just to see if people are. OK, so today we're going to talk about log-structured file systems. This is the last file system that we're going to talk about. And that's like a sign that everything that happened in file systems that was interesting happened before or around 1990. Because here we are, we're coming ever close to the present. We spent Wednesday in the 80s talking about FFS, and now we're on to a new decade of innovation in computer file systems. But we're going to talk about LFS. LFS is a fun design for file systems, so it should be kind of a fun lecture. There's some fun history here as well that plays into this story. So Simon 3 is on its way out. We're just working out the last kinks with it. If you've taken all your late days, I think if I calculated correctly, a Simon 2 must be turned in by tomorrow at midnight. So that's it. And we're working on the assignment 2 solution. I kind of hacked it together yesterday using the old code, and it seems to work, but I'm going to bang out a little bit more in case you guys would like to use that going forward on a Simon 3. If you don't have, look, I think it's a really baller move to keep you in your own code base. Maybe we'll have some awards at the end of class for people who have not chosen to use the solution size. But at the same time, if you don't want to spend your time working on the Simon 3, debugging all of your Simon 2 problems, and your Simon 2 isn't really in a strong working state, then I would suggest that you grab the solution and just move on. Lick your wounds, take your losses, and kind of move forward. So we talked about the Berkeley FAST file system on Wednesday. So anybody have any questions about the Berkeley FAST file system? Really kind of beautiful file system design, very intimate with the properties of disks. Any questions about FFS? Going once. Going twice. Can I ask a question on about the Berkeley FAST system? I guess. In Windows FAST 3.2 system, you cannot transfer. Right. Why do we need the limitation? We don't. And it would be great if it didn't exist. Is there any similar limitation? No, actually. So there probably was at some time in earlier versions of Linux systems. Look, early file system designs made assumptions about the size of files. And those assumptions seemed reasonable at the time. So if it's 1980 or 1990 in your state-of-the-art machine has 128 megabytes of RAM, then maybe you're thinking, ah, a 4 gigabyte file, that sounds like plenty. So no, there's no reason for that limitation. That's what some people would consider to be a bug or a mal feature or something like that. But there's no good reason for it, right? And it frustrates and irritates people who have to work with those file systems, right? I'm trying to remember that I was reading about UFS because FFS has kind of evolved into UFS now, the Unix file system. And I think new versions of the Unix file system can support file sizes up to a word I hadn't even heard of before. It's like nanobytes or something. So I think that's like lots of bytes, right? It's not quite like Google bytes. But it's good to move in that direction, right? So now I think people will start to assume that files might get really big, right?  And now that's a serious limitation on those file systems. So I think new file system designs are kind of like, OK, look, it's kind of like the longer IP addresses, IPv6, right? It's like, look, we ran out of IP addresses once. So now let's create enough IP addresses so that we can assign every atom in the universe its own IP address, right? And then we'll have enough, we think, right? Unless some atoms start to want two, and then you're going to have an issue, right?  All right, any questions on FFS before we talk a little bit about that? Yeah, what's that? Yeah, but I mean, that's yes and no, right? No, I think that's where that comes from, but I don't know why, right? Because on an indirect block file system, right, you can essentially, the file size, you could use 8 bytes on the file system to store the file size. That's not the end of the world, right? You know, ooh, I'm wasting 4 bytes so that I can have a file bigger than that. And depending on, remember we talked about the indirect block mechanism that allows us to associate many data blocks with a single file. So depending on how I set that up, I can potentially support really, really massive files, right? So if I have these quadruply indirect blocks, right, then every time I add a layer of indirection, I'm adding almost an exponent to my file size, right? So they can get big pretty quickly. Any other, good questions? Any other questions about file systems in general, FFS in particular? You know what, I have enough to cover today. I'm not really gonna go through the FFS review. I'll just let you guys look over this yourself. These are just copies of the old slides, right? So remember, FFS did both seek planning, right, with this idea of cylinder groups, trying to keep things that are related, almost like its whole little mini file system on each cylinder group, right? So without leaving the cylinder group, without moving the head very far, I can allocate inodes, I can allocate data blocks, I can, you know, hopefully put things in directories because hopefully the directory that I'm operating on is in my cylinder group itself, right? So it's almost like breaking the disk up into little mini file systems that are all trying to be located on a single cylinder group so I don't have to move the heads, right? And then, you know, FFS also did this funky rotational planning stuff, right? So disk geometry information was stored in the super block and used to try to actually figure out, you know, when I was done reading a certain sector, a certain block on a particular track, where was the head gonna be next, right? So there were a lot of like really delicate, intricate optimizations that FFS did to try to improve the performance of slow disks, okay? And we were kind of, at least I was kind of simultaneously amazed and bothered by this. All right, so yeah, any more questions about FFS? I wanna get to LFS because LFS is fun, all right? Okay, so again, we talked about FFS circa 1982, right?  I was three years old. You know, you guys, we just don't have memories of computers that are at all, right? Okay, so now fast forward. It's now 1991, right? So now we're getting into at least the distant future. Some of you may have been born by that point, although probably some of you haven't been. So what's different about 1991 from 1982? Well, I collected some information from the internet. So a big hit in 1982, Eye of the Tiger, you know? Great song, actually. 1991, everything I do, I do it for you. I don't know, like, maybe not my favorite song. I was gonna play this in class, but then I was like, no, I didn't really wanna play Brian Adams at this hour. It's just too early for that kind of stuff. All right, a hit movie in 1982, Gandhi, 1991, Silence of the Land. So we're getting darker, right?  So this is different. But okay, what about disks, right? What about disks and computers? What's changed about disks and computers, do you think? From 1982 to 1991, right?  You know about the personal computer revolution. So what's happened during this time period, right? So, disband width is improving a lot. Remember, we talked last time about how FFS was actually built for systems that couldn't stream data across the bus fast enough to actually keep up with the rotational movement of the disk, right? So now this problem is being addressed, and we actually can stream reads or writes to the disk much, much faster, okay? Assuming something, okay? Computers have more memory, right? You know, the big fancy machines that these guys were hacking on at that time were like 128 megabytes of memory. Wow, that was like a new feature. And actually, there was like, it was 64 bytes on one bus and then 64 bytes on another. There was something hacky you had to do to actually even jam 128 megabytes of memory. Now I think your phone has like eight times that much memory, right? So this is, these were the state of the art service at the time. What about disk seek times? Who thinks they know what happened to disk seek times? 1982, 1991. Maybe slightly better, but still really slow, okay? So you've got this improvement in disk bandwidth, but that assumes that you don't have to, you know, bounce the heads all over the disk, right? This is new, I'm gonna walk down an aisle. Not doing it very well, I gotta practice. Okay, so this is assuming, disk bandwidth's going up, but this is assuming that you don't have to move the heads. If you gotta move the heads, then you have this great improvement in bandwidth, but it's being wasted because I'm bouncing all over the disk, okay? All right, so, and here's the question that computer scientists at Stanford were asking themselves. So look, I still have seeks and seeks are terrible, right? Seeks are what make the disk slow, okay? But I've got a lot of growing bandwidth and I wanna get to that, that's frustrating me because I've got these seeks that are preventing me from really utilizing all this new bandwidth that's being added to these devices, okay? And of course, you know, the best way to improve performance is to take advantage of that bandwidth, right? So I've gotta solve this pesky seek issue, okay? And I've got a bunch of spare memory, right? Systems are being built with more and more memory, okay? So what do you guys think I'm gonna do here? Cash, all right? I can use a cash, right? Again, this is one of our system design principles. I'm gonna make a big slow thing look faster by using the cash, right? We've talked about this over and over. So I'm gonna put this, so now I've got this bigger cash on my system, more memory, and so I can cash the heck out of the file system. And this is gonna fix everything, right? I'm gonna use the cash. It's gonna fix everything. It's gonna be awesome. I've got this buffer cash thing. It's gonna be huge. And it's just gonna soak up all the traffic to the disk, right? It's problem solved, right? This is a short lecture today, you know? Everybody can go home, we're ready for the weekend, okay? All right, so I've got this huge cash, right? And what is that cash gonna soak up, right? What is that cash we think gonna be great for soaking up? It shouldn't, it should mean that I should barely have to do any what.  Reads don't modify data, right? So with the cash, once I put a block into the cash, that cash should just sit there soaking up all the reads and I'm golden, okay? So caches should just improve the performance of reads dramatically, right? Why doesn't this apply to writes?  Because if they don't get to the disk, then the data's actually not on the disk, right? And if the system fails or whatever, then I'm gonna have an issue, right? So this starts to become this, you know, this identification of the fact that caches are great for reads, right? Caches are fantastic for soaking up all this read traffic, but they are not as effective with writes because the writes have to go to disk, it's just that frustrating part about disk where we actually have to send data to them if we expect it to be preserved, right? I wish we could eliminate that feature. That however, the cash is also gonna help us with writes, right, and what the cash is gonna allow us to do is it's gonna allow us to coalesce writes in memory, okay? Until we can get, you know, a bunch of writes together and then we can do them all at once, right? So the cash does help with writes a little bit. So like writing one byte, right? You know, doing 10 one byte writes to one block shouldn't cause 10 writes to the disk, right? It should cause eventually one write to the disk, okay? So the cash helps with writes, but not to the degree that it helps with reads, okay? So we've been talking about sort of standard file system designs for a couple of weeks and I want you guys to just for a minute and I know you guys, I know that, you know, at least with me, you know, Leisure and, you know, reading magazines and, you know, imbibing certain kinds of beverages helps me forget things anyway, but let's, just for a minute, please try to forget everything that you've learned about file system design, right? So, and answer this simple question. I wanna avoid doing seeks, right? The cash is gonna help me with reads. The cash is gonna soak up reads, but I've still gotta do writes. So what's the best way to avoid seeks when I'm writing data? What's the best way? I've got a bunch of writes to do and I don't wanna do seeks. So what do I do? What do I do? What's the most obvious thing to do? I don't wanna do seeks. So what do I do? I just don't do seeks, right? I write everything to basically one place on the disk. Now that's the same place. This is entirely right, because then I would lose a lot of data, right? But I just try to keep the heads in the exactly same spot and I just keep adding stuff, right? I just keep adding stuff to the same location and I do the smallest seek possible. So I write 4K and then I get to the next block and then I write the next block and I just lay them out sequentially on disk, okay? So I'm just gonna write everything to the same place. And this is the key insight behind log-structured file systems. We'll talk about how they work, right? So there's two guys at Stanford. Mendo Rosenblum on the bottom was a, we believe it was a PhD student at the time. He's now a faculty member there and this is John Oosterhout who's an extremely well-known faculty member at Stanford. So they had this insight, which is if we want to avoid doing seeks, we should just stop doing them, right? And we should write everything to one place in the disk and then we'll deal with the consequences of that decision, right? We'll spend the rest of today talking about what the consequences of that decision are, right? Well, what there, okay? So, okay, so again, main idea. I treat the disk as a single append-only log, right? Log-structured file systems. All the rights are appended to the end of that log, okay? Anytime I write anything, it goes to the end of the log, okay? It sounds like a great idea, right? You know, easy, now I've just got this big log with a bunch of junk in it, right? So how do we actually do this, right? Okay, so let's look at what happens. So let me refresh your memory a little bit about what happens with a normal write, okay? So this is a normal write on a standard file system that has data structures spread all over the disk. It's not this log-structured file system thing. It's a normal file. So, okay, I wanna do a write, okay? And I wanna change one byte in my file, right? What do I normally have to do, okay? Well, I have to do a series of seeks, reads, and writes, okay? The first thing I might have to do is I might have to do a seek to read the INO map, right? Figure out where the data, where the INO corresponding to this INO number is, right? Now I've gotta do another seek to read the INO, right? So I've gotta move to some other place to actually read the INO to figure out where the data blocks are, right? Now I've gotta seek to the right data block that I need to modify, right? This actually might involve a couple of seats if I'm using a multi-level index, but let's just pretend it's just one more seek, right, to get to the data block, and I'm gonna do a write, right? And now I might need to update the metadata stored in the INO, like the modification time. So I'm gonna have to seek back and do another write to the INO, okay? So this is four seeks, two reads, two writes, okay? And let's look at how it looks on disk, right? So I seek to somewhere, and let's say my INO map, it's like way at one end of my disk where I know where to find it, so I do the read there, okay? Now I do a seek, I find the INO that I wanted, I read the INO, now I find the data block I wanted, somebody else I've got a, this is my second seek, and now I'm gonna seek back and I'm gonna modify that INO, right?  We've talked about ways to try to optimize where the stuff ends up, right? But still, like the optimization strategies that we've looked at aren't perfect, and they're still gonna lead to seeks, right? Okay, so let's say, okay, let's say that I'm gonna, now let's say that we have this nice cache, okay? And the cache is essentially gonna soak up reads, meaning that reads are gonna hit the cache. Let's just assume the worst, best case scenario here, and that the reads that we need to do are all in the cache already, so I don't need to read them again, so that means that the INO map is cached, so I don't need to read that off the disk, I can find that in memory. The INO itself is also cached, right? So I can avoid doing these first two seeks, right? But I still have, you know, two operations to do on disk, and some potentially large seek between these two structures, right? And again, I mean, a lot of file systems do a lot of work to try to put these things close together on disk, right? But the log-structured file system does an even better job, because again, all the writes go to the end of the log, okay? So this is my LFS file system, and this is the log I'm gonna tell you exactly what's in the log in a second, right? But the log is, what I maintain in an LFS system is a pointer somewhere to the end of the log, right? So this part of the disk is considered to be completely clean, free of any useful data, right? Any useful data, or potentially, we'll talk about, unuseful data is stored in the log, right? So I've got my log here, and I'm just appending here, and I'm just gonna append, append, append, append, look at that, look at those appends by me jiggling the laser pointer, that's pretty cool. Anyway, I'm gonna append, append, append, here to the end of the log, and that's kind of, that's how my log file structure file system is gonna work, but how do I actually do this, okay? So let's say that at some point previously, remember, everything on the file system is in the log somewhere, and it all got there because I appended it to the log at the last time that I modified it or wrote it, okay? So the current inode is in the log somewhere, right? But let's say it's cached in memory, and the current data block that I'm modifying is also in the log, right? So what happens when I actually do the modification? So remember, there's two things I need to change. I need to change the data block because I need to change the data that's in the data block and then I need to change the inode because I need to update some metadata about the file, all right? So where do I put the new data block? Anybody? Where do I put the new data block? At the end of the log, right? So there's my new data block, okay? And then I'm modifying something else. So where do I put the new inode? At the end of the log, okay? And I've got to update the inode to point to my new data block. So this is a file that only has one data block associated with it, right? So when I write the new inode, I can just write a pointer to this one data block and then I'm good, okay? Now what's the problem here? What's the last thing I potentially need to do here? Well, right, so now this is my most up-to-date copy of the inode and this is my new copy of the data block. So these two things are now stale, right? They're no longer needed. And so I need to free them, okay? And when I free things from the log, it creates these holes in the log that I'm gonna have to fight to work with later, okay? But at least conceptually, this is very nice, right? And this is essentially how it works. If I could've done a more complicated example, it would've taken me another hour. But you know, you can imagine if I had an inode that had pointers to multiple other data blocks that were in the log that I wasn't modifying, I would just write the inode and I would keep those pointers to those data blocks, right? Now if I'm doing reads from the log, right? I would have to find the inode, which we'll talk about in a sec, and then I would have to locate other things in the log. So it's possible that reads from a log structured file system can bounce around the disk, right? Because there's no way to know when I'm gonna read, right? And so the reads can happen anywhere in the log. But remember our assumption here. Why don't I care about reads skipping all over the disk? Because they're normally gonna be cached because my big, fat, big memory cache is gonna soak up most of my read traffic, right? And so if most of the traffic that's going to disk is writes and all my writes go to the append only log, then I'm minimizing my seeks, right? So most operations that go to disk are writes. Most writes don't seek very far at all, right? They're essentially just exploiting the natural geometry of the disk and continuing to append things to where the head's already up, okay? Questions about this, yeah. Well, so let's say this inode was in a directory somewhere. I don't need to change the directory file, right? Because the directory file contains the inode number, right? But the location is... Yes, yes, you're getting ahead of me, right? So, okay, so I just said this, right? So basically reads are, let me get to this. I'm coming there, it's the next thing, right? So reads are handled by the cache, writes I can stream to disk at full bandwidth, right? So now, because I'm limiting my seeks, I'm able to use the full bandwidth at the disk, right? And those bandwidths are going up and this is nice, right? So this is on some level this... On first blush, when you start to look at log structured file systems, you think this is brilliant, right? Like, wow, this is such a cool idea, okay? Oh, it goes downhill from there, it's so sad. All right, so let's talk about some things we need to fix, right? So, actually, let me get to the next thing, right? So you brought this up, right? And it's this question before. So in FFS and other types of file systems, how do I translate an INO number to a disk block, right? Remember, directories contain INO numbers. The INO number needs to be translated to the location of the INO on disk. So how did I do this in FFS and in the file systems we've talked about? Generic file systems we've talked about. How do they translate an INO number to a disk block? I'm gonna pick on this part of the room today. How did I do this? I have a number, right? I have the number four, and you need to tell me where is that data, where is that INO, where's the contents of that INO located? Anybody remember? I have an INO map, right? How do I find the INO map? I stored, yeah, so I stored in a well-known location, right? I've got somewhere on disk, when I format the disk, remember, I created all of the INO maps, and actually all of the INOs, right? So I knew exactly where those INOs are. There's just flat arrays of INOs located at specific points on the disk, okay? And this is a nice idea because it allows me to find the INO easily, but what problem have I just caused by my log-structured file system? Right, what happened to the INO? It moved, right? INOs weren't supposed to move, okay? So the FFS stored the INO map in a fixed location, right? For LFS, INOs are just appended to the log like anything else, and so the INOs can jump around. And this means that I need to potentially, what do you think LFS does about this? What do you think? I've got this really elegant solution, I'm just gonna write everything to the end of my append-only log, so where does the INO map go? At the end of the append-only log, right? When I change the INO location, I log a new INO map, and I just put it right there. Again, most of the operations of the INO map are reads, and so they're gonna hit the cache, but when I change, when I do what I just did, and I update an INOD, and I log it, then I just log the INO map at the end, right? So this again, this is kind of like, when you give somebody a hammer and they decide to take out some screws with it, right? Like at some point, like you, this is a great tool, and we can just keep, we'll just keep writing everything to the end of the log and figuring out how to sort out the details, right? Okay, so let me go back to this other thing. So remember, the other goal of LFS is not just to do writes in one place, but to try to stream as many writes to just together so I can maximize bandwidth, right? So when do writes actually happen? When do writes actually happen? So again, I can buffer writes in the cache, right? Can anyone guess when we actually write to the log? So there's one case where we have to write to the log, right? What case is that? Well, okay, so that's a good one.  And I need to evict something, then I have to write it at that, right? But again, I try to coalesce as many writes together so that I can write large portions of data to the desk all at once, okay? So okay, so we went through locating in iNodes, and then again, what about other file system metadata? I've got these iNode block bitmaps and things like that. Where do you guys think these go? There's a theme emerging at the end of the log, right? So you could just log this stuff too, right? Everything just goes to the end of the log. Anything that's written goes to the end of the log, okay. All right, so now I've got this great thing. I've got this brand new disk. I start logging from byte zero. I just start writing stuff. And then at some point, my log has traveled all the way across the disk. And at that point, I just say the file system's full, right? Like no more, there are no more bytes. Is that what happens? There's probably a lot of junk in the log that's dead, right? There's a lot of data blocks that I've written that are no longer valid, right? Remember the free space we created before when we updated the iNode in the data block? So there's a lot of holes in the log, right? So there's a lot of, there might be some valid data in the log, but there's a lot of invalid data in early parts of the log, okay? And so this starts to become the big question mark about this approach. Because now I've got this essentially what turns it to kind of a garbage collection memory management type problem, right?  And I need to somehow sweep through the log which is usually called log cleaning to reclaim empty space and create kind of a new log, right? Now, conceptually, you can think of this as happening across the entire disk. The way log searcher file systems actually do this is they break the disk into segments, right? If it happened across the entire disk, well, what happened is that you would get to the end of the disk and then your computer would freeze for two minutes, right? While it compacted the log and then it would start up again, right? So if I break things into smaller pieces, I can be cleaning certain segments while I'm using another segment, right? So, but essentially, again, you can think of this as kind of another mini-me sort of scenario, right? I break up the entire log into little mini-logs and I'm using, you know, I start using a mini-log, to start using a mini-log, I want it to be basically clean and then when I finish writing across the whole thing, I run some sort of task to compact it and store that data somewhere else so that I can reuse that segment, okay? So let's look at what happens, right? So here's my segment and I've got data from two files, the red file and the green file and let's say that, you know, my log is essentially run out of the end of the segment, so this segment is currently not in use. There's some other segment on the disk that I'm currently doing my log writes to. So what do I need to do here? Well, essentially I need to sweep through this segment and I need to identify all of the live data and I need to compact it into this new clean segment, right? So I need a clean segment on disk and I run a process that essentially collects all of the, again, the live data, writes it, appends it to this, so I've created one kind of compacted log and now this segment is ready to be used again, right? So this segment is completely clean and I can start logging right here, right? And I can just log right across this segment. Questions about how this works, right? So again, what's the trade-off here? What's the trade-off that I'm making compared with traditional file systems, right? I've made something easier and then I've created a new problem. What's the thing that I made much, much easier? Rights, right? I've eliminated seeks for rights. Rights are essentially seekless. They all just get appended to the same point on the disk. What's the new problem that I've caused? Fragmentation and what does that mean I have to do periodically? I have to do this cleaning process, okay? And most of the debate about FFS, sorry, LFS, has been how well does this part work, right? Because it's clear that the right stuff is brilliant, right? The right stuff is a fantastic idea but the mess it leaves behind is not necessarily an easy thing to deal with, okay? All right, so again, LFS seems like a great idea and then it's kind of like not having any sort of organizational strategy for your room and just throwing things everywhere and that works great for a while and then it's like, oh, I gotta clean things up. I can't find anything anymore and then you spent a whole weekend wishing that you had some sort of organizational system in the first place, yeah. So I think the cleaning is usually done kind of almost as it's described here, right? So I have a new segment that I'm gonna compact things into and what I want is I wanna produce a completely clean segment, right? Now you can imagine, right, what could I do here? So I could use this segment and just start the log here so I could seek here and just start logging that way but I don't think that's what they do, right? So yeah, so there's actually a third segment here that's being used by LFS while this is happening, right? And so this requires kind of a free segment and then I clean into that and now I've created a new free segment, right? So if I keep doing this enough times, I can always maintain some group of clean segments, right? Question. Yeah, yeah, yeah, yeah. So that's actually, that's a great point. So there were, right, so there were versions of this system, right? So let me go back to the, right? So what's happened here, right? Well, the interesting thing about this is that I still have an old version of the file in the log, right? So you can imagine that if I had a lot of disk and I didn't mind not being able to clean the log or compact it, I can store multiple versions of the same file because if I have some idea of version in some way of storing versions and the file system understands versions, then what I've done here is that if I want a previous version of the file, I just go look at this I know, right? And so yeah, so this actually does, that you can use a log-structured approach to implement a versioning file. I don't know if that's how versioning file systems work, but yeah, it's a great observation. All right, cleaning, okay. So yeah, so and once you start to bring the cleaner into the picture, right? This is kind of where the debate over LFS starts to get heated, right? Because again, it's one of those things where you're making a trade-off, right? It's like I'm giving you this great write performance for a little while and then you've got to run the cleaner and so things can get terrible, right? Uh-oh. Got a problem with the slides, hold on a second. All right, any other questions on LFS while I'm repairing my slide deck? So let's talk about cleaning, right? So again, I've got this cleaner, right? And I know that at some point, if I don't clean, I'm gonna get to the end of the disk and I have this completely dirty disk and then again, then your machine's just gonna stall for like two minutes while the cleaner runs. So this is not good, right? I would also love to run the cleaner when the system is idle, right? So, you know, while you're in class, not paying attention to your laptop because you're just reveling in my stimulating lecture, that's a great time for your cleaner to be running, right? So if you guys had any outlaw structured file systems, I could tell if you were paying attention or not because I could listen for like the heads to be running and the clean need to be happy, right? However, if you're sitting in here, you know, writing email or whatever, then maybe the cleaner isn't gonna be running as much. Other question, so what about segment size, right? So I didn't tell you how large the segments were that I wanted to clean and there's a trade-off here, right? So if I use a large segment size, it means that I'm amortizing some of the read and write costs, because essentially what I could do is I can potentially read the whole segment into memory, do the cleaning in memory, and then stream out all the writes for live data all at once, right? So that can be nice. However, small segments can be nice too, because they increase the probability that all the blocks in the segment are dead, right? So depending on the file system activity, it's possible that you have a segment that has no live data in it at all. All it contains are old unused I-Nos, old unused data blocks, old unused metadata, right? And cleaning that segment's really easy. You just toss it, right? So this is a nice corner case and a place where you can do a really nice optimization of the cleaning process, right? If you can tell that there's no live data in a segment, you can just discard it, right? So this is it. So there is kind of a runtime trade-off here and I just have it. So what other effect does log cleaning have, particularly on performance for this system? Anybody wanna make a guess of why? And we've talked a little bit, again. I mean, this is one of those fun things that the file system community debated because there's a clear win, right? But what would you expect the log cleaning process to be really dependent on? What's that? Well, okay, but let's say that I have some idle time, but like when I go to clean the log, how hard it's going to be depends a lot on what? Your usage patterns, right? It's incredibly workload dependent, the log cleaning. And so this is one of those cases where, when people started to run tests and experiments on log-structured file systems, group A could be like, ooh, wow, 100% performance improvement and group B could be like 100% performance degradation, because they're using slightly different workloads and those workloads either cause the cleaner to blow up and consume a huge amount of bandwidth or they allow the cleaner to run extremely efficiently, right? And there's also, there's a huge amount of work in figuring out how to run the cleaner, et cetera, et cetera. And then again, you start to get into sort of standard garbage collection territory here, all right? And so again, so this made it ripe for a great debate within the file system community, okay? And then finally, I wanna point out one other thing. So here's another trade-off that we haven't mentioned so far with log-structured file systems, right? What about reads? So let's say, well, I forgot the cache for a minute. Let's say that the cache doesn't soak up as many reads as we might like. Where is file data located in a log-structured file system? It's located all over the place, right? I mean, it just really depends on when stuff was logged. Imagine I have a, yeah, I'm only here. Well, the reads in general can get really, really terrible, right? On some level, if I keep modifying bits of the file, the reads might be okay, but imagine the following scenario. I have a file that has two data blocks, it's 8K. When I create the file, I write some data into the first data block, and that data block is never changed. And then I continue to make updates to the second data block. So what's gonna happen in log-structured file system? Well, I'm gonna continue to append that second data block to the log, but what about the seek distance between those two data blocks? Where is that first data block in the log? It's right at the beginning, right? And then where's that second data block keeps getting farther and farther and farther and farther away, right? And if I'm doing reads, and those reads aren't being cached for some reason, then, you know, again. So one of the things that's tough about LFS is that the file systems that we've been talking about until now do a lot of work, partly because they are more structured to lay out files contiguously on disk, right? We talked about extents, we talked about block allocates, a little bit about block allocation, we talked about FFS. And LFS essentially just ignores that. It says reads will hit the cache. I don't care about reads, right? And I'm gonna optimize for writes, okay? All right, so this, and again, this kind of prompted maybe one of the more interesting back and forth between luminaries in the file system community, right? So again, 1991 is the original paper from Stanford on LFS by John Oosterhout and Metal Rosebloom. And then in 1993, the log structure file system was reimplemented for BSD by Margot Seltzer, who was a Berkeley graduate student now as a professor at Harvard. And she, along with some colleagues, wrote a paper that questioned some of the performance improvements, right? So again, I mean, there, so what happened, right? Well, FFS was evolving too, right? So FFS made some changes. And when they benchmarked their system against an enhanced version of FFS, it outperformed LFS, okay? Well, the Stanford guys weren't just gonna take this lying down, right? So John Oosterhout wrote and basically wrote this complaint where he pointed out he claimed that they had done a bad job of implementing LFS. He claimed John did a bad job of choosing benchmarks, which again, we identified as something that's critical because of how benchmark dependent the cleaner overhead is. And finally, poor analysis, that's my favorite part. Like, and you're done too. You couldn't implement it, you couldn't test it, and then even the fact that you couldn't test it didn't prevent you from messing up, interpreting the results. Okay, so now, okay, two years later, there's another paper looking at LFS performance published by the same Margot Seltzer, again questioning the LFS performance claims, right? So, and I won't read this whole quote, but essentially it says when LFS is tuned for writing it's large file write performance is approximately 15% better than LFS, read is 25% worse. But when it's optimized for reading, it's large file read and write performance is comparable to LFS, right? So again, I mean, this stuff gets very nuanced, right? Large file performance, small file performance, and any time that somebody made a claim here, the other person would come back and say, oh, you know you're wrong. So again, Oosterhout described the 95 analysis improved, but still thinks that it was misleading, right? And at some level, this was kind of a fun back and forth between people in this community, right? So this is Margot Seltzer. Does anyone know what else Margot Seltzer did? To you. What's that? She's done a lot of work on databases. She taught this class. What else is she responsible for? Yeah, the OS 161 system that is your own little personal torture chamber. She looks like such a nice person, right? She is a very nice person. She's married to Keith Bostock. Yeah, another really well-known BSD developer. And she taught me this class. So, all right, so we're done with file systems, right? We are finished, file system unit is over. Yeah, right, right, so you're right. When we do cleaning, we do have a chance to adjust the layout of files on desk, right? Because on some of them, when we start to clean things, we see more at once, right? When we're doing writes, we're just seeing one block at a time, so when we did a read, we could, sorry, when we did a clean, we could correct that situation where this is huge span between these two blocks that are next to each other in the file, assuming they're in the same segment, right? If parts of the file are now located in multiple segments, you know, I'm not sure exactly what they did here, right? But yeah, so when I clean, I have some chances to adjust that. Okay, so next week's gonna be kind of a grab bag week. We're gonna do one lecture on operating system structure, which is something that's normally covered a little bit earlier, but I think it's nice that we've waited because you guys will have a little more context for this. So we're gonna talk about monolithic kernels, we're gonna talk about multi kernels, we're gonna talk about micro kernels, we're gonna talk about exo kernels, and maybe I'll make up some sort of name for a new kernel and see if you guys notice. And then I think what I'm gonna do next week on Wednesday and Friday is talk about performance. I don't think, I have to remember, I have to look at assignment three again. I don't think, there used to be a performance component to assignment three, I'm not sure it's gonna be part of the assignment this year, but I would like to introduce you to some guys, to some ideas about sort of how to do performance analysis, how to do benchmarking, and how to make sure that you're working on the right performance problem, because that is the key thing that people miss and it's something that will be useful for you guys to take with you from this class to whatever you end up doing next. So anyway, have a great weekend. If you're still finding assignment two, good luck, and I'll see you Monday.


In 1862, a café called Café du Monde opened up in the French Quarter of New Orleans. To this day, this café basically just sells beignets and coffee. Beignets are something that my mother used to make for us all the time growing up. A beignet is like a French doughnut. And to understand more about the people and some of its customs, in New Orleans, we have to talk about the heritage. But before we go any further, you know what to do. Please hit that subscribe button and give us a like. As always, a very, very, very special thank you to all of our producers and our patrons. Without you, we seriously could not do what we do. And so we thank you from the bottom of our heart. If you would like to join the Patreon community, there is a link down in the description box below. Welcome to Esoteric Atlanta. And today on this fun bonus episode, we're going to be talking about the Cajun people and the Creole people of Louisiana. Now, from my understanding, many people who are not from New Orleans or from Louisiana tend to get the two groups of people confused. As if the Cajun people and the Creole people are the same, but they're not. The Creole people are a combination of many different heritages, where the Cajun people have one distinct lineage. Both the Cajun people and the Creole people have their own flags and understand their own heritage. Today in the state of Louisiana, about 6 to 10 percent of people still speak French. Now, according to my research, the Cajun French, that could be understood by a native French speaker. But with Creole, the heritage is so mixed up now that most French-speaking people would not understand Creole. The Cajun people were the Arcadians. The Arcadians were people of French descent that immigrated over to Northern Canada, mostly the area of Nova Scotia during the 17th century. This was an area called New French. These people came from an area called Pontu, which was a province in the southwestern part of France. On this channel, we've spoken a lot about the history of France, especially with the House of Bourbon and the religious wars. The Arcadians were people living originally in the Pontu region of southwest France, who were basically farmers and had enough with all the warring going on between the ruling classes. Once they knew that there was a new world to be discovered, they decided to pack up and move to this New France. Once they got to the area of New France, which again is today, modern day, Nova Scotia, Prince Edward Island, that whole area, they arranged their own little culture and civilization. In fact, most of these peasant farmers that immigrated over for a new life came from the same neighborhood. They all knew each other, and so when they got to the new world, it wasn't like they were having to transverse this new area alone. They had each other, and with each other, they could keep the part of their French heritage and culture that they wanted to. It's also important to note that they gave themselves the name Arcadians. They were the first group here in this new continent to give themselves a name that showed no resemblance to their motherland over in Europe. A lot of the Americas today are taken from names over in England or other parts of Europe to signify where the people who settled there came from. But the Arcadians, they were vastly independent. They wanted their own world. They worked well with the natives to set up their own communities and kind of like their own little country. In fact, the Arcadians were pretty prosperous as a group, especially being in a new environment. They were pretty prosperous up until what we call the French Indian War. This was a war that lasted between 1754 and 1776. This was the British American colonies versus New France. Now many historians will tell you that this was just a theater, this war, for the Seven Years War that was happening over in Europe. But if you ask any Americans, they will tell you that this was a legitimate battle that happened. And as most Americans especially will tell you that if the English had not won the war, if France had won the war, then I would be speaking to you in French right now. The fact that I'm speaking to you in English as English being the American language is significant because the English won the French Indian War. Now it is said that after Great Britain won this war, they found out that the Arcadians were supporting New France. Now many people debate this though because it seems that the Arcadians literally wanted to be left alone. They didn't want anything to do with France or England, even though they spoke French as their native language. They just kind of wanted to do their own thing. And for a while they were just kind of left alone. But then something really sinister happened and this was called the Great Expulsion. As England now held the reins over most of North America, including present day United States and Canada, England decided that they would leave a part of Canada as French speaking. This is what we now know today as modern-day Quebec. But the Arab of Nova Scotia and Prince Edward Island, they were going to create as an English speaking land and stronghold. Therefore they needed to get the Arcadians out. From 1755 to 1764, Great Britain forced the removal of about 11,000 people from this area. Some were forced into servitude almost like slavery while others were taken back to Europe. Once they were back in France, they were then recruited by the Spanish government who was now dominant in the area of New Orleans to come back into Louisiana to re-establish a homestead. The Arcadians that took the Spanish up on their offer are now what we call the Cajuns. They didn't decide on the name change. That just kind of happened over time. Arcadian, Arcadian turned into Cajun. In today, still in Louisiana, especially near Lafayette, which is an area of Louisiana we'll be covering on Friday in more detail in our part two of the Axemen, is where the Cajun people tended to migrate. Again, for many many many years, the Cajun people kept their own French language and as they were up in Canada, they were fiercely independent. They had their own pockets of community. Now in the early 19th century, Louisiana was sold to the United States of America from Napoleon during the Louisiana purchase. And it was about a hundred years later that the United States started embarking on public education through the Federal Reserve. At this point, they told the Cajun people that they needed to learn to speak English, that they were not allowed to speak French in school anymore. And so we had this kind of transference of language where children who have grown up in French-speaking families were now forced to learn English during their state-mandated education. Again, to this day, six to 10% of Louisiana still does speak French, although most speak both English and French. Even today on the Louisiana state sign, it says welcome to Louisiana in English, but also says it in French as well. Now as I said in the beginning, allegedly a native French speaker would be able to communicate with the Cajun person. The French hasn't changed that much, just like us Americans can still very easily communicate with English people.  However, the Creole people are different. Where the Cajun people are predominantly of European descent, the Creole people are mixed. The Creole population covers about 4% of the state of Louisiana. These are people that are mixed with West African, Spanish, French, and indigenous natives of the area. In fact, a lot of the Creole people have something in common with the low country that I grew up going to off the coast of South Carolina in Georgia, where my mom's family is from. A group of people that we've spoken about on this channel, these are the Gullah people. Both the Creole and the Gullah people still carry a lot of their African heritage, beliefs, and culture. Then of course, down in New Orleans, you mix that with French and Spanish and indigenous. Most of the cooking that New Orleans is known for comes from Creole persuasion. When New Orleans was a settlement of colonists, before it was even part of the United States, when slavery was allowed, many of the people cooking the dishes for the French and Spanish were doing so coming from West Africa. They were using spices that they understood. As I heard one person say you have a Spanish settler asking for paella, well, a slave would do the very best they could, creating what we have now as jambalaya. And as the Cajuns are more in the Lafayette area of the state of Louisiana, the Creole people are mostly found still in New Orleans. One person I heard explaining Creole said anybody, anybody who has mixed heritage is technically Creole. And if you look at it that way, that's a good word to describe most of America is Creole. We got a little bit of something everywhere. Now I do hope to go into more Creole dishes, moving forward as some fun little bonus episodes to explore. But the next bonus episode we do, we're going to go back to the beignet, because the beignet was brought again by the Cajuns. The Arcadians. The French doughnut. A treat again my mother used to make for us when we were growing up. And I'm hoping to once again be able to film with my mother and my niece and my nephew and make some beignets. All right guys, thank you so much for sitting through this little bonus episode. I wanted to explain the difference between Cajun and Creole before we moved forward with more bonus episodes, especially revolving around food. And especially as we get into our Voodoo section of where that's mostly found in the Creole population versus the Cajun population. Again, many people outside of New Orleans or outside of the Southeast often get Cajun and Creole mixed up when they are two very distinct different groups. Again, the Cajuns are of European descent. Again, they were from France first were up in Arcadia and then ended up down in Louisiana. Whereas the Creole are very, very mixed. You have some Creole people who are very black in their heritage and you have some Creole people that are very white. They're just mixed. So I hope that makes sense. Please leave me your thoughts and your opinions down in the comment section below. Is there a dish from New Orleans that you want me to try to do on a bonus episode? Let me know. I'm not much of a cook myself but it would either be my boyfriend or my mother trying to do it. I'm also not really one that's good with spices. So I won't probably be tasting a lot of the spicy, spicy food but then, yes, I can definitely handle. All right, guys. I hope you're all doing really, really well. Next video will be part two of The Axe Man and then we've got some other videos coming up this weekend and then we'll be back with our Monday Mystery on Monday. All right, guys. I hope you're having a wonderful day. I'll talk to you soon. Bye.


Hello everyone this is Alice Gao. In this video I'm going to show you two applications of the product rule and this is regarding the two clicker questions in lecture 10 on slides 20 and 21. On slide 20 we want to calculate the probability that Dr. Watson is calling given that the alarm is not going. So the probability of w given not a, based on our product rule formula this is equal to the joint probability of w and not a divided by the probability of not a. Normally we would have to go back to the joint distribution to calculate both the numerator and the denominator, but luckily for us or because of my awesome design of the clicker questions I already asked you to calculate both quantities in the previous slides. So you can use them directly. This is equal to 0.36 divided by 0.9 which is 0.4. The second question on slide 21 is very similar. We want to calculate the probability that Mrs. Gibbons is not calling given that the alarm is going. So the probability of not g given a, this is equal to the probability of not g and a divided by the probability of a. So do we have both of these information? Well we certainly already have the joint probability over a and not g. So we have that, but we don't directly have the probability of a. That's okay. That's pretty easy to get right because we have the probability of not a. So the probability of a is just one minus the probability of not a which is 0.1. So let's plug in this is equal to 0.06 divided by one minus 0.1. So 0.06 divided by 0.1 which is 0.6. So option C. That's it for this video. After watching this video you should be able to calculate the conditional probability using the product rule. Thank you for watching. I will see you in the next video. Bye for now.


Okay, my name is Christian König. I'm working for AMD for something like eight and a half years now. I'm one of the maintainers of the AMD and Radeon kernel module, MDGPU and Radeon kernel module. And for the last two years, I'm also maintaining TTM. And that's what I want to talk about. So this presentation is all about the TTM memory manager and the Linux score. What's TTM? TTM is a manager for GPUs with dedicated video memory. So if you got something like an AMD GPU or an NVIDIA GPU, those Radeon, MDGPU, as well as Novo are using TTM to manage their buffer objects and to move their buffer objects around. The acronym TTM originals stand for translation table manager. But by today's standards, that's as inaccurate as it could be. Because TTM is managing quite a bunch of things, but not translation tables anymore. It's used to manage translation tables for AGP. So that's where that came from. Yeah, as I said, it's TTM is directly used by AMD GPU, Novo, Quixel, Radeon and VMware graphics. And the guys from VMware graphics, original tungsten graphics, one who originally wrote it and merged it into the Linux score. In addition to that, TTM is used indirectly through the DM VRAM helpers by ST, BOX, High Silicon, MTA 200 and the Virtual Video Box Video Driver. So how does TTM works? First of all, TTM defines so-called memory domains. Science is managing the local memory on your graphics hardware. The first thing that TTM defines is the so-called VRAM domain. That's representing your memory on the GPU. Then you got the system domain, which is system memory, which is mapped or available to the GPU or accessible to the GPU. So the GPU can directly write over PCIe and DMA to the buffer objects in the system domain. And the last thing is, you have this web domain. And in this web domain, that's what's not directly accessible by the GPU, but still backed by system memory. So the CPU could write and read from it, but not the GPU anymore. And stuff in this web domain can, in theory, also be swept out to disk, if necessary. Those yellow dots, or maybe orange, those orange dots here are buffer objects which are allocated and then backed by memory in the different domains. And the important thing in TTM is that those buffer objects can move from one domain to another. So for example, if you suspend your laptop, buffers from the VRAM domain usually move to the system or swept domain for the simple reason that the local GPU memory is turned, the power is turned off. So if you wouldn't evacuate those buffers, would get just random stuff on your screen or just a black screen if you turn the laptop on again after a suspend resume cycle. So that's what those red arrows here are good for. When applications then use those buffers, they usually move back into video memory or system memory, and that's what the green arrows represent on this slide. How does eviction works? Yeah, first of all, how eviction is a process of making room in a specific domain. So for example, if you have a lot of applications that allocate video memory, you're sooner or later going to run out of that. So what TTM does, it looks at the linked list of buffer objects in your video memory domain and starts to evict things from that domain. So it moves things in other domains. Usually the system domain, if that's not enough room anymore, it also moves on and moves stuff into this web domain. Eviction works by locking the LLU, then picking the first entry on the LLU and calls back into the driver to test eviction is value able. For example, in video memory, you usually have a part which is CPU accessible and not CPU accessible. And so the driver can decide if it needs only CPU accessible video memory that an eviction might not be value able to actually do. So it's skipped in the thing. Then we actually evict the video to move it to another domain. And then we retry the original allocation which failed in the first place. And if that succeeds, the algorithm ends, otherwise we repeat from the beginning again. This is actually whether inefficient because when we, for example, have a lot of videos on the beginning of the LLU list, we test over and over again if they're value able to evict. And that actually doesn't make much sense, but more on that later. Other functionalities that TTM provides. A big functionality when you want to move buffer around is that you need to make sure that nobody is accessing that buffer. When the kernel moves the buffer from A to B, you need to make sure that neither the GPU nor the CPU is still accessing A and writing changes to A while the thing is copied to B. So for that, we have the CPU page fault handling in TTM. That works by TTM tracking at which memory location, which virtual address location, buffers are mapped into the user space. And as soon as we want to move the buffer around, those mappings are invalidated. And if, for example, the CPU tries to access this memory by writing a reading from it, we end up in a page fault handler. This page fault handler can then identify which buffer object is meant to be accessed by the CPU and wait for that buffer, for the move of that buffer object to finish. That's what the CPU page fault handling is doing here. The other big functionality is the DMA memory page pools. The DMA memory page pools also originated in the ADP days. So on ADP, graphics hardware or general could only access uncaged system memory. Now uncaged system memory is something rather unusual, because when you want to access something fast with the CPU, you usually want to have it caged, so that one read doesn't result in tons of memory transactions. But making system memory uncaged is actually a rather costly process. You first call into the Linux kernel, say get three pages to get a free page, and then you change the caching attributes of that page, which requires a system-wide TLB flush of the kernel page table, and that can take quite a while. So what the memory page pool does is, when those pages are freed up, their caching policy are not changed back immediately, but instead we put them into a pool. So on the next allocation, we can serve from the pool instead of asking the operating system, the cooperating system for free pages. Later on, that was the first idea of how AGP worked. Later on, this was extended to provide uncaged wide combined pools for modern hardware, for PCI Express hardware, as well as decrypted pages and huge page and DMA32 page handling. DMA32 page comes into play when you have auto-graphics hardware which can't address all system memory. Yeah. As I said, TTM is, the whole framework is roughly 11 years old, nearly 11 years old now. It was merged upstream in June 2009, if I remember correctly.  And with that history, it also acquired quite a bunch of problems which I want to outline and discuss how we started on solving those problems and what else we should probably do to clean that up quite a bit. The first problem is that after TTM was merged in the upstream Linux kernel, it quickly became a dumping ground of driver-specific features. So whenever a driver maintainer had a feature which he wanted to implement, he just implemented it and instead of his driver, he put it into TTM because the assumption was that somebody else could sometimes make use of that. Usually that's probably a good idea in open source software. The problem here is that everybody did that without a central maintainer which actually filtered out which features were useful and which features were not useful. So what happened is that TTM became, as I said, a dumping ground. And as we later, we'll see on the next slide, it was rather hard to word that and move functionalities back into the drivers again. The next bigger problem is that we have a DMA, that we actually abuse the DMA API in TTM. So when we ask the cooperating system, as I said before, we have those page pools. And when we ask the core Linux kernel of the cooperating system to get us a free page, we always get caged system memory. Changing those attributes of those pages is actually completely x86 specific. And that's also the reason why the ATP back end in TTM always only worked on x86. There used to be AGP hardware on this PowerPC, for example. But as far as I know, we never got that working with AGP back end in TTM. Additionally for that, those page pools make assumptions how the DMA API works internally. This, then, works together with things like IOMMU, where you have an MMU block and memory management used in the source bridge, which also maps your DMA address coming in from the graphics hardware into the physical system address. The third item on my list here is that TTM has a horrible mid-layer design. And there are things which TTM calls driver and driver calls back into TTM. And also at the very bottom of this is a functionality which tries to limit system memory usage for processes using the graphics hardware, which are actually implemented from the wrong side. So, let's see how we tried. As I said, I'm one of the TTM maintainers for two years now. And during that time, we started to try to fix those problems a bit up. What you see here is the lines of code which the Linux kernel used for the TTM subsystem. As you can see in the beginning, please note the scaling on the left side is not that bad. As you can see in the beginning, when we took over, we continued developing new features for TTM and merging that into the upstream Linux kernel. And so the code base first started to rise a bit, rise a bit. And then some of our developers started to ask why we have this function here. Who is using that? And then we got around to, hmm, nobody is using that. Somehow we have forgot to clean up things in roughly 10 years. So, from one day to another, we removed 13% of the whole code base. That was quite a bit. Well, it wasn't for unused code, but it was more like a bunch of features which were used by only one driver. VMware graphics had a huge bunch of those which were in TTM, but we could just take them and move them around. That was roughly 2,000 lines of code. And as well as features in Radeon, as well as AMD GPU, which were only used by those drivers. And since we are also the maintainers of those drivers, it was relatively easy to move those around. The problem here is we still have features which are only used by, for example, Nouveau. And Nouveau actually doesn't seem to implement them correctly or doesn't seem to use them correctly. So, I am trying to sync up with the Nouveau guys to actually get on a page what we should do with that. Either remove it, move it into Nouveau or what else we need to do. My colleague, Wei Huang, did a talk about bike moves in TTM. That's a feature we did late last year. And this is a little bump here at the end, which is like something like 100 lines of code which got added for the bike move features. And later on we cleaned up a bit of stuff we actually didn't use. And so we got down with the line of code count quite a bit again. But I think something like 5% of the code base could be removed without losing much functionality. Usage of the DMA API. What you see here is the organization of those page pools. So you have a page pool for normal system memory which has, again, normal caged pages, normal uncaged pages, normal white combined pages. Then you have a pool for DMA32 caged pages, uncaged, and so on. And those page pools are actually quite important for quick application start-up and good performance. Because as I said before, changing the KG attributes of memory takes time and takes a lot of time. Especially if you don't use huge pages, for those who don't know that, the linear kernel are distinct between normal pages, huge pages, and sometimes called giant pages.  So if an application happens to allocate 1 gigabyte at a time, you can actually end up getting a really big block of memory 1 gigabyte. And not just thousands of small 4K allocations. Makes the rule think much, much more efficient because you have not so much housekeeping overhead. So what's abusing here? The problem is this rule implementation is completely x86 specific. So we had a really hard time getting it working on PowerPC as well as ARM.  And we are telling them over and over again that they have platform coherency issues and they don't really want to listen to that. So that's also one of the problems which end up in this domain here. Solution to that is moving the whole pooling concept into the DMA API. The DMA API already has the concept of pooling pages, of pooling core and memory allocations. The problem is it doesn't have a concept of uncaged and wide combined memory. So I've actually already synced up with Christopher Halvick, one of the core Linux developers in that area. That he wants to provide us with a bunch of new flags to make those allocations, move those allocations back into the DMA API. And when that's done, we need to implement memory management callback in the DMA API pools and that will probably solve this problem. When you look into the pooling code, there's a comment at the top of the file that this should probably be part of the DMA API and not be part of TTM. And this comment is sitting there for over 10 years now and nobody has fixed it. So yeah, just tackling things which are well known for a very, very long time. The biggest issue and that's also why we think that TTM in its current form is more or less a dead end are design issues. And the design issue which you can't easily fix even if it's an internal Linux kernel component with no external API dependencies. The problem here is when you call, let's imagine a user space driver wants to display something on the screen. Not something very unusual but it might happen. So it calls into its driver and says, hey, I want to allocate three megabytes of video memory to display something. The driver then calls into TTM asked for, hey, I need this buffer backed by three megabytes of system memory. TTM then says, oh, I'm running out of video memory backed by video memory. I'm running out of video memory. Let's call the driver what to do. The driver says, okay, evict some buffers to system memory when you're running out of video memory. TTM then calls and says, okay, I can do that. Let's call the driver to move those buffers. When you want to move those buffers, you're seeing, oh, in my system domain, I'm running out of space. And the driver calls TTM again and so on and so on. We stumbled over this actually quite a while after taking over maintainership just by looking at backtraces. When we got backtraces which was like this long and we are thinking, why the heck do we see the driver calling TTM, TTM calling the driver and so on. And it turned out that TTM is really designed in the way that your calling path or your call chain just does a ping-pong between the driver and TTM just to make it clear this is not a recursion. It just functions calling each other.  So yeah, we discussed this internally at AMD quite a bit and it's a big problem because then for example you imagine you add a new structure and want to protect it with a lock. Imagine you take a lock at your driver at the top and then the driver calls TTM and TTM calls the driver again and somehow in the middle you need to take the lock again because you don't know who is calling you. That's impossible, that's lock recursion, that won't work. So yeah, one possible solution to that would be to put the rule thing from the head to its feet. So instead of this calling ping-pong, TTM becomes some sort of component that just tells you which driver to evict and then the driver is which buffer to evict and then the driver is in control of the eviction and no longer TTM and then you don't need this recursion anymore. Yeah, how to fix it? What's coming up often is the idea to kill TTM with fire and just while the replacement and you start to use that in drivers turned out that is most likely not a good idea. We've prototyped something like that or thought about something like that and for the reason that it's used by many, many drivers in the column as well as AppStream wants a complete solution. David Arlight pretty much said that we want something that works for everybody and not one memory manager, often Intel, one memory manager for MD, one for the novel guys, we need one common memory manager. So that's actually not going to work. Additional to that TTM is mostly bug-free by now. Over 10 years, I mean we gathered quite a bunch of dumping stuff but we also hammered out most bugs in it so it actually works quite reliable. But the good to remove is maybe the AGP support. Hands up, anybody still using AGP-gate hardware? I don't think so. Really? Oh yeah. But you're not using that stuff so that's not a problem for you. Removing AGP actually won't mean that AGP hardware wouldn't work anymore because at least the hardware AMD ever sold had not only AGP but also this internal, how do you call that publicly? I think GPU VM, where page tables are handled like on modern hardware and the driver is handling the translation tables. So we would just remove the last translation table handling and move that into the driver and everything should more or less continue to work as it is. Just lose the common AGP translation table management. The next thing which comes to mind is slow decomposition and that's what we're certainly already doing is removing stuff which doesn't work, which isn't used anymore and moving stuff which is used but only by one driver into the driver again. That was like a certain percent code warp quite a bit. Then we have at some location to have unnecessary complex handling because TTM was to some degree meant to do something which by today's standard doesn't do anymore, managing translation tables. Vibers are managing that so we could remove that as well and it goes along with dropping AGP support properly. Last thing on my list here on that sublist is moving code into the DMA API. As I said, I already discussed that with Christoph Helwig and I think we have a plan we just need to implement it. So that is something we will probably do in the next year or so that we will get with quite a bunch of code here. The last bullet on my list here is moving more functionality into new components. Some guy at Redhead started with that. Previously, the jam objects, I didn't mention that before. Jam objects are your user space communication handle with your driver. So what you can think about this is jam is the front end of the driver interface and TTM is the back end of the driver interface implementing the backing store where buffers are actually are. Previously, it was organized like this that TTM and jam were completely separated. Recently, somebody of Redhead gone ahead and made the jam objects base class of TTM. This has a feature that we can now go ahead and to move duplicate handling. For example, we had for the same buffer objects, we had at least three reference counts. One in GEM for the handle to user space, one in TTM for the buffer itself and another one in TTM for eviction logic and list hands. With this move and a bit more cleanup, we can probably go ahead and move all of these reference count into a single one. We'll probably make handling quite a bit cleaner and quite a bit easier to maintain. Then what I've already prototyped with Daniel Federer from Intel as well is a DMA buff locking framework. Basically, when you submit commands from your user space application something like draw and triangle or draw a square or something like that you get one of the commands to draw something but you also get buffer handles where to draw, what textures to use, what index buffers to use and so on. Those handles are usually submitted to the kernel in the so-called command submission package. That's more or less the same idea for all drivers, not for Intel as well as AMD. But what we don't have is a common framework for handling those buffers. Every driver currently implements its own functionality to walk over those list of buffers and stitch together something which then can be given to TTM to move buffers into place to evict things and stuff like that. The DMA buff locking framework is a framework based on DMA buff and then should unify that throughout all drivers so that we don't need to implement that in each driver separately anymore. The last thing here is LiU cursor handling. As I said before doing the eviction, TTM is relatively inefficient when it comes to pick which buffer to evict. But it currently does, it always starts at the beginning and then moves over maybe thousands of buffers which are not valuable for eviction until it finally finds a candidate and then evict that candidate and then it starts from the beginning if that's not enough to find the next candidate. That is quite inefficient. So what this LiU cursor is doing is instead of getting a lock on the head of the list of the LiU list, you get a lock on the last item which is not valuable to evict and then move on from that to the next item and try to find something which you can remove from video memory and move it to system memory. So yeah, that's pretty much it. That fast. Questions? Yeah. Thank you for the presentation. Sure. So you have this piece of software that is like all the aspirin that is used by a lot of people and you want to change some part of it and you said earlier that you removed tons of time and lined up code overnight. How do you deal with that? How do you do changes in FBI that is used by so many people? What is your policy? Good question. So the question I should repeat that is how we make sure that we don't break anybody else. Is that correct? Pretty much. Okay. Yeah, first of all, removing the code was pretty easy. You just search if an exported symbol is used by anybody and if it turns out it's not used you can remove the function. That was rather easy. What's more tricky is moving stuff into drivers we don't maintain. For MDGPU and Radeon, it's relatively easy because we have the hardware, we have CI systems, we have QA which can look at the code and test it and make sure there are no bugs by removing or moving stuff around. So that was relatively easy. For the MBA that was relatively easy because we just asked the people to test it. I sent out a patch to Thomas, I forgot his last name, to Thomas Heldström, about moving stuff into the VMware graphics driver and to repeat it, oh yeah, good idea, let's do this but let's do it a bit differently and you made the typo here because of that it doesn't work. And based on that we rather quickly removed or moved code around but we didn't manage to do, for example, moving the NoVoCode because at MDG we don't have the NVIDIA hardware to test that, obviously and we also don't move around stuff for QXL or other things while we have some patches regarding that it's mostly just removing maybe 10 lines of code and that's not really worth it. So yeah. And general testing for us happens mostly on AMD hardware. Other questions? Is there a way for multiple applications hiding from the RAM to Q thrash or are they going to be stable in a certain situation while it's being extracted? Yeah, that's a really good question. So you're basically asking what's the policy and how different applications fighting for VRAM are basically going to do. So TTM, the real idea here is that TTM provides the guarantee for moving forward with a command submission. So if you have sent a bunch of, a list of buffers into your kernel which you want to have in VRAM, TTM then first of all locks down this list. Those buffers are not going to move then anymore. Then it goes over the list of buffers and when it finds, oh, something is on swap or something is in system memory, but I need it in VRAM, then it moves in that buffer. While doing so, it can happen that other things are addicted. In the same time, other applications send down requests to move in buffers as well, they start to evict something as well and then they would wait on that handle to become free. So at some point, you have to guarantee that you have moved forward with some submission. So if you have, for example, 10 submissions, one of them will win and move forward while others are addicted again and retry and have nine submissions and one of them will win and so on. So in theory, it's guaranteed that command submissions goes through. In practice, there's a lot of bunch which can go wrong. That's one of the things which didn't work so well in TTM when we started with it. We used my usage. Well, there is a functionality to figure out where a buffer currently is. So if the application is expecting a buffer in video memory, but it was moved out to swap or system memory by the kernel because of eviction, then an application could figure that out. The problem here is that this usually doesn't justify the extra overhead of asking the kernel. So you would need to send a list down to the kernel. Hey, give me the location for those buffers. And usually the kernel says, okay, I'm giving you a back set list, but till the next command submission, that could have changed already again and it's actually not that useful. What we do in the AMD DPU driver is we have statistics, how many buffers we have to move around for a command submission. And as soon as applications start to fight for memory, you see those buffer moves go up and then the application could react and go down a bit. I think the OpenGL driver actually, the major OpenGL actually do use that, but I don't think that our internal OpenGL driver actually does that. Question, you said that there's a way of finding out it's being swapped out, et cetera. Is that that kernel interface where you find the physical page mapping and you get the bits which tell you whether your page is dirty or swapped or swapped back, et cetera? Is that that one? No. That's what you mean. That's a question about CPU page table mappings. What you mean is that the CPU page table mappings. GPUs, at least our older generation GPUs work a bit differently. They can handle page faults. So you have page tables, but you need to guarantee that those are filled.  So it works a bit different. The latest AMD generation could actually do page faults, but we currently doesn't use it for HMM yet because it's kind of hard to implement. Is that thrashing eviction? Yeah. It kills your performance completely. Yeah, exactly. Yeah. To repeat the question, what's that question? I don't know. Just a statement. Just a statement. To repeat the statement, yeah. Whenever you got into eviction, it completely kills your performance and completely agreed to that. So we actually need to improve both TTM as well as GEM to get rid of eviction situations or to avoid eviction situations, except for things like suspend-resume where you really want to evict everything because it's going to be damaged otherwise. Yeah. I saw some smarts in TTM to figure out basically clustering of the LRU. So if you have a large buffer that you want to place in the VRAM, and then you have a lot of small, scattered around 4K buffers on the LRU, are you going to evict all of them first and then just figure out, oh, that didn't make any space for my buffer actually? Yeah. So the question is how intelligent TTM evicts things and that's completely brain-dead. So that's from the beginning and just evicts until it fits. Yeah. That's not very, very well implemented. That's correct. Anybody else? Central memory management code. It seems like there's... What do you mean with central management? Memory management code for Linux. For the CPU. That's the same thing. Problems, yeah. Okay, the question is basically could we reuse more of the core Linux memory management? Implementation or ideas? Both, yeah, actually. Yes and no. Yes, for example in the DMA API we're actually trying to move functionality there. No, because GPUs, at least the older generation GPUs were differently than the CPU. As I said, they have page tables, but they don't support recoverable page faults. So at all times you need to make sure that your page tables are filled from the beginning to the end. One very fundamental idea in the Linux memory management is that at all times you can clear the valid or the read bit or the write bit in your page tables and get a page fault and handle that. This way, for example, is copy on writers implemented in this way. You clear the... When you call fork, all write bits in your page table are cleared and the page which you want to access with the CPU is copied and the clone is created and the parent uses one copy and the child uses one other one. This won't work with GPUs because GPUs currently can't handle recoverable page faults. For AMD, Vega is the first generation which can, in theory, do that, but they unfortunately implemented only Windows requirements on Microsoft requirements. So the Linux requirements are a bit different and we actually have a hard time to actually use that hardware in this way. Excuse me? That would probably be something. I think the next big step we are going to use is stuff like memory limits and C-group. As I said in this slide, the big reason why we have this mess here is that at the very bottom of it have a limitation of how much memory applications can use and this is probably better put into C-group and into core system management. That's the final case, yes. Five minutes left. I don't think so. The first problem is I'm not an expert on the Windows side and second problem is I'm not sure if the Windows side isn't under some NDA. I don't know. Somebody else? Okay, that's it.


The coalition of NSAS protesters and supporters have accused the Lagos state government of misinforming the public on the mass burial for NSAS protesters, insisting that the state government was insincere about the killings that occurred at the leaky toll gate in October 2020. In a statement, the group called for the suspension of the planned mass burial of 103 bodies immediately, they however insisted that the government must stop using the sit-fall tactics and face the reality that the actions led to the death of the defenseless Nigerians.


Matthew Page and his team present the updated PRISMA 2020 reporting guideline for systematic reviews and meta-analyses. This article was authored by Matthew J. Page, Joanne McKenzie, Patrick M. Bosswit and others.


Hello friends, so welcome to another session on trigonometry and today we are going to understand Complementary angles and not only we are going to define and understand complementary angles We are also going to understand the rich other relation between various t ratios of complementary angles Now let us start this session by understanding what complementary angles are Now two angles are said to be complementary when their sum is equal to a right angle That is if two angles are there theta and phi and if their sum is 90 degrees Then we say that theta and phi are complementary to each other theta and phi are complementary angles Complementary angles. Okay. This is a very vital information. Keep this in your mind. Now examples 60 and 30 sums to 90. So hence it is They are complementary to each other similarly 40 and 50 degrees are complementary angles Here also if you see 10 and 80 70 and 20 all these pairs are of complementary angles now similarly 12 degrees, let us say and 78 degrees these are complementary angles 12.5 degrees and 77.5 degrees these are all so complementary so you can find out infinitely Many pairs of complementary angles now if you notice in a right angle triangle The two angles apart from the 90 degree are always complementary right in a right angle triangle The other two angles apart from the right angle are always complementary Why because if one is theta by angle some property, we know that it is 90 minus theta, right? So here if you see instead of this, yeah, right angle be here. So if you see Angle 90 degree plus theta which is angle C here plus angle B is 180 degrees. So hence angle B is 90 minus theta right by angle some property now, let us Analyze the t ratios of complementary angles. What does it mean? So let us first first find out sine of theta So if you see sine of theta is nothing but by definition its opposite side to the theta That is this side AB divided by what the hypotenuse that is this side that is BC So hence sine of theta is AB upon BC Similarly, if you look closely cos of beta now if you see from this angle 90 degree here 90 minus theta if you see from this Perspective so cost of this angle is nothing but the adjacent which is AB which is highlighted over here This is AB this one divided by what this line, right? This is cos of 90 So hence if you if I have written here So both sine of theta as well as cos of 90 minus theta are same ratio that is AB by BC So hence I can write sine theta is equal to cos of 90 minus theta This is a very vital information and this is going to be used by you if you pursue trigonometry In your career very very important information now Similarly, you can see cos of theta if you see cos of theta is nothing but this side now in this case This one this divided by The hypotenuse right that is AC by BC which happens to be the sine value of 90 minus theta Why because for 90 minus theta this side is opposite isn't it and this one is hypotenuse so hence What do we see cos of theta is? Equal to sine of 90 minus theta very important information Similarly other T ratios also cosecant now another important one is tan theta again So tan theta is nothing but what is tan theta in this case Opposite by Adjacent so AB by BC and hence which is nothing but cot of 90 minus theta so tan theta and cot 90 minus theta are Related they are equal now other is just a formality other T ratios cosic cosecant theta is 1 upon sine So if you go by whatever we found out sine is cos of 90 minus theta So that is secant 90 minus theta isn't it you can also do it by the Definitions of the T ratios that is in terms of the ratios of the sides if you want to calculate You will get the same value. So please remember cosecant is secant 90 minus theta now secant theta is also equal to cosecant 90 minus theta right now this is what we Derived and now let us write down the summary the summary is sine of theta is cosine of 90 minus theta now Don't think that this is only restricted to a right-angle triangle. Whatever is the value of theta? Cos of 90 minus theta will be Same to sign theta. Let us take an example also. So for example in the previous sessions we learned Sine of 30 degrees is nothing but half if you if you have seen those sessions lectures So sine 30 is half and now sine 30 degrees can be written as sine of 90 degree minus 60 degree isn't it now from the relation sine of 90 minus theta if you see is cos of theta So hence I can write this as cos of 60 degrees now if you see cos 60 also is half Isn't it? Let us take another example. Let us say tan of 60 degrees now tan of 60 degrees can be written as tan of 90 degrees minus 30 degrees right now Let us see what is tan 90 minus theta than 90 minus theta is cot theta. So that means this will become cot of 30 degrees Isn't it now what is tan 60 by the table if you see it is root 3 if you have the table with you You can check tan 60 is root 3 and similarly cot 30 also is root 3 root 3 right That means our whatever information or results we derived are accurate, right? It is true for all values of theta. So, please remember these relationships, right? So sine and cos are complementary if you see cos and sine same thing tan and cot tan and cot and secant and cosecant, right? So if one is theta the other will be 90 minus theta value I hope you understood these concepts will take up more problem solving on these concepts in problem solving sessions. Thank you


Hello and welcome to the Grand Line Review, your source for everything One Piece. Today we are going to be taking a look at a very neglected aspect of the series in the form of entrepreneurs. Now, given that One Piece is a battle manga, it's no surprise that most people focus on things like which character is stronger or what fight was better. And I mean, that's fine. That's generally what Shonen Manga boils down to in the end anyway. However, the world of One Piece is quite unique and there is certainly more than one way to make a mark in this world. And one of those methods is by venturing into the domain of business. To be clear, an entrepreneur is an individual who starts their own business often at significant financial risk in the hopes of being wildly successful and making all of the money in the universe.  So the criteria for this list is as follows. I will only be looking at individual characters rather than groups of people. And as always, every character on this list must be canon because I don't need a reason. But with that out of the way, let's begin. Welcome to the Top 5 Entrepreneurs in One Piece. Number 5 Shaki Kicking things off today, we have the seemingly age-immune partner of Silver's Rayleigh, Shaki. Once a fairly notorious pirate, this lady gave up her pillaging ways to start a bar on Sabati Archipelago. Its name is Shaki's Rip-Off Bar. Very apt as all the prices she charges for even the smallest of items are exorbitant to say the least. In fact, she once told Chopper that the price of cotton candy he had consumed in her bar was 100,000 berries. And although she was only teasing him, this isn't all that far from the truth. And although she was only teasing him, this isn't all too far from the truth. Now you won't believe this, but Shaki's Rip-Off Bar doesn't receive many customers, which one would think isn't great for business, and yeah it isn't. However, due to the extremely high price as she is able to con out of the occasional customer, it must be enough to continue operations at the very least. Her bar is also notorious for beating up customers who refuse to pay, presumably owing to the strength Shaki acquired during her years as a pirate. However, the best business decision Shaki made was to set the bar up in Grove 13 of the Archipelago, which is smack bang in the middle of a lawless zone, allowing her to operate this ever so shady business. And you know, she may not make the most money in the world, but Shaki certainly does serve as a great opening example of a successful entrepreneur. Number four, Zeph. Here we have another ex-pirate who, after being shipwrecked and forced to consume his own leg, decided that he was going to pursue a dream of opening up a floating restaurant, which would become known as Baratier. As an accomplished chef, Zeph had complete faith in his ability to construct and provide a menu of phenomenal food, but he was also a man with a true vision in regards to the atmospheric presentation of his business, which is stunning inside and out. However, Zeph also had the foresight to hire and reform outcasts of society, primarily from the world of piracy, like him. As a result, he was able to develop integral bonds of loyalty with his employees, as well as construct a natural army of chefs who are entirely capable of defending the floating restaurant from any attackers, which are fairly common in a world full of pirates. And despite all of that, Baratier has built itself a reputation of true gourmet dining, with individuals from all over East, Blue and Beyond making the trek just to sample the offerings at the restaurant. This success has also led to the expansion of Baratier and it has now developed a further two dining vessels, the Tepanyaki Ship, Nasukasira, and the Submarine Desert Ship, Sister Anko. And all of this has simply sprung from the mind of one very driven pirate, a true entrepreneur. Number three, Papug. Perhaps better known as Kami's pet starfish, Papug actually got his start in the workforce by assisting Hachi with his Takoyaki restaurant. However, Papug also had his own dreams of becoming a fashion designer and he would go on to create a brand known as Criminal. Exactly when it was founded as up for debate, as the logo has been seen on characters pre-timeskip. However, it would appear to have made its meteoric rise to popularity during the two-year timeskip. As a result, we were introduced to a very wealthy and famous Papug during the Fishman Island arc who lived in a mansion in the very flashy area of Gioverly Hills. And honestly, it's not too hard to see why the criminal brand often displayed as crimin is a nice simple logo that can be applied to a wide array of otherwise plain clothing, which is a tried and tested strategy of fashion, offering relatively bland clothing so as to appeal to as many people as possible, but slapping a brand over the top, thus giving them the right to charge far more for a regular shirt than any non-branded outlet. Genius really, and something this starfish took wonderful advantage of. Although if I had to criticize Papug in any way, it would certainly be when he offered the straw hats any items from one of his stores for free, which promptly resulted in the place being entirely cleaned out. And while not enough to sink the business, this surely would have been a very costly mistake. With that said, it's very difficult to argue that a starfish who owns his own mansion can be considered anything less than a wildly successful entrepreneur. Number two, Wapol. I never thought I'd see the day where Wapol would end up this high on another list, but here we are. After his fall from grace in the Drum Island dark, Wapol became very desperate to the point where he began consuming garbage. And thanks to his devil fruit, the Bakubakunomi, he inadvertently started creating a series of toys. These toys soon attracted the attention of children, which prompted Wapol to set up a shop, and bam, he was in business. And things further exploded from there when scientists discovered a secret within these toys, a new metal conjured as a result of Wapol's devil fruit, which was creatively named Wapo Metal. And from there, Wapol simply could not stop the money from coming in. Wapol became so rich that he was actually able to start an entirely new country known as the Black Drum Kingdom, as well as marry a stunning lady named Kinderella, also known as Miss Universe. In fact, Wapol's status now is exceptionally higher than when he was king of drum, proving that with some hard work, a good idea, and a bit of luck, in this case a lot of luck, you can go everywhere in this world. Wapol practically serves as the definition of entrepreneur, and yet there is still one figure that we need to examine. Number one, Iceberg. Moving on, we have a student of the legendary shipwright Tom, who was directly responsible for uniting the various shipyards of Water Seven into one Goliath company known as Galila. This company is one of if not the most prominent shipbuilding organisations in the One Piece world today, and employs only the most skilled of carpenters to service their clientele, which consists of pirates, the world government, and even general citizens. Essentially, if you need a ship, there is no better place to be. Under the direction of the company president, Iceberg, the success of Galila has led to rapid economic growth for the entire island of Water Seven, and furthermore led to Iceberg being elected as the mayor of the nation. And this truly is an entrepreneurial endeavour, as Iceberg now looks beyond operating a simple company and is instead invested in the prosperity of an entire civilisation through the key trade of shipbuilding. Iceberg's interests also lie in the area of innovation, and the Galila company has since expanded into the industry of building sea trains, having successfully completed the puffing ice following the two-year time skip, the use of which will significantly increase their ability to trade with other nations at great speeds. All in all, Iceberg is a man who is directly responsible for the rise of an entire island. He has gone beyond the territory of a simple businessman and descended into the true realm of entrepreneurship.