[08-pagealloc] Add freed memory to the beginning of the free block list

havensjg · havensjg · commit 491e0ece5f75 · 2024-05-09T08:33:09.000-04:00
diff --git a/08-pagealloc/readme.md b/08-pagealloc/readme.md
@@ -4,4 +4,4 @@ Uses the memory map information from the multiboot bootloader to initialize a pa
 
 Whenever pages are allocated, they are allocated from the end of the first free block of suitable size. The count of pages in the free block is decremented by the number of pages requested. If more than one page are requested, an entry is added into the multi-page allocation list, recording the number of pages allocated. If a free block no longer contains any pages, it is removed from the list.
 
-Whenever pages are freed, if the pages are directly after a free block, that block's page count is incremented by the allocation size retrieved from the multi-page allocation list. If the pages are directly before a free block, the base address is decreased to match the base address of the page and its page count increased by the allocation size. If two free blocks are found to be adjacent after the pages are freed, they are merged.
+Whenever pages are freed, if the pages are directly after a free block, that block's page count is incremented by the allocation size retrieved from the multi-page allocation list. If the pages are directly before a free block, the base address is decreased to match the base address of the page and its page count increased by the allocation size. If the freed pages are not adjacent to any other free block, a new free block is created and added to the front of the list so the freed memory is reused before the large blocks created by pgalloc_init. This should help reduce fragmentation in the free block list by using up smaller free blocks. If two free blocks are found to be adjacent after the pages are freed, they are merged.
diff --git a/08-pagealloc/src/pgalloc.c b/08-pagealloc/src/pgalloc.c
@@ -297,17 +297,13 @@ void pgfree(void *ptr) {
         /* Fill in the list entry */
         blk->base = base;
         blk->len = pages;
-        blk->next = NULL;
 
-        /* Add to the list */
-        if (blk != NULL) {
-            if (pgalloc_free_head == NULL) {
-                pgalloc_free_head = blk;
-            } else {
-                pgalloc_free_tail->next = blk;
-            }
+        /* Add to the front of the list. Due to how pgalloc works, this will give priority to previously used memory, which is usually closer in size than the free blocks created in pgalloc_init */
+        if (pgalloc_free_tail == NULL) {
             pgalloc_free_tail = blk;
         }
+        blk->next = pgalloc_free_head;
+        pgalloc_free_head = blk;
     }
 
     /* Merge if this makes the block adjacent to any others */

Original file line number	Diff line number	Diff line change
`@@ -4,4 +4,4 @@ Uses the memory map information from the multiboot bootloader to initialize a pa`
`4`	`4`
`5`	`5`	`Whenever pages are allocated, they are allocated from the end of the first free block of suitable size. The count of pages in the free block is decremented by the number of pages requested. If more than one page are requested, an entry is added into the multi-page allocation list, recording the number of pages allocated. If a free block no longer contains any pages, it is removed from the list.`
`6`	`6`
`7`		`-Whenever pages are freed, if the pages are directly after a free block, that block's page count is incremented by the allocation size retrieved from the multi-page allocation list. If the pages are directly before a free block, the base address is decreased to match the base address of the page and its page count increased by the allocation size. If two free blocks are found to be adjacent after the pages are freed, they are merged.`
	`7`	+Whenever pages are freed, if the pages are directly after a free block, that block's page count is incremented by the allocation size retrieved from the multi-page allocation list. If the pages are directly before a free block, the base address is decreased to match the base address of the page and its page count increased by the allocation size. If the freed pages are not adjacent to any other free block, a new free block is created and added to the front of the list so the freed memory is reused before the large blocks created by pgalloc_init. This should help reduce fragmentation in the free block list by using up smaller free blocks. If two free blocks are found to be adjacent after the pages are freed, they are merged.