All right. So today we're going to continue talking about file systems. And welcome to Friday. So in particular, we'll talk about some other, you know, we'll keep looking at doing some file assessment with respect to using common, or maybe not so common, but Linux utilities that you can use yourselves. And then we'll talk about finding data blocks. So we'll talk a little bit today about path aim resolution. We'll also talk about ways of, once I find a file, finding the data blocks that are associated with that file. And of course, this is something that's made somewhat challenging by the fact that I want to let files grow and shrink to take on different sizes. All right. No announcements today. Anybody have any questions about, of course, administrative or any other things before we go on? OK, good. Any questions about INO? So at the end of last class, we started talking about index nodes or INOs, which are special structures that are stored on the disk and are used to store information about files and file contents. So anybody have any questions about these before we do just a little bit of review? All right. So we started looking specifically at EXT4. I want to look at a specific file system to kind of put this stuff into context. EXT4 creates a single INO profile. We talked about the fact that these were 256 bytes. So if I'm talking about 512 bytes sectors, I can get two in a sector of 4K blocks. I can get 16 in a block. What is in the INOD structure? What does the INOD contain? Jeremy. OK, yeah. So INOs are really all metadata, right? So we talked a little bit about how, if you look down at the disk itself, right, there are two types of things that are stored on the disk in a very broad categorization. One type is file data, right? And the other type is sort of file system metadata, right? So things that are not data blocks, data that's on disk that's not part of any particular file but is used by the file system to find files, to organize information about files, to et cetera, et cetera. So INOs are in that second category. They are not file data. They are used to store information about the file system that the file system needs to operate. But what specifically is in an INOD? Navya. Yeah, so I might have some information about users and permissions, right? Something about the people who can open this file or read and write to it, right? Or some permission information. Simon. OK, so file name is interesting, right? We'll talk a little bit about that today. There's actually not necessarily a final name, but the second part of your answer is correct, right? So certainly once I find an INOD, what I want to be able to do is find the data associated with that file, right? This is not the file data, right? But there are data blocks on disks somewhere that are associated with this file, so once I locate the INOD, it would be nice if I could find that file data. What else is stored in here? Damn. Yeah, so there was a variety of different timestamps that EXT4 stored, right? When it was created, last modified, even a deleted time, right? So Simon got the location of the file data blocks. That's important. Permissions, Navia got, and then timestamps, right? So, and so let's go back to naming, right? So remember, INODs are numbered, right? INODs are, the file system understands numbers, right? So the INODs are all indexed by number. The INOD itself has really no concept of a name, right? The name that you use to tell the file system about an INOD is the INOD number, right? The path name and how it's resolved to an INOD number is something that we'll talk about today, right? Yeah, so here we go. So how do, I don't know if we actually went over this here. Oh, okay, right? So we asked, you know, if I have an INOD number, how do I find that INOD on disk, right? So path resolution is gonna take me from a path, right? A series of characters to an INOD number. Once I have the INOD number, how do I find that on disk? And what EXT4 does is it just stores those INODs in well-known locations, right? So you can imagine one big array of INODs at the beginning of the disk. That's not exactly how it works. They're actually spread throughout the disk. But anyway, it's a fairly simple mapping from INOD number to where the INOD is on disk, right? We talked about the fact that INODs may not be located near file contents in this model, right? And to reduce the seek times between INODs and the contents associated with the file, EXT4 creates multiple blocks of INODs throughout the disk, right? So it tries to put file contents and then when the EXT4 allocates file contents, it tries to do so close to the INOD that stores the file metadata, right? Why would you expect to see lots of seeks back and forth between INODs and the associated data blocks? Aging. Yeah, I mean, we talked about an example of a write operation, right? And how many different parts of the disk that write operation was gonna modify. Usually, any sort of file system operation involves reading or writing or modifying or changing both data blocks that store file contents and the INOD, right? If I wanna grow the file, I have to make sure that the INOD knows how to find the new data blocks and then I actually have to allocate the new data blocks and write data into them, right? So frequently, any change to a file is gonna involve modifying or reading both of these structures, right? And it turns out that INODs are also good candidates for file system caching, right? Which we'll talk about on Monday. And with the XD4, the other thing is when you format the system, you create a fixed number of INODs and if you run out of those INODs, you can't create any more files even if you have more data blocks on the system. And so, file systems try to make assumptions about file sizes so that they can allocate the right amount of metadata. Just in case this is not obvious, I mean, this is what happens when you format a disk, right? So you may have wondered, why do I need to format a drive, right? And why in some cases does it take so long? I don't know why it takes so long, right? But when you format the drive, what's happening is that the file system is taking the data blocks that you've given it and it's adding any metadata to the disk that it needs, right? So XD4, when you format it, it's gonna allocate all of these INOD structures and then potentially initialize some other parts of the disk, storing metadata that it needs to operate. Yeah, hopefully. Yeah, so the question is, where are, like, how do I find the blocks of INODs? I think they're stored in what's called the super block, right? Which is another on disk data structure and we'll actually look at the super block in more detail today, right? So a lot of times file systems will write a certain amount of data about the entire file system into a structure that we call the super block, right?  And one of the things that is probably in the XD4 super block is the location of these INOD arrays, right? Yeah, Sean. Yeah, so it's a great question, right? So in general, in the past, file systems haven't necessarily been great about doing these sort of online operations, but if anybody has used some more modern file systems, they've actually gotten much better at this, right? So, XD4, I know for a fact, because I've done this recently, can actually resize itself dynamically while the system is running, right? So if you may say, of course, as you imagine, it's easier to expand the file system that it is to contract it, right? Because there might be some data that you have to move around, but in an online fashion, the XD4 can actually expand itself dynamically, which is pretty wild, right? Like, when I was a young whipper snapper, file systems didn't do that, right? Like, you formatted them and they had a certain amount of space, and if you bought an extra drive, there was kind of like, well, you had to set up as a separate partition, it was a huge pain, right? But now, there's all these magical tools so you can kind of add it to that, and then suddenly you have more space, right? Which is, you know, again, I mean, something that still impresses me, but I still use Firefox, right? So obviously you guys know how that I'm an old, crafty person in general. All right, so, any other questions about Inodes? That's a good question. So yeah, I don't know about, I mean, you could certainly allocate more space on the disk. I don't know if you could actually find a way to allocate more Inodes, right? You might be able to, right? Any other questions about Inodes before we go on? So I have a few more. So before we go too much farther, right? So we talked a little bit about directories, right? And I've hinted so many times that directories are just files, right? And that's actually the case, right? So every directory has its own Ino number, it's a file. The contents of that directory are file system specific and essentially what directories hold is a data structure that maps Ino numbers to relative names, right? So this is how kind of important. So, because the directory has its own name, right? And then inside the directory there are, you can think of it almost like an array, right? I mean, I don't know exactly what the data structure looks like, but there's some sort of data structure that essentially maps, you know, relative path names to Ino numbers. So for example, even, this is kind of fun, right? So even your good old trusty friend, LS, right, can display this information. So for example, LS-I will actually tell LS to display the Ino numbers associated with the contents of the directory that you ask it to display, right? So for example, here I've asked it to give me the Ino number for the root directory, right? Remember that on EXT4, for whatever reason, my convention, the Ino for the root directory is two, okay? Now what I've done in the second command is asked it to give me a list all the Ino numbers for the contents of the root directory, right? So now this is going to read the contents of the root directory and tell me all the Ino numbers. And these are the Ino numbers for things that are in the root directory, right? So these are other directories, right? You see they have Ino numbers just like files, right? In fact, from this output, you really can't distinguish between files and directories, right? Some of these things are files like VM Linux is a file or VM Linux is a file and some of these things are directories. Yeah, Jeremy. Oh yeah, so okay, so this is a great question, right? Why do proc and sys have the same Ino number, right? Remember, this is an EXT4 file system rooted in root. What have we said before about proc and sys? Are proc and sys real file systems? No, so proc and sys here are actually not real files, right? I don't know why the number one is used. That's a good question, right? But the reason why these have the same number and I think that one is probably like a special number here which basically says that that's actually not a real, that's not a real file, right? If you looked at mount, what you'd find is that sys is mounted on root, right? So sys is actually its own separate file system, right? So the EXT4 file system that we're displaying information about doesn't actually include sys or proc. I wonder if there's another, yeah, there's not really another one here that's separate, that's a great question. Any other questions about this? Dev is also, I think, another special case, potentially, but I'm not sure about that. Right, so now what I can do, right, is I can say, okay, we'll show me the contents of a different directory, right? So here's my home directory, my home directory on this machine has I know number 393,219, I don't know why, but that's what it is. And now I can display the contents of it and the contents are a single, yeah, I'm trying to remember which one is which here, right? Oh, sorry, there's two directories, right? So there's an Ubuntu directory and there's my home directory and these are the I know numbers for those directories, right? So what you can see is, again, the directory contents are mapping these relative path names, right? So this is not, the directory does not map home Ubuntu, it maps Ubuntu, right? But because I'm inside the home directory, this is, so you guys probably have some sense now of how we're going to do path resolution, right? I think we already, yeah, I think we did this, right? So this is just a, oh, okay, well, this is a different, yeah, this is a directory, right? So we looked at this last time, it shows some information about the directory, right? Okay, let me show you some other cool stuff, right? So this is a different command. Now what I'm asking here is, I said before there's this special structure on disk that's called the super block, right? The super block is part of the file system data structure that contains all sorts of other information about the file, right? And you can see this command gives you some sense of what's inside the EXD4 super block and there's actually several pages worth of data in there, right? So this is a pretty interesting, important data structure. Let me ask a different question. So this super block, right? So for example, somebody had asked, how do I find the groups of inodes? Well, here they are, right? And in fact, if you, if this goes on for many, many more group numbers, I think there were like 64 different inode groups, right? And this will tell me for this particular group on disk, here is the inode table, right? So this is where the inode table is stored. There's an inode bitmap. What do you think the inode bitmap is for? People who are thinking about assignment three may be thinking about bitmaps and what can I do with the bitmap pretty efficiently? Any guesses? The inode bitmap is used to allocate inodes. So when I wanna find a free inode, right? I look in the inode bitmap and I look for a bit that's not set, right? So the inode bitmap is going to reflect which inodes are in use and which inodes are not, right? Based on that, what about this? What does the block bitmap do, Jen? Yeah, so this is for doing block allocations, right? So if I want a new data block in this particular group, this is the block bitmap that I'm going to use, right? And then it tells me a bunch of other things here. So this is kind of an interesting case, right? You'll see that there are zero free inodes in this group, right? This group has run out of inodes, right? So as the system started to allocate inodes, apparently it allocated a bunch from this group and this group is actually has no free inodes and no unused inodes. So all the inodes in this group are in use, right? However, it has a bunch of free blocks, right? In fact, there's quite a bit of data blocks, there's quite a few data blocks left in this group, right? So this is kind of interesting. This is an example of a group that maybe has a bunch of very small files in it, right? So it ran out of inodes before it ran out of data blocks. The next group is a little bit different, right? So this one is also full, right? We have zero free inodes, but it has much fewer free blocks, right? So this one looks like the file size was a better match for what EXT4 was expecting, right? And I actually don't know if EXT4 will allocate blocks between groups, right? So it's possible that these free blocks here are just gone, right? They're just, they will never be able to be used because this group, this little piece of the disk is out of inodes and so I might not be able to actually ever get these data blocks into a file. All right, let's go back here, right? So this is other information about the super block. It shows me where it's mounted, right? So this file system is mounted en route. This was the file system for this machine. It has a magic number here. What do you think that magic number is for? Amen. Yeah, well, it identifies the file system, right? So this identifies this as an EXT4 file system. If you try to mount, if you tell your system, mount this device as a EXT3 file system, it will check this magic number and say that's wrong, right? Whatever is in that part of the disk, I don't know anything about it, right? That's not me and if you ask me to try to do something with that stuff, I'll probably make lots of mistakes, right? So this is some way to distinguish different file systems from each other. So this gives me the total number of inodes and blocks that were allocated. This gives me the free blocks and free inodes. So this is a relatively, slightly used system. About 75% of my blocks are free and about looks like even more than that in terms of inodes. Gives me my block size, blocks per group, right? So we looked at those groups before. So this tells me how many blocks are in each group and if I can do this math in my head, it looks like I have about 128 megabytes per group, right, on the disk, right? 32K blocks, 4K blocks. This tells me the inodes that were allocated per group, et cetera, et cetera. And then there's some information about when the file system was created, how many times it's been mounted, et cetera, et cetera. So, oh, this is kind of a fun thing, the lifetime rights, right? So the system tracks, every time you do a write, this is the total amount of data that's ever been written to this particular file system. It's kind of cool. First inode, I don't know if this is the first inode that's available and then the inode size. So it's a bunch of interesting information in here and this is potentially quite important information for the system to have. So we talked before about disks and disks failing and just having sectors that go bad and other sorts of problems. So what do you think the file system does to try to make sure that all this data in this super block is stored safely? First of all, how do you think the file system finds the super block in the first place? Sarah, yeah, it just puts it in an unknown place, right? It might be in like the first block of the disk or something, right? So that works nicely. But what happens, like, what happens if this super block gets corrupted, right? Let's say that some of the data in here gets damaged by, I don't know, like a cosmic ray from outer space or something, right? Flips have been in here and so what could happen? So this data could potentially get corrupted and at that point, this could potentially cause the file system to be unusable. So what would the file system, what do you think file systems do about this, Jim? Yeah, so it's pretty simple approach to, you know, to try and to keep data up to date, make a bunch of copies of it, right? So there are probably multiple copies of this information that the file system is stored at multiple known locations within the disk, right? So if the, you know, the super block is corrupted, it can go try to get another copy of it and see if it can use that copy to repair the disk. Yeah, Jeremy. Good question, yeah. I mean, that probably is true, right? So there probably is some sort of check somewhere other way that it has it validated. It might actually compare it to super box in different parts of the disk, right? So you could do some sort of voting. But anyway, so very simple approach to, you know, to failure survival, which is make multiple copies of something and hope that there's one out there that's right, right? All right, so now let's go back to this idea of path name translation, right? So we have a name, right? You've said open this particular file, right? And the file system has to translate the path that you passed in into what? I mean, it has to find an I know number, right? Like that's what the disk knows about. The disk at some level says give me an I know number and I'll give you some information, right? So how do I bootstrap this process? I have a name, right? And when I need to get out of it is an I know number. So what's the first thing I need to do? Andrew, yeah, I need to start somewhere, right? I have to bootstrap this process somehow. Right now I have no I know numbers, right? So I need to start somewhere, right? And essentially I start here, right? With the top most portion of this, right? And I need the I know number for root. So what's the I know number for root though? I'm kind of stuck, right? I don't know what that is. Jen, what's the I know number for root? Two, right? Yeah, we just know what it is, right? So the file system, actually I think maybe it might be even in the super block, right? So the file system will know this is the root I know, right? And by convention I think I need to see four. It's two, right? So we start with two. This is a agreed on number, right? Okay, now what do I do? What do I do? Directories contain information about how to map relative paths to I know numbers. So what's the next step here? Mukta. Yeah, so I'm gonna open the root directory, right? I'm gonna tell the file system, give me the contents of the file with I know number two, right? These are directed. This is just a file, right? Directories are just files, right? And I'm gonna open that up and there's gonna be a data structure in there that's gonna map these strings, right? To other I know numbers, right? And I'm gonna use that to map ETC to what its I know number is, right? And let's say it's whatever this was. I actually think I took this from the real example. So 393,218, okay? What do I do next? Sirach? Yeah, which directory? Yeah, remember, file system doesn't understand ETC, right? You say ETC is what, you know? Give me a number, right? So you tell the file system, I'd like the contents of I know the file with I know number 392,218 and I look in there for default, right? So I find default and let's say it's at I know number 392,247, yeah, and what do I do now? Yeah, so I open this and I look for keyboard, right? So you guys see how this works, right? It's not super tough. And then at some point, right? What I'm gonna find along the way is a file, potentially, right? Let's say the keyboard hopefully was a file. So at some point I'm going to get a file that is not a special file, directory file that is actually a file, and then I have what I want, right? So this is, you know, in a nutshell how path translation is done. What happens if I, let's say, so here I've asked, so there's a couple of things. So first of all, how many people have noted the fact that on your OS 161 kernel, open destroys the path name that's passed in? How many people have noticed this? Possibly because it frustrated you for a period of time because you were doing something that looked obvious that didn't work, right? So this is one of the reasons why open destroys that path name, right? Because open is taking the path name and it's carving it up into little pieces and doing these operations on it separately, right? So that's just just kind of an interesting knit. Second thing is what happens if I do an open from a relative path name, right? So let's say rather than root ETC, I was opening, you know, just ETC, right? Something that's relative to where I am. How does that differ from this process? It's quite similar, right? How does it, how does it differ? So let's say I'm in home your username and I open, I try to open this file, right? What do I start with? Nothing. It's very similar. The only difference is how I get going, assume it. Yeah, so I need the I know number for the directory I'm in, right? Well, how do I have that? I have to have it, right? Because otherwise, how did I get in there in the first place, right? At some point, if you run commands, you know, that operate on path names, I have to have translated that path name at some point, right? The other thing is I usually, there's a variable in my environment that says here's the path name where, you know, my current working directory is and I could pre-pen that to the path, right? So that's another approach, right? I could just, I could construct a full path name for this one. Brune, did you have a question? Okay. All right. Okay, so now we've done this. Does anyone have any questions about path name translation, right? This is not super, this is, you know, now that we've figured out how to organize things on disk, this is not too bad. What, you know, what's the potential overhead of doing this, you know, on the disk itself? What could potentially be a problem here about doing this? Especially if I'm doing it repeatedly, right? Remember, you know, users and processes know about these file names. So one of the things the file system is doing often is translating names to I know numbers, right? What's the potential problem here? Oh, listen, what did I have to do with each step here? Yeah, so especially if these I know numbers are sprinkled all over the disk, right?  So this is potentially a performance issue. And again, when we come back to caching, we'll talk about the fact that I nodes are a real, usual target for file system caching because they're very heavily used, right? Especially in path name translation, the directory contents can be cached as well, right? So again, directories are files. If there's directories that I'm using often to translate path names, or really for any reason, the file system may start to cache them in memory to improve the lookup times, right? And of course there are consequences to doing that, right? Namely that if I change their contents in memory and don't end up getting a chance to write those contents to disk before you pull the power cord out in the machine, then the file system might be in a kind of weird state when I boot it up, and we'll talk about how to address that online. All right. So now, you know, so now at some point, you know, I've done my path name translation, but when I start to use files, right, what I really want is data from the file, right? So we've talked about how to find an I node, right? But in many file systems, and some file systems actually, including one that we'll probably talk about in lecture next week, they've done this optimization where they actually can, they actually will store a small amount of data in the I node itself, right? So remember we said that there's a lot of files that are pretty small, right? In that case, there are some file systems that will optimize for this by actually taking the I node and having the I node be big enough that they can have some metadata in there, but they can also jam some data in there if they need to, right? So for small files, the file might actually live, the contents might live in the I node, right? So finding the I node might be enough to find the contents. On EXT-4, that's clearly not true, right? I mean, the I nodes are 256 bytes, right? So not a lot's gonna fit in there. And I think probably all of that data is used for file system metadata, right? If you start in and up, you know, you have four byte timestamps, and then you have this and that and some other data structures in there. I'm pretty sure that they don't do that, right? But there have been some historical file systems that have done this, but in general, right? Once we find an I node, we're not done, right? We need to find the contents of the file. And so now the question is, how do we translate an offset within a file into the data blocks on disk, right? So I found my I node, I'm in great shape, right? But now the process says, you know, I wanna read from, you know, offset 345 or if I'm reading it directly, I might say from offset zero, I wanna read the contents of the file. So how do I find these data blocks, right? And this is another sort of data structure design question, right, that we can pose and talk about. So one way to do this is to just organize these data blocks into a linked list, right? So the I node contains, so this is nice because the I node only has to contain a pointer to the first data block. And then each data block has to have some metadata that allows me to find the next data block, right? So each data block, you know, the format of the data box is up to the file system. So in this case, the data block has some format where it has a little bit of a header that has a pointer to the next data block and the rest of it is data, right? And I can use those pointers in the data box to follow this string of data blocks. So data blocks like eight times in the past 30 seconds. They follow these data blocks so I can find all the data I want, right? In the data blocks. So this is one way of doing it, right? And what's nice about this approach? Come back to simple data structure design questions, Frank. Yeah, I mean, data structure is kind of straightforward. Like it's a linked list. What else is nice about it? Yeah, so there's no limit on the size of the file. That's one thing that I really wanted. What else is good? Yeah, so there's a small amount of information in each data block and there's also a small amount of information in the iNode, right? All in the iNode has to contain is the pointer to the next data block, right? So that's nice. It's also simple, linked list. Small amount of information in each node. What's problematic about this, Jen? It's slow to do what? Yeah, cause if I, let's say I'm trying to look up a portion of the file, right? I've asked for 512 bytes that are three megabytes deep in the file, right? You know, this might be an MP3 that I'm playing, right? So I'm asking for the next chunk of the file. I have to start from the iNode, right? And he potentially, right? I could cache some information about where I am, whatever. But, you know, the point is that in general, to look up an arbitrary block in the file, I have to start from the front and walk the file all the way till I get to the point where I walk, right? And as files get bigger, this becomes more and more inefficient, right? So offset lookups are, oh, wait, right? In the size of the file, right? All right, so let's talk about a, it's starting to feel like VM data structure is all over again, right? So another way I can do this is I can have a flat array, right? So I have pointers to all the data blocks in the iNode in a single array that's allocated when I create the file, right? And now, in order to get to any data block, I just convert the offset to an index within this data structure and use that to find a pointer to the data block or the offset of the data block, right? So what's nice about this? Yeah, sir. Yeah, I mean, what's the lookup time? Oh, one, right? It's constant time lookups, that's nice. It's also simple, right? What's terrible about this though, Paul? Yeah, so when I create the file, I'm like, that's it, right? Like the iNode has to store this array, the iNodes potentially are fixed size, so when I create the file, I've determined exactly how large the file is going to be, right, and probably, and again, this array doesn't scale very well, it potentially could be quite sparse, right? If I make, if I decide to support really large files, then I have this really ugly empty array sitting around that I don't need for the small files, right? So this is, you know, this is kind of too bad. So the data structure that a lot of file systems actually use is a multi-level index. It's similar in a certain way to multi-level page shables, but it's not quite the same, right? The reason here, right, with multi-level page shables, we had this challenge of trying to design an efficient, a space efficient, and look up efficient data structure, given that address spaces are very big, right, and also sparse, okay? Files, we're not worried about sparsity, right? And the file size is flexible, right? So some files can get quite big, right? But other files, we want to be quite small, and we want the state that we have to store in order to support large files to scale nicely as the file gets big. But we also still don't want lookups to take forever, right? Like they did with the linked list. So the way that we do this is the following, right? So the inodes, inodes can store several different types of pointer, right? And usually inodes are set up to store, you know, various types of these, right? So inodes will have some references potentially to data blocks themselves, right? We call these direct blocks, right? So direct blocks are directly linked to the inode, right? So finding a direct block is a very easy process. I find the inode, and you know, so the first bit of the file is stored in the direct blocks, right? As the file gets bigger, what I do is I start creating data blocks that are themselves full of pointers to other data blocks, right? So this is kind of a second level of my tree, and I call these indirect blocks, right? What do I do when the file gets even bigger? Sam. Yeah, I have pointers to blocks that contain pointers to blocks, right? And I call these doubly indirect blocks, right? And what happens if the file gets even bigger? You know, I can keep playing this game all day, right? I can create, actually some files that have triply indirect blocks, right? Pointers to blocks that contain pointers to blocks and contain pointers to blocks, right? I think I got that right. Yeah, so here's an example, right? So, and this is a pretty easy example, but you can imagine how this scales. So I have my inode, right? This inode, how many direct blocks does this inode have? Two, right? So there's two data blocks that are linked directly from the inode itself, and then how many indirect blocks does this inode have? It has one indirect block that is pointed to two, so this is the indirect block, right? This is the pointer, this is the block that contains pointers to other blocks, right? There are two extra data blocks that are linked out of this indirect block, right? If I allocated another, let's say that my indirect blocks store four pointers to data blocks. If I allocated another data block for this file, where would its pointer go? Tell. So I'm gonna add another data block, right? How am I going to store the pointer to that data block? Where is it going to go? Robert? Richard? I have four data blocks, I'm gonna go to five, right? It's like, this is like the razor thing, right? Like, going to five plates. Nobody got that joke except for me. So, where is the next block pointer going to go? Okay. Yeah, so I'm gonna add it to this indirect block, right? Because this indirect block still has two more, two more data blocks that it can store, right? So I can allocate two more data blocks and associate them with this file before I have to potentially add a doubly indirect block or allocate another indirect block or something, right? So this is essentially how this works, right? As files get big, the nice thing about it is, so the wasted quote unquote space, right here, are any of these blocks that only store pointers to other data blocks, right? But you can imagine those pointer blocks grow slowly as the file size grows, right? And the nice thing is, my lookup time is still quite fast, right? So essentially I have O one for data blocks that are directly linked to the I node and O N for an indirect, like for an N indirect block, right? So for a singly, so for an indirect block, I have two lookups, right? I have to find this guy and then find the data block, right? Does this make sense to everybody? Any questions on this? Yeah, Melissa? Okay, so yeah, so the I node, that's a good question, right? So the I node might have other metadata in it that's taken up space, right? So yeah, that's a great question. These guys, these guys can you probably usually store more block pointers than the I node can because they don't have this other information in it, right? Like, I try to pack these things with pointers as much as possible. But it's a good question, right? Any other questions about this example? Yeah, Sumit? So data on data and then? Yeah, so you could, right? It's a trade-off, right? So if you do that, right? So what Sumit is asking is can I put data in here, right? Yeah, you could. But if you do that, you're just eliminating the number of block pointers that you can store in here, right? So yeah, you could have the blocks that were a mixture of data blocks and data themselves, right? I don't know, I mean, I think at this point, almost every conceivable option in file systems has been tried, right? So I'm guessing that somebody did that once, right? And some file systems might still do it. These are good questions, any other questions? All right, so what's nice about this approach? We talked about it a little bit, right? Yeah. Yeah, so I could potentially, it's usually not infinite, right? There's usually some limit based on the inode structure, right? So a lot of file systems will have limits for it, for example, like I can only have three triply indirect blocks, right? But I can still have like really, really big files, right? I'm not, there probably are file systems that don't have limits on the size of the file, but with modern file systems, those limits are like in the dozens of terabytes, right? So they're not, I don't know, they're not, I mean, I say this now, right? Yesterday I was joking with a colleague of mine because a lot of old, well I shouldn't say this, a lot of current camcorders and cameras still use FAT32 as their file system, right? FAT32 I think was probably invented in like the early 1980s, right? And FAT32 has this limitation that files can only I think get to be two gigabytes, right? Which I'm sure at the time they designed FAT32 felt like huge, right? It was like two gigabytes, who would have a single file with two gigabytes? Well now when you start taking HD video, right? What happens on these camcorders is they fill up two gigabytes, sometimes it takes about half an hour, and then they just shut off, right? They're just like, well, you didn't wanna record anymore, right? And actually when I bought this camcorder, one of the things I had to look for was a camcorder that allowed you to take longer videos in HD because a lot of them hit this FAT32 limit and they stopped. So Oliver and I were laughing because we were saying, you know, how likely do you think it is that when people created FAT32, they were like, yeah, man, like 20 years from now, this is gonna irritate people who buy these HD camcorder things that we haven't even thought of yet. So at some point like the 128 terabyte file size limit with the XT4 or whatever it is, may be important, right, to somebody somewhere, right? And so we shouldn't laugh about it because it's possible, right? I can't imagine what they'd be doing that would store that much data. What's that? Yeah, recording holograms, yeah, that's a great one. So anyway, if that's the future, that's very cool, right? And I'm excited to be part of it. And we're just gonna say this right now. I hope by 20 years from now we're recording holograms that take up 128 terabytes of space, right? Okay, so anyway, so there is some limit, right? But hopefully we push that limit out far enough where it won't bother us for like another five, 10 years, right? Other pros of this approach. What about lookup times? They're pretty fast, right? Like, so the inner scales with the size of the file, which is what we want, and offset looks up, lookups are pretty fast, right? And you could probably quantify this as probably like log n or something, but they grow slowly, right? They don't grow linearly like they did with my list, but they're not constant time like they were with the array. So this is another kind of artful compromise, right? And also it allows us small files to say pretty small, right? So potentially a file NEXD4 would contain one i-node and one data block, right? And a lot of directories probably do. In fact, if you go back to our example with looking at the super block, right? Remember we had that one group that had run out of i-nodes, but still had many data blocks. What's one reason that that could have happened? What's one type of file that we would not expect to take up much space that your system probably has lots and lots and lots of? Well, configuration maybe, I'm thinking of something else though, directories, right? Maybe that group is full of directories, right?   All right, so on Monday, we're gonna talk about two things. We're gonna talk about, first of all, caching, right? So we're gonna say, how do I make file systems look fast? It's our favorite old trick where I'm gonna use a small fast thing to make a big slow thing look faster. And then the second thing we're gonna look at is consistency, both in terms of just the disk failures, but also clearly file system caching makes the consistency challenge a little bit more interesting and we'll spend, I think a lecture and a half talking about that because there's some nice approaches to it. So have a great weekend and I will see you on Monday.


