The next challenge binary is difficult
and we'll need to learn one more piece of malloc internals: remaindering.
Remaindering is simply the term the malloc maintainers give to splitting one free chunk down into two,
then allocating one of those parts whilst the other part is returned to the free lists.
The 'how' of remaindering is relatively simple,
say we've requested a 0x100-sized chunk
but our arena only has a 0x300 chunk to give us.
malloc will unlink the 0x300 chunk from its free list, split a 0x100 chunk off of it,
link the so-called "remainder" into the head of the unsortedbin and allocate the 0x100 chunk.
The 'when' is more complicated, remaindering can occur at one of three points in the malloc flowchart.
It happens during allocations from the largebins which aren't covered
in part 1 of this course, and during something called a "binmap" search. You can see from the malloc
flowchart in your PDF that a binmap search is one of the last allocation paths before the top chunk
is used.
Binmap is a play on the word bitmap and it's quite literally a bitmap representing which of an arena's
bins may be occupied.
I say "may" because it's a lazy bitmap, meaning that a bit is only cleared when malloc attempts to allocate
from an empty bin during a binmap search.
The binmap itself resides towards the tail end of an arena, as you can see from the Arena Layout diagram.
A binmap search works like this:
malloc uses the binmap to find the next largest, occupied bin
with respect to the requested chunk size, then it remainders the last chunk in that bin.
When a chunk isn't large enough to be remaindered by a request and leave behind at least a minimum-sized
chunk,
this leads to so-called "exhausting".
If you requested an 0x80-sized chunk
but the arena only had a 0x90 chunk, malloc would exhaust that chunk and you'd be allocated the
whole 0x90 chunk.
This is one of the few times you won't get the exact chunk size you expected.
This brings us to the third point at which remaindering can occur; if a chunk was remaindered during a binmap
search and the request size was within smallbin range,
the arena's 'last_remainder' field is set.
You can see the last_remainder field in your Arena Layout diagram between the top chunk and the unsorted
bin fd.
The last_remainder field is just a pointer to the last chunk to get remaindered
and the last_remainder field works in conjunction with the unsortedbin. During an unsortedbin search
for a small chunk,
if the search gets to the last chunk in the unsortedbin and that chunk is also the last remainder,
then that chunk will be remaindered again
and the last_remainder field will be updated accordingly.
Oddly, chunks aren't exhausted from the last remainder, although you'll still witness the same outcome
as the chunk is sorted and then exhausted by the subsequent binmap search.
Let's briefly visit the malloc testbed once again to see remaindering in action.
Make another copy of the pwntools template and open it in your editor.
Keep the lines that request chunks A and B
and the line that frees chunk A, discard the rest.
Change chunk A's size to 0x1f8, which will yield a 0x200-sized chunk.
Remember, you can just subtract eight from your desired chunk size to get an appropriate request size
for that chunk.
Run your script with both the usual debugging options,
break and inspect the heap with 'vis', the output of which shows that we have a 0x200-sized unsorted
chunk on our heap.
'continue'
and switch to the program window where we'll use a request size of 0xf8 to allocate a 0x100-sized
chunk.
Return to GDB and break again,
at which point 'vis' shows us that the 0x200-sized chunk has been split in half, or remaindered, to service
our request.
The lower half in terms of address became the 0x100-sized chunk that we wanted, whilst the upper half
has been linked back into the unsortedbin, becoming the last remainder in the process.
Although it appears as though the 0x200 chunk was remaindered directly from the unsortedbin,
this isn't actually the case.
It was first sorted into the 0x200 smallbin,
then remaindered from there via a binmap search.
If we were to make a request for, say, an 0x80-sized chunk now, then the 0x100 chunk would be
remaindered directly from the unsortedbin because it's the last remainder.
Regardless, the final result is the same.
And while remaindering isn't a complicated procedure, there's a lot to remember in terms of when it
can happen.
So for the purpose of the next challenge binary, we can think of remaindering simply as "malloc will split
apart free chunks to service a request if it can't find an exact fit."
If you want to refresh your memory on remaindering, there's a 'Remaindering' section in your HeapLAB PDF, and
I would also suggest using the malloc testbed to follow the remaindering process.
Don't forget that each version of GLIBC in the course material is packaged with its malloc source
code, which means if you set a breakpoint on the malloc() function, you can trace through the source
and identify the path through malloc() your requests are taking.
Once you're comfortable with the basics of remaindering, you're ready to take on the final challenge
binary,
so I'll see you in the next video.