From 6e75f2dcda90e74dfeaa38430a08f747bf4e05fe Mon Sep 17 00:00:00 2001
From: Martin Decky <martin@decky.cz>
Date: Thu, 12 Sep 2013 13:45:34 +0200
Subject: [PATCH] optimize bitmap allocation using the next-fit algorithm

---
 kernel/generic/include/adt/bitmap.h |  2 ++
 kernel/generic/src/adt/bitmap.c     | 35 ++++++++++++++++++++++-------------
 2 files changed, 24 insertions(+), 13 deletions(-)

diff --git a/kernel/generic/include/adt/bitmap.h b/kernel/generic/include/adt/bitmap.h
index a70ca42f6..a8b0d85bf 100644
--- a/kernel/generic/include/adt/bitmap.h
+++ b/kernel/generic/include/adt/bitmap.h
@@ -43,6 +43,7 @@
 typedef struct {
 	size_t elements;
 	uint8_t *bits;
+	size_t next_fit;
 } bitmap_t;
 
 static inline void bitmap_set(bitmap_t *bitmap, size_t element,
@@ -58,6 +59,7 @@ static inline void bitmap_set(bitmap_t *bitmap, size_t element,
 		bitmap->bits[byte] |= mask;
 	} else {
 		bitmap->bits[byte] &= ~mask;
+		bitmap->next_fit = byte;
 	}
 }
 
diff --git a/kernel/generic/src/adt/bitmap.c b/kernel/generic/src/adt/bitmap.c
index cf768e43e..af2a67263 100644
--- a/kernel/generic/src/adt/bitmap.c
+++ b/kernel/generic/src/adt/bitmap.c
@@ -99,6 +99,7 @@ void bitmap_initialize(bitmap_t *bitmap, size_t elements, void *data)
 {
 	bitmap->elements = elements;
 	bitmap->bits = (uint8_t *) data;
+	bitmap->next_fit = 0;
 }
 
 /** Set range of bits.
@@ -115,6 +116,7 @@ void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)
 	if (count == 0)
 		return;
 	
+	size_t start_byte = start / BITMAP_ELEMENT;
 	size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
 	
 	/* Leading unaligned bits */
@@ -128,14 +130,14 @@ void bitmap_set_range(bitmap_t *bitmap, size_t start, size_t count)
 	
 	if (start + count < aligned_start) {
 		/* Set bits in the middle of byte. */
-		bitmap->bits[start / BITMAP_ELEMENT] |=
+		bitmap->bits[start_byte] |=
 		    ((1 << lub) - 1) << (start & BITMAP_REMAINER);
 		return;
 	}
 	
 	if (lub) {
 		/* Make sure to set any leading unaligned bits. */
-		bitmap->bits[start / BITMAP_ELEMENT] |=
+		bitmap->bits[start_byte] |=
 		    ~((1 << (BITMAP_ELEMENT - lub)) - 1);
 	}
 	
@@ -168,6 +170,7 @@ void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
 	if (count == 0)
 		return;
 	
+	size_t start_byte = start / BITMAP_ELEMENT;
 	size_t aligned_start = ALIGN_UP(start, BITMAP_ELEMENT);
 	
 	/* Leading unaligned bits */
@@ -181,14 +184,14 @@ void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
 	
 	if (start + count < aligned_start) {
 		/* Set bits in the middle of byte */
-		bitmap->bits[start / BITMAP_ELEMENT] &=
+		bitmap->bits[start_byte] &=
 		    ~(((1 << lub) - 1) << (start & BITMAP_REMAINER));
 		return;
 	}
 	
 	if (lub) {
 		/* Make sure to clear any leading unaligned bits. */
-		bitmap->bits[start / BITMAP_ELEMENT] &=
+		bitmap->bits[start_byte] &=
 		    (1 << (BITMAP_ELEMENT - lub)) - 1;
 	}
 	
@@ -205,6 +208,8 @@ void bitmap_clear_range(bitmap_t *bitmap, size_t start, size_t count)
 		bitmap->bits[aligned_start / BITMAP_ELEMENT + i] &=
 		    ~((1 << tab) - 1);
 	}
+	
+	bitmap->next_fit = start_byte;
 }
 
 /** Copy portion of one bitmap into another bitmap.
@@ -268,9 +273,11 @@ int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base,
 	if (count == 0)
 		return false;
 	
-	size_t bytes = bitmap_size(bitmap->elements);
+	size_t size = bitmap_size(bitmap->elements);
 	
-	for (size_t byte = 0; byte < bytes; byte++) {
+	for (size_t pos = 0; pos < size; pos++) {
+		size_t byte = (bitmap->next_fit + pos) % size;
+		
 		/* Skip if the current byte has all bits set */
 		if (bitmap->bits[byte] == ALL_ONES)
 			continue;
@@ -287,24 +294,26 @@ int bitmap_allocate_range(bitmap_t *bitmap, size_t count, size_t base,
 				continue;
 			
 			if (!bitmap_get_fast(bitmap, i)) {
-				bool continuous = true;
+				size_t continuous = 1;
 				
 				for (size_t j = 1; j < count; j++) {
-					if ((i + j >= bitmap->elements) ||
-					    (bitmap_get_fast(bitmap, i + j))) {
-						continuous = false;
+					if ((i + j < bitmap->elements) &&
+					    (!bitmap_get_fast(bitmap, i + j)))
+						continuous++;
+					else
 						break;
-					}
 				}
 				
-				if (continuous) {
+				if (continuous == count) {
 					if (index != NULL) {
 						bitmap_set_range(bitmap, i, count);
+						bitmap->next_fit = i / BITMAP_ELEMENT;
 						*index = i;
 					}
 					
 					return true;
-				}
+				} else
+					i += continuous;
 			}
 		}
 	}
-- 
2.11.4.GIT