Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Heap fragmentation problem in malloc #23

Closed
nuta opened this issue Sep 23, 2020 · 27 comments
Closed

Heap fragmentation problem in malloc #23

nuta opened this issue Sep 23, 2020 · 27 comments
Labels
Component: Standard Library Good First Issue Good for newcomers Type: Enhancement

Comments

@nuta
Copy link
Owner

nuta commented Sep 23, 2020

The current malloc() implementation uses a naive algorithm and it easily creates heap fragmentation. Obviously we need to fix this.

resea/libs/resea/malloc.c

Lines 66 to 88 in 93d3f4d

for (struct malloc_chunk *chunk = chunks; chunk; chunk = chunk->next) {
ASSERT(chunk->magic == MALLOC_FREE || chunk->magic == MALLOC_IN_USE);
if (chunk->magic != MALLOC_FREE) {
continue;
}
struct malloc_chunk *allocated = NULL;
if (chunk->capacity > size + MALLOC_FRAME_LEN) {
allocated = split(chunk, size);
} else if (chunk->capacity >= size) {
allocated = chunk;
}
if (allocated) {
allocated->magic = MALLOC_IN_USE;
allocated->size = size;
memset(allocated->underflow_redzone, MALLOC_REDZONE_UNDFLOW_MARKER,
MALLOC_REDZONE_LEN);
memset(&allocated->data[allocated->capacity],
MALLOC_REDZONE_OVRFLOW_MARKER, MALLOC_REDZONE_LEN);
return allocated->data;
}
}

@nuta
Copy link
Owner Author

nuta commented Oct 12, 2020 •
edited
Loading

Using multiple bins might mitigate fragmentations.

In the current malloc implementation, there's only one bin (or aka free list) chunks:

resea/libs/resea/malloc.c

Line 8 in 93d3f4d

static struct malloc_chunk *chunks = NULL;

chunks is a linked list of unused (free) memory regions. If malloc is called, it searches the bin (chunks) for a sufficiently large chunk (first-fit), split the chunk into the allocated chunk and the remaining chunk, and lastly returns the pointer to the allocated chunk:

(1) Look for the search

          +-----------------+
prev -->  |   free chunk A  |  --> next free chunk
          +-----------------+

(2) Split the found chunk A into new two chunks A' and B'

          +-------+  +------+
prev -->  |   A'  |  |  B'  |  --> next free chunk
          +-------+  +------+

(3) Remove B' from the free list (`chunks`)

          +------+
prev -->  |  A'  |  --> next free chunk
          +------+

Multiple bins, as its name suggests, malloc has multiple chunks (i.e. static struct malloc_chunk *chunks[NUM_CHUNKS]). Each bin has predefined-sized chunks (8 byte, 16 bytes, 64 bytes, 256 bytes, 4096 bytes, and bigger than 4096 bytes, for example).

In multiple bins approach, malloc does not split the chunk except ones in the bin for remaining big ones. That is, once a chunk splitted into 16 bytes long, it will be in the bin for 16-bytes chunks forever.

I believe this approach work well.

@yashrajkakkad
Copy link
Contributor

Thank you for the wonderful explanation. I have a quick question. Pardon me if this is naive. Do we decide the number of chunks of sizes 8 bytes, 16 bytes etc. beforehand? Also, are all malloc requests multiple of 8 bytes in resea as described in the page you linked? If not, we still have some internal fragmentation there right?

@nuta
Copy link
Owner Author

nuta commented Oct 14, 2020

Do we decide the number of chunks of sizes 8 bytes, 16 bytes etc. beforehand?

Yes. We don't need to change the size of chunk in each bin dynamically. I recommend using power of 2 for chunk sizes and since existing Resea applications don't need large chunks, I suppose 16 is a good number of bins (i.e. the first bin have 2^0 == 1-sized chunks, the second largest bin have 2^14 == 16384-sized chunks, and the last bin have any bigger chunks). Of course I welcome other ideas.

