Question about JamesM heap, page aligned address

[skwee]

Sorry for asking it here, I don't know how to reach James, so James if you read this and can help me Ill appreciate it (others who might help, Ill appreciate it too!).

I don't like copy code, especially when I don't understand it. I see how someone did it and it gives me idea of how it should work and then I form my own solution. I'm now on the topic of heap in James's tutorial, and I have problem with page aligned allocation:

Code: Select all

static s32int find_smallest_hole(u32int size, u8int page_align, heap_t *heap)
{
    // Find the smallest hole that will fit.
    u32int iterator = 0;
    while (iterator < heap->index.size)
    {
        header_t *header = (header_t *)lookup_ordered_array(iterator, &heap->index);
        // If the user has requested the memory be page-aligned
        if (page_align > 0)
        {
            // Page-align the starting point of this header.
            u32int location = (u32int)header;
            s32int offset = 0;
            if ((location+sizeof(header_t)) & 0xFFFFF000 != 0)
                offset = 0x1000 /* page size */  - (location+sizeof(header_t))%0x1000;
            s32int hole_size = (s32int)header->size - offset;
            // Can we fit now?
            if (hole_size >= (s32int)size)
                break;
        }
        else if (header->size >= size)
            break;
        iterator++;
    }
    // Why did the loop exit?
    if (iterator == heap->index.size)
        return -1; // We got to the end and didn't find anything.
    else
        return iterator;
}

Well "location + sizeof.. & 0xFF ..." I understand, its just a check if the given address is already page aligned, but what happen if its not? What is offset and why we are subtracting it for hole size?

The same is going here:

Code: Select all

void *alloc(u32int size, u8int page_align, heap_t *heap)
{

    // Make sure we take the size of header/footer into account.
    u32int new_size = size + sizeof(header_t) + sizeof(footer_t);
    // Find the smallest hole that will fit.
    s32int iterator = find_smallest_hole(new_size, page_align, heap);
.....
    // If we need to page-align the data, do it now and make a new hole in front of our block.
    if (page_align && orig_hole_pos&0xFFFFF000)
    {
        u32int new_location   = orig_hole_pos + 0x1000 /* page size */ - (orig_hole_pos&0xFFF) - sizeof(header_t);
        header_t *hole_header = (header_t *)orig_hole_pos;
        hole_header->size     = 0x1000 /* page size */ - (orig_hole_pos&0xFFF) - sizeof(header_t);
        hole_header->magic    = HEAP_MAGIC;
        hole_header->is_hole  = 1;
        footer_t *hole_footer = (footer_t *) ( (u32int)new_location - sizeof(footer_t) );
        hole_footer->magic    = HEAP_MAGIC;
        hole_footer->header   = hole_header;
        orig_hole_pos         = new_location;
        orig_hole_size        = orig_hole_size - hole_header->size;
    }
.......
}

(I assume that orig_hole_pos & 0xFFF, is the same as orig_hole_pos % 0x1000)

Thanks a lot for help!

[JamesM]

Hi,

Sorry for asking it here, I don't know how to reach James, so James if you read this and can help me Ill appreciate it (others who might help, Ill appreciate it too!).

Don't worry, this is the correct place to ask it. You can also reach me via my email address, which is available on my website.

I don't like copy code, especially when I don't understand it. I see how someone did it and it gives me idea of how it should work and then I form my own solution. I'm now on the topic of heap in James's tutorial, and I have problem with page aligned allocation:

Code: Select all

static s32int find_smallest_hole(u32int size, u8int page_align, heap_t *heap)
{
    // Find the smallest hole that will fit.
    u32int iterator = 0;
    while (iterator < heap->index.size)
    {
        header_t *header = (header_t *)lookup_ordered_array(iterator, &heap->index);
        // If the user has requested the memory be page-aligned
        if (page_align > 0)
        {
            // Page-align the starting point of this header.
            u32int location = (u32int)header;
            s32int offset = 0;
            if ((location+sizeof(header_t)) & 0xFFFFF000 != 0)
                offset = 0x1000 /* page size */  - (location+sizeof(header_t))%0x1000;
            s32int hole_size = (s32int)header->size - offset;
            // Can we fit now?
            if (hole_size >= (s32int)size)
                break;
        }
        else if (header->size >= size)
            break;
        iterator++;
    }
    // Why did the loop exit?
    if (iterator == heap->index.size)
        return -1; // We got to the end and didn't find anything.
    else
        return iterator;
}

Well "location + sizeof.. & 0xFF ..." I understand, its just a check if the given address is already page aligned, but what happen if its not? What is offset and why we are subtracting it for hole size?

The same is going here:

Code: Select all

void *alloc(u32int size, u8int page_align, heap_t *heap)
{

    // Make sure we take the size of header/footer into account.
    u32int new_size = size + sizeof(header_t) + sizeof(footer_t);
    // Find the smallest hole that will fit.
    s32int iterator = find_smallest_hole(new_size, page_align, heap);
.....
    // If we need to page-align the data, do it now and make a new hole in front of our block.
    if (page_align && orig_hole_pos&0xFFFFF000)
    {
        u32int new_location   = orig_hole_pos + 0x1000 /* page size */ - (orig_hole_pos&0xFFF) - sizeof(header_t);
        header_t *hole_header = (header_t *)orig_hole_pos;
        hole_header->size     = 0x1000 /* page size */ - (orig_hole_pos&0xFFF) - sizeof(header_t);
        hole_header->magic    = HEAP_MAGIC;
        hole_header->is_hole  = 1;
        footer_t *hole_footer = (footer_t *) ( (u32int)new_location - sizeof(footer_t) );
        hole_footer->magic    = HEAP_MAGIC;
        hole_footer->header   = hole_header;
        orig_hole_pos         = new_location;
        orig_hole_size        = orig_hole_size - hole_header->size;
    }
.......
}

(I assume that orig_hole_pos & 0xFFF, is the same as orig_hole_pos % 0x1000)

Thanks a lot for help!

So first of all, there's a typo in the code on the website. It should be "& 0x00000FFF", not "& 0xFFFFF000". This has been mentioned by others, and I've updated the downloadable code but not the online code. Laziness is a disease.

Anyway, you appear to have got the point. To answer your question - if the address is not page aligned, and the user has requested it be page aligned, an offset is computed that will adjust the address so that it is page aligned.

That is, one can add the page size minus the offset into the page. That should get you to the next page boundary.

That is what this code does:

Code: Select all

offset = 0x1000 /* page size */  - (location+sizeof(header_t))%0x1000; <-- Index into current 4K block

I hope this explanation helps - that particular chapter isn't my finest piece of work and I'm fairly displeased with it. In the rewrite it will change completely.

Cheers,

James

[skwee]

Thanks a lot! I think I got it now!