From f842b6e30d7fec915211b97e654255a7b65f1dba Mon Sep 17 00:00:00 2001
From: Matthias Kruk <m@m10k.eu>
Date: Wed, 18 Sep 2019 16:13:21 +0900
Subject: [PATCH] Fix a bug in heap_grow() that would cause the heap list to be
 bent into a loop

---
 kernel/arch/heap.c | 62 ++++++++++++++++++++++++++++++++--------------
 1 file changed, 43 insertions(+), 19 deletions(-)

diff --git a/kernel/arch/heap.c b/kernel/arch/heap.c
index fa83b36..eac7d5d 100644
--- a/kernel/arch/heap.c
+++ b/kernel/arch/heap.c
@@ -16,6 +16,7 @@
  * along with Corax.  If not, see <http://www.gnu.org/licenses/>.
  */
 
+#include <corax/errno.h>
 #include <debug.h>
 #include "paging.h"
 #include "heap.h"
@@ -79,16 +80,23 @@ void heap_init(void *base, u32_t size)
 
 static int heap_grow(const u32_t size)
 {
-	struct heap_node *cur;
+	struct heap_node *last;
 	struct heap_node *new;
 	u32_t sreq;
+	u32_t allocated;
 	int ret_val;
 
 	new = NULL;
-	ret_val = 1;
+	ret_val = -ENOMEM;
+	allocated = 0;
 
-	/* add more pages to the pagedir */
+	last = (struct heap_node*)_kheap.h_base;
+
+	while(last->hn_next) {
+		last = last->hn_next;
+	}
 
+	/* add more pages to the pagedir */
 	for(sreq = ALIGN(size << 2, PAGE_SIZE); sreq > 0; sreq -= PAGE_SIZE) {
 		void *addr;
 
@@ -98,27 +106,35 @@ static int heap_grow(const u32_t size)
 			break;
 		}
 
-		if(!new) {
-			new = (struct heap_node*)addr;
-			cur = (struct heap_node*)_kheap.h_base;
+		if(!(last->hn_flags & FLAG_USED)) {
+			/* add memory to the last, unused node */
+			last->hn_size += PAGE_SIZE;
+			allocated += PAGE_SIZE;
+		} else {
+			/* add memory to a new node at the end */
 
-			new->hn_size = PAGE_SIZE - sizeof(*new);
-			new->hn_flags = 0;
-			new->hn_next = NULL;
+			if(!new) {
+				/* create the new node */
+				new = (struct heap_node*)addr;
 
-			/* add new node to the end of the heap */
-			while(cur->hn_next) {
-				cur = cur->hn_next;
-			}
+				new->hn_next = NULL;
+				last->hn_next = new;
 
-			cur->hn_next = new;
-		} else {
-			new->hn_size += PAGE_SIZE;
+				new->hn_size = PAGE_SIZE - sizeof(*new);
+				new->hn_flags = 0;
+			} else {
+				/* node has already been created - expand it */
+				new->hn_size += PAGE_SIZE;
+				allocated += PAGE_SIZE;
+			}
 		}
 	}
 
-	if(new) {
-		_kheap.h_size += new->hn_size;
+	_kheap.h_size += allocated;
+	_kheap.h_free += allocated;
+
+	/* return success if we allocated enough to satisfy the request */
+	if(size <= allocated) {
 		ret_val = 0;
 	}
 
@@ -136,6 +152,8 @@ void* kmalloc(u32_t size)
 		heap_grow(size);
 	}
 
+	heap_debug();
+
 	for(cur = (struct heap_node*)_kheap.h_base;
 		cur;
 		cur = cur->hn_next) {
@@ -158,7 +176,13 @@ void* kmalloc(u32_t size)
 
 			new = (struct heap_node*)(ret_val + size);
 
-			new->hn_size = cur->hn_size - size - (2 * sizeof(*new));
+			/*
+			 *       |<---       cur->hn_size      --->|
+			 * +-----+----------+-----+----------------+--------------+
+			 * | cur | < size > | new | <new->hn_size> | cur->hn_next |
+			 * +-----+----------+-----+----------------+--------------+
+			 */
+			new->hn_size = cur->hn_size - size - sizeof(*new);
 			new->hn_next = cur->hn_next;
 			new->hn_flags = 0;
 
-- 
2.47.3