If not, we still have some internal fragmentation there right?

Good point. Internal fragmentation is still inevitable in this multiple bins approach. To eliminate internal fragmentation, I think we need another solution such as the slab allocator.

@yashrajkakkad
Copy link
Contributor

yashrajkakkad commented Oct 17, 2020 •
edited
Loading

chunks is a linked list of unused (free) memory regions.

Are all the chunks free? If so, why do we have the below condition in the loop -

            if (chunk->magic != MALLOC_FREE) {
                continue;
            }

Also, I am assuming that initially chunks will have one chunk whose size is equal to the size of the heap. So from what I understand, for our multiple bins approach, we have to choose among the following:

  • On request, check if there's a free chunk of the given size. If not, split the large chunk and put it in the list. This idea needs a bit of refinement.
  • Create some free chunks beforehand of various sizes and connect them via the free list. This approach might restrict the number of chunks of every size and therefore might not be very flexible.

@nuta
Copy link
Owner Author

nuta commented Oct 18, 2020

Are all the chunks free? If so, why do we have the below condition in the loop -

Seems you're right. All chunks in the chunks are free. I forgot to remove in-use chunks from chunks.

Also, I am assuming that initially chunks will have one chunk whose size is equal to the size of the heap. So from what I understand, for our multiple bins approach, we have to choose among the following:

That's correct. Initially, we have a single chunk which points to the whole heap.

On request, check if there's a free chunk of the given size. If not, split the large chunk and put it in the list. This idea needs a bit of refinement.

I think this way is better. As you say we might need further improvements around the splitting, but I suppose it's way better than the current first-fit approach.

@yashrajkakkad
Copy link
Contributor

Okay. So here's what I think we can do:

  • Create an array of chunks as you said
static struct malloc_chunk *chunks[NUM_CHUNKS]

  • When malloc() is called, the current algorithm will change in the following ways:

    • First check the list of the appropriate size if a free chunk is available. If there is, very good.
    • Otherwise, perform the same algorithm that exists for the last element of chunks array.
    • Remove used chunks from the free list.

  • When free() is called, the freed chunk will be appended to the appropriate list.

Please let me know your views and suggestions.

@nuta
Copy link
Owner Author

nuta commented Oct 18, 2020

Sounds good! Let's try it.

@nuta
Copy link
Owner Author

nuta commented Oct 18, 2020 •
edited
Loading

I have some comments regarding malloc tests.

  • Currently, we have no tests for malloc.
  • Futhermore, you can't use unit testing since it does not support testing the standard library (libs/resea).
  • To try running your mallloc, I recommend to add tests toservers/apps/test. You can automatically start the application by setting <*> to Servers and Applications > Applications > test - The integrated tests for kernel and standard library in make menuconfig.

@yashrajkakkad
Copy link
Contributor

Is there a way I can use ceil and log2 from standard math.h library? I intend to do something like below:

size_t get_chunk_number_from_size(size_t size) {
    // If requested size is less or equal to the size of second largest chunk
    // (the last fixed chunk)
    if (size <= 1 << (NUM_CHUNKS - 2)) {
        return ceil(log2(size));
    }
    // Return index of the last, dynamic-sized chunk
    return NUM_CHUNKS - 1;
}

@yashrajkakkad
Copy link
Contributor

About the tests, noted! Let me try to figure out how to write proper tests. (I have written unittests for Django REST APIs in the past)

@nuta
Copy link
Owner Author

nuta commented Oct 18, 2020

log2 has been deleted because it was no longer used. It might be good idea to re-add it to libs/resea.

Since size is an integer, I believe there're clever algorithm using bitwise operators. That said, as the first step, how about a naive implementation using a for loop like:

size_t get_chunk_number_from_size(size_t size) {
     for (int i = 0; i < NUM_CHUNKS; i++) {
         if (size <= 1 << i) {
            return i;
        }
     }

     return NUM_CHUNKS - 1;
 }

