[PATCH v7 01/28] 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 4.2

Signed-off-by: Vijaya Kumar K <Vijaya.Kumar@caviumnetworks.com>
Acked-by: Jan Beulich <jbeulich@suse.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>
---
v5: Ported from Linux 4.2.
    Added bitmap_find_next_zero_area_off().
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      |   39 +++++++++++++++++++++++++++++++++++++++
 xen/include/xen/bitmap.h |   16 ++++++++++++++++
 xen/include/xen/lib.h    |    2 ++
 3 files changed, 57 insertions(+)

diff --git a/xen/common/bitmap.c b/xen/common/bitmap.c
index 61d1ea4..ad665d1 100644
--- a/xen/common/bitmap.c
+++ b/xen/common/bitmap.c
@@ -489,6 +489,45 @@ int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 }
 EXPORT_SYMBOL(bitmap_allocate_region);
 
+/*
+ * bitmap_find_next_zero_area_off - 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
+ * @align_offset: Alignment offset 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 plus @align_offset
+ * is multiple of that power of 2.
+ */
+unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
+					     unsigned long size,
+					     unsigned long start,
+					     unsigned int nr,
+					     unsigned long align_mask,
+					     unsigned long align_offset)
+{
+	unsigned long index, end, i;
+again:
+	index = find_next_zero_bit(map, size, start);
+
+	/* Align allocation */
+	index = ALIGN_MASK(index + align_offset, align_mask) - align_offset;
+
+	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_off)
+
 #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..161f990 100644
--- a/xen/include/xen/bitmap.h
+++ b/xen/include/xen/bitmap.h
@@ -101,6 +101,22 @@ 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_off(unsigned long *map,
+						    unsigned long size,
+						    unsigned long start,
+						    unsigned int nr,
+						    unsigned long align_mask,
+						    unsigned long align_offset);
+
+static inline unsigned long bitmap_find_next_zero_area(unsigned long *map,
+						       unsigned long size,
+						       unsigned long start,
+						       unsigned int nr,
+						       unsigned long align_mask)
+{
+	return bitmap_find_next_zero_area_off(map, size, start, nr,
+					      align_mask, 0);
+}
 
 #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