X-Git-Url: http://git.onelab.eu/?a=blobdiff_plain;f=lib%2Fbitmap.c;h=f7414e7fd04611739df4f4cc495e8b0f59e352aa;hb=af20d436230b2df6d73a406b6f1b31ae000775cb;hp=7eb16be309b5ff1fa1155d98b70fbbc7e39ffcd7;hpb=9bf4aaab3e101692164d49b7ca357651eb691cb6;p=linux-2.6.git

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 7eb16be30..f7414e7fd 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -9,7 +9,7 @@
 #include <linux/ctype.h>
 #include <linux/errno.h>
 #include <linux/bitmap.h>
-#include <asm/bitops.h>
+#include <linux/bitops.h>
 #include <asm/uaccess.h>
 
 /*
@@ -408,3 +408,85 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_parse);
+
+/**
+ *	bitmap_find_free_region - find a contiguous aligned mem region
+ *	@bitmap: an array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *	@order: region size to find (size is actually 1<<order)
+ *
+ * This is used to allocate a memory region from a bitmap.  The idea is
+ * that the region has to be 1<<order sized and 1<<order aligned (this
+ * makes the search algorithm much faster).
+ *
+ * The region is marked as set bits in the bitmap if a free one is
+ * found.
+ *
+ * Returns either beginning of region or negative error
+ */
+int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
+{
+	unsigned long mask;
+	int pages = 1 << order;
+	int i;
+
+	if(pages > BITS_PER_LONG)
+		return -EINVAL;
+
+	/* make a mask of the order */
+	mask = (1ul << (pages - 1));
+	mask += mask - 1;
+
+	/* run up the bitmap pages bits at a time */
+	for (i = 0; i < bits; i += pages) {
+		int index = i/BITS_PER_LONG;
+		int offset = i - (index * BITS_PER_LONG);
+		if((bitmap[index] & (mask << offset)) == 0) {
+			/* set region in bimap */
+			bitmap[index] |= (mask << offset);
+			return i;
+		}
+	}
+	return -ENOMEM;
+}
+EXPORT_SYMBOL(bitmap_find_free_region);
+
+/**
+ *	bitmap_release_region - release allocated bitmap region
+ *	@bitmap: a pointer to the bitmap
+ *	@pos: the beginning of the region
+ *	@order: the order of the bits to release (number is 1<<order)
+ *
+ * This is the complement to __bitmap_find_free_region and releases
+ * the found region (by clearing it in the bitmap).
+ */
+void bitmap_release_region(unsigned long *bitmap, int pos, int order)
+{
+	int pages = 1 << order;
+	unsigned long mask = (1ul << (pages - 1));
+	int index = pos/BITS_PER_LONG;
+	int offset = pos - (index * BITS_PER_LONG);
+	mask += mask - 1;
+	bitmap[index] &= ~(mask << offset);
+}
+EXPORT_SYMBOL(bitmap_release_region);
+
+int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
+{
+	int pages = 1 << order;
+	unsigned long mask = (1ul << (pages - 1));
+	int index = pos/BITS_PER_LONG;
+	int offset = pos - (index * BITS_PER_LONG);
+
+	/* We don't do regions of pages > BITS_PER_LONG.  The
+	 * algorithm would be a simple look for multiple zeros in the
+	 * array, but there's no driver today that needs this.  If you
+	 * trip this BUG(), you get to code it... */
+	BUG_ON(pages > BITS_PER_LONG);
+	mask += mask - 1;
+	if (bitmap[index] & (mask << offset))
+		return -EBUSY;
+	bitmap[index] |= (mask << offset);
+	return 0;
+}
+EXPORT_SYMBOL(bitmap_allocate_region);