2.6.9

 lib

diff -Nru a/lib/bitmap.c b/lib/bitmap.c
--- a/lib/bitmap.c   2004-10-18 14:56:49 -07:00
+++ b/lib/bitmap.c   2004-10-18 14:56:49 -07:00
@@ -408,3 +408,85 @@
    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);