All right, welcome back to operating systems. So your midterm grading is almost done. Hard to schedule like 13 TAs to grade it. So two of them got delayed, so they're grading it as we speak. So it should be back to you tomorrow. Alrighty, so today is a fun lecture.  So where we left off last time, we were talking about how to actually store the file in the disk and how you describe where the blocks of the file are. And we ended up with indexed allocation, which is basically a big array. So index zero is where points to where block zero is, index one points to where block one is of the file, so on and so forth. But we discovered that it can only hold a maximum file size of 16 megabytes, which is no good. So an iNode is a compromise, and this is how files are actually described on your file system. So it contains everything about the file, so the mode, so those are the permissions, who owns it, so like the user ID that owns it, and the group ID that owns this particular file. Timestamps are stored directly on this iNode, and that's like when you created it, when you modified it, when you last accessed it, how many blocks it takes up, and then where it describes the actual contents or the data of the file is through a bunch of pointers that point to blocks. So there are several pointers on the iNode structure itself, that point directly to blocks. In the case for Linux, there are 12 direct blocks, so there are 12 spaces there that point directly to an iNode, so in the case that the file takes up 12 blocks or less, we don't have to allocate a block just for pointers. So if the file is bigger than 12 blocks in this case, we have an entry that points to a single indirect block, so that will point to a block that is full of pointers, and each of those pointers points to an actual block that represents the data. So this is where we left off last time with our 16 megabytes, that could be done through single indirect. Now, if the file is bigger than 16 megabytes, then it would go through double indirect, so it points to a block that is full of pointers, and each of those pointers points to another block that is full of pointers, and then those point to the data. So that's like having two levels of page tables. And then in the case that the file is really big, then it would be triple indirect, so points to like an L2, points to an L1, points to an L0, and then those points to blocks. So any questions about this? So it will fill them up in order because the more indirection you have, the slower it is to access because I have to read a block to be able to read the pointers. So if my file only consumes 12 blocks, then I use the direct blocks, and then as soon as it consumes a 12th or 13th block, then I have to allocate a single indirect entry. I have to make a whole entry through full pointers. I have to create one and then point it to the block, and that would be slower, but if it's bigger than 13 blocks, that's what I have to do. So any questions based off that? So direct, fast, so the idea here is if the file's small, I want to be really quick. If it's big, well, I want to also support larger files. So the inode, again, just holds some metadata and pointers to blocks. Smaller files only use direct pointers, so they can access it faster.  And there is also an optimization. You will encounter in lab six. So if it's a very, very, very small file, remember we argued that, hey, the blocks are probably like four kilobytes or eight kilobytes. If it only consumes like 12 bytes or something like that, instead of allocating a whole block, well, there's an optimization to actually store the contents of the file on the inode itself. So now we can have this scenario. So assume that the inode stores 12 indirect, or 12 direct pointers, one single indirect, one double, and one triple. If the block size is eight kilobytes, and a pointer is four bytes, well, we should be able to argue about what is the maximum size of the file that's managed by this inode, or index block. So in that case, the number of pointers we can fit on a single indirect table, same calculation we use for page tables. So it is the size of the block, which in this case is two to the 13, divided by the size of the pointer, which is two to the two, so that gives us two to the 11. So the number of total blocks we can address with this inode, well, we can address 12 through the direct pointers, and then two to the 11 with the single indirect block, so that's a block full of pointers that points to other blocks, and then through the double indirect, it is two to the 11 to the power of two, all that to the power of two, because we have two levels we go through, and then for the triple indirect, it's two to the 11 all to the power of three, because we're going through three levels of indirection there. So technically I would have to add all these together, but the two to the 11 all to the power of three, that will dominate, so if I want to approximate it, I can just approximate it as two to the 33. So the maximum size of the file now would be, well, I can point to two to the 33 blocks, slightly more actually, and then if I multiply that by the size of the block, I get the maximum size of the file for this case. So in this case, the maximum size of the file I can support is 64 terabytes, which is pretty big. So we're all more happy with that, that's a more reasonable file system. So this is our current inode. So your maximum file size is likely something like 64 terabytes, past that we have to change the structure, but for now this should keep us good for, another five years or something like that. Yeah, question? Models get pretty big, but yeah, 64 terabytes per file should be enough for quite a while, probably more than five years. So this has been around for, I don't know how long, very long time.  So each of the file names you've ever used ever, well, the file names are basically just for you. The names just help you refer to inodes and an inode is whatever the operating system actually cares about. So if I have a file called todo.txt, that name is just going to point to an inode and that inode describes the contents of the file who owns it when it was last modified and all those things. So taking a name and pointing it directly to an inode, that it is called a hard link. And why is it called a hard link? Because as we'll discover, there's something called a soft link. So now we can actually try to describe what happens with LS. And most of this lecture will be just playing around with LS and making sure we understand it because we probably don't right now. So I will create a file called todo.txt. Let's make the contents just hello. So we've all used LS before, I hope. So does anyone know what all those things in LS mean? Can you describe everything in that line? Yeah, so this is the permissions for the file. So in this case, do you know which order they're in and what they all represent? So who can write to this file? Anyone help? Yeah, whoever created it, which in this case should be John. So for this, these are the permissions for the owner of the file. So whoever created it and here, this is the owner of the file and this is the group owner of the file and these permissions are the permissions if you are in the same group and not that user and these are the permissions you have if you are not that user and not part of that group. So these are like the default permissions you have. All right, so this is my username. Yes, so this would be the user that owns the file and this is a group that owns the file. Anyone know what this number means? All right, let's make a hint. So let's edit this file. So it was seven before. Now it's that number went from seven to 13. So what is it likely? Yeah, number of characters are more operating system. Operating system just cares about bytes. So it's the size of the file and bytes. All right, what about this? Yeah, last time this file was modified. Why does it show that? I don't know, and then the file name. So there's one mystery number.  Anyone know what this number means? It and it? Nope, any ideas? If you knew what this number means, you didn't need this course. This number is the whole reason this course exists. Not really, but kind of. So to create a hard link, you can create a hard link. So remember hard link, it's just a name to an inode. And in fact, we can use a new column in LS. So if I use dash i, it creates a new column. This new column is some gigantic number. What is this gigantic number? Well, that gigantic number is actually the inode number that it refers to. So this means that the contents of todo.txt is on inode gigantic number. I'm not gonna say it. So in order to create a hard link, I can use the ln command. And then the first argument is a name that points to an inode. So this is, I want to create another name that points to the same inode as todo.txt. Now I can call it b.txt. So if I do that and LS and show the inode number again, I can see that the inode numbers are the exact same. Oh, something interesting happened with that number. What's likely that number? Close, yeah? Yeah, the number of hard links to that inode.  So if I create another one, so let's say I create another hard link called d.txt. I can see, oh, that number has increased again to three. And now all of these names refer to the same inode and that describes the contents of the file. So, anyone want to tell me what happens if I just edit, let's say b.txt? I say hello everyone. Now, if I look at the contents of todo.txt, what am I likely going to see? Yeah, hello everyone. Because while the inode describes all the contents of the file, so now since they are all hard linked to that same inode, well, if I open that file, it will open that inode. That inode actually describes where all that data is. So if I modify that inode through any of the names, it modifies that inode and the contents change through all of them. All right, any other questions for that? Kind of fun, right? Not really. So what's the point? Why not create two what, sorry? So if I want them to be this, like just copy a file or something like that, could be bad, could be not. Let's see, we can use dash A and C. Now we know what that number means. Well, directories aren't bad, but we see here the number of links to dot is two. Does that make sense? Yeah, so what does dot dot mean? Yeah, this directory, the contents of this directory need to be stored somewhere. They're stored in an inode, in this case, whatever, ends in 60. So dot points to this inode 60 and since there are two links to it, what is probably another link to it? The absolute path or more specifically whatever it's called above it. So in here, if I just back up a directory, well, I have to be able to get to this directory. So in this directory, inode 60 is called test directory. So that's its two entries. One entry is test directory and then another entry that points to that same inode is dot in that directory itself. So that's fun. Then why is dot dot have three entries? Yeah, so for this dot dot, there's three things pointing to it. So I'm pointing through it through dot dot. If I go up to dot dot, well, what's it end in 56? So inside of the directory itself, it has a dot, which is also 56. And then if I back up again, it's called whatever it's called. Oh God, it's called inodes. So this is three and then in here it's called dot and then in this directory it's called dot dot. So yep, so let's see. If I do make dir, say directory one and then do it again. Oh, the number of references to dot just went up by one because in directory one, there's a hard link to it called dot dot. Cool, huh? All right, any questions about that? So how do they keep track of it? So you will discover how they keep track of it through lab six a bit, but really your whole file system hierarchy is a tree. It's a, in fact, it's a DAG if we remember algorithms and stuff. It's a directed day cyclic graph. And the only thing you need to know is the root and the root has a very specific inode. The root directory is always called inode two and that's how everything starts. To see that I am not full of it, I can do LS of the root directory. Inside of the root directory, it will have an entry called dot and it is inode two. So I was right with the magic number and the root directory is the only one that's special where it gets to loop on itself, in which case it has an entry for dot dot, but because it's the parent of everything, it's also the parent of itself. So it just has a self loop at the top. But knowing this, so everything is reachable through the root directory. So you just started inode two and then you can just go through everything. So just operating systems is really just magic numbers all over the place. So what else can we do? Oh yeah, we might notice other fun things. So if I do RM of a file, does that actually delete anything? Yeah, it just removes the name. So if I RM it, doesn't delete a thing. All it does is, well, the number of references went down from three to two because I deleted one of the hard links, but it doesn't actually remove anything. The name is actually a bit silly. In fact, if I wanna figure out what system call, RM actually does, what command would I use to do that? S trace, everyone's friend, all right. So if I S trace, let's say I S trace removing b.txt, I can see that, oh, there's no removed system call. It's actually just called unlink. So remove does not exist. There's only a system call called unlink. And all unlink does is remove that name from the directory and that's all it does. So what's the condition that I could actually delete the contents of that file from the hard drive and free up some space? Yeah, there's no more links to it. So this is also how your recycling bin works and why it should be instant. So as long as there is one hard link pointing to an inode, it's not free. So whenever you delete a file, how your recycling bin works is it just keeps a reference to that inode around and it'll keep that reference around for 30 days or whatever, but keeps it active so the hardware doesn't actually delete that file. And then eventually if you want to restore it, well, all you do is recreate a name, which is really quick and point it back to that inode and you've recovered your file. That's basically how your recycling bin works. If it's, so that's also why it's like that, even if you undelete a file that's like 20 gigabytes or something like that, it'll be instant because all we're doing is pointing to that inode again. We're not actually copying the file or doing anything random like that. But fun fact of the day, any questions about that or how anything else would work? All right, what about, what's going to happen if I copy to do.txt to, I don't know, d.txt? Yeah, so in this case to properly copy the file like kind of behaves like fork. So they should be exact copies of each other at the time I did the CP command, but they should be independent past that point. So if I do this, I should see that they are different inodes. So they are pointing to different blocks on the storage device itself. And in fact, they are different inodes. And now if I edit one file, they just have the same contents whenever I called CP. But after that I can modify one and not modify the other. So copying would just create a new inode and make the contents match. All right, any other fun questions? All right, well let's look at the other part of it. So here, so remember deleting a file, RM not a thing, can't delete a file. So you just have the unlink system call which just removes the hard link. And if there are zero references to the inode then your operating system can go ahead and actually physically delete the file from the hard drive. But guess what? Deleting files is also slow. So likely what your operating system will do is if you have no links to it anymore that inode doesn't exist. And you would instead of clearing it up and like zeroing it or something, which would be slow, all you do is mark it as inactive. And this is also why you can sometimes recover your deleted files. Well, they're just marked as inactive. So if you know what an inode looks like then you can just kind of brute force go through all the inactive ones and see if it still points to valid data. Because likely it's still there if you've only just tried to recover it and the operating system hasn't reused that block.  They just know what they look like and know how to search through all the inactive ones to see if there's any valid data still part of it. All right, so now we can talk about soft links. So soft links, I might also call them sim links. Soft links mean the same thing. The concept of shortcuts and windows also mean the same thing. So what a soft link is, is instead of pointing to an inode it's just a name to a name. You can think of it that way. There's another step in the middle but conceptually a soft link is just a name to another name. So the soft link target doesn't need to exist. Soft link targets can be deleted without the notice of the soft link. You just get a weird error and if you can't resolve the soft link leads to an exception. So why do we have soft links? So let's try and create a soft link. So I can create a soft link. All I have to do is do dash s. That means create a soft link or sim link instead of a hard link. And I'll also point it to to do dot txt and I'll call it b dot txt. Now if I'll s here, I can see I created b dot txt and it points to to do dot txt. It's a little bit more roundabout because it does need an inode and the contents that inode stores is just the name here which is to do dot txt which is why the size is eight bytes. So now what a soft link allows us to do is while we can create cycles it doesn't have to follow that directed to a cyclic graph and sometimes they're really useful so like web servers use this like your Python executable sometimes it's just a sim link and in order to move to the next version of Python all it does is update the sim link to point to the new program and that's it and typically you just access it through a sim link. So now if I tried to cat b dot txt I get hello everyone which is the same contents of to do dot txt. So what it will do if I cat b dot txt well it knows this is a sim link so in order to find the inode that has the contents of the file it knows that it needs to first look at to do dot txt because it's a soft link to find the inode and then it would find this inode. So same way I can kind of modify that same file. So any questions or want me to do anything silly with these sim links or soft links or whatever you want to call them. Yeah so if I open b dot txt I get the contents of to do dot txt. Yeah so the contents are through that inode but it's called b dot txt because that's the name we refer to it as. But really when we're modifying files we're modifying what's stored on that file and that is stored in the inode. All right let me do anything fun any ideas with how we can break this do I still have yeah remove the hard link or yeah so if I remove it looks angry immediately so if I do this looks a bit weird so I can cat it gives me a weird error which doesn't make sense it says b dot txt no such file directory which is a bit weird because well b dot txt clearly exists what doesn't exist is what it points to just gives you weird errors. So yeah you would get an error because it can't actually find an inode that has the contents of the file or anything like that. All right anything else I can do fun with sim links so our cycles bad or infant loops everyone loves infant loops so I could probably create one more soft link that would create an infant loop right. What should I create? Yeah let's create a soft link that points to b dot txt and call it to do dot txt. So in this case looks kind of bad. So to find the contents of b dot txt it's to do dot txt to do dot txt it's b dot txt. What happens if I do this? It will know an error. An error just hangs forever how smart are kernel developers? Ah too many levels of symbolic links. All right well then the question is who's smart? The kernel developers or whoever wrote cat? Kernel cat how would I figure out who's smart? S trace yeah I can S trace it. So if cat smart well it would open b dot txt then I'd see it open to do dot txt maybe I see it go a few times and then give up if the kernel smart I probably will only see an open of b dot txt.  So we can see we just tried to open b dot txt and that was it and then we got an error immediately from the kernel so the kernel is smart. All right any other questions about fun sim links? Too many levels so it went through like the cycle was too big so it has like a hard limit for a cycle so it will only go through like 10 sim links or something like that. Yeah you can have a cycle of more than two you can have three there's gonna be some limit in the kernel where if you go through sim links after x number of steps it's just gonna give up and give you an error message. All right so also fun security tip if you allow users to upload any type of file to your server well one big vulnerability you could do is upload a sim link so you could upload a sim link and point it to root and then suddenly you can access any file on the server which is fun and that's why guess what?  All right what other fun things can we do? Oh other fun things we can do we can use the stat command and stat will tell us all the information on the inode except well the file name is not stored on the inode well tell us a whole bunch of fun stuff so this is the size of the file in bytes this is how many blocks it takes up on your device in this case it seems really frankly stupid because it takes up eight blocks and it's only 16 bytes so why would it take up eight blocks and only be 16 bytes? Well the blocks reported here is stupid so the blocks reported here for some reason don't ask me why that is the number of 512 byte blocks and it is just hard coded at that number for reasons I don't know so the IO block here is the size of the block on your actual device and in this case if you just take 4096 and divide by the hard coded 512 you get eight so this is actually pointing to one IO block one block on the hard drive itself so all your files will be at least for this it will be in multiples of blocks of eight because it's a dumb fixed size and don't ask me why you will encounter that in lab six so just remember that this stupid blocks is hard coded 512 bytes all right so it has some other things so device is just the magic number that tells you what actual physical SSD this is on and then the IO number, number of links, permissions and then there's a whole bunch of timestamps so access, modify, change and birth modify and change sound like the exact same thing but modify is the last time you modified the contents of the file and change is the last time you modified the iNode itself so like you change the permissions or something that didn't actually touch the contents of the file and guess what all these timestamps you can change at will and this is why timestamps on your device don't matter because if I wanted to I could change all these to 1968 or whatever year I wanted to and no that is not the year I was born do not be smart asses all right any other questions about that stuff or other fun stuff I could do so where's the iNode actually stored so you will think you will it'll be part of your lab six but the iNodes are stored on blocks so there'll be some blocks in your device set aside that just stores a whole bunch of iNodes so they're stored directly on the device yeah yeah if you have a free trial of something that has like a timestamp it depends how they check when you last accessed it if they check it through file timestamps yeah just set it back in time some games do that too they care about your system clock so you just change the time back a bit and they think it's whatever time you set it generally it's not that smart and you know if you're taking an English course or something like that they don't know you can just freely modify these things so you can just modify it yourself and say hey I submitted this you know 10 weeks ago no problem also I definitely never ever ever did that so if you want to no wait should I tell you how to do it okay yeah so oh that's freaking out cool all right so in order to modify it whatever I'm too deep now all right so this is whoops d.txt let's see everything I last modified it at 31 or whatever so if I modify it now and I stat it I should see that okay now I've changed the i-node I've changed I've modified it and I've accessed it beforehand so if I want to update all these timestamps without actually doing anything to the file that's what the command touches for so if I touch it all it does is reset all of the timestamps to the current time so now I've reset all these to whenever I ran touch so access modify and change and guess what if you look at the man pages of this well it lets you update and access modification times of each file oh guess what I can change the modification time I can change the whatever and it just takes the date of this format change it to whatever the hell you want so now you can tell after taking this course makes life harder for you because you guys can't fool me you could just use that oh yeah no problem I submitted it a month ago what the hell are you talking about oh that was before it was even released oh okay makes sense so I definitely didn't show you that command and you forgot all that so any questions not regarding that so that's fun you can also can this thing stop freaking out you can also you know use it to mess with your friends if you really want prove to them that you know you created some sick software before you were even born and they have no idea so you can play a lot of tricks with first years all right so real quick too for this example so touch if you just give it a new file name and that file doesn't exist it will create an empty file for you with that name so in this case if I do touch that will create a new i-node and the contents the i-node is nothing so it will just be an empty file if I do ln that should make a new name b.txt points the same i-node as to do.txt and then if I create a soft link called c.txt that should point to the name to do.txt so before the move command my file system should look like this so c is a soft link so it points to to do.txt and to do .txt and b.txt are both hardlinks point to i-node 1 so any questions about how we got to that point so now if I do a move move is a weird name because it doesn't actually move anything all it does is rename the file so technically it should yeah it should probably just be called rename because move to do.txt to b.txt all that does is change the name of to do.txt to b.txt so after the move well we don't have to do.txt it's just called d.txt now and c.txt that soft link now points to the name to do.txt which I'll put in a filled in box because it doesn't exist anymore and now if I do rm b.txt that doesn't actually move anything it just gets rid of the name b.txt now it points just to an i-node so any questions about how we arrived at this alright so in Unix everything's a file so even directories are types of files so the only thing special about a directory is well we can go back and see what's special whoops so if I start . the only thing special about directory is here it tells you what the type of the i-node is for directory it's just type is a directory but other than that it's not that special it takes a block so it consumes some storage on the device and the contents of the directory all they are is name i-node tuples and that's it so the contents of this directory would just be a bunch of tuples so there'd be . pointing to this i-node an entry for . pointing with this i-node an entry for b with this i-node an entry for d1 with this i-node so on and so forth so all the directory is is just a specially formatted contents that are just name i-node tuples and you can think of it as just a list of name i-node tuples that represents everything in the directory that's it so any questions about that? the directories turns out there's not that much special about them so on ux everything is a file so like some types you can create name pipes if you want that are represented through an i-node so that's a way to share them between processes sockets can be represented as an i-node and all sorts of fun things in fact if you'd like proc look at proc cpu info or all your proc things from lab was that lab one those don't take up any space on your hard drive but they consume i-nodes and you can actually use them as if they were files but the only magic that happens with those is those i-nodes while the kernel controls so if you try to cat it and you try to access cpu info or anything in the proc directory the kernel will essentially intercept all of your accesses to that i-node and it will just make up data for it because it just needs to make up some bytes so you can read and write bytes to it so if you just proc proc one command or status or whatever the kernel knows that you're trying to access that data and it would just provide that data through that i-node alright any questions about that so if you stat all those i-nodes you'll see that they consume zero bytes on the drive and the kernel just handles them specially so you're not allowed so if i hardlink a directory to a different name so yeah you can try that but um you are not loud because that would break the hardlinks are always a directed acyclic graph so if i tried to do something what you want me to do like if i create a hardlink to dot and call it that not allowed to create hardlinks for directories yeah you're just not allowed to create a hardlink for a directory ever because otherwise you could create cycles and you break things so yeah you're not allowed to create hardlinks to directories the kernel will forbid you from doing that otherwise you could do odd things so all the dot dot and dot dot dot dot and dot dot those hardlinks are all managed by the kernel itself you're not allowed to touch them and that's why there are separate system calls specifically for directories sometimes all right so now we can say well what's stored on an inode so we'll go through this in record time so what's stored on the inode the file name not stored on the inode names are only stored in directories the inode also doesn't know what containing direct what directories it's in the file can also be in multiple directories the file size is stored on the inode the type is stored on the inode so if it's a directory if it's a regular file or a socket or whatever or a simlink the number of softlinks not stored on the inode location of softlinks not stored on the inode the only thing that's stored is the number of hardlinks to that inode so this is stored on the inode because while the kernel has to keep track of this number because if the number of references goes to zero then it means this file is not used anymore it can mark it as an active or less likely delete it and the location of the hardlinks aren't known for the inode itself if you need to ask you know what are all the names that point to this inode you would have to traverse everything starting from root because you have no idea the access rights or permissions are stored directly on the inode same with the timestamps that we now kind of know how to modify and the file contents are sometimes stored in the inode itself so you will find this optimization for simlinks that are very very small so instead of pointing to a block so if you're only storing like eight bytes of data there's no point consuming an entire four kilobyte block when there's some extra room on the inode itself you can just store it on the inode and then the order list of data blocks well that is what an inode is basically there for it's to tell you where the contents of this file actually exist on the disk so any questions about that all right so other fun things so writing data to a disk is slow so generally what happens if you are modifying a file well the operating system is going to have to read that block of data into memory and if you modify it well it's slow to just write it directly out to the drive typically what will happen is it will just cache your writes in memory and they won't actually go to the disk because that's really slow and also well if you just modified the file likely you're editing the file so you're going to probably modify it again so in that case they have something called temporal locality so if i modify it it's very likely that i will modify it again so it's probably a good idea just to cache it keep it around in memory and not actually write it to disk and likely if i'm modifying a file and i modify block zero well i will probably modify block one at some point in the future so maybe i want to load that in the memory before you actually use it so that's there already that's something called prefetching so what will happen to that is because writing to slow is really slow there'll be a kernel thread or something like that that just if there's some idle time it will periodically write the changes out to disk and that is why sometimes when you are modifying a file and you pull out the power or your battery dies or something like that all your changes get lost even though you would assume that hey i modified a file it should be on my disk and it's not because it was cached in memory you pull out the power and it wasn't actually written back out to disk so you would lose some information and spoiler alert this is also why you know that if people are using windows or i guess mac you know when you put in a usb drive and it's like safely remove safely remove means flush the right cache so for instance you might know sometimes if you put in a usb drive this has happened to me and you copy a gigantic file to it and you know that that usb drive is slow sometimes the operating system be like yep i'm done i have copied the contents of the file but if you were to yank it out well it didn't actually finish writing all the contents back out to the usb drive so if you hit safely remove from hardware you will sit there for like minutes while it's actually physically writing out the data back to the drive and as soon as it tells you it's safe to remove it it means it's written everything back out to the drive so it's actually stored on the device yep what is what so unmount so you'll get kind of familiar with them but unmount basically takes a device and maps it to a directory so you can access it and what was the other one unmount and eject eject is like the same thing as unmount so yeah in order to make devices available sometimes you have to just give them a directory name so you can access them through that directory name but so there are system calls to actually go ahead and trigger a write to so this is basically what that safely remove drives so there's a flush and there is a sync system call and that basically just forces all of the right caches to happen and now we are out of time so just remember poem for you we're on this together