‫Hello and welcome.
‫We are now going to implement our hape, the first thing I want you to do is just create a new folder
‫in your memory directory and just call it heap.
‫I'm going to keep following here because I just get that's up to you now in our memory directory and
‫our source create a new folder called Hape in here.
‫We're going to create a new fangled heap, Deitsch.
‫And we're then going to create a file called Heap Dot, see, OK, we're now just going to go includes
‫he hates.
‫And I would go back to the Hajj and we're just going to include some things, we're going to include
‫config Deitsch, we are going to include Estie in it Hajj.
‫We are going to include Estie Death d.H.
‫Now we're going to create those definitions I was talking about earlier that determine if an entry is
‫free or taken.
‫So we're going to go define heap lock table entry taken 001, define heap block table entry free.
‫So this is the way that the type you know, I was saying in the presentation, the last four bits,
‫I mean, the first four bits, they are they represent the type and these are the definitions.
‫The represent is taken.
‫Ofri free.
‫OK.
‫Now we're going to implement the bit mask for the two top bits, which determine if we have any more
‫blocks next to us or if this was the first block.
‫So we're just going to go define.
‫Heap block has next zero b one, two, three, four, five, six, seven, eight, six is good to count
‫them.
‫Right, because then it's easy.
‫It is easy to write binary if you count what you're doing so that we are the top most Petare has next
‫year to fine heap.
‫Block is free zero BS.
‫One, two, three, four, five, six, seven, eight.
‫There you go.
‫That is all fine if we just line that up so neatly.
‫Not nice and neat so we can see the top most badass has next.
‫The next bit down is is free.
‫So we'll use this in our BEP mask as shown in the presentation where I went to the table with you.
‫OK, so we're going to make a type this, so we're going to go typedef unsign char.
‫He Glocke table entry, and this will basically be those apitz in the entry table, so one of these
‫entries represents the Apitz and we just typedef it because it's cleaner than using a unsign char,
‫for example.
‫It's more straightforward what's going on if we give it a name, which is why we create this new type
‫here.
‫OK, so we're now going to create our pantry tables.
‫So we're going to construct a table and we're going to go heap block table entry entries.
‫So this is a pointer, OK, we're creating a pointer here to a place where where our entries are going
‫to be.
‫You know, I showed you some free memory in the presentation.
‫Well, that's not the only free memory in another initialize system.
‫There's other places, too, which while which I'll show you later and we will be pointing our entry
‫table there.
‫Whilst we could make some giant array inside of our kernel binary, I'd rather not do that because we're
‫unnecessarily making the kernel larger than it needs to be.
‫OK, so in our heap table, we also need to know how many entries we have, right?
‫That's also pretty important.
‫So we have so you know, I was saying that 25000, 600, I think that was the number we came up with
‫for 100 megabytes, something like that that would be stored in this total variable here.
‫OK, and then the entries point to a point to that table of these block heap table entries.
‫OK, so we're now going to create a structure for Ahepe.
‫And simply put, this will contain a pointer to our table and it will also contain our START address.
‫So remember, I was saying in the presentation we pointed to like zero one zero zero zero, something
‫like that.
‫Right.
‫We would store that state address in this address here and then would be able to reference it throughout
‫throughout AHEPE implementation as we go along and use it.
‫OK, so we have our structures all nice and set up.
‫We can now begin implementing the heap.
‫So if we go to Hiebert C and we will start here.
‫So inside heap dot C, we're going to create a function for creating the heap.
‫So we're going to go help create and it's going to return an integer if we return zero.
‫Everything went OK for returns below zero.
‫Something went wrong.
‫And whatever that negative value is represents the error code.
‫This is how Linux kernel do it.
‫This is how it should be done.
‫So we're going to accept a heap provided to us.
‫We're going to accept a pointer to the data, Paul.
‫And we're going to accept appointer to the end of our heap, finally, we're going to accept the help
‫table.
‫So the idea is the person who wants to create Ahepe will call create, they will pass in an initialised
‫heap structure appointer and we will initialize it.
‫They'll pass in where they want the heap to start, where they want the heap to end.
‫They will also be responsible for providing a valid heap table, one that they filled in.
‫So they would be expected to set up a heap table that points to the entries and has the total, we will
‫then use the end variable here to determine if the table is valid or not, i.e., did they make a mistake
‫setting up the table or not?
‫And that's how it will work.
‫We could break this down further and make it even easier for the caller.
‫But for now, you know, let's keep it simple.
‫This is your first time creating a heap.
‫Let's keep it as simple as we can.
‫OK, so we're just going to return zero here for now, which will mean no error.
‫We're going to copy the prototype and put it in a heap.
‫Deitsch And we're now just going to change the makefile to check that this little skeleton we've built
‫compiles absolutely fine just before we continue.
‫So just by here in the Makefile, we're going to go build a memory heap, heap of dots, source memory.
‫He he could see.
‫OK, we're going to copy and paste one of our Chaske commands here and make sure you change everything
‫here so that one will include from the Heap directory and we are compiling he puts out see.
‫And we're outputting it to this object, so you can just copy and paste what right there and we'll just
‫paste that in here.
‫So that's going to be our output binary, OK?
‫We now load up this oh, one more thing.
‫Scroll to the top.
‫We need to add it to the files, guys.
‫So just by here, we're going to go forward, slash builds memory, keep, he thought, oh, OK.
‫And now if we just go build that S.H..
‫I can see that works OK, and we can see that a Hebrew file has been compiled.
‫We do not make claim.
‫And there we go, keep that file is deleted.
‫OK, so that's good news, then we can work with that.
‫Excellent.
‫OK, so let's create a col heap.
‫Now, I know we haven't finished this implementation yet, but I want to take you through step by step
‫here.
‫Right.
‫We're not going to write the whole heap and then call it later.
‫That doesn't make sense because you need to learn what's going on.
‫So we're going to create a new file called Cohiba could see.
‫And we're just going to include Cohiba Hajj.
‫And obviously we're going to create a new file called Keep the Hajj if and death.
‫Keep Hajj, define Cohee page and if.
‫OK, good to keep Tazi.
‫And we are just going to say Voyt keeping it simple as that.
‫OK, now up here, we're going to declare our structures.
‫So first comes our Col heap.
‫OK, and we're going to include keep outrage as well, guys, so that we can access those structures,
‫OK?
‫Next comes our hope table.
‫OK, excellent.
‫So we don't need to initialize Colonel Heap.
‫We do need to initialize the Colonel Heap table.
‫OK, so first things first.
‫Let's get up a calculator and we're going to go 1000 decimal said decimal 1024, times 1024.
‫OK, that gives us one megabyte.
‫Now we're going to multiply that by a hundred.
‫That is how many bytes is one hundred megabyte.
‫We're going to create a hundred megabyte.
‫We're not going to worry about determining how much ram they have and making the heap based on that.
‫You know, I'm I'm giving you a taste of the heap.
‫If we decide to do that, we can get to that in another tutorial.
‫So what we now need to do is we need to divide it by our block size, which is four thousand eighty
‫six.
‫Right.
‫That gives us twenty five thousand six hundred col heap table entries.
‫OK, good.
‫So let's just go to figure out how much we're going to create some definitions.
‫Define Peach Oz, keep size bytes.
‫OK, so if you remember it was this number here.
‫Yeah.
‫So that's 100 megabyte.
‫So obviously, in a better invitation would determine the RAM, how much ram they have and it wouldn't
‫be static like this, anyone who runs our system needs to have at least one hundred megabytes installed.
‫It doesn't matter if they have four gig installed, we will only access 100 megabytes here, OK?
‫That's twice as much memory as our system can handle for now.
‫For now, we can change that at a later time.
‫OK, so this is obviously the equation.
‫We used to calculate that.
‫OK, but anyway, let's now define PCOS, keep block size so we'll have a block size of four nine six.
‫OK, we now go back to keep the Hajj.
‫We're now ready to set up some values.
‫So we're going to cranage here.
‫Total table entries.
‫Now this is the math that I literally just did in the calculator to show you.
‫Right.
‫So we're going to divide our total heap size by our block size, and that will give us the total table
‫entries.
‫So we got to configure how much we can see pictures, heap size bytes.
‫So we're going to use that divided by.
‫And let's just include confect here, guys as well.
‫Don't forget that.
‫So divide that by Piech OS.
‫Heap, block size, so that will give us the 20 that will give us the twenty twenty five thousand six
‫hundred that we calculate here, right.
‫OK, so as I said, we're in charge of initializing the heap table.
‫So all we do then we go Colonel Heap table dot entries and we're just going to set that to zero zero
‫for a moment because we're going to set this later and now we're going to keep her keep table dot total
‫equals.
‫Total table entries.
‫OK, so once we've set this to an appropriate address, which we will find soon, then it will be initialized
‫correctly.
‫OK, so let's now find some values that we can put in for our entry table and where we can point out
‫here, we just go to Google OS Stav memory map.
‫So, you know, this will give us a nice memory map of the system so we can see how it's laid out here.
‫Right.
‫OK, so we can see that we have usable memory here.
‫So we can we can map it.
‫We can map our table here if we wanted to.
‫OK.
‫That will work OK for us if we keep scrolling down to the extended memory.
‫We can see we have 14 megabyte free here, but we've mapped our colonel at this address so we can use
‫that and we can see at this address this is where our heap is going to go.
‫So if we are here data, Paul, so if we just copy this address here, we're going to go to configure
‫H define Piech OS heap address and we're just going to paste that in.
‫So that'll be our address.
‫We still need to find some memory where we can map our table, we could just extend this hip address,
‫given a small room, but we don't have to do that because there's another place where we can use this.
‫Oh, yes, here it is from seven 00 to seven F F F that gives us 480 kilobytes.
‫We can also pick a lower address if we wanted to because we no longer need our bootloader and stuff
‫like that at this point in time.
‫However, the 408 kilobytes is more than enough because we only need twenty five thousand six hundred
‫bytes, so we will point it at zero seven zero zero.
‫So let's just do that now.
‫Defines us heap table address.
‫This is the address for our table guys.
‫Right.
‫And we'll point it there because we can see in the memory map that we have four hundred eighty kilobytes
‫of memory here.
‫We can see the end address here.
‫So if we now go to keep that C, we're going to change this.
‫And rather than have void, we're going to have a block table entry.
‫I he block table entry and we're going to cast it to that.
‫OK, and the address, we're going to Cask Heap.
‫Table address, OK?
‫I should work absolutely fine.
‫OK, so now we need to calculate our end variable, so we're going to go end equals void and void.
‫Pintor end equals void points.
‫We're going to cast it.
‫Pitchers heap address plus pitcher s.
‫Keep size bites, so that points to the end of our table, right?
‫So I will go in response equals.
‫He creates and we're going to pass an appointed to our Colonel Heap variable in the global scope here.
‫We're going to pass in our pointer to the heap data, Paul, and that voice will have to cast it.
‫And that is simply US address.
‫OK, now the end.
‫We're going to pass an enviable and the table will be the kernel heap table.
‫OK, so if Rez is below zero, then there was an error.
‫OK.
‫So we can just go print fails to create heap.
‫Now, this should really be panic, but we'll make a panic later.
‫Panic is basically just a function the prince and error message and then has a while loop that never
‫ends.
‫So it only shows that messaging doesn't continue any further.
‫Will implement that later is very easy.
‫OK, so what we're now going to do is we're going to add the K heap into our make files to go to the
‫Makefile.
‫Scroll down.
‫We're going to copy and paste our previous declaration here and we're just going to change heap to keep
‫keep.
‫This stays the same.
‫CSOSA include directory keep keep OK.
‫And we're nearly ready.
‫We're just going to copy and paste this case by here now and we're going to pasted in our files which
‫are there, which are the requirements control.
‫Say that now.
‫Now we're just going to open the terminal, we're going to make clean and we're going to build.
‫And we can see in the declaration of Prince, if you go to keep that tazi, we just need to include
‫Colonel H in here, OK, which will give us access to that print prototype.
‫We now compile that again.
‫There you go.
‫It compiles.
‫So that's all fine.
‫We we now have a finished skeleton.
‫Obviously we don't have a heap yet, but we have a skeleton to work with.
‫So we're now going to implement the heap, create function and then we're going to create our functions
‫for allocating and freeing memory.
‫OK, so what we're going to do here, we're going to create a static function here.
‫Static and it heap.
‫Validates alignment, and that's just going to have to point to here.
‫And all we're going to do is return
‫pointer aligned with Heap.
‫Block size equals equals zero.
‫OK.
‫So that's going to return true, if there's an alignment here, however, we need to convert it back
‫to a intriago type, so we're just going to go and in it here.
‫OK.
‫As simple as that, and here we're going to include Colonel Deitsch as well, so this will validate
‫the alignment and return true if the alliance, fine or otherwise, falls.
‫But we can change that to a sir, if you if you want just include a city ball and we can change that
‫to a building.
‫It doesn't really matter.
‫That would be fine either way.
‫So here then what we say is and it rests equals zero and we're going to return.
‫OK, and now inside the root of our source directory, we're going to create a new file called Status
‫Stockage.
‫OK, and this is just going to define a bunch of status codes.
‫OK, so we're just going to find two for now, Pacho.
‫All OK.
‫And that'll be zero and process I error and that will be one.
‫OK.
‫So if we now go back to keep the C, we're going to include.
‫Status Deitsch.
‫And now we're now able to do things like rascal's minus CIO, right, which means that there's an error
‫essentially, and it says it isn't defined.
‫Skarbek.
‫OK, I did picosecond change that.
‫EIO Because Linux does it like this and it is quite clean.
‫So picturesquely all OK.
‫And I'll send you can you can do things like wrests equals minus Scio then.
‫Right, to just show that there's an error or something.
‫So what we're going to say is if he validate alignment's pointer and so if that was false or he validated
‫alignment and, and that was false because remember it needs to be aligned because our entire heap is
‫using block sizes here.
‫Right.
‫If it's not aligned, then we can't actually work with the address they're giving us.
‫So it has to be aligned because we're relying on a certain block size.
‫So when we go heat the alignment, this ensures that the pointers they've provided do align to a four
‫thousand eighty six boundary.
‫So we're going to go equals minus E in the ARG invalid argument.
‫OK, we're going to create that one now and here we're going to go to out and we're going to create
‫an out label by here.
‫OK, I know.
‫Go to consider evil in C it isn't because in C we don't have things like try and catch and stuff like
‫that.
‫And there's many reasons why you would use a go to file, such as cleaning up memory and stuff like
‫that.
‫It is you can abuse go to C, but for handling errors and stuff like that, this is perfectly fine.
‫And Linux do it as well, by the way, like Linux kernel.
‫So we're going to go to Fyne Invalid ARG.
‫Yeah.
‫In Varg and that'll be Erico too.
‫So obviously when we attach a negative here, it makes it a negative value.
‫Right.
‫That's why we do minus by here.
‫OK, so we validated the alignment of the heap.
‫So that's all good.
‫So if the heap alignments bad, we're going to return minus Æon Varg and because that's a negative value
‫below zero, it means there was a problem.
‫OK, so what we now need to do is we need to include memory, memory that Hajjaj OK, and we're going
‫to go mem said heap zero size of struct heap.
‫And obviously this just initializes the whole heap to zero which is what we want.
‫When are we going to go heap s address equals Peter.
‫OK, so that just sets our heap start address to the point that they provide to us.
‫When are we going to go heap.
‫Table equals table.
‫OK, and again that sets the heap table in our, in our heap object.
‫We are now going to have to validate our heap table static init heap validate table and we're going
‫to accept a pointer to our data pool appointed to the end of the heap data pool and appointed to the
‫heap table.
‫And we're just going to validate that the pointer they provided and the end address is correct for the
‫table they provided.
‫In other words, does this table know how many blocks we need between pointer and end?
‫And here we check if the person using our heap implementation has miscalculated that or not, which
‫is pretty important because we can't have a one hundred megabyte data heap with only ten megabytes of
‫blocks and the heap table is going to cause problems.
‫We're going to overflow and we're going to write into some data we shouldn't write.
‫Things can happen.
‫It's important that both both us and the person using our heap implementation agree on what the table
‫should be.
‫OK, so this is pretty easy then.
‫And it Rasco zero return address and we're going to have our out label here.
‫We're going to say size T, table size equals size T and minus pointer.
‫So this gives us the table size because we minus the end by the pointer.
‫Right.
‫Nice and simple.
‫Now we say size T total pages equals table size divided by PEOC block size.
‫So give us the total blocks and you know what we should call that total blocks really that will give
‫us the total blocks in our heap.
‫And we say if table total does not equal total blocks, then they've miscalculated that.
‫And that means that we return invalid argument because they.
‫Provided the wrong argument to us, the table needs to be recalculated before pasture's again because
‫the programmer has made a mistake.
‫Maybe they passed 10000 blocks for a one hundred megabyte heap.
‫Remember the table total, right.
‫That needs to be calculated correctly.
‫And that's the only reason why we require an end address provided to us is so that we can validate the
‫table they provided to us in a better implementation.
‫We could make a function that creates the table for them and then they won't have to worry about this
‫sort of stuff.
‫But for now, will will allow that will require them to make the table, as we've done in the case,
‫the Cohiba by here.
‫OK, so now we say wrasse equals heap validate table.
‫Pizza and table and are we safe, rest below zero, go to out, and that's as simple as that.
‫So that validates our table.
‫Make sure it's correct.
‫Right.
‫So the final step now is to initialize all of the blocks in the table in the in the hip table heap entry
‫table to zero, because, of course, when we first create a heap, all of those blocks are going to
‫be free.
‫Right.
‫So the first thing we do is we calculate the table size.
‫We could make a function for this if we wanted to.
‫But for now, we'll just do this size of heap block table entry.
‫Now we know this one by will you size off in case one day we make it a structure or something.
‫Right.
‫Think ahead.
‫Multiply by table total.
‫OK, that gives us our table size.
‫So now we can just go set table entries.
‫Heap, block, table free.
‫Table size, and we don't have to take those bits, those top two bits into account, because obviously
‫if we just go and set this byte to zero, then those bets will be zero anyway.
‫So we don't need to take those into account.
‫We don't need to just set the lower four bets here.
‫We just set the whole thing is just easier because then the flags are zero, too, right?
‫So this is absolutely acceptable and that is it for our create that will go through.
‫It will validate that was passed to us is correct.
‫And validate the table.
‫Make sure that's correct.
‫And finally, it will mark every other initialised byte in the entry table to zero, essentially saying
‫that the entire 100 megabyte heap has free memory.
‫We're now going to create our heap malac function.
‫So at the bottom of the heap, dot cifas, we're going to go void.
‫So we're turning a void heap mallock size to size.
‫OK, so obviously as you know how mallock works, people say they want 50 bytes.
‫We return block.
‫That can accommodate for that.
‫This is what we're doing here.
‫So we're just going to return zero here for now and we're going to go void heap free.
‫And that, of course, will accept a pointer to free and we'll just return zero for now.
‫OK, so you sort of understand the basic prototypes of what's going on.
‫We can copy and paste this into heap page.
‫OK, so that we have these.
‫OK.
‫Yep, that looks absolutely fine.
‫So now we have some functions for Malcolm free, obviously they don't work right now.
‫We're going to make them work.
‫So if you remember in the presentation, I said that when we malac, we need to find out how many blocks
‫to allocate based on the size provided where we're going to have to do that now.
‫So the first thing we do is we're going to go Statik Unit 32 to heap a line value to upper and we'll
‫just call it that.
‫That's absolutely fine.
‫And we're going to accept a value in here.
‫So if they give us 50, we give them four, nine six.
‫They give us four nine seven.
‫We give them four nine six multiplied by two.
‫Just see what I mean.
‫We we constantly give them the upmost alignment.
‫So we want a line down will always a line up.
‫OK, so first we check for alignment.
‫So if Val.
‫Heap.
‫Block size.
‫Equals zero, then we are already aligned, so we just return value.
‫Now, obviously, if it's not aligned, then what you need to do is vow equals.
‫Wow, minus.
‫Wow, PCOS, heap, block size.
‫OK, so we're not done.
‫I'm going to open up Python so I can show you how this works.
‫So let's say they give us 5000.
‫Yeah, so we do four nine six five thousand modulus four nine six equals nine for not zero.
‫So we are required to align this.
‫So what we then do on the next line, line 62, we go 5000.
‫Minus five thousand four nine six now that gives us four nine six, so it aligns it to the lower address.
‫OK, does that make sense now?
‫Because it allows it to the lower address.
‫We now need to add one more block because obviously four nine six is lower than the five thousand bytes
‫they wanted.
‫So the next thing so easy, you just go four nine six plus four nine six.
‫And that gives us a value of eight one nine to.
‫So if we want to allocate 5000 bites, this function says we need to allocate eight thousand one hundred
‫ninety two bites, so we do we go vald plus equals petrofsky block size, very simple.
‫And now we just return.
‫Wow.
‫Nice and easy.
‫So we're going to need to rely on this function.
‫And once once we have the value in this function, we can get the total number of blocks.
‫OK, so we just go sist aligned size.
‫OK, equals heap align value to upper, and we're going to pass in the civs may need to cast this,
‫but maybe not so are vowed to pass the airline size.
‫OK, so that gives us the new size.
‫Now, what we need here, then we go unit three to three total blocks equals a line size.
‫And what you think the equation is, it's very easy divide by as he blocks size.
‫OK, so we take our value here, the one the one our line size eight one nine to divide that by our
‫block size and look at that, we get to two blocks.
‫So these two lines here calculate how many blocks we need to allocate in our entry table to represent
‫the size that the caller is asking for.
‫OK, before we continue any further, let's just compile this to make sure there's no compile time errors
‫because we'll have to fix them if there is OK, there we go.
‫And use variable total blocks.
‫OK, that's completely fine because we're going to use that.
‫So there's nothing serious going on.
‫That's good.
‫OK, so when are we going to create a new mallock function?
‫But this will be a special one as it will take the number of blocks to allocate rather than the size,
‫because we've already made the size one here.
‫So we just go void heap mallock blocks struct heap heap.
‫And it's going to take the total blocks to allocate.
‫Now, we also need to accept the help here, guys, which is what I forgot to do.
‫So we go straight to hip hip and we're going to go struct heap, heap.
‫So just by accepting these two here, then we can pass those down the chain, you know, until the job's
‫done.
‫So what we're going to go here then instead of return zero, we're going to go return he malot blocks
‫and this should be pretty straightforward.
‫Now we just go heap total blocks, right?
‫Because we've calculate the total blocks.
‫So people call Mallak.
‫They don't come out of blocks, they call Mallak.
‫We calculate them out blocks we need and then we call he mahlab blocks for them.
‫OK, so when he malac blocks, we are responsible here to find the blocks that they need and return
‫appointer in the data pool.
‫So let's begin.
‫We're going to avoid address equals zero.
‫So we're going to a return address.
‫OK, so this is the address will be returning to the map we allocate.
‫So first we just stop block.
‫So we go in and start block equals hepcat stop block and we haven't implemented this function yet.
‫OK, and we're going to pass the heap in the total blocks.
‫So what our heap's get block function will do is it will look through the heat, the hip entry table
‫and see if it can find enough room for these toddled blocks in in in a series of each other.
‫If we can find it, it returns the first block it found on that series.
‫And Everton's the block number, essentially the index in the entry table, essentially.
‫Right.
‫And then we can use that stop blocked, calculate an absolute address and return it to them.
‫So what we're going to say is F-stop block is below zero.
‫Then there was an error.
‫Maybe we're out of memory, for example.
‫So then we just go to our OK, so we do that and we just go to out.
‫And that will return now, which means we couldn't allocate.
‫OK, so now we need to convert our block to an address.
‫So we just go address equals heap block to address.
‫And we're just going to pass in the Jeep and the stop block and then I'll just calculate a absolute
‫address in the Jeep for the stop block we provide.
‫And then obviously we need to mark the blocks as taken so that the next mallock doesn't return the same
‫address, allowing another program to overwrite our data.
‫You know, that's the last thing we want.
‫So here we just go, heap mark blocks taken heap stop block total blocks and that'll go through the
‫entry table and it will mark all of those blocks is taken and a marksman is taken simply by changing
‫its type from zero to take.
‫And it's not too difficult.
‫So that is Ahepe Malik Bloks, we now need to create the hepcat stop block function he blocked to address
‫and he mark blocks taken and then we have a heap that can allocate blocks.
‫OK, so we're going to start by implementing the heap get stop block.
‫And just bear in mind this implementation will be very basic.
‫It won't be optimized for speed.
‫Let's just get get something working and we can go from there.
‫So we go in a heap, gets our block OK, struct heap heap in it to the blocks.
‫OK, I guess you could use unit three to T here if you wanted to as well.
‫So we'll probably do that.
‫OK, so what we do now is we say struct heap table table equals heap table.
‫So I'll give us access to the entry table.
‫We can now reference that to the table variable here.
‫Right.
‫So we are nebbishy equals zero and it both equals minus one.
‫So simply put, piece will store the block, start the first block that that we find this free.
‫Essentially we will store that and B C will store the current block that we are on.
‫So we can use these two variables here to help us calculate a stop block that has enough blocks in series
‫to cover the total blocks.
‫OK, so we now do is we go for size T I equals zero I below table total I plus plus.
‫So this will go through our entire entry block table and it will look for three blocks in a better implementation.
‫You would point, I add some sort of start variable which will allow us to be more likely to find a
‫free block at the first index that is pointing to the eye is equal to I mean however, like I said,
‫to keep the same limitation simple.
‫We're not going to worry about that yet.
‫So we now need to make something that we now need to test the entry type.
‫OK, but to do that, we first need to make something that extracts the the entry type because remember,
‫the entry type is the lowest for bits.
‫Right.
‫So this is pretty simple.
‫We just go static in it.
‫He get entry type and we we accept a block table entry, OK, and we just return entry.
‫And Zuckoff really is as simple as that because that'll take that by and zero zero F is will give us
‫the first four bits.
‫Right.
‫So we go in here and we just type F switch the binary.
‫After you pressed enter, of course, you see one one, one one, so that's what we care about.
‫We want to return the last four beds and we don't care about the upper bed.
‫So this is why we do this right.
‫This bitwise logic here, entry ampersands zuckoff that extract the entry type for us.
‫Now we can do something like if we get entry type.
‫Table entries I.
‫Does not equal heat block table entry free, then with zero equals minus one continue.
‫OK, so.
‫I've spelt entries wrong there, by the way.
‫OK, so while this is basically saying is if the entry were on is not free, then we need to reset the
‫state because there's no way we can use our state entry that we already have.
‫Assuming there is a store injury, let's say finds one block Bambis might be equal to five or something.
‫Right.
‫Block index five, but maybe doesn't have enough blocks and series for us to cover the total blocks.
‫Yeah.
‫So OK, so in our block, sex, for example, is a free.
‫No it isn't.
‫Well we haven't reached the total block so that we can use the stop block.
‫So we reset beasts to minus one and we reset the current block to zero here.
‫OK, so that's what we do that.
‫And now what we do is.
‫Oh yeah.
‫And we continue as well, which is go back to the start of the loop and start again.
‫Right.
‫So here we go.
‫Boys equals minus one.
‫AFPs equals minus one.
‫So what we're basically saying here is if this is the first block now at this point in time, we know
‫that this is free because we we accommodate for it here.
‫Right.
‫And if it isn't free, we continue.
‫So online eighty-seven, we know that this block of this current block is free.
‫So all we do is we say AFPs equals minus one equals eight.
‫OK, so now we know our stop block and now we just go B, B, C plus plus plus block current.
‫And the final thing to do is FBC equals the total blocks.
‫Then guess what, we found a start block that has enough blocks in series for us to use.
‫It has enough blocks in series.
‫Take a look at that table in the presentation if you're confused guys, because that's why I made I
‫made the table so you can see exactly how it's lined up.
‫Look at the table if you're confused, right?
‫So we find enough blocks here.
‫So then we break, OK?
‫And Alby's is equal to the first block we found because we accounted for that here when we checked,
‫which is equal to minus one.
‫OK, OK, so now down here we say if B.S. is equal to minus one return minus NMM, which means no memory.
‫We'll have to, we'll have to create that in a minute.
‫Otherwise we would be OK.
‫So we now go to status start we're going to create NMM.
‫So we just go define Inzamam and we'll do three.
‫OK, excellent.
‫So he returns minus it means we're at a memory.
‫OK, so that's pretty useful.
‫So what we do here is we say stop block equals he gets block, OK?
‫And if Ahepe is out of memory, we'll know this because the blocks start will be minus one.
‫So we couldn't allocate.
‫So we just return no Inamine and then our mallock blocks will return an address of no and then he mallock
‫will return address of now because because it does return he mallock blocks.
‫Right.
‫So then the caller realizes he cannot allocate the memory.
‫OK, so that makes sense.
‫So this is, this is our finished function for calculating a start block, which is the most important
‫function in this implementation, really, to be honest.
‫OK, so now we've implemented the hepcat stop block function.
‫We now need to implement heap, block to address and heap mark blocks taken and then we are done with
‫our marlock.
‫So let's just do that now then.
‫So we're going to first implement he block to address.
‫So we just go void heap block to address struct.
‫He.
‫And it Bloch, OK, and I guess that can be a unit 30 to 40 if you wanted, but we'll just have it isn't
‫in it because you're not going to have more than two billion blocks, right?
‫No way.
‫So he blocked to address this.
‫Fine.
‫So we're going to return he?
‫S address plus block multiplied by Peatross keep block size.
‫So.
‫How this works then, well, we know whether he starts here, OK, we know how to calculate the offset
‫because we know that each block handles four thousand eighty six bytes.
‫So the equation is very simple.
‫Block multiplied by four nine six.
‫OK, so that is our offset.
‫So then we add offset to the start to address the heap and that gives us an absolute address.
‫I hope that makes sense, guys.
‫If it doesn't, we watched the presentation because I do break it down in the presentation, how it
‫works and I show you visual examples.
‫So if you haven't seen that or you skipped ahead, check that again, because that explains this.
‫We now need to create mark blocks taken so we go void, he mark blocks taken.
‫That's going to accept a heap.
‫It's going to accept a stop block.
‫And the total blocks now, this is pretty easy to do, we just go in it and block equals stop block
‫plus total blocks.
‫Minus one, so that should work absolutely fine, so that's our end block, right, because first stop
‫block is zero and our total blocks is for.
‫Then zero plus four equals four and then we minus one to take into account that our block number start
‫from zero and that gives us zero one, two, three, four, four blocks.
‫So by minus one, we get the end block index, which is what we're looking for.
‫Right.
‫OK, so we could we could assert here that the block is in bounds or something like that to make sure
‫there wasn't a bug.
‫Right.
‫But because we haven't written the assertion functions yet, we're not going to worry about that at
‫the moment.
‫OK, so what we're going to do then we're going to go hit block table entry because remember, we're
‫marking the blocks has taken now.
‫So we go entry equals hip block, table entry taken.
‫But that's not good enough because we also need to set the flags that this is the first block that we
‫are setting in our allocation because it is this is the very first one.
‫And we also need to set the next flag if there's any more blocks after this.
‫In other words, if the total blocks is more than one.
‫So we're going to we're going to start by ordering the hit block first, which I don't think we've made
‫a bit messy for that yet.
‫Have we got a heap to Hajj?
‫Wow.
‫And you can see I actually made a little mistake here further back in the in the lecture.
‫I'm not sure if you noticed, but we'll just correct that now.
‫This block is free is wrong.
‫It should be reblock block is first.
‫So that was my mistake.
‫But you can see that the type C taken in free are the actual types in the table.
‫However, this should not be he block is free.
‫It should be he block is first.
‫So we go back to that C he block is first.
‫There we go.
‫That's, that's, that's perfect.
‫So now we say if the total blocks is above one.
‫Then entry or equals heap lock has next.
‫So obviously we have more blocks after this one as part of the allocation, assuming that the total
‫blocks is above one.
‫Right.
‫So because of that, our first entry needs to have the house block.
‫He blockade's.
‫Next, Flagg's set so that our limitation is aware that our allocation is more than just one block.
‫OK, so we're now going to make a follow up.
‫Four inch I equals stop block I below equal M Block II plus plus keep table entries.
‫I equals entry.
‫If I does not equal M block minus one.
‫Entry or equal, he blockade's next, and just by here, we need to also go entry equals hip block entry
‫taken.
‫OK, OK, so what's happening then?
‫So we come in here.
‫Let's pretend that the stopwork provided zero the total blocks was to OK that I make the N block one
‫because zero plus two minus one is one.
‫OK, now a total blocks is above one.
‫So we set the hip block has next bit in the entry.
‫OK.
‫Now we go inch I EcoStar block iberico and block I plus plus.
‫So stop like a zero is equal to zero.
‫So what we're saying is if I is below equal one then this loop is present.
‫OK, good.
‫So we set that entry to the enter we just made up here.
‫OK, so we know that it has an X block, we know that the entry is taken and we know it's the first
‫block in our allocation.
‫OK, so we set that here.
‫Now we set the entry to heap block table entry taken because we're about to make the next entry as the
‫loop goes back around.
‫Right.
‫And we basically say here, minus one from the M block.
‫Which will give us zero and then we say, if I does not equal a zero.
‫Then the next entry, when we when we look back around in this loop, has a next block to come so that
‫that's what that does, right.
‫So in our case, because we only have two blocks, this is never called, which means that the entry
‫we've set here, which will be set here when we look back around, does not have the next best mask
‫set.
‫OK, which means there is no more blocks in this allocation.
‫We are done.
‫OK, so I hope that made sense to you.
‫We've now implemented Marlock by the looks of it.
‫We will need to test it to make sure.
‫OK, so before we go any further, then we just need to change the prototypes for heat mallock and keep
‫free.
‫Because remember, we a structure, we never change the prototypes.
‫So we got to keep domeij.
‫We're just going to simply go struct.
‫He.
‫Struct, heap, heap.
‫As simple as that, and now the prototypes match up, so we now go to the terminal and we're going to
‫build this firstly make clean.
‫Now we're going to build that S.H. And that's OK.
‫We can see return zero on one six two.
‫That's because we haven't implemented our free yet.
‫And also free is of type void.
‫So you can remove that return zero by there.
‫We don't need that.
‫If you know that again, we can see that compulsivity.
‫So Ahepe Mallock has now been implemented.
‫Excellent.
‫OK, so I know you're eager to test this mallock function, so we're going to do that now before we
‫even continue any further.
‫We're not going to implement free until we've tested this.
‫So we got a keyboard.
‫See, we're just going to create a new function here.
‫We're going to call it void pointer because we're returning a log pointer K malac Col Mallak, basically.
‫Yeah.
‫And we're going to accept a size T here.
‫OK, and this is simply going to say Return Heap Mallak and we're going to pass in our col heap and
‫the size nice and simple.
‫Look how simple that is.
‫Right.
‫We're going to copy and paste came along and we're going to put in the prototype of the heap here.
‫OK, if we now go to Colonel Dot C, we're going to include memory.
‫Keep keep the Hajj.
‫OK, and we got to keep that.
‫We also need to include city in it and we'll also include acidy death as well.
‫OK, cool.
‫So if we got a colonel that C again, we can now use that hip.
‫We should be able to.
‫OK, so we need to do now.
‫Is music OK, keep in it.
‫OK, initialize the hip and we should probably put this above it.
‫OK.
‫Now.
‫Before we go any further, go to keep see.
‫And we're just going to copy and paste keep in it.
‫Into the head of.
‫And what we're going to do now is we're going to go void Peter ECOSOC Mallock 50 void Peter to ECOSOC
‫Marlock 5000.
‫And now if we try to compile this, the compiler Wanis that we haven't used the variable because because
‫we have that warning enabled.
‫So all ours to do is go if pointer or pointer to and is obviously not going to do anything, it's just
‫there so we can compile it.
‫And I now want us to compare this with a make clean and a builder.
‫S.H. will go crebbin gdb and where to go target remote kumu system and rather than x 86 64 like we've
‫usually done just to I 386.
‫And the reason for this is because X 86 64 is a 64 bit virtual machine.
‫However, we are going to attach 32 bit symbols and it can cause a few problems.
‫So is sometimes so it's best we just use the 32 bit virtual machine, which is AI three eight six.
‫OK, so now we're going to go dash Ajda top foregoes double dash Catullus dash gdb.
‫Studio press enter and now we're going to go add single file Beeld Kernel 4.0 and we're going to put
‫that at this address.
‫So what we're going to go zero one zero zero zero zero zero.
‫OK, so hundred 100000 hacks and now we're just going to simply go break Colonel Dot see 86.
‫And now if we now proceed to continue, we can see it breaks there.
‫If we go print pointer, look at that address.
‫That is the first address in our hip, so that's great, that's great news.
‫Now do point to two and there we are.
‫Look what we see there.
‫We see a pointer to the next block in our hip.
‫So this is the first block.
‫This is the next block.
‫Because when we came out like 50 bites, it gets rounded up to four thousand ninety six bytes, which
‫is why our second block here starts at the start.
‫Address Vahe plus four nine six.
‫So if you if you put this into your calculator.
‫And you just switched to decimal, so you'll see that's the decimal value there, yeah.
‫Of that hexadecimal value if you just do minus four, nine, six switchback text decimal and now we
‫see the start of the heap again.
‫So this is great.
‫It means, okay, mallock is working.
‫So here we allocate one block, here we allocate two blocks so our heap's returned.
‫Ahepe implementation is return addresses we can actually use.
‫OK, so now that you can see that you now know your heap works, which is great news, we now just need
‫to implement Kifri, which will free those blocks.
‫OK, so we're going to do here then is Goheen Mark blocks free.
‫And we're going to go he he addressed to Block.
‫And we're going to pass in our hip and our points of there, so simple as that, you might want to check
‫the balance here to make sure they pass to some valid point and then, you know, maybe a certain panic
‫the system, if it's not.
‫But for now, that be fine.
‫We know how to implement heap mark blocks free and help address to block.
‫So we'll do help address to block first, which is nice and easy.
‫So just by here, we're going to go in it.
‫He address to block.
‫Struck Teep.
‫Void's address.
‫And we're just going to go return.
‫And we're going to cast this to an integer address minus s address divided by.
‫Our picture was.
‫Block size.
‫So how this works.
‫We get our address, which we know is equal to the start address or above it.
‫OK, and then we minus the state address, which will give us a relative offset.
‫Right.
‫And then we simply divide that by the block size to get the actual block number.
‫OK, and once we know the block number, we can once we know the starting block number, we know which
‫blocks to free.
‫OK, nice and simple.
‫So we've implemented address to block.
‫We now need to implement.
‫He mark free.
‫So this is pretty simple, we're just going to go void's.
‫He Mark Bloks free.
‫Struct heap heap in its starting block.
‫We don't need to know an end in block because remember, we checked those flags, right?
‫We checked those flags and because of all the bit masking we're doing, that's why we can use one byte
‫per entry rather than relying on some sort of structure that's like five, six bytes or whatever, one
‫byte per entry, because we use a bit mask's, which is very efficient.
‫So here we're going to go struct to table table equals heap table.
‫So we're now going to create a volume.
‫So we're going to go for integer I equals starting block I.
‫Below and we're going to cast this table total, because I know we use society for the total, but here
‫we use an integer, right?
‫So there's like a comparison issue.
‫It's not a big deal.
‫You know, we could just switch to size, but we're never going to reach that size anyway.
‫And this is just to demonstrate the creation of a heap.
‫So we're going to go E-Plus plus plus.
‫OK, so what this will do is it's a loop from a starting block to the end of the table, and that's
‫exactly what we want.
‫OK, because we're free and from the starting block and we don't know how many blocks we need to free.
‫So we loop from the starting block to the end of the entry table and now we're just going to go keep
‫block entry.
‫He block table entry.
‫Entry equals table entries.
‫I and just make sure you spelled that right.
‫OK, so we're now going to go table entries I equals he block table entry free so we set that entry
‫is free so it can be reused by Mallak.
‫Right.
‫Malac now knows it can return the address for the privacy return because we've just freed it.
‫OK, so we now need to know if we're ready to break out of the loop because obviously we don't want
‫to loop all the way to the end of the table and finally freed everyone's blocks, you know, so we need
‫to check for that flag, the states, if there's something next.
‫So this is very easy to do.
‫We just go if entry ampersand P Block has next and this will test that bed.
‫OK, and if you're not aware of what testing the bet is and stuff like this, you need to learn bitwise
‫operations because you're a little bit behind you.
‫You're not ready to continue until you know that it's not too difficult.
‫You could learn it in a day, learn about that bitwise operations if you don't know it.
‫Oh, and also you'll see here I made this a pointer.
‫Just get rid of that.
‫We don't want that as a pointer.
‫This is a literal value.
‫My bad.
‫So, yeah, if the entry does not have the has next bit set, then we break because we know we've just
‫reached the end of the application.
‫OK, and that is how we can break out of that them.
‫So we now scroll down, we can see that is all set up correctly and now we are ready to test this.
‫So in our keep tazi we're going to create Void Kifri and this is just going to accept void pointer here.
‫Right.
‫And all we're going to do is we're just going to go heap free pizza.
‫And obviously we need to pass in the kernel heap here as well.
‫So it's as simple as that, and if we know copy and paste free.
‫And criminal law, can the head of the prototype, we should now be able to use it, so we're going
‫to do now then we're going to create another point here.
‫Void point of three ECOSOC came Mallak five thousand six hundred.
‫Yeah.
‫And now we're going to go Kifri.
‫Peter and I were going to go Void's Peter for ECOSOC Mallock 50, OK, and now let's just add all of
‫those here to this statement so it doesn't cause Complera.
‫And now we should be able to see something pretty interesting, so if we if we now make clean and we
‫believe that I'm going to add those symbols again, add symbol file.
‫OK, uh, we're going to attach the virtual machine remembers i3 i3.
‫Remember, it's AI three eight six.
‫And now we're now going to break on Colonel C. Eighty-Nine.
‫And we're going to continue and we're now preempting.
‫We see that point or two, we see that point to three, we see that and now we freed appointer.
‫Remember that, right?
‫So if we now do point to four, you would expect to see one hundred four thousand one hundred four thousand.
‫But you won't.
‫You won't because we freed it.
‫So if we go print for you see the first hip address we started with, and that's because we k freed
‫the original pointer, which is this one.
‫So that block is now free and because we're only allocating a block fifty bytes, it'll, it'll obviously
‫scale it up to four thousand eighty six bytes.
‫As you know, the four thousand eighty six blocks.
‫But it'll give you the first block in the heap because we freed it online, this online 87 here you
‫see.
‫So you've now implemented your heap.
‫So congratulations on that because this is one of the most important parts of the kernel, if not the
‫most important part.
‫You can't really do anything decent without a heap.
‫A heap allows you to manage memory in a structured way.
‫It's very important.
‫So well done.
‫I know this was a mouthful, but you've done it.
‫Let's just delete these now because we don't need those now.
‫And yet that is done.
‫You've just implemented a heap.
‫If you run into any problems with this lecture, check back the check back on the presentation and check
‫back on this material.
‫And if you're still having trouble, send me a message with your specific problem that you're facing.
‫Um, I appreciate some of you might have run into problems with this is quite complicated subject.
‫And although Ahepe is not very big, one hundred eighty lines are obviously the logic here can be quite
‫confusing to some people.
‫So if the presentation didn't help clear up what we're doing and you're still struggling having an understanding
‫about this, just drop me a message in the Q&A rather than a personal message, because that way my
‫answer can help other people as well.