@yashrajkakkad
Copy link
Contributor

Okay yes. This sounds fair for a start. Once we get everything to work, we'll probably consider optimizing this. Thank you!

@yashrajkakkad
Copy link
Contributor

I added the function definition in test.h and added malloc_test.o in the associated build.mk file. Is that enough? I think my test is not running as even ASSERT(1==2) is not creating a warning.

I have implemented a malloc but as it crashed the OS I renamed it to mymalloc to test it properly first.

@nuta
Copy link
Owner Author

nuta commented Oct 20, 2020 via email

@yashrajkakkad
Copy link
Contributor

Yes, here's the branch we are working on - https://github.com/yashrajkakkad/resea/tree/malloc/libs/resea

malloc_test - https://github.com/yashrajkakkad/resea/blob/malloc/servers/apps/test/malloc_test.c
mymalloc - https://github.com/yashrajkakkad/resea/blob/malloc/libs/resea/mymalloc.c

@yashrajkakkad
Copy link
Contributor

Got the problem @nuta! I had forgotten to modify main.c. Meanwhile, how much memory does a typical resea application ask for as of now?

@yashrajkakkad
Copy link
Contributor

I have got the preliminary tests to work. You can find it in the same branch and the same files as I mentioned before. I found one or two small bugs when I gave my implementation a second thought. I am working on that.

Meanwhile, the MALLOC_FRAME_LEN in my system is 64. I suppose that's a constant value. Is there any point therefore to have chunks smaller than that? The system crashes right now because ASSERT(len > MALLOC_FRAME_LEN) fails.

@nuta
Copy link
Owner Author

nuta commented Oct 22, 2020 via email •
edited
Loading

@yashrajkakkad
Copy link
Contributor

Apologies for the delayed response. I actually had misunderstood some part of the code. Nevertheless, I have fixed the impending issues, integrated my new malloc to our branch and the tests have passed too. I have used DBG statements to verify that the behaviour is as expected. Resea seems to work perfectly fine. I request you to glance at it once before I make a pull request: resea I, too, will meanwhile see if I find something wrong.

@yashrajkakkad
Copy link
Contributor

Two integrated tests are apparently failing in GitHub actions - https://github.com/yashrajkakkad/resea/runs/1315001384?check_suite_focus=true
One is related to DHCP and other is related to shell. I am not sure what I ended up breaking. I am trying to investigate into that as well.

@nuta
Copy link
Owner Author

nuta commented Oct 28, 2020 via email

@nuta
Copy link
Owner Author

nuta commented Oct 28, 2020 via email

@yashrajkakkad
Copy link
Contributor

They still fail with a timeout - https://github.com/yashrajkakkad/resea/runs/1320690388?check_suite_focus=true

Also, minlin application shows an error - 'Already exists' when I run it in my system. Rest looks fine. I did some debugging but nothing seems suspicious from my changes.

@yashrajkakkad
Copy link
Contributor

yashrajkakkad commented Oct 28, 2020 •
edited
Loading

Also, minlin application shows an error - 'Already exists' when I run it in my system. Rest looks fine. I did some debugging but nothing seems suspicious from my changes.

Please ignore this. This shows up in resea's master branch as well.

@nuta
Copy link
Owner Author

nuta commented Oct 30, 2020

If you think your implementation is ready for the review, please feel free to send a pull request even if some CI tests are failing. They could be newly discovered bugs thanks to your new malloc implementation.

@yashrajkakkad
Copy link
Contributor

Just did that! I request you to check!

nuta pushed a commit that referenced this issue Nov 9, 2020
@yashrajkakkad
Fix Issue #23 - Heap fragmentation problem in malloc (#27)
b5a9455
@nuta
Copy link
Owner Author

nuta commented Nov 18, 2020

Closed by #27

@nuta nuta closed this as completed Nov 18, 2020
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
Component: Standard Library Good First Issue Good for newcomers Type: Enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@nuta @yashrajkakkad