[PATCH v4 01/17] xen/arm: Add bitmap_find_next_zero_area helper function

[vijay.kilari@gmail.com]

From: Vijaya Kumar K <Vijaya.Kumar@caviumnetworks.com>

bitmap_find_next_zero_area helper function will be used
by physical ITS driver. This is imported from linux

Signed-off-by: Vijaya Kumar K <Vijaya.Kumar@caviumnetworks.com>
CC: Ian Campbell <ian.campbell@citrix.com>
CC: Ian Jackson <ian.jackson@eu.citrix.com>
CC: Jan Beulich <jbeulich@suse.com>
CC: Keir Fraser <keir@xen.org>
CC: Tim Deegan <tim@xen.org>
---
v4: Removed spaces and added tabs
    Moved ALIGN macro to lib.h
v3: Moved changes to xen/common/bitmap.c and
    xen/include/xen/bitmap.h
---
 xen/common/bitmap.c      |   37 +++++++++++++++++++++++++++++++++++++
 xen/include/xen/bitmap.h |    5 +++++
 xen/include/xen/lib.h    |    2 ++
 3 files changed, 44 insertions(+)

diff --git a/xen/common/bitmap.c b/xen/common/bitmap.c
index 61d1ea4..77c68b0 100644
--- a/xen/common/bitmap.c
+++ b/xen/common/bitmap.c
@@ -489,6 +489,43 @@ int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 }
 EXPORT_SYMBOL(bitmap_allocate_region);
 
+/*
+ * bitmap_find_next_zero_area - find a contiguous aligned zero area
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @align_mask: Alignment mask for zero area
+ *
+ * The @align_mask should be one less than a power of 2; the effect is that
+ * the bit offset of all zero areas this function finds is multiples of that
+ * power of 2. A @align_mask of 0 means no alignment is required.
+ */
+unsigned long bitmap_find_next_zero_area(unsigned long *map,
+					 unsigned long size,
+					 unsigned long start,
+					 unsigned int nr,
+					 unsigned long align_mask)
+{
+	unsigned long index, end, i;
+again:
+	index = find_next_zero_bit(map, size, start);
+
+	/* Align allocation */
+	index = ALIGN_MASK(index, align_mask);
+
+	end = index + nr;
+	if (end > size)
+		return end;
+	i = find_next_bit(map, end, index);
+	if (i < end) {
+		start = i + 1;
+		goto again;
+	}
+	return index;
+}
+EXPORT_SYMBOL(bitmap_find_next_zero_area);
+
 #ifdef __BIG_ENDIAN
 
 void bitmap_long_to_byte(uint8_t *bp, const unsigned long *lp, int nbits)
diff --git a/xen/include/xen/bitmap.h b/xen/include/xen/bitmap.h
index e2a3686..238b976 100644
--- a/xen/include/xen/bitmap.h
+++ b/xen/include/xen/bitmap.h
@@ -101,6 +101,11 @@ extern int bitmap_scnlistprintf(char *buf, unsigned int len,
 extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
 extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
 extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
+extern unsigned long bitmap_find_next_zero_area(unsigned long *map,
+						unsigned long size,
+						unsigned long start,
+						unsigned int nr,
+						unsigned long align_mask);
 
 #define BITMAP_LAST_WORD_MASK(nbits)					\
 (									\
diff --git a/xen/include/xen/lib.h b/xen/include/xen/lib.h
index 4258912..e7d9d95 100644
--- a/xen/include/xen/lib.h
+++ b/xen/include/xen/lib.h
@@ -55,6 +55,8 @@
 
 #define ROUNDUP(x, a) (((x) + (a) - 1) & ~((a) - 1))
 
+#define ALIGN_MASK(x, mask) (((x) + (mask)) & ~(mask))
+
 #define reserve_bootmem(_p,_l) ((void)0)
 
 struct domain;
-- 
1.7.9.5