Changeset 64f3d3b in mainline

Timestamp:

2013-09-12T00:47:42Z (11 years ago)

Author:

Martin Decky <martin@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

3a0a4d8, 4a5f2b0

Parents:

33c058fe

Message:

basic optimizations of the bitmap allocator
(still not using the 2nd level bitmap)

Location:

kernel/generic

Files:

• include/adt/bitmap.h (modified) (1 diff)
• src/adt/bitmap.c (modified) (4 diffs)
• src/mm/frame.c (modified) (2 diffs)

kernel/generic/include/adt/bitmap.h

@@ -91 +91 @@
 
 extern int bitmap_allocate_range(bitmap_t *, size_t, size_t, size_t, size_t *);
-extern void bitmap_free_range(bitmap_t *, size_t, size_t);
 extern void bitmap_copy(bitmap_t *, bitmap_t *, size_t);
 

kernel/generic/src/adt/bitmap.c

@@ -56 +56 @@
 #define ALL_ZEROES  0x00
 
+/** Compute the size of a bitmap
+ *
+ * Compute the size of a bitmap that can store given number
+ * of elements.
+ *
+ * @param elements Number of elements to store.
+ *
+ * @return Size of the bitmap (in units of BITMAP_ELEMENT bits).
+ *
+ */
+static size_t bitmap_bytes(size_t elements)
+{
+        size_t bytes = elements / BITMAP_ELEMENT;
+        
+        if ((elements % BITMAP_ELEMENT) != 0)
+                bytes++;
+        
+        return bytes;
+}
+
+/** Compute the number of 2nd level blocks
+ *
+ * Compute the number of 2nd level blocks for a given number
+ * of elements.
+ *
+ * @param elements   Number of elements.
+ * @param block_size Number of elements in one block.
+ *
+ * @return Number of 2nd level blocks.
+ * @return Zero if block_size is zero.
+ *
+ */
+static size_t bitmap_blocks(size_t elements, size_t block_size)
+{
+        if (block_size == 0)
+                return 0;
+        
+        size_t blocks = elements / block_size;
+        
+        if ((elements % block_size) != 0)
+                blocks++;
+        
+        return blocks;
+}
+
+/** Unchecked version of bitmap_get()
+ *
+ * This version of bitmap_get() does not do any boundary checks.
+ *
+ * @param bitmap  Bitmap to access.
+ * @param element Element to access.
+ *
+ * @return Bit value of the element in the bitmap.
+ *
+ */
+static unsigned int bitmap_get_fast(bitmap_t *bitmap, size_t element)
+{
+        return !!((bitmap->bits)[element / BITMAP_ELEMENT] &
+            (1 << (element & BITMAP_REMAINER)));
+}
+
 /** Get bitmap size
  *
@@ -69 +130 @@
 size_t bitmap_size(size_t elements, size_t block_size)
 {
-        size_t size = elements / BITMAP_ELEMENT;
-        
-        if ((elements % BITMAP_ELEMENT) != 0)
-                size++;
-        
-        if (block_size > 0) {
-                size += elements / block_size;
-                
-                if ((elements % block_size) != 0)
-                        size++;
-        }
-        
-        return size;
+        size_t blocks = bitmap_blocks(elements, block_size);
+        
+        return (bitmap_bytes(elements) + bitmap_bytes(blocks));
 }
 
@@ -316 +367 @@
                 return false;
         
-        /*
-         * This is a trivial implementation that should be
-         * optimized further.
-         */
-        
-        for (size_t i = 0; i < bitmap->elements; i++) {
-                if (!constraint_satisfy(i, base, constraint))
+        size_t bytes = bitmap_bytes(bitmap->elements);
+        
+        for (size_t byte = 0; byte < bytes; byte++) {
+                /* Skip if the current byte has all bits set */
+                if (bitmap->bits[byte] == ALL_ONES)
                         continue;
                 
-                if (!bitmap_get(bitmap, i)) {
-                        bool continuous = true;
+                size_t byte_bit = byte * BITMAP_ELEMENT;
+                
+                for (size_t bit = 0; bit < BITMAP_ELEMENT; bit++) {
+                        size_t i = byte_bit + bit;
                         
-                        for (size_t j = 1; j < count; j++) {
-                                if ((i + j >= bitmap->elements) ||
-                                    (bitmap_get(bitmap, i + j))) {
-                                        continuous = false;
-                                        break;
+                        if (i >= bitmap->elements)
+                                break;
+                        
+                        if (!constraint_satisfy(i, base, constraint))
+                                continue;
+                        
+                        if (!bitmap_get_fast(bitmap, i)) {
+                                bool continuous = true;
+                                
+                                for (size_t j = 1; j < count; j++) {
+                                        if ((i + j >= bitmap->elements) ||
+                                            (bitmap_get_fast(bitmap, i + j))) {
+                                                continuous = false;
+                                                break;
+                                        }
+                                }
+                                
+                                if (continuous) {
+                                        if (index != NULL) {
+                                                bitmap_set_range(bitmap, i, count);
+                                                *index = i;
+                                        }
+                                        
+                                        return true;
                                 }
                         }
-                        
-                        if (continuous) {
-                                if (index != NULL) {
-                                        bitmap_set_range(bitmap, i, count);
-                                        *index = i;
-                                }
-                                
-                                return true;
-                        }
                 }
-                
         }
         
@@ -351 +411 @@
 }
 
-/** Clear range of set bits.
- *
- * This is essentially bitmap_clear_range(), but it also
- * checks whether all the cleared bits are actually set.
- *
- * @param bitmap Bitmap structure.
- * @param start  Starting bit.
- * @param count  Number of bits to clear.
- *
- */
-void bitmap_free_range(bitmap_t *bitmap, size_t start, size_t count)
-{
-        /*
-         * This is a trivial implementation that should be
-         * optimized further.
-         */
-        
-        for (size_t i = 0; i < count; i++) {
-                if (!bitmap_get(bitmap, start + i))
-                        panic("Freeing a bitmap range that is not set");
-        }
-        
-        bitmap_clear_range(bitmap, start, count);
-}
-
 /** @}
  */

kernel/generic/src/mm/frame.c

@@ -61 +61 @@
 #include <str.h>
 
-#define BITMAP_BLOCK_SIZE  1024
+#define BITMAP_BLOCK_SIZE  128
 
 zones_t zones;
@@ -352 +352 @@
         
         if (!--frame->refcount) {
-                bitmap_free_range(&zone->bitmap, index, 1);
+                bitmap_set(&zone->bitmap, index, 0);
                 
                 /* Update zone information. */