‫Understanding the heap, so firstly, what is the heap?
‫The heap is a giant memory region that can be shared in a controlled manner.
‫You can ask the heap for memory and tell the heap when you're done with that memory heap.
‫Implementations are essential system memory manages.
‫So as you must be aware, the C programming language allows you to point at any address in memory,
‫regardless if you can access it or not.
‫This code will compile absolutely fine if I try to run it.
‫Obviously the program will crash.
‫However, when writing a colonel, this code will not crash because no restriction has been put in place.
‫So as you know, Mallock in returns, a memory address that we can write to, it becomes ours for a
‫temporary amount of time.
‫So here, for example, we ask the system for 50 bytes.
‫It returns a memory address such as this memory address that I've made up.
‫And we can then set that data 50 Bodsworth.
‫When you ask the system for memory, the system also ensures it never gives that memory address to somebody
‫else.
‫Likewise, free and see accepts the memory address that we want to free them marks the memory address
‫and all associated blocks is free.
‫And in the next time someone calls Marlock, we can safely end up with a previous address that was used.
‫So before we go any further, you must be aware of the memory limits for 32 bit kernel.
‫Whilst in protective mode, we have certain restrictions because the processor is in a 32 bit state.
‫We are running in a 32 bit mode.
‫We have access only to 32 bit memory addresses, allowing us to address to a maximum of four point two
‫nine gigabytes of RAM.
‫It does not matter how much ram you have installed in your system because we're in a 32 bit kernel,
‫we can only access up to four gigabytes.
‫So when you put up your system, the memory is in an initialized state, your bias will start initializing
‫certain pieces of memory and so on.
‫You end up with video memory that takes up portions of RAM hardware memory.
‫That takes the portions of RAM, unused parts of RAM that are available for us to use.
‫So, for example, there is an array of initialized memory available to us from this address here.
‫This can be a lot of memory available to us, or very little, depending on how much installed RAM we
‫have.
‫You should note that this address here is reserved.
‫This means the memory area we have at this address can give us a maximum of three point two, two gigabyte
‫for a machine with four gigabyte Ohia installed.
‫Attempting to use more memory than this could be problematic.
‫So a heap is essentially a giant piece of memory.
‫That's all it is.
‫So we can point Ahepe, at this address I mentioned here, the other initialised memory at this address
‫we can point to here, and then assuming you have four gigabytes installed, that gives us around three
‫gigabytes to play with.
‫So that's all a heap is.
‫It's just a giant memory region.
‫So we point we point Ahepe address here and we create a heap implementation that manages that heap memory,
‫that giant chunk of memory.
‫And that is what your heap is essentially.
‫So, for example, we could decide that we want a 100 megabyte heap and as long as we have 100 megabytes
‫of memory available to us, our people work absolutely fine.
‫So we can't just have that giant memory region.
‫We need to create a heap implementation that will make our work properly.
‫It'll keep track of what's already allocated, what needs to be allocated and so on.
‫The heap will be responsible for storing information in our kernel.
‫So if someone says, give me 50 bytes, we will find a memory address inside Ahepe region that's free
‫and we will give them that a memory address and say you can use this memory address up to this size.
‫Do not use more than this size.
‫That's what we can do.
‫They tell us they want 100 bytes of memory.
‫We find 100 bytes of memory for them.
‫That is what our people fermentation is for.
‫So simply put, our hyper fermentation will be responsible for managing this giant chunk of memory that
‫we call the heap.
‫So the simplest possible heap of fermentation is rather simple.
‫We find a state address so we can point it at this address, for example, and then any call Marlock
‫gets the current address stores it in a temporary variable called temp.
‫And now we increment the current address by the size provides a Marlock.
‫The temporary variable called temp that contains the allocated address is now returned.
‫The current address now contains the next address for Myalup to return one.
‫Madlock is called again.
‫So the benefits to this, it's incredibly easy to implement.
‫There is no easy Ahepe to make the negatives.
‫You can't actually release memory because we don't keep track of how the memory was allocated.
‫Being unable to free the memory will lead to memory leaks and eventually a system crash.
‫This is the CECO for the simplest possible implementation so we can see we have our current address.
‫This points to that giant memory region that I was talking about.
‫We then set a temp variable to the current address.
‫We increment the current address by the size provided to us.
‫The current address now points to the next memory region for the next person that calls mallock.
‫Right.
‫And we now return temp, which is the address that we allocated.
‫If you call Mallak and say you want 50 bytes, it will return this address here, the one that we've
‫written here.
‫And then the next address will be this address plus 50.
‫Right.
‫So the next person that calls Malac will get that address.
‫And obviously, Ofri, function here can't do anything because unfortunately, this heap urbanization
‫is far too simple for us to keep track and be able to free blocks.
‫A very poor implementation indeed.
‫OK, so how will our help implementation work?
‫We obviously want something we can allocate and free from.
‫Well, our human mentation will consist of a giant table which will describe a free piece of memory.
‫And in our system.
‫Right, that's how I was work.
‫So this table will be responsible for describing which memory is taken and which memory is free.
‫We will call this the entry table throughout the rest of this presentation.
‫So that only makes a part of our plantation.
‫We also need a pointer to a giant piece of free memory.
‫Again, that that address that I showed you here.
‫This address here will be where we where we will point that right and will give us around three gig
‫memory for a four gigabyte installed system.
‫So, yes, simply put, this pointer will point to that memory and we will call this the data pool.
‫If we set up our heat to be able to allocate 100 megabytes, then the heap data pool will be 100 megabytes
‫in size.
‫OK, our hip limitation will be block based, so each address return from Mallak will be aligned to
‫four thousand ninety six bytes and will at least be four thousand ninety six bytes in size.
‫So for example, if you request if you call Marlock and request 50 bytes, it will give you four thousand
‫ninety six bytes because that is the lowest block size we can give you for the memory you're asking
‫for.
‫So our entry table composes of an array of one by values that represent an entry in our heap.
‫Data pool array size is calculated by taking the data pool size and dividing it by our block size of
‫four thousand six bytes.
‫We are then left with the total number of entries we need in our array.
‫So for example, if you want a heap that can store 100 megabytes of data, then we do one hundred megabytes
‫divided by block size in our case block size four nine six and that will give us twenty five thousand
‫six hundred entries in our entry table because each entry is only one by.
‫That means our table will be twenty five thousand six hundred bytes in size and this entire table will
‫describe how the 100 megabytes is allocated and what is free in that heap data pool for us to allocate
‫to someone else.
‫If our data pool is at this address, then entry zero in our table will represent the same address.
‫This address here, zero zero one zero zero zero and so on.
‫Entry zero in our table will represent that address.
‫Entry one will represent the same address plus four thousand six bytes entry to will represent and she
‫ones address plus four thousand ninety six bytes.
‫So you can see how each entry is in charge of a form of a four thousand ninety six block chunk.
‫So as you know, each entry in our table is just one byte.
‫So we need to use bitwise logic to allow us to make use of that memory efficiently.
‫So the lower four bits in an entry in our table will represent the entry type.
‫We can discuss that more later.
‫The upper orbits are Flagg's describing our entry, so bits seven in our entry bytes is has NP and has
‫has n a set if the entry to the right of us is part of the application.
‫So for example, if we allocate entry zero in our way but it takes up two blocks, then entry zero will
‫have the has N flag set because block one will also be part of that application.
‫If block one is the last block of that allocation, then it has N flag will not be set before six in
‫this byte is the is first.
‫This is set.
‫If this is the first entry of our allocation, using these two bits helps describe how we should be
‫handling the memory.
‫These two bits are very important because it describes how long an allocation is and when an application
‫ends, which is essential for our heap.
‫These two bits represented with zero are not used.
‫Each entry byte in our table describes four thousand eighty six bytes of data in the heap data pool.
‫In my implementation, we only have two entry types.
‫We have the entry taken and the entry free.
‫If the entry is free, we can use it.
‫If the entry type is taken, we cannot.
‫The data pool is simply a raw flat array of thousands or millions of bytes that our heap implementation
‫can give to people who need memory.
‫Let's now discuss how we can create our own Marlock.
‫Firstly, we assume we set our heap data pool to point to this address zero one zero zero zero and so
‫on.
‫We assume our heap is 100 megabytes in.
‫We assume we have twenty five thousand six hundred entries in our entry table that describe our hundred
‫megabyte of data in the data pool.
‫As you know, this is calculated by taking the heap data size and divide it by our entry size of four
‫or four thousand ninety six, which gives us twenty five thousand six hundred entries that describe
‫the one hundred megabytes of memory.
‫So the memory allocation process will soon come to you.
‫However, this implementation can be written in less than two hundred lines of code, so just bear with
‫me.
‫The first thing we do is we take the size from Marlock and calculate how many blocks we need to allocate
‫for this size.
‫If the user asks for five thousand bytes, we will need to allocate eight thousand one hundred ninety
‫two bytes because our implementation works on four thousand ninety six byte blocks, eight thousand
‫one hundred ninety two bytes is two blocks.
‫We now check the entry table for the first answer we can.
‫We find that has a type of heat block table entry free, which means that the four thousand ninety six
‫block of memory that this entry represents is free for us to use since we require two blocks.
‫We also need to ensure the next entry is also free for use.
‫Otherwise we will need to discard the first block we found and lock in our table until we find at least
‫two blocks that are next to each other because we need two blocks to allocate five thousand bytes.
‫Once we have two blocks, we mark those blocks as taken.
‫We now return the absolute address that the starting block represents.
‫The calculation is the heap data postcard address i.e. zero one zero zero zero so on, plus the block
‫number multiplied by the block size.
‫That is the absolute address we return that the programmer who called Mallak can use.
‫So let's break this down a little bit then.
‫How do we find the total blocks where we know our block size is four thousand eighty six?
‫So we get the size provided to Marlock, for example, value five thousand.
‫We then align it to four thousand eighty six.
‫We then get the value eight thousand one hundred ninety two.
‫This is the code for doing that.
‫We use this modulus operator to get the remainder.
‫Now we just divide eight thousand one hundred ninety two by our block size of four thousand ninety six
‫eight thousand one hundred ninety two, divided by four thousand ninety six, gives us two two blocks
‫to allocate.
‫So now that we know that we need to find two blocks in our entry table that are free, take this example
‫and shootable.
‫I've made that up.
‫That is actually based on the bit mask's that I showed you previous in this presentation.
‫So obviously, these are the hexadecimal equivalents, so feel free to change them to binary to see
‫how this lines up properly.
‫So you see means the block is taken.
‫This is also the first block for this allocation and that this allocation has more blocks and is not
‫finished zero for one.
‫The block is taken.
‫This is the first block, but there's no more blocks for this allocation.
‫Zero eight one.
‫The block is taken.
‫We have more blocks for this allocation.
‫We are not the first block for this allocation.
‫Zero zero one.
‫The block is taken.
‫We are not the first block for this allocation and there are no more blocks for this allocation.
‫Zero zero zero.
‫The block is free.
‫However, we should always just check the lower four bits to see if it's free because technically the
‫upper Flagg's, the upper Flagg's could still be set and this should still be legal because the lower
‫four bits represent the type and the type tells us if it's free or not.
‫So here we can see that there's an allocation XXXI on what does this mean?
‫Block taken first.
‫This is the first block and we have more blocks for this allocation.
‫So, OK, so that tells us that, yeah.
‫Now we see XOX 81.
‫What does 81 mean block take and we have more blocks this allocation.
‫So we have two of those and then we have a zero zero one which ends that allocation.
‫So we can see that this allocation is four blocks in size.
‫And it ends with zero one, which which has the two topmost flags as zero, which means that we are
‫not the first block and there are no more blocks.
‫However, because the type is one, we are not a free block, but this basically means where the last
‫block and you can see this goes on and on and on.
‫OK, so let's not get ahead of ourselves.
‫We are looking to find two free blocks and the table.
‫So there's two free blocks.
‫We see two zeros.
‫Remember, zero means free if the lower phobics zero the blocks free.
‫So we found two free blocks.
‫Brillion, let's allocate them.
‫So we've now allocated them we've set the first bite in red here to see one, which means the block
‫is taken.
‫It is the first block of our allocation and we also have more blocks for this allocation.
‫And then we ended with a nice selection, which means this block has taken we are not the first block
‫and there are no more blocks which ends our allocation.
‫So step three, we now need to calculate the apps we address the program we can use based on these blocks
‫that we've calculated.
‫So how do we do that?
‫Well, no, the entries in our table start from from zero, just like in a race.
‫So the first highlighted byte zero one is that index 22 of our entry table or our entry table of rape.
‫So 22 multiplied by the block size of four thousand ninety six gives us ninety thousand one hundred
‫and twenty two decimal.
‫This is our Offset the Heap data pool starts at address zero one zero zero zero zero and so on.
‫So all we do is we add the 90000 one hundred and twenty two decimal to that number, giving us an absolute
‫address of zero x one or one 600 a this is the absolute address our my our mallock implementation has
‫found for us.
‫We now return the address and the program.
‫I can safely write our 5000 bytes to that address technically because it's allocated 8000 192 bytes
‫due to our four thousand ninety six block size, we can use up to eight thousand one hundred ninety
‫two bytes before overflowing into other people's memory.
‫However, the program the use mallock only one of five thousand bytes.
‫So for him to use more than that, it probably means there's a bug in his program.
‫So now let me explain how we can free.
‫Well, we calculate the block number based on the address provided to us, we can get more on that later.
‫It's not too difficult.
‫We go through the entry table, staying at the block number.
‫We have calculated and set each entry to zero zero zero until we reach the last block of the allocation.
‫And we know when we're at the last block of the allocation because it will not have the has ended set
‫in the entry byte, which means that there's no more nex next to us for this allocation.
‫Right.
‫There's no more blocks associated with this allocation.
‫So what are the advantages of our implementation?
‫It's faster to allocate blocks of memory.
‫We're not relying on linked lists here.
‫We just send indexes in an array.
‫These can be calculated very quick on the process because it's essentially just a multiplication the
‫size of the data type four for our array multiplied by the index.
‫It's not difficult.
‫It's also fast to free blocks of memory for the same reason I just mentioned.
‫We go back to the array.
‫We said at zero it can be written in undertones and lines.
‫This is easy to implement.
‫I know it sounds complicated, but it's easy to implement.
‫So the disadvantages of our implementation, we can allocate a memory blocks, meaning misalign sizes.
‫So, for example, back to the 5000 byte situation, we have to give it another fifteen, two, 2000
‫bytes for it to work in our implementation.
‫Now, obviously, there's a lot of advantages to using block size heap's.
‫They're faster, for example.
‫But you know, we do waste memory here.
‫While modern operating systems tend to do is is your use.
‫A program will have an internal heap and it will ask the operating system for more memory for those
‫bigger chunks, and then it will handle the memory in the user application using much smaller sized
‫blocks or a better implementation that's suited for smaller memory blocks.
‫That's usually how that works, whereas the kernel, he will be using the block sized implementation
‫that I've described here.
‫So another disadvantage of our implementation, memory fragmentation is possible.
‫Now, the memory fragmentation is basically when we have enough free memory to allocate some memory
‫for someone, but because of the way the memory is laid out, we can't actually give them the memory
‫they're asking for.
‫So, for example, let's say we had a heap that could only have four blocks of memory, right.
‫So let's say the first block is taken, the second block isn't, the third block is taken and the fourth
‫block isn't.
‫Now, we know there's two, three blocks of memory.
‫Right.
‫However, because they're not next to each other, we can safely give it one block a memory because
‫it will overflow and overwrite the block of memory that isn't ours.
‫So that's the memory fragmentation.
‫Right.
‫So you can help solve this problem by using paging however this works best and 64 bit implementations
‫because people having four gigabytes of memory is very common.
‫People having terabytes of memory is not very common.
‫So 64 bit implementations you can get around this memory fragmentation issue using paging and our 32
‫bit protective mode.
‫Colonel, it will be a little more tricky.
‫So we probably won't cover getting around that.
‫OK, I hope that explains the heap that we will be implementing in our colonel.