Transcript for:
File Systems and Their Implementation

in this video we're going to look at creating a file system and file systems are rather complex so we probably won't get to everything and most of this is going to be very simplified but let's take a look at it and get started at least so kind of the plan is we're going to use a super block we need to implement a super block first to talk about the overall configuration and then we'll talk about I note for the files and then the disk box for the files within the file system and then how we if we have time how we would address accessing a file within this file system that we've created so to get started we're going to power dot H is we're gonna want to have a struct that's the super block and so what goes into this super block well this is the meta information about the file system so I'm minimum we might want to know like how many I nodes and the same number of this box and let's also say the size of the disc locks and so we have these three ends right now we could also do the size of the inodes but we're going to have a very simplified version so it might not be necessary okay so our super block and as you mentioned we're also going to have high notes and for now let's just say size and named and we're also going to need a disk block and we're going to use have a file allocation table approach and we'll have the next block number and then a bunch of space or data and let's make this just 512 bytes okay so that's you know we're gonna modify this as we go we're going to think about what operations we want on this and one operation would be to create the file system and again we're just going to do a very simple set up and so we're not going to we're going to use global variables so I want to be able to create and mount and let's say sink so a couple of comments okay so let's get started with that and that's yeah so that lets open up dot C file in just for reference I'll put that there now in that C file want to keep my global variables and so I want to want to declare those mainly the I'm going to declare the super Bock I'll declare and I note that the I note and in this box I can work with internally so to implement the create function let's set these up quickly so we're going to put this in a file on our regular file system so why to want to save these things for now I want like when I create the file system I'm just going to initialize my super Bock data structure and just arbitrarily I wanted to say something like now inodes let's say is equal to 10 and this is just random and let's say this is a hundred now for for the size of the box let's [Music] use the size of operation okay and so that's that's pretty much all that we're doing on on this we now another question is how are we going to represent the rest of these things so let's create an array of what's currently open okay so we'll create two arrays like this and then what we're going to do is we're going to initialize these and we should allocate that space first so [Music] let's see first was style so let's do my luck and one thing we're going to do in this video is use man pages a bit right so if I'm blanking a bit on the border parameters from My Luck I wanting to go and use a man page for my luck and I see I just need to pass it the size parameter and then that will allocate that okay yeah I'm going to need to include standard Lib so I just need the size of right oops this that one doesn't have a man page okay and again because we're trying to be quick and not careful I'm not going to check your fiber succeeds so I've allocated that space and I want to initialize it and in some ways say I nodes right and the data here is the size and a name and when I say minus one if it's not allocated right so sighs a name and now I need to do the same thing for the disk blocks so I want to allocate them in memory and then we go through initialism and I'm not going to bother to initialize the the data because it doesn't matter okay so this has initialized the filesystem right we set up our super block and then we set up our I nodes and then we set up our disk blocks how so how can we test this right well we can't do too much right now right so what we need to do is do a sync we need to be able to to write write it so we're going to use F open and F right so we're going to open up a file so we'll use standard IOH we want to give it a path theme in a character code the character code is or wanting to do open for reading and writing so let's fix our includes and this takes a this is going to turn a file pointer so let's I'll heat the file pointer I don't think we need to make that a global and I'm just going call a file system disk our data and I want to open it for right plus and then later on I'm going to need to do a close so I think it's a good habit just to when you do it open to also do the close all right just so that you're in the habit of doing that so we're going to do the clothes when we're done and then we're going to want to write data so F right and we're going to pass in the file pointer how much data we're writing how many blocks oops I'm sorry so the first one here is the pointer of the data were we're writing how big that data is how many items were writing and then the file so first we need to write out the superblock so we into the super Bock and then the size of the superblock we're just doing one of them and in the file okay now that I notes and we're just going to get right through so we got two loops from be doing and here we're going to do a half right and I note and let's try this and then our disk blocks okay so let's see what errors I've made in there so let's create test file so let's try creating the file system in a sink in the file system okay so let's work on a file so this is going to pend okay oops okay so lots of lots of things so let's start up oops so I made a typo up here and hopefully that was a bunch of it okay next one is lying 37 okay so it doesn't okay so what would want to do here is actually probably string copy right so so let's try that so we're going to need to include string.h anyway pass in the destination and the source okay and then I forgot to change my data structure and okay so I'm going to need to pass it the address here and then probably address for these also I could also multiply and add okay so right now I don't have the data file there so if this works I should have a new file and here it is and it's not very useful right I can't really see very much in there let so the size though is 50 1000 bytes ish right and that makes sense because we have a hundred box and each box is about 51 512 in size let's play something more interesting in there so the I set eight characters for my name so one two three four five six seven and then on all determinate don't fit to know in terms of counting for space and so now if I do if I run it I should see those I didn't make it though so if you don't compile your code it won't make changes and there here are my iron I nodes right we've got to cut this with a hex editor too I suspect you don't have the patience to kind of deconstruct the data like that so basically our super block is up here and then our eye nodes and then our data box are starting so we have the the first part looks okay so far next what we're going to want to do is to be able to mount the filesystem and mounting basically we want to open it up and access it for for use and so when we do a mount we're going to be opening it and copying data into our into it based in some ways well it's just the opposite of the right the sink so you can think I think as doing a write the amount as doing a read I'm only going to be reading it so I'm just going to open it as a read and if I look at f read I want to give it the destination point there where I'm copying stuff to how big how many and then the file okay so I sent to the same as right so I'll read it in the super block and then read in the I nodes and then read in the disk blocks now I don't know you know how do I know that is this working so let's add another function this would be more interesting if we had it if we took more time to have separate things right to open up multiple ones so we could see different data okay our super so let's just look at this and copy so if I want to print out the number of eye nodes and the blocks number of blocks and the block size and then let's print out the inode information and then let's print out well you know right now I don't want to print out the the data in the box so let's just print out the the chains oh I did so something I we need to fix is we don't hook the eye nose to the first disk walk so we need to fix that okay okay so let's fix our data structure and then we need to fix our initialization and it's set to minus 1/2 note that I said it 2-1 since it's not valid to start we shouldn't need to to change anything in the sink okay so and the read the mount the read she shouldn't have to change either I want to delete this for now since it's out of date so let's compile make sure it still works or still compiles at least and it's try running it now it should be slightly bigger so it's 40 right and that makes sense because we added 10 integers and each integer is 4 bytes so that's 40 more bytes so I think that data is there it's hard to hard to tell just looking at it but let's let's assume it's working let's go to the test file so I've created it so that's well let's do a print and make sure the print works like that and so we have all of our box none of them are pointing to anything and our I know it's look right right now if I want thing to notice the size of box is bigger than 512 and that's because each box also has an x-block pointer okay so next let's comment out these parts and just do the mount and see what happens see if it still works and it and it doesn't right so it crashed so it probably crashed because of how we're doing these read it probably doesn't like let's okay so crash because it didn't like we're messing up on all these let's let's change how we do this I think this is probably more efficient anyways let's try this so I just want to say I node give it that address and then the size and then here I'm gonna say so let's try that and let's do something similar for the disc box let's try the oops okay so it's when we're going printer inodes oh okay I didn't allocate this space so I'm just randomly writing that space so I should do some Alex oh no that wasn't it I think it's so good idea to do the Malick's okay because these are arrays I don't need to this is just one elements I need to use the address of operator for these these are arrays and so I don't need to use the address of operator and this is the blocks right this is the correct file system let's as try changing our our sync to use this style also and I want to see if it turns out the same so I'm going copy the my current version and then we'll do a diff after to see if they're equivalent and I need to change the test file and compile and now if I tip there okay so they're exactly the same they're identical so what have we done so far so we've we can read and write the superblock we've were reading and writing the Box in the data we haven't actually created a file yet instead of faiello so that can be our our next task so let's go back to our system and we want to allocate file and let's pass it in a character string of at most seven characters well let's say eight and we'll rely on them to include their no and it's going to no return file number that they can work with so what do we need to do the allocate file will first find an empty inode claim it claim a disk walk or walk find and claim a disk block and then return the file descriptor so let's have those as internal ones and let's just hurry through the whole super Bock and return the first one I thought about doing random things to make it more interesting but I think we're too pressed on time okay so we didn't see it the first block is empty or not and if nothing works out we'll return to minus one and we're going to a similar thing for the this vlog now for the for the disk block right now we say -1 for the next block if if it's not being used we'll say minus 2 if it's the end so - one is empty - yeah so we have an empty box and empty inode and to claim it we're just going to say inodes da well we need to get our block first again it really should be error checking okay so that I'll keep the file let's test this out so we've created our file system it's mounted that allocate a file I don't really care about the I don't really care I'm not going to use a file descriptor yet now if I do this oops okay probably typo so let's see where our typos our eighty-five oh okay let's just move these to the top when the C compiler got in there it didn't know about those internal functions yeah and yep okay now if we test it okay it shows up oh it didn't fix we didn't fix I mean so let's fix that also it's okay okay so we've allocated this it points to this block and then this block is marked as being used now if I go and just mount it though it's not going to show up and what I didn't do was I didn't sink it so let's allocate it and then sink it right so it shows up and now it's still there right you know if I look at my data I can see it here and then yeah I can't I don't recognize the minus 1 versus minus 2 but okay so what's next okay so let's write some data to a disk block or to it to a file so let's for our file we're going to need to keep track of kind of where we where we are in it so let's look at our interface so we've allocated a file it's probably not too interesting to read to from the file yeah let's let's set the size of the file and then what we're going to do is we're going to copy data to the file so we use position and some data and we'll pass the data in just as a car star actually just do right by so sympathies oops I mean okay yeah lost track of which file is in for a second okay so we want to do these two setting the file size we're going to adjust which block number kind of the box that we have and then writing a bite we're going to go ahead and figure put put it actually in there so it added into the box as necessary let's go back and make a constant so I'm not using magic numbers everywhere okay so we need to know how many box so what we need to do here is just say sighs / dis walk block size and then I'm going to add one because I always have to I need to round up essentially actually if I want to be a little more particular I could say so play yeah if size actually let's do it this way I think there's to be more elegant so we round up like this okay so this will tell us how many box we should have and now we're going to walk through in and count them so we got our first block and so let's dunk decrement our num and then I always say while num is greater than 0 we need to make adjustments so what do we need to do so on each one we need to check the next block number so and next num is equal to you check make sure that's right name next block number okay if so there's two two cases right either there is an X block or it's minus two so if it's minus 2 we're going to need to add more blocks so if next num is equal to minus 2 then we need to find empty block and then we're going to set this current block equal to the empty one and we're going to set the empty one to minus 2 okay and then we're going to save lock number is equal to the next block number and we're going to decorate decrement how many we need to do so this should be this should grow okay that should grow grow it now we need to check if we need to shrink it so when I say while the block number we really need to probably recursive a recursive would be easiest so let's create something called shorten file and pass it in the current block number and the way shorter file is going to work is we're going to look at the next block number that's pointing to something and then say if it's greater than or equal to zero then we're going to shorten the file again and then here we'll set this to minus one to say it's not allocated and down here back in our set file size we're going to set this one to be minus two to say it's the end so that should walk through and if we had a long file it should make it shorter and so now the file should be the correct size let's see if it compiles and compiles we test that new function yet so we're still at the same setup let's test the new file test the new function so if I mount the file system and then that's a set file size for file zero and let's set it to be just 100 all right so I should only take one which I shouldn't have any effect so that's our first case no effect actually we let's do a couple right so we can set it to be to box and then let's set it to a bunch of ox right so like nine or ten and then let's set it back to one block so this is two blocks and you can see the chain here so it looks good this is looks like ten blocks right here you can see the chain and then back to two blocks or one block that get one block okay so set the clock setting the block looks about right and for the last operation in this video let's go ahead and write a bike so let's write some data okay so this is going to take the file numb the position and the data we want to write so the first thing we need to do is calculate which block and then calculate the offset in the block right the data okay well I actually we need to find the block number calculate the offset in the block and then write the data okay so which walk well which walk is going to be based on the position so they say relative walk is going to equal the position divided by block size and now we need to get that get that block and so let's process in the pan um and so we're going to make a new operation so it kept lockdown actually that's to this [Music] yeah yeah so get down definitely a box you need to go when I sit down to offset the star I want to see a while and it's initialized our block numbers you know when I say while to go is greater than zero and then we're going to return the block number so every what we're going to do here is just walk down through it so we're going to say this box block number is equal to this box the current block number and the next block number so that should then will return which block number now for the offset that's just doing the Lambada operation and so here what we're going to say is this box lock number data offset is equal to data so we're just going to test sign and that should be it let's see if that compiles seems like it okay so let's go with the big one and [Music] let's do a little loop and this printout let's put a character in like every hundred bytes okay so we'll do this 49 times and I called this function right bite we're doing it on file zero we the address we want to use is I times 100 and then we're just going to pass in the character a and yeah let's try that okay so oops so that should terminate I probably messed up my get blocked number right I should subtract so let's try that again and let's look at the file system and I can see I have the data spread out okay so it looks like I'm able to write to the data right to the file system let's go ahead and let's try again let's try again and see okay this isn't thorough testing but okay so we can see there's the first file and then our second file right and then there's the disk blocks and so on so where are we at you know what what so we can write to the file we didn't practice reading I think that you should be able see how that would come about you know where we're mounting the file system and so if I want to read data out then that's a pretty straightforward operation we have our super Bock we have the I nodes we kept we didn't do a bitmap for either of these we just are iterating through them which is slower but again trying to keep everything simple and the blocks were chained kind of like the file allocation tables and you know the operations we need to be able to initialize the file system and be able to write out to disk and then after we were writing to disk right then we want to be able to read it in practice like the real file systems you know instead of a file on there they're using a disk device and then we can claim files we didn't do delete files but you know that you think about that setting the file size writing data right so some other operations you can think about will be delete and read byte will probably be the next ones to implement but that's it for for this video thank you and have a good day