In this video, we're going to provide the solution to question number five from exam three for math 2270 Which of the following matrices has real eigenvalues? There are three matrices provided rs and t we have to decide which of them has real eigenvalues And which ones do not there are a few things we can do to find eigenvalues very quickly because after all worst-case scenario if we have a Matrix that's two by two matrix We could always just compute the characteristic polynomial and find its roots, which are the eigenvalues That's sort of like a worst-case scenario this question's intending for us to be able to discover Eigenvalues a little bit quicker than that so what are some some of the tricks of the trade here when you look at when you look at r? You'll notice that r is an upper triangular matrix because you have a zero below the diagonal right there If you have an upper triangular matrix a lower triangular matrix or a diagonal matrix Which is both upper and lower triangular the eigenvalues are going to be those numbers along the diagonal only for triangular matrices here And so we see that the eigenvalues For r are going to be the numbers one and three in particular Those are real numbers and so we see that r will be a matrix with real numbers So we should include that in our solution when we look at Matrix s you have one two two one This is an example of a symmetric matrix for which we've learned that symmetric matrices always have real eigenvalues So that's one of the easiest things to detect. I don't even have to compute the characteristic polynomial of the eigenvalues I know they'll be real even though I have no idea what they are at the moment Whenever you find a symmetric matrix, it'll have real eigenvalues That's also true if you have a Hermitian matrix for which a Hermitian matrix is gonna be a complex matrix Which is equal to its own conjugate transpose So I don't want you to assume just because you see a complex matrix with non real entries that it means the eigenvalues are non real No, no, no, no Hermitian matrix is exactly a Non real matrix whose eigenvalues can be real. So so far we have r and s and if we look at The list of possibilities here, you'll notice that there is no solution that says r s and t So we can already see at this moment that the correct answer would have to be d R and s by process of elimination, but why does t not work? Well t is an example of a rotation matrix Just as a reminder. This is a rotational matrix a matrix of the form cosine theta negative sine theta sine theta and cosine theta now I sometimes forget Where does the negative sign go does it go here or here, right? And if you move the negative sign from from the top right position to the bottom left position You're just gonna switch it from a counterclockwise rotation to a clockwise rotation So it still would be a rotation matrix just yet the patient to the direction where this is the standard matrix for rotation in the plane about the origin by the Angle theta this right here is an example of a 90 degree rotation counterclockwise right here Why is this relevant to our discussion of real eigenvalues here? Well, one thing to report is that a rotation matrix never has real eigenvalues The only exception of that would be zero degrees and a hundred and eighty degrees And that's because if you have a zero degree rotational matrix that's just the identity matrix and that situation with the eigenvalues are one and one and If you'd rotate a hundred eighty degrees, that's actually just equal to negative One times the identity matrix in which case your eigenvalues are negative one negative one both Both of these are example of diagonal matrices for which we would invoke the previous principle But for all these other Rotational matrices we get that they don't have real eigenvalues There's no vector when you rotate it which will be a scalar multiple of its original using just real numbers In fact the eigenvalues of this 90 degree rotation are going to be plus or minus i which are not real numbers You can find that out again directly from the Characteristic polynomial, but again this question is intended for us to be able to find The eigenvalues whether they're real or non real without having to calculate the characteristic polynomial So rotation matrices. Nope not going to help us out here We can see the eigenvalues from a triangular matrix and we know the eigenvalues of a symmetric or Hermitian matrix are always real So D would be the correct response